ra2 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
  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.