doc/ego/lv/lv1

   1 .bp
   2 .NH 1
   3 Live-Variable analysis
   4 .NH 2
   5 Introduction
   6 .PP
   7 The "Live-Variable analysis" optimization technique (LV)
   8 performs some code improvements and computes information that may be
   9 used by subsequent optimizations.
  10 The main task of this phase is the
  11 computation of \fIlive-variable information\fR.
  12 .[~[
  13 aho compiler design
  14 .] section 14.4]
  15 A variable A is said to be \fIdead\fR at some point p of the
  16 program text, if on no path in the control flow graph
  17 from p to a RET (return), A can be used before being changed;
  18 else A is said to be \fIlive\fR.
  19 .PP
  20 A statement of the form
  21 .DS
  22 VARIABLE := EXPRESSION
  23 .DE
  24 is said to be dead if the left hand side variable is dead just after
  25 the statement and the right hand side expression has no
  26 side effects (i.e. it doesn't change any variable).
  27 Such a statement can be eliminated entirely.
  28 Dead code will seldom be present in the original program,
  29 but it may be the result of earlier optimizations,
  30 such as copy propagation.
  31 .PP
  32 Live-variable information is passed to other phases via
  33 messages in the EM code.
  34 Live/dead messages are generated at points in the EM text where
  35 variables become dead or live.
  36 This information is especially useful for the Register
  37 Allocation phase.
  38 .NH 2
  39 Implementation
  40 .PP
  41 The implementation uses algorithm 14.6 of.
  42 .[
  43 aho compiler design
  44 .]
  45 First two sets DEF and USE are computed for every basic block b:
  46 .IP DEF(b) 9
  47 the set of all variables that are assigned a value in b before
  48 being used
  49 .IP USE(b) 9
  50 the set of all variables that may be used in b before being changed.
  51 .LP
  52 (So variables that may, but need not, be used resp. changed via a procedure
  53 call or through a pointer are included in USE but not in DEF).
  54 The next step is to compute the sets IN and OUT :
  55 .IP IN[b] 9
  56 the set of all variables that are live at the beginning of b
  57 .IP OUT[b] 9
  58 the set of all variables that are live at the end of b
  59 .LP
  60 IN and OUT can be computed for all blocks simultaneously by solving the
  61 data flow equations:
  62 .DS
  63 (1)   IN[b] = OUT[b] - DEF[b] + USE[b]
  64 [2]   OUT[b] = IN[s1] + ... + IN[sn] ;
  65         where SUCC[b] = {s1, ... , sn}
  66 .DE
  67 The equations are solved by a similar algorithm as for
  68 the Use Definition equations (see previous chapter).
  69 .PP
  70 Finally, each basic block is visited in turn to remove its dead code
  71 and to emit the live/dead messages.
  72 Every basic block b is traversed from its last
  73 instruction backwards to the beginning of b.
  74 Initially, all variables that are dead at the end
  75 of b are marked dead. All others are marked live.
  76 If we come across an assignment to a variable X that
  77 was marked live, a live-message is put after the
  78 assignment and X is marked dead;
  79 if X was marked dead, the assignment may be removed, provided that
  80 the right hand side expression contains no side effects.
  81 If we come across a use of a variable X that
  82 was marked dead, a dead-message is put after the
  83 use and X is marked live.
  84 So at any point, the mark of X tells whether X is
  85 live or dead immediately before that point.
  86 A message is also generated at the start of a basic block
  87 for every variable that was live at the end of the (textually)
  88 previous block, but dead at the entry of this block, or v.v.
  89 .PP
  90 Only local variables are considered.
  91 This significantly reduces the memory needed by this phase,
  92 eases the implementation and is hardly less efficient than
  93 considering all variables.
  94 (Note that it is very hard to prove that an assignment to
  95 a global variable is dead).