A question about Dominators

"Robert Sherry" <rsherry8@home.com>
15 Dec 2001 00:38:53 -0500

          From comp.compilers

Related articles
A question about Dominators rsherry8@home.com (Robert Sherry) (2001-12-15)
Re:A question about Dominators kvinay@ip.eth.net (kvinay) (2001-12-20)
Re: A question about Dominators vbdis@aol.com (2001-12-20)
Re: A question about Dominators Martin.Ward@durham.ac.uk (2001-12-20)
Re: A question about Dominators sweeks@acm.org (2001-12-20)
Re: A question about Dominators jeremy.wright@merant.com (Jeremy Wright) (2001-12-20)
| List of all articles for this month |

From: "Robert Sherry" <rsherry8@home.com>
Newsgroups: comp.compilers
Date: 15 Dec 2001 00:38:53 -0500
Organization: Excite@Home - The Leader in Broadband http://home.com/faster
Keywords: analysis, books, question
Posted-Date: 15 Dec 2001 00:38:52 EST

        The following paragraph is from the book Advanced Compiler Design
Implementation by Steven S. Muchnick. I can be found on page 182.


        We give two approaches to computing the set of dominators of each node
in a flowgraph. The basic idea of the first approach is that node a
dominates node b if and only if a=b or a is the unique immediate predecessor
of b or b has more then one immediate predecessor and for all immediate
predecessors c of b, c is not equal to a and a dominates c.


        I believe that the above statement is incorrect. Please consider the
following flowgraph.
                Nodes{ a, b, c, d, e }
                Edges{ (a,c), (a,d), (c,e), (d,e), (e,b) )
                a is the start node


In this case, a dominates b. However, it violates the if and only if given
above since b has a unique predecessor. The believe the correct statement
would be:


                The basic idea of the first approach is that node a dominates
node b if and only if a=b or a is the unique immediate predecessor of
b or for all immediate predecessors c of b, c is not equal to a and a
dominates c.


Please comment.


                                                                                                        Robert Sherry


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.