Re: question on control dependence

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


This looks correct and I've never seen it presented before. However, you
need to consider the case where a node has more than two successors.
These occur in most languages and have to be handled somehow.


It looks like the correct solution for a node X with 3 successors, say A,
B, and C, would be


CD(X) = (P(A) ^ (P(B) | P(C)))
| (P(B) ^ (P(A) | P(C)))
| (P(C) ^ (P(A) | P(B)))


The general form appears to be expensive.


>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.


It's more complex but much more efficient to use Lengauer and Tarjan's
approach to compute the dominator tree (versus the ordinary data-flow
solution given in step 1).


    title="A Fast Algorithm for Finding Dominators in a Flowgraph",
    author="Thomas Lengauer and Robert Endre Tarjan",
    journal=toplas,
    year=1979,
    month=jul,
    volume=1,
    number=1,
    pages="121--141"


The primary attraction (in my mind) of Cytron, et al. is for the efficient
computation of SSA; control dependence is just a fortuitous side effect
that I never use (though plenty of other people do). Furthermore, I find
plenty of uses for the dominator tree, so the effort spent implementing
the efficient version is repaid many times.


Preston Briggs
--

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