Live variable analysis

Live variable analysis is defined by a set of data-flow equations over a control-flow graph. For each basic block, the live-in set is the set of variables live at the entry, and the live-out set is the set live at the exit. The equations are: live-in(B) = use(B) ∪ (live-out(B) − def(B)) and live-out(B) = ∪_{S ∈ succ(B)} live-in(S), where use(B) are variables used before definition in B, and def(B) are variables defined in B. Because the equations are monotone and the lattice of subsets is finite, the iterative algorithm converges to the least fixed point, which is the greatest set of live variables (since it is a may-analysis).

The primary use of live variable analysis is dead code elimination: if a variable is not live at the end of a block, any assignment to it that is not used later can be removed. In register allocation, the live ranges of variables (the set of program points where they are live) determine which variables can share a register; variables with non-overlapping live ranges can be assigned to the same physical register. Additionally, the analysis helps in stack slot reuse, where local variables that are not simultaneously live can occupy the same memory location, reducing stack frame size.

Live variable analysis is closely related to the concept of reaching definitions; in fact, a variable is live at a point if there exists a path from that point to a use of the variable that is not killed by a definition. The analysis can be extended to handle pointers and aliasing, where the notion of a variable becomes more complex. In functional languages, a similar analysis is used for liveness of closures to enable garbage collection optimizations. Historically, the analysis was formalized in the 1970s by Frances E. Allen and John Cocke, who laid the groundwork for modern data-flow analysis frameworks.

In practice, live variable analysis is implemented using a worklist algorithm that iteratively updates live sets until a fixed point is reached. The order of processing basic blocks can affect the number of iterations; processing in reverse postorder (for backward analysis) often reduces iterations. For large programs, bit-vector representations of sets are used for efficiency, and the analysis can be made context-sensitive for interprocedural analysis. The analysis is also used in just-in-time compilers and in static analyzers for detecting uninitialized variables.

Data-flow analysis

A technique to gather information about the possible set of values computed at various points in a program.

Control-flow graph

A graph representation of all paths that might be traversed through a program during its execution.

Dead code elimination

An optimization that removes code which does not affect the program's results.

Register allocation

The process of assigning local variables and temporary values to a limited number of processor registers.

Reaching definitions

A data-flow analysis that determines which definitions may reach a given point in the code.