Value-driven redundancy elimination

Files in this item

Files Size Format View
9631092.PDF 6.720Mb application/pdf Thumbnail

Show full item record

Item Metadata

Title: Value-driven redundancy elimination
Author: Simpson, Loren Taylor
Advisor: Cooper, Keith D.
Degree: Doctor of Philosophy thesis
Abstract: Value-driven redundancy elimination is a combination of value numbering and code motion. Value numbering is an optimization that assigns numbers to values in such a way that two values are assigned the same number if the compiler can prove they are equal. When this optimization discovers two computations that produce the same value, it can (under certain circumstances) eliminate one of them. Code motion is an optimization that attempts to move instructions to less frequently executed locations. Traditional techniques must assume that every definition produces a distinct value. Therefore, an instruction cannot move past a definition of one of its subexpressions. This restriction can be relaxed when certain definitions are known to produce redundant values. By understanding how these two optimizations interact, we can simplify each of them, and the resulting combination will be more powerful than the sum of the two parts. Value numbering will be simpler because it need not be concerned with eliminating instructions, and code motion will be simpler because identifying subexpressions is not necessary. This research investigates this value-driven approach to redundancy elimination. We improve upon the known algorithms for both value numbering and code motion, and we show experimental evidence of their effectiveness.
Citation: Simpson, Loren Taylor. (1996) "Value-driven redundancy elimination." Doctoral Thesis, Rice University.
Date: 1996

This item appears in the following Collection(s)