# question on control dependence

## mcconnel@newta1.cs.uiuc.eduMon, 14 Dec 1992 23:42:03 GMT

From comp.compilers

Related articles
Extension Languages marks@iris.mincom.oz.au (1992-12-14)
question on control dependence mcconnel@newta1.cs.uiuc.edu (1992-12-14)
Re: question on control dependence cliffc@rice.edu (1992-12-15)
Re: question on control dependence preston@dawn.cs.rice.edu (1992-12-15)
Re: question on control dependence preston@dawn.cs.rice.edu (1992-12-15)
Re: question on control dependence paco@cs.rice.edu (Paul Havlak) (1992-12-15)
Re: question on control dependence bwilson@shasta.stanford.edu (1992-12-15)
Re: question on control dependence paco@cs.rice.edu (1992-12-16)
[2 later articles]
| List of all articles for this month |

 Newsgroups: comp.compilers From: mcconnel@newta1.cs.uiuc.edu Organization: Compilers Central Date: Mon, 14 Dec 1992 23:42:03 GMT References: 92-12-056 Keywords: design

I've come up with a simple algorithm for computing control dependences,
and I was wondering if it was already known; I haven't seen it in the
literature. My algorithm uses straightforward data flow analysis, and
works like so:

=== Begin Algorithm ===

1. For a given flow node X, let P(X) denote the nodes that post-dominate
X, along with X itself. Compute P(X) by using any of the standard
techniques to solve the following backward data flow equations:
P(X) = X | (P(Y1) & ... & P(Yn)),
P(Stop) = {}
where Y1 ... Yn are the successors of X, "|" denotes set union, "&"
denotes set intersection, and Stop is a unique exit node for the flow
graph. (This part is pretty much straight out of the red dragon book.)

2. Assume that each node in the flow graph has no more than 2 successors,
and that if a node does have 2 successors, one is the "true" successor and
the other the "false" successor. For a given flow node X, let CD(X)
denote the nodes that are control dependent on X. If X has fewer than 2
successors, CD(X) is empty. Otherwise, we can find CD(X) as follows:
CD(X) = P(X-true) ^ P(X-false)
where X-true and X-false are respectively the true and false successors,
and "^" denotes symmetric difference (i.e., A ^ B = (A | B) - (A & B)).
Furthermore, the edges that should be labelled "true" in the control
dependence graph are the ones from X to the nodes in CD(X) & P(X-true);
and "false", the ones to the nodes in CD(X) & P(X-false).

=== End Algorithm ===

To me this algorithm seems much more intuitive and easier to program
than the control dependence algorithms in [1] and [2], since those
algorithms are based on the post-dominator tree, which is more
complicated to compute than P(X), and less suitable for computing
control dependences. This algorithm is asymptotically as efficient as
they are; for typical programs, it's probably more efficient than the
algorithm in [1]. My question is, has this algorithm been proposed
before? (It seems too simple not to have been.)

Carl McConnell
Department of Computer Science
University of Illinois at Urbana-Champaign
1304 W. Springfield Ave.
Urbana, IL 61801-2987

-------------------

References:

[1]
@article{ferrante87,
author="Jeanne Ferrante and Karl J. Ottenstein and Joe D. Warren",
title="The Program Dependence Graph and Its Use in Optimization",
journal=toplas,
volume=9,
number=3,
month=jul,
year=1987,
pages="319-349"
}

[2]
@article{cytron91,
author = "Ron Cytron and Jeanne Ferrante and Barry Rosen
and Mark Wegman and Kenneth Zadeck",
title="Efficiently Computing Static Single Assignment Form and the
Control Dependence Graph",
journal=toplas,
volume=13,
number=4,
month=oct,
year=1991,
pages="451-490"
}
--

Post a followup to this message