Low-level code improvement and loop optimizations made simple
Many low-level code and loop optimization techniques can be simplified with the
use of the the Chains of Recurrences (CR) algebra applied to SSA forms of
intermediate code. We applied the method to automatic loop parallelization and
SIMD vectorization. We also implemented the SSA-CR method in GCC 4.1 for
low-level code optimizations and produced better code optimization results
compared to the highest level of optimization in GCC 4.1.
Compiler transformations are applied under strict conditions to ensure the
semantic equivalence of the code before and after a code-optimizing
transformation. The conditions for loop transformations are based on extensive
loop code analysis to find linear and nonlinear induction variables, determine
cross-iteration data dependences, and other loop-related properties. Loop
parallelization for multicore machines gives reasonable speedups, because most
of the execution time of (scientific) applications is spent in loops.
New loop analysis techniques based on the Chains of Recurrences
(CR) algebra are applied to automatic loop parallelization, SIMD
vectorization, and strength reduction. We are also investigating efficient
methods for loop iteration space bounding, with applications to worst-case
execution time (WCET) estimation.