Compiler PhD Thesis Available

At long last, the _final_ version of my Ph.D. thesis is available.
You can find it at


    ftp://cs.rice.edu/public/cliffc/thesis.ps.gz


or on a link from


    http://bellona.cs.rice.edu/MSCP/cliff.html


If you have a problem with these sites, email me and we'll make
other arrangements.


Cliff
-------------------------------------------------------------------------------
Cliff Click HP Laboratories Scientist
Cambridge Research Office, Hewlett-Packard Laboratories
1 Main Street, 10th Floor (617) 225-4915 Work
Cambridge, MA 02142 (617) 225-4930 Fax
cliffc@hpl.hp.com
-------------------------------------------------------------------------------




                                                      Combining Analyses,


                                                  Combining Optimizations


                                                  Clifford Noel Click, Jr.


                                                                  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(n^2) 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 conjunc-
tion with global code motion, these peephole optimizations generate
excellent code very quickly, a useful feature for compilers that stress
compilation speed over code quality.


--

Return to the comp.compilers page.
Search the comp.compilers archives again.