Last updated August 6, 1996.Brian Grant (grant@cs.washington.edu)
Can we preserve "structured" subgraphs? Can we preserve subgraphs beginning at static branches?
Suppose we want to preserve "structured subgraphs" during the graph transformation. Can we identify the underlying structure in a CFG with a few stray "unstructured edges"? To do that, we would need definitions of "structured" and "unstructured".
One possible definition of structured code is code containing only looping and decision constructs that are strictly nested, with no short cuts or gotos. However, most C code contains simple forms of unstructure:
Ideally, we should be able to handle these common forms of unstructure as efficiently as perfectly structured code. Can we come up with more lenient definitions of "structured subgraphs" that include these cases?
Unfortunately, isolating the "unstructuredness" of a CFG is very difficult. One characteristic of a node in the graph we could use to locate "unstructuredness" is whether a new OR is introduced into the reachability conditions at a merge. We call merges with new ORs introduced into the reachability conditions disjunctive merges.
Let's look at how we would want to transform some simple graphs with a little unstructuredness.
Study the following diagram of a CFG. Assume S is a static branch, and Z is "the sky" (an edge from some unspecified place in the CFG).
| |
S Z
/ \ /
A B
\ /
M
|
Why can't we leave edges SB, AM, and BM intact and place a test (does B need to be stitched?) on edge ZB? The main impediment to leaving those edges intact is identifying that there is something special about the nonconstant merges B and M, that treatment of the edge ZB should be delayed. The merge at B may not even be a disjunctive merge, such as in the following example.
Here is a more concrete example (D dynamic, S static):
if (D && S)
{A}
else
{B}
{M}
This code translates to the following CFG:
|
D
/ \
S | B and M are nonconstant,
/ \ / but not disjunctive
A B
\ /
M
|
The reachability conditions at B and M are the same as those at D, so we always want to eagerly stitch B, but only want to stitch A if S is true. So, we want to create the following CFG:
|
D
|
S
/|
A |
\|
B
|
M
|
Here are some similar examples (S denotes static branch, D dynamic):
| |
S S
/ \ / \
D | D |
/ \ / transformed -> | / B is constant
A B A / M is nonconstant
\ / |/
M B
| |
M
| |
D1
/ \
D2 |
/ \ / transformed -> -D1-D2-A-B-M-
A B B and M are nonconstant
\ / merges with identical
M reachability conditions
| on all incoming edges
|
S1
/ \
S2 |
/ \ / transformed -> unchanged
A B B and M constant
\ / B is disjunctive
M
|
So, because of the difficulty in deciding where to pass by certain edges and because of the difficulties created by passing by edges and violating the topological order (either gosub or code duplication is required), I'm not going to try to preserve any particular underlying structure in the graph when restructuring it for stitching.
Last updated August 6, 1996.