8.1 Data Flow Analysis and Optimization Legality: When Can Code Be Removed?

After lexical, syntactic, and semantic analysis, the compiler front end emits TAC- or SSA-form IR. The IR may be semantically correct yet contain temporary values, unused assignments, and repeated computations. The back end must prove each transformation legal before generating machine code; “looks redundant” is not a proof.

The goal of optimization is not to make the IR shorter, but to generate equivalent programs with lower costs within the observable behavior allowed by the source language.

This lesson's objectives

• Use CFG data flow equations to understand cross-block facts;
• Distinguish constant folding, constant propagation, CSE, DCE, and LICM;
• Establish validity conditions for overflow, floating-point, memory, and exceptions;
• Maintain pass preconditions, analysis caches, and verifiers.

1. A basic block doesn't mean proof is unnecessary

t0 = add a, b
t1 = mul t0, c
t2 = add a, b
t3 = mul t2, d

If a and b remain unchanged between the two add operations, and add has the same type, overflow, and exception semantics, then t2 can reuse t0. In SSA, operand identity is already fixed, but memory reads, calls, and floating-point environment may still prevent merging.

Common local transformations:

• constant folding: evaluate constant expressions at compile time;
• algebraic simplification: such as under legal conditions x+0 → x;
• common subexpression elimination: reuse previously computed expressions;
• copy propagation: replace copies with their sources;
• dead code elimination: remove definitions that are unused and have no side effects.

Each transformation must list its preconditions. Wrapping, trapping, and undefined integer overflow affect reassociation and strength reduction. Ordinary integer x+0 cannot itself overflow, whereas floating-point x+0 may change signed zero. Preconditions must address the actual transformation; a generic overflow warning is not enough.

2. Data flow analysis is a fixed point on a graph

For reaching definitions, the entry facts of block $B$ come from the merging of all predecessor exits:

$$IN[B]=\bigcup _{P\in pred(B)}OUT[P],$$$$OUT[B]=GEN[B]\cup (IN[B]-KILL[B]).$$

Start from the initial values and repeatedly update until all sets stabilize. The loop allows information to propagate along back edges multiple times, so you can't just sweep through once in source order.

Different analysis directions and merge operations:

• reaching definitions: forward, union;
• available expressions: forward, intersection;
• liveness: backward, union;
• definite assignment: typically forward, intersection.

Initialization depends on whether an analysis tracks may or must facts. Reaching definitions is a may analysis: the example grows from empty sets, with parameters or external initial definitions supplied at the entry boundary. Must analyses typically need different initialization. A finite lattice and monotone transfer functions ensure termination here; other abstract domains may need widening. Wrong boundary conditions can omit real paths even when the equations are correct.

This complete example has edges entry → header → body → header and header → exit. Both d0 and d1 define the same variable x; the sets contain definition identities, not variable names. There are no external entry definitions:

pred = {
    "entry": [], "header": ["entry", "body"],
    "body": ["header"], "exit": ["header"],
}
gen = {"entry": {"d0"}, "header": set(), "body": {"d1"}, "exit": set()}
kill = {"entry": {"d1"}, "header": set(), "body": {"d0"}, "exit": set()}
inside = {block: set() for block in pred}
outside = {block: set() for block in pred}
changed = True
while changed:
    changed = False
    for block, parents in pred.items():
        incoming = set().union(*(outside[parent] for parent in parents))
        outgoing = gen[block] | (incoming - kill[block])
        changed |= incoming != inside[block] or outgoing != outside[block]
        inside[block], outside[block] = incoming, outgoing
print(sorted(inside["header"]))  # ['d0', 'd1']
print(sorted(outside["body"]))   # ['d1']

3. Constant Propagation and Branch Reachability

A regular constant propagation record indicates whether a value is constant, non-constant, or unknown. Sparse Conditional Constant Propagation (SCCP) simultaneously tracks SSA values and executable CFG edges:

cond = const false
br cond, then, else

If the then edge is not executable, φ inputs arriving through that dead path can be ignored at a join, and computations in the dead branch may be removed. "Unreachable" is proven by the current IR semantics, not guessed from runtime sampling.

Fold operations must use target semantics rather than the default behavior of the compiler host language. For example, integer widths, floating-point formats, and rounding rules may differ when cross-compiling.

4. DCE Must Check Results and Effects

t = pure_add a, b       // t is unused and can be removed
u = load volatile p     // u is unused, but cannot be deleted arbitrarily
v = call write_log()    // return value is unused, call has side effects
w = div x, y            // If a trap is possible, removing this changes behavior

The IR or its instruction descriptions must answer:

• Read/write memory?
• Is it possible to throw an exception or trigger a trap?
• Whether volatile/atomic;
• Does it interact with external state;
• Guaranteed to terminate;
• Whether it affects floating-point state or synchronization order.

“Nobody used the results” only proves the data is dead, not that the operation itself can't be observed.

5. CSE, GVN, and Memory Aliasing

For pure SSA operations, value-numbering keys include opcode, type, operands, and semantic flags, including floating-point and overflow flags. Reusing an equivalent value also requires its definition to be available at the replacement use, such as dominating an ordinary SSA use. Equal numbers alone do not establish that control-flow condition.

Memory reads are harder:

x = load p
store q, 1
y = load p

For these ordinary, non-atomic, non-volatile accesses, replacing y with x requires proving that the accessed byte ranges do not overlap, or that the store cannot change the load, along with the other memory-model conditions. Merely knowing p != q need not prove that multi-byte ranges are disjoint. Alias analysis typically conservatively answers "may-alias"; when uncertain, it gives up optimization to ensure correctness.

Calls may also read or write unknown memory. The effect summary, readonly/pure attributes, combined with inter-procedural analysis, can expand the optimization scope, but incorrect attributes can directly result in erroneous code.

6. Loop Invariant Code Motion

To move the loop expression to the preheader, we must at least prove:

• The operand remains unchanged throughout the loop;
• Executing at the new location won't introduce exceptions that wouldn't have occurred otherwise;
• Memory reads are not modified by possible alias writes in the loop;
• Movement does not violate atomicity, volatility, or synchronization ordering;
• If the loop might execute zero times, early execution at the new location is still observationally equivalent.

for (...) {
    t = a * b
    use(t)
}

Hoisting is straightforward when a*b has no observable effects and is safe to speculate. Merely not writing memory does not rule out traps, exceptions, or nontermination. A division that might cause a divide-by-zero error moved before the loop can generate an exception in zero iterations.

7. Strength Reduction Needs Valid Examples

Suppose i starts at zero and increases by one each iteration. The original loop computes a byte address:

address = base + i * 8

Induction variables can be introduced:

address = base
If another iteration remains, increment address by 8

This turns each multiplication into an addition, but we still need to prove that the iteration count, overflow, pointer bounds, and exit path semantics remain consistent. On modern hardware, multiplication isn't necessarily expensive, so the value of this transformation must be evaluated within the target cost model.

“Change i=i*2 to i=i+1” alters the sequence, not strength reduction.

8. Floating-point Optimization Is Semantically Constrained

Floating-point addition does not guarantee associativity. There are inputs satisfying the following inequality; it does not hold for every triple:

$$(a+b)+c\ne a+(b+c).$$

On a Python implementation using IEEE 754 binary64:

a, b, c = 1e16, -1e16, 1.0
print((a + b) + c)  # 1.0
print(a + (b + c))  # 0.0

NaN, infinity, signed zero, rounding modes, and exception flags also affect conversions. The compiler can only perform transformations like reassociation or replacing division with multiplication by the reciprocal if language rules, explicit fast-math flags, or proven conditions allow it.

This is not the same issue as commutativity. For ordinary finite values, a+b and b+a are typically equal; what is truly universally constrained are regrouping and special state semantics.

9. Pass Pipelines Must Keep Analyses Valid

After a pass modifies the CFG, dominance trees, loop information, liveness, and other cached data may become invalid. Each transformation should declare:

• What analyses are needed;
• Which analyses it preserves;
• Modified the CFG, instructions, or types;
• Which verifiers must be called after execution.

Optimization passes can inspire each other: constant propagation exposes dead branches, DCE removes remnants, simplifying the CFG creates opportunities for the next φ simplification. Convergence conditions and iteration budgets should be set to prevent back-and-forth rewriting between the transformations.

Common Misconceptions

• Mathematical equivalence is enough to justify optimization: Overflow, exceptions, and floating-point semantics in the source language can differ.
• Instructions with unused results are dead code: The operation might still have observable effects.
• Guessing at aliasing when alias analysis is uncertain: The optimizer should conservatively give up unless the language contract guarantees otherwise.
• Optimization passes can ignore one another: CFG rewriting will invalidate results from other analyses.

Practice

1. Write reaching-definitions equations for a branch-containing IR and iterate until stable.
2. Determine whether load, volatile loads, pure function calls, and division that might trap can be eliminated when their results are not used.
3. Construct a counterexample for LICM where "zero loop iterations cause premature exception".
4. List the analysis caches that must be invalidated for a CFG simplification pass.

Summary

Optimization is not a collection of pattern replacements, but rather program transformations with a proof obligation. Data flow analysis provides facts across paths, and IR effect models and language semantics determine which transformations are valid, while the pass pipeline ensures these facts remain valid.

The next lesson is to hand the optimized virtual operations over to the target machine: select valid instructions, follow the ABI, and map virtual registers into the finite physical register set.