An Experimental Study of Several Cooperative Register Allocation and Instruction Scheduling Strategies

Cindy Norris, Lori L. Pollock


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 and register allocation, a lack of cooperation between the scheduler 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.


instruction level parallelism, register allocation, global instruction, scheduling, local instruction scheduling

Talk Overheads (93249 bytes)