il3 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164
  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