Tue, 15 Dec 1992 16:24:51 GMT

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

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.