20 Dec 2001 00:37:32 -0500

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

From: | Martin.Ward@durham.ac.uk (Martin Ward) |

Newsgroups: | comp.compilers |

Date: | 20 Dec 2001 00:37:32 -0500 |

Organization: | Compilers Central |

References: | 01-12-067 |

Keywords: | analysis, books |

Posted-Date: | 20 Dec 2001 00:37:32 EST |

Robert Sherry <rsherry8@home.com> writes:

*> 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 think that the last part should be "if c is not equal to a then

a dominates c", in which case it would be a correct definition

of the *immediate* dominator.

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

a dominates b in this graph, but e is the immediate dominator of b.

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

This definition is also flawed. Consider the graph:

Nodes{ a, b, c }

Edges{ (a,b), (a,c), (c,b) }

Then a is not the unique predecessor of b (so the first part fails),

and b has a predecessor equal to a, so the second part also fails.

But a clearly dominates b.

Appel ("Modern Compiler Implementation in C") in Section 18.1

on page 413 gives a simple pair of equations for dominators

which basically say that "start" is the only dominator of the start

node, and for all other nodes n, the dominators for n are n plus

the nodes which dominate all predecessors of n:

Dom[start] = {start}

and

Dom[n] = {n} \union ( \Intersection_{p \in pred[n]} Dom[p] )

for n not equal to start.

It seems appropriate here to plug the latest release of the

FermaT Program Transformation System which includes perl modules

for fast computation of immediate dominators, control dependencies

and Static Single Assignment form. It also includes new transformations

for computing SSA form and for forwards and backwards slicing of WSL

using dataflow analysis. See:

http://www.cse.dmu.ac.uk/~mward/martin/software/

Martin

Martin.Ward@durham.ac.uk http://www.cse.dmu.ac.uk/~mward/ Erdos number: 4

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.