boomanaiden154

Found it. It was https://www.phoronix.com/news/Intel-Thin-Layout-Optimizer.

It was open source, but has since been deprecated.

Propeller can’t really do many instruction level modifications due to how it works (constructs a layout file that then gets passed to the linker).

BOLT could do this, but does not as far as I’m aware.

Most of vectorization like this is also probably better done in a compiler middle end. At least in LLVM, the loop vectorizer and especially the SLP Vectorizer do a decent job of picking up most of the gains.

You might be able to pick up some gains by doing it post-link at the MC level, but writing an IR level SLP Vectorizer is already quite difficult.

I might be thinking of a different project then...

I swore Intel had their own PLO tool, but I can only find https://github.com/clearlinux/distribution/issues/2996.

Post link optimization (PLO) tools have been around for quite a while. In particular, Meta’s BOLT (fully upstream in LLVM) and Google’s Propeller (somewhat upstream in LLVM, but fully open source) have been around for 5+ years at this point.

It doesn’t seem like Intel’s BOT delivers more performance gains, and it is closed source.

Quite a few patches have landed. A couple features using this have already shipped in Apple’s downstream clang.

You can make the synthetic benchmarks relatively accurate, it just takes effort. The compile-time hit and additional effort is often worth it for the extra couple percent for important applications.

Performance is also pretty different on the scales that performance engineers are interested in for these sorts of production codes, but without the build system scalability problems that LTO has. The original AutoFDO paper shows an improvement of 10.5%->12.5% going from AutoFDO to instrumented PGO. That is pretty big. It's probably even bigger with newer instrumentation based techniques like CSPGO.

They also mention the exact reasons that AutoFDO will not perform as well, with issues in debug info and losing profile accuracy due to sampling inaccuracy.

I couldn't find any numbers for Chrome, but I am reasonably certain that they have tried both and continue to use instrumented PGO for the extra couple percent. There are other pieces of the Chrome ecosystem (specifically the ChromeOS kernel) that are already optimized using sampling-based profiling. It's been a while since I last talked to the Chromium toolchain people about this though. I also remember hearing them benchmark FEPGO vs IRPGO at some point and concluding that IRPGO was better.

I'm not sure where you're getting your information from.

Chrome (and many other performance-critical workloads) is using instrumented PGO because it gives better performance gains, not because it's a more mature path. AutoFDO is only used in situations where collecting data with an instrumented build is difficult.

It's not called AutoFDO. AutoFDO refers to a specific sampling-based profile technique out of Google (https://dl.acm.org/doi/abs/10.1145/2854038.2854044). Sometimes people will refer to that as PGO though (with PGO and FDO being somewhat synonymous, but PGO seeming to be the preferred term in the open source LLVM world). Chrome specifically uses instrumented PGO which is very much not AutoFDO.

PGO works just fine in Rust and has support built into the compiler (https://doc.rust-lang.org/rustc/profile-guided-optimization....).

Do you have more information on how the dataset was constructed?

It seems like somehow build systems were invoked given the different targets present in the final version?

Was it mostly C/C++ (if so, how did you resolve missing includes/build flags), or something else?

I'm not sure it's likely that the LLM here learned from gcc. The size optimization work here is focused on learning phase orderings for LLVM passes/the LLVM pipeline, which wouldn't be at all applicable to gcc.

Additionally, they train approximately half on assembly and half on LLVM-IR. They don't talk much about how they generate the dataset other than that they generated it from the CodeLlama dataset, but I would guess they compile as much code as they can into LLVM-IR and then just lower that into assembly, leaving gcc out of the loop completely for the vast majority of the compiler specific training.

This would be difficult to deploy as-is in production.

There are correctness issues mentioned in the paper regarding adjusting phase orderings away from the well-trodden O0/O1/O2/O3/Os/Oz path. Their methodology works for a research project quite well, but I personally wouldn't trust it in production. While some obvious issues can be caught by a small test suite and unit tests, there are others that won't be, and that's really risky in production scenarios.

There are also some practical software engineering things like deployment in the compiler. There is actually tooling in upstream LLVM to do this (https://www.youtube.com/watch?v=mQu1CLZ3uWs), but running models on a GPU would be difficult and I would expect CPU inference to massively blow up compile times.

Sure, performance is more interesting, but it's significantly harder.

With code size, you just need to run the code through the compiler and you have a deterministic measurement for evaluation.

Performance has no such metric. Benchmarks are expensive and noisy. Cost models seem like a promising direction, but they aren't really there yet.

I'm reasonably certain the authors are aware of alive2.

The problem with using alive2 to verify LLM based compilation is that alive2 isn't really designed for that. It's an amazing tool for catching correctness issues in LLVM, but it's expensive to run and will time out reasonably often, especially on cases involving floating point. It's explicitly designed to minimize the rate of false-positive correctness issues to serve the primary purpose of alerting compiler developers to correctness issues that need to be fixed.

PGO can be used in such situations, but the profile needs to be checked in. Same code + same profile -> same binary (assuming the compiler is deterministic, which is tested quite extensively).

There are several big projects that use PGO (like Chrome), and you can get a deterministic build at whatever revision using PGO as the profiles are checked in to the repository.

I would not say we are anywhere close to perfect in compilation.

Even just looking at inlining for size, there are multiple recent studies showing ~10+% improvement (https://dl.acm.org/doi/abs/10.1145/3503222.3507744, https://arxiv.org/abs/2101.04808).

There is a massive amount of headroom, and even tiny bits still matter as ~0.5% gains on code size, or especially performance, can be huge.

Right, it's only solving phase ordering.

In practice though, correctness even over ordering of hand-written passes is difficult. Within the paper they describe a methodology to evaluate phase orderings against a small test set as a smoke test for correctness (PassListEval) and observe that ~10% of the phase orderings result in assertion failures/compiler crashes/correctness issues.

You will end up with a lot more correctness issues adjusting phase orderings like this than you would using one of the more battle-tested default optimization pipelines.

Correctness in a production compiler is a pretty hard problem.

LLVM doesn’t spend really any runtime solving the phase ordering problem since the pass pipelines are static. There have been proposals to dynamically adjust the pipeline based on various factors, but those are a ways out from happening.

Pretty much this. It's called Alive2.

https://dl.acm.org/doi/abs/10.1145/3453483.3454030

ML 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.

What'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 2. https://arxiv.org/abs/2207.08389 3. https://arxiv.org/abs/2112.14679 4. https://ieeexplore.ieee.org/document/9926313 5. https://arxiv.org/abs/1807.06735

Most 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.

I did a bit of work on this last summer on (much) smaller models [1] and it was briefly discussed towards the end of last year's MLGO panel [2]. For heuristic replacements specifically, you might be able to glean some things (or just use interpretable models like decision trees), but something like a neural network works fundamentally differently than the existing heuristics, so you probably wouldn't see most of the performance gains. For just tuning heuristics, the usual practice is to make most of the parameters configurable and then use something like bayesian optimization to try and find an optimal set, and this is sometimes done as a baseline in pieces of ML-in-compiler research.

1. https://github.com/google/ml-compiler-opt/pull/109 2. https://youtu.be/0uUKDQyn1Z4?si=PHrx9RICJIiA3E6C

You'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.

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.

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].

We have a solution for this and are hoping to put something out in the next week.

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

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

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

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

It'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-compil...