123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164 |
- .NH 2
- Feasibility and desirability analysis
- .PP
- Feasibility and desirability analysis
- of in line substitution differ
- somewhat from most other techniques.
- Usually, much effort is needed to find
- a feasible opportunity for optimization
- (e.g. a redundant subexpression).
- Desirability analysis then checks
- if it is really advantageous to do
- the optimization.
- For IL, opportunities are easy to find.
- To see if an in line expansion is
- desirable will not be hard either.
- Yet, the main problem is to find the most
- desirable ones.
- We will deal with this problem later and
- we will first attend feasibility and
- desirability analysis.
- .PP
- There are several reasons why a procedure invocation
- cannot or should not be expanded in line.
- .sp
- A call to a procedure P cannot be expanded in line
- in any of the following cases:
- .IP 1. 3
- The body of P is not available as EM text.
- Clearly, there is no way to do the substitution.
- .IP 2.
- P, or any procedure called by P (transitively),
- follows the chain of statically enclosing
- procedures (via a LXL or LXA instruction)
- or follows the chain of dynamically enclosing
- procedures (via a DCH).
- If the call were expanded in line,
- one level would be removed from the chains,
- leading to total chaos.
- This chaos could be solved by patching up
- every LXL, LXA or DCH in all procedures
- that could be part of the chains,
- but this is hard to implement.
- .IP 3.
- P, or any procedure called by P (transitively),
- calls a procedure whose body is not
- available as EM text.
- The unknown procedure may use an LXL, LXA or DCH.
- However, in several languages a separately
- compiled procedure has no access to the
- static or dynamic chain.
- In this case
- this point does not apply.
- .IP 4.
- P, or any procedure called by P (transitively),
- uses the LPB instruction, which converts a
- local base to an argument base;
- as the locals and parameters are stored
- in a non-standard way (differing from the
- normal EM calling sequence) this instruction
- would yield incorrect results.
- .IP 5.
- The total number of bytes of the parameters
- of P is not known.
- P may be a procedure with a variable number
- of parameters or may have an array of dynamic size
- as value parameter.
- .LP
- It is undesirable to expand a call to a procedure P in line
- in any of the following cases:
- .IP 1. 3
- P is large, i.e. the number of EM instructions
- of P exceeds some threshold.
- The expanded code would be large too.
- Furthermore, several programs in ACK,
- including the global optimizer itself,
- may run out of memory if they they have to run
- in a small address space and are provided
- very large procedures.
- The threshold may be set to infinite,
- in which case this point does not apply.
- .IP 2.
- P has many local variables.
- All these variables would have to be allocated
- in the stack frame of the calling procedure.
- .PP
- If a call may be expanded in line, we have to
- decide how to access its parameters.
- In the previous section we stated that we would
- use in line parameters whenever possible and desirable.
- There are several reasons why a parameter
- cannot or should not be expanded in line.
- .sp
- No parameter of a procedure P can be expanded in line,
- in any of the following cases:
- .IP 1. 3
- P, or any procedure called by P (transitively),
- does a store-indirect or a use-indirect (i.e. through
- a pointer).
- However, if the front-end has generated messages
- telling that certain parameters can not be accessed
- indirectly, those parameters may be expanded in line.
- .IP 2.
- P, or any procedure called by P (transitively),
- calls a procedure whose body is not available as EM text.
- The unknown procedure may do a store-indirect
- or a use-indirect.
- However, the same remark about front-end messages
- as for 1. holds here.
- .IP 3.
- The address of a parameter location is taken (via a LAL).
- In the normal calling sequence, all parameters
- are stored sequentially. If the address of one
- parameter location is taken, the address of any
- other parameter location can be computed from it.
- Hence we must put every parameter in a temporary location;
- furthermore, all these locations must be in
- the same order as for the normal calling sequence.
- .IP 4.
- P has overlapping parameters; for example, it uses
- the parameter at offset 10 both as a 2 byte and as a 4 byte
- parameter.
- Such code may be produced by the front ends if
- the formal parameter is of some record type
- with variants.
- .PP
- Sometimes a specific parameter must not be expanded in line.
- .sp 0
- An actual parameter expression cannot be expanded in line
- in any of the following cases:
- .IP 1. 3
- P stores into the parameter location.
- Even if the actual parameter expression is a simple
- variable, it is incorrect to change the 'store into
- formal' into a 'store into actual', because of
- the parameter mechanism used.
- In Pascal, the following expansion is incorrect:
- .DS
- procedure p (x:integer);
- begin
- x := 20;
- end;
- \&...
- a := 10; \kxa := 10;
- p(a); ---> \h'|\nxu'a := 20;
- write(a); \h'|\nxu'write(a);
- .DE
- .IP 2.
- P changes any of the operands of the
- actual parameter expression.
- If the expression is expanded and evaluated
- after the operand has been changed,
- the wrong value will be used.
- .IP 3.
- The actual parameter expression has side effects.
- It must be evaluated only once,
- at the place of the call.
- .LP
- It is undesirable to expand an actual parameter in line
- in the following case:
- .IP 1. 3
- The parameter is used more than once
- (dynamically) and the actual parameter expression
- is not just a simple variable or constant.
- .LP
|