doc/ego/il/il1

   1 .bp
   2 .NH 1
   3 Inline substitution
   4 .NH 2
   5 Introduction
   6 .PP
   7 The Inline Substitution technique (IL)
   8 tries to decrease the overhead associated
   9 with procedure calls (invocations).
  10 During a procedure call, several actions
  11 must be undertaken to set up the right
  12 environment for the called procedure.
  13 .[
  14 johnson calling sequence
  15 .]
  16 On return from the procedure, most of these
  17 effects must be undone.
  18 This entire process introduces significant
  19 costs in execution time as well as
  20 in object code size.
  21 .PP
  22 The inline substitution technique replaces
  23 some of the calls by the modified body of
  24 the called procedure, hence eliminating
  25 the overhead.
  26 Furthermore, as the calling and called procedure
  27 are now integrated, they can be optimized
  28 together, using other techniques of the optimizer.
  29 This often leads to extra opportunities for
  30 optimization
  31 .[
  32 ball predicting effects
  33 .]
  34 .[
  35 carter code generation cacm
  36 .]
  37 .[
  38 scheifler inline cacm
  39 .]
  40 .PP
  41 An inline substitution of a call to a procedure P increases
  42 the size of the program, unless P is very small or P is
  43 called only once.
  44 In the latter case, P can be eliminated.
  45 In practice, procedures that are called only once occur
  46 quite frequently, due to the
  47 introduction of structured programming.
  48 (Carter
  49 .[
  50 carter umi ann arbor
  51 .]
  52 states that almost 50% of the Pascal procedures
  53 he analyzed were called just once).
  54 .PP
  55 Scheifler
  56 .[
  57 scheifler inline cacm
  58 .]
  59 has a more general view of inline substitution.
  60 In his model, the program under consideration is
  61 allowed to grow by a certain amount,
  62 i.e. code size is sacrificed to speed up the program.
  63 The above two cases are just special cases of
  64 his model, obtained by setting the size-change to
  65 (approximately) zero.
  66 He formulates the substitution problem as follows:
  67 .IP
  68 "Given a program, a subset of all invocations,
  69 a maximum program size, and a maximum procedure size,
  70 find a sequence of substitutions that minimizes
  71 the expected execution time."
  72 .LP
  73 Scheifler shows that this problem is NP-complete
  74 .[~[
  75 aho hopcroft ullman analysis algorithms
  76 .], chapter 10]
  77 by reduction to the Knapsack Problem.
  78 Heuristics will have to be used to find a near-optimal
  79 solution.
  80 .PP
  81 In the following chapters we will extend
  82 Scheifler's view and adapt it to the EM Global Optimizer.
  83 We will first describe the transformations that have
  84 to be applied to the EM text when a call is substituted
  85 in line.
  86 Next we will examine in which cases inline substitution
  87 is not possible or desirable.
  88 Heuristics will be developed for
  89 chosing a good sequence of substitutions.
  90 These heuristics make no demand on the user
  91 (such as making profiles
  92 .[
  93 scheifler inline cacm
  94 .]
  95 or giving pragmats
  96 .[~[
  97 ichbiah ada military standard
  98 .], section 6.3.2]),
  99 although the model could easily be extended
 100 to use such information.
 101 Finally, we will discuss the implementation
 102 of the IL phase of the optimizer.
 103 .PP
 104 We will often use the term inline expansion
 105 as a synonym of inline substitution.
 106 .sp 0
 107 The inverse technique of procedure abstraction
 108 (automatic subroutine generation)
 109 .[
 110 shaffer subroutine generation
 111 .]
 112 will not be discussed in this report.