Intervals and Derived Graphs

Theorem: There is a unique partition of a program flow graph into intervals.

After a program graph has been partitioned into intervals, a derived graph ( I, &Gamma _I) can be formed as follows:

• Nodes of the derived graph are the intervals of the original graph.

• Transitions of the derived graph are transitions between nodes of intervals of the original graph.
  &Gamma _I = { (I_i, I_j) | &exist x &isin I_i &exist y &isin I_j (x, y) &isin &Gamma }
  where i &ne j . Note that a transition can only be to the head node of an interval.

The process of making derived graphs is continued until a single node is reached. Some graphs are irreducible; these are rare in practice and can be handled by making an artificial duplicate of a node.

Contents    Page-10    Prev    Next    Page+10    Index