Skip to main content
eScholarship
Open Access Publications from the University of California

An algorithm for minimizing spill code in loops

Abstract

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 that performs as well as the exponential approach on typical loops from scientific code. Finally, we examine this algorithm's feasibility in production compilers.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View