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 (the 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 by a constant with the constant itself:
x = 5
y = x + 1 → y = 6
These are usually performed in the same pass (one pass propagates, one folds, recursively until saturation). In SSA, you only need to replace along the def-use chain; data flow analysis is not required—each variable has a unique definition point in SSA.
Conditional constant propagation is stronger: It eliminates impossible branches by using 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 doesn't 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 in 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 the definition of that operand; it may 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 preserved). 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 -- threshold is adjustable)
- Call frequency (functions called only once can have their original body deleted after inlining)
- Calls within loops (calls inside 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, making decisions one by one.
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 returning 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," and 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 only occurs when the loop bounds are compile-time constants. After unrolling, CSE and vectorization (SLP) are often triggered—adjacent loads become a single SIMD load.
7. SROA (Scalar Replacement of Aggregates)
Replace "alloca for the entire struct + load/store for fields" with "independent variables for each field":
Original: After SROA:
%struct = alloca {i32, float} ; (alloca is dismantled)
%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 promote loads/stores away.
SROA is a prerequisite for mem2reg—dismantling 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 Repeated Execution
Optimization passes are not sufficient when run just once—optimizations in pass A create new opportunities for pass B, and pass B creates new opportunities for pass A. LLVM's pass pipeline runs multiple rounds repeatedly (Inlining → CSE → DCE → LICM → ...), cleaning up residues from the previous round each time. 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 — Complete 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