12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182 |
- .NH 2
- Interprocedural analysis
- .PP
- It is often desirable to know the effects
- a procedure call may have.
- The optimization below is only possible if
- we know for sure that the call to P cannot
- change A.
- .DS
- .TS
- l l.
- A := 10; A:= 10;
- P; -- procedure call --> P;
- B := A + 2; B := 12;
- .TE
- .DE
- Although it is not possible to predict exactly
- all the effects a procedure call has, we may
- determine a kind of upper bound for it.
- So we compute all variables that may be
- changed by P, although they need not be
- changed at every invocation of P.
- We can get hold of this set by just looking
- at all assignment (store) instructions
- in the body of P.
- EM also has a set of \fIindirect\fR assignment
- instructions,
- i.e. assignment through a pointer variable.
- In general, it is not possible to determine
- which variable is affected by such an assignment.
- In these cases, we just record the fact that P
- does an indirect assignment.
- Note that this does not mean that all variables
- are potentially affected, as the front ends
- may generate messages telling that certain
- variables can never be accessed indirectly.
- We also set a flag if P does a use (load) indirect.
- Note that we only have to look at \fIglobal\fR
- variables.
- If P changes or uses any of its locals,
- this has no effect on its environment.
- Local variables of a lexically enclosing
- procedure can only be accessed indirectly.
- .PP
- A procedure P may of course call another procedure.
- To determine the effects of a call to P,
- we also must know the effects of a call to the second procedure.
- This second one may call a third one, and so on.
- Effectively, we need to compute the \fItransitive closure\fR
- of the effects.
- To do this, we determine for every procedure
- which other procedures it calls.
- This set is the "calling" attribute of a procedure.
- One may regard all these sets as a conceptual graph,
- in which there is an edge from P to Q
- if Q is in the calling set of P. This graph will
- be referred to as the \fIcall graph\fR.
- (Note the resemblance with the control flow graph).
- .PP
- We can detect which procedures are called by P
- by looking at all CAL instructions in its body.
- Unfortunately, a procedure may also be
- called indirectly, via a CAI instruction.
- Yet, only procedures that are used as operand of an LPI
- instruction can be called indirect,
- because this is the only way to take the address of a procedure.
- We determine for every procedure whether it does
- a CAI instruction.
- We also build a set of all procedures used as
- operand of an LPI.
- .sp
- After all procedures have been processed (i.e. all CFGs
- are constructed, all loops are detected,
- all procedures are analyzed to see which variables
- they may change, which procedures they call,
- whether they do a CAI or are used in an LPI) the
- transitive closure of all interprocedural
- information is computed.
- During the same process,
- the calling set of every procedure that uses a CAI
- is extended with the above mentioned set of all
- procedures that can be called indirect.
|