Post-pass periodic register allocation to minimise loop unrolling degree

摘要

This paper solves an open problem regarding loop unrolling after periodic register allocation. Although software pipelining is a powerful technique to extract fine-grain parallelism,it generates reuse circuits spanning multiple loop iterations.These circuits require periodic register allocation, which in turn yield a code generation challenge, generally addressed through:(1)hardware support-rotating register files-deemed too expensive for embedded processors,(2)insertion of register moves with a high risk of reducing the computation throughput-initiation interval (II)-of software pipelining, and(3)post-pass loop unrolling that does not compromise throughput but often leads to unpractical code growth.The latter approach relies on the proof that MAXLIVE registers are sufficient for periodic register allocation(2;3;5);yet the only heuristic to control the amount of post-pass loop unrolling does not achieve this bound and leads to undesired register spills(4;7).We propose a periodic register allocation technique allowing a software-only code generation that does not trade the optimality of the II for compactness of the generated code.Our idea is based on using the remaining registers:calling R-arch the number of architectural registers of the target processor,then the number of remaining registers that can be used for minimising the unrolling degree is equal to R-arch-MAXLIVE.We provide a complete formalisation of the problem and algorithm,followed by extensive experiments. We achieve practical loop unrolling degrees in most cases-with no increase of the II-while state-of-the-art techniques would either induce register spilling,degrade the II or lead to unacceptable code growth.