.bp .NH 1 Live-Variable analysis .NH 2 Introduction .PP The "Live-Variable analysis" optimization technique (LV) performs some code improvements and computes information that may be used by subsequent optimizations. The main task of this phase is the computation of \fIlive-variable information\fR. .[~[ aho compiler design .] section 14.4] A variable A is said to be \fIdead\fR at some point p of the program text, if on no path in the control flow graph from p to a RET (return), A can be used before being changed; else A is said to be \fIlive\fR. .PP A statement of the form .DS VARIABLE := EXPRESSION .DE is said to be dead if the left hand side variable is dead just after the statement and the right hand side expression has no side effects (i.e. it doesn't change any variable). Such a statement can be eliminated entirely. Dead code will seldom be present in the original program, but it may be the result of earlier optimizations, such as copy propagation. .PP Live-variable information is passed to other phases via messages in the EM code. Live/dead messages are generated at points in the EM text where variables become dead or live. This information is especially useful for the Register Allocation phase. .NH 2 Implementation .PP The implementation uses algorithm 14.6 of. .[ aho compiler design .] First two sets DEF and USE are computed for every basic block b: .IP DEF(b) 9 the set of all variables that are assigned a value in b before being used .IP USE(b) 9 the set of all variables that may be used in b before being changed. .LP (So variables that may, but need not, be used resp. changed via a procedure call or through a pointer are included in USE but not in DEF). The next step is to compute the sets IN and OUT : .IP IN[b] 9 the set of all variables that are live at the beginning of b .IP OUT[b] 9 the set of all variables that are live at the end of b .LP IN and OUT can be computed for all blocks simultaneously by solving the data flow equations: .DS (1) IN[b] = OUT[b] - DEF[b] + USE[b] [2] OUT[b] = IN[s1] + ... + IN[sn] ; where SUCC[b] = {s1, ... , sn} .DE The equations are solved by a similar algorithm as for the Use Definition equations (see previous chapter). .PP Finally, each basic block is visited in turn to remove its dead code and to emit the live/dead messages. Every basic block b is traversed from its last instruction backwards to the beginning of b. Initially, all variables that are dead at the end of b are marked dead. All others are marked live. If we come across an assignment to a variable X that was marked live, a live-message is put after the assignment and X is marked dead; if X was marked dead, the assignment may be removed, provided that the right hand side expression contains no side effects. If we come across a use of a variable X that was marked dead, a dead-message is put after the use and X is marked live. So at any point, the mark of X tells whether X is live or dead immediately before that point. A message is also generated at the start of a basic block for every variable that was live at the end of the (textually) previous block, but dead at the entry of this block, or v.v. .PP Only local variables are considered. This significantly reduces the memory needed by this phase, eases the implementation and is hardly less efficient than considering all variables. (Note that it is very hard to prove that an assignment to a global variable is dead).