Register Allocation sans Coloring

The time spent on register allocation must be reasonable compared to other global optimizations in a compiler. While graph coloring is an excellent abstraction for global register allocation, it incurs high overhead with respect to both memory consumption and compile time. We describe a new algorithm for global register allocation called fast allocation to address this problem. Fast allocation avoids graph coloring but achieves a global allocation by allocating and assigning registers in two passes -- a local pass and a global pass. While it affects the execution time performance of codes, the fast allocator is attractive when one seeks a reasonable balance between compile and execute time. Experimental results of an implementation of fast allocation are presented to validate our claim. Keywords: register allocation, graph coloring, interference graph, data flow analysis, live ranges, coalescing, instruction scheduling. Make it as simple as possible but not simpler. Albert Einstein 1..