doc/ego/sp/sp1

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