Patent ID: 7877739

Claim:
A computer-implemented method for determining whether an array within a loop can be privatized for that loop, the method comprising: (a) identifying target regions within an array, the target regions being accessible by a loop with access to the target regions being controlled by a guard, the identifying includes identifying a first set of the target regions that includes elements of the array that may be overwritten, the identifying includes identifying a second set of the target regions that includes elements of the array that will be overwritten, the identifying includes identifying a third set of the target regions that includes elements of the array that have a use not preceded by a definition along a path from a header of the loop, the identifying includes identifying a fourth set of the target regions that includes elements of the array that are accessible by code intended to be executed after the loop has been executed; (b) determining, in any iteration of the loop, if a target region in the first set of the target regions overlaps any of the target regions in the third set of the target regions; (c) when the target region in the first set of the target regions has been determined not to overlap any of the target regions in the third set of the target regions, determining, in any iteration of the loop, if the target region in the first set of the target regions overlaps any of the target regions in the fourth set of the target regions; (d) when the target region in the first set of the target regions has been determined to overlap any of the target regions in the fourth set of the target regions, determining, over all iterations of the loop, if the first set of the target regions is contained in the second set of the target regions; (e) when the first set of the target regions has been determined to be contained in the second set of the target regions, marking as private the target region in the first set of target regions that has been determined to overlap any of the target regions in the fourth set of target regions, ensuring that each of the target regions in the second set of target regions is marked as last private and that each of the target regions in the third set of target regions is marked as first private; and (f) repeating steps (c)-(e) for a each of the other target regions in the first set of target regions.