123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112 |
- .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.
|