23 Sep 2003 13:26:49 -0400

Related articles |
---|

Value numbering: RPO vs SCC-based algorithm s.bosscher@student.tudelft.nl (2003-09-23) |

From: | s.bosscher@student.tudelft.nl (Steven Bosscher) |

Newsgroups: | comp.compilers |

Date: | 23 Sep 2003 13:26:49 -0400 |

Organization: | http://groups.google.com/ |

Keywords: | analysis, question |

Posted-Date: | 23 Sep 2003 13:26:48 EDT |

Hello,

Does anyone have a comparison of the RPO and SCC-based value numbering

algorithms? Both algorithms should find the same partitioning and have

the same time complexity in theory, but it is claimed that the RPO

algorithm is less efficient. I'd like to know if anyone has ever

actually compared their efficiency experimentally...

Both algorithms are described in "Value-driven redundancy

elimination", Taylor Simpsons PhD. thesis. Simpson claims that the SCC

algorithm is more efficient than the RPO algorithm, which seems

obvious since the SCC algorithm only iterates on the vertices of SCCs

of the SSA graph, instead of over the whole flow graph.

But why, then, did the same people (at Rice) who "invented" the

SCC-based value numbering algorithm, actually implement the RPO

algorithm for the SGI Pro64 compiler (now ORC/Open64/etc.)?

In his experimental results, Simpson doesn't test the RPO algorithm,

so the reader can't verify his claim. Robert Morgan also mentions the

RPO algorithm (well, he talks about "iterating over the flow graph")

and then just states that "this is inefficient", and goes on to

describe the SCC-based algorithm. Googling for some comparison of the

two algorithms also doesn't help.

Anyone ever seen such a comparison?

Gr.

Steven

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.