Show simple item record

dc.contributor.advisor Cooper, Keith D.
dc.creatorGrosul, Alexander
dc.date.accessioned 2009-06-04T08:42:44Z
dc.date.available 2009-06-04T08:42:44Z
dc.date.issued 2005
dc.identifier.urihttps://hdl.handle.net/1911/18844
dc.description.abstract It has long been known that the quality of the code produced by an optimizing compiler is dependent upon the ordering of transformations applied to the code. In this dissertation, we show that the best orderings vary in unpredictable ways according to the properties of the input code and performance objectives, making adaptation a necessity to obtain the best results. We further demonstrate the most practical techniques to search the spaces of transformation orderings. Our analysis of six exhaustively enumerated subspaces of limited size determines the choice and parameters of search algorithms described and implemented in this work: random sampling, greedy methods, variations of the stochastic hillclimber, and genetic algorithms. We then apply the search algorithms to the full spaces of all available transformations, which are too big to enumerate. We evaluate the performance and cost of running these algorithms and discuss the tradeoffs between the quality of discovered orderings and an effort to find them. Stochastic hillclimbers discover effective orderings within approximately 500 evaluations. Compared to a fixed ordering of transformations, they result in 5%--40% improvements for a variety of input programs and performance objectives. To reduce the computational overhead in finding these orderings, we introduce and analyze a novel approach to precise static estimation of runtime frequencies of basic blocks. Termed "Estimated Virtual Execution", this approach reduces the search time by 40%--60%.
dc.format.extent 268 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectComputer science
dc.title Adaptive ordering of code transformations in an optimizing compiler
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
dc.identifier.citation Grosul, Alexander. "Adaptive ordering of code transformations in an optimizing compiler." (2005) Diss., Rice University. https://hdl.handle.net/1911/18844.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record