cf5 2.9 KB

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