Re: question on control dependence

cliffc@rice.edu (Cliff Click)
Tue, 15 Dec 1992 16:24:51 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: cliffc@rice.edu (Cliff Click)
Organization: Center for Research on Parallel Computations
Date: Tue, 15 Dec 1992 16:24:51 GMT
References: 92-12-056 92-12-065
Keywords: optimize

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


Post a followup to this message

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