Predicated Register Allocation

Alexandre E. Eichenberger, Edward S. Davidson


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.


Register Allocation, Predicated Execution, Interference, Hyperblocks, Software Pipelining

Talk Overheads (178582 bytes)