Precise analysis of array usage in scientific programs

The automatic transformation of sequential programs for efficient execution on parallel computers involves a number of analyses and restructurings of the input. Some of these analyses arebased on computing array sections, a compact description of a range of array elements.Array sections describe the set of array elements that are either read or written by programstatements. These sections can be compactly represented using shape descriptors such asregular sections, simple sections, or generalized convex regions. However, binary operationssuch as Union performed on these representations do not satisfy a straightforward closureproperty, e.g., if the operands to Union are convex, the result may be nonconvex. Approximations are resorted to in order to satisfy this closure property. These approximations introduceimprecision in the analyses and, furthermore, the imprecisions resulting from successive operations have a cumulative effect. Delayed merging is a technique suggested and used in someof the existing analyses to minimize the effects of approximation. However, this techniquedoes not guarantee an exact solution in a general setting. This article presents a generalizedtechnique to precisely compute Union which can overcome these imprecisions.