doc/ego/il/il3

   1 .NH 2
   2 Feasibility and desirability analysis
   3 .PP
   4 Feasibility and desirability analysis
   5 of in line substitution differ
   6 somewhat from most other techniques.
   7 Usually, much effort is needed to find
   8 a feasible opportunity for optimization
   9 (e.g. a redundant subexpression).
  10 Desirability analysis then checks
  11 if it is really advantageous to do
  12 the optimization.
  13 For IL, opportunities are easy to find.
  14 To see if an in line expansion is
  15 desirable will not be hard either.
  16 Yet, the main problem is to find the most
  17 desirable ones.
  18 We will deal with this problem later and
  19 we will first attend feasibility and
  20 desirability analysis.
  21 .PP
  22 There are several reasons why a procedure invocation
  23 cannot or should not be expanded in line.
  24 .sp
  25 A call to a procedure P cannot be expanded in line
  26 in any of the following cases:
  27 .IP 1. 3
  28 The body of P is not available as EM text.
  29 Clearly, there is no way to do the substitution.
  30 .IP 2.
  31 P, or any procedure called by P (transitively),
  32 follows the chain of statically enclosing
  33 procedures (via a LXL or LXA instruction)
  34 or follows the chain of dynamically enclosing
  35 procedures (via a DCH).
  36 If the call were expanded in line,
  37 one level would be removed from the chains,
  38 leading to total chaos.
  39 This chaos could be solved by patching up
  40 every LXL, LXA or DCH in all procedures
  41 that could be part of the chains,
  42 but this is hard to implement.
  43 .IP 3.
  44 P, or any procedure called by P (transitively),
  45 calls a procedure whose body is not
  46 available as EM text.
  47 The unknown procedure may use an LXL, LXA or DCH.
  48 However, in several languages a separately
  49 compiled procedure has no access to the
  50 static or dynamic chain.
  51 In this case
  52 this point does not apply.
  53 .IP 4.
  54 P, or any procedure called by P (transitively),
  55 uses the LPB instruction, which converts a
  56 local base to an argument base;
  57 as the locals and parameters are stored
  58 in a non-standard way (differing from the
  59 normal EM calling sequence) this instruction
  60 would yield incorrect results.
  61 .IP 5.
  62 The total number of bytes of the parameters
  63 of P is not known.
  64 P may be a procedure with a variable number
  65 of parameters or may have an array of dynamic size
  66 as value parameter.
  67 .LP
  68 It is undesirable to expand a call to a procedure P in line
  69 in any of the following cases:
  70 .IP 1. 3
  71 P is large, i.e. the number of EM instructions
  72 of P exceeds some threshold.
  73 The expanded code would be large too.
  74 Furthermore, several programs in ACK,
  75 including the global optimizer itself,
  76 may run out of memory if they they have to run
  77 in a small address space and are provided
  78 very large procedures.
  79 The threshold may be set to infinite,
  80 in which case this point does not apply.
  81 .IP 2.
  82 P has many local variables.
  83 All these variables would have to be allocated
  84 in the stack frame of the calling procedure.
  85 .PP
  86 If a call may be expanded in line, we have to
  87 decide how to access its parameters.
  88 In the previous section we stated that we would
  89 use in line parameters whenever possible and desirable.
  90 There are several reasons why a parameter
  91 cannot or should not be expanded in line.
  92 .sp
  93 No parameter of a procedure P can be expanded in line,
  94 in any of the following cases:
  95 .IP 1. 3
  96 P, or any procedure called by P (transitively),
  97 does a store-indirect or a use-indirect (i.e. through
  98 a pointer).
  99 However, if the front-end has generated messages
 100 telling that certain parameters can not be accessed
 101 indirectly, those parameters may be expanded in line.
 102 .IP 2.
 103 P, or any procedure called by P (transitively),
 104 calls a procedure whose body is not available as EM text.
 105 The unknown procedure may do a store-indirect
 106 or a use-indirect.
 107 However, the same remark about front-end messages
 108 as for 1. holds here.
 109 .IP 3.
 110 The address of a parameter location is taken (via a LAL).
 111 In the normal calling sequence, all parameters
 112 are stored sequentially. If the address of one
 113 parameter location is taken, the address of any
 114 other parameter location can be computed from it.
 115 Hence we must put every parameter in a temporary location;
 116 furthermore, all these locations must be in
 117 the same order as for the normal calling sequence.
 118 .IP 4.
 119 P has overlapping parameters; for example, it uses
 120 the parameter at offset 10 both as a 2 byte and as a 4 byte
 121 parameter.
 122 Such code may be produced by the front ends if
 123 the formal parameter is of some record type
 124 with variants.
 125 .PP
 126 Sometimes a specific parameter must not be expanded in line.
 127 .sp 0
 128 An actual parameter expression cannot be expanded in line
 129 in any of the following cases:
 130 .IP 1. 3
 131 P stores into the parameter location.
 132 Even if the actual parameter expression is a simple
 133 variable, it is incorrect to change the 'store into
 134 formal' into a 'store into actual', because of
 135 the parameter mechanism used.
 136 In Pascal, the following expansion is incorrect:
 137 .DS
 138 procedure p (x:integer);
 139 begin
 140    x := 20;
 141 end;
 142 \&...
 143 a := 10;                \kxa := 10;
 144 p(a);        --->       \h'|\nxu'a := 20;
 145 write(a);               \h'|\nxu'write(a);
 146 .DE
 147 .IP 2.
 148 P changes any of the operands of the
 149 actual parameter expression.
 150 If the expression is expanded and evaluated
 151 after the operand has been changed,
 152 the wrong value will be used.
 153 .IP 3.
 154 The actual parameter expression has side effects.
 155 It must be evaluated only once,
 156 at the place of the call.
 157 .LP
 158 It is undesirable to expand an actual parameter in line
 159 in the following case:
 160 .IP 1. 3
 161 The parameter is used more than once
 162 (dynamically) and the actual parameter expression
 163 is not just a simple variable or constant.
 164 .LP