Code Optimization
Open in the Padhaiko app6.1 Loops in flow graphs, constant propagation, partial redundancy elimination
Most of a program's execution time is spent inside loops, making loop analysis and global scalar optimizations central to compiler performance.
6.1.1 Dominators and Natural Loops in Flow Graphs
Dominator and Immediate Dominator
In a control-flow graph with start node ENTRY (or ), node dominates node (written ) if every path from the entry node to must pass through . Every node dominates itself. The immediate dominator is the unique strict dominator of that is dominated by all other strict dominators of , forming a dominator tree.
Dominator sets satisfy the data-flow equation:
Back Edges and Natural Loops
- Back Edge: A directed edge in the flow graph whose head dominates its tail ().
- Natural Loop: Given a back edge , its natural loop consists of node (the loop header) together with all nodes that can reach without passing through .
- Pre-header: Before applying loop optimizations, compilers often insert a new empty basic block called a pre-header whose only successor is the loop header , giving a safe landing pad for hoisted loop-invariant instructions.
- Reducible Flow Graph: A CFG in which deleting all back edges leaves a directed acyclic graph (DAG) and every cycle has a single entry header. Structured control flow (
while,for,if-else) always produces reducible CFGs.
6.1.2 Constant Propagation
Constant propagation replaces uses of variables known to hold a constant value at a program point with that constant, often enabling constant folding (evaluating constant expressions at compile time) and branch elimination.
To track constants across merges (if-else and loops), compilers evaluate an abstract value from a 3-level constant-propagation lattice for each variable :
- (): Variable has not yet been initialized along any reached path.
- Constant : Variable definitely holds the specific constant .
- (, Not-A-Constant): Variable may hold non-constant or multiple distinct values along different paths.
At a control-flow join (meet ), if two incoming paths assign and :
- (same constant on both paths preserves ).
- when (different constants merge to non-constant).
- and .
6.1.3 Partial Redundancy Elimination (PRE)
An expression is fully redundant at point if it has already been computed along every path reaching without redefinition of or . It is partially redundant at if it has been computed along some, but not all, paths reaching (a common situation with loop-invariant expressions or if-else branches).
Partial Redundancy Elimination (PRE)
Partial Redundancy Elimination (PRE) transforms a flow graph by inserting evaluations of an expression along paths where it was not previously computed, converting partial redundancy into full redundancy so that the original duplicate computation can be replaced by a temporary variable.
Before PRE: After PRE (insert on missing path):
if (cond) if (cond) {
t = a + b; t = a + b;
else } else {
... (a + b not computed) t = a + b; // inserted
... }
z = a + b; // partially redundant z = t; // fully redundant!PRE (implemented in modern compilers via Lazy Code Motion) simultaneously achieves global common subexpression elimination and loop-invariant code motion without introducing unnecessary computations on paths that never use the expression.
6.2 Data-flow analysis and solving data-flow equations
Data-flow analysis collects static information about how values, definitions, and expressions propagate across basic blocks along all possible execution paths in a CFG.
6.2.1 General Data-Flow Schema
For each basic block , a data-flow analysis associates two sets (or lattice values):
- : Data-flow state immediately before the first statement of .
- : Data-flow state immediately after the last statement of .
The relationship between and is governed by:
- Transfer Function (): Models how statements inside generate new facts () and invalidate prior facts ().
- Meet Operator (): Combines information at control-flow merges—either Union () for may analyses (true along at least one path) or Intersection () for must analyses (true along all paths).
- Direction: Forward (computes from across predecessors) or Backward (computes from across successors).
6.2.2 Three Classical Data-Flow Analyses
| Analysis | Domain | Direction & Meet | Transfer Equation | Boundary & Initial State |
|---|---|---|---|---|
| Reaching Definitions | Set of definition IDs | Forward, May () | ; all | |
| Live Variables | Set of variables | Backward, May () | ; all | |
| Available Expressions | Set of expressions | Forward, Must () | ; interior (universal set) |
- Reaching Definitions: A definition reaches point if there is a path from to along which is not redefined. Used for constant propagation and loop-invariant code motion.
- Live Variables: Variable is live at point if its value at may be used before being redefined along some path from . Used for dead-code elimination and register interference graphs.
- Available Expressions: Expression is available at point if every path from
ENTRYto evaluates with no subsequent redefinition of or . Used for global common subexpression elimination.
6.2.3 Iterative Fixed-Point Algorithm
Because transfer functions on finite-height lattices are monotone, iterating over basic blocks until no or set changes is guaranteed to terminate at the unique least (or greatest) fixed point:
- Initialize boundary node (
ENTRYorEXIT) and interior blocks (\emptysetfor union/may, universal set for intersection/must). - Repeat until
changed == false:- For each block (in reverse postorder for forward problems, postorder for backward problems), update from predecessors (or from successors) using the meet operator, then apply to compute the new (or ).
- If the newly computed set differs from the old set, set
changed = true.
6.3 Storage organization and allocation strategies (Stack, heap)
Effective optimization depends heavily on how the compiler and runtime system organize activation records on the stack and dynamically allocated objects on the heap.
6.3.1 Stack Allocation Strategies and Optimizations
The control stack manages procedure activation records in strict LIFO order using a Stack Pointer (SP) and Frame Pointer (FP):
- Fixed-Size vs. Variable-Length Stack Data: Local variables of known compile-time size live at fixed offsets from
FP. Variable-length local arrays (VLAs) place a fixed-size pointer in the activation record while allocating the array body above the temporaries at the top of the frame. - Tail-Call Optimization (TCO): When a function's final action is returning the result of another call (
return f(x);), the compiler reuses the caller's existing stack frame instead of pushing a new one, converting tail recursion into an -space loop. - Frame Pointer Elimination: In leaf procedures or functions without variable-sized frames, variables are addressed directly relative to
SP, freeingFPas an extra general-purpose register. - Dangling Reference Hazard: Returning the address of a stack-allocated local variable creates a dangling pointer once the stack frame is popped; escape analysis detects variables that outlive their frame and promotes them to heap allocation.
6.3.2 Heap Organization and Allocation Strategies
The heap manages objects whose lifetimes are independent of procedure call nesting (malloc/free in C, new/Garbage Collection in Java/Python).
| Strategy | Allocation Rule | Advantages | Drawbacks |
|---|---|---|---|
| First Fit | Scan free list from start; allocate the first block | Fast allocation ( short scan); leaves large blocks intact near end | Accumulates tiny unusable fragments near the head of the free list |
| Best Fit | Scan entire free list; pick the smallest block | Minimizes wasted leftover space on each single allocation | Slow ( scan) and produces numerous tiny "splinter" fragments |
| Next Fit | Start scanning from the position of the previous allocation | Avoids clustering small fragments at the front of the list | Slightly worse locality; can break up large free blocks |
| Buddy System | Round size up to power of (); split larger blocks into twin buddies | Extremely fast coalescing via XOR address arithmetic | High internal fragmentation (up to nearly waste for sizes just above ) |
| Segregated Free Lists (Binning) | Maintain separate free lists for common size classes (e.g., bytes) | allocation/deallocation and high cache locality (used in jemalloc/ptmalloc) | Higher allocator metadata complexity |
Fragmentation and Garbage Collection
- Internal Fragmentation: Unused memory inside an allocated block (e.g., rounding a -byte request to a -byte buddy block wastes bytes).
- External Fragmentation: Total free heap memory exceeds a request, but no single contiguous free chunk is large enough. Coalescing adjacent freed chunks and compacting garbage collection mitigate external fragmentation.
- Automatic Heap Reclamation: Compilers targeting managed runtimes pair allocation with Reference Counting (immediate reclamation, fails on cycles unless aided) or Tracing Garbage Collectors (Mark-and-Sweep, Stop-and-Copy, and Generational GC exploiting the weak generational hypothesis that most objects die young).
6.4 Need and criteria of code optimization and basic optimization techniques
6.4.1 Need and Criteria for Code Optimization
High-level languages express algorithms clearly using abstractions (objects, multi-dimensional array indexing, helper functions, bounds checks) that introduce substantial redundant work if translated naively. Code optimization eliminates this abstraction penalty to reduce execution time, memory footprint, and energy consumption.
Every compiler optimization must satisfy three strict criteria:
- Correctness (Semantic Preservation): The transformed program must produce the exact same observable outputs and side effects as the unoptimized program for all valid inputs.
- Worthwhile Performance Gain: On typical workloads, the optimization must measurably improve runtime speed, code size, or power efficiency rather than degrading performance (e.g., excessive loop unrolling can overflow instruction caches).
- Reasonable Compilation Cost: Optimization passes must execute within practical compile-time and memory budgets (hence tiered optimization flags
-O0,-O1,-O2,-O3).
6.4.2 Basic Machine-Independent Optimization Techniques
| Technique | Description | Before After Example |
|---|---|---|
| Constant Folding | Evaluates constant expressions at compile time | x = 2 * 3 + 4; x = 10; |
| Constant Propagation | Substitutes known constant variables into subsequent uses | pi = 3.14; c = 2 * pi * r; c = 6.28 * r; |
| Copy Propagation | Replaces uses of x with y after x = y so x may become dead | x = y; z = x + 1; z = y + 1; |
| Common Subexpression Elimination (CSE) | Reuses an earlier computed value instead of recomputing it | a = x + y; b = x + y + 1; t = x + y; a = t; b = t + 1; |
| Dead-Code Elimination | Removes unreachable branches and assignments to unread variables | if (0) { foo(); } (deleted) |
| Code Motion (Loop Hoisting) | Moves loop-invariant computations out of a loop into its pre-header | Computing limit = n * 4 once before while instead of inside |
| Strength Reduction | Replaces expensive operations (*, /, ^) with cheaper ones (+, <<) | t = 4 * i in loop t = t + 4 per iteration |
| Induction-Variable Elimination | Replaces derived loop counters with a single primary counter | Removing i when t = 4 * i can directly drive the loop exit test |
Peephole Optimization
A peephole optimizer slides a small fixed-size window ("peephole") of – instructions across generated intermediate or target code and applies local pattern replacements:
- Redundant Load/Store Elimination: Removing
LD R0, aimmediately followingST a, R0in the same block. - Unreachable Code & Flow-of-Control Optimization: Eliminating dead code after unconditional
gotoand collapsing jump chains (goto L1whereL1: goto L2goto L2). - Algebraic Simplifications: Eliminating
x = x + 0,x = x * 1, and replacingx * 2with bit-shifts. - Machine Idioms: Replacing
ADD R0, #1withINC R0or auto-increment addressing modes.
6.5 Basic block optimization
Whereas global optimization analyzes paths across the entire CFG, basic block (local) optimization operates strictly inside a single straight-line basic block where control enters only at the top and exits only at the bottom.
| Aspect | Local (Basic-Block) Optimization | Global (Intra-Procedural) Optimization |
|---|---|---|
| Scope | Single basic block (no branches inside) | Entire function / procedure CFG across loops and joins |
| Primary Tool | Basic-block DAG and backward liveness scan | Data-flow analysis (IN/OUT equations), SSA form, dominator trees |
| Complexity | Very fast ( in block size); always enabled even at -O1 | Higher compile-time cost (fixed-point iteration); enabled at -O2/-O3 |
| Capabilities | Local CSE, constant folding, algebraic identities, dead temporaries, local instruction scheduling | Loop-invariant code motion, PRE, global CSE, dead-store elimination across branches |
Inside each basic block, compilers construct a value-numbered DAG (as detailed in Chapter 5) and apply:
- Local Value Numbering (LVN): Assigns unique integer value numbers to expressions so identical computations map to the same value number, eliminating redundant operations and propagating copies in one linear pass.
- Local Algebraic & Constant Simplification: Folds constants and reduces identities (, ) before emitting nodes.
- Local Dead-Store & Dead-Temporary Pruning: Discards assignments overwritten later in the same block before being read, and drops temporaries that are dead on block exit.
6.6 Case studies of some compilers, like the c compiler, the C++ compiler
Modern production compilers—most notably GCC (GNU Compiler Collection) and Clang/LLVM—demonstrate how the theoretical phases and optimizations above work together in practice.
6.6.1 Case Study: The C Compiler (gcc / clang)
A modern C compiler processes a .c translation unit through a multi-tier pipeline:
- Preprocessing (
cpp): Expands#definemacros, resolves#includeheaders, strips comments, and processes#ifdefconditional compilation. - Front-End Parsing & Semantic Checks: Produces an AST, enforces C's static type rules, and lowers ASTs into GIMPLE (in GCC, a three-address-like IR) or LLVM IR (in Clang, a strongly typed Static Single Assignment (SSA) IR where every virtual register is assigned exactly once).
- Target-Independent Optimization (
-O1to-O3): Runs dozens of passes—SSA construction (mem2reg), constant propagation (SCCP), global value numbering (GVN), partial redundancy elimination, dead-code elimination, loop-invariant code motion, function inlining, and SIMD auto-vectorization. - Back-End Code Generation: Lowers IR to target-specific machine representation (GCC RTL or LLVM SelectionDAG / MIR), performs instruction selection, graph-coloring or linear-scan register allocation, instruction scheduling, and peephole optimization, emitting
.sassembly for the assembler (as) and linker (ld).
C-Specific Optimization Challenges
- Pointer Aliasing: Because C allows arbitrary pointers (
*p = 10;), the optimizer must prove*pcannot alias local variablexbefore keepingxin a register across the store. Compilers rely on type-based alias analysis (TBAA / strict aliasing) and therestrictkeyword to unlock aggressive vectorization and load hoisting.
6.6.2 Case Study: The C++ Compiler (g++ / clang++)
C++ shares the middle-end and back-end optimizer of gcc/clang, but its front-end must resolve dramatically richer language semantics before optimization:
| Aspect | C Compiler (gcc / clang) | C++ Compiler (g++ / clang++) |
|---|---|---|
| Symbol Naming | Simple external linkage names (e.g., foo) | Name Mangling encodes namespaces, class names, parameter types, and const qualifiers so overloaded functions have unique linker symbols (e.g., _Z3fooi) |
| Genericity | Preprocessor macros or void* | Template Instantiation (Monomorphization) generates specialized type-checked code per template argument combination |
| Dispatch Mechanism | Direct calls or explicit function pointers | Virtual Method Tables (vtable / vptr) for polymorphic calls; optimizer attempts devirtualization to turn indirect calls into direct inlinable calls |
| Resource & Error Control | Manual cleanup and return-code checks | RAII inserts deterministic destructor calls on every scope exit (including exceptions); zero-cost DWARF exception tables avoid runtime overhead on normal paths |
| Object Copy Optimization | Struct bitwise copies | Copy Elision / RVO / NRVO constructs returned objects directly in the caller's target memory, eliminating redundant copy/move constructors |
Worked Examples
1
Consider a control-flow graph with basic blocks through (where is the entry block) and directed edges:
- Compute the dominator set for every block.
- Identify any back edge and determine the natural loop it defines.
- If the loop executes iterations and contains loop-invariant TAC instructions (
t1 = x + 4andt2 = y * 8), how many dynamic instruction executions are saved by code motion into a pre-header?
Computing Dominator Sets: Initialize and for , then apply :
(Re-checking : , so fixed point reached.)
Identifying Back Edges and Natural Loop: Check every edge to see if :
- Only satisfies . Thus is the unique back edge.
- Natural Loop of : Start with and walk backward from without crossing : predecessors of are and ; predecessor of is ; predecessor of is (stop).
- Natural loop .
Dynamic Instruction Savings from Code Motion: Without code motion, the loop-invariant instructions execute times. Hoisting them to a pre-header executes them times before the loop begins:
- Dominators: , , , , , .
- Back edge: , defining natural loop .
- Code motion saves dynamic instruction executions.
2
Perform iterative Reaching Definitions analysis on the following 3-block flow graph with edges , (loop), and :
- : ,
- : ,
- :
Compute , , and iterate the Reaching Definitions data-flow equations until and converge.
Computing gen and kill Sets: Total definitions: , , .
- : Defines () and ().
- , .
- : Defines () and ().
- , .
- : Defines ().
- , .
Iterative Fixed-Point Solution: Using and , initialized with all :
| Pass | Block | ||
|---|---|---|---|
| Init | All | ||
| Pass 1 | |||
| Pass 1 | |||
| Pass 1 | |||
| Pass 2 | (unchanged) | ||
| Pass 2 | (unchanged!) | ||
| Pass 2 | (unchanged!) |
At convergence:
- ,
- ,
- ,
3
Optimize the following straight-line basic block (assuming only out is live on exit) by sequentially applying constant folding, constant propagation, copy propagation, algebraic identities / strength reduction, and dead-code elimination:
c = 2 + 2
y = x * 1
z = c * y
w = z + 0
p = w * 2
out = w + pVerify the simplified expression numerically when x = 5.
Applying Constant Folding, Algebraic Identity, and Constant/Copy Propagation:
- Constant Folding:
c = 2 + 2folds toc = 4. - Algebraic Identity:
y = x * 1simplifies to copyy = x;w = z + 0simplifies to copyw = z. - Constant & Copy Propagation:
- Replace
cwith4andywithxinz = c * yz = 4 * x. - Replace
wwithzinp = w * 2andout = w + pp = z * 2,out = z + p.
- Replace
Applying Strength Reduction, Dead-Code Elimination, and Final Verification:
- Since
c,y, andware no longer read anywhere and onlyoutis live on exit, eliminatec = 4,y = x, andw = z. - Furthermore,
z = 4 * xandp = z * 2giveout = 4*x + 8*x = 12*x(or using bit-shifts/additions in TAC:t1 = x << 2,p = t1 << 1,out = t1 + p, orout = 12 * x). - Numerical Check at
x = 5:- Original code:
c = 4,y = 5,z = 20,w = 20,p = 40,out = 20 + 40 = 60. - Optimized code:
out = 12 * 5 = 60(exact match).
- Original code:
The -statement block reduces to z = 4 * x; p = z * 2; out = z + p (or simply out = 12 * x), preserving the exact output at x = 5.
Exercises
Practice Exercises — Code Optimization
For a 5-block CFG with entry and edges , , , , , and :
- Compute for all blocks.
- Identify the back edge and list the blocks belonging to its natural loop.
Computing Dominators:
Back Edge and Natural Loop: Checking edge : since , is a back edge. Walking backward from without passing through visits and , giving natural loop .
Dominator sets are , , , , and . The back edge is and its natural loop is .
Perform backward Live-Variable analysis on a 3-block CFG (, , ) with:
- :
a = 1; b = 2 - :
c = a + b; a = a + 1 - :
return c
Compute , , , and for all three blocks until convergence.
Computing use and def Sets: Remember: if is read in before any redefinition in ; if is assigned in before any read in (or simply defined in when using ):
- : , .
- :
aandbare read inc = a + bbeforeais written;cis written before any read. Thus , (noteais inuse[B2], and even ifais also listed indef[B2],use[B2]re-addsaon every iteration). - : , .
Backward Fixed-Point Iteration: Initialize all , :
- Pass 1 (reverse order ):
- : .
- : .
- : .
- Pass 2:
- : (unchanged).
- : (unchanged!).
- : , (unchanged!).
At convergence:
- ,
- ,
- ,
- Trace constant propagation on the lattice for variable
xafter the merge below, and evaluatey = x + 3:
if (flag)
x = 10
else
x = 5 + 5
y = x + 3- How does Partial Redundancy Elimination (PRE) differ from standard global Common Subexpression Elimination (CSE)?
Constant Propagation Lattice Trace:
- On the
thenbranch:xreceives lattice value10. - On the
elsebranch:5 + 5folds to10, soxalso receives lattice value10. - At the join point before
y = x + 3, the meet operator evaluates (identical constants agree!). - Therefore,
xremains constant10, andy = x + 3folds toy = 13. (Had theelsebranch assigned12, would prevent folding.)
PRE vs. Global CSE: Standard global CSE only removes an expression at point if is available along every path reaching . PRE handles expressions computed along some (not all) incoming paths by inserting on the missing paths first, transforming partial redundancy into full redundancy and subsuming loop-invariant code motion.
At the merge point , so y = x + 3 simplifies to y = 13. Unlike standard CSE (which requires full availability on all paths), PRE inserts computations on missing paths to eliminate partial redundancies across branches and loops.
- A contiguous heap initially allocates four adjacent blocks in order:
B1(),B2(),B3(), andB4(), leaving free at the end. BlocksB1andB3are then freed (without compaction).- Compute the total free memory remaining.
- Can a new allocation request of succeed under First Fit or Best Fit? Explain what type of fragmentation this illustrates.
- In a Buddy System allocator with minimum block size and power-of-2 block sizes, how many bytes of internal fragmentation occur for a request?
Heap Fragmentation Analysis:
- Occupied blocks remaining:
B2() andB4(). - Free holes (non-adjacent):
H1(whereB1was),H2(whereB3was), andH3(tail). - Total free memory .
- Because
B2separatesH1fromH2andB4separatesH2fromH3, none of the holes coalesce. The largest contiguous hole is , so the request fails under both First Fit and Best Fit! This is external fragmentation.
Buddy System Internal Fragmentation: The smallest power of that fits is .
Total free memory is , yet the request fails under both First Fit and Best Fit due to external fragmentation (largest contiguous hole is ). In the Buddy System, a request allocates a block, wasting to internal fragmentation.
Compare how a C compiler (gcc/clang) and a C++ compiler (g++/clang++) compile and optimize programs with respect to:
- Symbol naming and linking (name mangling)
- Polymorphic function dispatch (vtables and devirtualization)
- Aliasing and memory optimization (pointer aliasing vs. RAII/copy elision)
1. Symbol Naming (Name Mangling): C does not allow function overloading, so symbol names map nearly 1-to-1 to linker identifiers. C++ supports function overloading, namespaces, and class member functions, requiring name mangling (encoding function name, scope, and parameter types into unique linker symbols like _Z3fooi) to preserve type safety across translation units.
2. Virtual Dispatch and Devirtualization: C uses direct function calls or explicit function pointers. C++ classes with virtual methods store a hidden vptr pointing to a vtable, turning calls into indirect memory loads + jumps that block inlining. Modern C++ optimizers run devirtualization (when the dynamic concrete type is statically provable, or via speculative profile-guided checks) to convert virtual calls into direct inlinable calls.
3. Aliasing, RAII, and Copy Elision: Both compilers use Type-Based Alias Analysis (TBAA) and SSA form to prove pointers do not alias so variables stay in registers. Additionally, C++ compilers emit deterministic RAII destructor calls along normal and exception-unwinding paths (via zero-cost unwind tables) and apply Copy Elision / RVO to construct returned objects directly in the caller's stack frame.
C++ compilers extend the shared C optimizer pipeline with name mangling for overloading, vtable dispatch and devirtualization for polymorphism, RAII destructor insertion with exception unwind tables, and copy elision (RVO/NRVO) alongside standard SSA and alias optimizations.