Liveness Analysis

Every program you write is full of variables that stop mattering before the function ends. You compute a temporary sum, use it once, and move on. A smart compiler spots that moment — the instant the value is no longer live — and immediately reuses that register for something else.

Liveness analysis is the algorithm that finds those moments. It answers a precise question for every point in the program: which variables hold a value that might be read in the future? A variable is live at a point if there is some execution path from that point to a use of the variable, without any intervening redefinition.

The key insight is that liveness is a backward property. You can't know whether a variable will be read by looking forward — you have to look back from every use and ask: "what was live just before this instruction?"

This single backward sweep is the foundation of register allocation, dead-code elimination, and a dozen other compiler passes that make your programs run fast.

Below is a small three-variable program. Each line is an instruction that either defines (writes) or uses (reads) a variable. The analysis runs backward from the bottom up, computing the set of live variables just before each instruction.

<!-- {{c_html_intro}} -->
<div class="panel">
  <div class="prog-header">
    <span class="label">{{label_program}}</span>
    <span class="label live-legend"><span class="dot live"></span>{{label_live}}</span>
    <span class="label dead-legend"><span class="dot dead"></span>{{label_dead}}</span>
  </div>
  <table id="prog" class="prog"></table>
</div>
<div class="panel info-panel">
  <p class="hint">{{hint_para}}</p>
  <div class="status" id="status">{{status_idle}}</div>
</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.panel { background: #f5f7fa; border: 1px solid #dde2e8; border-radius: 10px; padding: .7rem 1rem; margin-bottom: .6rem; }
.prog-header { display: flex; gap: 1rem; align-items: center; margin-bottom: .4rem; flex-wrap: wrap; }
.label { font-size: .8rem; color: #555; font-weight: 600; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; margin-right: 3px; vertical-align: middle; }
.dot.live { background: #2a9d4e; }
.dot.dead { background: #adb1b8; }
.live-legend, .dead-legend { display: flex; align-items: center; gap: 2px; }
.prog { border-collapse: collapse; width: 100%; font-family: ui-monospace, monospace; font-size: .88rem; }
.prog tr { border-bottom: 1px solid #e4e8ed; }
.prog tr.current { background: #e8f0fe; }
.prog td { padding: .28rem .4rem; vertical-align: middle; }
.prog td.lineno { color: #999; width: 24px; text-align: right; user-select: none; }
.prog td.instr { color: #1d3557; white-space: pre; }
.prog td.vars { display: flex; gap: 4px; flex-wrap: wrap; padding: .2rem .4rem; }
.var-chip { padding: 2px 8px; border-radius: 12px; font-size: .8rem; font-weight: 600; transition: background .2s, color .2s; }
.var-chip.live { background: #d1fae5; color: #065f2e; border: 1px solid #6ee7b7; }
.var-chip.dead { background: #e5e7eb; color: #6b7280; border: 1px solid #d1d5db; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .4rem; line-height: 1.5; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .2rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }

// Code not found

Step through the program or click Run analysis to see the fixed-point solution. A variable highlighted in green is live at that point — its current value might still be read. A gray variable is dead — its register is free to reuse.

Liveness is computed by solving a system of set equations over the control-flow graph (CFG). For each basic block $B$, the equations are:

$$\text{LiveOut}(B) = \bigcup_{S \in \text{succ}(B)} \text{LiveIn}(S)$$

$$\text{LiveIn}(B) = \text{use}(B) \;\cup\; (\text{LiveOut}(B) \setminus \text{def}(B))$$

Here $\text{use}(B)$ is the set of variables read in $B$ before any local definition, and $\text{def}(B)$ is the set of variables defined in $B$. The algorithm iterates these equations until no set changes — the fixed point.

• Termination: sets only grow monotonically (upward in the lattice of subsets), so the fixed point is always reached. With $n$ blocks and $v$ variables the work is $O(n \cdot v)$ per round and converges in at most $d+2$ rounds, where $d$ is the loop-nesting depth.
• In practice linear: for reducible CFGs (virtually all real programs) the analysis runs in $O(n)$, which is why it appears in the hot path of every production compiler.
• Undecidability lurks nearby: for interprocedural liveness — tracking what's live across function calls — the problem becomes undecidable in general. Compilers conservatively over-approximate: if a variable might be live, treat it as live.

Fran Allen introduced dataflow analysis frameworks at IBM in 1970, and liveness became one of the canonical examples. It is the direct ancestor of register allocation via graph coloring: two variables whose live ranges overlap cannot share a register, and that overlap graph is the interference graph handed to the allocator.

Liveness analysis is one of the most widely used dataflow analyses in practice:

• Register allocation: two variables that are live at the same point interfere — they cannot share a register. The live-range interference graph is exactly the graph that graph-coloring allocators color. Without liveness, register allocation is blind.
• Dead-code elimination: if a variable is defined but its live range is empty immediately after — no future use — the definition is dead and can be deleted. Liveness makes this precise.
• Garbage collection: many GC systems use liveness information to collect objects sooner. A precise GC only keeps objects whose references are live; an imprecise one must be conservative and keep more.
• SSA construction: Static Single Assignment form, the IR used by LLVM and GCC, inserts φ-functions exactly where live ranges of the same variable merge. Liveness pinpoints those merge points.
• Security: uninitialized-variable detectors and memory sanitizers flag variables that are used before being defined — the dual of a dead variable. Same dataflow, opposite direction.

Every time a C, Rust, Java or Swift compiler produces fast code, liveness analysis has already run, silently deciding the fate of every variable in your program.

Liveness analysis is a beautiful example of a problem that looks like it requires seeing the future — "will this variable be read?" — but is solved perfectly by looking backward. The fixed-point iteration over set equations is provably correct, always terminates, and runs in linear time on real programs.

The next time a compiler squeezes an extra variable into a register, or a garbage collector frees an object the moment you stop using it, liveness analysis is the reason. It is one of the oldest and most elegant tools in the compiler writer's kit — and a direct gateway to register allocation via graph coloring and the wider world of program equivalence checking.