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.