A spill code minimization technique - Application in the Metrowerks StarCore C compiler
Graph coloring algorithms have been shown to be an efficient and effective means of performing register allocation. The power of these algorithms lies in their strong coloring heuristics and their ability to abstract away disparate allocation problems such as data-flow constraints, conforming to calling conventions, and target machine restrictions. However, even optimal algorithms cannot color every graph, and often some live ranges must be spilled to memory to make room for others. In this paper, we present a new approach of reducing spill code, which can be used to complement virtually any register allocation algorithm, and provides a good support to implement cheaper spill methods like spilling to another register (from a different class) and rematerialization (reloading the register from a constant or expression). This algorithm was partially implemented into the Metrowerks StarCore C compiler where it has proven its efficiency in terms of both cycle count and code size.
spill code register allocation optimization rematerialization