Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Large Language Models for Compiler Optimization

arxiv.org

Post reply on HN
Print view View original

21–30 of 119 posts

Re: Large Language Models for Compiler Optimization

#21

Post by boomanaiden154 »

haltist wrote: post #14

Next step is to add verification for optimized code from the LLM with an SMT solver (like Z3) to remove "hallucinations". If the input and output code can be verified to be equivalent then this would be a great addition to an optimization pipeline. Once that's done the same can be applied to intermediate representations of GPU kernels in a recursive loop of AI optimizing AI code for faster execution times.

There's already tooling available for using SMT to validate LLVM-IR transformations [1]. It's designed for zero false positives however, so some things might slip through the cracks.

Additionally, this work focuses on phase ordering, which produces correct code regardless of what the LLM puts out, assuming there aren't any bugs in the passes being used (which could crop up as random orderings aren't as well tested as the standard orderings in the commonly used pipelines).

1. https://users.cs.utah.edu/~regehr/alive2-pldi21.pdf

Re: Large Language Models for Compiler Optimization

#22

Post by drug-freedom »

jebarker wrote: post #11
kukkamario wrote: post #7

Earlier quoted context omitted.

They are not using LLM to directly produce the result code, but as tool that lists which optimisations should be done and in which order, which is fairly complex problem to solve. But if optimisation passes are implemented correctly (which is anyway required for a functioning optimising compiler), it cannot produce incorrect code, maybe only suboptimal compared to default heuristics used.

If there's a list of known optimizations that preserve correctness then it becomes an optimization problem based on output length (as a proxy for cycle count). So is the idea that an LLM is more efficient than a search or direct optimization?

One example where a LLM might be better is which functions to inline.

Current compilers use a complex set of heuristics, a more holistic approach the kind neural networks do might outperform.

Re: Large Language Models for Compiler Optimization

#23

Post by boomanaiden154 »

TheLoafOfBread wrote: post #13
wyldfire wrote: post #5

> understanding. We evaluate on a large suite of test programs. Our approach achieves a 3.0% improvement in reducing instruction counts over the compiler, 3% code size reduction is really good. The challenge will be having codegen like this that someone is willing to support. And for that they'd want to be able to reason about why the compiler made this decision or that one. IIUC that's an outstanding problem for AI…

Also bugs from this approach are going to be funny - program compiled with compiler version X will work as expected and same program compiled with version X+1 will start crashing because AI under some circumstances decided that dereference of a specific pointer was unnecessary, so it won't drop it into the assembly. Good luck finding such a bug, because you will be looking on correct code, but computer will be execut…

The focus of this work is finding the optimal ordering of optimization passes to perform, not doing neural compilation. This guarantees correct code, assuming the underlying transformation passes are correct.

Most work in ML for compilers focuses on replacing heuristics and phase ordering precisely because they don't impact correctness. There is some work being done on neural compilation [1], but I'm not sure that's going to be a viable approach anytime soon.

1. https://ieeexplore.ieee.org/document/9926313

Re: Large Language Models for Compiler Optimization

#24

Post by reic »

jebarker wrote: post #20
reic wrote: post #10

Earlier quoted context omitted.

Quantification can be done by measuring in at least two dimensions: (1) the size of the synthesised code, and (2) how precisely the generated code matches the input (which means roughly: on what fraction of input do the two programs give different output). We have set up a challenge that seeks to entice the community to look into this problem domain more. And we've simplified the assumptions, so as to make it more tr…

How well does (2) really measure accuracy? It seems like a single output that doesn't match the input code could indicate a fundamental floor in the optimized code, so it's essentially 100% wrong even though it gets the correct answer almost all the time. Good luck on the challenge though, this seems like an interesting and valuable area of research.

Of course (2) is not a perfect measure of accuracy, since it does not quantify how far wrong an output is, e.g. if 111111111111 is the correct output, then both 111111111110 and 829382934783 count as equally faulty. The main advantage of (2) is that it is natural, easy to understand, and easy to measure and compare. We have to start somewhere. I imagine that, in the future, it can be refined (e.g. taking the Hamming distance between desire and actual output). I expect that more refined quantification emerges in response to the community better understanding exactly what is hard in the synthesis of programs.

Feel free to submit something! A simple submission is probably just a few lines of code.

Re: Large Language Models for Compiler Optimization

#25

Post by boomanaiden154 »

drug-freedom wrote: post #22
jebarker wrote: post #11

Earlier quoted context omitted.

If there's a list of known optimizations that preserve correctness then it becomes an optimization problem based on output length (as a proxy for cycle count). So is the idea that an LLM is more efficient than a search or direct optimization?

One example where a LLM might be better is which functions to inline. Current compilers use a complex set of heuristics, a more holistic approach the kind neural networks do might outperform.

For function inlining specifically, I'm not sure LLMs are necessarily the right choice. The original MLGO paper [1] demonstrated a big code-size improvement with a ML model for making inlining decisions (7-20% code size wins), but they used tens of engineered features. Maybe a LLM could squeeze some additional size wins out, but maybe not [2].

Additionally, there are other factors to consider when productionizing these systems. Compile time is important (which LLMs will almost certainly explode), and anyone concerned about code size will probably be doing (Thin)LTO which would require feeding a lot more context into a LLM making inlining decisions.

1. https://arxiv.org/abs/2101.04808 2. https://dl.acm.org/doi/10.1145/3503222.3507744

Re: Large Language Models for Compiler Optimization

#26

Post by boomanaiden154 »

One of the biggest things that seems to be holding back ML in compilers right now is dataset size. This model was only trained on a gigabyte of source code, 30+% of that synthetic. Even on much simpler models, there have been massive performance gains by just throwing more data at them. Some experimentation with the original MLGO inlining model on a much bigger data corpus doubled the code-size wins. LLMs have also been shown to perform better they more data they are fed [1].

1. https://arxiv.org/abs/2203.15556

Re: Large Language Models for Compiler Optimization

#28

Post by boomanaiden154 »

sesuximo wrote: post #27

I wonder if you could get a correct compiler (or 100% emulation in their terms) by allowing it to choose optimization pass order rather than doing more arbitrary things

I'm not sure a fully correct production optimizing compiler is that feasible. LLVM gets multiple miscompilation reports per week (from what I've haphazardly seen observing the issue tracker).

Theoretically changing the order of the passes in the optimization pipeline shouldn't cause any correctness issues, but the fact is that the ordering in the default compilation pipelines is the one that is most tested, so there will probably be bugs exposed when fuzzing the pass ordering.

Re: Large Language Models for Compiler Optimization

#30

Post by alex_lav »

naveen99 wrote: post #29

Chatgpt4 can do source to source optimization which is pretty cool. I got it to beat gcc at -03 on simple small toy problems. and it can do similar things with python also. But it threw its hands up when I gave it a longer piece of code to optimize.

At my company we have some "loadbearing" code that was written by a mad scientist that no longer works at our company. We have a total ban on AI for source code analysis (so chatgpt, copilot etc are all banned). I've really wanted to throw some of the grosser parts of that codebase into gpt-4 just to see if it could bring some small amount of sanity.
Post reply on HN