next up previous
Next: Region-Based Flow-Sensitive Analysis. Up: Detecting Coarse-Grain Parallelism Using Previous: Array Reduction Recognition.

Interprocedural Analysis Issues

  Interprocedural data-flow analysis can support interprocedural optimization in a much more space-efficient manner than inlining by analyzing only a single copy of each procedure. To capture precise interprocedural information requires a flow-sensitive approach, which derives analysis results along each possible control flow path through the program. Precise and efficient flow-sensitive interprocedural analysis is difficult because information flows into a procedure both from its callers (representing the calling context in which a procedure is invoked) and from its callees (representing the side effects of the invocations). For example, in a straightforward interprocedural adaptation of traditional iterative analysis, analysis might be carried out over a program representation called the supergraph [22], where individual control flow graphs for the procedures in the program are linked together at procedure call and return points. Iterative analysis over this structure will be slow because the number of control paths through which information flows can be very large. Such analysis also loses precision by propagating information along unrealizable paths [17]; the analysis may propagate calling context information from one caller through a procedure and return the side-effect information to a different caller.

Saman Amarasinghe
Fri Sep 15 09:15:06 PDT 1995