5 ms·

A whirlwind tour of the LLVM optimizer

107 points by matt_d 4y ago

quickthrower2 3y ago
What is this horrendous website? Every 3 slides I get a full screen video ad. Download requires login. If the creator is here: I recommend just sticking the pdf on github and then submit the raw link so we can read your good work!
- simonw 3y ago
  https://en.wikipedia.org/wiki/SlideShare https://en.wikipedia.org/wiki/SlideShare - launched in 2006, acquired by LinkedIn in 2012, then acquired from LinkedIn by Scribd in 2020. It looks like Scribd have leaned hard into interstitial ads to try and monetize the 17+ years of content on there.
- dxf 3y ago
  Videos and slides from the LLVM developer's meetings get posted onto the event site, though not immediately afterwards (as they have to get all the videos processed). If you're willing to wait a short while, the slides and presentation should eventually be uploaded and linked to from https://llvm.org/devmtg/2023-05/ https://llvm.org/devmtg/2023-05/.
jevinskie 3y ago
Scribd-free PDF: https://cdn.discordapp.com/attachments/1104096132486938727/1106040345210409041/awhirlwindtourofthellvmoptimizer.pdf https://cdn.discordapp.com/attachments/1104096132486938727/1...
- Xelynega 3y ago
  I was about to go insane having to view an ad every 3 slides(which sometimes is the same slide). Thanks.
jimsimmons 3y ago
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.
deterministic 3y ago
I maintain a high-performance JIT compiler used by large corporations around the world to run complicates business rules for logistics and optimisations. It uses LLVM as the backend for machine code generation. I mostly disable the optimisations provided by LLVM. Because it makes code generation much slower with almost no performance gains. Writing high level optimisation passes before converting the AST to LLVM is what made the generated code super fast. LLVM has no knowledge of the semantics of the language. So it can only optimise low level details that the higher level optimisations will get rid of anyway. It seems to me that the LLVM optimisations are only of benefit to you if you generate really bad LLVM code in the first place.
- brickteacup 3y ago
  Can you elaborate on the extent to which you use LLVM optimizations? Is it comparable to e.g. clang's -O1/2/3?
- yukIttEft 3y ago
  I guess your generated code contains a lot of black boxes that the optimizer can't see through. At my work, the LLVM optimizer is doing an insane amount of optimizations.
  - pornel 3y ago
    Rust is very optimizable by LLVM, but still has similar issue with performance. It's costly to optimize overly verbose/inefficient LLVM IR. Rust ended up implementing its own (MIR) optimization passes before LLVM to generate more optimized IR for it.
    - sanxiyn 3y ago
      MIR optimization doesn't just move work from LLVM to Rust, it saves work, because it runs before monomorphization (template specialization in C++).
- fooker 3y ago
  This is the exact problem MLIR intends to solve. LLVM optimizations are only really effective for simplifying integer expressions and loop patterns seen in code generated from imperative languages.
deleted 3y ago
[deleted]

107 points by matt_d 4y ago

What is this horrendous website? Every 3 slides I get a full screen video ad. Download requires login. If the creator is here: I recommend just sticking the pdf on github and then submit the raw link so we can read your good work!

simonw 3y ago
https://en.wikipedia.org/wiki/SlideShare https://en.wikipedia.org/wiki/SlideShare - launched in 2006, acquired by LinkedIn in 2012, then acquired from LinkedIn by Scribd in 2020. It looks like Scribd have leaned hard into interstitial ads to try and monetize the 17+ years of content on there.
dxf 3y ago
Videos and slides from the LLVM developer's meetings get posted onto the event site, though not immediately afterwards (as they have to get all the videos processed). If you're willing to wait a short while, the slides and presentation should eventually be uploaded and linked to from https://llvm.org/devmtg/2023-05/ https://llvm.org/devmtg/2023-05/.

jevinskie 3y ago

Scribd-free PDF: https://cdn.discordapp.com/attachments/1104096132486938727/1106040345210409041/awhirlwindtourofthellvmoptimizer.pdf https://cdn.discordapp.com/attachments/1104096132486938727/1...

Xelynega 3y ago
I was about to go insane having to view an ad every 3 slides(which sometimes is the same slide). Thanks.

jimsimmons 3y ago

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.

deterministic 3y ago

I maintain a high-performance JIT compiler used by large corporations around the world to run complicates business rules for logistics and optimisations. It uses LLVM as the backend for machine code generation. I mostly disable the optimisations provided by LLVM. Because it makes code generation much slower with almost no performance gains. Writing high level optimisation passes before converting the AST to LLVM is what made the generated code super fast. LLVM has no knowledge of the semantics of the language. So it can only optimise low level details that the higher level optimisations will get rid of anyway. It seems to me that the LLVM optimisations are only of benefit to you if you generate really bad LLVM code in the first place.

brickteacup 3y ago
Can you elaborate on the extent to which you use LLVM optimizations? Is it comparable to e.g. clang's -O1/2/3?
yukIttEft 3y ago
I guess your generated code contains a lot of black boxes that the optimizer can't see through. At my work, the LLVM optimizer is doing an insane amount of optimizations.
- pornel 3y ago
  Rust is very optimizable by LLVM, but still has similar issue with performance. It's costly to optimize overly verbose/inefficient LLVM IR. Rust ended up implementing its own (MIR) optimization passes before LLVM to generate more optimized IR for it.
  - sanxiyn 3y ago
    MIR optimization doesn't just move work from LLVM to Rust, it saves work, because it runs before monomorphization (template specialization in C++).
fooker 3y ago
This is the exact problem MLIR intends to solve. LLVM optimizations are only really effective for simplifying integer expressions and loop patterns seen in code generated from imperative languages.

deleted 3y ago

[deleted]