Register allocation using cyclic interval graphs

We propose the use of cyclic interval graphs as an alternative representation for register allocation. The "thickness" of the cyclic interval graph captures the notion of overlap between live ranges of variables relative to each particular point of time in the program execution. It is effective in capturing the regular periodic nature of loop-carried dependent live ranges found in loops.As most scientific code spend a lot of time executing loop structures, it is most crucial to perform well when register allocating for it. A good spilling algorithm and a close to optimal coloring algorithm is invaluable in minimizing the cost that may be incurred while performing register allocation for loop structures. Minimization of spill code often greatly increases the performance of the code. Our proposed spilling and coloring scheme is very well suited to these loop structures, and could be used to reap maximum benefit when used in tandem with loop scheduling algorithms (NG93, Nin93).A collection of real program loops are used to test the effectiveness of our approach