Minimization of Instructions to Access Memory by Color Flipping in the Interference Graph

Graph coloring is one of the most effectiveness approaches to perform register allocation. This work describes a new approach to flip colors in an interference graph to minimize the code insertion for accessing memory. To evaluate the impact of using this strategy in the graph coloring register allocator, a George and Appel allocator has been developed in two ways - flipping the colors and without flipping the colors in the interference graph. Experiments with a set of 27,921 graphs of real programs were performed. In some cases, our results showed over 12% of reduction in number of variables sent to memory