Improved spill code generation for software pipelined loops

Software pipelining is a loop scheduling technique that extracts parallelis m out of loops by overlapping the Execution of several consecutive iteratio ns. Due to the overlapping of iterations, schedules impose high register re quirements during their execution. A schedule is valid if it requires at mo st the number of registers available in the target architecture. If not its register requirements have to be reduced either by decreasing the iteratio n overlapping or by spilling registers to memory. In this paper we describe a set of heuristics to increase the quality of register-constrained module schedules. The heuristics decide between the two previous alternatives and define criteria for effectively selecting spilling candidates. The heurist ics proposed for reducing the register pressure can be applied to any softw are pipelining technique. The proposals are evaluated using a register-cons cious software pipeliner on a workbench composed of a large set of loops fr om the Perfect Club benchmark and a set of processor configurations. Propos als in this paper are compared against a previous proposal already describe d in the literature. For one of these processor configurations and the set of loops that do not Bt in the available registers (32), a speed-up of 1.68 and a reduction of the memory traffic by a factor of 0.57 are achieved wit h an affordable increase in compilation time. For all the loops, this repre sents a speedup of 1.38 and a reduction of the memory traffic by a factor o f 0.7.