8 ms·
Large Language Models for Compiler Optimization
- quadrature 3y agoI wonder if this requires a 7B parameter model.Assembly has a small grammar and is very constrained compared to natural language.
- kaba0 3y agoI don’t see why would the output language’s complexity matter - that’s clearly not the hard part. You need plenty of “thinking” to do for outputting sensible assembly, let alone whole programs. With that said, it is not doing neural compilation as others have mentioned, it’s only about ordering/enabling different phases of the compiler based on ML, over the current, simpler heuristics.
- quadrature 3y agoExactly, since its not doing whole program synthesis im thinking it could be done with fewer parameters. However program synthesis is part of the loss function.
- cec 3y agoProgram synthesis is part of the loss function, which is what makes it a auxiliary learning task. We haven’t experimented with model size yet, we just used the same configuration as the smallest Code Llama. We did play with dataset size and found thah performance tracks the usual scaling laws. Details in the paper
- quadrature 3y agoThanks for the reply!. This is really interesting research, hope to see more from your team.
- foota 3y agoThis kind of application of LLMs is most interesting to me, since it's possible to evaluate correctness and performance quantitatively.
- jebarker 3y agoIt seems like a poor fit to me precisely because correctness is boolean, difficult to measure and getting it wrong is very bad. I do think there's a place for AI here but it's probably not LLMs in their current form.
- armchairhacker 3y agoThe trick is finding a way to ensure that LLM produces something which is always correct. Like in this case, the LLM only changes compiler optimizations, not the assembly itself, so no matter what it outputs the code is correct, it just may be larger. Other possibilities: an LLM which applies semantics-preserving program transformations, or an LLM combined with a proof assistant to verify the output (more generally and for any domain, an LLM as an NP oracle). But I agree, as of now I haven't seen good uses where LLMs produce reliable output. Not only do you need that guarantee that whatever output always generates a correct program, you need something where an LLM is considerably better than a simple or random algorithm, and you need a lot of training data (severely restricting how creative you can be with the output).
- foota 3y agoThe approach seems to focus on selecting optimizations to apply for LLVM (e.g., imagime: should this be inlined as an example), but the worst case is that the code is poorly optimized, you can't select optimizations to apply and get a wrong result. I agree that what you say is true of compilation as a whole, but that doesn't seem to be the focus here (rather, it's used as a sort of crutch to help the LLM learn)
- kukkamario 3y agoThey 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.
- CalChris 3y agoThere's a half day tutorial at the LLVM Developers Meeting on this, ML-Guided Compiler Optimization in LLVM. However, the authors of this paper aren't giving that tutorial.
- klohto 3y agoMLGO uses RL
- mathisfun123 3y agomaybe today but MLGO, the initiative, uses whatever. To wit: chris cummins (first author here) was on last year's MLGO panel.
- boomanaiden154 3y agoIt's a workshop intended to facilitate discussion in the space. The lead author of this paper (Chris Cummins) will probably be there. https://discourse.llvm.org/t/pre-llvm-dev23-ml-guided-compiler-optimization-workshop/71431 https://discourse.llvm.org/t/pre-llvm-dev23-ml-guided-compil...
- wyldfire 3y ago> 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 in general.
- TheLoafOfBread 3y agoAlso 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 executing invalid output.
- a_wild_dandan 3y agoDamn. These things imitate humans too well. Guess we’ll need a giant test suite to feel stable. Sounds like work. Let’s train a GAN for that and put our feet up. Turtles all the way down, my dudes.
- boomanaiden154 3y agoThe 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 https://ieeexplore.ieee.org/document/9926313
- wyldfire 3y ago> phase ordering precisely because they don't impact correctness. lol let's say they're less likely to impact correctness than an arbitrary new optimization.
- haltist 3y agoNext 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.
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- boomanaiden154 3y agoThere'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 https://users.cs.utah.edu/~regehr/alive2-pldi21.pdf
- haltist 3y agoInteresting. AI code has no loops so the problem they mention in the beginning about unrolling loops to a certain depth is a non-issue.
- boomanaiden154 3y agoOne 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 https://arxiv.org/abs/2203.15556
- isaacfung 3y agoQuality matters just as much as quantity. LIMA: Less Is More for Alignment https://arxiv.org/abs/2305.11206 https://arxiv.org/abs/2305.11206 AlpaGasus: Training A Better Alpaca with Fewer Data https://arxiv.org/abs/2307.08701 https://arxiv.org/abs/2307.08701 Textbooks Are All You Need II: phi-1.5 technical report https://arxiv.org/abs/2309.05463 https://arxiv.org/abs/2309.05463
- uoaei 3y agoWhat's holding them back is provable correctness. It's possible, nay, mandatory to constrain the outputs of the model at each step of generation in order to guarantee that a given structure or grammar is adhered to. If you can fine-tune the model with these constraints in place you can offload a lot of the effort that the LLM otherwise has to perform in comprehending correctness so it has more capacity for generating good content. To be sure, quality and quantity of data are important, but it's all too easy to introduce subtle bugs that take years to tease out if you don't adhere to the right constraints.
- boomanaiden154 3y agoMost of the work in this space is not focused on neural compilation (having a ML model perform the transformation/entire compilation), but on replacing heuristics or phase ordering, where the issue of correctness falls back onto the compiler. For pretty much exactly the reasons you mentioned, neural compilation isn't really tractable. This specific paper focuses on phase ordering, which should guarantee correctness, assuming the underlying transformations are correct. They do train the model to perform compilation, but as an auxiliary task.
- sesuximo 3y agoI 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
- boomanaiden154 3y agoI'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.
- naveen99 3y agoChatgpt4 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.
- alex_lav 3y agoAt 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.
- reidjs 3y agoDo you know why that policy is in place? Is it fear that the llm provider will steal company trade knowledge?
- esrauch 3y agoIt's probably both that is leaking your source out and the risk of it being a copyright violation if it spits out some GPL source verbatim and you check it in.
- Filligree 3y ago> if it spits out some GPL source verbatim Does that ever actually happen? I've only heard of it happening to people who forced the AI's hand by including the comments for said code in the prompt.
- callalex 3y agoWhile many software companies get away with an “it’ll be fine” attitude, that is not sufficient for all companies and industries. Sometimes things have to be provably correct.
- kolbe 3y ago> Our approach achieves a 3.0% improvement in reducing instruction counts over the compiler, outperforming two state-of-the-art baselines that require thousands of compilations. If that's their target, then what's the point? LLVM's optimizations are not done to minimize instructions but to maximize performance. On modern processors, these can be very different things.
- boomanaiden154 3y agoYou're right that a decrease in code size doesn't mean a performance increase (and oftentimes they can be inversely correlated like in inlining). But LLVM targets both depending upon what optimization pipeline you select. (-Oz/-Os are targeting minimum code size, -O1,-O2,-O3 are optimization focussed). Code size reduction is critical in some use cases like embedded environments and mobile apps and it is a significant area of research.
- cec 3y agoHey, we’re targeting code size in this work, not runtime performance. You would use an option like -O3 to optimize for runtime and -Oz to optimize for code size. The pass pipelines are different for both
- dhosek 3y ago“generating compilable code 91% of the time” which means that almost ten percent of the time, it doesn’t generate compilable code. Given the fact that ChatGPT has gotten worse at math over time,¹ I’m wondering if this too will get worse. ⸻ 1. Although I also find myself thinking about my kids as they were developing language where they initially correctly conjugated some common irregular verbs, then they started conjugating them as if they were regular and then finally returned to correctly conjugating them, which might be what’s happening with ChatGPT and math.
- deleted 3y ago[deleted]
- gamerpuppy 3y agoLLm's are agi, you can use them for anything so posts like "LLm's for x" are really so boring.
- deleted 3y ago[deleted]
- csjh 3y agoLLMs are definitely not AGI
- primordialsoup 3y agoThis is very interesting work, but it's not really a LLM. It doesn't have language abilities. They should have called it a seq2seq model, but I think that term is not in vogue these days :)
- deleted 3y ago[deleted]
- cec 3y agoWe use the same architecture as other LLMs, but we include no natural language in our pretraining. We figured a single-domain training corpus would make evaluation easier. We’ll be looking at layering this on top of something like Code Llama next
- CJefferson 3y agoWhile this isn't optimization, is there any LLM systems that create "provably correct" transformations yet? I have used ChatGPT on some fairly awful code, asking it to add comments, rename variables and functions, etc. I find the outputs useful, but a couple of times it's broken the code. I imagine for many (not all) languages, you could ask the LLM to produce suggested changes, then use a code-rewriting tool to apply them in a way you could be 100% sure they weren't going to change the behaviour of the progrma.
- deleted 3y ago[deleted]
- quickthrower2 3y agoSounds like TDD and langchain? Where the T can be anything from Ruby unit tests to Coq proofs.
- wrsh07 3y agoAre you compiling the code or interpreting?
- CJefferson 3y agoCompiling C++ code, which means there is a chance you could prove transformations correct, but I’m not going to try it myself :)
- wrsh07 3y agoAt the very least transformations that produce identical assembly are safe. I think.
- darksaints 3y agoI can't imagine there would be any success with an LLM that isn't already known about via Satisfiability Modulo Theory.
- 3y ago
- neonsunset 3y agoI was hoping to see a more ambitious language model based project. Rather than just picking compiler arguments, an LLM could parse, and then transform AST into its more optimized form in a way that does not rely on a very formal way it is treated by compilers of today, apply guesstimate-based branch reordering and inlining heuristics not dissimilar to how a programmer would do so manually. Once done, a compiler could perform final AST validation and either route it back to LLM to fix it or auto-fix most common cases.
- haltist 3y agoHow do you validate semantic equivalence?
- boomanaiden154 3y agoWhat's the benefit of having an LLM do those things in a way that guesstimates? There are big wins to be had in code-size and some wins to be had in performance related to inlining [1][2], but I think the implementation in the references directly tied into the compiler's inlining heuristic is a much better way to do that as it guarantees correctness. In addition, there's a reason that compilers basically ignore the `inline` keyword these days. For branch reordering, techniques like BOLT [5] are pretty effectively able to reorder code layout at the binary level for big performance gains by using profile information. ML models can sometimes synthesize that information [3], but if I recall correctly, the performance of those models wasn't as good. Neural compilation (like what you're describing) has been tried with LLMs [4], but has a lot of correctness problems currently, and I don't think it's going to be feasible anytime soon to do reinforcement learning for performance/code-size improvements. 1. https://arxiv.org/abs/2101.04808 https://arxiv.org/abs/2101.04808 2. https://arxiv.org/abs/2207.08389 https://arxiv.org/abs/2207.08389 3. https://arxiv.org/abs/2112.14679 https://arxiv.org/abs/2112.14679 4. https://ieeexplore.ieee.org/document/9926313 https://ieeexplore.ieee.org/document/9926313 5. https://arxiv.org/abs/1807.06735 https://arxiv.org/abs/1807.06735
- PhilipRoman 3y agoI see a lot of misconceptions about using ML for compilers. You don't ask the model what instructions to emit. Instead, you prepare a set of passes which are guaranteed to preserve correctness (we already have hundreds of them). Then you ask the model - what passes should I apply and in what order. Writing code to unroll a loop is trivial. The limitations of compilers are that almost all currently existing languages are too low level for optimization. ML has the potential to extract back this lost information. Basically the opposite of lowering an IR.
- boomanaiden154 3y agoML for phase ordering is just one problem that ML could solve within compilers. Heuristic replacement (like loop unrolling) is another big one. For the specific case of loop unrolling, I would think lower level elements like how much iCache pressure the unrolling creates/whether or not the loop could fit in the DSB buffer would matter more. For your point about existing IRs being too low-level, there has been a large push to try and work on that. MLIR has been used pretty extensively for that problem in ML applications, and languages like Rust have multiple higher level IRs. There's also a preliminary implementation of a Clang-IR for C/C++, and there's even be some work on higher level representations within LLVM-IR itself.
- eru 3y ago> You don't ask the model what instructions to emit. You could still do that, you'd just also need to ask the model for a proof. (But I guess that's much harder than heuristically picking which passes to apply.)
- SiempreViernes 3y agoWhat do you do when you check the proof and discover it is false? Just ask again for a proof or discard the emitted instructions?
- eru 3y agoDepends on your use case, I guess?
- smusamashah 3y agoDo LLMs need to see some information just once to answer about it? My understanding was that they need to see many examples of the same thing to be able to answer it correctly (generate text around it correctly). Shouldn't this mean that it is safe to ask GPTs about something proprietary if it was just once because rare examples should just disappear in weights of everything else. And this also means that even GPT4 won't be able to answer any queries about obscure or rare knowledge it has seen in its training dataset.
- aratauto 3y agoSome recent discoveries indicate that LLMs might remember information after seeing it only once. See e.g.: https://www.fast.ai/posts/2023-09-04-learning-jumps/ https://www.fast.ai/posts/2023-09-04-learning-jumps/
- Lynix48 3y agoI was thinking about writing my bachelor's thesis about LLMs and compilers. My idea is to maybe attempt to write a C (to assembler)-Compiler and see how well it does. Attempting to convert assembler to C using an LLM would be interesting too, but the results would probably be poor since there is just so much information that gets lost when compiling, so the C code would be pretty statistical. I guess I could improve it by somehow adding "C code is or is not compilable because of line n" and whether the result is correct to the lost function. What do you guys think about this?
- cec 3y agoThere’s a researcher at Edinburgh who is looking into this. You may want to reach out. Check the related work section in this paper
- JonChesterfield 3y agoFrom the abstract: - 3.0% improvement in reducing instruction counts over the compiler - generating compilable code 91% of the time - perfectly emulating the output of the compiler 70% of the time. I read through the paper to see what perfectly emulating the output means. In this case, I think it's that it's also possible to get the same code out of the compiler using a different pass order. I was hoping for still passes original test suite or similar. The authors are aware that the generated code has different semantics to the input in some cases but don't seem to consider that particularly important. The section is "Evaluation of Generated Code". So - using machine learning, it is possible to delete a small percentage of the instructions emitted by a compiler while breaking the semantics. A tool which miscompiles programs while making them slightly smaller doesn't seem to be progress in compiler optimization. Does anyone see some value add here that I'm missing?
- hoosieree 3y agoI've just skimmed it but I think they're not using the model's output for codegen, but rather to choose what compiler passes to use and in what order.
- cec 3y agoHey, author here. We use machine learning to generate a list of _optimization passes_ for the compiler to run. These optimization passes give us a 3.0% improvement over the default (-Oz), and are what generates correct code. We don't do anything to the code that breaks semantics (assuming no bugs in the compiler passes; some nuance is needed here ;) ). We also train the model to generate what it thinks the optimized code will look like. We find that this helps the model choose better pass lists, but obviously the code cannot be trusted and semantics are not guaranteed. It only compiles in 91% of cases. "Perfectly emulating the output of the compiler" means the model spat out code that is character-for-character identical to what the compiler generates with the given pass list (even choosing the same variable names etc). IMO this is no mean feat, but is still a long way to go before using LLMs for codegen. We provide a bunch of examples in the paper of things that LLMs can and cannot do.
- Yvan-xy 3y ago
- misrasaurabh1 3y agoI see a lot of interest in this field which is amazing! I have been working on this problem for a while and have made a lot of progress! If you are interested in building a general purpose code performance optimizer, I am hiring founding engineers. We are still in stealth so can't say too much but we already have great results on customers are already funded by some of the best investors of silicon valley. If you might be interested, pls reach out at misra.saurabh1@gmail.com
- parentheses 3y agoWhat is interesting to me about this approach is that they're fine tuning an existing model. If they could train a model using input/output pairs from scratch and entirely on the optimization task, I could see a smaller LLM performing drastically better than the compiled output - according to whatever the loss function is implemented to optimize for.