On minimizing register usage of linearly scheduled algorithms with uniform dependencies

In this paper, we discuss an approach to minimize register pressure of loop nests with regular dependencies through the use of linear schedules in conjunction with loop unrolling. Linear scheduling is a method of partitioning the indexes of loop nests into a series of hyperplanes defined by a vector parameter Π. Once a suitable linear schedule has been discovered, the loop nest will be unrolled in a way that satisfies Π. For each linear schedule, we determine the minimum number of registers needed by the loop nest to avoid spilling (i.e. each variable is loaded into a register exactly once during a loop nest). In the case where the loop nests contains variables with at most one dependence we present a method to estimate the number of registers used. Otherwise we employ a more general method to determine the exact register requirements. Our experimental results indicate that an optimal linear schedule uses 36% fewer register than a schedule that uses the most registers on average.