Register Allocation via Hierarchical Graph Coloring

Register allocation is a vital stage in compiler optimization. It greatly impacts the effectiveness of other compiler optimization techniques. Graph coloring is the commonly used mechanism for register allocation. Since graph coloring is an NP-complete problem, heuristics are needed to find a practical solution. Several heuristics are available that perform well in practice. Commonly used heuristics, however, have a problem in that they do not include program structure information in register allocation. Without the information of program structure, poor spill decisions can be made. Callahan and Koblenz developed an algorithm that takes the program structure into account by performing register allocation hierarchically. Unfortunately, Callahan and Koblenz have not presented any experimental evidence to establish the effectiveness of their algorithm. This thesis examines the effectiveness of Callahan and Koblenz's algorithm and shows that when register pressure is high, Callahan and Kob..