# Re: question on control dependence

## Paul Havlak <paco@cs.rice.edu>Tue, 15 Dec 1992 19:13:56 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)
Re: question on control dependence dkchen@sp91.csrd.uiuc.edu (1992-12-16)
| List of all articles for this month |

 Newsgroups: comp.compilers From: Paul Havlak Organization: Center for Research on Parallel Computation Date: Tue, 15 Dec 1992 19:13:56 GMT Keywords: optimize, design, bibliography References: 92-12-056 92-12-065

mcconnel@newta1.cs.uiuc.edu writes:
I've come up with a simple algorithm for computing control dependences, ...

Looks to me like the algorithm should work. I dislike it anyway
for two reasons:

* It's not very general; many languages allow more than two
branches out of a node.

* It uses bit vectors. Sure, you only require O(N) bit-vector
steps for N nodes, but the bit vectors are O(N) long,
so you're always paying O(N^2) time and space.

My favorite algorithm for control dependence calculation is in [3].
It requires no data structures besides the control-flow graph and the
postdominator tree, as input, and the control dependence graph, as output.
The algorithm takes time linear in the number of control dependences,
which is usually linear in the number of nodes.
First, build the postdominator tree using the method of [4]
(almost-linear) or [5] (linear). Then to enumerate the set CD(X, L) [the
control dependence successors of a node X with label L], do the following:

* CD(X, L) = {}

* Assign Y = the sink of X's control-flow outedge with label L

* While (Y != immediate postdominator of X)
CD(X, L) += Y
Assign Y = immediate postdominator of Y

(where += denotes addition of member to set)

Note that this method can also be used in the construction of SSA form;
see [3] for details.

References:

[3]
@inproceedings{CFS:Compact,
Author={R. Cytron and J. Ferrante and V. Sarkar},
Title={Compact representations for control dependence},
BookTitle=SIGPLAN90,
Pages={337--351},
Month=Jun,
Year={1990}}

[4]
@Article{LeTa:Dom,
Author = {T. Lengauer and R. E. Tarjan},
Title = {A fast algorithm for Finding Dominators in a flowgraph},
Journal = TOPLAS,
Volume = 1,
Pages = {121--141},
Year = 1979}

Actually, [3] cites another method for building the postdominator
tree which, I just realize, I've never looked up:

[5]
@inproceedings{Harel:Dom,
Author = {Dov Harel},
Title = {A linear-time algorithm for finding dominators in
flow graphs and related problems},
BookTitle = {Symposium on Theory of Computing},
Month = May,
Year = {1985}}
--
Paul Havlak Dept. of Computer Science
Graduate Student Rice University, Houston TX 77251-1892
PFC/ParaScope projects (713) 527-8101 x2738 paco@cs.rice.edu
--

Post a followup to this message