6 ms·

A Superoptimizer for LLVM IR

135 points by eatonphil 6y ago

erichocean 6y ago
I feel like this gets submitted at least once a year.
- gumby 6y ago
  Indeed: if it were so great it would have moved into the tree by now.
  - fooker 6y ago
    That's not how research projects work..
    - mhh__ 6y ago
      Well, at least this one has code publicly available (I can't be bothered to name and shame but it's so annoying printing out a paper, reading it, seeing it looks good, and then realizing there's no code to verify)
    - derefr 6y ago
      It kind of happened with Erlang’s HiPE, but then it fell back out because nobody upstream understood it well-enough to keep it working through major version updates.
deleted 6y ago
[deleted]
jey 6y ago
Past discussion: https://news.ycombinator.com/item?id=10463312 https://news.ycombinator.com/item?id=10463312
malux85 6y ago
The UI toolkit without screenshots. The scientific paper without reproducible environment. The deep learning models with no weights. The optimizer without benchmarks.
- xxpor 6y ago
  In the context of a superoptimizer benchmarks dont make sense really. You don't know what it's going to find.
  - ianhanschen 6y ago
    For this sort of benchmarking you don’t want to know what it should find, that would be a functional test and not a benchmark. Compiling and profiling reasonably complex apps against baseline would be enough.
    - JJJollyjim 6y ago
      I'd also like to see motivating examples of specific things it does find (that LLVM doesn't), even if that's not a representative benchmark
    - xxpor 6y ago
      I think I get what you're saying, I think people would read too much into them though. The results are very dependent on the type of program you have. I wouldn't be surprised if there were 10s of percentage point differences in benchmarks between various examples.
  - HelloNurse 6y ago
    That's the point. Benchmarks would show what code is already squeezed dry by basic LLVM tools and what code could benefit from superoptimization, which (as other comments point out) is the only reasonable basis for deciding to give Souper a try.
- hinkley 6y ago
  I wish the Codeless Code wasn’t in mothballs.
rahimiali 6y ago
I'm not sure if I'm interpreting the paper [0] correctly, but both the abstract and the quote below from the Experiments section sound like they're not going to aim for faster code, but for a meta goal (that I admit I don't understand) instead? "The goal is to give compiler developers actionable advice about missing optimizations. To do this, someone uses sclang to extract Souper left-hand sides from programs of interest. Since Souper finds many more optimizations than developers could reasonably implement, the crux is ranking them in such a way that desirable optimizations are found early in the list. We are not aware of any single best ranking function, but rather we have created several such functions that can be used together or separately" [0] https://arxiv.org/abs/1711.04422 https://arxiv.org/abs/1711.04422
- jcranmer 6y ago
  When you develop compilers, you generally have a three-way tradeoff that you can't get all three of simultaneously: runtime speed, generated code size, and compile time. For what's effectively a peephole pass, the main balance question is if the increase in runtime speed is going to be worth the extra time compiling the code. If patterns don't crop up very frequently, and the resulting code has only marginal speedups, then it's not going to be worth slowing everyone's compile time for that speedup. In the context of LLVM IR, there's a subtle issue which is even more important. LLVM IR is sufficiently divorced from actual hardware instructions to be a good basis for a cost model. I believe Souper is largely using instruction count as its cost model [1], which is going to really fall down when you handle i1 values, since most processors aren't capable of doing arithmetic on i1 values natively, and converting the result of a comparison instruction into one that can be reasoned about with boolean circuits can involve several extra instructions. [1] Regehr's original blog post on the matter says instructions are cost 1, constants and phis cost 0, and selects and div/rem cost 3. sexts/zexts/truncs aren't explicitly modeled, and so also presumably cost 0. So it's mostly instruction cost.
kstenerud 6y ago
It seems like this is one of those projects that isn't really interested in explaining anything to non-compiler developers. Every time this link comes up, we get discussion variations of: - Where are the benchmarks? - Benchmarks aren't relevant; it's only for detecting possibilities. - But it has some kind of direct replacement mode, why aren't there benchmarks for that? - Crickets... - Where is this used in practice? - By developers who take its advice. - Examples? - Crickets...
- judofyr 6y ago
  But it has some kind of direct replacement mode, why aren't there benchmarks for that? Crickets... That's not fair. They've published a paper which has lots of details: https://arxiv.org/pdf/1711.04422.pdf https://arxiv.org/pdf/1711.04422.pdf > Performance of the SPEC benchmarks was also unevenly affected by Souper: five become faster and seven become slower. None of the differences was very large.
  - kstenerud 6y ago
    I'm not trying to denigrate their work or assert that it's not valuable research. My point is that the discoverability and information accessibility is very very low here, which is what leads to the frustration whenever this site gets posted.
    - dataking 6y ago
      The research is very likely under peer-review so it is very likely that the site will be revised once the paper is accepted and presented at a conference. Just everyone else, people in academic have more stuff to do than there are hours in a day. Be kind, please.
- ur-whale 6y ago
  You're missing this one: "how can I use this without investing two days of my time figuring out how to plug it in my workflow?"
- amelius 6y ago
kzrdude 6y ago
If there are any rustc devs in this thread, would it be possible to make a superoptimizer for Rust MIR? To do optimizations on this pre-monomorphization representation always sounds so attractive.
- secondcoming 6y ago
  Just raise a ticket
- CUViper 6y ago
  There's a working group for MIR optimization: https://rust-lang.github.io/compiler-team/working-groups/mir-opt/ https://rust-lang.github.io/compiler-team/working-groups/mir...
ausbah 6y ago
how can something published on the Google github repo not be a product of Google..?
- londons_explore 6y ago
  Google internally requires employees pet projects done on company time to be published on the google git repo. But if the company doesn't want to provide any kind of ongoing support (eg. if that employee leaves the company and abandons it), then they say this.

135 points by eatonphil 6y ago

erichocean 6y ago

I feel like this gets submitted at least once a year.

gumby 6y ago
Indeed: if it were so great it would have moved into the tree by now.
- fooker 6y ago
  That's not how research projects work..
  - mhh__ 6y ago
    Well, at least this one has code publicly available (I can't be bothered to name and shame but it's so annoying printing out a paper, reading it, seeing it looks good, and then realizing there's no code to verify)
  - derefr 6y ago
    It kind of happened with Erlang’s HiPE, but then it fell back out because nobody upstream understood it well-enough to keep it working through major version updates.

deleted 6y ago

[deleted]

jey 6y ago

Past discussion: https://news.ycombinator.com/item?id=10463312 https://news.ycombinator.com/item?id=10463312

malux85 6y ago

The UI toolkit without screenshots. The scientific paper without reproducible environment. The deep learning models with no weights. The optimizer without benchmarks.

xxpor 6y ago
In the context of a superoptimizer benchmarks dont make sense really. You don't know what it's going to find.
- ianhanschen 6y ago
  For this sort of benchmarking you don’t want to know what it should find, that would be a functional test and not a benchmark. Compiling and profiling reasonably complex apps against baseline would be enough.
  - JJJollyjim 6y ago
    I'd also like to see motivating examples of specific things it does find (that LLVM doesn't), even if that's not a representative benchmark
  - xxpor 6y ago
    I think I get what you're saying, I think people would read too much into them though. The results are very dependent on the type of program you have. I wouldn't be surprised if there were 10s of percentage point differences in benchmarks between various examples.
- HelloNurse 6y ago
  That's the point. Benchmarks would show what code is already squeezed dry by basic LLVM tools and what code could benefit from superoptimization, which (as other comments point out) is the only reasonable basis for deciding to give Souper a try.
hinkley 6y ago
I wish the Codeless Code wasn’t in mothballs.

rahimiali 6y ago

I'm not sure if I'm interpreting the paper [0] correctly, but both the abstract and the quote below from the Experiments section sound like they're not going to aim for faster code, but for a meta goal (that I admit I don't understand) instead? "The goal is to give compiler developers actionable advice about missing optimizations. To do this, someone uses sclang to extract Souper left-hand sides from programs of interest. Since Souper finds many more optimizations than developers could reasonably implement, the crux is ranking them in such a way that desirable optimizations are found early in the list. We are not aware of any single best ranking function, but rather we have created several such functions that can be used together or separately" [0] https://arxiv.org/abs/1711.04422 https://arxiv.org/abs/1711.04422

jcranmer 6y ago
When you develop compilers, you generally have a three-way tradeoff that you can't get all three of simultaneously: runtime speed, generated code size, and compile time. For what's effectively a peephole pass, the main balance question is if the increase in runtime speed is going to be worth the extra time compiling the code. If patterns don't crop up very frequently, and the resulting code has only marginal speedups, then it's not going to be worth slowing everyone's compile time for that speedup. In the context of LLVM IR, there's a subtle issue which is even more important. LLVM IR is sufficiently divorced from actual hardware instructions to be a good basis for a cost model. I believe Souper is largely using instruction count as its cost model [1], which is going to really fall down when you handle i1 values, since most processors aren't capable of doing arithmetic on i1 values natively, and converting the result of a comparison instruction into one that can be reasoned about with boolean circuits can involve several extra instructions. [1] Regehr's original blog post on the matter says instructions are cost 1, constants and phis cost 0, and selects and div/rem cost 3. sexts/zexts/truncs aren't explicitly modeled, and so also presumably cost 0. So it's mostly instruction cost.

kstenerud 6y ago

It seems like this is one of those projects that isn't really interested in explaining anything to non-compiler developers. Every time this link comes up, we get discussion variations of: - Where are the benchmarks? - Benchmarks aren't relevant; it's only for detecting possibilities. - But it has some kind of direct replacement mode, why aren't there benchmarks for that? - Crickets... - Where is this used in practice? - By developers who take its advice. - Examples? - Crickets...

judofyr 6y ago
But it has some kind of direct replacement mode, why aren't there benchmarks for that? Crickets... That's not fair. They've published a paper which has lots of details: https://arxiv.org/pdf/1711.04422.pdf https://arxiv.org/pdf/1711.04422.pdf > Performance of the SPEC benchmarks was also unevenly affected by Souper: five become faster and seven become slower. None of the differences was very large.
- kstenerud 6y ago
  I'm not trying to denigrate their work or assert that it's not valuable research. My point is that the discoverability and information accessibility is very very low here, which is what leads to the frustration whenever this site gets posted.
  - dataking 6y ago
    The research is very likely under peer-review so it is very likely that the site will be revised once the paper is accepted and presented at a conference. Just everyone else, people in academic have more stuff to do than there are hours in a day. Be kind, please.
ur-whale 6y ago
You're missing this one: "how can I use this without investing two days of my time figuring out how to plug it in my workflow?"
amelius 6y ago

kzrdude 6y ago

If there are any rustc devs in this thread, would it be possible to make a superoptimizer for Rust MIR? To do optimizations on this pre-monomorphization representation always sounds so attractive.

secondcoming 6y ago
Just raise a ticket
CUViper 6y ago
There's a working group for MIR optimization: https://rust-lang.github.io/compiler-team/working-groups/mir-opt/ https://rust-lang.github.io/compiler-team/working-groups/mir...

ausbah 6y ago

how can something published on the Google github repo not be a product of Google..?

londons_explore 6y ago
Google internally requires employees pet projects done on company time to be published on the google git repo. But if the company doesn't want to provide any kind of ongoing support (eg. if that employee leaves the company and abandons it), then they say this.