PadhaikoAll subjects

Code Optimization

Compiler Design (ENCT 326)

Open in the Padhaiko app

6.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

Definition

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

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 :

At a control-flow join (meet ), if two incoming paths assign 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).

Definition

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.

PRE Example: Hoisting Partial Redundancy Out of a BranchText
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):

The relationship between and is governed by:

  1. Transfer Function (): Models how statements inside generate new facts () and invalidate prior facts ().
  2. 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).
  3. Direction: Forward (computes from across predecessors) or Backward (computes from across successors).

6.2.2 Three Classical Data-Flow Analyses

Classic Intra-Procedural Data-Flow Frameworks
AnalysisDomainDirection & MeetTransfer EquationBoundary & Initial State
Reaching DefinitionsSet of definition IDs Forward, May (); all
Live VariablesSet of variables Backward, May (); all
Available ExpressionsSet of expressions Forward, Must (); interior (universal set)

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:

  1. Initialize boundary node (ENTRY or EXIT) and interior blocks (\emptyset for union/may, universal set for intersection/must).
  2. 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):

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).

Dynamic Heap Allocation Strategies
StrategyAllocation RuleAdvantagesDrawbacks
First FitScan free list from start; allocate the first block Fast allocation ( short scan); leaves large blocks intact near endAccumulates tiny unusable fragments near the head of the free list
Best FitScan entire free list; pick the smallest block Minimizes wasted leftover space on each single allocationSlow ( scan) and produces numerous tiny "splinter" fragments
Next FitStart scanning from the position of the previous allocationAvoids clustering small fragments at the front of the listSlightly worse locality; can break up large free blocks
Buddy SystemRound size up to power of (); split larger blocks into twin buddiesExtremely fast coalescing via XOR address arithmeticHigh 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


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:

  1. Correctness (Semantic Preservation): The transformed program must produce the exact same observable outputs and side effects as the unoptimized program for all valid inputs.
  2. 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).
  3. 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

Fundamental Compiler Optimization Techniques
TechniqueDescriptionBefore After Example
Constant FoldingEvaluates constant expressions at compile timex = 2 * 3 + 4; x = 10;
Constant PropagationSubstitutes known constant variables into subsequent usespi = 3.14; c = 2 * pi * r; c = 6.28 * r;
Copy PropagationReplaces uses of x with y after x = y so x may become deadx = y; z = x + 1; z = y + 1;
Common Subexpression Elimination (CSE)Reuses an earlier computed value instead of recomputing ita = x + y; b = x + y + 1; t = x + y; a = t; b = t + 1;
Dead-Code EliminationRemoves unreachable branches and assignments to unread variablesif (0) { foo(); } (deleted)
Code Motion (Loop Hoisting)Moves loop-invariant computations out of a loop into its pre-headerComputing limit = n * 4 once before while instead of inside
Strength ReductionReplaces expensive operations (*, /, ^) with cheaper ones (+, <<)t = 4 * i in loop t = t + 4 per iteration
Induction-Variable EliminationReplaces derived loop counters with a single primary counterRemoving 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:


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.

AspectLocal (Basic-Block) OptimizationGlobal (Intra-Procedural) Optimization
ScopeSingle basic block (no branches inside)Entire function / procedure CFG across loops and joins
Primary ToolBasic-block DAG and backward liveness scanData-flow analysis (IN/OUT equations), SSA form, dominator trees
ComplexityVery fast ( in block size); always enabled even at -O1Higher compile-time cost (fixed-point iteration); enabled at -O2/-O3
CapabilitiesLocal CSE, constant folding, algebraic identities, dead temporaries, local instruction schedulingLoop-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:

  1. 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.
  2. Local Algebraic & Constant Simplification: Folds constants and reduces identities (, ) before emitting nodes.
  3. 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:

  1. Preprocessing (cpp): Expands #define macros, resolves #include headers, strips comments, and processes #ifdef conditional compilation.
  2. 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).
  3. Target-Independent Optimization (-O1 to -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.
  4. 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 .s assembly for the assembler (as) and linker (ld).

C-Specific Optimization Challenges

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:

AspectC Compiler (gcc / clang)C++ Compiler (g++ / clang++)
Symbol NamingSimple 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)
GenericityPreprocessor macros or void*Template Instantiation (Monomorphization) generates specialized type-checked code per template argument combination
Dispatch MechanismDirect calls or explicit function pointersVirtual Method Tables (vtable / vptr) for polymorphic calls; optimizer attempts devirtualization to turn indirect calls into direct inlinable calls
Resource & Error ControlManual cleanup and return-code checksRAII inserts deterministic destructor calls on every scope exit (including exceptions); zero-cost DWARF exception tables avoid runtime overhead on normal paths
Object Copy OptimizationStruct bitwise copiesCopy Elision / RVO / NRVO constructs returned objects directly in the caller's target memory, eliminating redundant copy/move constructors

Worked Examples

Example 1

1

Consider a control-flow graph with basic blocks through (where is the entry block) and directed edges:

  1. Compute the dominator set for every block.
  2. Identify any back edge and determine the natural loop it defines.
  3. If the loop executes iterations and contains loop-invariant TAC instructions (t1 = x + 4 and t2 = 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:

Answer:
  • Dominators: , , , , , .
  • Back edge: , defining natural loop .
  • Code motion saves dynamic instruction executions.
Example 2

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 :

Reaching Definitions Convergence Trace
PassBlock
InitAll
Pass 1
Pass 1
Pass 1
Pass 2 (unchanged)
Pass 2 (unchanged!)
Pass 2 (unchanged!)
Answer:

At convergence:

  • ,
  • ,
  • ,
Example 3

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:

Unoptimized Basic BlockText
c   = 2 + 2
y   = x * 1
z   = c * y
w   = z + 0
p   = w * 2
out = w + p

Verify the simplified expression numerically when x = 5.

Applying Constant Folding, Algebraic Identity, and Constant/Copy Propagation:

  1. Constant Folding: c = 2 + 2 folds to c = 4.
  2. Algebraic Identity: y = x * 1 simplifies to copy y = x; w = z + 0 simplifies to copy w = z.
  3. Constant & Copy Propagation:
    • Replace c with 4 and y with x in z = c * y z = 4 * x.
    • Replace w with z in p = w * 2 and out = w + p p = z * 2, out = z + p.

Applying Strength Reduction, Dead-Code Elimination, and Final Verification:

  • Since c, y, and w are no longer read anywhere and only out is live on exit, eliminate c = 4, y = x, and w = z.
  • Furthermore, z = 4 * x and p = z * 2 give out = 4*x + 8*x = 12*x (or using bit-shifts/additions in TAC: t1 = x << 2, p = t1 << 1, out = t1 + p, or out = 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).
Answer:

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

Question 1

For a 5-block CFG with entry and edges , , , , , and :

  1. Compute for all blocks.
  2. 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 .

Answer:

Dominator sets are , , , , and . The back edge is and its natural loop is .

Question 2

Perform backward Live-Variable analysis on a 3-block CFG (, , ) with:

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 ):

  • : , .
  • : a and b are read in c = a + b before a is written; c is written before any read. Thus , (note a is in use[B2], and even if a is also listed in def[B2], use[B2] re-adds a on every iteration).
  • : , .

Backward Fixed-Point Iteration: Initialize all , :

  • Pass 1 (reverse order ):
    • : .
    • : .
    • : .
  • Pass 2:
    • : (unchanged).
    • : (unchanged!).
    • : , (unchanged!).
Answer:

At convergence:

  • ,
  • ,
  • ,
Question 3
  1. Trace constant propagation on the lattice for variable x after the merge below, and evaluate y = x + 3:
Constant Propagation SnippetText
if (flag)
    x = 10
else
    x = 5 + 5
y = x + 3
  1. How does Partial Redundancy Elimination (PRE) differ from standard global Common Subexpression Elimination (CSE)?

Constant Propagation Lattice Trace:

  • On the then branch: x receives lattice value 10.
  • On the else branch: 5 + 5 folds to 10, so x also receives lattice value 10.
  • At the join point before y = x + 3, the meet operator evaluates (identical constants agree!).
  • Therefore, x remains constant 10, and y = x + 3 folds to y = 13. (Had the else branch assigned 12, 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.

Answer:

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.

Question 4
  1. A contiguous heap initially allocates four adjacent blocks in order: B1 (), B2 (), B3 (), and B4 (), leaving free at the end. Blocks B1 and B3 are 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.
  2. 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 () and B4 ().
  • Free holes (non-adjacent): H1 (where B1 was), H2 (where B3 was), and H3 (tail).
  • Total free memory .
  • Because B2 separates H1 from H2 and B4 separates H2 from H3, 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 .

Answer:

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.

Question 5

Compare how a C compiler (gcc/clang) and a C++ compiler (g++/clang++) compile and optimize programs with respect to:

  1. Symbol naming and linking (name mangling)
  2. Polymorphic function dispatch (vtables and devirtualization)
  3. 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.

Answer:

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.

← Code Generation