123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135 |
- .NH 2
- Heuristic rules
- .PP
- Using the information described
- in the previous section,
- we can find all calls that can
- be expanded in line, and for which
- this expansion is desirable.
- In general, we cannot expand all these calls,
- so we have to choose the 'best' ones.
- With every CAL instruction
- that may be expanded, we associate
- a \fIpay off\fR,
- which expresses how desirable it is
- to expand this specific CAL.
- .sp
- Let Tc denote the portion of EM text involved
- in a specific call, i.e. the pushing of the actual
- parameter expressions, the CAL itself,
- the popping of the parameters and the
- pushing of the result (if any, via an LFR).
- Let Te denote the EM text that would be obtained
- by expanding the call in line.
- Let Pc be the original program and Pe the program
- with Te substituted for Tc.
- The pay off of the CAL depends on two factors:
- .IP -
- T = execution_time(Pe) - execution_time(Pc)
- .IP -
- S = code_size(Pe) - code_size(Pc)
- .LP
- The change in execution time (T) depends on:
- .IP -
- T1 = execution_time(Te) - execution_time(Tc)
- .IP -
- N = number of times Te or Tc get executed.
- .LP
- We assume that T1 will be the same every
- time the code gets executed.
- This is a reasonable assumption.
- (Note that we are talking about one CAL,
- not about different calls to the same procedure).
- Hence
- .DS
- T = N * T1
- .DE
- T1 can be estimated by a careful analysis
- of the transformations that are performed.
- Below, we list everything that will be
- different when a call is expanded in line:
- .IP -
- The CAL instruction is not executed.
- This saves a subroutine jump.
- .IP -
- The instructions in the procedure prolog
- are not executed.
- These instructions, generated from the PRO pseudo,
- save some machine registers
- (including the old LB), set the new LB and allocate space
- for the locals of the called routine.
- The savings may be less if there are no
- locals to allocate.
- .IP -
- In line parameters are not evaluated before the call
- and are not pushed on the stack.
- .IP -
- All remaining parameters are stored in local variables,
- instead of being pushed on the stack.
- .IP -
- If the number of parameters is nonzero,
- the ASP instruction after the CAL is not executed.
- .IP -
- Every reference to an in line parameter is
- substituted by the parameter expression.
- .IP -
- RET (return) instructions are replaced by
- BRA (branch) instructions.
- If the called procedure 'falls through'
- (i.e. it has only one RET, at the end of its code),
- even the BRA is not needed.
- .IP -
- The LFR (fetch function result) is not executed
- .PP
- Besides these changes, which are caused directly by IL,
- other changes may occur as IL influences other optimization
- techniques, such as Register Allocation and Constant Propagation.
- Our heuristic rules do not take into account the quite
- inpredictable effects on Register Allocation.
- It does, however, favour calls that have numeric \fIconstants\fR
- as parameter; especially the constant "0" as an inline
- parameter gets high scores,
- as further optimizations may often be possible.
- .PP
- It cannot be determined statically how often a CAL instruction gets
- executed.
- We will use \fIloop nesting\fR information here.
- The nesting level of the loop in which
- the CAL appears (if any) will be used as an
- indication for the number of times it gets executed.
- .PP
- Based on all these facts,
- the pay off of a call will be computed.
- The following model was developed empirically.
- Assume procedure P calls procedure Q.
- The call takes place in basic block B.
- .DS
- .TS
- l l l.
- ZP \&= # zero parameters
- CP \&= # constant parameters - ZP
- LN \&= Loop Nesting level (0 if outside any loop)
- F \&= \fIif\fR # formal parameters of Q > 0 \fIthen\fR 1 \fIelse\fR 0
- FT \&= \fIif\fR Q falls through \fIthen\fR 1 \fIelse\fR 0
- S \&= size(Q) - 1 - # inline_parameters - F
- L \&= \fIif\fR # local variables of P > 0 \fIthen\fR 0 \fIelse\fR -1
- A \&= CP + 2 * ZP
- N \&= \fIif\fR LN=0 and P is never called from a loop \fIthen\fR 0 \fIelse\fR (LN+1)**2
- FM \&= \fIif\fR B is a firm block \fIthen\fR 2 \fIelse\fR 1
- pay_off \&= (100/S + FT + F + L + A) * N * FM
- .TE
- .DE
- S stands for the size increase of the program,
- which is slightly less than the size of Q.
- The size of a procedure is taken to be its number
- of (non-pseudo) EM instructions.
- The terms "loop nesting level" and "firm" were defined
- in the chapter on the Intermediate Code (section "loop tables").
- If a call is not inside a loop and the calling procedure
- is itself never called from a loop (transitively),
- then the call will probably be executed at most once.
- Such a call is never expanded in line (its pay off is zero).
- If the calling procedure doesn't have local variables, a penalty (L)
- is introduced, as it will most likely get local variables if the
- call gets expanded.
|