6 ms·

Question to pros: Things like constant propagation, loop unrolling, TCO, memory reuse etc., seem simple in theory. Yet why do languages end up depending on LLVM

Question to pros: Things like constant propagation, loop unrolling, TCO, memory reuse etc., seem simple in theory. Yet why do languages end up depending on LLVM and not implement these algorithms on their own and avoid a monstrous dependency? Like what exactly is the implementation of the top 20 optimizations? It can’t be that high right..

DannyBee 3y ago
Optimizer person here, who has implemented each of these at least 20 times each ;-) The tradeoffs and engineering are quite complex. The short answer is that the algorithms themselves are not the hard part. Compilers do not get better by magic algorithms most of the time, they get better by careful and hard tuning and testing (where are optimizations missed, what performance is lost or gained somewhere, etc). They get better 0.01% at a time over 20 years. There are no magic bullets, only really hard work. Those that try to implement these without LLVM discover it themselves, and either put in the work, or give up and realize it's better to reuse the work. I mean, don't get me wrong - we spend plenty of time reducing complexity of algorithms, etc. The difference between a textbook algorithm and one implemented in a production compiler is often the difference between a fisher price cell phone and and iphone. That isn't always true mind you (sparse constant prop is pretty simple in both cases), but it's often true. But this is applied engineering. For example, the SSA construction algorithm in LLVM is based on sreedhar and gao's linear time algorithm. The paper describes a mechanism that requires construction of separate data structures, is somewhat complex, etc. If you were to implement it straight out, it's pretty slow. Much slower than other mechanisms. LLVM's version is simple, 200 lines of code, and faster than just about any other algorithm you will find on both small and large functions. Oh, it also handles liveness pruning and works to compute both forward and reverse iterated dominance frontiers. See https://llvm.org/doxygen/GenericIteratedDominanceFrontier_8h_source.html https://llvm.org/doxygen/GenericIteratedDominanceFrontier_8h... Could language authors spend their time understanding the theory well enough to do this, reducing complexity, and engineering something that works as well. Sure, it's just software. Is it a good use of their time? Probably not. This did not come out of thin air like this either. It's based on 10+ years of people improving pieces of it, reducing complexity, reusing it elsewhere/etc. It's easy to look at it as having come this way fully formed, but it didn't ;) (in this particular case, even the in-llvm code history does not do it justice). Someday, I hope LLVM is not really necessary, whether it's because we can run the sorts of complex/combined algorithms and not worry about it, or because AI is good enough at approximating optimizing pipelines or whatever. But right now? if you want to compete on performance for real, you'd be hard pressed to do it.
astrange 3y ago
You'd need to reimplement LLVM code generation and all. These optimizations only work in that part of the compilation process; do it on your own IR and after lowering to LLVM you'll still want to do it again.
- jimsimmons 3y ago
  Let’s say I’m targeting x86 or PTX or some standard subo instruction set. I can do vanilla codegen but it is slow af
  - pertymcpert 3y ago
    But why would you when LLVM is there and will generate much better, much easier and very probably have fewer bugs than any custom one.
    - jimsimmons 3y ago
      Because I want to be self hosted
      - compiler-guy 3y ago
        Self-hosting llvm isn't all that hard. But you might possibly have found that one weird corner case where it doesn't make sense to depend on a mighty, highly-sophisticated, industrial-strength, extremely well tested and supported, nicely mature, compiler tooling framework. But that's a pretty big exception to most language implementers who get all of that and more for super-cheap compared to implementing it themselves.
        vidarh 3y ago
        Self hosted typically includes building the compiler in the language it compiles. E.g. my Ruby compiler is self hosted except for needing an assembler and linker (and I might get rid of that need too) and a minimal C library. If you're writing a C++ compiler, self-hosting LLVM might not be a massive additional complexity. For any other language it's not an option if self hosting is one of your goals.
mathisfun123 3y ago
>Like what exactly is the implementation of the top 20 optimizations? It can’t be that high right.. I love the full-throated arrogance of this - "I have no idea but I'm sure it's not hard" lol So I'll tell you - each pass is at minimum a paper (mem2reg) and at maximum several dissertations (polly) to understand. Then have fun implementing a basic basic alpha in your compiler that doesn't have all the creature comforts of LLVM - iterators, efficient data-structures, debugging aids, etc. And then give up because a paper or a dissertation is out-of-date like as soon as it's in deadtree form, while LLVM is a living, breathing, tapestry of insights, breakthroughs, and hacks too. I highly recommend you attempt even one pass to get a feel: pick any language that has a parser impl and design an IR for it and then optimize it (designing an IR from scratch can't be that hard can it?)
- jimsimmons 3y ago
  (tbc I was forthcoming with my arrogance, like it genuinely didn’t make sense to me) Why would constant propagation need a PhD level proficiency to implement? It’s basically running part of your code and no different from parsing. Again not trying to trivialize or be rude. I wish this was something I could ask ChatGPT and trust its outputs but you know I can’t
  - lemming 3y ago
    The Programmers’ Credo: we do these things not because they are easy, but because we thought they were going to be easy https://twitter.com/Pinboard/status/761656824202276864 https://twitter.com/Pinboard/status/761656824202276864
  - mathisfun123 3y ago
    >Why would constant propagation need a PhD level proficiency to implement? This is false premise or one of those other ones - constant prop might not be complex but constant prop isn't in the top 20 perf codegen relevant passes.
  - NavinF 3y ago
    > ask ChatGPT and trust its outputs If anyone's wondering, its response to the GP comment is 100% correct as far as I can tell. Only problem is that it's missing technical details and has a hard time giving specific examples. --- There are several reasons why programming languages might choose to rely on LLVM or other external compilers and optimization frameworks rather than implementing optimizations on their own: Focus on language design: Many programming languages prioritize language design and functionality over compiler optimization. Implementing optimizations can be a complex and time-consuming process, and language designers may prefer to focus on other aspects of the language. Difficulty of optimization: While some optimizations may seem simple in theory, they can be difficult to implement in practice, especially for complex programs. Additionally, different optimizations may interact with each other in unpredictable ways, making it challenging to optimize code effectively. Targeting multiple platforms: Many programming languages are designed to be portable and run on multiple platforms. Relying on external compilers and optimization frameworks like LLVM can help ensure that code is optimized for each platform without requiring extensive platform-specific optimizations. Access to expertise: Compiler optimization is a specialized field that requires a deep understanding of computer architecture, algorithms, and programming languages. By relying on external frameworks like LLVM, programming languages can leverage the expertise of experienced optimization engineers and researchers. As for the implementation of the top 20 optimizations, the specific details will depend on the optimization and the programming language being used. However, many optimizations involve analyzing the code to identify opportunities for improvement and then applying transformations to the code to make it more efficient. Some optimizations, like constant propagation and loop unrolling, may involve relatively simple transformations, while others, like register allocation and instruction scheduling, can be more complex. --- snippets from "Use highly technical details and examples to answer this question.": Memory reuse involves optimizing the use of memory to reduce the number of accesses and minimize cache misses. This can involve techniques such as loop-invariant code motion, which moves code that does not depend on loop variables outside of the loop, or loop fusion, which combines multiple loops that iterate over the same data into a single loop. However, these optimizations may also depend on the specific architecture being targeted, as the optimal memory access patterns may differ depending on the cache size and associativity Writing a high-quality compiler that can handle all of the edge cases and produce optimized code for a wide range of architectures requires a significant amount of expertise and resources. Additionally, using an external compiler can provide a degree of portability, as the same code can be compiled for multiple architectures without requiring changes to the code itself --- snippet from "Why would constant propagation need a PhD level proficiency to implement? It’s basically running part of your code and no different from parsing.": Constant propagation is indeed a relatively simple optimization technique in theory, and it does not require a PhD level proficiency to implement it. In fact, most compilers include some form of constant propagation as part of their optimization pipeline, and many of these implementations are relatively straightforward. However, there are several factors that can make constant propagation more challenging to implement in practice. Some of these factors include: Handling interactions with other optimizations: Constant propagation can interact with other optimizations in non-trivial ways, such as dead code elimination and loop unrolling. Ensuring that these optimizations work together correctly can require careful analysis and testing. Dealing with complex data structures: In some cases, constant propagation may need to deal with complex data structures, such as arrays or pointers. Ensuring that constant propagation works correctly in these cases can require more advanced techniques, such as dataflow analysis or points-to analysis. Supporting language features: Different programming languages may have different rules for when constant propagation is allowed or required. For example, some languages may allow constants to be defined using complex expressions or function calls, while others may require constants to be literal values. Supporting these language features can require additional analysis and code generation logic.
wyldfire 3y ago
The architecture specific backends are another significant part of the compiler, including architecture specific optimizations. I suppose one of the reasons you might think of the llvm project as monstrous is because it's feature-rich.
- jimsimmons 3y ago
  What if I care about like 4 archs: x86/64, arm64 and PTX
  - compiler-guy 3y ago
    Then you still have to do 4x the amount of work than you otherwise would. And when the next iteration of those chips become available, you will have to update your tooling yourself instead of get updated pipeline models for the cost of a source upgrade.
  - saagarjha 3y ago
    Your backend will probably be much worse than the one LLVM provides.
  - mananaysiempre 3y ago
    You might be underestimating the intricacy of the CPU models LLVM uses. If you want to see them in action, the same data drives llvm-mca[1], which given a loop body can tell you the throughput, latency, and microarchitectural bottlenecks (decoding, ports, dependencies, store forwarding, etc.)—if not always precisely, then still as well on average as, say, x86’s IACA, the tool written at Intel by people who presumably knew how those CPUs work, unlike LLVM contributors and the rest of us who can only guess and measure. This separately for Haswell, Sandy Bridge, Skylake, etc.; not “x86”. Now, is this the best model you can get? Not exactly[2], but it’s close enough to not matter. Do we often need machine code optimized that finely? Perhaps not[3], and if you’re using generic distro binaries, you’re not getting it, either. (Unlike Facebook, Google, etc., who know precisely what their servers have inside, and who fund or contribute sizable portions of this optimization work.) With that in mind you can shave at least a factor of ten off LLVM’s considerable bulk at the cost of 20—30% of performance[4,5]. But if you do want those as well, it seems that the complexity of LLVM is a fair price, or has the right order of magnitude at least. (Frontend not included, C++ frontend required to bootstrap sold separately, at a similar markup compared to a C-only frontend with somewhat worse ergonomics.) [1] https://llvm.org/docs/CommandGuide/llvm-mca.html https://llvm.org/docs/CommandGuide/llvm-mca.html [2] https://www.uops.info/ https://www.uops.info/ [3] https://briancallahan.net/blog/20211010.html https://briancallahan.net/blog/20211010.html [4] https://c9x.me/compile/ https://c9x.me/compile/ [5] https://drewdevault.com/talks/qbe.html https://drewdevault.com/talks/qbe.html
lanza 3y ago
> Yet why do languages end up depending on LLVM and not implement these algorithms on their own and avoid a monstrous dependency? That's like asking why construction companies rely on cranes, concrete and steel rebar when they can be using sticks, leaves and vine. LLVM is so mature that it's hard to improve it. If you don't care about the performance of your languages code then fine, use leaves and sticks and moderate winds will knock down your shelter.
- mathisfun123 3y ago
  Ya I was thinking about an analogy as I was writing my other response - thinking you're gonna make your life easier by reinventing LLVM is like those people that think they're gonna make their lives easier by freeing themselves of the encumbrances of `society` (by moving off-grid to middle of nowhere). I believe they quickly come to realize that `society` was invented for a reason.
WalterBright 3y ago
It turns out that many of the standard optimizations just don't work without a lot of extra work. For example, loop optimization algorithms don't take into account things like the loop induction variable changes may result in overflows. It just takes a while to figure out how to account for signed/unsigned, integral promotions, overflows, etc. Some optimizations also defeat other optimizations. For example, on the x86, various arithmetic operations can be combined into a single instruction. But common subexpression elimination can subvert it. It isn't always better to do common subexpression elimination.

DannyBee 3y ago

Optimizer person here, who has implemented each of these at least 20 times each ;-) The tradeoffs and engineering are quite complex. The short answer is that the algorithms themselves are not the hard part. Compilers do not get better by magic algorithms most of the time, they get better by careful and hard tuning and testing (where are optimizations missed, what performance is lost or gained somewhere, etc). They get better 0.01% at a time over 20 years. There are no magic bullets, only really hard work. Those that try to implement these without LLVM discover it themselves, and either put in the work, or give up and realize it's better to reuse the work. I mean, don't get me wrong - we spend plenty of time reducing complexity of algorithms, etc. The difference between a textbook algorithm and one implemented in a production compiler is often the difference between a fisher price cell phone and and iphone. That isn't always true mind you (sparse constant prop is pretty simple in both cases), but it's often true. But this is applied engineering. For example, the SSA construction algorithm in LLVM is based on sreedhar and gao's linear time algorithm. The paper describes a mechanism that requires construction of separate data structures, is somewhat complex, etc. If you were to implement it straight out, it's pretty slow. Much slower than other mechanisms. LLVM's version is simple, 200 lines of code, and faster than just about any other algorithm you will find on both small and large functions. Oh, it also handles liveness pruning and works to compute both forward and reverse iterated dominance frontiers. See https://llvm.org/doxygen/GenericIteratedDominanceFrontier_8h_source.html https://llvm.org/doxygen/GenericIteratedDominanceFrontier_8h... Could language authors spend their time understanding the theory well enough to do this, reducing complexity, and engineering something that works as well. Sure, it's just software. Is it a good use of their time? Probably not. This did not come out of thin air like this either. It's based on 10+ years of people improving pieces of it, reducing complexity, reusing it elsewhere/etc. It's easy to look at it as having come this way fully formed, but it didn't ;) (in this particular case, even the in-llvm code history does not do it justice). Someday, I hope LLVM is not really necessary, whether it's because we can run the sorts of complex/combined algorithms and not worry about it, or because AI is good enough at approximating optimizing pipelines or whatever. But right now? if you want to compete on performance for real, you'd be hard pressed to do it.

astrange 3y ago

You'd need to reimplement LLVM code generation and all. These optimizations only work in that part of the compilation process; do it on your own IR and after lowering to LLVM you'll still want to do it again.

jimsimmons 3y ago
Let’s say I’m targeting x86 or PTX or some standard subo instruction set. I can do vanilla codegen but it is slow af
- pertymcpert 3y ago
  But why would you when LLVM is there and will generate much better, much easier and very probably have fewer bugs than any custom one.
  - jimsimmons 3y ago
    Because I want to be self hosted
    - compiler-guy 3y ago
      Self-hosting llvm isn't all that hard. But you might possibly have found that one weird corner case where it doesn't make sense to depend on a mighty, highly-sophisticated, industrial-strength, extremely well tested and supported, nicely mature, compiler tooling framework. But that's a pretty big exception to most language implementers who get all of that and more for super-cheap compared to implementing it themselves.
      - vidarh 3y ago
        Self hosted typically includes building the compiler in the language it compiles. E.g. my Ruby compiler is self hosted except for needing an assembler and linker (and I might get rid of that need too) and a minimal C library. If you're writing a C++ compiler, self-hosting LLVM might not be a massive additional complexity. For any other language it's not an option if self hosting is one of your goals.

mathisfun123 3y ago

>Like what exactly is the implementation of the top 20 optimizations? It can’t be that high right.. I love the full-throated arrogance of this - "I have no idea but I'm sure it's not hard" lol So I'll tell you - each pass is at minimum a paper (mem2reg) and at maximum several dissertations (polly) to understand. Then have fun implementing a basic basic alpha in your compiler that doesn't have all the creature comforts of LLVM - iterators, efficient data-structures, debugging aids, etc. And then give up because a paper or a dissertation is out-of-date like as soon as it's in deadtree form, while LLVM is a living, breathing, tapestry of insights, breakthroughs, and hacks too. I highly recommend you attempt even one pass to get a feel: pick any language that has a parser impl and design an IR for it and then optimize it (designing an IR from scratch can't be that hard can it?)

jimsimmons 3y ago
(tbc I was forthcoming with my arrogance, like it genuinely didn’t make sense to me) Why would constant propagation need a PhD level proficiency to implement? It’s basically running part of your code and no different from parsing. Again not trying to trivialize or be rude. I wish this was something I could ask ChatGPT and trust its outputs but you know I can’t
- lemming 3y ago
  The Programmers’ Credo: we do these things not because they are easy, but because we thought they were going to be easy https://twitter.com/Pinboard/status/761656824202276864 https://twitter.com/Pinboard/status/761656824202276864
- mathisfun123 3y ago
  >Why would constant propagation need a PhD level proficiency to implement? This is false premise or one of those other ones - constant prop might not be complex but constant prop isn't in the top 20 perf codegen relevant passes.
- NavinF 3y ago
  > ask ChatGPT and trust its outputs If anyone's wondering, its response to the GP comment is 100% correct as far as I can tell. Only problem is that it's missing technical details and has a hard time giving specific examples. --- There are several reasons why programming languages might choose to rely on LLVM or other external compilers and optimization frameworks rather than implementing optimizations on their own: Focus on language design: Many programming languages prioritize language design and functionality over compiler optimization. Implementing optimizations can be a complex and time-consuming process, and language designers may prefer to focus on other aspects of the language. Difficulty of optimization: While some optimizations may seem simple in theory, they can be difficult to implement in practice, especially for complex programs. Additionally, different optimizations may interact with each other in unpredictable ways, making it challenging to optimize code effectively. Targeting multiple platforms: Many programming languages are designed to be portable and run on multiple platforms. Relying on external compilers and optimization frameworks like LLVM can help ensure that code is optimized for each platform without requiring extensive platform-specific optimizations. Access to expertise: Compiler optimization is a specialized field that requires a deep understanding of computer architecture, algorithms, and programming languages. By relying on external frameworks like LLVM, programming languages can leverage the expertise of experienced optimization engineers and researchers. As for the implementation of the top 20 optimizations, the specific details will depend on the optimization and the programming language being used. However, many optimizations involve analyzing the code to identify opportunities for improvement and then applying transformations to the code to make it more efficient. Some optimizations, like constant propagation and loop unrolling, may involve relatively simple transformations, while others, like register allocation and instruction scheduling, can be more complex. --- snippets from "Use highly technical details and examples to answer this question.": Memory reuse involves optimizing the use of memory to reduce the number of accesses and minimize cache misses. This can involve techniques such as loop-invariant code motion, which moves code that does not depend on loop variables outside of the loop, or loop fusion, which combines multiple loops that iterate over the same data into a single loop. However, these optimizations may also depend on the specific architecture being targeted, as the optimal memory access patterns may differ depending on the cache size and associativity Writing a high-quality compiler that can handle all of the edge cases and produce optimized code for a wide range of architectures requires a significant amount of expertise and resources. Additionally, using an external compiler can provide a degree of portability, as the same code can be compiled for multiple architectures without requiring changes to the code itself --- snippet from "Why would constant propagation need a PhD level proficiency to implement? It’s basically running part of your code and no different from parsing.": Constant propagation is indeed a relatively simple optimization technique in theory, and it does not require a PhD level proficiency to implement it. In fact, most compilers include some form of constant propagation as part of their optimization pipeline, and many of these implementations are relatively straightforward. However, there are several factors that can make constant propagation more challenging to implement in practice. Some of these factors include: Handling interactions with other optimizations: Constant propagation can interact with other optimizations in non-trivial ways, such as dead code elimination and loop unrolling. Ensuring that these optimizations work together correctly can require careful analysis and testing. Dealing with complex data structures: In some cases, constant propagation may need to deal with complex data structures, such as arrays or pointers. Ensuring that constant propagation works correctly in these cases can require more advanced techniques, such as dataflow analysis or points-to analysis. Supporting language features: Different programming languages may have different rules for when constant propagation is allowed or required. For example, some languages may allow constants to be defined using complex expressions or function calls, while others may require constants to be literal values. Supporting these language features can require additional analysis and code generation logic.

wyldfire 3y ago

The architecture specific backends are another significant part of the compiler, including architecture specific optimizations. I suppose one of the reasons you might think of the llvm project as monstrous is because it's feature-rich.

jimsimmons 3y ago
What if I care about like 4 archs: x86/64, arm64 and PTX
- compiler-guy 3y ago
  Then you still have to do 4x the amount of work than you otherwise would. And when the next iteration of those chips become available, you will have to update your tooling yourself instead of get updated pipeline models for the cost of a source upgrade.
- saagarjha 3y ago
  Your backend will probably be much worse than the one LLVM provides.
- mananaysiempre 3y ago
  You might be underestimating the intricacy of the CPU models LLVM uses. If you want to see them in action, the same data drives llvm-mca[1], which given a loop body can tell you the throughput, latency, and microarchitectural bottlenecks (decoding, ports, dependencies, store forwarding, etc.)—if not always precisely, then still as well on average as, say, x86’s IACA, the tool written at Intel by people who presumably knew how those CPUs work, unlike LLVM contributors and the rest of us who can only guess and measure. This separately for Haswell, Sandy Bridge, Skylake, etc.; not “x86”. Now, is this the best model you can get? Not exactly[2], but it’s close enough to not matter. Do we often need machine code optimized that finely? Perhaps not[3], and if you’re using generic distro binaries, you’re not getting it, either. (Unlike Facebook, Google, etc., who know precisely what their servers have inside, and who fund or contribute sizable portions of this optimization work.) With that in mind you can shave at least a factor of ten off LLVM’s considerable bulk at the cost of 20—30% of performance[4,5]. But if you do want those as well, it seems that the complexity of LLVM is a fair price, or has the right order of magnitude at least. (Frontend not included, C++ frontend required to bootstrap sold separately, at a similar markup compared to a C-only frontend with somewhat worse ergonomics.) [1] https://llvm.org/docs/CommandGuide/llvm-mca.html https://llvm.org/docs/CommandGuide/llvm-mca.html [2] https://www.uops.info/ https://www.uops.info/ [3] https://briancallahan.net/blog/20211010.html https://briancallahan.net/blog/20211010.html [4] https://c9x.me/compile/ https://c9x.me/compile/ [5] https://drewdevault.com/talks/qbe.html https://drewdevault.com/talks/qbe.html

lanza 3y ago

> Yet why do languages end up depending on LLVM and not implement these algorithms on their own and avoid a monstrous dependency? That's like asking why construction companies rely on cranes, concrete and steel rebar when they can be using sticks, leaves and vine. LLVM is so mature that it's hard to improve it. If you don't care about the performance of your languages code then fine, use leaves and sticks and moderate winds will knock down your shelter.

mathisfun123 3y ago
Ya I was thinking about an analogy as I was writing my other response - thinking you're gonna make your life easier by reinventing LLVM is like those people that think they're gonna make their lives easier by freeing themselves of the encumbrances of `society` (by moving off-grid to middle of nowhere). I believe they quickly come to realize that `society` was invented for a reason.

WalterBright 3y ago

It turns out that many of the standard optimizations just don't work without a lot of extra work. For example, loop optimization algorithms don't take into account things like the loop induction variable changes may result in overflows. It just takes a while to figure out how to account for signed/unsigned, integral promotions, overflows, etc. Some optimizations also defeat other optimizations. For example, on the x86, various arithmetic operations can be combined into a single instruction. But common subexpression elimination can subvert it. It isn't always better to do common subexpression elimination.