🤖 AI

AI-PROPELLER: Warehouse-Scale Interprocedural Code Layout Optimization with AlphaEvolve

AI-PROPELLER introduces an agentic workflow called Magellan that evolves the Propeller post-link optimizer to achieve the first successful fine-grained interprocedural code layout optimization for large warehouse-scale applications, yielding performance improvements of 0.23% to 1.6% by leveraging real hardware execution for precise reward signals.

Original authors: Chaitanya Mamatha Ananda, Rajiv Gupta, Mircea Trofin, Aiden Grossman, Sriraman Tallam, Xinliang David Li, Amir Yazdanbakhsh

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chaitanya Mamatha Ananda, Rajiv Gupta, Mircea Trofin, Aiden Grossman, Sriraman Tallam, Xinliang David Li, Amir Yazdanbakhsh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, incredibly complex library (a computer program) with millions of books (functions) and billions of pages (code instructions). For years, librarians (optimizers) have been trying to arrange these books on the shelves to make them easier to find.

The old way of doing this was like organizing a single bookshelf at a time. If you had a book with 100 chapters, the librarian would rearrange those chapters so the most popular ones were right next to each other. This is called intraprocedural optimization. It helped, but it missed a huge opportunity: the most popular chapter of Book A might be followed immediately by the most popular chapter of Book B. If those two books were on opposite sides of the library, the reader (the computer processor) had to run all the way across the room to turn the page, wasting time and energy.

AI-PROPELLER is a new, super-smart librarian system that solves this by rearranging the entire library at once, not just one bookshelf at a time.

Here is how it works, broken down into simple concepts:

1. The Problem: The "Combinatorial" Nightmare

Rearranging one book is hard. Rearranging millions of books so that every single popular page is next to the page that comes after it (even if that page is in a different book) is a math problem so huge that human brains and traditional computers can't solve it. It's like trying to find the perfect seating arrangement for a stadium of 100,000 people where everyone wants to sit next to their best friend, but the friends are scattered across different sections.

Furthermore, the old librarians used "guesswork" (static models) to decide where to put things. They didn't actually test the arrangement; they just calculated what should work.

2. The Solution: The "AI Agent" (Magellan)

The researchers used a system called Magellan, which acts like a tireless, experimental robot team. This team has two main workers:

The Architect (AlphaEvolve): An AI that writes and rewrites the rules for how to arrange the books. It tries new ideas, like "What if we split Book A into three parts and put the middle part next to Book B?"
The Tuner (Vizier): A tool that fine-tunes the specific numbers in those rules (like "how far apart can books be?").

3. The Secret Sauce: Real-World Testing (No Guessing)

This is the most important part. Instead of the AI guessing if a new arrangement is good, the system actually builds the library and tests it.

The AI creates a new arrangement of the code.
It compiles the program into a real, working binary (like building a new version of the software).
It runs this new version on real computer hardware.
It measures exactly how fast it runs using real performance counters (like a stopwatch and a fuel gauge).

This gives the AI a "reward signal." If the new arrangement is faster, the AI gets a gold star and learns to do more of that. If it's slower, it learns to avoid that mistake. Because they tested this on real hardware in a controlled environment, the results are incredibly precise, not just theoretical.

4. The Results: Tiny Gains, Huge Impact

The paper tested this on massive, real-world software, including the LLVM Clang compiler (a tool used to build other software) and a giant Google Search service.

The Clang Compiler: The new system made it 1.6% faster.
The Google Search Service: It made the search service 0.23% faster.

You might think, "0.23% is nothing!" But in the world of massive data centers, this is like finding a hidden gold mine. If you save 0.23% of time on billions of searches every day, you save millions of dollars in electricity and server costs. It's the difference between a runner finishing a race in 9.58 seconds vs. 9.56 seconds—a tiny fraction that separates a world record from second place.

5. How It Actually Works (The "Splitting" Trick)

The paper highlights a specific trick the AI discovered.

Old Way: If a function (a piece of code) has a "hot" (frequently used) part and a "cold" (rarely used) part, the old system would split the function in two: Hot on one shelf, Cold on another.
AI-PROPELLER Way: The AI realized that sometimes, a function needs to be split into three or more pieces. It found that a specific "hot" chunk of Function A should be placed right next to a "hot" chunk of Function B, even though they are in different files. It essentially cuts the code into tiny, precise puzzle pieces and reassembles them so the most-used pieces are always touching, regardless of which "book" they originally came from.

Summary

AI-PROPELLER is the first system to successfully use AI to rearrange the internal code of massive, industrial-scale software across function boundaries. It doesn't just guess; it builds, tests, and learns from real hardware. By doing this, it squeezes out extra performance (0.23% to 1.6%) from software that was already considered "perfectly optimized," proving that even in mature systems, there is still hidden speed waiting to be found if you look at the whole picture rather than just one piece at a time.

Technical Summary: AI-PROPELLER

Problem Statement

Post-link optimizers (PLOs) like Propeller and BOLT have successfully improved the performance of large-scale warehouse applications through precise, profile-guided intraprocedural code layout. These tools reorder basic blocks within functions and split hot/cold code regions to optimize instruction cache and TLB utilization. However, they largely leave interprocedural code layout untapped.

Interprocedural layout—reordering basic blocks across function boundaries—is historically difficult due to:

Combinatorial Explosion: The search space is several orders of magnitude larger than intraprocedural exploration (e.g., a warehouse-scale application may have ~1.4 million functions and ~40 million basic blocks).
Complex Semantics: Unlike intraprocedural layout where fall-through jumps can be eliminated, interprocedural layout must strictly adhere to call-return semantics. Placing blocks from different functions adjacently does not eliminate dynamic instruction counts in the same way, making cost modeling complex.
Lack of Proven Value: Previous attempts at interprocedural layout resulted in long build times (3x–10x) with marginal or unproven performance gains, leading the community to treat it as "future work."

Consequently, the performance potential of fine-grained interprocedural layout in industrial, warehouse-scale settings remains unproven.

Methodology

The paper introduces AI-PROPELLER, a framework that leverages the Magellan agentic workflow to evolve compiler heuristics for interprocedural code layout.

1. The Magellan Framework

AI-PROPELLER integrates two components to optimize the Propeller code layout policy:

AlphaEvolve (LLM Agent): Evolves the source code of the layout heuristic (specifically code_layout.cc). It takes an initial policy and a prompt, generating novel code edits (additions, modifications, removals) to improve the heuristic.
Vizier (Black-box Optimizer): Fine-tunes the numerical hyperparameters (compiler flags) exposed by the evolved policy.

2. High-Fidelity Reward Signal

A critical innovation is the move away from approximate static cost models. To ensure the evolutionary loop receives a precise, noise-free reward signal:

Hardware Execution: The system compiles multiple layout variants and executes them on actual hardware (Intel Skylake systems).
Noise Reduction: The environment is strictly controlled (Turbo Boost, SMT, and ASLR disabled; CPU frequency locked at 75% peak).
Statistical Stability: Each binary is executed 10 times to ensure run-to-run variance is below 0.05%.
Reward Calculation: The reward is derived from real performance counters (cycle counts), calculated as $1 - (\text{cycles} / \text{reference})$ .

3. The Evolved Policy

The framework evolves a policy that governs three key factors of interprocedural reordering:

Chain Split Threshold: Determines when to split sequences of basic blocks. AI-PROPELLER increased this threshold (from 0 to 213), allowing more sequences to be split and reinserted across functions.
Memory Offsets (Forward/Backward): Defines the maximum distance between blocks for an edge to be considered profitable. The evolved policy expanded these limits significantly (e.g., forward from 1024 to 3059 bytes) to capture long-range caller-callee relationships.
Global Sorting Logic: Replaced function-specific block ID sorting with a global layout index to ensure the final binary preserves the intended interprocedural order.

Key Contributions

First Demonstration of Interprocedural Gains: This is the first study to demonstrate clear performance improvements using fine-grained interprocedural code layout on real-world, large warehouse-scale binaries.
Scalable Optimization: The framework optimizes industrial-scale applications (e.g., LLVM Clang, Search) without perceptible degradation in build time or memory usage, overcoming the historical engineering barrier of interprocedural optimization.
Novel Heuristic Discovery: The system autonomously discovered non-intuitive layout policies that outperform state-of-the-art static heuristics (Ext-TSP) and function-level reordering (CDSort).

Experimental Results

The framework was evaluated on front-end bound workloads (LLVM Clang, LevelDB, Redis, and a proprietary warehouse-scale Search application).

Performance Improvements:
- LLVM Clang: Achieved a 1.6% reduction in execution time over the baseline (FDO + ThinLTO + Ext-TSP). This represents squeezing an additional ~20% of performance out of an already highly optimized binary.
- Warehouse-Scale Search: Achieved a 0.23% improvement over the deployed Ext-TSP baseline. While seemingly small, the authors note this is significant for operational costs at this scale.
- Other Benchmarks: LevelDB and Redis also showed statistically significant improvements (p-value ~0).
Microarchitectural Impact:
- Frontend Stalls: AI-PROPELLER significantly reduced frontend-bound stalls (instruction fetch/decode stalls). For example, in Clang, stalls dropped from 45% to 39%; in Redis, from 49% to 34.2%.
- Instruction Retirement: Improved the percentage of CPU pipeline slots spent retiring instructions (useful work), e.g., Clang improved from 27% to 30%.
Ablation Study (Inter vs. Intra):
- When interprocedural transformations were disabled (forcing blocks to remain contiguous within functions), the performance gain dropped from 1.6% to ~0.3%.
- This indicates that approximately 80% of the speedup is derived specifically from the ability to interleave blocks across function boundaries, confirming that global interprocedural reordering is the primary driver of success.

Significance and Claims

The paper claims that AI-PROPELLER is the first framework to successfully apply fine-grained interprocedural code layout to large binaries in industrial settings. Its significance lies in:

Validating the Potential: Proving that the "untapped" potential of interprocedural layout is real and measurable, even in hyper-optimized environments.
Overcoming the Search Space: Demonstrating that AI-driven agentic workflows can navigate the exponentially larger search space of interprocedural layout where manual tuning and static heuristics fail.
Practicality: Showing that these optimizations can be achieved without compromising the scalability of distributed build systems, making them viable for production use.

The authors emphasize that while the percentage gains (0.23%–1.6%) may appear modest, they are operationally significant for warehouse-scale applications where marginal improvements translate to substantial business value, and they are exceptionally difficult to achieve given the existing state-of-the-art optimization techniques.