Last updated July 29, 1996.Brian Grant (grant@cs.washington.edu)
One way of tackling the transformation problem is to identify subgraphs of the SCFG that are to be linearized, linearize those subgraphs, and connect them so that the appropriate subgraphs are stitched.
To do this, we group blocks in nested equivalence classes. Blocks with the same reachability conditions are put in the same equivalence class. Thus, new nested equivalence classes are created at static branches and disjunctive merges. A disjunctive merge is one introducing an OR into the reachability conditions.
The blocks in the innermost equivalence classes contain no static branches and so can be linearized by topological sort. Once that is completed, the surrounding equivalence class can be linearized. So, by starting at the innermost nested equivalence classes and working out, the whole graph can be linearized.
A subgraph of a nested equivalence class spawned by a static branch is connected to the subgraph of its parent by the original static branch. Static branches, then, choose between linearized subgraphs at stitch-time.
Subgraphs of disjunctive-merge equivalence classes are connected to the parent graph in different ways. NTBS flags are set on the edges from the original parent nodes. These new nodes are linearized along with the parent nodes. The disjunctive-merge blocks are then appended (in topo. order) to the subgraph of the parent equivalence class of all of the parent nodes.
The following diagram shows a CFG with two constant disjunctive merges.
ENTRY
|
1
|
S1
/ \
2 3
| |
S2 S3
/ \ / \
4 5 6 7
\ \ / /
\ 8 /
\ / /
9 /
\ /
10
|
EXIT
The following tree shows the nested equivalence classes for this CFG. Blocks within parentheses are in the same equivalence class, and children in the tree are in nested equivalence classes.
(ENTRY,1,10,EXIT)
| \_ \_
S1 \_ \_
t/ \f \w \w
(2) (3) (8)(9)
| |
S2 S3
t/ \f t/ \f
(4) (5) (6) (7)
From this equivalence-class tree, we construct the following CFG.
ENTRY
|
1
|
S1
/ \
2 3
| |
S2 S3
/ \ / \
4 5 6 7
| | | |
9NS 8NS 8NS |
\ / \ /
\/ \/
\ /
\ /
\ /
10
|
8NS?
/|
8 |
| |
9NS |
\|
9NS?
/|
9 |
\ |
\|
EXIT
So, all blocks are stitched that need to be. Since we don't want blocks 8 and 9 to be stitched unnecessarily, we set need-to-be-stitched flags for the blocks on the edges from blocks 4, 5, and 6 and check those flags before the blocks are stitched.
How does this relate to control-dependence trees? Reachability conditions are a type of control-dependence information, where we are only concerned about dependence upon static branches. Building the nested equivalence classes based on reachability conditions is very similar to insertion of region nodes into the control-dependence subgraph. The region nodes become the parents of nodes with the same control dependencies and children of nodes with fewer dependencies. The main difference in the two approaches is in the handling of disjunctive merges and back edges.
Last updated July 29, 1996.