question on control dependence

I've come up with a simple algorithm for computing control dependences,
and I was wondering if it was already known; I haven't seen it in the
literature. My algorithm uses straightforward data flow analysis, and
works like so:


=== Begin Algorithm ===


1. For a given flow node X, let P(X) denote the nodes that post-dominate
X, along with X itself. Compute P(X) by using any of the standard
techniques to solve the following backward data flow equations:
        P(X) = X | (P(Y1) & ... & P(Yn)),
        P(Stop) = {}
where Y1 ... Yn are the successors of X, "|" denotes set union, "&"
denotes set intersection, and Stop is a unique exit node for the flow
graph. (This part is pretty much straight out of the red dragon book.)


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)).
Furthermore, the edges that should be labelled "true" in the control
dependence graph are the ones from X to the nodes in CD(X) & P(X-true);
and "false", the ones to the nodes in CD(X) & P(X-false).


=== End Algorithm ===


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. This algorithm is asymptotically as efficient as
they are; for typical programs, it's probably more efficient than the
algorithm in [1]. My question is, has this algorithm been proposed
before? (It seems too simple not to have been.)


        Carl McConnell
        Grad Student
        Department of Computer Science
        University of Illinois at Urbana-Champaign
        1304 W. Springfield Ave.
        Urbana, IL 61801-2987


-------------------


References:


[1]
@article{ferrante87,
    author="Jeanne Ferrante and Karl J. Ottenstein and Joe D. Warren",
    title="The Program Dependence Graph and Its Use in Optimization",
    journal=toplas,
    volume=9,
    number=3,
    month=jul,
    year=1987,
    pages="319-349"
}


[2]
@article{cytron91,
    author = "Ron Cytron and Jeanne Ferrante and Barry Rosen
and Mark Wegman and Kenneth Zadeck",
    title="Efficiently Computing Static Single Assignment Form and the
            Control Dependence Graph",
    journal=toplas,
    volume=13,
    number=4,
    month=oct,
    year=1991,
    pages="451-490"
}
--

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