5 Dec 2006 06:19:39 -0500

Related articles |
---|

[6 earlier articles] |

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

Re: finding all dominator trees mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-12-06) |

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

From: | "Amir Michail" <amichail@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 5 Dec 2006 06:19:39 -0500 |

Organization: | Compilers Central |

References: | 06-11-09606-11-131 06-12-025 06-12-033 |

Keywords: | analysis |

Posted-Date: | 05 Dec 2006 06:19:39 EST |

diablovision@yahoo.com wrote:

*> Amir Michail wrote:*

*> > ...*

*> > I don't understand this solution. How would it work in this example?*

*> >*

*> > A -> B <-> C*

*> >*

*> > The dominator tree for A:*

*> >*

*> > A*

*> > |*

*> > B*

*> > |*

*> > C*

*> >*

*> > The dominator tree for B:*

*> >*

*> > B*

*> > |*

*> > C*

*> >*

*> > The dominator tree for C:*

*> >*

*> > C*

*> > |*

*> > B*

*>*

*> The problem seems to be the definition of dominance. Dominance in*

*> compiler land is defined with respect to some (already chosen) root*

*> node, because the definition states that a node X dominates Y iff every*

*> path from the root node R to Y goes through node X.*

*>*

*> In your example, the dominator tree for C is not correct if we chose A*

*> to be the root node. C cannot dominate B because there exists a path*

*> from A to B that does not go through C (the direct path).*

*>*

But we don't choose A to be the root. In my problem, the dominator tree

for a node X is determined by taking X as the root. So a simple way to

get what I want is to run a dominator tree algorithm with respect to

each node in the graph taken as root, but I was hoping there would be a

more efficient way to do this. And as part of this more efficient

algorithm, maybe we could have an efficient way of storing all of these

dominator trees, as they may share some common parts.

*> I'm not sure what property you are going after in the general graph*

*> problem, but the standard definitions of dominance (in compiler land)*

*> are going to assume the existence of a unique root node.*

*>*

*> Perhaps if you collapse cycles (do a SCC decomposition) of your graph*

*> first, and consider cyclic structures to be a single node, the*

*> resulting DAG can be sorted topologically, and the top node can be*

*> considered the root?*

Why would this help in my problem?

*>*

*> Because, in truth, the dominance relation doesn't make any sense unless*

*> you have either or both of the following conditions:*

*>*

*> 1. a unique entry node.*

*> 2. an acyclic graph.*

*>*

My problem is well defined as discussed above, although it's a bit

different from what people normally do in compilers.

Amir

*> Hope this helps.*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.