Register Allocation by Evolutionary Algorithm

Graph coloring is a highly effective approach to intraprocedural register allocation. In this paper, we describe a new algorithm for intraprocedural register allocation called HECRA, an algorithm that extends a classic graph coloring register allocator to use a hybrid evolutionary coloring algorithm. The experiments demonstrated that our algorithm is able to minimize the amount of spills, thereby improving the quality of the generated code. Besides, HECRA is interesting in contexts where compile time is a concern, and not only the quality of the generated code.