Constructing DO loops for non-convex iteration spaces in compiling for parallel machines

A need that frequently arises in code generation for shared and distributed memory machines is to scan a region of index points intersected by an integer lattice in their lexicographical order. Methods have been proposed in the special case when the given region is a convex polyhedron. This paper contributes a method in the more general case when the given region is a union of convex polyhedra-a non-convex polyhedron in general. As a secondary contribution, we show the usefulness of this method by presenting its applications in several areas, such as non-singular transformations of nested loops with non-convex iteration spaces, generation of data transfer code for shared memory machines, and generation of SPMD DO loops with communication code for distributed memory machines, where existing methods do not apply. Thus, these various code generation problems can all be unified as one of constructing DO loops to scan a union of convex polyhedra, possibly intersected by a lattice