sp1 5.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184
  1. .bp
  2. .NH 1
  3. Stack pollution
  4. .NH 2
  5. Introduction
  6. .PP
  7. The "Stack Pollution" optimization technique (SP) decreases the costs
  8. (time as well as space) of procedure calls.
  9. In the EM calling sequence, the actual parameters are popped from
  10. the stack by the \fIcalling\fR procedure.
  11. The ASP (Adjust Stack Pointer) instruction is used for this purpose.
  12. A call in EM is shown in Fig. 8.1
  13. .DS
  14. .TS
  15. l l.
  16. Pascal: EM:
  17. f(a,2) LOC 2
  18. LOE A
  19. CAL F
  20. ASP 4 -- pop 4 bytes
  21. .TE
  22. Fig. 8.1 An example procedure call in Pascal and EM
  23. .DE
  24. As procedure calls occur often in most programs,
  25. the ASP is one of the most frequently used EM instructions.
  26. .PP
  27. The main intention of removing the actual parameters after a procedure call
  28. is to avoid the stack size to increase rapidly.
  29. Yet, in some cases, it is possible to \fIdelay\fR or even \fIavoid\fR the
  30. removal of the parameters without letting the stack grow
  31. significantly.
  32. In this way, considerable savings in code size and execution time may
  33. be achieved, at the cost of a slightly increased stack size.
  34. .PP
  35. A stack adjustment may be delayed if there is some other stack adjustment
  36. later on in the same basic block.
  37. The two ASPs can be combined into one.
  38. .DS
  39. .TS
  40. l l l.
  41. Pascal: EM: optimized EM:
  42. f(a,2) LOC 2 LOC 2
  43. g(3,b,c) LOE A LOE A
  44. CAL F CAL F
  45. ASP 4 LOE C
  46. LOE C LOE B
  47. LOE B LOC 3
  48. LOC 3 CAL G
  49. CAL G ASP 10
  50. ASP 6
  51. .TE
  52. Fig. 8.2 An example of local Stack Pollution
  53. .DE
  54. The stacksize will be increased only temporarily.
  55. If the basic block contains another ASP, the ASP 10 may subsequently be
  56. combined with that next ASP, and so on.
  57. .PP
  58. For some back ends, a stack adjustment also takes place
  59. at the point of a procedure return.
  60. There is no need to specify the number of bytes to be popped at a
  61. return.
  62. This provides an opportunity to remove ASPs more globally.
  63. If all ASPs outside any loop are removed, the increase of the
  64. stack size will still only be small, as no such ASP is executed more
  65. than once without an intervening return from the procedure it is part of.
  66. .PP
  67. This second approach is not generally applicable to all target machines,
  68. as some back ends require the stack to be cleaned up at the point of
  69. a procedure return.
  70. .NH 2
  71. Implementation
  72. .PP
  73. There is one main problem the implementation has to solve.
  74. In EM, the stack is not only used for passing parameters,
  75. but also for evaluating expressions.
  76. Hence, ASP instructions can only be combined or removed
  77. if certain conditions are satisfied.
  78. .PP
  79. Two consecutive ASPs of one basic block can only be combined
  80. (as described above) if:
  81. .IP 1.
  82. On no point of text in between the two ASPs, any item is popped from
  83. the stack that was pushed onto it before the first ASP.
  84. .IP 2.
  85. The number of bytes popped from the stack by the second ASP must equal
  86. the number of bytes pushed since the first ASP.
  87. .LP
  88. Condition 1. is not satisfied in Fig. 8.3.
  89. .DS
  90. .TS
  91. l l.
  92. Pascal: EM:
  93. 5 + f(10) + g(30) LOC 5
  94. LOC 10
  95. CAL F
  96. ASP 2 -- cannot be removed
  97. LFR 2 -- push function result
  98. ADI 2
  99. LOC 30
  100. CAL G
  101. ASP 2
  102. LFR 2
  103. ADI 2
  104. .TE
  105. Fig. 8.3 An illegal transformation
  106. .DE
  107. If the first ASP were removed (delayed), the first ADI would add
  108. 10 and f(10), instead of 5 and f(10).
  109. .sp
  110. Condition 2. is not satisfied in Fig. 8.4.
  111. .DS
  112. .TS
  113. l l.
  114. Pascal: EM:
  115. f(10) + 5 * g(30) LOC 10
  116. CAL F
  117. ASP 2
  118. LFR 2
  119. LOC 5
  120. LOC 30
  121. CAL G
  122. ASP 2
  123. LFR 2
  124. MLI 2 -- 5 * g(30)
  125. ADI 2
  126. .TE
  127. Fig. 8.4 A second illegal transformation
  128. .DE
  129. If the two ASPs were combined into one 'ASP 4', the constant 5 would
  130. have been popped, rather than the parameter 10 (so '10 + f(10)*g(30)'
  131. would have been computed).
  132. .PP
  133. The second approach to deleting ASPs (i.e. let the procedure return
  134. do the stack clean-up)
  135. is only applied to the last ASP of every basic block.
  136. Any preceding ASPs are dealt with by the first approach.
  137. The last ASP of a basic block B will only be removed if:
  138. .IP -
  139. on no path in the control flow graph from B to any block containing a
  140. RET (return) there is a basic block that, at some point of its text, pops
  141. items from the stack that it has not itself pushed earlier.
  142. .LP
  143. Clearly, if this condition is satisfied, no harm can be done; no
  144. other basic block will ever access items that were pushed
  145. on the stack before the ASP.
  146. .PP
  147. The number of bytes pushed onto or popped from the stack can be
  148. easily encoded in a so called "pop-push table".
  149. The numbers in general depend on the target machine word- and pointer
  150. size and on the argument given to the instruction.
  151. For example, an ADS instruction is described by:
  152. .DS
  153. -a-p+p
  154. .DE
  155. which means: an 'ADS n' first pops an n-byte value (n being the argument),
  156. next pops a pointer-size value and finally pushes a pointer-size value.
  157. For some infrequently used EM instructions the pop-push numbers
  158. cannot be computed statically.
  159. .PP
  160. The stack pollution algorithm first performs a depth first search over
  161. the control flow graph and marks all blocks that do not satisfy
  162. the global condition.
  163. Next it visits all basic blocks in turn.
  164. For every pair of adjacent ASPs, it checks conditions 1. and 2. and
  165. combines the ASPs if they are satisfied.
  166. The new ASP may be used as first ASP in the next pair.
  167. If a condition fails, it simply continues with the next ASP.
  168. Finally, the last ASP is removed if:
  169. .IP -
  170. nothing has been popped from the stack after the last ASP that was
  171. pushed before it
  172. .IP -
  173. the block was not marked by the depth first search
  174. .IP -
  175. the block is not in a loop
  176. .LP