Back to search

University of Victoria (Canada)

Isothermality: making speculative optimizations affordable

Abstract

dc:description.abstract

Partial Redundancy Elimination (PRE) is a ubiquitous optimization used by compilers to remove repeated computations from programs. Speculative PRE (SPRE), which uses program profiles (statistics obtained from running a program), is more cognizant of trends in run time behaviour and therefore produces better optimized programs. Unfortunately, the optimal version of SPRE is a very expensive algorithm, of high-order polynomial time complexity, and unlike most compiler optimizations, which run effectively in linear time complexity over the size of the program that they are optimizing. This dissertation uses the concept of “isothermality”—the division of a program into a hot region and a cold region—to create the Isothermal SPRE (ISPRE) optimization, an approximation to optimal SPRE. Unlike SPRE, which creates and solves a flow network for each program expression being optimized—a very expensive operation—ISPRE uses two simple bit-vector analyses, optimizing all expressions simultaneously. We show, experimentally, that the ISPRE algorithm works, on average, nine times faster than the SPRE algorithm, while producing programs that are optimized competitively. This dissertation also harnesses the power of isothermality to empower another kind of ubiquitous compiler optimization, Partial Dead Code Elimination (PDCE), which removes computations whose values are not used. Isothermal Speculative PDCE (ISPDCE) is a new, simple, and efficient optimization which requires only three bit-vector analyses. We show, experimentally, that ISPDCE produces superior optimization than PDCE, while keeping a competitive running time. On account of their small analysis costs, ISPRE and ISPDCE are especially appropriate for use in Just-In-Time (JIT) compilers.

Degree

thesis:*
Level thesis:degree_level
Doctor of Philosophy Ph.D.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pereira, David John
Advisor dc:contributor.supervisor
  • Horspool, R. Nigel

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/292

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pereira, David John. Isothermality: making speculative optimizations affordable. Doctor of Philosophy Ph.D. thesis, 2007. http://hdl.handle.net/1828/292