Show simple item record

dc.contributor.advisor Cooper, Keith D.
dc.contributor.advisor Kennedy, Ken
dc.creatorDasgupta, Anshuman
dc.date.accessioned 2009-06-03T21:07:58Z
dc.date.available 2009-06-03T21:07:58Z
dc.date.issued 2007
dc.identifier.urihttp://hdl.handle.net/1911/20595
dc.description.abstract Runtime compilation, due to its online nature, presents unique challenges and opportunities to compiler designers. Since compilation occurs during program execution, a just-in-time compiler (JIT) must be judicious in expending compilation time. The literature on traditional, offline compilers describes numerous program transformation techniques that strive to increase execution efficiency. However, while optimization passes for static compilers are well understood and have been thoroughly investigated, many such transformation algorithms cannot be implemented on a JIT environment due to compilation-time constraints. Further, offline algorithms are not designed to exploit information available to an online compiler at program execution time. The thesis of the research presented in this document is that program optimization techniques designed for traditional, offline compilers can be profitably adapted for a runtime compiler by effectively respecting the constraints imposed on compilation time and by exploiting the opportunities available in a runtime compilation environment. To that end, the dissertation explores the complexity of implementing program transformations for a runtime compiler and redesigns two optimization techniques for a JIT: register allocation and loop unrolling. The two transformations present contrasting challenges when they are included in a runtime compiler. While several offline, heuristic allocation algorithms achieve impressive results, they consume large amounts of compilation-time that are typically unacceptable for a JIT. We describe the design of two allocation algorithms that reduce allocation time while preserving the advantages of strong techniques authored for offline compilers. An experimental evaluation of the new algorithms demonstrates their effectiveness on a runtime compilation environment. While a runtime compiler is limited by the constraints imposed by its environment, compiling just prior to program invocation provides certain advantages over an offline compiler. In particular, it can examine information only available at program execution time. We describe the design of a lightweight runtime value-examining mechanism and a loop unrolling algorithm that work in tandem. Our experimental results indicate that the runtime unroller achieves significant improvements on floating point, scientific benchmarks. In summary, thus, the research described in this dissertation demonstrates how compiler optimization algorithms can be effectively tailored for runtime compilation.
dc.format.extent 125 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectComputer science
dc.title Tailoring traditional optimizations for runtime compilation
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record