.bp .NH 1 Inline substitution .NH 2 Introduction .PP The Inline Substitution technique (IL) tries to decrease the overhead associated with procedure calls (invocations). During a procedure call, several actions must be undertaken to set up the right environment for the called procedure. .[ johnson calling sequence .] On return from the procedure, most of these effects must be undone. This entire process introduces significant costs in execution time as well as in object code size. .PP The inline substitution technique replaces some of the calls by the modified body of the called procedure, hence eliminating the overhead. Furthermore, as the calling and called procedure are now integrated, they can be optimized together, using other techniques of the optimizer. This often leads to extra opportunities for optimization .[ ball predicting effects .] .[ carter code generation cacm .] .[ scheifler inline cacm .] .PP An inline substitution of a call to a procedure P increases the size of the program, unless P is very small or P is called only once. In the latter case, P can be eliminated. In practice, procedures that are called only once occur quite frequently, due to the introduction of structured programming. (Carter .[ carter umi ann arbor .] states that almost 50% of the Pascal procedures he analyzed were called just once). .PP Scheifler .[ scheifler inline cacm .] has a more general view of inline substitution. In his model, the program under consideration is allowed to grow by a certain amount, i.e. code size is sacrificed to speed up the program. The above two cases are just special cases of his model, obtained by setting the size-change to (approximately) zero. He formulates the substitution problem as follows: .IP "Given a program, a subset of all invocations, a maximum program size, and a maximum procedure size, find a sequence of substitutions that minimizes the expected execution time." .LP Scheifler shows that this problem is NP-complete .[~[ aho hopcroft ullman analysis algorithms .], chapter 10] by reduction to the Knapsack Problem. Heuristics will have to be used to find a near-optimal solution. .PP In the following chapters we will extend Scheifler's view and adapt it to the EM Global Optimizer. We will first describe the transformations that have to be applied to the EM text when a call is substituted in line. Next we will examine in which cases inline substitution is not possible or desirable. Heuristics will be developed for chosing a good sequence of substitutions. These heuristics make no demand on the user (such as making profiles .[ scheifler inline cacm .] or giving pragmats .[~[ ichbiah ada military standard .], section 6.3.2]), although the model could easily be extended to use such information. Finally, we will discuss the implementation of the IL phase of the optimizer. .PP We will often use the term inline expansion as a synonym of inline substitution. .sp 0 The inverse technique of procedure abstraction (automatic subroutine generation) .[ shaffer subroutine generation .] will not be discussed in this report.