doc/ego/ud/ud1

   1 .bp
   2 .NH 1
   3 Use-Definition analysis
   4 .NH 2
   5 Introduction
   6 .PP
   7 The "Use-Definition analysis" phase (UD) consists of two related optimization
   8 techniques that both depend on "Use-Definition" information.
   9 The techniques are Copy Propagation and Constant Propagation.
  10 They are best explained via an example (see Figs. 11.1 and 11.2).
  11 .DS
  12    (1)  A := B                  A := B
  13          ...          -->        ...
  14    (2)  use(A)                  use(B)
  15
  16 Fig. 11.1 An example of Copy Propagation
  17 .DE
  18 .DS
  19    (1)  A := 12                  A := 12
  20          ...          -->        ...
  21    (2)  use(A)                  use(12)
  22
  23 Fig. 11.2 An example of Constant Propagation
  24 .DE
  25 Both optimizations have to check that the value of A at line (2)
  26 can only be obtained at line (1).
  27 Copy Propagation also has to assure that the value of B is
  28 the same at line (1) as at line (2).
  29 .PP
  30 One purpose of both transformations is to introduce
  31 opportunities for the Dead Code Elimination optimization.
  32 If the variable A is used nowhere else, the assignment A := B
  33 becomes useless and can be eliminated.
  34 .sp 0
  35 If B is less expensive to access than A (e.g. this is sometimes the case
  36 if A is a local variable and B is a global variable),
  37 Copy Propagation directly improves the code itself.
  38 If A is cheaper to access the transformation will not be performed.
  39 Likewise, a constant as operand may be cheeper than a variable.
  40 Having a constant as operand may also facilitate other optimizations.
  41 .PP
  42 The design of UD is based on the theory described in section
  43 14.1 and 14.3 of.
  44 .[
  45 aho compiler design
  46 .]
  47 As a main departure from that theory,
  48 we do not demand the statement A := B to become redundant after
  49 Copy Propagation.
  50 If B is cheaper to access than A, the optimization is always performed;
  51 if B is more expensive than A, we never do the transformation.
  52 If A and B are equally expensive UD uses the heuristic rule to
  53 replace infrequently used variables by frequently used ones.
  54 This rule increases the chances of the assignment to become useless.
  55 .PP
  56 In the next section we will give a brief outline of the data
  57 flow theory used
  58 for the implementation of UD.