Learning to Superoptimize real-world programs | Hacker News Reader

Learning to Superoptimize real-world programs

arxiv.org

I don't understand the wording: "Our method, SILO, superoptimizes programs an expected 6.2% of our test set when compared with the gcc version 10.3 compiler's aggressive optimization level -O3."

Does that mean that the runtime is only 6.2% of the runtime after gcc optimization, or that there was a 6.2% reduction in runtime compared to gcc optimization?

Neither, they found that 6.2% of the programs that SILO generated performed better on their benchmarks (based on a sum of the expected and actual execution latency of the assembly on some test data) than the gcc -O3 baseline (i.e. 93.8% of the programs SILO generated did not perform better, or were not correct). AFAIK they don't state how much better the super optimized programs were.

I'm convinced that neural networks in compilers are the Next Big Thing in AI. e.g. GPUs are very difficult to program for mere mortals.

Well, we quite dont know since AFAICT GPUs instruction sets (real instruction set, not IR) are completely closed, so the first reason they're difficult to program is by secrecy, not technical.

AMD is open, right?

Indeed, you can get them all here - https://gpuopen.com/documentation/amd-isa-documentation/

And that's the ISA that actually executes on the gpu, including instruction encoding and whatnot - not just some IR

Intel can't be too well kept secret either since they develop drivers as opsource.Then there are the reverse engineered mobile GPUs.

Openness is also a no-brainer play to get market share especially as a business-card e.g. if we buy a GPU, it only needs above a certain performance - stock and driver support is all that matters for us in today's market (obviously this is not the case for GPGPU work)

Even things like instruction selection could be pretty interesting. People think compilers are basically sentient but they really aren't, even ignoring the tuning parameters, they really do need help when you get the edges of what the ISA designers incorporate.

Similarly, try and work out how a compiler schedules and lays out code for a modern superscalar processor. Both things do matter (potentially a lot) but it's not like the old days where you have a very fixed model of the pipeline to evaluate your schedule with (or a simple one at least)

Escape analysis leads to Rust's memory safety model. I think we will see a similar cross-domain learnings in optimization, and I don't think NN are it. Monte Carlo simulation seems more likely to me, and that can steal ideas from either game AI, property-based testing, or both.

More boringly, treating the compilation metadata more as a database may also be waiting to be exploited. Right now we have feedback-directed optimization which basically takes a 1:many or 1:1 approach of one data set gives you one binary. Next compile you start with new input and run the process again, whereas retaining a history might allow for deeper tree searches.

It's always annoyed me a little that every single time my code loads or gets compiled that the runtime has to start from ground state and build up. If I run the same compile fifty times in a row it's always the same output and it always takes the same amount of time. If a big improvement is just beyond the search budget it will forever remain out of sight. Especially in a CI/CD world my ratio of changes to binaries is very, very low, and so the waste is much more pronounced.

If instead you store a map of decisions and constraints, can I test the constraints, flush all of the decisions whose constraints are violated, and begin my search tree from there? Going a little deeper every time in stable areas of the code?

You mention searching the tree of potential programs that satisfy a set of constraints—but what's the fastest way to search that tree, both in making edits that are contextually sensible, and in using prior programs to factor out common patterns?

If you want to go off the deep end of the possibilities of NNs in compilers, I suggest you look up wake-sleep program synthesis at the least: https://dl.acm.org/doi/10.1145/3453483.3454080

IIRC Milespost GCC already does the database approach

Okay, had to register just because of the positive comments so far. I know nearly nothing about machine learning and may be a bit biased, but has anybody actually read the paper?

As I understand it, the model is trained on what compilers do anyway (the training data consists of compiler output from -O0 and -O3), so it won't come up with the kind of clever tricks that a human might.

One of their cherry-picked examples (fig5, prstree_empty) is incorrect: in one branch it is supposed to return true if the value at rdi+0x10 is a null pointer, but in the optimized version it falls through from "sete %al" to the next instruction, which overwrites that register so it will always return true.

It would be easy to fix by inserting another return instruction, but this clearly shows the neural net doesn't "understand" how to generate correct code. Besides some peephole optimizations, a lot of what it learned seems to be how to fool automated checks, and in this case even the authors who didn't spot the bug.

See also the section about verifier exploits, which are embarassingly simple: a completely empty "if statement" which depends on memory causes a function to pass when it clearly does nothing more than always return false.

The 6.2% figure is after "human verification" (again, one of the examples in the paper is broken!), down from 8.3% using only the automated verifier.

Not impressed.

This sounds really promising. Could this be extended to other kinds of optimizations, eg data layout for memory traffic reduction?

Almost definitely, only rub is that the compiler isn't allowed to do anything hugely funky with memory layout in C/C++ esque languages.

Yes, those are lost causes if they can't ride the as-if optimization rule. But if the assembly language modules just have to return same outputs for same inputs...

Reply on news.ycombinator.com