Optimal register assignment to loops for embedded code generation.
Abstract: One of the challenging tasks in code generation for embedded systems is register assignment. When more live variables than registers exist, some variables are necessarily accessed from data memory. Because loops are typically executed many times and are often time-critical, good register assignment in loops is exceedingly important, since accessing data memory can degrade performance. The issue of finding an optimal register assignment to loops, one which minimizes the number of spills between registers and memory, has been open for some time. In this paper, we address this issue and present an optimal, but exponential, algorithm which assigns registers to loop bodies such that the resulting spill code is minimal. We also show that a heuristic modification performs as well as the exponential approach on typical loops from scientific code.
INTRODUCTION
Typically, an embedded system consists of an embedded, programmable
processor interconnected with some memory and specialized "accelerators"
This work was supported in part by ONR grant K000042879921. A preliminary version of this
paper appears in the Proceedings of the 8th International Symposium on System Synthesis
(ISSS-95).
Authors' addresses: D.J. Kolson, A. Nicolau, and N. Dutt, Department of Information and
Computer Science, University of California, Irvine, Irvine, CA 92717-3425; K. Kennedy,
Department of Computer Science, Rice University, Houston,
Permission to make digital / hard copy of part or all of this work for personal or classroom use
is granted without fee provided that the copies are not made or distributed for profit or
commercial advantage, the copyright notice, the title of the publication, and its date appear,
and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to
republish, to post on servers, or to redistribute to lists, requires prior specific permission
and / or a fee.
ACM Transactions on Design Automation of Electronic Systems, Vol. 1, No. 2, April 1996, Pages 251-279.
(application-specific components). This embedded processor can be realized
by either a processor core or an application-specific instruction-set processor
(ASIP). The architecture of an embedded processor may resemble a general-purpose
processor in its datapath "regularity" or may have some
degree of irregularity in the datapath for efficient implementation of the
application-specific instructions and/or features. In either case, the proces-
sor's memory may be consolidated into one memory module or may be
distributed into various modules (which can have size one, corresponding to
a single register). Examples of embedded processors with a consolidated
memory are the MIPS RC4000 and the microSPARC-II, whereas Texas
Instruments' TMS series and Motorola's 56000 are examples with distributed
memories.
Currently, much research has focused on code generation for these
embedded systems. 1 One of the challenging tasks in generating code for an
embedded processor is that of register assignment. In this assignment
process, program values are mapped to the architecture's registers so that
values are available and in the appropriate registers for computation.
When the number of simultaneously live variables is larger than the
number of registers available, some of these values will have to reside in
the data memory (i.e., "spilled" to memory), requiring data transfers
between memory and registers when those values are updated or necessary
for computation.
Typically, embedded processors have a small number of registers with,
perhaps, some registers having restricted or specialized uses. Because of
these limitations, register assignment is exceedingly critical, especially for
innermost loops that are executed many times and often time-critical. Thus
any mapping of variables to registers that contains poor choices for variable
spills will adversely affect performance.
In the compiler domain, optimal register assignment solutions have been
extensively studied [Horwitz et al. 1966; Hsu et al. 1989; Kennedy 1972].
Although these approaches are effective for straight-line code, they do not
address the issue of an optimal assignment of registers to loops-innermost
loops probably being the only place such extreme methods are practical.
Thus adaptation and extension of this work to the problem of assigning an
embedded processor's registers to program values requires that we overcome
the fundamental difficulty that these previous techniques did not
address satisfactorily-that of matching the register usage at the entry and
exit of loop iterations. That is, for loop code to be correct, the mapping of
variables to registers at the beginning of an iteration and at the end of that
iteration must be equivalent (i.e., the "right" values must be in the "right"
places) so that it is correct to iterate over that loop code.
In this article we demonstrate that the algorithms for register assignment
in basic blocks given in Hsu et al. [1989] and Kennedy [1972] can be
extended to assign registers in loops by incorporating loop unrolling tech-
1 See Lanneer et al. [1994], Liem et al. [1994], Marwedel [1993], Marwedel and Goossens
[1995], and Strik et al. [1995].
252 . D. J. Kolson et al.
niques into the algorithm. We also present a heuristic derived from our
algorithm that, in practice, seems to perform as well as its exponential
counterpart.
In Section 2 we discuss related work and in Section 3 we describe the
problem we are addressing. Section 4 discusses the optimal assignment of
registers in basic blocks for architectures with consolidated register files,
and Section 5 extends this technique to loops. Section 6 discusses the
convergence and optimality of the loop algorithm. Section 7 extends the
loop algorithm to assign registers for architectures with multiple register
files and special purpose registers. Section 8 gives our experimentation and
observed results and Section 9 concludes this article.
2. RELATED WORK
The register assignment problem is an important issue and has become
pervasive in many areas: compiler design, where typically the number of
registers is fixed and uniform access to all registers is available; high-level
synthesis, where the number and interconnection of registers is being
synthesized; and code generation for embedded systems, where embedded
processors have a very limited number of registers with, perhaps, partitioned
register files and special-purpose registers.
In the compiler domain, the most popular approach to register assignment
is the heuristic graph coloring approach [Briggs 1992; Chaitin et al.
1991]. In assigning registers by graph coloring, a graph is constructed
where each node represents a variable and the edges between nodes
represent the overlapping of the respective variable's lifetimes. The task is
then to "color" the graph with the number of colors equal to the number of
physical registers. If a coloring is not found, some variable is spilled to
memory and the process is repeated. As the key to good register assignment
in this scheme is the selection of a particular variable to spill, heuristics for
selection have received attention [Briggs et al. 1989] along with methods of
coloring the graph [Chow and Hennessy 1990]. Also, loops are addressed in
Hendren et al. [1992], but without regard to the number of register-to-
register transfers potentially required by their technique at the end of an
iteration.
Many researchers have felt that for particularly critical code segments,
such as the innermost loops of time-sensitive applications, an optimal
assignment is necessary. Horwitz et al. [1966] present a method for
obtaining an optimal register assignment to index registers that minimizes
the number of loads and stores. Further work either improves upon the
efficiency of the Horwitz algorithm [Luccio 1967] or extends the basic
algorithm to deal with simple loops [Kennedy 1972], but in doing so loses
optimality and degrades performance. More recent research [Hsu et al.
1989] extends the basic idea in Horwitz's algorithm to include register
assignment for general purpose registers.
In High-Level Synthesis the problem of register assignment traditionally
refers to determining the number of registers necessary to save values
Optimal Register Assignment . 253
between time-steps [Kurdahi and Parker 1987; Paulin and Knight 1989]. In
order to reduce the interconnect and multiplexor cost of scattered registers,
some researchers have focused on grouping registers into memory mod-
ules. 2 Other research has addressed the assignment of registers to loop
variables whose lifetimes are cyclic in nature [Park et al. 1993; Stok 1990].
These approaches (arbitrarily) break a cyclic variable's lifetime at loop
boundaries, creating two "coupled" variables that the assignment process
tries to assign to the same register. If the coupled variables are not
assigned to the same register, register transfers are necessarily inserted at
the end of the loop to correctly set up the next iteration. Because these
techniques were developed for register allocation, they do not consider
cases where variables are stored within various levels of a memory hierarchy

Work in code generation for embedded systems has extended the left-edge
algorithm and incorporated register classes for register assignment
[Liem et al. 1994], or formulated the problem of register assignment as an
ILP formulation [Wilson et al. 1994]. However, these techniques introduce
register-to-register moves at loop boundaries. In Lanneer [1994] a complex
searching scheme is used to navigate a large search space with many
tradeoffs, one of which is register assignment. Some work has been done in
minimizing the number of spills for an accumulator-based architecture
[Liao et al. 1995].
However, none of this previous work has addressed the issue of finding
an optimal assignment of registers to loops (i.e., an assignment of variables
to registers that requires no register-to-register transfers and minimizes
the cost due to added spill code).
3. TARGET ARCHITECTURE AND PROBLEM DESCRIPTION
An example of the architectural organization that we are targeting is found
in

Figure

1. In this architecture, an embedded processor is interconnected
with program memory (typically, read-only memory), data memory, and one
or more ASICs. This embedded processor can be realized either by a
processor core or by an ASIP. As previously mentioned, an embedded
processor may offer the functionality and datapath regularity of a general-purpose
processor (GPP), comparing with a GPP in the following: a narrower
datapath bit-width, a smaller instruction set, and a fewer number of
registers. Or, an embedded processor may offer an application-specific
instruction set with some degree of irregularity in the datapath. In either
case, the available register set may be consolidated into one register file or
may be distributed in multiple register files. Examples of the former are
the MIPS RC4000 and Sun Microsystem's microSPARC-II, and examples of
the latter are Texas Instruments' TMS series and Motorola's 56000. Thus
the task of register assignment for an embedded processor corresponds to
Ahmed and Chen [1991], Balakrishnan et al. [1988], Kim and Liu [1993], and Marwedel
[1984].
254 . D. J. Kolson et al.
either determining a mapping of program variables to the registers contained
within one register file or determining a mapping of program
variables to the registers of distributed register files while, in both cases,
honoring any access (i.e., port) restrictions to the register file(s). In addi-
tion, we model the target instruction set as n-operand instructions (also
called n-address instructions [Aho et al. 1986]).
In our approach the task of register assignment follows that of code
selection and scheduling of operations into time steps. When resource
shortages occur during the register assignment phase (i.e., when more live
variables than registers exist, thus requiring multiple variables to share
registers) spill code, or explicit data transfer operations between the
registers and data memory, becomes necessary. Given an application
containing loops, our goal is to minimize the number of transfer operations
due to spills between the registers and the data memory that will be
repeatedly executed within each loop. 3
Register assignment begins with the analysis of the intermediate representation
of the algorithm to determine the variable accesses in execution,
thus deriving the variable access stream. This intermediate representation
is a sequence of fine-grain n-operand instructions that can be efficiently
mapped to the target architecture. For instance, if a RISC processor is the
target, the intermediate representation of an algorithm might be a sequence
of 3-operand instructions, whereas, for an accumulator-based pro-
cessor, the intermediate instructions might be composed of 1- and 2-oper-
and instructions.
As an example, for the 3-operand operation A 5 B 1 1, the variable
access stream is B, A* (reads of variables before writes), where "*" denotes
a write to a variable. To denote concurrent accesses, parentheses bracket
those reads or writes performed in parallel. For example, if the operations
3 In the case of nested loops, we operate on the innermost loop.
Fig. 1. Target architecture organization.
Optimal Register Assignment . 255
are executed concurrently, then the variable
access stream is (BDE)(A*C*), as the variables B, D, and E are read
concurrently after which the variables A and C are written concurrently.
Once the variable access stream is derived, it is input to the assignment
algorithm.
4. OPTIMALLY ASSIGNING REGISTERS IN BASIC BLOCKS
Using a variant of the algorithm presented in Hsu et al. [1989], we can
derive an optimal (i.e., spill minimizing) algorithm that assigns variables to
registers in basic blocks. This algorithm, which we call OPT-Assign-BB, is
found in Figure 2. OPT-Assign-BB takes as input the variable access
stream for a code segment and the mapping of variables to registers that
immediately precede that segment (which could be null, signifying that all
registers are initially free). This algorithm then builds an assignment tree
where the nodes in the tree correspond to a variable mapping or configuration
representing the contents of each register found at some particular
point in execution and the root of the tree is the given (initial) mapping of
variables to registers. Each path in the tree from the root to a leaf is a
(unique) mapping of variables to registers.
As the assignment tree is built, each successive level in the tree is
derived by examining the variable stream and all the current configurations
to determine if they contain the variable under consideration. If the
Fig. 2. Register assignment algorithm.
256 . D. J. Kolson et al.
variable is contained within a configuration, that node is duplicated at the
next level of the tree and a zero-cost edge connects the two. When a
variable is not contained within a node, a variable access miss occurs and
spill code might be necessary. For any configuration causing an access
miss, each variable currently in that configuration is replaced in turn by an
access to the faulting variable. An edge joining the access miss node with
each of the newly created nodes represents the cost, in spill code, of going
from the first mapping to the second. This cost is composed of the cost of
(possibly) storing the replaced register if it is live and dirty 4 [the Store-
in our algorithm] and/or the cost of (possibly) loading the faulting
variable [the Load-Cost(V) in our algorithm] if this is a variable read.
Setting the load and store costs both to one gives a total cost equal to the
number of memory operations. 5 Thus if there are r registers, a faulting
configuration in the current level will generate r configurations in the next
level, resulting in an optimal, but exponential method. Heuristics can be
(and have been) used to prune this search space [Horwitz et al. 1966; Hsu
et al. 1989; Kennedy 1972].
Once the last variable access is considered, all the leaves of the assignment
tree are examined for the lowest cost node. Tracing the path from the
root to this lowest cost node will yield an assignment of registers to
variables that results in the minimal cost in terms of memory loads and
stores due to spill code, because it has exhaustively generated every
possible assignment.
In

Figure

3(a), an example code segment appears and Figure 3(b)
contains the variable access stream for this segment. For this example,
there are two registers, R1 and R2, that have been initially assigned to a
and b, respectively. The OPT-Assign-BB algorithm begins with this (initial)
mapping and constructs the assignment tree in Figure 3(c).
The first two variable accesses, to the variables a and b*, are to variables
contained in the current configuration; therefore no spill code is necessary.
However, the next access to c causes a variable access miss and spill code
becomes necessary. Two configurations are generated at the next level,
corresponding to assigning c to R1 or to R2. The left child assigns c to R1,
displacing the variable a. Because a does not need to be stored (its value is
consistent with that in memory), the spill code generated by this is the load
of c, for a cost of one. The other possibility, assigning c to R2, is represented
by the right child and displaces the variable b. Because b is dirty (it
has previously been written), b must be stored and then c is loaded, for a
cost of two.
This process, examining the next variable access(-es) and checking
whether they are contained within the current configurations, continues for
the remainder of the variable access stream and the full tree in Figure 3(c)
Every variable is assumed to have a unique memory location where it may be kept if a spill
of that variable is necessary. Dirty refers to the case where the value in a register is
inconsistent with the value stored in the memory location.
5 Priorities can be given to loads or to stores simply by changing these costs.
Optimal Register Assignment . 257
Fig.
3.
Building
an
assignment
tree.
258 . D. J. Kolson et al.
is generated. In Figure 3(c) there are some nodes that have dashed
outlines. These nodes can be pruned from the tree as there are identical
nodes at the same level that will generate identical subtrees. Within a
group of identical nodes, only the one with lowest cost need be kept,
breaking ties arbitrarily.
5. EXTENDING THE BASIC BLOCK ALGORITHM TO LOOPS
By applying the OPT-Assign-BB algorithm to the body of a loop, we get an
optimal assignment for a single execution of that code. Because this code is
contained within a looping construct, it is necessary for the register
mappings at the beginning and end of the code segment to match in order
to correctly iterate over that segment. In general, the assignment produced
by OPT-Assign-BB will not satisfy this criteria (i.e., the lowest cost configuration
at a leaf of the assignment tree does not necessarily match the
root). Thus this basic algorithm is not adequate to optimally assign
registers to loop code.
To remedy this, one might try simply to add register-to-register moves
and/or spill code (loads and/or stores) to enforce a match. However, because
the cost of this additional spill code may vary greatly from each conceivable
mapping to another, and would vary further by unrolling the loop some
number of times, OPT-Assign-BB's results, which ignore this effect, cannot
be guaranteed to be optimal. Another suboptimal approach is to "force" a
match between loop top and bottom, that is, to choose from the exponential
tree derived by OPT-Assign-BB the least cost leaf node that is identical to
the initial configuration (leaf configurations that match the root configuration
are not necessarily guaranteed to be those with lowest cost).
5.1 Our Algorithm
It is not immediately obvious how many iterations suffice to produce an
assignment that results in the minimal amount of spill code. In fact, this is
why this problem has been an open issue. If the process of unwinding a loop
and applying OPT-Assign-BB is continued, the cost may be decreased. By
iteratively unrolling one loop iteration and applying OPT-Assign-BB to the
resulting code, we can find a new loop body potentially spanning several
iterations of the original loop such that: (a) the cost of spills per iteration in
the loop body is minimal; and (b) the entry and exit configurations of the
new loop match.
Our algorithm for assigning registers to loop code, which we refer to as
OPT-Assign-LOOP, is found in Figure 4. The general structure of our
algorithm is to iteratively unroll the loop one iteration and then to apply
OPT-Assign-BB to the new iteration once for each possible previous iteration
exit mapping. Then the algorithm analyzes each resulting exit mapping
of that new iteration to determine if there are matches between those
nodes and iteration ancestors (i.e., a node in the assignment tree that lies
on the path from the root to this node and also lies on an iteration
boundary). If so, a legal register assignment to the unrolled loop has been
Optimal Register Assignment . 259
found. If not, then that exit mapping becomes one of the mappings that will
be used as an initial configuration to the next iteration.
Each time a match is found, our algorithm computes the average cost per
iteration for that assignment (because the assignment may span multiple
iterations). If the loop were fully unrolled, the assignment with the lowest
average cost per iteration would be the optimal assignment for the loop.
Because full unrolling of the loop is not necessarily practical, we have parameterized
our algorithm with K, the number of unrollings of the loop body to
perform. The lowest cost mapping found with this "cut-off" scheme is a local
minimum, but is "global" over the number of iterations unrolled so far (K).
Note that this algorithm must always get an average cost less than or equal to
what OPT-Assign-BB would get because we deal strictly with the costs
calculated by OPT-Assign-BB and add nothing more-beyond unrolling.
5.2 Heuristic Pruning
Although our algorithm may be computationally prohibitive even for moderately
long loops, it does provide a strong starting point for determining
Fig. 4. Loop register assignment algorithm.
260 . D. J. Kolson et al.
good heuristics. The computational complexity in this algorithm arises
from the replacement of each register in the current configuration when a
variable read or write miss occurs. Our heuristic modification is a simplistic
pruning strategy where only the m best configurations are kept for
future expansion once all mappings at a particular level are generated.
That is, for each node in the current level, when an access miss occurs, all
possibilities for spills are considered. Then, of those newly generated nodes,
the m lowest cost nodes are retained for consideration.
6. CONVERGENCE AND OPTIMALITY OF THE LOOP ALGORITHM
Previously it was not known whether optimal register assignment for a loop
could be accomplished, regardless of the efficiency of the algorithm. The
difficulty in ensuring optimality for the overall loop requires matching of
registers at the top and bottom of the loop body and can impose additional
spills. To optimally minimize these spills, loop unwinding with different
register assignments to each unwound iteration may be needed. Further-
more, it was not known whether any finite unwinding can be guaranteed to
converge and result in an optimal assignment.
To answer these questions, we introduce the notion of a configuration
graph. A node in the configuration graph corresponds to a specific mapping
of variables to registers found at an iteration boundary, and a directed edge
in the configuration graph corresponds to the cost in spill code of using the
source node as the initial mapping to an iteration, applying the loop
algorithm and having the sink node as one of the resultant nodes. Thus the
edge represents the cost of spill code with the source node as the initial
register assignment to, and the sink node resulting from, an iteration of the
loop.

Figure

5 illustrates the method of building a configuration graph. We use
the same assignment tree from Figure 3 and have labeled the leaf nodes. A
partial configuration graph, shown in (b), can be constructed from the
assignment tree in (a). Traversing a path from the root configuration,
which has been labeled P, to each leaf configuration gives a directed edge in
the configuration graph from P to that respective node with a weight equal
to the cost of the path. For instance, the path from the root to the first leaf
node on the left, labeled Q, has a cost of three. Thus an edge in the
configuration graph from P to Q is added with that edge having weight
three. Similarly, other edges are added to the configuration graph by
traversing the various paths. The partial configuration graph in (b) results.
To construct the complete graph requires that we build the assignment
trees for each possible exit configuration.
6.1 Convergence
In order to guarantee that our algorithm converges, it must be shown that
by unrolling, new exit configurations (i.e., mappings of variables to regis-
ters) that previously did not exist are not generated. Because our algorithm
exhaustively replaces registers each time a variable access miss occurs, all
Optimal Register Assignment . 261
conceivable mappings are generated. Stated another way, when an unrolling
of the loop body and assignment to that iteration is performed, the costs
associated with going from the initial to the derived exit mappings become
known. Thus the edges in the configuration graph that connect the initial
configuration with all possible exit configurations are generated. If the
assignment algorithm is again applied to each of these nodes (e.g., unroll
the loop body for another iteration), directed edges from each of those exit
configurations to one another are obtained. Convergence of our algorithm,
therefore, is equivalent to finding a cycle in the configuration graph. Thus
our algorithm converges because the number of variables and the number
of registers is finite and therefore the number of permutations of the
variables in the registers is finite, although exponential.
6.2 Optimality
An optimal assignment is one in which the memory traffic is minimized.
When the loop body is unrolled, an optimal assignment is an assignment
that has minimal memory traffic or spill cost over the iterations that are
Fig. 5. Building a configuration graph from assignment trees.
262 . D. J. Kolson et al.
contained within the unrolled loop. Thus in the optimal assignment, the
ratio of the spill cost for the new unrolled loop body to the number of
iterations it contains is minimized. In the configuration graph this corresponds
to the ratio of the total cost of some cycle to the number of nodes in
that cycle.
Therefore an optimal assignment is found by examining the average costs
of all possible cycles of all possible lengths in the configuration graph and
taking the minimum. Note that this does not necessarily correspond to the
minimal cycle of length one in the graph. 6 In the worst-case it is possible
that the optimal cycle must make a complete tour of the graph.
7. EXTENDING THE MODEL TO DISTRIBUTED MEMORIES
The algorithm presented earlier for register assignment in loops has the
underlying assumption that access to all available registers is equivalent,
as is found, for instance, in general-purpose processors and some embedded
processors. That is, all registers are consolidated into one register file and
any variable mapped to a register is uniformly available to any operation
using that variable. However, in the case of an architecture where the
available registers have been partitioned into disjoint register files or some
of the available registers have specialized purposes, this assumption must
be modified to generate feasible register assignments. Previously there was
the assumption that enough ports on the register file exist to support the
reading and writing of all variables accessed in a particular step. However,
it is possible that restrictions are present on the number of registers that
are concurrently accessible (i.e., the number of read/write ports on a
register file constrains the number of reads/writes to that register file).
In this section we discuss the extension of our algorithm to loop register
assignment when the target embedded processor architecture contains
distributed register files and/or special-purpose registers and specific restrictions
on register accessing exist. We start by discussing the addition of
register classes to the model. Then we consider separate modifications
necessary to our algorithms to handle special-purpose registers and distributed
register files.
7.1 Adding Register Classes to the Model
To extend our algorithms, we introduce the notion of register classes.
Register classes have been used in compilers [Aho et al. 1986; Stallman
1992] and in microcode synthesis [Feuerhahn 1988; Liem et al. 1994] to
denote functional equivalences between registers. However, combining all
registers having the same (potential) usages into one class is not precise
enough for register assignment to our target architecture class. To see this,
consider a simple case where two register files are composed of "general-
purpose" registers, each register file connected to a different ALU. Clearly
6 A cycle of length one would imply that some assignment to the loop body is minimal and its
initial configuration naturally (i.e., without spills or moves) matches its exit configuration.
Optimal Register Assignment . 263
any operation scheduled on either ALU must have its operands present in
the respective register file. However, if the collective registers are grouped
into one register class (called "general-purpose"), it is possible that the
necessary operands have been assigned in such a way as to honor the
register classes, but be invalid for execution, thus making that register
assignment invalid. The main cause of this problem is not due to registers
being grouped by their equivalency, but rather how the equivalency is
established.
In our approach, two types of register classes are defined: connectivity
register classes and operation register classes. The connectivity register
class (conn_RC) defines the equivalency between registers as a function of
the architecture's connectivity, whereas the operation register class
(oper_RC) defines the equivalency between registers as a function of an
operation's semantics. The motivation for deriving both these classes is
that the connectivity of the architecture defines which registers may be
read from or written into by some functional unit, whereas the semantics of
a particular operation executing on a particular functional unit may
preclude the use some of the connected registers (a load operation, for
instance, may require that the memory address reside in a specific register,
and the functional unit that executes that load operation may be connected
to many registers that do not serve the same purpose).

Figure

6 contains an algorithm to derive the register classes for a given
architecture. A connectivity register class is derived for each of the inputs
and outputs of each functional unit in the architecture based upon which
registers may be accessed by that input or output. Operation register
classes are derived by examining which operations a functional unit can
execute and selecting all the readable (and writable) registers imposed by
an operation's semantics. In a large number of cases, the conn_RC and
oper_RC will be equivalent.
Fig. 6. Algorithm to derive register classes.
264 . D. J. Kolson et al.
7.2 Extension to Special-Purpose Registers
The algorithm OPT-Assign-BB exhaustively generates variable mappings
by placing a variable in each register either when a read miss occurs
(requiring a load of the variable) or when a variable is written. When
access to all registers is uniform, this strategy is correct. However, when
some registers have specialized usages, this strategy generates some mappings
that are invalid as variables have been assigned to registers that
cannot perform the required specialized function. Thus it is necessary to
restrict the placement of variables into registers so that variables only
reside in registers that can perform the necessary functionality.
With the notion of register classes, we can extend the OPT-Assign-BB
algorithm to handle registers that have specialized usages. When a variable
causes an access miss, only those registers that perform the necessary
functionality are considered. These are found by intersecting the operation
register class for the accessing operation and the connectivity register class
for the functional unit that is executing that operation. Recall that we
perform register assignment on a scheduled dataflow graph. Thus when
performing register assignment the operations (and their types) that access
variables, as well as the functional units that those operations execute on,
are known-retrieving this information is a simple matter.

Figure

7 contains an extended version of the OPT-Assign-BB algorithm
for register assignment with specialized register usages. The function op_of
returns the operation that currently accesses the variable V. From this, the
type of operation and the functional unit that executes the operation are
found via calls to functions OperationType and FunctionalUnit, respec-
tively. Then the appropriate operation register class and connectivity
register class are found and intersected. RC_intersect, the intersection of
these classes, defines the feasible registers in which a variable V may
reside. If the variable is in one of those registers, then no spill code is
necessary. If not, then all the registers contained in RC_intersect are
candidates for replacement and spill code is generated.
7.3 Extension to Multiple Register Files
To extend our algorithms to assign registers to multiple register files
requires that the notion of a node in the assignment tree be altered. In
assigning registers to an architecture with a consolidated register file, the
semantics of a node are that all registers are uniformly available. For
instance, if there are eight registers filled with the variables a- h, a
mapping of variables to registers is represented as {a,b,c,d,e,f,g,h}, signifying
that a is mapped to register one, b is mapped to register two, and so
on.
To model multiple register files, we change the information contained in
a node to reflect the grouping of registers into a register file. Each node in
the assignment tree is then composed of a number of register sets equal to
the number of register files.
Optimal Register Assignment . 265
7.3.1 Assigning Variables. Figure 8 contains an extended version of the
OPT-Assign-BB algorithm that assigns registers to multiple register files.
The main modification required when multiple register files exist is that
only the registers in the respective register file are examined to determine
if a variable is resident. If a variable is not contained within the necessary
register file, rather than loading it from memory, a check is first made to
see if the variable is contained within one of the other register files. If so,
then a move operation is used to transfer the value into the necessary
register file if the necessary connections exist, as this transfer is likely to
have a lower latency than a load from (slower) memory. Otherwise, the
variable is loaded from memory. Once a spill is considered, 7 any access
restrictions present on the register files, such as the number of registers
that can be simultaneously accessed, are considered. If the restrictions are
satisfied, then the assignment is valid and is maintained for future
assignment, otherwise the mapping represents an assignment that causes
an access conflict to exist and the node is removed from future consideration

7 We can assign different costs for spilling to memory, fetching from memory, and fetching
from another register file.
Fig. 7. Extending OPT-Assign-BB to special-purpose registers.
266 . D. J. Kolson et al.
7.3.2 A Note on Optimality. With the addition of register classes and
extension to special purpose registers, our algorithm derives optimal (i.e.,
spill minimizing) results. However, with multiple register files and the
version of our algorithm presented, it may be possible that suboptimal
results are obtained. Previously, when a variable was assigned to a
register, all registers were viewed as candidates for replacement. Extending
this to cases where some registers have special purposes merely
removes some number of registers as candidates (and thus serves to
restrict the growth of the assignment tree). However, in the case of
multiple register files, our algorithm may no longer derive an optimal
solution. When one variable is displaced by another in the same register
file, that displaced variable may need to be stored into data memory,
requiring a load when it is needed in the future. However, if a free register
exists in some other register file, then it might be possible to "store" the
displaced value there temporarily until its future use. Further, even if
there is no free register in the remote file, it still possible that some remote
variable can be spilled without loss of performance, thus freeing a register.
In general, this effect can have cascading effects and become quite complex,
with a variable "hopping" from register file to register file until its future
use. Extending our algorithms to handle this would be straightforward, but
impractical.
Fig. 8. Extending OPT-Assign-BB to multiple register files.
Optimal Register Assignment . 267
8. EXPERIMENTS AND RESULTS
To examine the benefits of our technique, we conducted two sets of
experiments. The first targeted architectures with consolidated register
files, and the second targeted architectures with partitioned register files
and special use registers.
For both experiments our benchmark suite consisted of six numerical
codes written in C and then compiled into RISC-like code which is typical of
the code executed by most embedded core processors and ASIPs. From
those codes, the variable access streams were derived and used as input to
our algorithms. For each experiment, we derived register assignments from
the optimal basic block algorithm (OPT-Assign-BB), the optimal loop algorithm
(OPT-Assign-LOOP), and a heuristic version of the loop optimal
algorithm (heuristic OPT-Assign-LOOP), and counted the number of spills
(i.e., loads and stores) for those assignments.
In generating assignments for the OPT-Assign-BB algorithm, the registers
were assumed to be empty upon initial assignment to the loop. Because
OPT-Assign-BB is not guaranteed to produce an assignment in which the
initial and exit mappings match, we noted the point at which the registers
became full (i.e., the point where more live variables than registers exist)
and introduce spill code and/or moves to match usage from the minimal
(leaf) node to the previously noted (initial) node. Also, in order to create
opportunity for OPT-Assign-BB to do well, we used enlarged loop bodies
constructed by unwinding the loops three times. Thus some of our results
for OPT-Assign-BB are not whole numbers as they represent averages for a
single iteration of the original loop.
8.1 Experimentation With a Consolidated Register File
We use the microSPARC-II as a target for code generation to an architecture
with a consolidated register file as the microSPARC-II has a RISC
instruction set similar to that found in many embedded core processors.
Using the variable access streams, register assignments were produced by
the OPT-Assign-BB, OPT-Assign-LOOP, and heuristic OPT-Assign-LOOP
algorithms. From those register assignments, the number of spill code
operations were counted. In Section 8.1.1, we compare the OPT-Assign-BB
and OPT-Assign-LOOP results. Next we compare our heuristic version of
OPT-Assign-LOOP to the graph coloring approach implemented in the Gnu
Compiler 8 in Section 8.1.2. Section 8.1.3 compares the optimal and
heuristic loop versions and Section 8.1.4 compares the number of iterations
spanned by the optimal and heuristic loop assignments.
8.1.1 Comparison of OPT-Assign-BB and OPT-Assign-LOOP. Table I
contains our observed results and contains the number of spills per
iteration for OPT-Assign-BB and OPT-Assign-LOOP, as well as the absolute
percentage improvement of OPT-Assign-LOOP over OPT-Assign-BB
8 The code produced by this compiler is generally accepted to be of high quality [Granlund and
Kenner 1992].
268 . D. J. Kolson et al.
measured as: (Spills BB 2 Spills Loop )/Spills Loop . There is a general trend for
the percentage improvement to increase as the number of registers increases
(i.e., the disparity between the loop assignments and the basic
block assignments increases as the number of registers increases) that can
be attributed to the fundamental difference between OPT-Assign-BB and
OPT-Assign-LOOP: OPT-Assign-BB assigns registers without regard to the
effect of iterating on those register usages, whereas OPT-Assign-LOOP
examines the iterating effects on register usages while naturally discovering
a minimal assignment for a loop. The minimal assignments produced by
OPT-Assign-BB are not guaranteed to match at the loop entry and exit
points. Therefore some spill code becomes necessary to match the register
usage at those two points. However, because OPT-Assign-LOOP explores
the possibilities of keeping the variables in registers found at the loop end
as it assigns registers to the next iteration, it discovers better register
usages and places for inserting spill code. Essentially, OPT-Assign-LOOP

Table

I. Basic Block Optimal vs. Loop Optimal for microSPARC-II.
Optimal Register Assignment . 269
produces superior results as it naturally (i.e., without additional loads,
stores, and/or register moves) finds a match between loop entry and exit
configurations during the assignment process.
8.1.2 Comparison of Heuristic OPT-Assign-LOOP and Graph Coloring.
Gcc was configured to produce SPARC code and the register assignment
module was modified so that gcc would produce code that used four, six and
eight registers. 9 For our heuristic version of OPT-Assign-LOOP we used a
pruning factor parameter m 5 2 best configurations. 10 Table II summarizes
the results of the spill code produced by gcc as well as our heuristic
algorithm. Percentage improvement is measured as: (Spills gcc 2 Spills heur )/
Spills heur .
In all cases, our heuristic produced assignments superior to gcc. In the
graph coloring approach, variables are assigned to registers for their entire
lifetime. In some segments of code, where a variable assigned to some
register is currently not being accessed, keeping that variable in a register
causes high "register pressure" where more loads and stores of other
9 Gcc produced an internal compiler error when the real register count was set to two.
Recall that our pruning strategy keeps the m best configurations after considering all
possibilities each time a variable miss occurs.

Table

II. Graph Coloring vs. Heuristic for microSPARC-II.
270 . D. J. Kolson et al.
variables (which currently are being accessed) are generated than is
necessary if the unaccessed variable had been previously spilled to memory
during this segment.
Another interesting result is that our heuristic produces assignments
that are better than OPT-Assign-BB (the optimal assignment for basic
blocks) in a number of cases. Comparing Tables I and II shows that our
heuristic results are better than optimal basic block assignment by an
average of 8%. Although this is a heuristic version of the loop algorithm, it
is able to derive better results than OPT-Assign-BB because it has the
ability to find matching register assignments over loop execution that the
OPT-Assign-BB algorithm does not.
8.1.3 Comparison of OPT-Assign-LOOP and Heuristic OPT-Assign-
LOOP.

Table

III contains the number of spills per iteration for the
OPT-Assign-LOOP and heuristic OPT-Assign-LOOP algorithms in columns

Table

III. Comparison of Loop Assignments for microSPARC-II.
Optimal Register Assignment . 271
three and four, respectively. Column five contains the heuristic results'
percentage within optimal, measured as: (Spills Heur 2 Spills Opt )/Spills Opt .
For this measure, lower numbers are better (i.e., the lower the number, the
closer the heuristic is approximating the optimal). In half the cases (12 of
24), the heuristic produced results that are equal to the optimal. Also, 71%
of the cases (17 of 24) are within 10% of the optimal, and 92% (22 of 24) are
within 20% of the optimal. These results demonstrate that, although the
optimal may be computationally prohibitive, the simple heuristic version,
which executes in a matter of seconds, produces results that are acceptably
close enough to the optimal.
8.1.4 Code Size of Loop Register Assignments. One concern of our
technique is the increase in code size that results from loop unrolling as our
method typically produces register assignments that span multiple itera-
tions. This is especially a concern in the context of embedded code generation
where the program code resides in ROM, and thus directly affects the

Table

IV. Comparison of Loop Code Sizes for microSPARC-II.
272 . D. J. Kolson et al.
ROM size. In Table IV we have noted the number of iterations spanned by
the assignments produced by OPT-Assign-LOOP and heuristic OPT-Assign-
LOOP 11 in columns three and four, respectively. Column five of Table IV
indicates whether the heuristic version derived assignments with the same
amount of spill code as the optimal.
In the majority of cases (18 of 24), the number of iterations spanned by
both versions is the same. Of those cases, the heuristic version derived
assignments with the same amount of spill code as the optimal in nine
cases (50%). There are a few cases (5 of 24) where the heuristic spanned
more iterations than the optimal and, of those, the same amount of spill
code was produced in three cases. There is one case where the heuristic
version spanned a fewer number of iterations than the optimal due to the
nature of the heuristic. However, in this case, the heuristic version produced
more spill code. Overall, the number of iterations spanned by the
loop assignments ranges between two and five, which, we feel, is within
acceptable limits for the performance gain resulting from fewer memory
accesses.
8.1.5 Run-Time of the Algorithms. Because the methods proposed here
are exponential in nature, the execution time of these techniques is a
concern. In Table V we have noted the minimum, average, and maximum
execution times in CPU seconds of the OPT-Assign-BB, OPT-Assign-LOOP,
and Heuristic OPT-Assign-LOOP algorithms as well as the register allocation
phase of gcc executing on a Sun 4/30 system running UNIX. Although
the run-times of the exponential methods (OPT-Assign-BB and OPT-As-
sign-LOOP) are on the order of several CPU minutes, they are reasonable
in the context of embedded code generation where longer compile times can
be tolerated to obtain high-quality code.
Also included in Table V are the average number of spills per iteration
for each of the register configurations previously studied. These results
demonstrate the tradeoff between run-time and quality of the produced
register assignment. Again, the run-times of the OPT-Assign-BB and
OPT-Assign-LOOP are on the order of several CPU minutes, but the
quality of the assignments produced (as compared with the graph coloring
approach) are at least 40% better for both, measured as (Heuristic 2
Optimal)/Optimal, and increases as the number of registers increases. Also
11 Results for the two-register case for the heuristic version appear in this table, but do not
appear in Table II because as mentioned earlier they are not available for gcc.

Table

V. Comparison of Running Times for microSPARC-II.
Optimal Register Assignment . 273
the heuristic version of the loop algorithm derives results that are close to
the optimal, whereas its run-time is comparable to that of gcc's register
allocation phase.
8.2 Experimentation With Distributed Register Files
We use the TMX320C44 as an example of an architecture with distributed
register files. Figure 9 shows a simplified view of the architecture and in
Section 8.2.1 we give a brief overview. For the purposes of code generation
we use "scaled-down" versions of the TMX320C44 in which we parameterize
the number of registers for the register banks. In our tables, the "#
Registers" column denotes this number (i.e., a "2" means that each bank
contained two registers-two extended precision, two general-purpose, and
two auxiliary registers-for a total of six). We then generated assignments
with OPT-Assign-BB, OPT-Assign-LOOP, and our heuristic version of
OPT-Assign-LOOP. In Section 8.2.2 we compare the results of basic block
optimal and loop optimal. Because we did not have access to a commercially
available compiler for the TMX320C44, a comparison between our heuristic
and another heuristic is unavailable. However, in Section 8.2.3, we compare
the results of OPT-Assign-LOOP to the heuristic OPT-Assign-LOOP.
Section 8.2.4 compares the code size of the loop assignments.
8.2.1 TMX320C44

Overview

. Figure 9 shows a simplified view of the
TMX320C44. In this architecture, there are three register files: Extended
Precision Registers which are 40-bits wide and used for floating-point and
long integer arithmetic; Auxiliary Registers which are 32-bits wide and
used as address pointers with dedicated address generation hardware to
auto-increment and auto-decrement address values; and General-Purpose
Registers which are 32-bits wide. All register files are connected to the
Reg1 and Reg2 buses and available to the Multiplier and ALU. The
Multiplier and ALU may both write to the Extended Precision Registers or
Fig. 9. Simplified view of TMX320C44.
274 . D. J. Kolson et al.
one of them may write to either the Auxiliary Registers or the General
Purpose Registers. In addition, an operand may be supplied to the Multiplier
or ALU by the memory.
8.2.2 Comparison of OPT-Assign-BB and OPT-Assign-LOOP. Table VI
contains our observed results and contains the number of spills per
iteration for OPT-Assign-BB and OPT-Assign-LOOP, as well as the absolute
percentage improvement of OPT-Assign-LOOP over OPT-Assign-BB
measured as (Spills BB 2 Spills Loop )/Spills Loop . As before, there is a general
trend for the percentage improvement to increase as the number of registers
increases due to OPT-Assign-LOOP's ability to naturally match the
register usages at loop top and bottom. Upon inspection of the assignments
produced it was noted in some cases that the assignments produced by the
basic block scheme assigned an address variable to a general purpose
register near the end of the iteration. This variable was heavily used at the
top of the loop, so more spill code (spills of other address variables
currently within the Auxiliary Registers) than necessary was generated to
accommodate that variable.
8.2.3 Comparison of OPT-Assign-LOOP and Heuristic OPT-Assign-
LOOP.

Table

VII presents the results of the spill code produced by the
optimal and heuristic algorithms in columns three and four, respectively.
Column five contains the heuristic results' percentage within optimal,
measured as (Spills Heur 2 Spills Opt )/Spills Opt . For this measure, lower
numbers are better (i.e., the lower the number, the closer the heuristic is
approximating the optimal). In a few cases (3 of 12), the heuristic produced
results equal to the optimal. For 58% of the cases (7 of 12) results were
produced that were within 15% of the optimal. For the rest of the cases (5 of

Table

VI. Basic Block Optimal vs. Loop Optimal for TMX320C44.
Optimal Register Assignment . 275
12), the percentage within optimal is higher, however; the actual difference
in spill code produced is only one instruction.
8.2.4 Code Size of Loop Register Assignments. Again, because code size
directly affects the size of the program ROM, we study the number of
iterations produced by our loop assignments. Table VIII contains the
number of iterations spanned by each of the loop methods for the given

Table

VIII. Comparison of Loop Code Sizes for TMX320C44.

Table

VII. Comparison of Loop Assignments for TMX320C44.
276 . D. J. Kolson et al.
number of registers, as well as indication of whether the heuristic method
produced an equal amount of spill code as the optimal. In the majority of
cases (9 of 12) our heuristic derived assignments that spanned the same
number of iterations as the optimal, and, of those, generated the same
amount of spill code in three cases (33%). In the other cases (3 of 12), the
heuristic assignments spanned one more iteration, producing the same
amount of spill code in one case (33%). The overall range of the number of
iterations spanned by the assignments is between two and four, which we
believe is within acceptable limits.
8.2.5 Run-Time of the Algorithms. Again we note the run-time of the
algorithms, in this case for the TMX320C44 results. Table IX contains the
minimum, average, and maximum execution times in CPU seconds of the
OPT-Assign-BB, OPT-Assign-LOOP, and Heuristic OPT-Assign-LOOP algorithms
executing on a Sun 4/30 system running UNIX. Included in Table
IX are the average number of spills per iteration for each of the register
configurations previously examined with the TMX320C44. Although another
heuristic is unavailable for comparison, the heuristic loop algorithm
derives results that are close to the optimal, and its run-time is efficient
enough to be practical.
8.2.6 Using the Full Register Set. Previously our experimentation used
a scaled-down model of the TMX320C44 in which the number of registers in
each register file was reduced. In this section we present results for
register allocation to one benchmark where the number of registers used
for allocation is the actual number in the TMX320C44 architecture-8
auxiliary registers, 12 extended precision registers and 14 general-purpose
registers. The benchmark selected for this is a partial differential integration
excerpt. The results for this experiment may be found in Table X.
Columns two and three give the number of spills for the basic block and
loop methods, respectively. Column four gives the percentage improvement
of the loop method over the basic block method. These results demonstrate
that, in the presence of realistic resource constraints, our technique, which
derives an assignment of variables to registers that naturally match at loop
boundary points, has a definite advantage over the optimal basic block
method, which arbitrarily forces register usages.

Table

IX. Comparison of Running Times for TMX320C44.
Optimal Register Assignment . 277
9. CONCLUSION
In this article we have motivated and presented an algorithm that optimally
assigns registers to loops. In this case an optimal assignment is one
in which the memory traffic resulting from spill code is minimized. Our
work answers the long-standing question of whether it is possible in
principle to achieve optimal (minimal) spill code in loops. We have demonstrated
the feasibility of using our technique for the task of register
assignment in embedded code generation by conducting experiments on
RISC-like code typical of embedded core processors. We have also extended
our algorithm to assign registers to irregular datapaths, such as those
found in many ASIPs, where some registers have specialized uses and/or
registers are partitioned into multiple register files. Experimentation with
our methods has demonstrated that heuristic methods obtain suitable
performance, while outperforming the graph coloring-based approach used
by the Gnu C compiler (gcc).



--R


Compilers: Principles
Allocation of multiport memories in data path synthesis.
IEEE Trans.
Register coloring via graph coloring.
Coloring heuristics for register allocation.

Register allocation via coloring.
The priority-based coloring approach to register alloca- tion

Eliminating branches using a superoptimizer and the GNU C compiler.
A register allocation framework based on hierarchical cyclic interval graphs.
Index register allocation.
On the minimization of loads/stores in local register allocation.
Spill Code Results Using All Registers of TMX320C44.

Utilization of multiport memories in data path synthesis.
REAL: A program for register allocation.
Data routing: A paradigm for efficient data-path synthesis and code generation
Instruction selection using binate covering for code size optimization.
Register assignment through resource classification for ASIP microcode generation.
A comment on index register allocation.
The MIMOLA design system: Tools for the design of digital processors.


Code Generation for Embedded Processors.
Register allocation for data flow graphs with conditional branches and loops.

Using and Porting GNU CC.
Interconnect optimisation during data path allocation.
Efficient code generation for in-house DSP-cores
An integrated approach to retargetable code generation.
revised January
--TR
REAL: a program for REgister ALlocation
Coloring heuristics for register allocation
On the Minimization of Loads/Stores in Local Register Allocation
The priority-based coloring approach to register allocation
Utilization of multiport memories in data path synthesis
Register allocation via graph coloring
Register assignment through resource classification for ASIP microcode generation
Data routing
An integrated approach to retargetable code generation
Tree-based mapping of algorithms to predefined structures
Index Register Allocation
A Register Allocation Framework Based on Hierarchical Cyclic Interval Graphs
Interconnect optimisation during data path allocation

--CTR
Catherine H. Gebotys, Low energy memory and register allocation using network flow, Proceedings of the 34th annual conference on Design automation, p.435-440, June 09-13, 1997, Anaheim, California, United States
Wei-Kai Cheng , Youn-Long Lin, Code generation of nested loops for DSP processors with heterogeneous registers and structural pipelining, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.3, p.231-256, July 1999
heuristic modification;loops;storage allocation;minimal spill code;real-time systems;scientific code;data memory access;optimal register assignment;embedded code generation;program control structures;optimisation;exponential algorithm;live variables