Optimal register allocation and assignment for loops

This paper presents a new technique for the problem of allocating and assigning registers to variables in loops. Traditionally, cyclic variables (variables written in the current iteration and read in subsequent iterations) are split at the loop boundary and treated as separate variables during register allocation and assignment. When these split variables are not assigned to the same register, register copy operations are necessary to match the register usages at the beginning and end of a loop iteration. Register copy operations, which are inherently overhead operations, have an adverse impact on the quality of the final design both in area (extra hardware—registers, busses—may be necessary) and in performance (register copy operations lengthen the schedule). Therefore, it is desirable to eliminate these spurious copy operations. In this paper, we describe a novel technique that incorporates loop unrolling into an assignment algorithm so that cyclic variables are used directly in subsequent iterations without requiring additional register copy operations, and also without requiring more registers than that used by the left-edge algorithm. We conducted experiments on some core numerical and image algorithms and observed optimal allocation