Code Optimization: Loop Unrolling, Inlining, Constant Folding

Compilers Compilers 8 min read 1620 words Beginner ExcellentWiki Editorial Team

Code optimization transforms a program into an equivalent version that runs faster, consumes less memory, or uses less energy. The optimizer sits between the frontend (which produces IR) and the backend (which generates machine code). It is the phase that makes compiled languages competitive with hand-tuned assembly. Most compiler optimization passes operate on Static Single Assignment (SSA) form, which simplifies data-flow analysis and enables transformations that would be complex or impossible with mutable variables. This article covers the major classes of compiler optimizations: loop transformations, function inlining, constant propagation and folding, and dead code elimination.

SSA Form: The Foundation for Optimization

Static Single Assignment form ensures that each variable is assigned exactly once. When a variable has multiple definitions in the original program, SSA introduces φ (phi) functions at control-flow merge points to select the correct value. The dominance frontier algorithm, described by Cytron et al. in their 1991 paper “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph,” efficiently places φ functions.

SSA enables several optimizations:

Constant propagation becomes trivial — if a variable has a single definition and that definition is a constant, every use can be replaced
Dead code elimination is straightforward — if a variable is never used, its defining instruction can be removed
Global Value Numbering (GVN) detects redundant computations across basic blocks
Partial redundancy elimination (PRE) moves computations out of loops

LLVM’s mem2reg pass converts alloca-based variables to SSA registers. GCC’s ssa pass performs an equivalent transformation early in the optimization pipeline. The optimization pipeline in both GCC and LLVM runs dozens of passes in a carefully ordered sequence, with each pass cleaning up work for the next.

Loop Optimizations

Loops dominate execution time in most programs — the 90-10 rule suggests that 90% of execution time is spent in 10% of the code, and that 10% is typically loops. Compilers therefore invest heavily in loop optimizations.

Loop Unrolling

Loop unrolling reduces loop overhead by replicating the loop body multiple times. Instead of:

for (i = 0; i < 100; i++) a[i] = b[i] + c[i];

The compiler might generate:

for (i = 0; i < 100; i += 4) {
    a[i]   = b[i]   + c[i];
    a[i+1] = b[i+1] + c[i+1];
    a[i+2] = b[i+2] + c[i+2];
    a[i+3] = b[i+3] + c[i+3];
---

This reduces the number of branch-and-increment operations by 75% and exposes more instruction-level parallelism. The tradeoff is increased code size, which can cause instruction cache misses. GCC’s -funroll-loops flag controls unrolling; LLVM’s LoopUnrollPass uses heuristics based on loop trip count and body size.

Loop Invariant Code Motion (LICM)

LICM moves computations that produce the same result on every iteration outside the loop body. If an array length is recomputed in every iteration:

for (i = 0; i < length; i++) { ... }

But length does not change, the compiler hoists it. LICM requires alias analysis to ensure safety — the compiler must prove that hoisting does not introduce exceptions or affect memory operations.

Loop Vectorization

Vectorization transforms scalar loop iterations into SIMD (Single Instruction, Multiple Data) operations. Modern CPUs have SIMD instruction sets (SSE, AVX, NEON, SVE) that operate on vectors of 128, 256, or 512 bits. Auto-vectorization analyzes loop-carried dependencies and alignment to generate vector code. LLVM’s LoopVectorizePass is one of its most impactful optimization passes, often producing 2x-4x speedups on numerical code.

The Intel C++ Compiler is particularly aggressive with vectorization, using runtime checks to prove aliasing safety when static analysis cannot. GCC and Clang both support -fopt-info-vec to report which loops were vectorized.

Function Inlining

Inlining replaces a function call with the body of the callee, avoiding call overhead and enabling further optimizations that span the caller-callee boundary. When a small function like square(x) { return x * x; } is inlined, the multiplication can be constant-folded or CSE’d with surrounding code.

Inlining decisions are economic: the compiler estimates the cost of the call site vs. the benefit of inlining. Heuristics consider:

Function size — large functions are less profitable to inline
Call frequency — hot call sites benefit more from inlining
Call depth — deeply nested inlining causes code bloat
Parameter constancy — inlining with constant parameters enables constant propagation

LLVM’s InlineCost analysis provides a detailed cost model. The AlwaysInline pass inlines functions marked __attribute__((always_inline)). Both GCC and Clang support -finline-limit=N and profile-guided inlining with -fprofile-generate.

Constant Propagation and Folding

Constant propagation replaces symbolic variables with known constant values. If x = 5 precedes y = x + 3, the propagator rewrites to y = 8. Folding then evaluates 8 as a literal.

Sparse Conditional Constant (SCC) propagation extends this to conditionals. If a branch condition is constant, SCC eliminates the dead branch entirely. Wegman and Zadeck’s 1991 paper “Constant Propagation with Conditional Branches” describes the algorithm that is still used in production compilers.

Dead Code Elimination (DCE)

DCE removes instructions that do not affect the program’s observable behavior. This includes:

Unused variable definitions — x = 5 with no subsequent read of x
Dead basic blocks — code after an unconditional return
Unreachable functions — functions that are never called

Aggressive DCE works in tandem with other passes: inlining may make a function dead, then DCE removes it. DCE also cleans up after constant folding — if a branch becomes unconditional, the dead path is eliminated.

Interprocedural Optimization (IPO)

IPO extends optimization across function boundaries. GCC’s -fwhole-program and Link-Time Optimization (LTO) in both GCC and LLVM defer optimization until the entire program is visible. LTO enables:

Cross-module inlining — inlining functions defined in other translation units
Dead symbol elimination — removing unreachable global functions and variables
Constant propagation across calls — propagating constants through function arguments
Devirtualization — resolving virtual calls when the dynamic type is known

LLVM’s LTO is documented in the LLVM Language Reference Manual and is available through -flto on Clang. ThinLTO partitions the optimization to keep memory usage manageable while still providing most LTO benefits.

Profile-Guided Optimization (PGO)

PGO uses runtime profiling data to guide optimization decisions. The program is first compiled with instrumentation (-fprofile-generate), which inserts code to count basic block executions. The instrumented program runs on representative training data, producing profile files. A second compilation (-fprofile-use) reads the profiles and directs optimization effort to hot code paths.

PGO enables optimizations that static analysis cannot:

Function splitting — hot and cold parts of a function are placed in different sections, improving instruction cache locality
Switch optimization — the most frequent cases are placed early in the jump table
Inlining decisions — only functions that are actually called frequently are inlined
Block placement — basic blocks are ordered so that hot paths are sequential, minimizing taken branches

Clang reports 5-20% performance improvements with PGO on SPEC CPU benchmarks, depending on the benchmark and the quality of the training data.

Optimization for Code Size

Some use cases — embedded systems, mobile apps, cloud functions — prioritize small code size over speed. Compilers provide size optimization levels (-Os in GCC/Clang) that apply:

If-conversion — replacing branches with conditional move instructions
Loop rerolling — reversing unrolling when the code size increase outweighs speed benefit
Tail call optimization — converting recursive calls to jumps when the caller’s stack frame is no longer needed
Merge constants — combining identical constant strings and data

LLVM also supports -Oz (optimize for size more aggressively than -Os), which applies additional size-reducing transformations that may impact performance.

Alias Analysis and Optimization

Many optimizations depend on knowing whether two memory accesses can refer to the same location. Alias analysis (also called pointer analysis or disambiguation) determines whether two pointers can alias — point to the same memory.

The result of alias analysis is crucial for:

Load/store elimination — if a store and subsequent load cannot alias, the load can reuse the stored value without re-reading memory
LICM — a memory operation can be hoisted out of a loop only if the memory location is not modified by other operations in the loop
Auto-vectorization — memory operations can be vectorized only if the accesses do not overlap (or if overlapping is proven safe)

LLVM’s alias analysis infrastructure is a pass pipeline with multiple levels of precision: basicaa uses type-based rules (e.g., a float pointer cannot alias an int pointer in C), tbaa uses type-based alias analysis metadata, scev-aa uses scalar evolution to disambiguate array accesses, and globalsmodref-aa tracks which global variables functions access.

The cost is compile time — precise alias analysis can be O(N³) for programs with many pointers. Compilers therefore use a hierarchy: fast, cheap analysis for most queries, and more expensive analysis only when the cheap analysis returns “may alias.”

FAQ

What is the difference between constant folding and constant propagation? Folding evaluates constant expressions at compile time (2 + 3 → 5). Propagation replaces variables with their known constant values (x = 5; y = x + 3 → y = 8). Propagation creates more opportunities for folding.

Why does SSA form help optimization? SSA makes data-flow explicit. Each variable has exactly one definition, so the compiler can immediately find the defining instruction. This simplifies the implementation of constant propagation, GVN, dead code elimination, and many other passes.

What is the most impactful single optimization? Auto-vectorization often produces the largest single speedups on numerical code. Loop invariant code motion and inlining are also consistently high-impact.

Does optimization guarantee faster code? No. Aggressive optimization can increase code size, causing instruction cache pressure. Profile-guided optimization (PGO) helps direct optimization effort to the hottest code paths.