12.5 Liveness Analysis and Loop Optimizations

A value is live at a program point if some future execution may read its current value before that value is overwritten. Liveness is a backward may-analysis: the future determines whether a value matters now, and a value is live if any successor path may use it.

For each block:

OUT[B] = union of IN[S] for every successor S
IN[B]  = USE[B] ∪ (OUT[B] − DEF[B])

USE[B] contains values read before being defined in the block. DEF[B] contains values defined by the block. A definition kills the incoming version, while a use makes the value live.

From block facts to instruction intervals

After solving block-level liveness, scan instructions backward. Start with the block's OUT set. For instruction d = op(a, b), remove d from the live set, then add a and b. The set before the instruction is its live-in set.

1: a = load input
2: b = add a, 1
3: c = mul b, 2
4: print a
5: return c

Because a is used again at line 4, its live range overlaps b and c. If the final print a is removed, a dies after line 2 and register pressure falls. Two values whose live ranges overlap interfere: they cannot occupy the same register at that point.

Liveness supports dead-store elimination, register allocation, stack-map construction, and precise garbage collection. Calls complicate the picture because calling conventions clobber some physical registers; values live across a call may need callee-saved registers or spills.

Why loops deserve special treatment

A loop repeats work, so saving one instruction in its body may save millions dynamically. Natural-loop detection and dominance from Chapter 10 identify a header, back edge, body, preheader, and exits. Those structural facts enable several transformations.

Loop-invariant code motion

Loop-invariant code motion (LICM) moves a computation to the preheader when:

• its operands are constant or defined outside the loop, or by other invariants;

• the operation is safe to execute whenever the loop is entered;

• moving it does not change memory behavior, exceptions, or ordering;

• its definition dominates all loop uses that rely on it.

A load from limit_ptr is not invariant merely because its address is invariant. A store in the loop or an unknown call may modify the pointed-to value. Alias and effect analysis must prove the load stable.

Induction variables and strength reduction

In addr = base + i * 8, where i increases by one, the multiplication can become a loop-carried address updated by addr_next = addr + 8. This strength reduction replaces repeated multiplication with addition. The compiler must preserve overflow and pointer semantics and update the value on every back edge.

Unrolling

Unrolling duplicates the body to process several iterations per branch. It reduces loop-control overhead and may expose vectorization, but increases code size and needs a remainder path when the trip count is not divisible by the unroll factor.

Transformations interact with pressure

Loop optimization is not a collection of independent switches. LICM may extend a value's live range across the entire loop. Unrolling creates more simultaneously live temporaries. Vectorization uses wider registers and may require alignment checks. A transformation that removes dynamic instructions can still slow the program through spills or instruction-cache growth.

Therefore a loop optimizer first proves legality, then estimates profitability using trip counts, target costs, profile data, and register pressure. Tests must compare zero, one, small, and large trip counts; exercise every exit and continue; and include aliasing, trapping operations, overflow boundaries, and non-divisible remainders.