Value numbering: RPO vs SCC-based algorithm

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

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