Re: question on control dependence

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


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


The general case of more than 2 succesoors is handled like this...


CD(X) = union(P(S)) - intersection(P(S)), for S in successors(X)


(This is a much simpler version of another answer I posted earlier)


cliffc@rice.edu (Cliff Click) writes:
>3) Your problem is 1-bounded; a single pass over the graph is
>sufficient.


Only for part 2. For part 1 (computing post dominance), more than 1
pass may be required.


>4) Your problem requires O(N) bit-vectors, or
> O(N^2) COMMON CASE but with a small constant.


That is, O(N^2) space, where N is the number of basic blocks.


>5) The authors in Cytron et al. claim O(N) in practice, although they admit
> to O(N^2) in the worst case. Their algorithm will surely run with a
> larger constant than yours.


McConnel's algorithm will require at least O(N^2) time (consider the bit
vectors to be initialized). On the other hand, I believe it only requires
O(N^2) time worst-case. Therefore, worst case, the algorithms are the
same. Best case (and probably expected case , Cytron et al. are faster,
though perhaps only for very large N.


Preston Briggs
--

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