Show simple item record

dc.contributor.authorClick, Clifford Noel, Jr.
dc.date.accessioned 2017-08-02T22:03:27Z
dc.date.available 2017-08-02T22:03:27Z
dc.date.issued 1995-02
dc.identifier.urihttps://hdl.handle.net/1911/96451
dc.descriptionThis work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/16807
dc.description.abstract This thesis presents a framework for describing optimizations. It shows how to combine two such frameworks and how to reason about the properties of the resulting framework. The structure of the framework provides insight into when a combination yields better results. Also presented is a simple iterative algorithm for solving these frameworks. A framework is shown that combines Constant Propagation, Unreachable Code Elimination, Global Congruence Finding and Global Value Numbering. For these optimizations, the iterative algorithm runs in O(n2) time. This thesis then presents an O(n log n) algorithm for combining the same optimizations. This technique also finds many of the common subexpressions found by Partial Redundancy Elimination. However, it requires a global code motion pass to make the optimized code correct, also presented. The global code motion algorithm removes some Partially Dead Code as a side-effect. An implementation demonstrates that the algorithm has shorter compile times than repeated passes of the separate optimizations while producing run-time speedups of 4%–7%. While global analyses are stronger, peephole analyses can be unexpectedly powerful. This thesis demonstrates parse-time peephole optimizations that find more than 95% of the constants and common subexpressions found by the best combined analysis. Finding constants and common subexpressions while parsing reduces peak intermediate representation size. This speeds up the later global analyses, reducing total compilation time by 10%. In conjunction with global code motion, these peephole optimizations generate excellent code very quickly, a useful feature for compilers that stress compilation speed over code quality.
dc.format.extent 157 pp
dc.language.iso eng
dc.rights You are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, but this permission is only for a period of forty-five (45) days from the most recent time that you verified that this technical report is still available from the Computer Science Department of Rice University under terms that include this permission. All other rights are reserved by the author(s).
dc.title Combining Analysis, Combining Optimizations
dc.type Technical report
dc.date.note February 1995
dc.identifier.digital TR95-252
dc.type.dcmi Text
dc.identifier.citation Click, Clifford Noel, Jr.. "Combining Analysis, Combining Optimizations." (1995) https://hdl.handle.net/1911/96451.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record