next up previous
Next: Analysis of Array Up: Scalar Parallelization Analysis Previous: Scalar Parallelization Analysis

Live Variable Analysis.

We solve a standard live-variable problem interprocedurally through a two-phase region-based backward analysis. In Phase 1, the transfer function for each region is computed as a pair of sets: Gen set, containing variables with upwards exposed reads in the region, and Kill set, containing variables written in the region. In Phase 2, the set of live variables on entry to a region is determined from the set of live variables on exit of the region: .

For loops containing returns and breaks, the situation is somewhat complicated, since there is not just a single exit. A single transfer function is not sufficient to describe the behavior of a region with multiple exits in a backward data-flow problem. Instead, we summarize the behavior of a loop body by three transfer functions---from loop body exit, from loop exit, and from enclosing procedure exit. A loop is described by just two transfer functions---from loop exit and from procedure exit. A single transfer function still suffices to describe a procedure. In other respects the analysis is straightforward.

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