Magellan: Autonomous Discovery of Novel Compiler Optimization Heuristics with AlphaEvolve

AI summary

Overview

Research area: AI for compiler optimization — combining large language model (LLM)-driven program synthesis with evolutionary search to automatically design compiler optimization heuristics.

Technical level: Advanced. The paper assumes familiarity with compiler internals (LLVM passes, function inlining, register allocation, XLA), program synthesis, and evolutionary/autotuning search methods.

Scope: The paper presents Magellan, an agentic framework that evolves executable C++ decision logic inside production compilers, and reports case studies on LLVM function inlining (for binary size and for runtime performance), LLVM register allocation, and preliminary XLA results on graph rewriting and auto-sharding.

What This Paper Is About

Compilers depend on hand-written heuristics to decide how to optimize code, and these rules are hard to design, tune, and maintain as software and hardware become more diverse. Instead of generating per-program optimization sequences or replacing the compiler with an LLM code generator, the authors target the compiler's own decision logic: they search over human-readable, deployable C++ implementations of a compiler pass and evaluate candidates on real macro-benchmarks. The goal is to produce heuristics that match or beat decades of manual engineering while remaining as shippable and maintainable as human-authored compiler code.

Key Contributions

1. Magellan, an end-to-end compiler optimization agent. Built on AlphaEvolve and paired with an LLM coding agent, Magellan evolves compiler passes by synthesizing and evaluating executable C++ heuristics via a simple integration step into existing compilers, demonstrated with LLVM (and portable to XLA).

2. A hierarchical search strategy. The system separates high-level policy design from low-level parameter tuning: the LLM proposes a heuristic template with symbolic hyperparameters exposed as compiler flags, and an external black-box autotuner later fills in those values.

3. Case studies on realistic production compiler tasks. Function inlining for binary size, function inlining for end-to-end performance, and register allocation in LLVM, plus preliminary results on XLA graph rewriting and auto-sharding, showing code-size reduction and runtime speedups over expert-crafted baselines.

4. Evidence of generalization and maintainability. The evolved inlining policy is compact (143 lines of executable logic versus a 2,115-line manual implementation after removing comments and blanks, roughly 15x shorter) and generalizes across time and across application domains without retraining.

Main Findings

• Feature-based inlining for size: Starting from a naive policy that always returns false, Magellan composing 38 predefined MLInlineAdvisor features achieved a 4.27% size reduction relative to LLVM's upstream heuristic after 1.5 days of sequential exploration, converging to a stable plateau within a few dozen iterations.

• API-level inlining for size: When Magellan generated the entire heuristic directly using LLVM APIs, it started from a weaker initial point and had a longer trial-and-error phase, but continued improving beyond the feature-based plateau, reaching a 5.23% improvement over the human-developed heuristic at the end of the same 1.5-day search window.

• Autotuning accelerates convergence: With a policy template held fixed and an autotuner proposing batches of 10 candidate hyperparameter configurations per outer iteration, Magellan achieved more than a 5% size reduction in roughly 5 hours, within just 10 outer iterations (100 program samples). The invalid rate dropped from over 65% (LLM proposing full heuristics directly) to 13% with autotuning, a 5x reduction in wasted samples.

• Temporal generalization: Evaluating the best policy across four snapshots of the application benchmark collected over consecutive months, Magellan delivered code size reductions between 5.75% and 5.95%, slightly outperforming a neural network policy trained around 2 years earlier with evolutionary strategy followed by offline imitation learning, despite compiler internals and workloads drifting.

• Domain generalization: Across more than ten production binaries compiled with production optimization flags (spanning domains such as search infrastructure and embedded workloads), Magellan achieved an average size reduction of 8.79%, closely matching the neural model's 8.52% and outperforming it on a majority of individual binaries.

• Inlining for performance: Using clang itself as the macro-benchmark with PGO and distributed ThinLTO at -O3, and with 40 autotuner hyperparameter proposals per iteration, Gemini-2.5-Pro recovered from a naive false starting policy but plateaued around a -2.4% regression after 60 iterations and did not surpass the baseline. Gemini-3-Pro also failed to move beyond 0% after 100 iterations (about one week of sequential evaluation). Seeding Gemini-3-Pro with the best Gemini-2.5-Pro heuristic let it escape the plateau and surpass the hand-tuned baseline by 0.61%.

• Register allocation: Targeting the priority-queue policy for live-range processing in RegAllocGreedy on a large-scale production search workload, Magellan converged to a surprisingly simple constant-value policy, improving from -0.55% to -0.15% within relatively few iterations and matching intricate human-crafted heuristics.

• XLA graph rewriting: Synthesizing extraction heuristics for equality-saturation-based graph rewriting (building on Enzyme-JAX) produced a 7% improvement over manually designed policies.

• XLA auto-sharding: Following the ASPLOS'25 IOPDDL contest protocol (5 public and 20 private instances), Magellan evolved a strategy to reduce global cost while respecting memory constraints, reaching performance comparable to top contest submissions after one week of evolution and without manually engineered cost models.

• What the synthesized policies look like: The size-oriented inlining policy aggressively inlines single-use functions so the call site and entire function body disappear, prioritizes readonly functions that enable dead code elimination, uses a weighted complexity model that penalizes control-flow instructions more heavily, and adds bonuses for constant arguments and exact type matches. The performance-oriented policy skips zero-cost instructions, applies large bonuses for constant arguments, loop nesting, and vector code, and scales thresholds aggressively for hot call sites.

Methodology in Plain English

Magellan runs four stages in a closed loop. First, an LLM (AlphaEvolve, using Gemini-2.5-Pro as the base model unless noted) edits a marked region of a compiler source file (EVOLVE-BLOCK comments delimit editable code) to propose a decision policy, writing it as a template whose numeric constants are exposed as compiler flags. Second, the compiler is rebuilt and the resulting toolchain is run on representative macro-benchmarks, with the reward measured from real outcomes such as binary size (via llvm-size) or runtime performance (via perf stat) — the authors deliberately use end-to-end reward rather than synthetic objectives, and note that proxy signals can substitute when full evaluation is too costly. Third, a black-box autotuner (Vizier) searches over the exposed hyperparameters while the template stays fixed, returning the best configuration. Fourth, the scores, tuning logs, and profiling traces are fed back to AlphaEvolve, which performs evolutionary search over templates and proposes new variants. The loop repeats. Because heuristics are ordinary C++ that conform to compiler APIs, only policies that integrate successfully are evaluated, so compiler output correctness is preserved by the existing infrastructure. Experiments use Google's internal clang/LLVM toolchain tracking LLVM's main repository tip-of-tree, with commits from the 2025 summer timeframe representative of the version used.

Why This Matters

Impact on research. The paper argues for a practical middle ground between manual engineering and integrating neural network policies into compilers. Prior neural approaches can match or beat expert heuristics but require embedding learned models into compiler infrastructure, which is expensive to reproduce for new passes, objectives, or accelerators. Framing heuristic design as program synthesis over deployable C++ means the discovered artifact has the same deployment and maintenance properties as human-written compiler code. The results also show that heavily studied, decades-old passes like inlining still contain untapped gains under scalable automated search.

Real-world applications:

• Binary size reduction for edge and mobile deployments, which the paper names specifically: Fuchsia OS, Chrome on Android, and cloud infrastructure.
• Runtime performance optimization of large production workloads under production flags (PGO, ThinLTO, -O3), exemplified by compiling clang itself.
• Register allocation policy tuning for large-scale production workloads, such as the search workload used in the study.
• ML compiler stack optimization in XLA, including equality-saturation graph rewriting and auto-sharding for distributed TPU execution from real models such as diffusion and Gemma.

Industry relevance. The paper emphasizes productivity: Magellan generates heuristics that match or surpass ones developed manually over decades, using the same macro-benchmarks human developers use, and emits concise, human-readable code that can be shipped and maintained like human-authored compiler code. It reports generalization across four monthly snapshots and more than ten production binaries without retraining or feature re-engineering, which the authors present as meeting a criterion for practical deployment in evolving toolchains.

Future Directions

1. Characterize the limits of the search. The loop is constrained by the cost of compiling and evaluating each candidate, especially for noisy performance objectives requiring macro-benchmarks. The authors want longer search iterations to characterize convergence behavior, and to understand how effectiveness scales with search budget, model choice, and objective noise.

2. Clarify when pass-level evolution beats neural policies. It remains unclear which properties make LLM-driven pass evolution competitive with neural-policy approaches, which face similar evaluation-cost challenges, and when this alternative is preferable.

3. Combine with learned representations. Magellan could complement neural approaches by automating feature discovery, for example in conjunction with learned embedding methods such as IR2Vec.

4. Move to green-field targets and new architectures. Apply Magellan to compilers for GPUs and NPUs — kernel mapping, operator scheduling, task assignment — to test whether it can discover heuristics in the absence of pre-existing literature and examples, and evolve into a platform for co-design across new architectures, tasks, and performance constraints.

The authors also note an open concern about maintainability: it is unclear whether a broader multi-objective policy (jointly optimizing size and performance at the scope of the default heuristic) would remain as concise as the 143-line size-focused policy, and XLA integration into the full pipeline was still in progress by the contest organizers at the time of writing.

Target Audience

Compiler engineers and researchers working on LLVM, XLA, or production toolchains; researchers in LLM-driven program synthesis, evolutionary search, and automated algorithm discovery; and machine learning systems practitioners interested in automating performance engineering. Readers will get the most from the paper with prior familiarity with compiler optimization passes, LLVM APIs, and search-based optimization, though the framing of the problem and the reported outcomes are accessible to a broader AI research audience.

Authors’ abstract

Modern compilers rely on hand-crafted heuristics to guide optimization passes. These human-designed rules often struggle to adapt to the complexity of modern software and hardware and lead to high maintenance burden. To address this challenge, we present Magellan, an agentic framework that evolves the compiler pass itself by synthesizing executable C++ decision logic. Magellan couples an LLM coding agent with evolutionary search and autotuning in a closed loop of generation, evaluation on user-provided macro-benchmarks, and refinement, producing compact heuristics that integrate directly into existing compilers. Across several production optimization tasks, Magellan discovers policies that match or surpass expert baselines. In LLVM function inlining, Magellan synthesizes new heuristics that outperform decades of manual engineering for both binary-size reduction and end-to-end performance. In register allocation, it learns a concise priority rule for live-range processing that matches intricate human-designed policies on a large-scale workload. We also report preliminary results on XLA problems, demonstrating portability beyond LLVM with reduced engineering effort.