Heuristic Algorithms for Register Allocation

A model to find the optimal register allocation of program variables, including large strongly connected regions (loops), is presented. The program is represented by a directed control flow graph and assumes that all variables have been allocated to memory locations. The model takes into account the cost and saving times involved in allocating variables to registers in each node of the program in order to maximise the global time saving in program execution. As the solution of this model requires exponential resources (both time and space) in the worse case, two heuristic algorithms with O(m) and O(m2) complexities have been developed. Comparisons between the performance of the two heuristic algorithms and the optimal one are made for a set of representative programs.