doc/ego/ra/ra2

   1 .NH 2
   2 Usage of registers in ACK compilers
   3 .PP
   4 We will first describe the major design decisions
   5 of the Amsterdam Compiler Kit,
   6 as far as they concern register allocation.
   7 Subsequently we will outline
   8 the role of the Global Optimizer in the register
   9 allocation process and the interface
  10 between the code generator and the optimizer.
  11 .NH 3
  12 Usage of registers without the intervention of the Global Optimizer
  13 .PP
  14 Registers are used for two purposes:
  15 .IP 1.
  16 for the evaluation of arithmetic expressions
  17 .IP 2.
  18 to hold local variables, for the duration of the procedure they
  19 are local to.
  20 .LP
  21 It is essential to note that no translation part of the compilers,
  22 except for the code generator, knows anything at all
  23 about the register set of the target computer.
  24 Hence all decisions about registers are ultimately made by
  25 the code generator.
  26 Earlier phases of a compiler can only \fIadvise\fR the code generator.
  27 .PP
  28 The code generator splits the register set into two:
  29 a fixed part for the evaluation of expressions (called \fIscratch\fR
  30 registers) and a fixed part to store local variables.
  31 This partitioning, which depends only on the target computer, significantly
  32 reduces the complexity of register allocation, at the penalty
  33 of some loss of code quality.
  34 .PP
  35 The code generator has some (machine-dependent) knowledge of the access costs
  36 of memory locations and registers and of the costs of saving and
  37 restoring registers. (Registers are always saved by the \fIcalled\fR
  38 procedure).
  39 This knowledge is expressed in a set of procedures for each target machine.
  40 The code generator also knows how many registers there are and of
  41 which type they are.
  42 A register can be of type \fIpointer\fR, \fIfloating point\fR
  43 or \fIgeneral\fR.
  44 .PP
  45 The front ends of the compilers determine which local variables may
  46 be put in a register;
  47 such a variable may never be accessed indirectly (i.e. through a pointer).
  48 The front end also determines the types and sizes of these variables.
  49 The type can be any of the register types or the type \fIloop variable\fR,
  50 which denotes a general-typed variable that is used as loop variable
  51 in a for-statement.
  52 All this information is collected in a \fIregister message\fR in
  53 the EM code.
  54 Such a message is a pseudo EM instruction.
  55 This message also contains a \fIscore\fR field,
  56 indicating how desirable it is to put this variable in a register.
  57 A front end may assign a high score to a variable if it
  58 was declared as a register variable (which is only possible in
  59 some languages, such as "C").
  60 Any compiler phase before the code generator may change this score field,
  61 if it has reason to do so.
  62 The code generator bases its decisions on the information contained
  63 in the register message, most notably on the score.
  64 .PP
  65 If the global optimizer is not used,
  66 the score fields are set by the Peephole Optimizer.
  67 This optimizer simply counts the number of occurrences
  68 of every local (register) variable and adds this count
  69 to the score provided by the front end.
  70 In this way a simple, yet quite effective
  71 register allocation scheme is achieved.
  72 .NH 3
  73 The role of the Global Optimizer
  74 .PP
  75 The Global Optimizer essentially tries to improve the scheme
  76 outlined above.
  77 It uses the following principles for this purpose:
  78 .IP -
  79 Entities are not always assigned a register for the duration
  80 of an entire procedure; smaller regions of the program text
  81 may be considered too.
  82 .IP -
  83 several variables may be put in the same register simultaneously,
  84 provided at most one of them is live at any point.
  85 .IP -
  86 besides local variables, other entities (such as constants and addresses of
  87 variables and procedures) may be put in a register.
  88 .IP -
  89 more accurate cost estimates are used.
  90 .LP
  91 To perform its task, the optimizer must have some
  92 knowledge of the target machine.
  93 .NH 3
  94 The interface between the register allocator and the code generator
  95 .PP
  96 The RA phase of the optimizer must somehow be able to express its
  97 decisions.
  98 Such decisions may look like: 'put constant 1283 in a register from
  99 line 12 to line 40'.
 100 To be precise, RA must be able to tell the code generator to:
 101 .IP -
 102 initialize a register with some value
 103 .IP -
 104 update an entity from a register
 105 .IP -
 106 replace all occurrences of an entity in a certain region
 107 of text by a reference to the register.
 108 .LP
 109 At least three problems occur here: the code generator is only used to
 110 put local variables in registers,
 111 it only assigns a register to a variable for the duration of an entire
 112 procedure and it is not used to have some earlier compiler phase
 113 make all the decisions.
 114 .PP
 115 All problems are solved by one mechanism, that involves no changes
 116 to the code generator.
 117 With every (non-scratch) register R that will be used in
 118 a procedure P, we associate a new variable T, local to P.
 119 The size of T is the same as the size of R.
 120 A register message is generated for T with an exceptionally high score.
 121 The scores of all original register messages are set to zero.
 122 Consequently, the code generator will always assign precisely those new
 123 variables to a register.
 124 If the optimizer wants to put some entity, say the constant 1283, in
 125 a register, it emits the code "T := 1283" and replaces all occurrences
 126 of '1283' by T.
 127 Similarly, it can put the address of a procedure in T and replace all
 128 calls to that procedure by indirect calls.
 129 Furthermore, it can put several different entities in T (and thus in R)
 130 during the lifetime of P.
 131 .PP
 132 In principle, the code generated by the optimizer in this way would
 133 always be valid EM code, even if the optimizer would be presented
 134 a totally wrong description of the target computer register set.
 135 In practice, it would be a waste of data as well as text space to
 136 allocate memory for these new variables, as they will always be assigned
 137 a register (in the correct order of events).
 138 Hence, no memory locations are allocated for them.
 139 For this reason they are called pseudo local variables.