Breeding Better Binaries with Shackleton

This is a PRISM adaptation of Siddharth's original Shackleton write-up, with the math made interactive where it helps. The primary paper is Optimizing LLVM Pass Sequences with Shackleton: A Linear Genetic Programming Framework, and the framework lives at ARM-software/Shackleton-Framework.

The core idea is simple enough to sound suspicious: instead of trusting one fixed compiler optimization pipeline, treat the order of LLVM passes as something that can evolve. Generate many pass sequences, compile a benchmark with each one, measure the runtime, keep the better ones, mutate and recombine them, and repeat.

That sounds like compiler alchemy. It is actually a search problem.

What LLVM is optimizing

A compiler takes source code and produces machine code. LLVM adds an intermediate representation, usually called IR, between those two ends:

That middle layer is the trick. If a frontend can emit LLVM IR, then LLVM can apply the same transformations before generating code for x86, Arm, RISC-V, or another target. Those transformations are called passes.

An analysis pass reads IR and computes facts: which values are dead, which pointers may alias, where loops begin and end. A transform pass changes IR: it inlines functions, removes dead code, simplifies control flow, unrolls loops, or combines instructions.

The order matters because a transform can invalidate earlier analysis, and one transform can create or destroy opportunities for another transform. instcombine before gvn is not the same genome as gvn before instcombine.

The search space explodes

Represent one compiler pipeline as an ordered pass sequence:

P = \langle p_1, p_2, \dots, p_n \rangle

Each pass $p_i$ comes from the available set $\mathcal{P}$ . If we allow every sequence length from 1 to $L$ , the possible sequence space is:

\mathcal{S} = \bigcup_{n=1}^{L} \mathcal{P}^{n}

and its size is:

|\mathcal{S}| = \sum_{n=1}^{L} |\mathcal{P}|^n

Slide the numbers around. Even conservative values become absurd quickly.

evolution workbench

Search atlas and generation cockpit

gen

fit

1.031

div

76%

population manifoldGeneration 0; best fitness 1.031; focused genome rank 1.

combinatorial scale field

1.27 x 10^230

The atlas is not a chart of every sequence; it is a compressed sky map of an impossible search volume. Step the run and watch selection make a tiny moving sample of it.

observable-universe anchor

10^150.1 larger

Same scale comparison as the prose, held beside the living run.

failed compiles

0/18

Bad genomes remain visible because they still consume search effort.

pass alphabet

200

max length

100

population rank rail

best 1.031

This is why "just try every pass order" dies immediately. If there are 200 possible passes and a maximum length of 100, the dominant term is roughly $200^{100}$ , which is about $10^{230}$ . For comparison, the usual back-of-the-envelope estimate for atoms in the observable universe is $10^{80}$ .

Brute force is gone before the compiler starts.

Why genetic programming fits the shape

Genetic programming starts with a population of candidate programs. Each candidate gets scored by a fitness function. Better candidates are more likely to become parents. Parents produce children through crossover and mutation. The weak candidates get replaced. Repeat until the search budget runs out or the population stops improving.

For Shackleton, a genome is a linear sequence of compiler passes:

G_i = [p_1, p_2, \dots, p_{L_i}]

In pure GP mode, sequence lengths and pass choices can be sampled at random:

L_i \sim U(L_{\min}, L_{\max}), \quad p_j \sim U(\mathcal{P})

In genetic improvement mode, the initial population can start near a known-good pipeline such as -O2, then mutate around it. That is much less chaotic because the search begins in a region where programs usually compile and run.

Selection pressure is a knob

Shackleton uses tournament selection. Pick $k$ individuals from the population, keep the fittest among them, and use that winner as a parent. Bigger tournaments increase pressure toward the current best genomes.

If ranks are sampled with replacement from a population of size $N$ , the probability that rank $r$ wins is:

\Pr(r) = \left(\frac{N-r+1}{N}\right)^k - \left(\frac{N-r}{N}\right)^k

That probability depends on rank, not the raw fitness magnitude. The score decides ordering; $k$ decides how aggressively ordering is exploited.

selection pressure

Tournament arena

gen

fit

1.031

div

76%

pressure matrix

Pick how many genomes enter each tournament.

k=3

rank probability ribbon

#115.8%

#214.0%

#312.4%

#410.8%

#59.4%

#68.0%

#76.8%

#85.7%

#94.6%

#103.7%

current winner

rank 10

Fitness 1.021 advances into crossover; increase k to watch diversity collapse faster.

Too little pressure and the population wanders. Too much pressure and it converges early on one decent but not great sequence. That is the central evolutionary tradeoff in miniature.

Crossover and mutation

Linear genetic programming is convenient here because a compiler pipeline is already a list. Single-point crossover can take a prefix from one parent and a suffix from another:

\text{child}_1 = [A_1, \dots, A_c, B_{c+1}, \dots, B_{L_B}]

\text{child}_2 = [B_1, \dots, B_c, A_{c+1}, \dots, A_{L_A}]

Mutation then perturbs the child: replace a pass, insert a pass, delete a pass, or swap adjacent passes. If a child has length $L$ and the per-position mutation probability is $p_m$ , the expected number of mutation events is:

\mathbb{E}[\text{mutations}] = Lp_m

linear genetic programming

Genome surgery table

gen

fit

1.031

div

76%

parent A prefix

cut 4

licm

loop-unroll

parent B suffix

cut 4

instcombine

sroa

mem2reg

sroa

mutation toolhead

preview fitness

1.0305

Mutations update this immediately.

compile state

valid

Invalid sequences stay inspectable.

child length

L=9

Insert/delete tools change the program body.

child after crossover and manual mutation

Arrow keys move focus across tokens; Enter mutates the focused pass.

L=11

This is not magic. Crossover tries to preserve useful subsequences. Mutation injects new local changes. The hard part is that compiler pass interactions are nonlinear, so a useful subsequence in one context can become useless in another.

How Shackleton stores genomes

Shackleton uses the Osaka List Structure, or OSL, to hold genetic sequences. It is a doubly linked list whose nodes contain generic genetic objects. In the LLVM pass domain, each object wraps a pass invocation such as instcombine, licm, or gvn.

The linked-list choice makes insert and delete mutations cheap:

T_{\text{insert/delete}} = O(1)

The tradeoff is traversal:

T_{\text{traverse}} = O(n)

For pass sequences around tens or low hundreds of nodes, that is a practical trade. Insert and delete happen constantly during evolution; pointer traversal is not usually the dominant cost compared with compiling and benchmarking every individual.

The generic genetic object abstraction is the important engineering move. Shackleton's core loop does not need to know whether it is evolving AArch64 instructions or LLVM passes. It asks the object how to mutate itself, evaluates the resulting individual, and records ancestry and fitness metadata.

Fitness is measured, not inferred

For an individual $i$ , compile a benchmark $f$ with genome $G_i$ :

\text{binary}_i = \text{compile}(f, G_i)

Run the binary $R$ times:

T_i^{(1)}, T_i^{(2)}, \dots, T_i^{(R)}

Average the timings:

\hat{T}_i = \frac{1}{R} \sum_{r=1}^{R} T_i^{(r)}

Then score relative to a baseline such as -O2:

\Phi_i = \frac{\hat{T}_{\text{-O2}}}{\hat{T}_i}

A score above 1 means the candidate is faster than baseline. If the sequence fails to compile or crashes at runtime, assign it zero fitness and move on.

The nasty part is that runtime measurements are noisy. CPU frequency scaling, cache state, thermal behavior, and background work can easily create apparent wins that vanish under repeated measurement.

benchmark noise

Runtime oscilloscope

gen

fit

1.031

div

76%

benchmark tape

97.04 ms

96.1

95.2

93.8

98.2

94.2

106.3

95.5

benchmark runs

Load a cartridge to recalibrate the trace.

runtime noise

Load a cartridge to recalibrate the trace.

mean runtime

97.04 ms

95% band +/- 3.21 ms

fitness

1.0305

Baseline runtime divided by observed candidate runtime.

verdict

noise risk

Winner may be timing noise, not a real compiler win.

This is why a compiler autotuner needs more than one benchmark run. If the claimed speedup is smaller than the timing uncertainty, evolution may be selecting noise.

What the LLVM mode does

With the -llvm_optimize mode, Shackleton can:

Take source files from its LLVM input directory.
Generate candidate pass sequences.
Run LLVM tooling to apply the pass sequence.
Compile the transformed IR.
Benchmark the resulting binary.
Keep evolving toward lower runtime.

At a high level:

The paper reports experiments on two applications with different complexity levels and studies how hyperparameters affect the search. The important result is not "evolution replaces -O2 tomorrow." It is more modest and more useful: LLVM pass ordering can be exposed as an evolutionary search space, but the search is expensive, noisy, and benchmark-specific.

Where it bites in practice

The biggest practical problems are not hard to name.

Compilation failures. Random pass orders often produce invalid or broken outputs. Those candidates still cost compilation time before they get a zero.

Epistasis. The value of one pass depends on the passes around it. A one-pass difference can move the program to a completely different performance region:

\Phi(P) \not\approx \Phi(P') \quad \text{even when } \text{diff}(P, P') = 1

Overfitting. The best sequence for one benchmark input may not generalize to another input size, another CPU, or another cache state.

Measurement cost. A population of 150 individuals over 50 generations is 7,500 compile-and-run evaluations before repeated timing runs. If $R = 10$ , the runtime measurement count alone becomes 75,000.

Noisy winners. If the fastest individual is only 1 percent better than baseline, but benchmark variance is 3 percent, the "winner" may just be lucky.

How it compares

Approach	Method	Good at	Weak at
Shackleton	Linear genetic programming over pass sequences	No training set, per-program search, weird targets	Expensive evaluation, noisy fitness, weak generalization
Random search	Sample pass sequences directly	Simple, parallel, honest baseline	Sample-inefficient
Hill climbing	Mutate a known-good sequence and keep improvements	Cheap local improvement	Gets trapped in local optima
ML-guided optimization	Learn policies or costs from program features	Generalizing from data	Needs training data and model infrastructure
Hand-tuned `-O2`	Human-designed general pipeline	Strong default for common workloads	Not specific to your one benchmark and one target

Shackleton is most attractive when the deployment target is fixed and unusual: a firmware workload on a specific embedded board, a custom RISC-V core, or a benchmark where one small runtime win matters enough to pay for overnight search.

The take

The neat part is not that evolution is guaranteed to beat LLVM's hand-tuned defaults. It probably will not, most of the time. LLVM's default pipelines are the result of years of expert work and broad testing.

The neat part is that Shackleton reframes optimization as an experiment you can run against your exact program and hardware. If the pass landscape has a narrow local improvement that general-purpose -O2 does not hit, evolutionary search might find it. If it does not, the failed search still teaches you something about the stability of your benchmark and the strength of LLVM's default pipeline.

That makes Shackleton less like a replacement compiler and more like a lab instrument: expensive, picky, sometimes noisy, but very good at forcing vague optimization guesses into measurable hypotheses.