Symbolic expression evaluation to support parallelizing compilers.
Thomas Fahringer · 1997
Symbolic analysis is of paramount importance to further advance the state-of-the-art of parallelizing compilers. The quality of various compiler analyses and optimizing code transformations depend on the ability to evaluate symbolic expressions for equality and inequality (=; !; ?) relationships. This paper describes a powerful algorithm that computes lower and/or upper bounds of wide classes of linear and non-linear symbolic expressions given a set of constraints on loop variables and loop invariants. The algorithm is used to compare symbolic expressions, examine non-linear array index functions for data dependences, and simplify systems of constraints. Among others the algorithm supports dependence analysis, detecting zero-trip-loops, dead code elimination, and performance prediction. We have implemented the algorithm and use it as part of a parallelizing compiler and a static performance estimator. 1 Introduction Many parallelizing compilers fail to effectively parallelize program...