The overlapping of loop iterations in software pipelining techniques imposes high register requirements. The schedule for
a loop is valid if it requires at most the number of registers available in the target architecture. Otherwise its register
requirements have to be reduced by spilling registers to memory. Previous proposals for spilling in software pipelined loops
require a two-step process. The first step performs the actual instruction scheduling without register constraints. The second
step adds (if required) spill code and reschedules the modified loop. The process is repeated until a valid schedule, requiring
no more registers than those available, is found.
The paper presents MIRS (Modulo scheduling with Integrated Register Spilling), a novel register-constrained modulo scheduler that performs modulo
scheduling and register spilling simultaneously in a single step. The algorithm is iterative and uses backtracking to undo
previous scheduling decisions whenever resource or dependence conflicts appear. MIRS is compared against a state-of-the-art two-step approach already described in the literature. For this purpose, a workbench
composed of a large set of loops from the Perfect Club and a set of processor configurations are used. On the average, for
the loops that require spill code a speed-up in the range 14–31% and a reduction of the memory traffic by a factor in the
range 0.90–0.72 are achieved.
Keywords Instruction-Level Parallelism - Software Pipelining - Register Allocation - Spill Code
This work has been supported by the Ministry of Education of Spain under contracts TIC 98/511 and TIC2001-0995-C02-01, and
by CEPBA (European Center for Parallelism of Barcelona). Javier Zalamea is granted by the Agencia Española de Cooperación
Internacional.