A Learning-based Coloring Algorithm for Register Allocation Problem

Abstract

The register allocation problem involves assigning variables in a program to physical registers in a computer's processor. It can be modeled as a weighted node coloring problem by representing each variable as a node in a graph and assigning a weight to each node corresponding to the number of times the variable is used in the program. The purpose of the problem is to allocate all the variables in the program to the least number of registers. In this study, a learning-based coloring algorithm was designed to solve the problem. The performance of the proposed work has been tested on DIMACS samples by comparing it with the leading evolutionary algorithms in the literature. Experimental studies show that the proposed learning-based coloring algorithm achieves the best results for DIMACS instances in a shorter time than evolutionary algorithms in the literature.