Simplifying Polynomial Constraints Over Integers to Make Dependence Analysis More Precise

Abstract

Why do existing parallelizing compilers and environments fail to parallelize many realistic FORTRAN programs? One of the reasons is that these programs contain a number of linearized array references, such as {\tt A(M*N*i+N*j+k)} or {\tt A(i*(i+1)/2+j)}. Performing exact dependence analysis for these references requires testing polynomial constraints for integer solutions. Most existing dependence analysis systems, however, restrict themselves to solving affine constraints only, so they have to make worst-case assumptions whenever they encounter a polynomial constraint. In this paper we introduce an algorithm which exactly and efficiently solves a class of polynomial constraints which arise in dependence testing. Another important application of our algorithm is to generate code for loop transformation known as symbolic blocking (tiling). (Also cross-referenced as UMIACS-TR-93-68.1)