[Back]

G. Barany, A. Krall:
"Optimistic Integrated Instruction Scheduling and Register Allocation";
Talk: 15th Workshop on Compilers for Parallel Computing (CPC 2010), Wien; 2010-07-07 - 2010-07-09; in: "15th Workshop on Compilers for Parallel Computing (CPC 2010)", (2010), 15 pages.

Instruction scheduling and register allocation are two fundamental operations in an optimizing compiler's back-end. Scheduling is especially important in order to exploit parallel functional units in modern superscalar or VLIW architectures. There is a well-known phase ordering problem between these two stages: Performing either stage first can force the other stage to make suboptimal decisions.

We propose an optimistic integrated approach in which scheduling is performed before register allocation, but where not all scheduling decisions are final; rather, the register allocator may rearrange the order of certain instructions to find a good match of register usage to the actually available registers.

The rescheduling register allocator is based on a linear-scan allocator. The allocator passes over the program and assigns registers to live ranges. When at some point there are more live values than available machine registers, standard allocators make a decision to spill some value to memory or to split a live range. With our scheme, there is an additional possibility: Instructions may be rearranged so that some live ranges end earlier, freeing registers for other values. Such code motion may lead to longer schedules because more unfilled delay slots may be exposed. In many cases, we expect this to be preferable to more expensive spilling.

We evaluate a prototype implementation of our approach and find that it succeeds in eliminating some spills, but (as expected) not as many as a scheduler aimed at minimizing register use. To expose greater opportunities for aggressive optimizations, we will investigate our integrated approach in the setting of superblock scheduling for instruction-level parallel processor architectures.

compilers, code generation, register allocation, instruction scheduling

http://publik.tuwien.ac.at/files/PubDat_187382.pdf

Project Head Andreas Krall:
Optimale Code Erzeugung für explizit parallele Prozessoren