An algorithm for accurate data dependence test

To test if there is a dependence between different iterations in a loop can be converted to checking if there exist integral points in a polyhedron described by a set of linear equations and inequalities. In this paper, a method for accurate data dependence test is proposed. In this method, first, data dependence test problems with any number of linear equations are transformed equivalently to test problems with only one linear equation and constant inequality bounds. Then, a sequence of efficient test methods applicable to test problems with one equation are used in order of their time complexities. If one of those methods succeeds, then stop, if not, a more expensive method is tried. If all those methods do not work, then the tent function method is applied which always gives accurate results. In the proposed tent function method, which is also applicable to any test problems, a nonnegative and piecewise linear function called tent function, is defined on the polyhedron whose minimum value is zero if the polyhedron contains integers. Thus, an integer checking problem is converted to an optimization problem. A piecewise linear program is used to find the minimum value of this tent function