Although software pipelining has been proposed as one of the most important loop scheduling methods, simultaneous scheduling and register allocation is less understood and remains an open problem [28]. The objective of this paper is to develop a unified algorithmic framework for concurrent scheduling and register allocation to support time-optimal software pipelining. A key intuition leading to this surprisingly simple formulation and its efficient solution is the association of maximum computation rate of a program graph with its  critical cycles  due to Reiter's pioneering work on Karp-Miller computation graphs [29]. In particular, our method generalizes the work by Callahan, Carr and Kennedy on  scalar expansion [6], the work by Lam on  modular variable expansion  for software pipelined loops [20], and the work by Rau et al. on register allocation for modulo scheduled loops[28].
['Qi Ning', 'Guang R. Gao']
A novel framework of register allocation for software pipelining