Graph-coloring and treescan register allocation using repairing

Graph coloring and linear scan are two appealing techniques for register allocation as the underlying formalism are extremely clean and simple. This paper advocates a decoupled approach that first lowers the register pressure by spilling variables, and then performs live ranges splitting/coalescing /coloring in a separate phase; this enables the design of simpler, cleaner, and more efficient register allocators. This paper gives a new and more general approach to deal with register constraints. This approach called repairing does not require pre live range splitting and does not introduce additional spill code. It ignores register constraints during coloring/coalescing, and repairs violated constraints afterwards. We applied this method to both graph based and scan based allocators into a decoupled approach. Here, the Iterated Register Coalescer (IRC) and a scan algorithm that uses Static Single Assignment (SSA) properties, the treescan. Moreover, this paper provides a survey on existing and new techniques of bias coloring during scan approaches. Our experimental evaluation shows for the graph based approach, that we reduced the number of vertices (edges) in the interference graph by 26% (33%) without compromising the quality of the generated code. The treescan algorithm improved the compile time of the allocation process by 6:97x over IRC while providing comparable results for the quality of the generated code. Copyright © 2011 ACM