next up previous
Next: Scalar Data-Flow Analysis Up: Algorithm Previous: Phase 1: Calculating

Phase 2: Deriving Calling Contexts and Computing Final Values.

For a two-phase problem, the second phase of the algorithm derives the data-flow input to each procedure and its subregions. This phase of the analysis is performed top-down over the call graph and from outermost to innermost loops within each procedure body. For a procedure, the analysis derives the set of calling contexts contributed by calls to the procedure. Instead of performing a meet operation over all of the calling contexts, the analysis partitions these contexts into equivalence classes under the relation according to their data-flow information before meeting only the contexts within each equivalence class.

The number of partitions is reduced by first using a to eliminate from the data-flow values information not relevant to the called procedure. (We describe an example of this filtering in Section 4.)

Each partition defines a data-flow input value , the meet of the calling contexts in that partition. For each partition, the analysis applies the transfer functions to this data-flow value to propagate information from outermost to innermost to yield the input to inner regions. For a region R representing a procedure call, the analysis adds to the corresponding call graph edge the calling context . It is important to note that our analysis does not actually generate cloned procedure bodies, but merely replicates their data-flow information for the purposes of analysis.

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