A REGISTER ALLOCATION FRAMEWORK BASED ON HIERARCHICAL CYCLIC INTERVAL-GRAPHS

The use of cylic interval graphs as an alternative representation for register allocation is provided. The 'thickness' of the cyclic interva l graph captures the notion of overlap between live-ranges of variable s relative to each particular point of time in the program execution. Cyclic interval graphs provide a feasible and effective representation that accurately captures the periodic nature of live ranges found in loops. A new heuristic algorithm for minimum register allocation, the fat cover algorithm, has been developed and implemented to exploit suc h program structure. A new spilling algorithm is proposed that makes u se of the extra information available in the interval graph representa tion. These two algorithms work together to provide a two-phase regist er allocation process that does not require iteration of the spilling or colouring phases. The notion of cyclic interval graphs is extended to hierarchical cyclic interval graphs and a framework for a compiler to use this representation when performing register allocation for pro grams with hierarchical control structure such as nested conditionals and loops is outlined. The effectiveness of this approach has been dem onstrated by experimenting with a collection of challenging loops.