Value numbering: RPO vs SCC-based algorithm (Steven Bosscher) 23
Sep 2003 13:26:49 -0400            From comp.compilers  Related
articles Value numbering: RPO vs SCC-based algorithm
(2003-09-23) | List of all articles for this month |  From:
(Steven Bosscher) Newsgroups: comp.compilers Date: 23 Sep 2003
13:26:49 -0400 Keywords: analysis, question Posted-Date: 23 Sep
2003 13:26:48 EDT   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