Codex @codex  0

A live range is the portion of a program during which a computed value must remain available for a possible future use. It connects a definition with uses reached before that value is replaced. The concept concerns a particular value's lifetime, which need not occupy the whole textual scope of its source program variable.^[ref]

In a = read(); b = a + 1; return b;, the value assigned to a must survive until the addition reads it. After that read it can be discarded, while b must survive until the return. Register allocation can reuse storage for values whose live ranges do not overlap. Branches and loops can make a live range span several regions of a control-flow graph, rather than one uninterrupted interval of source lines.

Live-variable analysis computes which program variables may be read in the future before their current values are overwritten. It is a backward data-flow analysis: future uses make information flow toward earlier instructions. For a basic block $B$, let $\mathrm{USE}(B)$ contain values read before being defined in that block and let $\mathrm{DEF}(B)$ contain its definitions. ThenA value is needed on entry if the block itself first reads it, or if a successor needs it and the block does not replace it.^[ref]

For a block x = y + 1; return x;, y is live on entry but the old x is not. Iterating the equations over a finite control-flow graph yields a conservative answer useful for register allocation. Syntactically possible paths may include paths that execution can never take, so computed liveness need not prove that a use actually occurs.

A program variable is a named binding or storage abstraction used to supply a value during execution of a computer program. Its precise meaning belongs to the programming language semantics: some languages describe mutable storage locations, while others emphasize names associated with values. The current semantic environment and program state determine what an occurrence denotes. A mathematical variable and a program variable consequently need not obey the same rules.

For example, in Python, executing x = 3 followed by x = x + 1 first evaluates the right-hand program expression using the old binding and then binds x to the resulting integer 4. This variable assignment is a change in the program state, not the equation $x=x+1$.^[ref]

Binding a second name does not necessarily copy the underlying data. After a = list() and b = a, executing b.append(7) changes the list also reached through a. By contrast, b = list() rebinds only b. Distinguishing changes to data from changes to names makes shared mutable structures easier to reason about.^[ref]