IMPROVEMENTS TO GRAPH-COLORING REGISTER ALLOCATION

We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The second extends Ch aitin's treatment of rematerialization to handle a larger class of val ues. These techniques are complementary. Optimistic coloring decreases the number of procedures that require spill code and reduces the amou nt of spill code when spilling is unavoidable. Rematerialization lower s the cost of spilling some values. This paper describes both of the t echniques and our experience building and using register allocators th at incorporate them. It provides a detailed description of optimistic coloring and rematerialization. It presents experimental data to show the performance of several versions of the register allocator on a sui te of FORTRAN programs. It discusses several insights that we discover ed only after repeated implementation of these allocators.