Donald Bren School of Information and Computer Sciences

Loops are the main source of parallelism in applications. The issue of finding an optimal register allocation to loops has been an open issue for some time. In this case optimal refers to the minimization of spills from registers to memory. In this paper we address this issue and present an optimal, but exponential algorithm which allocates registers to loop bodies such that the spill code is minimal. We also show heuristic modifications to the algorithm which perform in practice as well as the exponential approach. Finally, we examine this algorithm's feasibility in production compilers.