An Approach to Register Number Determination Based on Simulation of Register Allocation via Graph Colouring

Abstract

An important task in most optimising compilers is register allocation i.e. deciding which program variables will use physical registers of processors. Register allocation may be formulated as a graph colouring problem. The nodes in the interference graph represent variables, and two nodes are connected by an edge if variables they represent are simultaneously live. The allocation process is successful if the graph can be coloured so that adjacent nodes are assigned different colours. The number of colours is determined by the number of available registers. Based on simulation of the register allocation procedure via graph colouring this paper discusses the necessary number of registers for storing variables within a single procedure.