next up previous
Next: Selective Procedure Cloning. Up: Interprocedural Framework Previous: Interprocedural Framework

Region-Based Flow-Sensitive Analysis.

To capture precise interprocedural information requires a flow-sensitive analysis 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 the procedure is invoked) and from its callees (representing the effects of the invocation). For example, in a straightforward interprocedural adaptation of traditional iterative analysis, analysis might be carried out over a program representation called the supergraph [16], 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 is slow because the number of control flow paths through which information flows increases greatly.

Such analysis also loses precision by propagating information along unrealizable paths [14]; the analysis may propagate calling context information from one caller through a procedure and return the side-effect information to a different caller. In our system, we use a region-based analysis that solves the problems of unrealizable paths and slow convergence. We perform analysis efficiently in two passes over the program.

Saman Amarasinghe
Mon Oct 2 11:00:22 PDT 1995