next up previous
Next: Phase 2: Deriving Up: Algorithm Previous: Algorithm

Phase 1: Calculating Region Transfer Functions

For each region R from innermost loop to outermost loop, and from bottom to top in the call graph, we compute its transfer function . A basic block's transfer function is derived directly (using the function). The transfer function of a procedure call takes the procedure body's transfer function and maps it to the caller space, renaming variables in its representation (using the operation).

The transfer function for a loop applies the Iteration operation to the transfer function of its loop body to obtain a transfer function representing the effect of i iterations of the body, where i is the loop's normalized index variable. The final transfer function showing the total effect of the loop is obtained by using the Closure operation to eliminate the iteration counter i.

For loop bodies and procedure bodies, deriving the transfer function involves the transfer functions of its immediate subregions. In a forward data-flow problem, for each subregion , we compute , the transfer function from the entry of R to the entry of . This calculation results from a meet over the predecessors of . If the immediate subregions graph is cyclic, then an iterative solution may be required to find the transfer function. Otherwise, the subregions are simply visited in the appropriate (reverse postorder) order within the region. The final transfer function for the loop body or procedure body is derived by composing the transfer function for the subregion that represents the exit from region R, with the transfer function of that region.

Data-flow problems that require a backward propagation within the intervals are analogous. For an acyclic subregion graph, a postorder traversal over the subregions derives transfer functions to describe the effects from the exit of R up to the exit of .



next up previous
Next: Phase 2: Deriving Up: Algorithm Previous: Algorithm



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