Hardness and Algorithms for Local Register Allocation

We study the problem of local register allocation (LRA): assign pseudo-registers to actual registers in a basic block so as to minimize the spill cost. Our version of LRA does not allow instruction scheduling, but only the insertion of spill code. We assume that the spill cost depends only on the number and type of load and store operations, but not on their position. Although LRA has been intensively studied, very little was known about it. LRA could be solved exactly by an algorithm that took exponential time and space. On the other hand, LRA was not known to be NP-hard. LRA could be solved by heuristics, but the relative performance of those heuristics was unclear. In this paper, We prove that LRA is NP-hard. We describe the rst space- and time-efficient optimum algorithm. We propose a new heuristics for LRA which we call Conservative-Furthest-First (CFF). We conduct detailed experiments on common benchmarks. We compare the optimum algorithm, the heuristics Furthest-First (FF), Clean-First (CF), and CFF. We obtain statistics on the running time of the allocators and on the dynamic instruction count of the compiled code. CFF is the best suboptimal heuristic under both performance measures.Technical report DCS-TR-33