.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