29 Nov 2006 11:51:18 -0500

Related articles |
---|

[2 earlier articles] |

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

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

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

[2 later articles] |

From: | Hans-Peter Diettrich <DrDiettrich1@aol.com> |

Newsgroups: | comp.compilers |

Date: | 29 Nov 2006 11:51:18 -0500 |

Organization: | Compilers Central |

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

Keywords: | analysis |

Amir Michail wrote:

*> But maybe there's a more efficient way (even though the relationship*

*> between these dominator trees may not be obvious in general).*

I'm not sure what you mean with dominator "trees". Isn't it sufficient

to find the immediate dominator for each each node, in order to create

any other dominator structure subsequently? AFAIR all the basic

algorithms are O(n).

A root node is not normally required by graph algorithms, the only

requirement IMO is an ordered list of all nodes. Within that list more

orders can be implemented, e.g. by (reverse) DFS numbering, to simplify

procedures like finding dominators.

The results of properly implemented algorithms are independent from any

order of the nodes. For completeness: A graph can have zero or more

"root" nodes, which are not reachable from any other nodes. There can

exist singletons and isolated subgraphs, too, which must be treated as

separate graphs.

DoDi

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.