Advanced Backend Optimization

11

Loop Unrolling Degree Minimization for Periodic Register Allocation

We address the problem of generating compact code for software pipelined loops. Although software pipelining is a powerful technique for extracting fine-grain parallelism, it generates lifetime intervals spanning multiple loop iterations. These intervals require periodic register allocation (also called variable expansion), which in turn yields a code generation challenge. We are looking for the minimal unrolling factor enabling the periodic register allocation of software pipelined kernels. This challenge is generally addressed through one of the following: (1) hardware support in the form of rotating register files, which solve the unrolling problem but are expensive in hardware; (2) register renaming by inserting register moves, which increase the number of operations in the loop, and may damage the schedule of the software pipeline and reduce throughput; (3) postpass loop unrolling that does not compromise throughput but often leads to impractical code growth. The latter approach relies on the proof that MAXLIVE registers are sufficient for periodic register allocation [HEN 92, WER 99, TOU 04, TOU 03]; yet the only heuristic to control the amount of postpass loop unrolling does not achieve this bound or leads to undesired register spills [WER 99, LAM 88b].

This chapter gathers our research results on the open problem of minimal loop unrolling allowing a software-only code generation that does not trade the ...