VALUE NUMBERING

Value numbering is a compiler-based program analysis method that allow s redundant computations to be removed. This paper compares hash-based approaches derived from the classic local algorithm(1) with partition ing approaches based on the work of Alpern, Wegman and Zadeck.(2) Hist orically, the hash-based algorithm has been applied to single basic bl ocks or extended basic blocks. We have improved the technique to opera te over the routine's dominator tree. The partitioning approach partit ions the values in the routine into congruence classes and removes com putations when one congruent value dominates another. We have extended this technique to remove computations that define a value in the set of available expressions (AVAIL).(3) Also, we are able to apply a vers ion of Morel and Renvoise's partial redundancy elimination(4) to remov e even more redundancies. The paper presents a series of hash-based al gorithms and a series of refinements to the partitioning technique. Wi thin each series, it can be proved that each method discovers at least as many redundancies as its predecessors. Unfortunately, no such rela tionship exists between the hash-based and global techniques. On some programs, the hash-based techniques eliminate more redundancies than t he partitioning techniques, while on others, partitioning wins. We exp erimentally compare the improvements made by these techniques when app lied to real programs. These results will be useful for commercial com piler writers who wish to assess the potential impact of each techniqu e before implementation. (C) 1997 by John Wiley & Sons, Ltd.