A Nonlinear Array Subscripts Dependence Test

Linear dependence tests determine the dependences with linear array subscripts, but only give the passive results for those with nonlinear ones. That is to say, dependences exist as long as there are nonlinear cases, which may lead to pseudo-dependences. However, to maximize the parallelism of applications and improve the credibility of the optimizing compiler, it is necessary to develop a nonlinear dependence test to eliminate the pseudo-dependences. By analyzing the optimal solution of the quadratic subscripts with the indexes bounds constraints, a new nonlinear dependence test was proposed. We theoretically proved that the nonlinear dependences satisfying the quadratic programming model can be determined, and introduced a nonlinear dependence testing algorithm based on quadratic programming. Effectiveness of this algorithm was verified at the end.