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}
}