Title: A Study of Spilling and Coalescing in Register Allocation as Two Separate Phases
Abstract: The goal of register allocation is to assign the variables of a program to the registers or to spill them to memory whenever there are no register left. Minimizing the spilling is a difficult problem, tightly bounded with the colorability of the program. The SSA form simplifies the coloring by splitting variables : we discovered that it makes the interference graph chordal. Our first goal was to better understand from where the complexity of register allocation does come, and why SSA seems to simplify the problem, by revisiting to the original proof of Chaitin (1981). The difficulty comes from the presence of (critical) edges and the possibility to perform permutations of colors or not. We studied the spill problem under SSA and several versions of the coalescing problem. We used it to design new heuristics to better solve the coalescing problem, so that an aggressive splitting can be used beforehand. This led us to promote a better register allocation scheme : First, spilling to reduce the register pressure to the number of registers, possibly by splitting a lot; Then color the variables and perform coalescing to remove most of the added copies. This scheme is expected to perform well in an aggressive compiler. However, the high number of splits and the increased compilation time required to perform the coalescing is prohibitive for just-in-time (JIT) compilation. So, we devised a heuristic, called permutation motion, that is intended to be used with SSA-based splitting in place of our more aggressive coalescing in a JIT context.