Loop Unrolling Degree Minimization for Periodic Register Allocation
Sid Ahmed Ali Touati, Benoît Dupont de Dinechin · 2014
The chapter gathers research results on the open problem of minimal loop unrolling allowing a software-only code generation that does not trade the optimality of the initiation interval for the compactness of the generated code. Software pipelining (SWP) allows instructions to be scheduled independently of the original loop iteration barriers. The chapter formalizes the problem of minimizing the loop unrolling degree in the presence of multiple register types when the loop is unscheduled. For clarity, the chapter discusses the explanation of the loop-unrolling minimization algorithm with the case of a single register type. It generalizes the solution to multiple register types. When the loop is already scheduled, an adapted algorithm is provided based on the meeting graph framework. The chapter presents detailed experimental results on standard benchmark suites. It also discusses some related work on code generation for periodic register allocation. Unroll factor reduction for already scheduled loops.