Deep Learning-based Hybrid Graph-Coloring Algorithm for Register Allocation
This addresses register allocation, a key compiler optimization problem, with an incremental hybrid approach combining deep learning and traditional methods.
The paper tackles register allocation in compilers by developing a hybrid deep learning-based graph coloring algorithm that outputs colors for nodes, followed by a correction phase to ensure valid coloring. It performs on par or better than LLVM's greedy allocator on SPEC CPU 2017 benchmarks and matches optimal coloring for graphs with up to 100 nodes.
Register allocation, which is a crucial phase of a good optimizing compiler, relies on graph coloring. Hence, an efficient graph coloring algorithm is of paramount importance. In this work we try to learn a good heuristic for coloring interference graphs that are used in the register allocation phase. We aim to handle moderate sized interference graphs which have 100 nodes or less. For such graphs we can get the optimal allocation of colors to the nodes. Such optimal coloring is then used to train our Deep Learning network which is based on several layers of LSTM that output a color for each node of the graph. However, the current network may allocate the same color to the nodes connected by an edge resulting in an invalid coloring of the interference graph. Since it is difficult to encode constraints in an LSTM to avoid invalid coloring, we augment our deep learning network with a color correction phase that runs after the colors have been allocated by the network. Thus, our algorithm is hybrid in nature consisting of a mix of a deep learning algorithm followed by a more traditional correction phase. We have trained our network using several thousand random graphs of varying sparsity. On application of our hybrid algorithm to various popular graphs found in literature we see that our algorithm does very well when compared to the optimal coloring of these graphs. We have also run our algorithm against LLVMs popular greedy register allocator for several SPEC CPU 2017 benchmarks and notice that the hybrid algorithm performs on par or better than such a well-tuned allocator for most of these benchmarks.