Re: question on control dependence

preston@dawn.cs.rice.edu (Preston Briggs)
Tue, 15 Dec 1992 18:18:33 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: preston@dawn.cs.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Date: Tue, 15 Dec 1992 18:18:33 GMT
References: 92-12-056 92-12-065
Keywords: design

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


Post a followup to this message

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