Superoptimizing LLVM (2014) [video] | Hacker News Reader

Superoptimizing LLVM (2014) [video]

youtube.com

92 pointspmalynin12 comments

engineering fast, effective and correct optimizations for LLVM is challenging

Indeed, just a few days ago I reported a miscompilation bug in the LLVM optimizer... https://llvm.org/bugs/show_bug.cgi?id=27190

Seems like work has died down a bit on the Souper repo[0], last commit was in January.

Anyone know what the current state of super optimization compilers is?

[0] https://github.com/google/souper

This new paper covers some state-of-the-art techniques:

https://www.eecs.berkeley.edu/~mangpo/www/papers/lens-asplos...

To be clear: that is a distinct project that merely relies on a similar set of techniques at a high level.

If my understanding of Souper is correct, it's using synthesis to improve optimization rules inside LLVM. Lens, on the other hand, uses synthesis to optimize code directly with some neat algorithmic improvements to prune the search space. It targets ARM and, of all things, GreenArrays (a weird, extremely low-energy Forth-based architecture).

To be clear: I think both projects are interesting, as are other efforts in the field (ie Aiken at Stanford has done some cool stuff). Program synthesis is a topic I'm definitely interested in. But if you're interested more in LLVM and less in synthesis in general, this paper is going to be less interesting.

GreenArrays's main claim to fame is that it's a fully asynchronous architecture (no central clock). Oh, and it's from Chuck Moore (the Forth guy and kinda the Mike Pall of hardware design).

I had no idea Lens targets it. That's awesome.

Yeah, the project came out of Chlorophyll[1] which was a compiler for GreenArrays that used program synthesis for optimization.

I imagine ARM has more immediate practical applications and useful benchmarks, but it came second—I assume out of a collaboration with Qualcomm Research.

[1]: http://pl.eecs.berkeley.edu/projects/chlorophyll/

It's definitely still an active project, but I'm on sabbatical this academic year and have had much less time than usual for my regular research. I'll be getting back to it in June. Also, Raimondas Sasnauskas, who implemented the instruction synthesizer, finished his postdoc position and moved on.

In any case, there's been a lot of progress since I did that UW talk, for example here are some early synthesis results:

http://blog.regehr.org/archives/1252

That's great to hear! It is a very interesting project

Can you explain why your goal is to implement these optimizations in llvm? Why not have Souper as one of the optimization passes?

It turns out it's harder than you'd think to decide whether or not an optimization is a good idea. Of course there are some relatively simple optimizations that are obviously good, but a lot of those have already been implemented. Also, I'm not sure how many people are going to want to add a solver into their compilation path.

On the other hand, if we simply contribute optimizations then all LLVM users benefit.

We're also using Souper to reveal imprecisions in LLVM dataflow analyses such as known bits -- this turns out to work really well.

Ahh, I see. I assumed that any and all optimizations are good, that makes sense.

Keep up the good work!

I've used Souper a bunch of times on hand-written, performance-critical LLVM code, hoping for some magic superoptimal version of the function. Even saving a few instructions would help in these cases. Unfortunately, in my experience Souper is the identity function: it has literally not once changed my LLVM code in any way. If I'm doing something wrong, I'd love to know what. Perhaps it's not expected that hand-written LLVM will have much room for improvement? Is the intended target of optimization only expected to be fairly obviously redundant machine-generated code?

Working with llvm IR generally doesn't find as nice things compared to super optimizing assembly instructions. This is because there are lots of esoteric assembly instructions a human might not consider using that a machine can brute force.

That is probably one source of problems for souper.

Reply on news.ycombinator.com