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

Region-Based Flow-Sensitive Analysis.

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 separate passes over the program.

Proceeding bottom-up through the call graph, the first pass analyzes each procedure to obtain a description of its side-effect behavior in the form of a transfer function; the transfer function is in turn inserted at call sites when computing transfer functions of callers. In a second, top-down pass over the call graph, data-flow information from the calling context is applied to these transfer functions to derive the final analysis results for each procedure. We use a similar approach within each procedure, summarizing code region (e.g., loop) behavior during the bottom-up pass and propagating context into each region during the top-down pass.

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