REGISTER ALLOCATION USING GRAPH NEURAL NETWORKS

International Journal of Computer Science (IJCS) Published by SK Research Group of Companies (SKRGC).

Abstract

The execution lifecycle of a program goes through various optimizations and code generation. Register allocation is critical part of optimization phase of compiler. Graph coloring is one of the NP hard problem and it applies to various applications such as register allocation. Deep Learning methods has various state-of-art techniques in domains like computer vision, natural language processing. In this paper we propose a solution for register allocation problem of compiler using Deep Learning networks based on graphs called as graph neural networks (GNN). We start with basic idea that two connected nodes with temporaries will have different registers allocated.

References

[1] A. V. Aho and J. D. Ullman. Principles of Compiler Design. Addison-Wesley, 19
[2] G. J. Chaitin, 1982. Register allocation and Spilling via
Graph Coloring. Proceedings of the 1982 SIGPLAN
Symposium on Compiler construction - SIGPLAN '82.
[3] M. Prates, P. Avelar, H. Lemos, L. Lamb, and M. Vardi, “Learning to solve NP-complete problems - a graph neural network for decision TSP” arXiv preprint arXiv:1809.02721, 2018.
[4] Preston Briggs, Keith D. Cooper, and Linda Torczon. Rematerialization. ACM SIGPLAN Notices, pages 311–321, 1
[5] Preston Briggs, Keith D. Cooper, and Linda Torczon. Improvements to Graph Coloring Register Allocation. ACM Transactions on Programming Languages and Systems, pages 428–455, 19
[6] Preston Briggs, Keith D. Cooper, Ken Kennedy, and Linda Torczon. Coloring Heuristics for Register Allocation. ACM SIGPLAN Notices, pages 275–284
[7] D. Bernstein, D. Q. Goldin, M. C. Golumbici, H. Krawczykand Y. Mansour, I. Nahshon, and R. Y. Pinter. Spill Code Minimization Techniques for Optimizing Compilers. ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 258–263,
[8] Guei-Yuan Lueh. Issues in Register Allocation by Graph Coloring. Technical Report CMU-CS-96-171, School of Computer Science, 19
[9] S. Thevenin, N. Zufferey, and J. Potvin, “Graph multi-coloring for a job scheduling application,” Discrete App. Math., vol. 234, pp. 218 – 235, 2018.
[10] F. C. Chow and J. L. Hennessy. The Priority-based Coloring Approach to Register Allocation. ACM Transactions on Programming Languages and Systems, pages 501–536, 19
[11] David Callahan and Brian Koblenz. Register Allocation Via Hierarchical Graph Coloring. Conference on Programming Language Design and Implementation, pages 192–203
[12] Peter Bergner, Peter Dahl, David Engebretsen, and Matthew T. O’Keefe. Spill Code Minimization Via Interference Region Spilling. SIGPLAN Conference on Programming Language Design and Implementation, pages 287–295
[13] D. Selsam, M. Lamm, B. Bunz, P. Liang, L. de Moura, and D. Dill, “Learning a sat solver from single-bit supervision,” arXiv preprint arXiv:1802.03685, 2018.
[14] H. Lemos, M. Prates, P. Avelar and L. Lamb, "Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems," 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), 2019, pp. 879-885, doi: 10.1109/ICTAI.2019.00125.
[15] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61–80, 2009. 

Keywords

Register allocation, graph coloring, graph neural networks.