Re: question on control dependence

mcconnel@newta1.cs.uiuc.edu writes:


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


I am not the world's most knowledgeable dataflow expert, so Caveat Emptor!
With the disclaimer out of the way, here goes:


1) Your MEET operator is set intersection ("&").
2) Your transfer function for node Z is: f(x) = Z | x.
      (The "x" here is the MEET over the inputs.)
3) Your problem is 1-bounded; a single pass over the graph is sufficient.
4) Your problem requires O(N) bit-vectors, or
      O(N^2) COMMON CASE but with a small constant.


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. I have implemented a variation of [2]
      and seen it run "fast enough" for my research compiler.


6) You don't say how to handle indirect jumps.
      Real compilers gotta deal with this case.


7) With all that said, your algorithm is intuitive to me.




> My question is, has this algorithm been proposed before?
> (It seems too simple not to have been.)


I've not seen it before.


Cliff
cliffc@cs.rice.edu
--

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