Cooperative register allocation and instruction scheduling

In order to exploit the fine-grain parallelism in pipelined, superscalar, superpipelined and VLIW machines, various strategies for scheduling instructions at compile time have been developed. Unfortunately, these strategies can have a negative effect on register allocation which is one of the most important optimizations performed in optimizing compilers. Until recently instruction scheduling and register allocation were treated separately, one occurring before the other in isolation. Due to the conflicts in ordering these two phases, several efforts have been made to provide communication between instruction scheduling and register allocation. However, the current schemes suffer a number of drawbacks. This dissertation investigates these issues through several strategies to provide cooperation between register allocation and instruction scheduling. One strategy, a Scheduler Sensitive Global register allocator (SSG), provides cooperation between global register allocation and per basic block instruction scheduling by making modifications to key phases of a successful global register allocator. Experimental results indicate that this technique performs as well as and increasingly better than other techniques with an increasing number of registers without the complexity of the previous approaches. A second strategy, Register Allocation Sensitive Region scheduling (RASER), performs a global scheduling technique called region scheduling while keeping track of the number of live variables in each region. RASER creates regions with parallelism matching the amount of parallelism exploitable by the architecture and also reduces the number of live variables in a region in order to reduce the amount of spill code generated by the subsequent register allocation phase. In addition, the design and implementation of a Register Allocator which allocates over the Program dependent graph (RAP) is also presented. By basing the allocation on the program dependence graph, the register allocation phase may be more easily integrated and intertwined with other optimization analyses and transformations, including instruction scheduling.