Last updated July 29, 1996.Brian Grant (grant@cs.washington.edu)
The Solution
-- Linearize the graph with a modified topological sort
-- Don't serialize mutually exclusive paths
-- Redirect loop entries to loop heads
-- If a node might not be stitched, go back to it where the
predecessor before successor rules would otherwise be
violated
-- Include back edges for unrolled loops
The Algorithm
1) Peel 1st iteration off unrolled loops
2) Compute for each loop-entry edge the head of the outermost
loop entered
3) Remove back edges from the graph
4) Insert empty nodes on all non-last edges into nonconstant
merges
5) Redirect each loop-entry to the head of the outermost loop
entered
6) Recompute reachability conditions
7) Compute graph predecessors
8) Copy the nodes to a duplicate graph
9) Invoke the recursive transformation routine on the entry
node of the graph
10) Add the back edges corresponding to unrolled loops to the
duplicate graph
Since we're traversing the SCFG and making modifications as we go
along, we maintain two graphs for sanity (traverse the original and
build a duplicate).
By passing another parameter to transform(), we could eliminate the
BACK_STACK, but it would complicate the code.
The topological traversal defines a unique order on the edges (by the
topological numbers of the edge destinations).
Notation
--------
NTBS_LIST is a sorted list of nodes
NTBS is need to be stitched
HBS is has been stitched
RC is reachability conditions (modified)
ME is mutually exclusive
is_predecessor(A, B) is true if A is a predecessor of B or A == B
SCFG2 is a duplicate CFG, initially containing duplicates of all the
nodes, but no edges.
The Algorithm
-------------
1) Peel off the first iteration of every one-way unrolled loop. This
makes stitching of unrolled loops with multiple entries more efficient
and any unnecessarily generated code will be eliminated.
2) Find all loops and annotate each loop-entry edge with the head of
the outermost loop it enters.
3) Remove back edges from SCFG.
4) Redirect each loop-entry edge to point to the head of the outermost
loop entered.
5) Insert empty nodes into the SCFG on all edges from dynamic
branches. This prevents redirection of the first edge from a dynamic
branch, and prevents redirection to edges that will later themselves
be redirected (edges from dynamic branches into nonconstant merges).
It also ensures that the destination of each edge from a dynamic
branch has only one incoming edge.
6) Recompute reachability conditions.
7) Compute SCFG predecessors.
8) Copy the nodes of SCFG to SCFG2.
9) Start the recursive transformation and topological traversal by
calling transform(SCFG->entrynode).
10) Add back edges corresponding to loops to be unrolled to SCFG2.
Invariants on the SCFG when transform is called:
-- No back edges
-- Edges from dynamic branches don't go into merges
transform(node) {
/* if we're done, quit */
if node == SCFG->exitnode {
return
}
if ends_in_dynamic_branch(node) {
/* Push the destinations of dynamic edges onto the
stack so that we can redirect edges into
nonconstant merges to them. We want the edges to
be popped from BACK_STACK in the same order in
which they are traversed. We don't redirect to
edges emanating from static branches because:
-- If we're redirecting, the RC of the edge
are not ME with those of the last edge into
a nonconstant merge.
-- So, there must be an edge from a dynamic
branch that leads to the path from which
the last edge comes.
-- The RC of the next edge from a static
branch to be traversed must be ME with
those of the redirected edge, and only one
of the two paths should be stitched.
*/
for each outgoing edge node->e[i] (in reverse order) {
push(BACK_STACK, node->e[i]->dest)
}
}
/* Recursively invoke transform() on graph successors,
backtracking at non-last edges into merges.
*/
for each outgoing edge node->e[i] {
/* Remove the current edge from the stack so the top
of the stack is the next dynamic edge we're going
to handle.
*/
if ends_in_dynamic_branch(node) {
assert(node->e[i]->dest == peek(BACK_STACK))
pop(BACK_STACK)
}
/* Case 1: edge is only incoming edge (not a merge)
Simply move down the graph.
*/
/* If the edge destination is not a merge, then go to
that node.
*/
if (not is_merge(node->e[i]->dest) {
/* For dynamic branches, add only the first
edge to the new graph. The other branch
destinations will be strung together. All
singleton edges and edges from static
branches may be added.
*/
if (not ends_in_dynamic_branch(node)) or
(ends_in_dynamic_branch(node) and
node->e[i] is the first edge from node) {
Add edge node->e[i] to SCFG2
}
transform(node->e[i]->dest)
}
/* Case 2: last edge into a merge, an edge into a constant
merge, or an edge into a nonconstant merge where the RC of
the current edge are ME with those of the last edge
Insert checks to go back if necessary and move down the
graph if it's the last edge.
*/
/* we know the edge destination is a merge */
/* If the edge is the last edge or its reachability
conditions are mutually exclusive with those of the
last edge, we're going to stitch the merge next.
So, if the merge is a nonconstant merge, check if
we need to insert checks to go back and stitch any
blocks to preserve topological order. At a
constant merge (this case catches all constant
merges), there won't be any blocks to go back and
stitch.
*/
else if (node->e[i] == node->e[i]->dest->last_in_edge)
or ( RC(node->e[i]) ME RC(node->e[i]->dest->last_in_edge) ) {
if is_nonconstant_merge(node->e[i]->dest) {
/* Merges in the NTBS_LIST will be tested
in ascending order by their begin
times. This ensures that no merge
will be checked before a
predecessor. That is necessary to
ensure that we don't stitch the same
part of the graph twice. The
NTBS_LIST is actually in
descending order and we insert the
checks backwards.
We may also be able to use the
ordering to optimize this loop.
*/
v = node->e[i]->dest
for every node n in NTBS_LIST {
/* We need to insert a check
to go back to a merge if
the destination of the
current edge is a successor
of a merge in NTBS_LIST,
but the source of the edge
is not. If the source is
also a successor, we are
guaranteed the merge to
check has already been
stitched due to the strict
topological ordering,
making the check unnecessary.
*/
if is_predecessor(n,
node->e[i]->dest) && (not
is_predecessor(n, node)) {
Add subgraph u
"if (n NTBS && !(n HBS)),
then goto n, else goto v"
to SCFG2
v = u
}
}
/* Connect node to the string of
checks anchored to
node->e[i]->dest.
*/
Add edge (node, v) to SCFG2
}
else {
/* No checks are necessary, so just
add the edge.
*/
Add edge node->e[i] to SCFG2
}
/* If the edge is the last edge into a merge,
then go to that node. If the edge is not
the last edge into the merge, then we need
to backtrack.
*/
if (node->e[i] == node->e[i]->dest->last_in_edge) {
transform(node->e[i]->dest)
}
}
/* Case 3: non-last edge into a nonconstant merge
Redirect the edge and determine whether we might need to
come back to the merge or not.
*/
/* we know the edge destination is a nonconstant merge */
/* we know the edge is not the last edge into the
merge, so we're going to backtrack */
/* we know the reachability conditions of the edge
are not mutually exclusive with those of the last
edge, so we're going to redirect */
/* we know the edge is a singleton edge or an edge
from a static branch */
/* If the reachability conditions of the current edge
are not mutually exclusive with those of the last
edge (includes most edges at nonconstant merges),
then redirect the edge and check whether the last
edge might not be traversed.
*/
else {
/* If reachability conditions of the current
edge imply those of all remaining incoming
edges (the last edge and all edges whose
reachability conditions are mutually
exclusive with those of the last edge),
then we know we will reach the merge again
and no check is needed. Otherwise, insert
the check.
*/
rc_remaining_edges = RC(node->e[i]->dest->last_in_edge)
for each incoming edge node->e[i]->dest->ie[j] {
if ( RC(node->e[i]->dest->ie[j]) ME
RC(node->e[i]->dest->last_in_edge) ) {
rc_remaining_edges =
rc_remaining_edges or
RC(node->e[i]->dest->ie[j])
}
}
if ( rc_remaining_edges && RC(node->e[i]) ) !=
RC(node->e[i]) {
/* The remaining edges might not be
traversed, so insert a need-to-
be-stitched flag and add the merge
to the set of nodes to go back and
check.
*/
assert(is_a_cross_edge(
node->e[i]->dest->last_in_edge))
Add node n
"set NTBS flag for node->e[i]->dest"
to SCFG2
Add edge (node, n) to SCFG2
v = n
Insert "set HBS flag for node
node->e[i]->dest" in node
node->e[i]->dest, if it is not there
already
Insert node->e[i]->dest into NTBS_LIST
(begin times in descending order)
}
else {
v = node
}
/* If we could have backtracked from the
merge, we're going to want to skip back to
it.
*/
backtrack = false
for every node n in NTBS_LIST {
if is_predecessor(n, node) && (not
is_predecessor(n,
node->e[i]->dest->last_in_edge)) {
backtrack = true
break
}
}
/* If we don't want to go straight back to the
merge, go to the redirected location.
*/
if backtrack {
Add subgraph u
"if peek(BACK_STACK) HBS,
then goto node->e[i]->dest,
else goto peek(BACK_STACK)"
to SCFG2
Add edge (v, u) to SCFG2
Insert "set HBS flag for node
peek(BACK_STACK)" in node
peek(BACK_STACK), if it is not there
already
}
else {
Add edge (v, peek(BACK_STACK)) to SCFG2
}
}
}
return
}
Last updated July 29, 1996.