1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495 |
- .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).
|