28 Nov 2006 00:13:49 -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) |

[6 later articles] |

From: | "s1l3ntr3p" <s1l3ntR3p@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 28 Nov 2006 00:13:49 -0500 |

Organization: | Compilers Central |

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

Keywords: | analysis |

Posted-Date: | 28 Nov 2006 00:13:49 EST |

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

*>*

*> Amir*

*>*

*> > See "Efficiently Computing Static Single Assignment Form and the*

*> > Control Dependence Graph" by Cytron et al.*

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.

Suppose that we have a graph G, directed or not, doesnt matter, and

lets say that i, j are in V(G) (G's vertex set), now 1) i dom j, or 2)

j dom i or 3) neither. How can we know that if we dont have a root

node from where to start?. In teo. all 3 are posible. If we take a

node "n" as a root (the node from which my paths will start) then it

could happen that i dom j. But if we take a node "m", "m \== n" it

could happen that j dom i. So either u have a root node already or u

choose one (it doesnt matter) or u try every posible node, O(V(G) *

O(Dom)). Something like that. But if u do that, I feel that many

cases are going to repeat or it could be like a fixed point algorithm

for all the graph. Domination can be computed using fix point.

Alfredo Cruz

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.