Unified Compiler Framework for Program Analysis, Optimization, and Automatic Vectorization with Chains of Recurrences

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.