doc/ego/ud/ud4

   1 .NH 2
   2 Implementation
   3 .PP
   4 UD first builds a number of tables:
   5 .IP locals: 9
   6 contains information about the local variables of the
   7 current procedure (offset,size,whether a register message was found
   8 for it and, if so, the score field of that message)
   9 .IP defs:
  10 a table of all explicit definitions appearing in the
  11 current procedure.
  12 .IP copies:
  13 a table of all copies appearing in the
  14 current procedure.
  15 .LP
  16 Every variable (local as well as global), definition and copy
  17 is identified by a unique number, which is the index
  18 in the table.
  19 All tables are constructed by traversing the EM code.
  20 A fourth table, "vardefs" is used, indexed by a 'variable number',
  21 which contains for every variable the set of explicit definitions of it.
  22 Also, for each basic block b, the set CHGVARS containing all variables
  23 changed by it is computed.
  24 .PP
  25 The GEN sets are obtained in one scan over the EM text,
  26 by analyzing every EM instruction.
  27 The KILL set of a basic block b is computed by looking at the
  28 set of variables
  29 changed by b (i.e. CHGVARS[b]).
  30 For every such variable v, all explicit definitions to v
  31 (i.e. vardefs[v]) that are not in GEN[b] are added to KILL[b].
  32 Also, the implicit defininition of v is added to KILL[b].
  33 Next, the data flow equations for use-definition information
  34 are solved,
  35 using a straight forward, iterative algorithm.
  36 All sets are represented as bitvectors, so the operations
  37 on sets (union, difference) can be implemented efficiently.
  38 .PP
  39 The C_GEN and C_KILL sets are computed simultaneously in one scan
  40 over the EM text.
  41 For every copy A := B appearing in basic block b we do
  42 the following:
  43 .IP 1.
  44 for every basic block n /= b that changes B, see if the definition A := B
  45 reaches the beginning of n (i.e. check if the index number of A := B in
  46 the "defs" table is an element of IN[n]);
  47 if so, add the copy to C_KILL[n]
  48 .IP 2.
  49 if B is redefined later on in b, add the copy to C_KILL[b], else
  50 add it to C_GEN[b]
  51 .LP
  52 C_IN and C_OUT are computed from C_GEN and C_KILL via the second set of
  53 data flow equations.
  54 .PP
  55 Finally, in one last scan all opportunities for optimization are
  56 detected.
  57 For every use u of a variable A, we check if
  58 there is a unique explicit definition d reaching u.
  59 .sp
  60 If the definition is a copy A := B and B has the same value at d as
  61 at u, then the use of A at u may be changed into B.
  62 The latter condition can be verified as follows:
  63 .IP -
  64 if u and d are in the same basic block, see if there is
  65 any assignment to B in between d and u
  66 .IP -
  67 if u and d are in different basic blocks, the condition is
  68 satisfied if there is no assignment to B in the block of u prior to u
  69 and d is in C_IN[b].
  70 .LP
  71 Before the transformation is actually done, UD first makes sure the
  72 alteration is really desirable, as described before.
  73 The information needed for this purpose (access costs of local and
  74 global variables) is read from a machine descriptor file.
  75 .sp
  76 If the only definition reaching u has the form "A := constant", the use
  77 of A at u is replaced by the constant.
  78