An experimental study of several cooperative register allocation and instruction scheduling strategies

Compile-time reordering of low level instructions is successful in achieving large increases in performance of programs on fine-grain parallel machines. However, because of the interdependences between instruction scheduling rand register allocation, a lack of cooperation between the schedules and register allocator can result in generating code that contains excess register spills and/or a lower degree of parallelism than actually achievable. This paper describes a strategy for providing cooperation between register allocation and both global and local instruction scheduling. We experimentally compare this strategy with other cooperative and uncooperative scenarios. Our experiments indicate that the greatest speedups are obtained by performing either cooperative or uncooperative global instruction scheduling with cooperative register allocation and local instruction scheduling.