Wed, 16 Dec 1992 17:08:33 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: | paco@cs.rice.edu (Paul Havlak) |

Organization: | Center for Research on Parallel Computation |

Date: | Wed, 16 Dec 1992 17:08:33 GMT |

Keywords: | optimize, analysis |

References: | 92-12-056 92-12-070 |

preston@dawn.cs.rice.edu (Preston Briggs) writes:

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

It depends on how you define "worst case". In terms of the time

and space required per control dependence, the newer Cytron et al.

algorithm (and I think the older one as well) can beat McConnel's

method by a linear factor.

* When the number of control dependences is O(N), McConnel's

algorithm is quadratic in its output -- O(|CD|^2). It

is linear in its output only when |CD| is O(N^2).

* The newer Cytron et al. algorithm is always linear in its

output -- O(|CD|). This is particularly important

because |CD| is much more often O(N) than O(N^2).

I believe the newer Cytron et al. algorithm to be as fast as

theoretically possible. Once you've built the predominator tree, it

requires very few (less than a dozen?) instructions to find each control

dependence relation.

Note: The newer Cytron et al. algorithm, which amounts to reading control

dependences off the postdominator tree, appeared in Cytron, Ferrante and

Sarkar's SIGPLAN '90 paper. However, the method was also described

briefly in Ferrante, Ottenstein and Warren's July 1987 TOPLAS paper

(although without handling of labels).

--

Paul Havlak Dept. of Computer Science

Graduate Student Rice University, Houston TX 77251-1892

PFC/ParaScope projects (713) 527-8101 x2738 paco@cs.rice.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.