Tue, 15 Dec 1992 18:58:20 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: | preston@dawn.cs.rice.edu (Preston Briggs) |

Organization: | Rice University, Houston |

Date: | Tue, 15 Dec 1992 18:58:20 GMT |

References: | 92-12-056 92-12-065 |

Keywords: | design |

mcconnel@newta1.cs.uiuc.edu writes:

*>I've come up with a simple algorithm for computing control dependences,*

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

The general case of more than 2 succesoors is handled like this...

CD(X) = union(P(S)) - intersection(P(S)), for S in successors(X)

(This is a much simpler version of another answer I posted earlier)

cliffc@rice.edu (Cliff Click) writes:

*>3) Your problem is 1-bounded; a single pass over the graph is*

*>sufficient.*

Only for part 2. For part 1 (computing post dominance), more than 1

pass may be required.

*>4) Your problem requires O(N) bit-vectors, or*

*> O(N^2) COMMON CASE but with a small constant.*

That is, O(N^2) space, where N is the number of basic blocks.

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

McConnel's algorithm will require at least O(N^2) time (consider the bit

vectors to be initialized). On the other hand, I believe it only requires

O(N^2) time worst-case. Therefore, worst case, the algorithms are the

same. Best case (and probably expected case , Cytron et al. are faster,

though perhaps only for very large N.

Preston Briggs

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.