13 ms·

Future Directions for Optimizing Compilers

144 points by lifthrasiir 8y ago

mpweiher 8y ago
While the suggestions are definitely interesting, and the fact that compilation times are given proper attention is positive, it does seem to me that this is still pushing in the wrong direction, overall, of fully automatic optimization. We now have machines that are fast enough for many/most activities, as evidenced by production code that's written in Ruby, Python, JS, etc. For these we don't really need optimizations. On the other hand, performance critical routines tend to require human attention, and for these the approach of having the optimizations fully automated is generally less than helpful. As Knuth put it, in 1974 nonetheless: "For some reason we all (especially me) had a mental block about optimization, namely that we always regarded it a behind-the-scenes activity, to be done in the machine language, which the programmer isn’t supposed to know. This veil was first lifted from my eyes in the Fall of 1973. when I ran across a remark by Hoare [42] that, ideally, a language should be designed so that an optimizing compiler can describe its optimizations in the source language. Of course! Why hadn’t I ever thought of it? Once we have a suitable language, we will be able to have what seems to be emerging as the programming system of the future: an interactive program-manipulation system ..." -- http://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf http://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammin... So let's have systems/languages that allow us to express performance constraints and performance-oriented transformations, and let the compiler/language assist us in doing this.
- lifthrasiir 8y ago
  For what it's worth, the paper does acknowledge this view in the section 1.3 (and your quote of Knuth does appear in a Bernstein's talk, referenced from that section). The main reason the authors still pursue this direction is, to my best understanding, that: * As you pointed out, we are moving to higher-level constructs and languages (this is directly addressed by a Pugh's talk as well); and * "[...] in any case getting high-performance executables out of high-level languages seems to fundamentally require aggressive compiler optimization". In the other words, the widespread use of higher-level languages does not prove that the (automatic) optimization is not needed, but rather that the needs for higher-level languages are very high despite of the cost. And indeed, all languages you've mentioned have highly optimized interpreters or JIT compilers, albeit crafted by humans. I also feel that the paper importantly discusses the speed and correctness of code optimization along with the resulting optimized code (Thesis 1), and it is not just for the fully-automatic optimizer as you detest. The correctness of such program transformations will eventually require many tools mentioned in the paper.
  - mpweiher 8y ago
    > section 1.3 I missed the reference to Bernstein (and Pugh), thanks! Though they seem to think he was kidding. I don't think so. A little tongue-in-cheek, maybe, but not kidding, because what Bernstein and Pugh discuss are very real. Most code is cold, most optimizations here are a waste of compiler resources, better to compile to a simple/compact bytecode to keep code-densities high and memory clean. (See also Google's recent experience with re-implementing their JS engines). Some code is hot, here most compilers are not good enough, though we will take what they can give us, not necessarily because you need assembler (as Bernstein says), but because higher level optimizations that do 100x - 1000x are needed when coming from high-level code. Often, the "cold" code is setup code, whereas the hot code is in loops that get run once set up, see the Scripted Components pattern. Of course, once you follow that pattern, you run into the Two Languages problem that Julia is trying to solve. > getting high-performance executables out of high-level languages seems to fundamentally require aggressive compiler optimization". If you (a) treat the compiler (or runtime) as a black box and (b) don't permit multiple levels (as per Knuth) than I agree, sort of. Except that you don't actually reliably get high performance that way. You may sometimes get high peak performance, if you're lucky. Now they seem to argue that their approach would do away with the variability of that approach, by consistently/reliably burning through layers of abstraction. "finding optimizations using aggressive search algorithms and SMT solvers that are, unlike humans, not easy to fool with superficial changes of representation." I wish them cough sufficiently smart compiler cough luck, particularly when the goal is also to make/keep compile times reasonable. I also have a hard time with the phrase "unlike humans, not easy to fool", because what's easy to fool here is the compiler, and the "superficial changes of representation", as the changes needed are often not superficial. To me, an alternative solution to the the Scripted Components / Two Languages problem with progressive refinement and the ability to specify constraints seems like the right path. So instead of, for example, writing high level (OO?) code and hoping that the compiler/runtime will do the escape analysis and put things in registers instead of allocating them on the heap, you write the same code and then (a) specify that you don't want heap allocations in a particular region (b) have the compiler tell you whether that was possible and (c) assist you in putting in annotations/transformations that accomplish this goal and remain visible in the code, possibly separate from the other other code.
- deleted 8y ago
  [deleted]
- simias 8y ago
  That seems interesting in theory but I have a hard time imagining what it would look like in practice. In my experience micro-optimizing C code looks like what you describe: when you write your algorithm you have a pretty clear idea about what the machine code should look like. You compile it and check the assembly output to see if the compiler understood what you were going for. If it doesn't look like what you were expecting you need to make sure that the compiler didn't manage to actually generate better code than you exepected (because it might know things about the underlying architecture that you don't) and if it turns out that it's genuinely sub-optimal then you refactor your code a bit until you manage to get the compiler to do what you want. It can be a frustrating process. Now we do have a few language constructs to help us here, although sometimes it's not enough. We have inline, restrict, register as well, although that one is not really used a lot in practice in my experience (at least not for its original purpose). We have compiler extensions for computed GOTOs, alignment constraints etc... In this context what would "an interactive program-manipulation system" look like? Personally I think we could use more standardized constraints in languages like C to be able to annotate code in a way that could be useful to optimizer, such as tagging "cold" code, having control of the prefetcher and being able to write SIMD code without using intrinsics (a very complex problem admittedly). Standardizing computed gotos would be nice as well. Beyond that, in my experience a big problem with modern architectures is that it's very much non-trivial to figure out what's the fastest way to implement an algorithm. You have to consider which CPU model you're using, the cache architecture, RAM speed ... Second-guessing the compiler is pretty hard if you don't have a lot of experience optimizing for a particular architecture.
  - tonyg 8y ago
    > That seems interesting in theory but I have a hard time imagining what it would look like in practice. This is one of the properties that makes an idea a worthy research direction.
  - pjmlp 8y ago
    Only to be taken under our feet the moment the code gets compiled by another compiler, or updated version of the same one.
  - 8y ago
- userbinator 8y ago
  We now have machines that are fast enough for many/most activities, as evidenced by production code that's written in Ruby, Python, JS, etc. For these we don't really need optimizations. Only if you think that things like power savings and being able to run more on the same hardware are not important. https://en.wikipedia.org/wiki/Wirth%27s_law https://en.wikipedia.org/wiki/Wirth%27s_law
  - mpweiher 8y ago
    Oh, I think these things are important, but it's obvious that mine is not a majority opinion, otherwise pretty much all Python code would be running on PyPy, for example and there would be very little Rails in production. So machines are fast enough that a lot of people are happy making that trade-off, and it's hard to argue that they're all wrong. And of course they are also fast enough on single user machines (PCs, phones, tablets) that typical frameworks and 'best practices' often waste orders of magnitude of performance and developers don't even know or care to find out, and if they find out don't care enough to fix it.
    - jcelerier 8y ago
      > Oh, I think these things are important, but it's obvious that mine is not a majority opinion, otherwise pretty much all Python code would be running on PyPy, for example and there would be very little Rails in production. Pretty much everyone agrees that climate change is bad but if you base your ... say, meat consumption or car usage on what others do you are going to wait a long time
  - pcwalton 8y ago
    This ignores the rule of thumb that 90% of CPU time is spent in 10% of the code. It is completely pointless to optimize most high-level glue logic, for instance: even making it run 10x faster produces insignificant performance and power savings.
michaelmior 8y ago
> For these we don't really need optimizations. While it's true that many sites with high volume are written in high level languages, it's still true that these will require more CPU and memory than something which is highly optimized written in a lower level language. The trade-off is that it takes less developer time to write code in the high level language and the savings there are enough to invest in more computing power. However, if you can optimize code for high level languages even further, you're still reducing the hardware requirements and ultimately saving costs. If you can build a stable Ruby VM that runs with 10% fewer resources and is compatible with existing applications, I think you'll find people willing to throw money your way.
- userbinator 8y ago
  The trade-off is that it takes less developer time to write code in the high level language and the savings there are enough to invest in more computing power. Not if your application is being used by many users; optimising exclusively for development time is only for rarely-used/one-off things or if you don't value your user's time --- some of whom may be themselves developers. The more users you have, the more it matters. We've somehow gotten ourselves into a situation where relatively few developers are making countless more users waste time and hardware resources for their own selfish benefit, and I think that's a very bad thing.
  - pjmlp 8y ago
    I think it is a matter of saving resources on language design until it matters, not always a good decision. Take Java for example. When it came into scene we had Oberon and its variants, Ada, Modula-3 and Eiffel. All supported JIT/AOT compilation, value types, and with exception of Oberon, generics. Most of the last changes at the JVM level, and the upcoming ones on Java's roadmap are basically catching up with what was already possible in the mid-90's. So how much money could Sun, Oracle and IBM have saved if those features were there from the beginning? We will never know, but we will know how much the bill is going to be, given that it is 10+ year process currently. All because the current hardware changes make it impossible for Java to continue to ignore those features, if it is to stay relevant against other languages. Same applies to other languages in different ways.
delinka 8y ago
I think something like BOLT[1] has more promise. Now that I think about it, I'm curious if I take my unoptimized executable, generate the profile for BOLT, then apply BOLT's optimizations, is it possible to come out ahead of the Compiler+BOLT optimizations? 1 - https://github.com/facebookincubator/BOLT https://github.com/facebookincubator/BOLT
- dbaupp 8y ago
  Correct me if I'm wrong, but that architectually seems to be a conventional (profile-guided/feedback-driven) optimizing compiler, except the input "language" is machine code. For instance, it's peephole optimizations are also a chunk of hand-written C++ code (https://github.com/facebookincubator/BOLT/blob/2ed436a6d3b17044a8d230af7a73eaf7b7249e8c/src/Passes/BinaryPasses.cpp#L1047-L1147 https://github.com/facebookincubator/BOLT/blob/2ed436a6d3b17...), and thus could benefit just as much from the more declarative (and possibly SMT-driven) ideas in this paper. Finally, there's all sorts of optimizations that are only possible because of high-level information from the source language. For instance, removing unnecessary loads & stores requires knowing pointers don't alias, which is very difficult to deduce given unannotated integers (most of this is driven by language rules, such as the (controversial) TBAA in C). Additionally, even the BOLT paper itself mentions things that can be understood (and optimized for) from a higher-level language, but are much harder to deduce from a raw binary (Section 8): > Indirect tail calls are more challenging for static binary rewriters because it is difficult to guess if the target is another function or another basic block of the same function, which could affect the CFG And, the paper touches on your curiosity in the conclusion: > Nevertheless, a post-link optimizer has fewer optimizations than a compiler. We show that the strengths of both strategies combine instead of purely overlapping (Oh, one more post-finally thing, there's probably an argument to be had that BOLT fits into the (backend) superoptimizer category of the paper.)
  - delinka 8y ago
    BOLT’s input is machine code and a profile from running the executable in production. This definitely puts it outside the conventional optimizing compiler because the conventional compiler has no information about how the code will actually be executed.
ananya_muddu 8y ago
A friend recently defended his doctoral thesis on using constraint-based optimization in compiler backends (reg alloc and instr shed).
- ananya_muddu 8y ago
  Link to thesis: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-232192 http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-232192
  - CalChris 8y ago
    Lazano did the Unison combined RA + scheduler. Cool that he followed through and got his PhD. Register Allocation and Instruction Scheduling in Unison http://llvm.org/devmtg/2017-03//assets/slides/register_allocation_and_instruction_scheduling_in_unison.pdf http://llvm.org/devmtg/2017-03//assets/slides/register_alloc...
- DannyBee 8y ago
  Constraint based optimization in those areas is not actually that new, i've seen about 50 different approaches in the past 20 years ;P This one is somewhere in the middle, to be honest (no offense meant to your friend). I realize what people writing research papers have to deal with (really!), but the words "scales to 837 instructions" and "practical" should never appear in the same abstract. PBQP and friends can handle larger functions in better time bounds (and give near-optimal or optimal results for the problem they solve). This is one reason PBQP is actually part of LLVM mainline. Unison (the framework your friend uses), will never be part of LLVM (or GCC, or ...) unfortunately.
wiz21c 8y ago
A bit off topic, but how does one frame the difference between "compiler level optimisation" and "high level optimisation" ? I can sure make a difference between optimising for CPU cycles and optimizing a QuickSort pivot search, but I have hard times generalizing/formalizing that idea. It seems important to me because it would be needed to set realistic/measurable objectives on compilers.
- Q6T46nT668w6i3m 8y ago
  In my opinion, it’s mostly ambiguous. Most compiler optimization researcher focuses on particular programming languages and particular targets rather than denotational or operational semantics and abstract machines.
- CalChris 8y ago
  I think that high level optimization is a synonym for machine independent optimization. The classic example would be common subexpression elimination. Similarly compiler level is a synonym for low level, machine dependent code generation. An example would be peephole optimization. Front end vs back end.
  - masklinn 8y ago
    I don't know, HLO could also be language-level optimisations (specific based on known language semantics), while LLO would be IR-level optimisations (more generic and reusable).
BlackFingolfin 8y ago
Am I missing something, or is their example at the start of section 3 (bottom of page 7) plain wrong? If x is an uint32_t, then ((x << 31) >> 31) + 1 returns either 1 or 2; while the "optimized" version ~x&1 reutrns 1 or 0 (which matches the semantics they describe, while the initial code does not).
- jcdavis 8y ago
  If you look at the llvm IR, it is using ashr (arithmetic shift), so you can probably assume this isn't targeting unsigned types
  - Someone 8y ago
    The text also explicitly states this is about signed integers: ”let’s look at taking ((x << 31) >> 31) + 1, an inefficient idiom for isolating and flipping the low bit of a signed 32-bit integer” I think there is an error on page 9, though: ”Second, −a+−b can be rewritten as −(a − b)”. I think that should be either a left-hand side of ”-a--b” or a right-hand side of ”-(a + b)”.
stcredzero 8y ago
One thing I've been wondering about recently, is if we should have a compile-time vs. runtime distinction? What if the language was running on a tracing JIT, where the JIT output and runtime tracing from last time was cached and available immediately?
deleted 8y ago
[deleted]
carapace 8y ago
I've been working with compilation using Prolog (after Warren 1980 went by here on HN a month or so ago.[1]) Two things: 1) If you are writing a compiler and NOT using Prolog you are almost certainly working way too hard. 2) I think I can see an alternate reality where compiler-like software exists but high-level programming languages as such do not. [1] https://news.ycombinator.com/item?id=17674859 https://news.ycombinator.com/item?id=17674859
- dman 8y ago
  Anything publicly available?
  - carapace 8y ago
    I'm afraid my own work is yet inchoate, but there are decades of research. Here are some papers I've been looking at recently: "Logic Programming and Compiler Writing" David H. D. Warren (this is the kickoff.) "Parsing and Compiling Using Prolog" Jacques Cohen and Timothy J. Hickey "Provably Correct Code Generation: A Case Study" Qian Wang, Gopal Gupta "From Programs to Object Code and back again using Logic Programming: Compilation and Decompilation" Jonathan Peter Bowen "Automatic Derivation of Code Generators from Machine Descriptions" R. G. G. Cattell
- pjmlp 8y ago
  As Prolog fanboy I would put ML and Lisp on the list for compiler development as well. :)
- fooker 8y ago
  >If you are writing a compiler and NOT using Prolog you are almost certainly working way too hard. If you are trying to write a compiler for anything but a toy language in Prolog, you are going to be at it for far too long without getting anything done.

144 points by lifthrasiir 8y ago

While the suggestions are definitely interesting, and the fact that compilation times are given proper attention is positive, it does seem to me that this is still pushing in the wrong direction, overall, of fully automatic optimization. We now have machines that are fast enough for many/most activities, as evidenced by production code that's written in Ruby, Python, JS, etc. For these we don't really need optimizations. On the other hand, performance critical routines tend to require human attention, and for these the approach of having the optimizations fully automated is generally less than helpful. As Knuth put it, in 1974 nonetheless: "For some reason we all (especially me) had a mental block about optimization, namely that we always regarded it a behind-the-scenes activity, to be done in the machine language, which the programmer isn’t supposed to know. This veil was first lifted from my eyes in the Fall of 1973. when I ran across a remark by Hoare [42] that, ideally, a language should be designed so that an optimizing compiler can describe its optimizations in the source language. Of course! Why hadn’t I ever thought of it? Once we have a suitable language, we will be able to have what seems to be emerging as the programming system of the future: an interactive program-manipulation system ..." -- http://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf http://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammin... So let's have systems/languages that allow us to express performance constraints and performance-oriented transformations, and let the compiler/language assist us in doing this.

lifthrasiir 8y ago
For what it's worth, the paper does acknowledge this view in the section 1.3 (and your quote of Knuth does appear in a Bernstein's talk, referenced from that section). The main reason the authors still pursue this direction is, to my best understanding, that: * As you pointed out, we are moving to higher-level constructs and languages (this is directly addressed by a Pugh's talk as well); and * "[...] in any case getting high-performance executables out of high-level languages seems to fundamentally require aggressive compiler optimization". In the other words, the widespread use of higher-level languages does not prove that the (automatic) optimization is not needed, but rather that the needs for higher-level languages are very high despite of the cost. And indeed, all languages you've mentioned have highly optimized interpreters or JIT compilers, albeit crafted by humans. I also feel that the paper importantly discusses the speed and correctness of code optimization along with the resulting optimized code (Thesis 1), and it is not just for the fully-automatic optimizer as you detest. The correctness of such program transformations will eventually require many tools mentioned in the paper.
- mpweiher 8y ago
  > section 1.3 I missed the reference to Bernstein (and Pugh), thanks! Though they seem to think he was kidding. I don't think so. A little tongue-in-cheek, maybe, but not kidding, because what Bernstein and Pugh discuss are very real. Most code is cold, most optimizations here are a waste of compiler resources, better to compile to a simple/compact bytecode to keep code-densities high and memory clean. (See also Google's recent experience with re-implementing their JS engines). Some code is hot, here most compilers are not good enough, though we will take what they can give us, not necessarily because you need assembler (as Bernstein says), but because higher level optimizations that do 100x - 1000x are needed when coming from high-level code. Often, the "cold" code is setup code, whereas the hot code is in loops that get run once set up, see the Scripted Components pattern. Of course, once you follow that pattern, you run into the Two Languages problem that Julia is trying to solve. > getting high-performance executables out of high-level languages seems to fundamentally require aggressive compiler optimization". If you (a) treat the compiler (or runtime) as a black box and (b) don't permit multiple levels (as per Knuth) than I agree, sort of. Except that you don't actually reliably get high performance that way. You may sometimes get high peak performance, if you're lucky. Now they seem to argue that their approach would do away with the variability of that approach, by consistently/reliably burning through layers of abstraction. "finding optimizations using aggressive search algorithms and SMT solvers that are, unlike humans, not easy to fool with superficial changes of representation." I wish them cough sufficiently smart compiler cough luck, particularly when the goal is also to make/keep compile times reasonable. I also have a hard time with the phrase "unlike humans, not easy to fool", because what's easy to fool here is the compiler, and the "superficial changes of representation", as the changes needed are often not superficial. To me, an alternative solution to the the Scripted Components / Two Languages problem with progressive refinement and the ability to specify constraints seems like the right path. So instead of, for example, writing high level (OO?) code and hoping that the compiler/runtime will do the escape analysis and put things in registers instead of allocating them on the heap, you write the same code and then (a) specify that you don't want heap allocations in a particular region (b) have the compiler tell you whether that was possible and (c) assist you in putting in annotations/transformations that accomplish this goal and remain visible in the code, possibly separate from the other other code.
deleted 8y ago
[deleted]
simias 8y ago
That seems interesting in theory but I have a hard time imagining what it would look like in practice. In my experience micro-optimizing C code looks like what you describe: when you write your algorithm you have a pretty clear idea about what the machine code should look like. You compile it and check the assembly output to see if the compiler understood what you were going for. If it doesn't look like what you were expecting you need to make sure that the compiler didn't manage to actually generate better code than you exepected (because it might know things about the underlying architecture that you don't) and if it turns out that it's genuinely sub-optimal then you refactor your code a bit until you manage to get the compiler to do what you want. It can be a frustrating process. Now we do have a few language constructs to help us here, although sometimes it's not enough. We have inline, restrict, register as well, although that one is not really used a lot in practice in my experience (at least not for its original purpose). We have compiler extensions for computed GOTOs, alignment constraints etc... In this context what would "an interactive program-manipulation system" look like? Personally I think we could use more standardized constraints in languages like C to be able to annotate code in a way that could be useful to optimizer, such as tagging "cold" code, having control of the prefetcher and being able to write SIMD code without using intrinsics (a very complex problem admittedly). Standardizing computed gotos would be nice as well. Beyond that, in my experience a big problem with modern architectures is that it's very much non-trivial to figure out what's the fastest way to implement an algorithm. You have to consider which CPU model you're using, the cache architecture, RAM speed ... Second-guessing the compiler is pretty hard if you don't have a lot of experience optimizing for a particular architecture.
- tonyg 8y ago
  > That seems interesting in theory but I have a hard time imagining what it would look like in practice. This is one of the properties that makes an idea a worthy research direction.
- pjmlp 8y ago
  Only to be taken under our feet the moment the code gets compiled by another compiler, or updated version of the same one.
- 8y ago
userbinator 8y ago
We now have machines that are fast enough for many/most activities, as evidenced by production code that's written in Ruby, Python, JS, etc. For these we don't really need optimizations. Only if you think that things like power savings and being able to run more on the same hardware are not important. https://en.wikipedia.org/wiki/Wirth%27s_law https://en.wikipedia.org/wiki/Wirth%27s_law
- mpweiher 8y ago
  Oh, I think these things are important, but it's obvious that mine is not a majority opinion, otherwise pretty much all Python code would be running on PyPy, for example and there would be very little Rails in production. So machines are fast enough that a lot of people are happy making that trade-off, and it's hard to argue that they're all wrong. And of course they are also fast enough on single user machines (PCs, phones, tablets) that typical frameworks and 'best practices' often waste orders of magnitude of performance and developers don't even know or care to find out, and if they find out don't care enough to fix it.
  - jcelerier 8y ago
    > Oh, I think these things are important, but it's obvious that mine is not a majority opinion, otherwise pretty much all Python code would be running on PyPy, for example and there would be very little Rails in production. Pretty much everyone agrees that climate change is bad but if you base your ... say, meat consumption or car usage on what others do you are going to wait a long time
- pcwalton 8y ago
  This ignores the rule of thumb that 90% of CPU time is spent in 10% of the code. It is completely pointless to optimize most high-level glue logic, for instance: even making it run 10x faster produces insignificant performance and power savings.

michaelmior 8y ago

> For these we don't really need optimizations. While it's true that many sites with high volume are written in high level languages, it's still true that these will require more CPU and memory than something which is highly optimized written in a lower level language. The trade-off is that it takes less developer time to write code in the high level language and the savings there are enough to invest in more computing power. However, if you can optimize code for high level languages even further, you're still reducing the hardware requirements and ultimately saving costs. If you can build a stable Ruby VM that runs with 10% fewer resources and is compatible with existing applications, I think you'll find people willing to throw money your way.

userbinator 8y ago
The trade-off is that it takes less developer time to write code in the high level language and the savings there are enough to invest in more computing power. Not if your application is being used by many users; optimising exclusively for development time is only for rarely-used/one-off things or if you don't value your user's time --- some of whom may be themselves developers. The more users you have, the more it matters. We've somehow gotten ourselves into a situation where relatively few developers are making countless more users waste time and hardware resources for their own selfish benefit, and I think that's a very bad thing.
- pjmlp 8y ago
  I think it is a matter of saving resources on language design until it matters, not always a good decision. Take Java for example. When it came into scene we had Oberon and its variants, Ada, Modula-3 and Eiffel. All supported JIT/AOT compilation, value types, and with exception of Oberon, generics. Most of the last changes at the JVM level, and the upcoming ones on Java's roadmap are basically catching up with what was already possible in the mid-90's. So how much money could Sun, Oracle and IBM have saved if those features were there from the beginning? We will never know, but we will know how much the bill is going to be, given that it is 10+ year process currently. All because the current hardware changes make it impossible for Java to continue to ignore those features, if it is to stay relevant against other languages. Same applies to other languages in different ways.

delinka 8y ago

I think something like BOLT[1] has more promise. Now that I think about it, I'm curious if I take my unoptimized executable, generate the profile for BOLT, then apply BOLT's optimizations, is it possible to come out ahead of the Compiler+BOLT optimizations? 1 - https://github.com/facebookincubator/BOLT https://github.com/facebookincubator/BOLT

dbaupp 8y ago
Correct me if I'm wrong, but that architectually seems to be a conventional (profile-guided/feedback-driven) optimizing compiler, except the input "language" is machine code. For instance, it's peephole optimizations are also a chunk of hand-written C++ code (https://github.com/facebookincubator/BOLT/blob/2ed436a6d3b17044a8d230af7a73eaf7b7249e8c/src/Passes/BinaryPasses.cpp#L1047-L1147 https://github.com/facebookincubator/BOLT/blob/2ed436a6d3b17...), and thus could benefit just as much from the more declarative (and possibly SMT-driven) ideas in this paper. Finally, there's all sorts of optimizations that are only possible because of high-level information from the source language. For instance, removing unnecessary loads & stores requires knowing pointers don't alias, which is very difficult to deduce given unannotated integers (most of this is driven by language rules, such as the (controversial) TBAA in C). Additionally, even the BOLT paper itself mentions things that can be understood (and optimized for) from a higher-level language, but are much harder to deduce from a raw binary (Section 8): > Indirect tail calls are more challenging for static binary rewriters because it is difficult to guess if the target is another function or another basic block of the same function, which could affect the CFG And, the paper touches on your curiosity in the conclusion: > Nevertheless, a post-link optimizer has fewer optimizations than a compiler. We show that the strengths of both strategies combine instead of purely overlapping (Oh, one more post-finally thing, there's probably an argument to be had that BOLT fits into the (backend) superoptimizer category of the paper.)
- delinka 8y ago
  BOLT’s input is machine code and a profile from running the executable in production. This definitely puts it outside the conventional optimizing compiler because the conventional compiler has no information about how the code will actually be executed.

ananya_muddu 8y ago

A friend recently defended his doctoral thesis on using constraint-based optimization in compiler backends (reg alloc and instr shed).

ananya_muddu 8y ago
Link to thesis: http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-232192 http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-232192
- CalChris 8y ago
  Lazano did the Unison combined RA + scheduler. Cool that he followed through and got his PhD. Register Allocation and Instruction Scheduling in Unison http://llvm.org/devmtg/2017-03//assets/slides/register_allocation_and_instruction_scheduling_in_unison.pdf http://llvm.org/devmtg/2017-03//assets/slides/register_alloc...
DannyBee 8y ago
Constraint based optimization in those areas is not actually that new, i've seen about 50 different approaches in the past 20 years ;P This one is somewhere in the middle, to be honest (no offense meant to your friend). I realize what people writing research papers have to deal with (really!), but the words "scales to 837 instructions" and "practical" should never appear in the same abstract. PBQP and friends can handle larger functions in better time bounds (and give near-optimal or optimal results for the problem they solve). This is one reason PBQP is actually part of LLVM mainline. Unison (the framework your friend uses), will never be part of LLVM (or GCC, or ...) unfortunately.

wiz21c 8y ago

A bit off topic, but how does one frame the difference between "compiler level optimisation" and "high level optimisation" ? I can sure make a difference between optimising for CPU cycles and optimizing a QuickSort pivot search, but I have hard times generalizing/formalizing that idea. It seems important to me because it would be needed to set realistic/measurable objectives on compilers.

Q6T46nT668w6i3m 8y ago
In my opinion, it’s mostly ambiguous. Most compiler optimization researcher focuses on particular programming languages and particular targets rather than denotational or operational semantics and abstract machines.
CalChris 8y ago
I think that high level optimization is a synonym for machine independent optimization. The classic example would be common subexpression elimination. Similarly compiler level is a synonym for low level, machine dependent code generation. An example would be peephole optimization. Front end vs back end.
- masklinn 8y ago
  I don't know, HLO could also be language-level optimisations (specific based on known language semantics), while LLO would be IR-level optimisations (more generic and reusable).

BlackFingolfin 8y ago

Am I missing something, or is their example at the start of section 3 (bottom of page 7) plain wrong? If x is an uint32_t, then ((x << 31) >> 31) + 1 returns either 1 or 2; while the "optimized" version ~x&1 reutrns 1 or 0 (which matches the semantics they describe, while the initial code does not).

jcdavis 8y ago
If you look at the llvm IR, it is using ashr (arithmetic shift), so you can probably assume this isn't targeting unsigned types
- Someone 8y ago
  The text also explicitly states this is about signed integers: ”let’s look at taking ((x << 31) >> 31) + 1, an inefficient idiom for isolating and flipping the low bit of a signed 32-bit integer” I think there is an error on page 9, though: ”Second, −a+−b can be rewritten as −(a − b)”. I think that should be either a left-hand side of ”-a--b” or a right-hand side of ”-(a + b)”.

stcredzero 8y ago

One thing I've been wondering about recently, is if we should have a compile-time vs. runtime distinction? What if the language was running on a tracing JIT, where the JIT output and runtime tracing from last time was cached and available immediately?

deleted 8y ago

[deleted]

carapace 8y ago

I've been working with compilation using Prolog (after Warren 1980 went by here on HN a month or so ago.[1]) Two things: 1) If you are writing a compiler and NOT using Prolog you are almost certainly working way too hard. 2) I think I can see an alternate reality where compiler-like software exists but high-level programming languages as such do not. [1] https://news.ycombinator.com/item?id=17674859 https://news.ycombinator.com/item?id=17674859

dman 8y ago
Anything publicly available?
- carapace 8y ago
  I'm afraid my own work is yet inchoate, but there are decades of research. Here are some papers I've been looking at recently: "Logic Programming and Compiler Writing" David H. D. Warren (this is the kickoff.) "Parsing and Compiling Using Prolog" Jacques Cohen and Timothy J. Hickey "Provably Correct Code Generation: A Case Study" Qian Wang, Gopal Gupta "From Programs to Object Code and back again using Logic Programming: Compilation and Decompilation" Jonathan Peter Bowen "Automatic Derivation of Code Generators from Machine Descriptions" R. G. G. Cattell
pjmlp 8y ago
As Prolog fanboy I would put ML and Lisp on the list for compiler development as well. :)
fooker 8y ago
>If you are writing a compiler and NOT using Prolog you are almost certainly working way too hard. If you are trying to write a compiler for anything but a toy language in Prolog, you are going to be at it for far too long without getting anything done.