Abstract:
Traditionally, software pipelining is applied either to the innermost
loop of a given loop nest or from the innermost loop to the outer
loops. In a companion paper, we proposed a scheduling method, called
Single-dimension Software Pipelining (SSP), to
software pipeline a multi-dimensional loop nest at an arbitrary loop
level.
In this paper, we describe our solution to SSP code generation. In
contrast to traditional software pipelining, SSP handles two distinct
repetitive patterns, and thus requires new code generation algorithms.
Further, these two distinct repetitive patterns complicate register
assignment and require two levels of register renaming. As rotating
registers support renaming at only one level, our solution is based on
a combination of dynamic register renaming (using rotating registers)
and static register renaming (using code replication). Finally, code
size increase, an even more important issue for SSP than for
traditional software-pipelining, is also addressed. Optimizations are
proposed to reduce code size without significant performance
degradation.
We first present a code generation scheme and subsequently implement
it for the IA-64 architecture, making effective use of rotating
registers and predicated execution. We present some initial
experimental results, which demonstrate not only the feasibility and
correctness of our code generation scheme, but also its code quality.