doc/ego/cf/cf5

   1 .NH 2
   2 Interprocedural analysis
   3 .PP
   4 It is often desirable to know the effects
   5 a procedure call may have.
   6 The optimization below is only possible if
   7 we know for sure that the call to P cannot
   8 change A.
   9 .DS
  10 .TS
  11 l l.
  12 A := 10;        A:= 10;
  13 P;  -- procedure call    -->    P;
  14 B := A + 2;     B := 12;
  15 .TE
  16 .DE
  17 Although it is not possible to predict exactly
  18 all the effects a procedure call has, we may
  19 determine a kind of upper bound for it.
  20 So we compute all variables that may be
  21 changed by P, although they need not be
  22 changed at every invocation of P.
  23 We can get hold of this set by just looking
  24 at all assignment (store) instructions
  25 in the body of P.
  26 EM also has a set of \fIindirect\fR assignment
  27 instructions,
  28 i.e. assignment through a pointer variable.
  29 In general, it is not possible to determine
  30 which variable is affected by such an assignment.
  31 In these cases, we just record the fact that P
  32 does an indirect assignment.
  33 Note that this does not mean that all variables
  34 are potentially affected, as the front ends
  35 may generate messages telling that certain
  36 variables can never be accessed indirectly.
  37 We also set a flag if P does a use (load) indirect.
  38 Note that we only have to look at \fIglobal\fR
  39 variables.
  40 If P changes or uses any of its locals,
  41 this has no effect on its environment.
  42 Local variables of a lexically enclosing
  43 procedure can only be accessed indirectly.
  44 .PP
  45 A procedure P may of course call another procedure.
  46 To determine the effects of a call to P,
  47 we also must know the effects of a call to the second procedure.
  48 This second one may call a third one, and so on.
  49 Effectively, we need to compute the \fItransitive closure\fR
  50 of the effects.
  51 To do this, we determine for every procedure
  52 which other procedures it calls.
  53 This set is the "calling" attribute of a procedure.
  54 One may regard all these sets as a conceptual graph,
  55 in which there is an edge from P to Q
  56 if Q is in the calling set of P. This graph will
  57 be referred to as the \fIcall graph\fR.
  58 (Note the resemblance with the control flow graph).
  59 .PP
  60 We can detect which procedures are called by P
  61 by looking at all CAL instructions in its body.
  62 Unfortunately, a procedure may also be
  63 called indirectly, via a CAI instruction.
  64 Yet, only procedures that are used as operand of an LPI
  65 instruction can be called indirect,
  66 because this is the only way to take the address of a procedure.
  67 We determine for every procedure whether it does
  68 a CAI instruction.
  69 We also build a set of all procedures used as
  70 operand of an LPI.
  71 .sp
  72 After all procedures have been processed (i.e. all CFGs
  73 are constructed, all loops are detected,
  74 all procedures are analyzed to see which variables
  75 they may change, which procedures they call,
  76 whether they do a CAI or are used in an LPI) the
  77 transitive closure of all interprocedural
  78 information is computed.
  79 During the same process,
  80 the calling set of every procedure that uses a CAI
  81 is extended with the above mentioned set of all
  82 procedures that can be called indirect.