FINDING THE MAXIMUM GRID CONVEX POLYGON FOR A CONVEX-REGION ON THE PLANE

Dependence analysis in parallelizing compilers can be formulated as so lving a set of Diophantine equations and a set of linear inequalities. The intersection of the linear inequalities is usually a convex regio n in the iteration space. For more precise data dependence analysis, w e need to enumerate or at least find the ''tightest'' boundary of the grid points (i.e., iterations) inside the convex region. The region bo unded by this tightest boundary is called the maximum grid convex poly gon (MGCP). It is the largest convex polygon inside the convex region in which the corners are integer-valued and all the integer points sat isfying the given linear inequalities are enclosed. In this paper, we consider the problem of finding the MGCP on a two-dimensional grid pla ne, and we give an algorithm with a time complexity O(max(m, K)L + m l og m), where K is the number of corners of the found MGCP, m is the nu mber of the given constraints, and L is the maximum length of the bina ry representation of the coefficients. As a side step of the algorithm , we can decide whether an integer solution exists in the convex regio n, and thus whether a dependence actually exists. Also with the MGCP, we can determine precisely the region of the flow and anti-dependence vectors. This information is very useful in loop parallelism. (C) Else vier Science Inc. 1997.