doc/ego/ud/ud2

   1 .NH 2
   2 Data flow information
   3 .PP
   4 .NH 3
   5 Use-Definition information
   6 .PP
   7 A \fIdefinition\fR of a variable A is an assignment to A.
   8 A definition is said to \fIreach\fR a point p if there is a
   9 path in the control flow graph from the definition to p, such that
  10 A is not redefined on that path.
  11 .PP
  12 For every basic block B, we define the following sets:
  13 .IP GEN[b] 9
  14 the set of definitions in b that reach the end of b.
  15 .IP KILL[b]
  16 the set of definitions outside b that define a variable that
  17 is changed in b.
  18 .IP IN[b]
  19 the set of all definitions reaching the beginning of b.
  20 .IP OUT[b]
  21 the set of all definitions reaching the end of b.
  22 .LP
  23 GEN and KILL can be determined by inspecting the code of the procedure.
  24 IN and OUT are computed by solving the following data flow equations:
  25 .DS
  26 (1)    OUT[b] = IN[b] - KILL[b] + GEN[b]
  27 (2)    IN[b]  = OUT[p1] + ... + OUT[pn],
  28          where PRED(b) = {p1, ... , pn}
  29 .DE
  30 .NH 3
  31 Copy information
  32 .PP
  33 A \fIcopy\fR is a definition of the form "A := B".
  34 A copy is said to be \fIgenerated\fR in a basic block n if
  35 it occurs in n and there is no subsequent assignment to B in n.
  36 A copy is said to be \fIkilled\fR in n if:
  37 .IP (i)
  38 it occurs in n and there is a subsequent assignment to B within n, or
  39 .IP (ii)
  40 it occurs outside n, the definition A := B reaches the beginning of n
  41 and B is changed in n (note that a copy also is a definition).
  42 .LP
  43 A copy \fIreaches\fR a point p, if there are no assignments to B
  44 on any path in the control flow graph from the copy to p.
  45 .PP
  46 We define the following sets:
  47 .IP C_GEN[b] 11
  48 the set of all copies in b generated in b.
  49 .IP C_KILL[b]
  50 the set of all copies killed in b.
  51 .IP C_IN[b]
  52 the set of all copies reaching the beginning of b.
  53 .IP C_OUT[b]
  54 the set of all copies reaching the end of b.
  55 .LP
  56 C_IN and C_OUT are computed by solving the following equations:
  57 (root is the entry node of the current procedure; '*' denotes
  58 set intersection)
  59 .DS
  60 (1)    C_OUT[b] = C_IN[b] - C_KILL[b] + C_GEN[b]
  61 (2)    C_IN[b]  = C_OUT[p1] * ... * C_OUT[pn],
  62          where PRED(b) = {p1, ... , pn} and b /= root
  63        C_IN[root] = {all copies}
  64 .DE