# 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