A new practical array data dependence analysis for parallelizing compilers

Data dependence analysis is essential for automatic parallelizing compilers. Compilers determine the possibility of parallelization on given source programs by using the result from data dependence analysis. Several dependence analysis tests on array data have been already proposed. Each test cannot avoid the trade-off between its analysis speed and exactness of analysis. Among such tests, the Omega test is well known as an exact test for the broader class of index expressions. However, the Omega test algorithm is so complicated that its analysis is very time consuming and it is difficult to implement the Omega test. Therefore, in this paper a new original test is proposed, whose algorithm combines both the Simplex method for linear programming and an exhaustive solution search method. The algorithm, its implementation details, and evaluation applied to concrete numerical programs are also described.