List Colouring for Register Assignment

Abstract

This thesis focuses on the register assignment problem. A crucial problem in com- piler optimization is creating an instruction schedule and performing register allocation along with generating a register assignment as well as minimizing and efficiently managing spilling of program variables. Given an instruction schedule, the assigning of variables to registers is known to be synonymous to the classical graph colouring problem. For modern computer architectures with heterogeneous register sets this problem gets generalized to the list colouring problem. This thesis presents an algorithm to produce register assignments by list colouring of the constructed interval graphs. This is done using specific properties of these widely studied sub-class of graphs. The algorithm tested on register assignment instances generated from standard list-coloring test suites in the literature returns almost optimal assignments with the distance from optimal solutions increasing for complex graph structures. The algorithm shows a lot of promise with some directed future work.