Value Numbering

This document presents an implementation of several types of value numbering within the Massively Scalar Compiler Project. Although the name was originally applied to a method for improving single basic blocks, it is now used to describe a collection of optimizations that vary in power and scope. The primary objective of value numbering is to assign an identifying number (a value number) to each expression in a particular way. Two expressions must have the same number if the compiler can prove they are equal for all possible program inputs. These numbers can then be used to find redundant computations and remove them. There are two other objectives accomplished by certain forms of value numbering: 1. To recognize certain algebraic identities, like i = i + 0 and j = j \Theta 1, and to use them to simplify the code and to expand the set of expressions known to be equal. 2. To evaluate expressions whose operands are constants and to propagate their values through the code. There are several ways to accomplish each of these goals, and the methods can be applied across different scopes. The reader should be aware of the partitioning methods, but they will not be implemented here [2, 5, 16]. This document implements a collection of techniques built around hashing. Our approach hashes an operator and the value numbers of its operands to produce a value number for the resulting expression. Hashing provides an efficient representation of the expressions known at any point during the analysis. The efficiency relies on the constant expected-time behavior of hashing. This approach can easily be extended to propagate constants and simplify algebraic identities. We perform value numbering over the static single assignment (SSA) form of the routine [10, 6]. The basic idea used in cons..