A sparse algorithm for predicated global value numbering

This paper presents a new algorithm for performing global value numbering on a routine in static single assignment form. Our algorithm has all the strengths of the most powerful existing practical methods of global value numbering; it unifies optimistic value numbering with constant folding, algebraic simplification and unreachable code elimination. It goes beyond existing methods by unifying optimistic value numbering with further analyses: it canonicalizes the structure of expressions in order to expose more congruences by performing global reassociation, it exploits the congruences induced by the predicates of conditional jumps (predicate inference and value inference), and it associates the arguments of acyclic ø functions with the predicates controlling their arrival (ø predication), thus enabling congruence finding on conditional control structures. Finally, it implements an efficient sparse formulation and offers a range of tradeoffs between compilation time and optimization strength. We describe an implementation of the algorithm and present measurements of its strength and efficiency collected when optimizing the SPEC CINT2000 C benchmarks.