Back Edges and Predecessors

Classification of Edges

In the depth-first-search (DFS) traversal, a merge node is traversed the first time it is reached and the algorithm must backtrack on all subsequent visits. This is, in a sense, the opposite of the depth-first topological traversal, in which a merge node is only traversed once it is reached from the last parent to be traversed.

However, I will sometimes use DFS edge-classification terminology. In particular, I will identify back edges using DFS. Multiflow calls such edges quasi back edges. Back edges extend from a loop tail to a loop head, and must be eliminated before (or ignored while) performing a topological traversal. The edge classifications tree, forward, and cross have no particular significance in a CFG.

Nodes are added to the DFS tree as the CFG is traversed. A tree edge is an edge to a node not yet in the DFS tree (the first edge to a block). A forward edge is an edge to a successor in the DFS tree. A back edge is an edge to a predecessor in the DFS tree. A cross edge is an edge to a node that is neither a successor or predecessor in the DFS tree.

Identifying predecessors in the CFG

The ability to quickly determine if one block is the predecessor of another is used in all of the proposed algorithms, including the splitting-and-merging algorithm. The check can be reduce to constant time by precomputing some information on the graph.

1. Identify back edges using DFS, and mark them.
2. Perform a depth-first topological traversal, ignoring back edges, and count the nodes as they are visited. These counts are the topological numbers and will also serve as begin_times.
3. Reverse all edges except the back edges, which are still ignored, and continue counting from the bottom of the CFG to the top. These counts are the end_times. The bottom of the CFG will have end_time = begin_time + 1.

If the (begin_time, end_time) range of one node is completely contained within the range of another node, the first node is a successor of the second in the original CFG.

Last updated July 29, 1996.
Brian Grant (grant@cs.washington.edu)