Re: question on control dependence

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,
      Address={White Plains, New York},
      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
--

Return to the comp.compilers page.
Search the comp.compilers archives again.