Some of the material in is restricted to members of the community. By logging in, you may be able to gain additional access to certain collections or items. If you have questions about access or logging in, please use the form on the Contact Page.
In this dissertation a unified compiler framework for program analysis, optimization, and automatic vectorization with techniques based on the Chains of Recurrences (CR) algebra is proposed. The root theoretical foundations of the CR algebra and the CR# additions for program analysis, that is specifically developed for this dissertation research, are given. Based on the theory, an extension of the Single Static Assignment (SSA) form, called the Inductive SSA form, is proposed. The form associates inductive proofs with SSA variables to describe their inductive properties. The proofs are derived with algorithms based on the CR# theory. Inductive SSA provides an internal program representation that facilitates more effective loop analysis by a compiler. Based on the Inductive SSA form, a collection of compiler algorithms for program optimization at the SSA level is described and evaluated. More specifically, Inductive SSA merges static SSA information with semantic recurrence information to describe the value progressions of loop-variant variables. We will show how Inductive SSA enables and/or enhances loop-variant variable analysis, improves dependence testing for loops, and how it can be effectively used by many classic compiler optimizations to improve compilation results. Inductive SSA is based on our theoretical work on extending the CR formalism by the CR# (CR-sharp) algebra and lattice to effectively represent the value sequences and value ranges of conditionally updated variables in loops. Using empirical results on SPEC benchmarks with GCC 4.1, we will show that the Inductive SSA form captures more recurrence relations compared to state-of-the-art induction variable recognition techniques. Because the CR# term rewriting system is complete (confluent and terminating), it can be used for congruence detection in programs at all optimization levels. The Inductive SSA program analysis is far less sensitive to syntactical code changes, due to the real semantic information it captures. As a result of the independence of code structure, the phase ordering problem, in which multiple optimizing transformations can be ordered based on their effect on enabling or disabling other transformations, is greatly alleviated with Inductive SSA for many traditional low-level and loop-level optimizations. The experimental results show that the effectiveness of loop-variant variable analysis, congruence detection, and loop optimizations can be significantly increased with Inductive SSA. For this dissertation research a math function library generator is also developed. Many computational tasks require repeated evaluation of functions over structured grids, such as plotting in a coordinate system, rendering of parametric objects in 2D and 3D, numerical grid generation, and signal processing. The library generator speeds up closed-form function evaluations over grids by vectorizing the CR forms of these functions. The approach is comparable to aggressive strength reduction and short-vector vectorization of the resulting CRs. Strength reduction of floating point operations is usually prevented in a compiler due to safety issues related to floating point roundoff. Auto-tuning of the library ensures safe floating point evaluation. Experiments show significantly improved execution of streaming SIMD extensions (SSE) and instruction-level parallelism (ILP) of math function evaluations.
Congruence Detection, Short Vector SIMD, Vectorization, CR#, Induction Variable, Chains of Recurrences, Inductive SSA, Loop Optimization
Date of Defense
April 8, 2009.
A Dissertation Submitted to the Department of Computer Science in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy.
Includes bibliographical references.
Florida State University
Use and Reproduction
This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). The copyright in theses and dissertations completed at Florida State University is held by the students who author them.