On this page
Classic Optimizations
Seven classic optimizations every optimization pipeline must perform—from constant folding and loop invariant code motion to SROA—how each leverages data flow analysis to find opportunities, and the hard limits when they cannot be applied (side effects, volatile, irreducible control flow).
Overview
Data flow analysis provides information about "which expressions have been computed at a given point" and "which variables are still live." This article discusses what to do with this information: seven optimizations that industrial compilers must perform, how each uses the results of data flow analysis to identify optimization opportunities, and when they cannot be applied (constraints are more numerous than you might think). These optimizations correspond to different passes in LLVM and are run repeatedly in the compilation pipeline—optimizations in one pass create opportunities for the next pass.
Prerequisite for all optimizations: Perform them in SSA form. The def-use chains in SSA make each optimization a sparse operation with O(n) or O(n log n) complexity.
1. Constant Folding and Propagation
Constant folding: Compute constant expressions at compile time:
x = 2 + 3 → x = 5
y = a * 0 → y = 0
Constant propagation: Replace all uses of a variable defined as a constant with the constant itself:
x = 5
y = x + 1 → y = 6
These are usually performed in the same pass (one pass of propagation, one of folding, recursively until saturation). Under SSA, this only requires replacing along the def-use chain; no data flow analysis is needed—each variable has a unique definition point in SSA.
Conditional constant propagation is stronger: it eliminates impossible branches by leveraging constant conditions like if (false) { ... }, preventing the code within those branches from being compiled. This is the core of the Wegman-Zadeck algorithm, based on Sparse Conditional Constant Propagation (SCCP) in SSA.
2. CSE (Common Subexpression Elimination)
Problem: a = b + c; ... ; d = b + c. If b and c are not modified in between, the second b + c is a common subexpression and can be replaced with the value of a.
Implementation relies on available expressions (from data flow analysis):
For each expression e = x op y:
Check in the available expressions information: is e "still valid" at the current point?
If valid: use the existing result, delete the current computation.
Otherwise: keep the current computation, mark e as "available here".
LLVM uses GVN (Global Value Numbering) as a generalization of CSE for CSE—it does not just look for "two occurrences of the same expression," but assigns a number to each value. If two different expressions have equal values (e.g., x+1 and 1+x, when commutativity holds), they share the same value number.
3. DCE (Dead Code Elimination)
Problem: If the value produced by an instruction is never used, that instruction can be deleted.
DCE is extremely simple under SSA—follow the def-use chain:
worklist = all instructions
for each instruction:
if the value produced by the instruction has no users (use list is empty)
AND the instruction has no side effects (is not a store/call/IO):
mark as dead
for each operand of the instruction: check its definition;
it might become dead due to losing this user.
Iterate until a fixed point is reached.
Several hard limits prevent elimination: store (modifies memory, which might be loaded elsewhere), call (may have side effects, even if the return value is unused), and volatile load/store (explicitly required to be retained). Instructions with side effects can only be eliminated when the compiler proves that the side effect's value is also not observed—this requires heavier analysis (e.g., MemorySSA, see below).
4. Inlining
Problem: call @f copies the body of function f directly to the call site, eliminating function call overhead (parameter passing/jump/return) and exposing context for subsequent optimizations (the function body may trigger new constant folding/CSE/DCE under specific parameter values).
The trade-off for inlining is not "whether to do it," but when to do it:
Decision factors:
- Function body size (small functions are inlined; large functions may not be -- thresholds are adjustable)
- Call frequency (functions called only once can have their original body deleted after inlining)
- Calls inside loops (calls within loop bodies are more likely to be inlined, as inlining may trigger loop optimizations)
- Recursive functions are inlined only for the first N levels (to prevent infinite expansion)
LLVM's inlining pass is based on a cost model—it estimates the size change and performance gain after inlining for each call site, deciding on a case-by-case basis.
5. LICM (Loop Invariant Code Motion)
Problem: Expressions that compute the same value in every iteration of a loop body are moved outside the loop to be computed only once:
while (i < n) { t = a + b ← moved before the loop
x = a + b; → while (i < n) {
i = i + 1; i = i + 1;
} }
Implementation relies on loop detection (finding natural loops—one header block dominates all body blocks, and there is a back edge leading back to the header):
For each instruction instr in loop L:
if none of instr's operands change within the loop (they are defined as loop constants or come from outside the loop):
if instr is dominated by the same instruction on all paths reaching it (it won't be skipped from some paths):
if instr has no side effects:
move instr to the loop preheader → delete from original location.
The first two conditions ensure that "moving it out does not change semantics," while the third excludes instructions with loop dependencies.
6. Loop Unrolling
Copy the loop body N times to reduce the overhead of branches/back-edges/induction variable updates:
for i in 0..4: a[0] = b[0] + c[0]
a[i] = b[i] + c[i] → a[1] = b[1] + c[1]
a[2] = b[2] + c[2]
a[3] = b[3] + c[3]
LLVM unrolls by 2–4 times by default; full unrolling occurs only when the loop bound is a compile-time constant. After unrolling, CSE and vectorization (SLP) are often triggered—adjacent loads become a single SIMD load.
7. SROA (Scalar Replacement of Aggregates)
Replace "alloca of an entire struct + load/store of fields" with "independent variables for each field":
Original: After SROA:
%struct = alloca {i32, float} ; (alloca is removed)
%f0 = gep %struct, 0, 0 %x = ...
store i32 %x, ptr %f0 %y = ...
%f1 = gep %struct, 0, 1 %add = add i32 %x, ...
store float %y, ptr %f1
%r = load i32, ptr %f0 → each field becomes an independent SSA virtual register
%add = add i32 %r, 1 mem2reg continues to hoist load/store away.
SROA is a prerequisite for mem2reg—splitting aggregates into fields allows mem2reg to promote each field individually to SSA. Together, they form the first set of passes in the LLVM optimization pipeline.
Optimization Order and Re-running
Optimization passes are not sufficient to run just once—optimizations in pass A create new opportunities for pass B, and optimizations in pass B create new opportunities for pass A. LLVM's pass pipeline runs multiple rounds repeatedly (inlining → CSE → DCE → LICM → ...), with each round cleaning up residues from the previous one. Loop optimizations (LICM + Unrolling) are often placed in a separate phase to perform large-scale loop transformations centrally, followed by a new round of scalar optimizations.
References
- Dragon Book: Chapters 9–10 — Comprehensive classification of machine-independent optimizations
- Cooper/Torczon: "Engineering a Compiler", Chapters 8–10 — Algorithms and pseudocode for each optimization
- LLVM:
lib/Transforms/Scalar/(scalar passes),lib/Transforms/IPO/(interprocedural passes),lib/Analysis/(data flow analysis)
Keywords: constant folding, constant propagation, SCCP, CSE, common subexpression elimination, GVN, global value numbering, DCE, dead code elimination, inlining, cost model, LICM, loop invariant code motion, loop unrolling, SROA, scalar replacement, mem2reg, pass pipeline, phase ordering