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. We provide a detailed analytical comparison of some
of these algorithms.