Predicated Register Allocation
Alexandre E. Eichenberger, Edward S. Davidson
Abstract
Current compilers for VLIW and superscalar machines increase the
instruction level parallelism of an application by merging several
basic blocks into an enlarged predicated block, resulting in high
performance code but increased register requirements. We present a
technique that reduces the register requirements of a predicated basic
block by computing precise interferences among virtual registers in
presence of predicated operations and by allowing non-interfering
virtual registers that overlap in time to share a common virtual
register. Preliminary measurements on a benchmark from the Perfect
Club, SPEC-89, and the Livermore Fortran Kernels indicate the
effectiveness of this technique, decreasing the average register
requirements from 39.3 to 36.5 registers, 1% above a schedule-dependent
lower bound, and increasing from 85% to 95% the percentage of loops
with no more than 64 registers. Our preliminary results also indicate
that this technique is currently more successful when applied after
rather than before scheduling.
Keywords
Register Allocation, Predicated Execution, Interference,
Hyperblocks, Software Pipelining
Talk
Overheads (178582 bytes)