# 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.