HN Theater @HNTheaterMonth

⬐ davidrusu

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

⬐ vok

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

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

⬐ tikhonj

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.

⬐ PeCaN

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.

⬐ tikhonj

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/

⬐ regehr

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

⬐ davidrusu

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?

⬐ regehr

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.

⬐ davidrusu

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

Keep up the good work!

⬐ StefanKarpinski

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?

⬐ andrewchambers

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.

⬐ cperciva

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

I'm one of the Souper developers and can offer a few pointers that may be more helpful than the github repo. Here's a somewhat recent blog post showing things that Souper can do:

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

Here's a talk I gave at the University of Washington last winter (before Souper did synthesis):

  https://www.youtube.com/watch?v=Ux0YnVEaI6A

Recently we've been teaching Souper to use dataflow facts such as LLVM's known bits and demanded bits. Perhaps interestingly, Souper can also teach LLVM how to compute these facts more precisely:

  http://lists.llvm.org/pipermail/llvm-dev/2015-September/089904.html

One really common question about Souper is "why operate on LLVM IR instead of instructions?" One of the main answers is "so that we can interact with dataflow analyses." This isn't something that previous superoptimizers have done. It seems to be working out really well.