Live variable analysis

In compiler theory, live variable analysis (or simply liveness analysis) is a classic data-flow analysis performed by compilers to calculate for each program point the variables that may be potentially read before their next write, that is, the variables that are live at the exit from each program point.

Stated simply: a variable is live if it holds a value that may be needed in the future.

Recently as of 2006^[update], various program analyses such as live variable analysis have been solved using Datalog. The Datalog specifications for such analyses are generally an order of magnitude shorter than their imperative counterparts (e.g. iterative analysis), and are at least as efficient.

The set of live variables at line L3 is {b, c} because both are used in the multiplication, and thereby the call to f and assignment to a. But the set of live variables at line L1 is only {b} since variable c is updated in L2. The value of variable a is never used. Note that f may be stateful, so the never-live assignment to a can be eliminated, but there is insufficient information to rule on the entirety of L3.

Liveness analysis is a "backwards may" analysis. The analysis is done in a backwards order, and the dataflow confluence operator is set union. In otherwords, if applying liveness analysis to a function with a particular number of logical branches within it, the analysis is performed starting from the end of the function working towards the beginning (hence "backwards"), and a variable is considered live if any of the branches moving forward within the function might potentially (hence "may") need the variable's current value. This is in contrast to a "backwards must" analysis which would instead enforces this condition on all branches moving forward.

The dataflow equations used for a given basic block s and exiting block f in live variable analysis are the following:

...
Wikipedia