Liveness Analysis

live: of continuing or current interest

Webster's Dictionary

OVERVIEW

The front end of the compiler translates programs into an intermediate language with an unbounded number of temporaries. This program must run on a machine with a bounded number of registers. Two temporaries a and b can fit into the same register, if a and b are never "in use" at the same time. Thus, many temporaries can fit in few registers; if they don't all fit, the excess temporaries can be kept in memory. Therefore, the compiler needs to analyze the intermediate-representation program to determine which temporaries are in use at the same time. We say a variable is live if it holds a value that may be needed in the future, so this analysis is called liveness analysis. To perform analyses on a program, it is often useful to make a control-flow graph. Each statement in the program is a node in the flow graph; if statement x can be followed by statement y, there is an edge from x to y. shows the flow graph for a simple loop.GRAPH 10.1: Control-flow graph of a program.

Let us consider the liveness of each variable (). A variable is live if its current value will be used in the future, so we analyze liveness by working from the future to the past. Variable b is used in statement 4, so b is live on the 3 → 4 edge. Since statement 3 does not assign into b, then b is also live on the 2 → 3 edge. Statement 2 assigns into b. That means that the contents of b on the 1 → 2 edge are not needed by anyone; b is dead on this edge. So the live range of b is {2 → 3, 3 → 4}.
Image 10.2: Liveness of variables a, b, c.

The variable a is an interesting case. It's live from 1 → 2, and again from 4 → 5 → 2, but not from 2 → 3 → 4. Although a has a perfectly well-defined value at node 3, that value will not be needed again before a is assigned a new value. The variable c is live on entry to this program. Perhaps it is a formal parameter. If it is a local variable, then liveness analysis has detected an uninitialized variable; the compiler could print a warning message for the programmer.

Once all the live ranges are computed, we can see that only two registers are needed to hold a, b, and c, since a and b are never live at the same time. Register 1 can hold both a and b, and register 2 can hold c.