A Polynomial-Time Algorithm for Global Value Numbering
Abstract
We describe a polynomial-time algorithm for global value numbering,
which is the problem of discovering equivalences among program
sub-expressions. We treat all conditionals as non-deterministic and
all program operators as uninterpreted. We show that there are
programs for which the set of all equivalences contains terms whose
value graph representation requires exponential size. Our algorithm
discovers all equivalences among terms of size at most $s$ in time
that grows linearly with $s$. For global value numbering, it suffices
to choose $s$ to be the size of the program. Earlier deterministic
algorithms for the same problem are either incomplete or take
exponential time.