BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1365
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Finding Regions Fast: Single Entry Single Exit and Control Regions 
        in Linear Time
AUTHOR:: Johnson, Richard C.
AUTHOR:: Pearson, David 
AUTHOR:: Pingali, Keshav
DATE:: July 1993
PAGES:: 18
ABSTRACT::
Many compilation problems require computing the control dependence 
equivalence relation which divides nodes in a control flow graph into 
equivalence classes such that nodes are in the same class if and only if they 
have the same set of control dependences. In this paper, we show that this 
relation can be computed in $O(E)$ time by reducing it to a naturally stated 
graph problem: in a strongly connected component, divide nodes into 
equivalence classes such that every cycle passes through all or none of the 
nodes in an equivalence class. Our algorithm does not require the computation 
of the control dependence relation or of the postdominator relation - in 
fact, it runs faster in practice than the best algorithms for either of these 
problems. We also show that our algorithm can be used to determine the single 
entry single exit regions of a control flow graph in $O(E)$ time.
END:: CORNELLCS//TR93-1365
BODY::
Finding Regions Fast:
Single Entry Single Exit and
Control Regions in Linear Time*
Richard Johnson
David Pearson
Keshav Pingali
TR 93-1365
July 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*This research was supported by an NSF Presidential Young Investigator award
CCR-8958543, NSF grant CCR-9008526, ONR grant N00014-93-1-0103, and a grant
from Hewlett-Packard Corporation. David Pearson is supported by a Fannie and John
Hertz Fellowship.
Finding Regions Fast:
Single Entry Single Exit and Control Regions
in Linear Time
Richard Johnson			David Pearson			Keshav Pingati
Department of Computer Science
Cornell University, Ithaca, NY 1?853
Report # CTC93TRl4l
July 1993
Abstract
Many compilation problems require computing the controi dependence equivalence relation which divides
nodes in a control flow graph into equivalence classes such that nodes are in the same class if and only if
they have the same set of control dependences. In this paper, we show that this relation can he computed
in 0(E) time by reducing it to a naturally stated graph problem: in a strongly connected component,
divide nodes into equivalence classes such that every cycle passes through all or none of the nodes in an
equivalence class. 0ur algorithm does not require the computation of the control dependence relation or
of the postdominator relation in fact, it runs faster in practice than the best algoritlims for either of
these problems. We also show that our algorithm can be used to determine the single entry single exit
regions of a control flow graph in 0(E) time.
1 Introduction
The notion of control dependence plays an important role in optimization and parallelization. Intuitively, a
node n is control dependent on a node c if c determines whether n is executed. For example, in a conditional
statement, statements on the true and false sides of the conditional are control dependent on the predicate.
Since statements from different sides are control dependent on the predicate in a complementary sense, it is
useful to associate a direction with control dependence; for example, we can say that statements on the true
side of a conditional statement are control dependent on the predicate in the true direction. In the presence
of nested control structures, multiway branches and unstructured flow of control, intuition is an unreliahle
guide and it is better to rely on a formal, graph theoretic notion of control dependence defined as follo'vs.
Definition 1 A control flow graph G is a graph with distinguished nodes START and END such that every
node is reachable from START and END is reachable from every node in G. START has no predecessors and
END has no successors.
To simplify the discussion, we will follow standard practice and assume that there is an edge from START
directly to END in the control flow graph.
Definition 2 A node p is said to postdominate a node n if every path from n to END contains p.
1This research was supported by an NSF Presidential Young Investigator award CCR?s958543, NSF grant CCR-9008526,
0NR grant NOo014-931?o1o3, and a grant from Hewlett-Packard Corporation. David Pearson is supported by a Fannie and
John Hertz Fellowship.
START
END
Node Control Dependences
a START a 1
b ? a?b,f?eb 1
c fsTART?a,f?b1
d tc?d1
e			f c			e 1
f			f START			a, f			b 1
CD ffa1,?b1,?c,f1,td1,fe11
Figure 1: A Program and its Control Dependences
By convention, a node postdominates itself. Control dependence can now be defined as follows [FO\V87j:
Definition 3 A node n is said to be control dependent on node c with direction i if there is a path from
c to n beginning with edge t such that
1. n postdominates ati nodes other than c on this path, and
2. if n and c are distinct nodes, n does not postdominate c.
Although a control dependence is usually written as a tuple consisting of a node and a direction, the
node is simply the source of the direction edge, so we will often leave the node implicit in our presentation.
In the worst-case, the control dependence relationship can have size O(NE), where N and E are the number
of nodes and edges respectively in the control flow graph. Figure 1 shows a small irreducible program and
the control dependences of its nodes.
In many applications, the full control dependence relation is not needed instead, we only want to know
if two nodes have the same set of control dependences. One such application, discussed in more detail in
Section 5, is the determination of single entry single exit (SESE) regions of a control flow graph, which in
turn can be used to build the dependence flow graph or SSA form of a program [JP93j. These representations
permit efficient optimization of programs. Another application of the control dependence equivalence relation
is in global scheduling of instructions for pipelined machines [GS87]. Techniques for basic block scheduling
can be extended immediately to a set of basic blocks with identical control dependences, since all instructions
in such a set can be pooled together and scheduled subject only to data dependences. This increases the
scope of the scheduling beyond basic blocks without introducing the complications of speculative execution.
Our goal then is to divide nodes into equivalence classes in which two nodes are in the same class if and
only if they have the same set of control dependences. These equivalence classes have been called control
dependence regions in the literature [FOW87]. In Figure 1, nodes c and f are in the same region, while all
the other nodes are in regions containing only themselves. Note also that nodes c and f enclose a SESE
region. We will use CD to stand for the control dependence equivalence relation.
Cytron, Ferrante, and Sarkar [CFS90] gave an O(EN) time, O(E + N) space algorithm for computing
CD--H . Briefly, this algorithm works by placing all nodes in a single equivalence class and then repeatedly
reflning the equivalence relation by considering the effect of each control dependence on the existing partition.
In the worst-case, the algorithm performs 0(N) work for each of 0(E) control dependences. The prohlem
with this approach is that CD is defined in terms of the control dependence relation, whid? is O(EN) size
in the worst-case.
In this paper, we show how to compute CD in 0(E) time. To accomplish this, we reduce the problem
to one of computing a simple graph property that we call c?cte equivatence: two nodes are cycle equivalent
2
in a strongly connected component iff for all cycles C, either C contains both nodes or neither node. In this
paper, we describe a simple linear time algorithm based on depth-first search for solving the cycle equivalence
problem, thereby constructing the CD relation in linear time2. Ball [Bal92] has also recognized the need to
characterize CD= without using control dependence and has developed a linear time algorithm for computing
CD= . However, his algorithm works only for reducible graphs, and requires computation of both dominators
and postdominators. We will show in Section 4 that computing just dominators or postdominators takes
longer than computing CD using our algorithm.
The rest of the paper is organized as follows. In Section 2, we reduce the problem of computing CD--H
to that of cycle equivalence. In Section 3, we reduce the cycle equivalence problem in directed graphs to an
equivalent problem in undirected graphs. The main motivation for this reduction is that depth-first search
algorithms in undirected graphs are simpler than those in directed graphs since there are no cross edges
or forward edges to consider in the case of undirected graphs. In Section 4, we give a simple algorithm
based on depth-first search for solving the cycle equivalence problem in undirected graphs. We also present
experimental results that show that our algorithm for CD= is faster than computing postdominance, the
first step of previous algorithms for control dependence and control dependence equivalence. In Section 5,
we show how CD= can be used to determine the single entry single regions of a control flow graph in 0(E)
time. Section 6 concludes the paper with a list of open problems related to this work.
2 Control dependence equivalence is cycle equivalence
In this section, we define cycle equivalence formally and show that the problem of control dependence
equivalence can be reduced to cycle equivalence.
Definition 4 In a graph G, two nodes are cycle equivalent if they occur in the same set of cycles.
Viewed as a binary relation on nodes, it is clear that the relation is reflexive, symmetric and transitive.
We will call the equivalence relation CYC_ . Note that cycle equivalence is defined for both directed and
undirected graphs. To reduce CD to CYC--H we need the following lemma.
Lemma 1 Let a, b and p be nodes in G where b is distinct from a and p. Suppose that a is control dependent
on node p with direction 1 but b is not. Then there must be a path p $ a that does not contain b.
Proof: Let f be the destination of edge I. If f is a itself, the result is established.
Otherwise, f, a and b are distinct nodes. Suppose every path from f to a passes through b. We
show that this implies that b is control dependent on node p with direction 1, leading to a contra-
diction. Since a postdominates f, every path f $ END can be written as f $ a $ END, which
in turn can be written as f $ b $ a $ END because every path from f to a passes through b.
Therefore, b postdominates f. Moreover, this implies that a postdominates b; since a does not
postdominate p, this means b does not postdominate p. Therefore, b is control dependent on
which is incorrect. Therefore, there must be a path p $ a that does not pass through b. c
We now prove the key result that reduces CD to CYC_
Theorem 1 Let 5 be the strongly connected component constructed by adding an edge END START to a
control flow graph G . Nodes a, b in G have the same set of control dependences iff a, b are cycle equivalent
in 5.
2This algorithin was sketched in an e&lier paper [JP93l but there was not enough room in the margin for a complete
description and proof.
3
Proof: (by contradiction)
1. We show that if there is a cycle in S containing a but not b, then a and b do not have the
same control dependences. This is done by showing that any such cycle must contain a node
p (possibly a itself) such that a is control dependent on p, but b is not.
If a postdominates all nodes on the cycle, then there must be a path a A END that does
not pass through any of the nodes in the cycle other than a, and a is control dependent on
itself with some sense 1 where I, the destination of edge 1, is on the cycle. If a does not
postdominate all nodes on the cycle, there must be a node p distinct from a such that a
does not postdominate p but a postdominates all nodes in the cycle strictly hetween p and
a (trace backwards from a in the cycle to find such a node). Then a is control dependent
on p with some sense I where f, the destination of edge 1, is on the cycle.
For b to have the same control dependence, 6 must postdominate f. The portion of the
cycle f A p can be extended with any path pA END to give a path from f to END. Since 6
is not on the cycle, it follows that 6 must occur on every path p A END; so 6 postdominates
p and cannot be control dependent on p.
We conclude that if a and 6 have the same control dependences in 0, they are cycle eciuivalent
in S.
2. We show that if a and 6 do not have the same set of control dependences, then there must
be a cycle passing through one that does not pass through the other. Suppose a is control
dependent on p with direction I but 6 is not. Let f be the destination of edge I. There are
four cases.
(a) a dominates p, 6 dominates p. Note that 6 and p or a and p may be the same node.
If there is some path (possibly empty) from a to p that does not contain 6, & is distinct
from a and p, and by Lemma 1, we have a cycle a A p A A containing a but not 6.
Otherwise, every path from a to p contains 6. Therefore, a dominates 6 and there is a
path START a that does not pass through 6. 6 cannot postdominate a; otherwise, 6
would be control dependent on p with direction 1. Therefore, there is a path a A END
that does not contain 6. Thus we can construct a 6-free path START a END'
together with backedge END START, this gives a cycle containing a but not 6.
a dominates p, 6 does not dominate p. So 6 and p must be distinct nodes.
+
There must be a path START H a A p that does not pass through 6. From Lemn?a 1,
+ +
there is a path p a that does not pass through 6. Therefore, we have a cycle a H ? a
that does not contain 6.
a does not dominate p, 6 dominates p.
There must a path START p that contains 6 since 6 dominates p. Since a is control
dependent on p, there is a path from p to END that does not contain a. Therefore, there
is a path from START to END that contains 6 but not a.
a does not dominate p, 6 does not dominate p. So a, 6 and p are distinct nodes.
Since a is control dependent on p with direction 1 but 6 is not, either (i) 6 does not
postdominate f, or (ii) 6 postdominates p.
Suppose (i) is true. Since 6 does not dominate p, there is a path START p that
does not contain 6. There is a path p f that does not contain 6. Since 6 does not
postdominate F, there is a path p END that does not contain 6; however, this path
contains a since a postdominates f. Therefore, there is a path START A ? A a A END
that does not contain 6.
Suppose (ii) is true. There is a path p 6 END that does not contain a. Since there
is a path START H p that does not contain a, we have a path START A p A 6 A END
that does not contain a.
4
Li
We leave it to the reader to verify that Theorem 1 holds for the program of Figure 1. We show how to
compute CYC_ next.
3 From directed to undirected graphs
Rather than compute CD directly on a strongly connected component, we reduce the problem to that of
finding cycle equivalence in an undirected graph. The motivation is that algoritbms based on depth-first
search of undirected graphs are simpler than those using directed graphs since cross edges and forward edges
are eliminated.
Let 8 be a strongly connected component. Create a corresponding undirected graph U as follows.
1. Expand 8 into 8': split each node n into nodes flj, fl1 and no such that inedges to a now flow to n?,
outedges from n flow from no, and there are directed edges flj n' and n' .` a0.
2. Undirect edges in 8' to form U.
Figure 2(a) shows the node expansion step pictorially. To avoid cluttering the diagram, we have simply used
triangles to represent new nodes introduced by node expansion. The directions of the triangles differentiate
in-nodes from out-nodes. Figure 2(b) illustrates node expansion for the program of Figure 1. This figure
also shows a DFS spanning tree for the undirected graph, with backedges shown as dashed lines.
In the actual implementation, node expansion and undirection of edges are not carried out literally;
instead, a tuple holding information for the (conceptually) expanded nodes is associated witb each node in
the directed graph.
Theorem 2 Let 8 be a strongly connected component, and let U be the undirected graph formed from 8 by
the above transformation. Nodes a and b are cycle equivalent in 8 if and only if their corrcsponding nodes
a' and b' are cycle equivalent in U.
Proof:
] Suppose a and b are not cycle equivalent in 8. Then there is some directed cycle in 8
containing one of a or b but not both. The corresponding undirected cycle in U contains one of
a' and b' but not both, so a' and 6' are not cycle equivalent in U.
? ] Without loss of generality, assume there is at least one cycle in G containing a' but not
b'. Such a cycle also contains a? and a0, and they are adjacent to a'. Each edge oil such a cycle
has an associated direction from the intermediate transformation step. AQacent edges either
have the same direction or opposing directions; if adjacent edges have opposing directions, we
say there is a direction change at the node between the opposing edges.
Let C' be a cycle of minimum direction changes containing a' but not 6'. If C' has no direction
changes, then there is a corresponding directed cycle in 8 that contains a but not 6.
Otherwise, C' has one or more direction changes. Since C' begins with edge a' a0 and ends
with edge a? a', there is no direction change at a'. Furthermore, there must be an even number
of direction changes that alternate between inward opposing and outward opposing edges; the
first direction change occurs between inward opposing edges.
Now consider the first two direction changes on C'. The first clash occurs at an input node c?
since the directions are inward opposing. The second clash occurs at an output node d0 siiice
the directions are outward opposing. Nodes c' and d' are adjacent to c? and d0 and are not on
C'. Since 8 is strongly connected, there exists a directed path in 8 from c to d; let E' be the
corresponding path from c? to d0 in U.
If neither a' nor b' occur on E', consider the cycle obtained by replacing the portion of cycle C'
between c? and d0 with path E'. This is a cycle containing a' but not 6', and it has two less
direction changes than C', whid? contradicts the assumption that cycle C' had the minimum
number of direction changes.
5
$7
`I
no v			no v
(a) Expanding Nodes and Undirecting Edges
(b) Transformation and DFS of Program in Figure 1
Figure 2: The Transformation and an Example
6
Otherwise, a' and b' may occur (perhaps several times) on E'. If the first occurrence on E' (after
c?) is a', then juxtapose the path a' c? in C' with the path c? a' to the first occurrence of
a' in E'. This is a cycle containing a' but not b' and it has no direction changes. Similarly, if the
last occurrence of either a' or on E' is an a', the cycle a' d0 a' gives a cycle containing
a', but not b', with fewer direction changes than C' which is a contradiction.
Otherwise, both the first and the last occurrence of a' or b' on E' are of b' The path b' d0
Cj			b' gives a directed cycle containing b' but not a'.
Therefore, we conclude that two nodes are cycle equivalent in 8 iff their representatives arc cycle
equivalent in U.
In Figure 2(b), notice that nodes c' and f' occur in all the same cycles. Every other representative
node has some cycle that separates it from other representatives. For example, node b' occurs in a cycle
a0 bi b' b0 c? a0 which does not contain any other representative. Similarly, e' is separated
from d' by the cycle containing c', d', f' and b'.
4 Computing cycle equivalence in undirected graphs
To determine the set of cycle equivalent nodes in an undirected graph, we could enumerate all cycles in the
graph but this would be too expensive. Fortunately, we can use depth-first search to recast the prohlem ii?
terms of sets of backedges rather than sets of cycles.
4.1 Brackets of a node
Let U be an undirected graph formed from a control flow graph by
1.			adding an edge END			START, and then
2. expanding each node and undirecting each edge as shown in Figure 2(a).
We perform a depth-first search of U starting from STARTi and obeying the following rulc:
Whenever DFS visits a node a? or a0, prefer to visit a' before visiting any other neighhor.
This rule ensures that nodes a' corresponding to nodes in the original control flow graph are interior
nodes in the DFS spanning tree. Thus, these interesting nodes are adjacent only to a tree parent and a tree
child (nodes a?, a0) and have no incident backedges. After depth-first search, every edge is either a tree edge
or a backedge, so every cycle in U consists of tree and backedges.
Definition 5 In any depth-first traversal of U, a bracket of a node n is a backedge connecting n or one of
its descendants to an ancestor of n or to n itself
Given our convention for depth-first search, a bracket of a representative node a' always connects a strict
descendent of a' to a strict ancestor of a'. We now show that the set of brackets of a representative node
effectively identify the set of cycles through that node.
Lemma 2 In any DFS walk of U, if representative nodes a' and b' have any bracket in coi'?mon then theg
are ordered by the ancestor relation in the DFS tree.
Proof: (by contradiction) Suppose a' and b' are not ordered by the ancestor relation. Then
no descendent of a' is a descendent of b' and vice versa. Any bracket of a' connects a descendent
of a' (say node x) to an ancestor of a' (say node y); since x is not a descendent of b', this cannot
be a bracket of b'.
7
x
<xl>
a
y
<xl>
(a)			Structured Loops			(b) Unstructured Loops
Figure 3: Names for Cycle Equivalence Sets
a
(c) General Tree Node
Theoreni 3 Representative nodes a' and b' in U are cycle eqnivalent if and only if they have the same set
of brackets in every DFS walk of U.
Proof: (a) We show that if two nodes do not have the same set of brackets in a DFS walk of
U, they are not cycle equivalent. Suppose edge e is a bracket of node a' but not b'. Let x and
y be the two end points of edge e. Consider the tree path between x and y : by definition of
brackets, ?? must occur on this path but b' cannot. By concatenating edge e with the tree path
from x to y, we get a cycle containing a' but not b'.
(b) If a' and b' have the same set of brackets, Lemma 2 asserts that they are ordered by the
ancestor relation in the DFS tree. Without loss of generality, assume that a' is an ancestor of b'.
Consider any cycle through a'. There are no cross edges or forward edges in the DFS tree;
moreover, a' has no brackets incident on it. Therefore, the cycle must contain at least one edge
that connects a strict descendent of a' to a strict ancestor of a'. Let e (x, y) be the first such
edge in the cycle after a', so that all the nodes between a' and x in the cycle are descendants
of a'. Since e is a bracket of a', it must be a bracket of b', so x must be a strict descendent
of b'. If the path from a' to x does not pass through b', there must be some edge (p, q) on the
path where p is a descendent of a' but not of b' and q is a strict descendent of both a' and b'.
Since there are no cross edges in the tree, (p, q) is a bracket of b' but not of a', which contradicts
the assumption that a' and b' have the same set of brackets. Therefore, every cycle containing
a' must contain b'. The proof that every cycle containing b' contains a' is similar and is on?itted. E]
In Figure 2(b), ?? and f' have the brackets (bi, a0) and (b0, ci). No other representative node has exactly
this set of brackets; for example, note that node d' has the bracket (e?, c0).
We can use a straight-forward DFS algorithm to compute the set of brackets for each node; by comparing
these sets, we can compute cycle equivalence. However, comparisons of sets are expensive, so we proceed as
follows. Intuitively, the set of brackets of a node can be viewed as a name for the cycle equivalence class
of the node. To speed the comparisons of names, we need a compact naming scheme for the equivalence
classes. We describe one such scheme next.
4.2 Compact names for sets of brackets
Consider the graph shown in Figure 3(a) in which the DFS tree is simply a chain, and backedges corre-
spond to `structured' loops in which loops are either disjoint or are nested within each other. For simplicity,
8
only representative nodes are shown in the figure. For such graphs, it is easy to see that the set of brackets of
a representative node is uniquely named by the innermost bracket of that node. To compute cycle equivalence
for such graphs, we simply visit nodes in reverse depth-first order, keeping a stack of brackets - when we exit
a node, we delete all brackets connecting the node to a descendent, and then push all brackets connecting
the node to an ancestor. Each representative node is labeled with the name of the topmost bracket on the
stack when the DFS visits it, so nodes with the same label have the same control dependences.
The next complication to consider is that backedges may partially overlap with each other. This situation
is shown in Figure 3(b). The first problem is that in the reverse DFS walk, brackets are not deleted in stack
order. Moreover, note that nodes a' and b' do not have the same set of brackets even though the topmost
element of the bracket stack of both nodes is z. To fix the deletion problem, we represent the bracket set as a
doubly-linked list rather than as a stack. Brackets will always be added to the same end of the list, but may
be deleted from anywhere within the list. In this way, the most recently added bracket (tbe bracket whose
lower endpoint is highest in the tree) will be at the head of the list. If the brackets are properly nested, the
list will behave exactly like a stack. In addition, we maintain a counter that keeps track of the size of the
bracket set. It is easy to see that the pair < topmost bracket, set size > uniquely labels each equivalence
class --H for example, in Figure 3(b), nodes a' and b' will be placed in different equivalence classes, while
nodes a' and c' are placed in the same equivalence class.
Finally, we must handle the case of general DFS trees, not just chains. Figure 3(c) gives an example.
When we encounter a node that has more than one child, the bracket sets of the children must be merged.
Unfortunately, the `most recently added' bracket is no longer well defined. For example, at node e in
Figure 3(c), it is not clear whether the most recently added backedge should be edge (f, d) or edge (h, c).
The resolution of this difficulty rests on the observation that only one of the sub-trees below node e can
contain any nodes cycle-equivalent to any ancestor of e. The reason is that nodes in the sub-trees can only
have brackets that originate in the same sub-tree. Therefore any ancestor of e having brackets from more
than one of the branches cannot be cycle equivalent to a node in any of the bran4?es. Therefore, nodes
between e and b cannot be cycle equivalent to a node below e. However, nodes between b and a can be cycle
equivalent to nodes between h and i.
The solution therefore is to add an additional backedge whenever we need to merge two bracket sets.
This backedge becomes the topmost bracket in the set, and the children's bracket sets are then concatenated
in arbitrary order. The new bracket originates from the vertex whose children are being merged, and extends
up to the highest vertex whose brackets come from more than one of the branches. To add it thus requires
keeping track, at each point in the tree, of the highest vertex reached by any backedge below this point.
The destination of the new backedge is the second-highest of the children's high backedges. This could be
found by examination of the bracket sets, but the highest-ending backedge is not necessarily related to the
first bracket in each set (the highest-originating) so a full search of the bracket set would be necessary.
Fortunately, we can simply compute it independently in constant time. In Figure 3(c), we would add a
dummy backedge from e to b, as shown. Once this is done, the pair < topmost bracket,set size > identifies
the equivalence class as before.
4.3 The Algorithm
We can put these observations together into the following fast algorithm which makes use of an abstract
data type called BracketList to maintain lists of brackets. The following operations are defined on this data
type.
create () : BracketList . Make an empty BracketList structure;
size ( bl:BracketList ) : integer : Number of elements in BracketList structure;
push ( bl:BracketList, e:bracket ) : BracketList : Push e on top of bi;
top ( bl:BracketList ) : bracket : Topmost bracket in bi;
delete ( bl:BracketList, e:bracket ) : BracketList : Delete e from b1
concat ( bll,b12:BracketList ) : BracketList : Concatenate bil and b12;
This abstract data type can be implemented as a record consisting of
9
1. a doubly-linked list of brackets
2. a pointer to the last cell of the list, and
3. an integer representing the size of the list.
The doubly-linked list permits deletions anywhere in the list. The pointer to the last cell of the list
permits fast concatenation of lists by in-place update to the cell. We leave it to the reader to verify that
each of the operations of the abstract data type can be implemented in constant time using this concrete
representation. The only subtlety is in delete. When an edge is pushed onto a bracket list, the edge data
structure is updated so it has a pointer to the bracket list cell containing that edge; this permits constant
time deletion of an edge from a bracket list.
We use integers to identify CD--H classes. We assume a procedure new--HClass--Hname() which returns a new
integer each time it is called. This can be implemented using a procedure with an stalic variable that starts
at 0 and that is incremented each time the procedure is called; the procedure simply returns the current
value of the variable.
The following operations on nodes are used in the algorithm.
Number ( n:node ) : integer : DFS number of node
Class ( n:node ) : integer : CD class of node;
BList ( n:node ) : BracketList : List of brackets of node;
Hi ( n:node ) : integer : Highest destination node of any edge originating from a descendent
of node;
Since an edge may be the topmost bracket of the bracket list of several representative nodes, the edge
data structure caches the CD= class number and the size of the bracket list when the edge was most recently
the topmost bracket of a node's bracket list. For example, in Figure 3(b), edge z is the topmost bracket for
nodes c', a1 and finally b'. a' is given the same CD _ class number as c' because the size of the bracket lists
at a' is the same as the value cached on edge z at node c'. In contrast, a' and b' are given different CD--H
class numbers. To access the values cached on brackets, the following operations are defined on edges.
RecentSize ( e:edge ) : integer : Size of bracket set when e was most recently the topmost
bracket for a representative node;
Recent Class ( e:edge ) : integer : CD class number of representative node for which e was
most recently the topmost bracket;
The edge and node data types can be implemented using records in the obvious way.
It is easy to see that during the DFS walk of the undirected graph, the amount of work performed at
each node is some constant amount together with work proportional to the number of edges incident at the
node. Since the numbers of nodes and edges in the undirected graph is the same, within a constant factor,
as in the control flow graph, the complexity of the algorithm is 0(E) where E is the number of edges in the
original control flow graph.
4.4 Correctness
In proving the correctness of the algorithm, we will need the following lemma.
Lemma 3 The backedges added by Ihe atgorithm do not affect the cycle-equivalence relation for represen?a-
tive vertices.
Proof: By Theorem 3, two representative vertices are cycle-equivalent if and only if they have
the same set of brackets. Consider two representative vertices x' and y'. If they have the same
set of brackets with the added backedges, then clearly deleting the new backedges will still leave
them with the same sets. If they have the same brackets from the original edge set, we must
show that they will share the same set of new brackets.
Consider the example in Figure 3(c). Suppose node x' is bracketed by the new backedge (e, b).
The origin of that backedge, e, is a node with at least two children: the highest-reaching branch
10
Procedure cycle?equiv (G : CFG)
/* Preprocessing */
Add edge from END to START in G;
Expand each node and undirect edges as described in Section 3;
Perform depth-first search of undirected graph as described in
Section 4.1, assigning preorder nuiber to each node;
/* Compute CD equivalence classes */
for each node n, in reverse depth-first order, do
/* Compute Hi(n) */
hiO min? Number(t) I (t,n) is a backedge >; /* how hi using backedges only */
hit min? Hi(c) I c is a child of n >; /* how hi through children */
hi-child any child of n whose Hi value is equal to hit; /* hit going child */
hi2 min? Hi(c) I c is a child of n other than hi-child +;
Hi(n) = min? hiO, hit );
/* Compute BList(n) */
BList (n) create ();
for each child c of n do
BList (n) := concat (BList (n), Blist (c)) od;
for each backedge e from a descendant of n to n do
Blist (n)			delete (Blist (n), e) od;
for each backedge e from n to an ancestor of n do 1* in any order! */
BList (n) := push (BList (n), e) od;
RecentSize Ce)			-t; /* n is not a representative node */
if n has more than one child then
push (BList (n), <n,hi2>); /* ``capping'' backedge */
1* Compute Class (n) */
if n is a representative node, then
if RecentSize (top (BList (n))) o+ size (BList (n)) then
/* start a new equivalence class */
RecentSize (top (BList (a))) := size (BList (n));
RecentClass (top (BList (a))) := new-Class-nane ();
Class (n) = RecentClass (top (BList (a)))
+
+ /* for each node */
+ /* procedure */
Figure 4: The CYC_ Algorithm
11
has a backedge to a point higher in the tree than b (or to b itself, if there was a tie), and the
second-highest-reaching branch has a backedge to b. Now consider where the node y' (which
shares with x' all brackets from the original set) can occur. It must share the bracket (g, b) with
so it must be somewhere on the tree path from g to b, but it also shares the bracket (i, a), so
must occur on the path from i to a. The only region where these two paths intersect is in the
path from e to b. This means that y' will also have the new bracket (e, h).
Theorem 4 The fast algorithni is correct.
Proof: We need to prove that two representative vertices will be in the same class if and only
if they are cycle-equivalent. One direction is reasonably easy: if two vertices are cycl&equivalent,
they will end up in the same class. By Theorem 3 two cycle-equivalent vertices will have the
same bracket sets. By Lemma 3 the backedges added during the DFS will not affect the cycle-
equivalence relation. Therefore the bracket sets, as computed by the algorithm, will have the
same size and the same top bracket. They will therefore be grouped into the same class.
To complete the proof, we need to establish that if two representative vertices are not cycle-
equivalent, then they will not be in the same class. Let a' and b' be two representative vertices
that are not cycle-equivalent. By Theorem 3 they must have different bracket sets, iiicliiding
(by Lemma 3) the new backedges added by the algorithm. If these sets are different size the
algorithm clearly places them in different class, so let us suppose the bracket sets are the same
size. By Lemma 2, if a' and b' are not ordered by the ancestor relation, then they have no
brackets in common and are therefore placed in different classes. Otherwise, assume without loss
of generality that a' is an ancestor of b'. Since the sets are the same size, but not identical, a'
must have a bracket (p, q) not shared by b', and b' must have a bracket (r, s) not shared by a'.
The node p is a descendant of a' if it is also an ancestor of b' then the edge (p, q) must be
linked on the bracket list ahead of b's top bracket. Either (p, q) will be the top bracket, or there
will be another still higher. This bracket cannot include b', so b' will have a different top bracket
and will be in a different class.
Now assume that p is not an ancestor of b'. In that case the paths from a' to p and to 1)' diverge
at some point. Call this node d. Since d has multiple children, a backedge was added from d
to a point at which backedges from only one of the branches were still present. If that point is
above a', then the added backedge will bracket a', and it or a still higher backedge will be the
top bracket for a', while it could not be the top bracket for b'. If the point is below a', then all
backedges from the branch b' is on must have ended below a', so the top bracket for h', whatever
it is, must have ended also and so cannot be a bracket of ?? In either case, a' and 6' will have
different top brackets, and so will be in different classes. 0
4.5 Implementation
Our algorithm for CD is asymptotically optimal; in addition, the constant factor is small and the
algorithm runs fast in practice. One detail of our implementation is worth noting: we avoid explicitly
expanding nodes and ttndirecting edges. Instead, we use doubly-linked control flow edges (so that depth-first
search can traverse edges in either direction), and we maintain a tuple of information at each control flow
node, corresponding to the information that would be stored on the expanded nodes. The resulting code is
slightly more complex, but the savings in space and time over working with the explicitly transformed graph
are significant.
Figure 5 shows two graphs for which the control dependence relation is quadratic in the size of the
program. We compared our implementation of the CD algorithm to an implementation of Lenganer and
Tarjan's fast postdominator algorithm, running on a Sun SPARC ELC. Figure 6 shows that the running
time of our algorithm is linear in the size of the program, as expected. This figure also shows that our
algorithm runs faster than the postdominator algorithm on all graphs. Times shown are the average over 25
consecutive runs.
12
START			START
p
tt
END
(a) Lattice Graphs
END
(b) Nested Repeat-until Loops
Figure 5: Difficult Graphs for Control Dependence
We chose these examples because any straight-forward algorithm for CD that partitions nodes into
equivalence classes using the control dependence relation must have a running time that is quadratic in
the size of the program. Moreover, finding postdominators is the first step in the standard algorithms for
the computation of control dependence [FOW87] or for computing control dependence equivalence [CFS9Oj
therefore, we compute control dependence equivalence faster than the first step of either traditional
algorithm.
5 Finding Single Entry Single Exit regions
An important application of cycle equivalence is the determination ofsingle entry single exit (SESE) regions
of a control flow graph. SESE regions are defined as follows.
Definition 6 Two distinct nodes a and b in a control flow graph G encThse a single entry single exit
region if
o+ a dominates b
o+ b postdominates a
o+ a and 6 are cycle equivalent in G.
Every node in a control flow graph constitutes by itself what we might intuitively call a SESE region,
but we exclude such trivial regions from consideration by requiring that a and 6 be distinct nodes. The
first two conditions ensure that control reaches 6 whenever it reaches a and vice versa. The third condition
ensures that whenever control reaches a, it reacbes 6 before reaching a again and vice versa. These conditions
correspond to our intuitive notion of a single entry single exit region. We use an ordered pair (a, 6) to denote
a SESE region where a is the entry node and 6 is the exit node. In practice, we have found it more useful to
work with SESE regions defined by pairs of edges, rather than by pairs of nodes, satisfying these properties.
It is straightforward to rephrase our discussion in terms of edges, but we will not do so here.
5.1 Finding Canonical SESE regions
The first problem we must solve is the determination of non-trivial SESE regions of a graph. If (a, 6) is a
SESE region and (6, c) is a SESE region, then (a, c) is a SESE region as well. In other words, SESE regions
have a certain transitivity property. A graph with N nodes can have 0(N2) SESE r??ions each of the
13
0.8 -
0.71
0.6
0.51
E
? 0A I
w
0.31
0.21
0.1
I--H
I--H
CDequiv -+.--H
dominators ?-
0
1000			2000			3000			4000			5000			6000			7000			8000
Lattice Size
(a) Performance on Lattice Graph
0.8
0.7 I
0.6 I
0.5
E
? 0A
w
0.3
0.2
0.1
ii
I--H
CDequiv
dominators ?-
0
1000			2000			3000			4000			5000			6000			7000			8000
Repeat.-Loop Nesting
(b) Performance on Nested Repeat-Loops
Figure 6: Linear time behavior on difficult graphs
14
N2 node pairs in a chain of N nodes encloses a SESE region. However, we have never found any use for
complete enumeration of all SESE regions of a graph. Instead, for each node x in the graph, we want to find
the smallest SESE regions, if they exist, for which x is an entry node or an exit node. We will call these the
canonical SESE regions associated with x; taking the `transitive closure' of the canonical SESE regions of a
graph generates all the SESE regions of that graph. We express this more formally as follows.
1. Given a node x, find a node b, if it exists, such that
o+ (x, b) is a SESE region, and
o+ if (x, b') is also a SESE region, then b dominates 6'.
2. Given a node x, find a node a, if it exists, such that
o+ (a, x) is a SESE region, and
o+ if (a', x) is also a SESE region, then a postdominates a'.
The following result is the key to solving this problem for all nodes in the graph in 0(E) tin?e.
Theorem 5 Let S be the strongly connected component constructed by adding an edge END STAW? to a
control flow graph G . Nodes a and 6 in G enclose a SESE region iff they are cycle equivaThnt in 5.
Proof: Suppose a and 6 enclose a SESE region in G. Consider any cycle in 5. If this cycle
does not include the edge END START, the cycle is present in G and must contain either both
or neither of a and 6. Suppose the cycle does contain the edge END START. If the cycle
contains a but not 6, then a must occur on the portion of the cycle from START to END. Since
this path contains a but not 6, 6 does not postdominate a, which contradicts the definition of
SESE regions. Therefore, if the cycle contains a it must contain 6. A similar argument shows the
converse. Therefore, every cycle in 5 contains both or neither of a and 6, which means a and 6
are cycle equivalent.
Suppose a and b are cycle equivalent in 5. Every cycle in G occurs in 5; therefore, a and 6 must
occur in all the same cycles in G. It remains to be shown that a and b are ordered by both
dominance and postdominance. Every path from START to END contains both a and 6 or neither.
Without loss of generality, suppose that there is a 6-free path from START to a. Then, every
path from a to END must contain b, so b postdominates a. Since a and 6 are distinct nodes a
cannot postdominate b, so there is an a-free path from 6 to END. This means that a must occur
on every path from START to b; in other words, a dominates 6. Therefore, a and 6 are ordered by
dominance and postdominance.
We can compute cycle equivalent nodes in 0(E) time and space using the algorithm given earlier. To
find canonical SESE regions, we simply order the nodes in each cycle equivalence class by dominance (alter
natively, by postdominance). This is easy to do in a single DFS walk of the control flow graph because if a
dominates 6, then a must be an ancestor of b in every DFS walk of the graph. Therefore, once each node
has been assigned to a cycle equivalence class by the algorithm of Figure 4, we can order the nodes in each
class by inserting them into each class in the order visited during a DFS walk of the graph.
To find the canonical SESE regions associated with a node N, we simply find, if they exist, the predecessor
and the successor of N in the ordered cycle equivalence class of N. This takes 0(E) time for all nodes in
the graph.
5.2 Nesting structure of canonical SESE regions
The second problem which arises in many applications is the determination of the nesting structure of
canonical SESE regions.
Definition 7 A node n in a graph 0 is contained within a SESE region (a, 6) if a dominates a and 6
postdominates n.
15
Intuitively, node n is `between' a and bin the graph. This definition can be extended in the obvious way
to containment of SESE regions. Theorem 6 describes how canonical SESE regions in a graph are related.
Theorem 6 If R1 and R2 are two canonical SESE regions of a graph, one of the following statements
applies.
1.
2.
3.
R1 and R2 are node disjoint.
R1 is contained within R2 or vice versa.
The exit node of Ri is the entry node of R2 or vice versa.
In other words, canonical SESE regions cannot have any partial overlap if two regions have any nodes
in common, they are either nested or in tandem3. This is most obvious in the case of structured programs.
For general control flow graphs, the required result may be proved as follows.
Proof:
Suppose distinct canonical SESE regions (a, b) and (c, d) both contain a node n. Then a and c
both dominate n, and so they are ordered by dominance. Without loss of generality, assume that a
dominates c. Similarly, b and d both postdominate n, and so they are ordered by postdominance.
If b postdominates d, then (c, d) is contained within (a, b).
Otherwise, d postdominates b. There are now three cases to consider.
1. Suppose b and c are the same node. Since b postdominates n and c dominates n, it tollows
that n, b and c must be the same node. Therefore, n is the only node in common and the
two SESE regions are in tandem.
2. Suppose c dominates b and c and b are distinct nodes. We show that a, b, c aud (I are in
the same control region and that (a, b) cannot form a canonical SESE region, leading to a
contradiction.
Since a dominates c and c dominates b, it follows that every path from a to b must contain
c. Since b postdominates a, this means that c postdominates a and b postdominates c.
Therefore, a, 6 and c are ordered by dominance/postdominance; this argument can be
extended to show that this is true for d as well, but this is not necessary for the proof.
Every cycle through a and 6 contains a path from a to 6, and hence contains c. If there is a
cycle through c that does not contain 6, then there is a path from c to d without 6; since d
postdominates c, this means that 6 does not postdominate c, whid? is incorrect. Therelore,
every cycle through c contains 6 and hence contains a. This means that a, c and 6 are in
the same cycle equivalence class and c should be ordered between a and 6 in the equivalence
class. This violates the assumption that the exit node of the canonical SESE region with
entry a is 6.
Therefore, this case cannot occur.
3. Suppose c does not dominate 6. Then, there is a c-free path from START to 6. This means
that c must postdominate 6; otherwise, we have a path START 2+ 6 2+ END which passes
through d (since d postdominates 6) but not c, violating the assumption that c dominates
d. Since 6 postdominates n, this means that c postdominates n. But c also dominates n.
Therefore, c and n must be identical. Therefore, 6 postdominates c. Since we have shown
that c postdominates 6, 6 and c are identical. But by assumption, c does not domiiiate 1),
so c and 6 are distinct. We conclude that this case cannot occur.
3Notice that this property may not be true for SESE regions that are not canonical.
16
Figure 7: Merge Factoring
To determine the smallest SESE region containing a given SESE region, we can extend the DFS algorithm
that determines canonical SESE regions. We maintain a stack during DFS that records the SESE regions
containing the node being visited. Whenever DFS enters a SESE region through either the entry node or
retreats into it through the exit node, we push the name of the SESE region on this stack; when exiting the
region, we pop this name from the stack. From Theorem 6, it follows that the pushing and popping follows a
stack discipline, which is the required behavior. The topmost SESE region on this stack whe?? DFS reaches
the entry node of a SESE region 1?1 is the name of the smallest SESE region containing J?i
5.3 Discussion
As a final remark, we note that a concept related to SESE regions called a hammock has been defined in the
literature [Kas75]. Although it appears common practice to confuse hammocks and SESE regions, they are in
fact different. The exit node of a hammock can be the target of edges outside the hammock; therefore, there
are hammocks that are not SESE regions, as shown in Figure 7. Also, the entry node of a hammock cannot
be the target of an edge from the exit of the hammock; therefore, there are SESE regions that are hammocks.
For example, a repeat-until loop in a structured program is a SESE region but it is not a hammock.
The standard algorithm for finding hammocks has complexity O(EN) [Kas75J. It may he possible to use
the ideas of this paper to find hammocks in 0(E) time, but we have not explored this furthei?.
6 Extensions
We conclude this paper by describing three open problems related to this work.
A small program transformation can increase the number of SESE regions in the program When a set of
edges come together at some node in the control flow graph, it may be possible to introduce dummy nodes in
the graph to bring the edges together in stages, rather than all at once. This process, called merge factoring,
is shown in Figure 7. Nodes a and b in the original program do not form a SESE region. When the dummy
node d is inserted, nodes a and d form a SESE region. Is there a fast algorithm for deciding where and how
merge factoring should be performed? Note that the original program in Figure 7 is a hammock; therefore
this problem may be related to hammock detection.
Secondly, it may be possible to use the ted?niques in this paper to represent the full control dependence
relation in 0(E) space such that the control dependences of a node can be determined in time proportional
to the number of these dependences. This problem is of academic interest since we have never found a need
to enumerate all the control dependences of a node. The intuitive idea is the following. The full control
dependence relation has O(EN) size. However, it may be possible to factor this relation to represent it in
0(E) space and to compute it in 0(E) time. Notice that control dependence equivalence can be used to
reduce the space required to represent the control dependence relation for example, we can introduce a
region node to represent an equivalence class, connect each node in the class to the region node, and direct
17
control dependences to the region node, not to every node in the equivalence class. If there are P nodes in
the equivalence class and they have C control dependence edges each, the space required to represent this
information goes down from P * C to P + C, without increasing the (asymptotic) time required to find all
nodes with a given control dependence, or the time required to find all the control dependences of a node.
We do not know if this idea can be extended to compute and to represent a factored control dependence
relation in linear time and space4.
Finally, is there a fast incremental algorithm for updating the control dependence equivalence relation
when the control flow graph is changed? Such an algorithm would be useful in programming environments
and text editors in which the structure of control flow may be modified incrementally by editing tbe text
of the program. The theory of incremental algorithms for determining properties of directed graphs is
still in its infancy. However, there is a well-established body of work on such incremental algorithms for
undirected graphs [Rau92]. Since our algorithm for CD ultimately solves a problem on undirected graphs,
this technology may be applicable to the CD problem for directed graphs.
References
[Bal92]
[CFS90]
[FOW87]
Thomas Ball. What's in a region? -or- computing control dependence regions in linear time and
space. Technical Report 1108, University of Wisconsin --H Madison, Computer Sciences Department,
September 1992. To appear in LOPLAS.
Ron Cytron, Jeanne Ferrante, and Vivek Sarkar. Compact representations for control dependence.
In Proceedings of the SICPLAN `90 Conference on Programming Language Design and Implemen-
tation, pages 337--H351, White Plains, New York, June 20--H22, ?990. Published as ACM SIGPLAN
Notices 25(6).
J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependency graph and its uses in
optimization. ACAl Transactions on Programming Languages and Sgstems, 9(3):319--H349, June
1987.
[GS87] Rajiv Gupta and Mary Lou Soffa. Region sd?eduling. In 2nd hiternational Coaference on Saper-
computing, pages 141--H148,1987.
[JP93]
Richard Johnson and Keshav Pingali. Dependence-based program analysis. In Proceedings of the
SIGPLAN `93 Conference on Programming Language Design and Implementation, pages 78--H89,
Albuquerque, New Mexico, June 23--H25,1993. Published as ACM SICPLAN Notices 28(6).
[Kas75] V. N. Kas'janov. Distinguishing hammocks in a directed graph. Soviet Math. Dokiady, 16(5):448--H
450,1975.
[Rau92] Monika Raud?. Fully Dynamic Graph Algonthms and their Data Structures. PhD thesis, Princeton
University, December 1992. Advisor: R. E. Tarjan.
44n [JP93J, we implied that we had a solution, but in wnting this paper we realized that the problem remaios open.
18
