Software Pipelining with Reduced Register Requirement

Jian Wang, Andreas Krall and M. Anton Ertl

Institut für Computersprachen
Technische Universität Wien
Argentinierstraße 8
A-1040 Wien, Austria
{jian,andi}@complang.tuwien.ac.at

Abstract

Although it is well-known that a strong interaction exists between software pipelining and register allocation, simultaneous software pipelining and register allocation is still less understood and remains an open problem. In this paper, we first analyze the influence of the re-use of registers on the loop data dependence graph and model the problem of software pipelining to reduce register requirement based on the concepts of row-number and column-number of decomposed software pipelining. Given the row-numbers of all operations in the loop, generating the column-numbers to obtain the minimum register requirement can be modelled as the integer programming problem which can be solved in polynomial time. Then, a solution is presented to the special case without resource constraints and an approximate solution is presented to the general case with resource constraints. Register spilling and register coloring are considered to further reduce the number of actually needed registers. The preliminary experimental results are presented to indicate the efficiency of our new approach.