EXTENSIONS TO CYCLE SHRINKING

An important part of a parallelizing compiler is the restructuring pha se, which extracts parallelism from a sequential program. We consider an important restructuring transformation called cycle shrinking [5], which partitions the iteration space of a loop so that the iterations within each group of the partition can be executed in parallel. The me thod in [5] mainly deals with dependences with constant distances. In this paper, we propose certain extensions to the cycle shrinking trans formation. For dependences with constant distances, we present an algo rithm which, under certain fairly general conditions, partitions the i teration space in a minimal number of groups. Under such conditions, o ur method is optimal while the previous methods are not. We have also proposed an algorithm to handle a large class of loops which have depe ndences with variable distances. This problem is considerably harder a nd has not been considered before in full generality.