Partial Redundancy Elimination for Global Value Numbering

VanDrunen, Thomas John

Abstract

Partial redundancy elimination (PRE) is a program transformation that removes operations that are redundant on some execution paths, but not all. Such a transformation requires the partially redundant operation to be hoisted to earlier program points where the operation’s value was not previously available. Most well-known PRE techniques look at the lexical similarities between operations.

Global value numbering (GVN) is a program analysis that categorizes expressions in the program that compute the same static value. This information can be used to remove redundant computations. However, most widely-implemented GVN analyses and related transformations remove only computations that are fully redundant.

This dissertation presents new algorithms to remove partially redundant computations in a value-based view of the program. This makes a hybrid of PRE and GVN. The algorithms should be simple and practical enough to be implemented easily as optimization phases in a compiler. As far as possible, they should also to show true performance improvements on realistic benchmarks.

The three algorithms presented here are: ASSAPRE, a PRE algorithm for programs in a form useful for GVN; GVNPRE, the hybrid algorithm for value-based PRE; and LEPRE, an approximate PRE technique for object and array loads.

@phdthesis{VanDrunen2004PhD,
  author = {VanDrunen, Thomas John},
  title = {Partial Redundancy Elimination for Global Value Numbering},
  school = {Purdue University},
  year = {2004},
  type = {PhD dissertation},
  month = {August}
}