Parameterization and adaptive search for graph coloring register allocation

Abstract

Graph coloring register allocators use heuristics for register coalescing and allocation, which are relevant to the number of physical registers that a group of virtual registers will use after allocation. They cannot be determined accurately in allocation, thus we made them tunable by introducing new parameters as the thresholds for coalescing and the thresholds for defining constrained live intervals in simplification. Experiments demonstrated neither the aggressive method nor the conservative method can outperform the other for all tests and the best parameters vary significantly among programs. This parameterization is profitable because the best running time reached by varying the parameters is up to 16% faster than the best of fixed-parameter methods. Hill-climbing and random probe algorithms were used to find good parameters, and the later performed better. Further analysis reveals the search space has many irregular fluctuations that are not suitable for the hill-climber.