Software Pipelining with Register Allocation and Spilling
Jian Wang, Andreas Krall, M. Anton Ertl and Christine Eisenbeis
Institut für Computersprachen
Technische Universität Wien
Argentinierstraße 8
A-1040 Wien, Austria
{jian,andi}@complang.tuwien.ac.at
Abstract
Simultaneous register allocation and software pipelining is still less
understood and remains an open problem. In this paper, we first present the
Register Requirement Graph (RRG) which can dynamically reflect the register
requirement during software pipelining. Then, using the RRG as a basis, we
develop a Register-Pressure-Sensitive (RPS) scheduling technique and study the
problem of register spilling for software pipelining. We also present three
algorithms -- RPS without spilling, RPS with spilling and the software
pipelining with a limited number of registers. The preliminary experimental
results show that the first two algorithms can efficiently reduce the register
requirement without degradation of the optimal performance and the third can
effectively exploit instruction-level parallelism within loops even for those
machines with a small register file.