Improved spill code generation for software pipelined loops.
Software pipelining is a loop scheduling technique that extracts parallelism out of loops by overlapping the execution of several consecutive iterations. Due to the overlapping of iterations, schedules impose high register requirements during their execution. A schedule is valid if it requires at most the number of registers available in the target architecture. If not, its register requirements have to be reduced either by decreasing the iteration overlapping or by spilling registers to memory. In this paper we describe a set of heuristics to increase the quality of register-constrained modulo schedules. The heuristics decide between the two previous alternatives and  define criteria for effectively selecting spilling candidates. The heuristics proposed for reducing the  register pressure can be applied to any software pipelining technique. The proposals are evaluated using a register-conscious software pipeliner on a workbench composed of a large set of loops from the Perfect Club benchmark and a set of processor configurations. Proposals in this paper are compared against a previous proposal already described in the literature. For one of these processor configurations and the set of loops that do not fit in the available registers (32), a speed-up of 1.68 and a reduction of the memory traffic by a factor of 0.57 are achieved with an affordable increase in compilation time. For all the loops, this represents a speed-up of 1.38 and a reduction of the memory traffic by a factor of 0.7.
Introduction
Software pipelining [9] is an instruction scheduling technique that exploits instruction level
parallelism (ILP ) out of a loop by overlapping operations from various successive loop
iterations. Different approaches have been proposed in the literature [2] for the generation
of software pipelined schedules. Some of them mainly focuses on achieving high throughput
[1, 11, 16, 22, 23, 25]. The main drawback of these aggressive scheduling techniques is their
high register requirements [19, 21]. Using more registers than available requires some actions
which reduce the register pressure but may also degrade the performance (either due to the
additional cycles in the schedule or due to additional memory traffic). For this reason, other
proposals have also focused their attention in the minimization of the register requirements
[12, 15, 20, 27].
Register allocation consists on finding the final assignment of registers to loop variables
(variants and invariants) and temporaries. It has been extensively studied in the framework
of acyclic schedules [3, 5, 6, 7] based on the original graph coloring proposal [8]. However,
software pipelining imposes some constraints that inhibit the use of these techniques for
register allocation. Although there have been proposals to handle them [13, 14, 24], none of
them deals with the addition of spill code (and its scheduling) that is needed to reduce the
register pressure in software pipelined loops.
Any software pipeliner fails if it generates a schedule that requires more registers than
those available in the target machine. In this case, some additional actions have to be
performed in order to alleviate the high register demand [24]. One of the options is to
reschedule the loop with a reduced execution rate (i.e. with less iteration overlapping);
this reduces the number of overlapped operations and variables. Unfortunately, the register
reduction may be at the expense of a reduction in performance. Another option is to spill
some variables to memory, so that they do not occupy registers for a certain number of clock
cycles. This requires the insertion of store and load instructions that free the use of these
registers. The evaluation performed in [18] shows that reducing the execution rate tends to
generate worse schedules than spilling variables; however, the authors show that in a few
cases the opposite situation may happen.
Several aspects contribute to the quality of the spill code generated by the compiler. The
first one is deciding if the spill code applies to all the uses of a variable or just to a subset.
The second aspect relates to the selection of spilling candidates, which implies deciding the
number of variables (or uses) selected for spilling and the priority function used to select
among them. Both decisions need accurate estimates of the benefits that the selection of a
spilling candidate will produce in terms of register pressure reduction.
In order to motivate this work, Table 1 shows, for two different spill algorithms, the average
execution rate (cycles between the initiation of two consecutive iterations) and average
memory traffic (number of memory accesses per iteration) for all the loops in our workbench
(Section 2.4) whose schedule does not fit in 32 registers and for one of the processor
configurations used along this paper. The table also includes the ideal case (i.e. when infinite
registers are available and no spill is needed). Notice that the gap between the two
implementations (one commercial, as described in [26] and the other experimental [18]) and
the ideal case is large. These results motivated the proposal of new heuristics to improve
the whole register pressure reduction process; the last column in the same table shows the
results after applying the heuristics proposed in this paper, which represent more than 40%
reduction in the execution rate and memory traffic with respect to previous proposals.
In this paper we use a register-conscious pipeliner, named HRMS [20], to schedule the
loops. Once the loops are scheduled, register allocation is performed using the wands-
only strategy with end-fit and adjacency ordering [24]. Then, the register requirements are
decreased if required. The paper contributes with a set of heuristics to: 1) decide between the
two different possibilities aforementioned (adding spill code or directly decrease the execution
rate); and 2) do a better selection of spilling candidates (both in terms of assigning priorities
to them and selecting the appropriate number). The paper also contributes with an analysis
of the results when spill of variables or uses is performed. The different proposals are
compared against the ideal case (which is an upper bound for performance) and against the
Metric Ideal [18] [26] This paper
avg. execution rate 12.01 28.32 29.43 20.66
avg. memory traffic 15.38 50.88 52.13 35.71

Table

1: Motivating example for improving the spill process.
proposals presented in [18]. The workbench is composed of all the loops from the Perfect
[4] that are suitable for software pipelining.
The paper is organized as follows. Section 2 makes a brief overview of modulo scheduling,
register allocation and spill code for modulo scheduling. Section 3 focuses on the different
steps and proposals for spilling variables to memory. Then, Section 4 presents different alternatives
to select the spilling candidates in a more effective way, and analyze the trade-off
between reducing the execution rate or adding spill code. In Section 5 the different alternatives
and heuristics are evaluated in terms of dynamic performance, taking into account the
relative importance of each loop in the total execution time of the benchmark set. Finally,
Section 6 states our conclusions.
2 Basic concepts
2.1 Modulo scheduling
In a software pipelined loop, the schedule of an iteration is divided into stages so that the
execution of consecutive iterations, that are in distinct stages, are overlapped. The number
of stages in one iteration is termed Stage Count (SC). The number of cycles between the
initiation of successive iterations in a software pipelined loop determines its execution rate
and is termed the Initiation Interval (II).
The execution of a loop can be divided into three phases: a ramp up phase that fills the
software pipeline, a steady state phase where the maximum overlap of iterations is achieved,
and a ramp down phase that drains the software pipeline. During the steady state phase,
the same pattern of operations is executed in each stage. This is achieved by iterating on a
piece of code, named the kernel, that corresponds to one stage of the steady state phase.
The II is bounded by recurrence circuits in the dependence graph of the loop (RecMII)
or by resource constraints of the target architecture (ResMII). The lower bound on the II is
termed the Minimum Initiation Interval ResMII)). The reader is
referred to [11, 25] for an extensive dissertation on how to calculate RecMII and ResMII.
In order to perform software pipelining, the Hypernode Reduction Modulo Scheduling
(HRMS) heuristic [20] is used. HRMS is a software pipeliner that achieves the MII for a
large percentage of the workbench considered in this paper (97.4 % of loops). In addition,
it generates schedules with very low register requirements. A register-sensitive software
pipelining technique has been used in order to not overestimate the necessity of spill code.
The scheduling is performed in two steps: a first step that computes the priority of operations
to be scheduled and a second step that performs the actual placement of operations in the
modulo reservation Table.
2.2 Register allocation
Once a loop is scheduled, the allocation of values to registers is performed. Values used in a
loop correspond either to loop-variant or loop-invariant variables. Invariants are repeatedly
used but never defined during the execution of the loop. Each invariant has only one value
for all iterations of the loop, and therefore requires a single register during the execution of
the loop (regardless of the scheduling and the machine configuration).
For loop variants, a new value is generated in each iteration of the loop and, therefore,
there is a different lifetime (LT) [15]. Because of the nature of software pipelining, the LT
of values defined in an iteration can overlap with the LT of values defined in subsequent
iterations. The LT of loop variants can be measured in different ways depending on the
execution model of the machine. We assume that a variable is alive from the beginning of
the producer operation until the start of the last consumer operation.
By overlapping the LT in different iterations, a pattern of length II cycles, that is indefinitely
repeated, is obtained. This pattern indicates the number of values that are live at any
given cycle. The maximum number of simultaneously live values (MaxLive) is an accurate
approximation of the number of registers required for the schedule [24].
Variants may have LT values greater than II ; this poses an additional difficulty since
new values are generated before previous ones are used. One approach to fix this problem
is to provide some form of register renaming so that successive definitions of the same value
use distinct registers. Renaming can be performed at compile time using modulo variable
expansion (MVE) [17] (i.e. unroll the kernel and rename the multiple definitions of each
variable that exist in the unrolled kernel). Rotating register files provide a hardware solution
to solve the same problem without replicating code [10] (i.e. the renaming of the different
instantiations of a loop-variant is done at execution time).
In our study and implementation, we assume the existence of a rotating register file and
use the wands-only strategy using end-fit with adjacency ordering [24]. This strategy usually
achieves a register allocation that uses MaxLive registers and almost never requires more
than MaxLive registers. However, the heuristics proposed in this paper are applicable
regardless of the hardware model and the register allocation strategy used.
2.3 Decreasing the register requirements
The register allocation techniques for software pipelined loops [24] assume an infinite number
of registers. From now on we name Used Registers (UR) the number of registers required
to execute a given schedule and Available Registers (AR) the number of registers available
in the target architecture.
If UR is greater than AR, then the obtained schedule is not valid for the target processor.
In this case, the register pressure must be decreased so that the loop can be executed (e.g.
we must obtain a schedule so that UR - AR). Different alternatives to decrease the register
requirements have been outlined in [24]: 1) to reschedule the loop with a larger II; 2) to spill
some variables to memory; or 3) to split the loop into several smaller loops. To the best
of our knowledge, loop splitting has not yet been evaluated for the purpose of decreasing
the register pressure. The other two alternatives have been evaluated and compared in [18]
and are used by production compilers (e.g. the Cydra5 compiler increases the II [11], and
the MIPS compiler, as described in [26], adds spill code). Next we summarize the main
conclusions from the comparison:
ffl Rescheduling the loop with a bigger II usually leads to schedules with less iteration
overlapping, and therefore with less register requirements. Unfortunately, the UR
decrease is directly at the expense of a reduction in performance (less parallelism is
exploited). In addition, for some loops is not possible to find a valid schedule with
UR - AR by simply increasing the II.
ffl Spilling variables to memory makes available their associated registers for other values.
This spill requires the use of several load and store operations and may saturate the
memory units, turning the loop into a memory-bounded loop; in this case, the addition
of spill code leads to an increase of the II and to a degradation of the final performance.
Increasing the II produces, in general, worse schedules than adding spill code. However, for
some loops the first option is better. This suggests that a hybrid method that in some cases
adds spill code and in others increases the II can produce better results. For instance, [27]
spills as many uses as possible without increasing the II (i.e. it tries to saturate the memory
buses). If the schedule obtained does not fit in AR, then the II is increased. Although
this heuristic always ends up with a valid schedule, it does not care about minimizing the
memory traffic (in fact it may increase memory traffic for loops that do not require spill).
In this paper we present a heuristic to allow the bypassing of the step to add spill code in
some cases and simply increase the II. The paper also proposes several new heuristics for
adding spill code. These heuristics allow for a better tuning of the final schedule so that the
performance degradation is reduced as well as the memory traffic overhead.
2.4 Experimental framework
The different proposals of the paper are evaluated on a set of architectures PiMjLk defined
as follows: i is the number of functional units used to perform each kind of computations
(adders, multipliers and div/sqr units); j is the number of load/store units; and k is the
latency of the adders and the multipliers. In all configurations, the latency of load and store
accesses is two and one cycles, respectively. Divisions take 17 cycles and square roots take
cycles. All functional units are fully pipelined, except for the div/sqr functional units. In
particular, four different configurations are used: P2M2L4, P2M2L6, P4M2L4 and P4M4L4,
with registers each.
In order to evaluate the heuristics proposed, a total of 1258 loops that represent about
80% of the total execution time of the Perfect Club [4] (measured on a HP-PA 7100) have
been scheduled. First of all we evaluate the effectiveness of our proposals (Section 4); for
this evaluation we use only those loops for which UR ? AR. The number of loops that
fulfills this condition, for the different processor configurations aforementioned, is shown in

Table

2. Notice that when 64 registers are available, the number of loops that do not fit in
the AR is very small (and therefore subject to the variance of the heuristics themselves). As
a consequence, the main conclusions of our experimental evaluation will be drawn for the
configurations with however, results for 64 registers will be used to confirm the
trend. Then we evaluate the real impact on performance taking into account all the loops
in the workbench (Section 5).
AR P2M2L4 P2M2L6 P4M2L4 P4M4L4

Table

2: Number of loops that require more registers than available for a set of processor configurations
PiMjLk.
The metrics used to evaluate the performance are the following:
ffl \SigmaII , which measures the sum of the individual II for all the loops considered.
ffl \Sigmatrf , which measures the sum of the individual number of memory operations used in
the scheduling.
ffl SchedTime, which measures the time to schedule the loops.
Adding spill code
The initial algorithm that we use for generating register constrained modulo schedules is
the iterative algorithm shown in Figure 1. After scheduling and register allocation, if a
loop requires more registers than those available, a set of spilling candidates is obtained and
ordered. The algorithm then decides how many candidates are finally selected for spilling
and introduces the necessary memory accesses in the original dependence graph. The loop
is rescheduled again because modulo schedules tend to be very compact -the goal is to
saturate the most used resource- and it is very difficult to find empty slots to allocate the
new memory operations in the modulo reservation table. The process is repeated until a
schedule requiring no more registers than available is found. To the best of our knowledge,
all previous spilling approaches are based on a similar iterative algorithm [18, 26, 27].
In the following subsections we describe in more detail each one of these aspects and
present the solutions proposed by previous researchers.
3.1 Variables and uses
The lifetime of a variable spans from its definition to its last use. The lifetime of a variable
can be divided in several sections (uses) whose lifetime spans from the previous use to
Priority
Regs. Allocation
Add Spill
Select Candidates
Sort Candidates
Generation of Spill Code
Scheduling
Rgs. Reqrm.
Scheduling

Figure

1: Flow diagram for the original spill algorithm.
the current one. For example, Figure 2.a shows a producer operation followed by four
independent consumer operations. In this case, the lifetime of the variable ranges from the
beginning of Prod to the beginning of Cons4; four different uses can be defined (U1 . U4),
as shown in the right part of the same figure.
The disadvantage of spill of variables is that, if one variable has several successors, the
number of associated spill memory operations is suddenly increased; this may produce an
increase of the II and thus reduce performance. In addition, some of the loads added might
not actually contribute to a decrease of the register requirements. Spill of uses allow a
more fine-grain control of the spill process. Both alternatives have been used in previous
proposals: spill of variables is used in [18, 26] and spill of uses in [27]. In this paper we
evaluate the performance of the two alternatives and their combination with the heuristics
proposed in Section 4.
3.2 Sorting spilling candidates
Some criteria are needed to decide the most suitable spilling candidates (i.e. those decreasing
the most the register requirements with the smallest cost). This is achieved by assigning a
priority to each spilling candidate; this priority is usually computed according to the LT of
the candidate [18] or to some ratio between its LT and the memory traffic introduced when
spilled [18, 26, 27]. As expected, the second heuristic always produces better results. In this
paper we propose a new criterion that takes into account the criticality of the cycles spanned
by the lifetime of each spilling candidate.
3.3 Quantity selection
After giving priorities to each spilling candidate, the algorithm decides how many candidates
are actually spilled to memory. The objective is to decrease the register requirements so that
UR - AR with the minimum number of spill operations. This requires an estimation of the
benefits that each candidate will produce in the final schedule. However, the new memory
operations may saturate the memory units and lead to an increase of the II; this increase in
the II reduces by itself the register pressure and may lead to a situation where an unnecessary
number of candidates have been selected.
This selection process can be done in different ways. For instance, [18] proposes to
spill one candidate at a time and reschedule again. This heuristic avoids overspilling at
the expense of an unacceptable scheduling time. To avoid it, [26] performs several tries by
spilling a power-of-two number of candidates; the process finishes when a new schedule that
fits in AR is found. To reduce the number of reschedulings in a more effective way, [18]
selects as much candidates as necessary to directly reduce the UR to AR; in order to avoid
overspilling, each time a candidate is selected, its lifetime is subtracted from the current
UR to compute an estimated number of registers needed after spilling. Another alternative,
which is used in [27] to generate schedules with minimum register requirements, consists on
selecting as much candidates as necessary to saturate the memory units with the current II.
This paper proposes a new heuristic that tries to better foresee the overestimation that
is produced by some of the previous heuristics.
3.4 Adding memory accesses
Once the set of candidates has been selected, the dependence graph is modified, in order
to introduce the necessary load/store instructions, and rescheduled. In order to guarantee
that the spill effectively decreases UR, the spilled operations have to be scheduled as close
as possible to their producers/consumers. This is accomplished by scheduling each spill
operation and its associated producer/consumer as a single complex operation [18].
For the spill of variables, a store operation has to be inserted after the producer and
a load operation inserted before each consumer. Figure 2.b shows the modification of the
dependence graph when spilling the variable in Figure 2.a. For the spill of uses, a store
lat. FU
Cons.1
Cons.2
Cons.3
Cons.4
Store
Prod.
Cons.1
Cons.2
Cons.3
Cons.4
Store
Prod.
Prod.
a) b) c)
Cons.1
Cons.2
Cons.3
U3
Cons.4

Figure

2: a) Original graph. b) Graph after spilling a variable. c) Graph after spilling a single use
of the same variable.
operation has to be added after the producer and a single load operation added before the
consumer that ends the corresponding use. Figure 2.c shows the modification of the graph
when use U3 is selected (the one that has the largest lifetime and therefore releases more
registers).
4 New heuristics for spill code
In this section we describe the issues and gauges that are used to control the generation
of valid schedules and spill code. The first control decides the priority of candidates to be
selected for spill. The idea behind the proposal is to give priority to those ones that contribute
to a reduction of the register pressure in the most effective way. The second control decides
how many candidates should be spilled before rescheduling the loop. Finally the third control
decides when it is worth to apply a direct increase of the II with no additional spill. In this
analysis, we also consider spilling candidates to be either variables or uses.
4.1 Spill of variables and spill of uses
The algorithms described in Section 3 decide the candidates to spill based on their lifetime
or some ratio between their lifetime and the memory traffic that their spill would generate.
Configuration P4M2L4
Registers
Use 1932 4454 250 875
UseCC
UseQF 1626 3791 229 787
UseTF 1408 3139 132 593
UseCCQFTF 1232 2895 126 606

Table

3: Improving performance metrics by applying different heuristics.
Some of them make a difference when considering either spill of variables or uses of variables.
For instance, Table 3 shows the \SigmaII and \Sigmatrf for two register file sizes (32 and 64 registers)
and processor configuration P4M2L4, when either spill of variables (row labeled Var) or spill
of uses (row labeled Use) is applied (using the LT=trf criterion to order spilling candidates).
The table reports figures relative to the ideal case, i.e. the \SigmaII and \Sigmatrf for the ideal case
has been subtracted from the values for the specific configuration. Notice that in general,
doing spill of uses achieves schedules with lower II and memory traffic.
From these initial results, the reader may conclude that doing spill of uses is more effective
than doing spill of variables. However, we will see along the paper that our proposals improve
the metrics and tend to reduce the gap between these two alternatives. In addition, their
behavior also depends on the architecture being evaluated, as will be shown in Section 5.
4.2 Critical cycle
First of all we propose a new criterion to select candidates for spill. Sometimes the selection
based on LT=trf may select candidates that do not effectively reduce the register pressure.
The rationale behind is that their spill reduces the number of simultaneous live candidates
but not in the scheduling cycle where this number is maximum (thus deciding the number
of registers needed).
The Critical Cycle (CC) is defined as the scheduling cycle for which the number of used
registers UR is maximum. The new selection criterion gives more priority to those candidates
that cross the CC. This criterion for candidates selection may improve the efficiency of the
spill process, as shown in Table 3 for the processor configuration selected. Rows labeled
VarCC and UseCC show the two performance metrics for our workload.
4.3 Number of variables to spill
The computation of the number of candidates may not be accurate because the new spill
code might increase the II of the schedule (as a result of the saturation of the memory unit);
this increase of the II could reduce the overall register pressure and therefore it would not
be necessary to use as much spill as initially expected. The proposal in this section tries to
foresee this overestimation.
The algorithm assumes that the register file has more available registers (AR 0
actually has. It adds to the actual number of available registers a number proportional to
the gap between the UR and AR, as follows: AR 0
being QF the
Quantity Factor. Notice that corresponds to the spill of one candidate at a time
and to the spill of all the necessary candidates to reduce the UR to AR.
QF is a parameter whose optimal value depends on the architecture and the characteristics
of the loop itself. In this paper we conduct an experimental evaluation of this parameter
in order to determine a range of useful values and to analyze its effects on performance and
on the scheduling time SchedTime. Figure 3 plots the behavior for \SigmaII , \Sigmatrf and SchedTime
for QF values in the range between 1 and 0. The lowest values of QF leads to worst results
in terms of II and trf but with the low SchedTime. Large values for QF lead to better
performance at the expense of an increase in compilation time. In particular, for values of
QF larger than 0.6, the increase in SchedTime does not compensate the increase in perfor-
mance. In general medium values of QF generate good schedules with a negligible increase
in compilation time.

Table

3 (rows labeled VarQF and UseQF ) shows the results for 0.5. Notice that
QF (Quantity Factor)18002200Sum(II)
a.1
QF (Quantity Factor)40005000
b.1
Use
QF (Quantity Factor)5001500
SchedTime
QF (Quantity Factor)250Sum(II)
a.2
QF (Quantity Factor)8001000
b.2
QF (Quantity Factor)100300500
SchedTime
c.2

Figure

3: Behavior of: a) \SigmaII , b) \Sigmatrf and c) total SchedTime for values of QF between 0 and 1
(32 registers (.1) and 64 registers (.2)).
this value does not increase too much the compilation time and reduces considerably both
the II and trf.
4.4 Traffic control
The previous techniques try to improve the performance of the spill process by increasing
the effectiveness of the selection of candidates. There are situations in which it is better to
increase II instead of applying spill. For example, when AR - UR and adding spill code
would lead to a saturation of the memory unit; in this case, the II and memory traffic would
be increased (in order to fit the new memory operations). However, if we only increase the
II (without adding spill), the memory traffic will not increase and we might also reduce UR.

Figure

4 shows the algorithm proposed with a control point that decides when it is better
to increase II or to insert spill code.
In order to foresee the previous situation, the algorithm performs an estimation of the
memory traffic (number of loads and stores) that would be introduced if spill is done
(NewTrf). If the maximum traffic MaxTrf that can be supported with the current value
of II is not enough to absorb NewTrf, then the algorithm directly increases the II (without
inserting spill) and the process is repeated again. In particular, the new II value might
produce less spill code or it may not be required at all.
Priority
Regs. Allocation
Add Spill
Select Candidates
Sort Candidates
Trf. can be absorbed
II ++
Generation of Spill Code
Scheduling
Rgs. Reqrm.
Scheduling

Figure

4: Flow diagram for the proposed algorithm that combines spill code and traffic control.
The maximum traffic the architecture can support is multiplied by TF (Traffic Factor)
to control the saturation of the memory unit (the condition that accepts the addition of
spill code is NewTrf - MaxTrf   TF). This is done because there is a trade-off between
applying the spilling mechanism and increasing the II. When the TF parameter is included
we obtain a better trade-off between both mechanisms. Moreover, if we take
we are always increasing II , and if we take TF !1 then we are always inserting spill.
The TF can take any positive value. But after some experimentation, we have observed
that the best results are obtained when TF ranges between 0.7 and 1.4. Figure 5 plots the
behavior of \SigmaII , \Sigmatrf and SchedTime for values of TF within this range. In general, it can
be observed that the best value of II is obtained with a TF value close to 0.95, but if we
want to reduce the traffic we have to use smaller values for TF. Notice that the time to
obtain the schedules has a small variation.

Table

3 (rows labeled VarTF and UseTF ) shows the performance in terms of \SigmaII and
\Sigmatrf when the TF is set to 0.95. Notice that for registers, spill of variables performs
better than spill of uses.
Both parameters, QF and TF, tend to reduce the spill code but may interfere in a positive
way.

Figure

6 plots the combined effect of both parameters. Notice that a tuning of these
parameters might lead to better values of \SigmaII . Another observation is that if the TF is not
used, then higher values of QF are needed (which results in higher scheduling times). In
particular, for 32 registers the best results are obtained when QF is set to zero while for 64
registers the best results are obtained when QF is set between 0.3 and 0.5.
In order to summarize all the previous effects, rows labeled VarCCQFTF and UseCC-
QFTF in Table 3 show the performance when CC, QF and TF are used (QF and TF are
set to the value that produce the best performance results). When spill of variables is used,
the \SigmaII is reduced by 47% and 52% and that the \Sigmatrf is reduced by 42% and 35% (with
respect to the initial Var for 32 and 64 registers, respectively). Similarly, when spill of uses
is applied, \SigmaII is reduced by 36% and 50% and that \Sigmatrf is reduced by 35% and 30% (with
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)160020002400
a.1
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)300040005000
b.1
Use
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)50150SchedTime
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)200300
a.2
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)600800Sum(trf)
b.2
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)2060
SchedTime
c.2

Figure

5: Behavior of: a) \SigmaII , b) \Sigmatrf and c) SchedTime when TF ranges between 0.7 and 1.4
(32 registers (.1) and 64 registers (.2)). The first point (*) corresponds to TF !1.
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)160020002400
a.1
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)35004500Sum(trf)
b.1
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)100300
SchedTime
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)200300
a.2
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)600800Sum(trf)
b.2
* 1.4 1.3 1.2 1.1 1.0 0.9 0.8 0.7
TF (Traffic Factor)2060
SchedTime
c.2

Figure

Behavior of: a) \SigmaII , b) \Sigmatrf and c) SchedTime for several values of QF when TF
ranges between 0.7 and 1.4 (32 registers (.1) and 64 registers (.2)). The first point (*) is given with
respect to the initial Use for 32 and 64 registers, respectively). This increase in performance
is at the expenses of an affordable increase in scheduling time: for 32 registers, the scheduler
requires 1.8 times the original time; for 64 registers, the increase is negligible.
Performance Evaluation
The effectiveness of the proposed mechanisms has been evaluated using static information:
II and trf . This evaluation has demonstrated that the new heuristics are very effective in
obtaining better schedules. However, a static evaluation does not show how useful they are
in terms of execution time and dynamic memory traffic.
The execution time is estimated as II   (N being N the total number
of iterations and E the number of times the loop is executed. The dynamic memory traffic
is estimated as M   (N being M the number of memory operations in the
kernel code of the software pipelined loop.
The results, obtained for the P4M2L4 configuration, are shown in Figure 7. The bar
graphs at the upper part (a.) show the execution time degradation relative to the ideal case
(i.e. assuming an infinite number of registers). The closer the results are to 1, the better is
the performance. Notice that 1 is the upper bound for performance. The lower part of the
same figure (b.) shows the memory traffic Mem relative to the ideal case Ideal Mem. Again,
the closer the traffic to 1 the better the schedules. However in this case 1 is a lower bound
for memory traffic. The plots at the left side (.1) correspond to all loops in the benchmark
set while the plots at the right side (.2) refer only to the loops that require spill code.
For a configuration with registers, Figure 7.a.1 shows an speed-up of 1.38 with respect
to the original proposal when spill of variables is used, and 1.27 when spill of uses is applied.
For the same configuration, Figure 7.b.1 shows a reduction of memory by a factor close to
0.7 in both cases. For 64 registers, the speed-up reported is less important (close to 1.06)
and the memory traffic is reduced by a factor close to 0.9.

Figures

7.a.2 and 7.b.2 show the performance for the subset of loops that require spill.
For a configuration with registers, performance for these loops increases by a factor of
1.70 when spill of variables is applied and 1.52 when spill of uses is applied. For 64 registers,
performance increases by a factor close to 1.26 in both cases. Notice that the memory traffic
registers 64 registers0.20.61.0
Cycles
a.1
Use
Use+CC
Use+CC+QF
Use+CC+QF+TF
registers 64 registers13
Mem
b.1
registers 64 registers0.20.61.0
a.2
registers 64 registers2610
Men/Ideal_Mem
b.2

Figure

7: Dynamic results for different spill heuristics. Configuration P4M2L4, QF=0.3 and
TF=0.95.
is extraordinarily decreased. When 32 registers are available, the memory traffic is reduced
by factors of 0.57 and 0.62 with respect to the original proposals with spill of variables and
uses, respectively. When 64 registers are available, memory traffic is reduced by factors of
0.72 and 0.77.
For this architecture notice that spill of uses performs better than spill of variables for
any combination of heuristics and for both 32 and 64 registers. When the critical cycle is
considered, spill of uses improves better than spill of variables. However, when the quantity
factor and the traffic factor are used, performance tends to level between spill of variables
and spill of uses (spill of uses still performs slightly better).
The results that are obtained for the other processor configurations are shown in Figure
8. First of all, notice that for all configurations the heuristics proposed in this paper perform
better. However there are some aspects that need further discussion. For example, in some
cases (e.g. configuration P2M2L4), spill of uses performs worse than spill of variables; other
configurations (e.g P4M4L4) perform better when spill of uses is applied and 64 registers are
available while spill of variables performs better with registers. Also, contrary to what
happens for all other configurations, P2M2L4 with 64 registers and with spill of uses has a
big performance degradation when the critical cycle is considered.
Finally, the parameters QF and TF have been set to different values for each config-
uration. These parameters give flexibility to the algorithm, and allow it to adapt to the
registers 64 registers0.20.61.0
Cycles
a.1
registers 64 registers2610
Mem
b.1
registers 64 registers0.20.61.0
Cycles
a.2
Use
Use+CC
Use+CC+QF
Use+CC+QF+TF
registers 64 registers2610
Mem
b.2
registers 64 registers0.20.61.0
a.3
registers 64 registers2610
Mem
b.3

Figure

8: Dynamic results for different spill heuristics. Configurations: (.1) P2M2L4, (.2) P2M2L6
and (.3) P4M4L4.
configuration. However, these parameters should be tuned for each configuration in order to
obtain good results. For instance we used
with registers and spill of uses, while the same architecture with spill of variables obtains
the best performance with We have performed extensive evaluations
to empirically obtain a useful range for these values so that reasonably good results
are obtained. In particular QF should range from 0.0 to 0.3 and TF should range from 0.9
to 1.0.
In addition these values can be tuned for specific applications or even for specific loops
if final performance is much more important than compilation time like in embedded applications

6 Conclusions
In this paper we have presented a set of heuristics that improve the efficiency of the process
that reduces the register pressure of software pipelined loops. The paper proposes some
new criteria to decide between two different alternatives that contribute to this reduction:
decrease the execution rate of the loop (increase its II) or temporarily store registers into
memory (through spill code). For the second alternative, the paper also contributes with new
criteria to select the spilling candidates (both how many and which ones). The proposals have
been evaluated using a register-conscious software pipeliner; however they are orthogonal to
it and could be applied to any algorithm.
The experimental evaluation has been done over a large collection of loops from the
Perfect Club benchmark. The impact of the different heuristics is evaluated in terms of
effectiveness and efficiency. In terms of effectiveness, the heuristics proposed reduce in most
of the cases the execution rate and memory traffic with respect to the original proposals.
In terms of efficiency, these reduction contributes to a real increase in performance. In
particular, the dynamic performance for the loops that do not fill in the available registers
increases by a factor that ranges between 1.25 and 1.68. The memory traffic is also reduced
by a factor that ranges between of 0.77 and 0.57. This reduction in the execution time
and memory traffic is achieved at the expenses of a reasonable increase in the compilation
time. In the worst case, the scheduler requires 1.8 times the original time. For the whole
workbench, the dynamic performance increases by a factor that ranges between 1.07 and
1.38 while the memory traffic is reduced by a factor that ranges between 0.9 and 0.7. The
scheduler manages to compile all these loops in less than one minute (for a configuration
with 64 registers) and less than 3.5 minutes (for a configuration with
Although the heuristics proposed contribute to better register-constrained schedules,
some additional work is needed to tune several parameters (like the traffic and quantity
factors) and to analyze their real effect for different architectural configurations. We have
also shown that, depending on the configuration, spilling candidates are either variables or
uses. This suggests that a more dynamic process, in which the scheduler decides on-the-fly
the specific values for some of these parameters and takes into account both variables and
uses, may lead to better schedules.



--R

A realistic resource-constrained software pipelining algorithm
Software pipelining.
Spill code minimization techniques for optimizing compilers.
The Perfect Club benchmarks: Effective performance evaluation of supercomputers.
Coloring heuristics for register allocation.
Improvements to graph coloring register allocation.
Register allocation via hierarchical graph coloring.
Register allocation and spilling via graph coloring.
An approach to scientific array processing: The architectural design of the AP120B/FPS-164 family
Overlapped loop support in the Cydra 5.
Compiling for the Cydra 5.
Stage scheduling: A technique to reduce the register requirements of a modulo schedule.
The meeting a new model for loop cyclic register allocation.
Register allocation using cyclic interval graphs: A new approach to an old problem.

Circular scheduling: A new technique to perform software pipelining.
A Systolic Array Optimizing Compiler.
Heuristics for register-constrained software pipelining
Quantitative evaluation of register pressure on software pipelined loops.
Hypernode reduction modulo scheduling.
Register requirements of pipelined pro- cessors
Software pipelining in PA-RISC compilers
Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing.
Register allocation for software pipelined loops.
Iterative modulo scheduling: An algorithm for software pipelining loops.
Software pipelining showdown: Optimal vs. heuristic methods in a production compiler.
Software pipelining with register allocation and spilling.
--TR
Overlapped loop support in the Cydra 5
Spill code minimization techniques for optimizing compliers
Coloring heuristics for register allocation
Register allocation via hierarchical graph coloring
Circular scheduling
Register allocation for software pipelined loops
Register requirements of pipelined processors
Lifetime-sensitive modulo scheduling
Compiling for the Cydra 5
Improvements to graph coloring register allocation
Iterative modulo scheduling
Software pipelining with register allocation and spilling
Software pipelining
Stage scheduling
Hypernode reduction modulo scheduling
Software pipelining showdown
Heuristics for register-constrained software pipelining
Quantitative Evaluation of Register Pressure on Software Pipelined Loops
A Systolic Array Optimizing Compiler
Conversion of control dependence to data dependence
Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing
Register allocation MYAMPERSANDamp; spilling via graph coloring

--CTR
Javier Zalamea , Josep Llosa , Eduard Ayguad , Mateo Valero, Software and hardware techniques to optimize register file utilization in VLIW architectures, International Journal of Parallel Programming, v.32 n.6, p.447-474, December 2004
Alex Alet , Josep M. Codina , Antonio Gonzlez , David Kaeli, Demystifying on-the-fly spill code, ACM SIGPLAN Notices, v.40 n.6, June 2005
Xiaotong Zhuang , Santosh Pande, Differential register allocation, ACM SIGPLAN Notices, v.40 n.6, June 2005
Xiaotong Zhuang , Santosh Pande, Allocating architected registers through differential encoding, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.2, p.9-es, April 2007
Javier Zalamea , Josep Llosa , Eduard Ayguad , Mateo Valero, Two-level hierarchical register file organization for VLIW processors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.137-146, December 2000, Monterey, California, United States
Josep M. Codina , Josep Llosa , Antonio Gonzlez, A comparative study of modulo scheduling techniques, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
Javier Zalamea , Josep Llosa , Eduard Ayguad , Mateo Valero, Modulo scheduling with integrated register spilling for clustered VLIW architectures, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
Bruno Dufour , Karel Driesen , Laurie Hendren , Clark Verbrugge, Dynamic metrics for java, ACM SIGPLAN Notices, v.38 n.11, November
Javier Zalamea , Josep Llosa , Eduard Ayguad , Mateo Valero, Register Constrained Modulo Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.15 n.5, p.417-430, May 2004
software pipelining;spill code;instruction-level parallelism;register allocation