Abstract/Details

Partial redundancy elimination for global value numbering


2004 2004

Other formats: Order a copy

Abstract (summary)

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.

Indexing (details)


Subject
Computer science
Classification
0984: Computer science
Identifier / keyword
Applied sciences; Compilers; Global value numbering; Programming languages; Redundancy elimination
Title
Partial redundancy elimination for global value numbering
Author
VanDrunen, Thomas John
Number of pages
138
Publication year
2004
Degree date
2004
School code
0183
Source
DAI-B 65/11, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
9780496153107, 0496153102
Advisor
Hosking, Antony L.
University/institution
Purdue University
University location
United States -- Indiana
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
3154748
ProQuest document ID
305152109
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/305152109
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.