A generalized GCD test based affine partitioning algorithm

The Affine partitioning framework unifies many useful program transforms such as unimodular transformations, loop fusion, fission, scaling, reindexing, and statement reordering. The affine partitioning algorithm put forward by the SUIF compiler team has been proved to be successful in automatic discovery of the loop-level parallelization in programs. Generalized GCD Test is a basic dependence testing algorithm. In this paper, we proved that generalized GCD test has a strong relationship with affine partitioning algorithm. Then we presented an improved affine partitioning algorithm based on generalized GCD test. We illustrated that the compiling speed of affine partitioning algorithm can be significantly improved by our method.