29 Nov 2006 00:52:26 -0500

Related articles |
---|

finding all dominator trees amichail@gmail.com (Amir Michail) (2006-11-22) |

Re: finding all dominator trees diablovision@yahoo.com (2006-11-26) |

Re: finding all dominator trees martin@gkc.org.uk (Martin Ward) (2006-11-27) |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-11-27) |

Re: finding all dominator trees s1l3ntR3p@gmail.com (s1l3ntr3p) (2006-11-28) |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-11-29) |

Re: finding all dominator trees bmoses-nospam@cits1.stanford.edu (Brooks Moses) (2006-11-29) |

Re: finding all dominator trees s1l3ntR3p@gmail.com (s1l3ntr3p) (2006-11-29) |

Re: finding all dominator trees DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-11-29) |

Re: finding all dominator trees cfc@shell01.TheWorld.com (Chris F Clark) (2006-11-30) |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-12-03) |

Re: finding all dominator trees diablovision@yahoo.com (2006-12-04) |

Re: finding all dominator trees amichail@gmail.com (Amir Michail) (2006-12-05) |

[4 later articles] |

From: | Brooks Moses <bmoses-nospam@cits1.stanford.edu> |

Newsgroups: | comp.compilers |

Date: | 29 Nov 2006 00:52:26 -0500 |

Organization: | Stanford University |

References: | 06-11-09606-11-111 06-11-114 |

Keywords: | analysis |

s1l3ntr3p wrote:

*> Amir Michail wrote:*

*>> diablovision@yahoo.com wrote:*

*>>>> Is there an efficient algorithm for finding all dominator trees of a*

*>>>> graph? That is, for every node, find its dominator tree. I'm looking*

*>>>> for something better than simply running a dominator tree algorithm*

*>>>> for each node in the graph.*

*>>> Unless I am missing some subtlety of your situation, you should just be*

*>>> able to run the dominator tree algorithm for the root node of the*

*>>> graph. Dominator trees have the property that each subtree for a node*

*>>> corresponds to the dominator tree for that node.*

*>>>*

*>> There is no root. This is an arbitrary graph.*

*>*

*> This is from Torczon's book: "In a CFG, node i <dominates> node j if*

*> every path from the entry node to j passes through i". What this tells*

*> us is that we need a root (entry) node.*

Yes, but isn't what Amir is asking for the set of dominator trees

obtained when one chooses each node in turn as the entry node? So any

given node will be the root for one of the trees, but he wants some

way to calculate all of them.

- Brooks

--

The "bmoses-nospam" address is valid; no unmunging needed.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.