SPILL CODE MINIMIZATION VIA INTERFERENCE REGION SPILLING

Many optimizing compilers perform global register allocation using a C haitin-style graph coloring algorithm. Live ranges that cannot be allo cated to registers are spilled to memory. The amount of code required to spill the live range depends on the spilling heuristic used. Chaiti n's spilling heuristic offers some guidance in reducing the amount of spill code produced. However, this heuristic does not allow the partia l spilling of live ranges and the reduction in spill code is limited t o a local level. In this paper, we present a global technique called i nterference region spilling that improves the spilling granularity of any local spilling heuristic. Our technique works above the local spil ling heuristic, limiting the normal insertion of spill code to a porti on of each spilled live range. By partially spilling live ranges, we c an achieve large reductions in dynamically executed spill code; up to 75% in some cases and an average of 33.6% across the benchmarks tested .