next up previous
Next: Data-Flow Functions Up: Interprocedural Framework Previous: Selective Procedure Cloning.

The Region Graph

The region-based analysis aggregates information at the boundaries of program regions: basic blocks, loop bodies and loops (restricted to DO loops), procedure calls, procedure bodies, and procedures. We use a program representation called the region graph to represent the loop nesting and procedure nesting of the program. The region graph is a directed graph whose nodes represent regions and whose edges represent nesting relationships. With each region is associated an immediate subregions graph, a directed flow graph consisting of immediately nested regions and control flow edges between them.

Each region has a single entry node. To simplify presentation, we primarily describe analyses with regions that also have a single exit. (The actual analysis framework implementation is more general. Irreducible graphs are supported in the scalar data-flow analysis described in Section 4, although the array analysis approximates when graphs are irreducible or when loops contain multiple exits.)

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