Efficient global register allocation for minimizing energy consumption.
Data referencing during program execution can be a significant source of energy consumption especially for data-intensive programs. In this paper, we propose an approach to minimize such energy consumption by allocating data to proper registers and memory. Through careful analysis of boundary conditions between consecutive blocks, our approach efficiently handles various control structures including branches, merges and loops, and achieves the allocation results benefiting the whole program. The computational cost for solving the energy minimization allocation problem is rather low comparing with known approaches while the quality of the results are very encouraging.
Introduction
Today's high demand of portable electronic products makes low energy consumption as important
as high speed and small area in computer system design. Even for non-portable high performance
systems, lower power consumption design helps to decrease packing and cooling cost and increase
the reliability of the systems [25]. A lot of research has been done in improving the power
consumptions of various components in computer systems [8, 13, 19, 20, 25]. In particular, it is
well recognized that access to dierent levels of storage components, such as register, cache, main
memory and magnetic disk, diers dramatically in speed and power consumption [8, 17]. Hence
allocation of variables in a program to dierent storage elements plays an important role toward
achieving high performance and low energy consumption [13]. With today's IC technology and
computer architecture, memory read/write operations take much more time and consume much
more power than register read/write operations [3, 8]. For some data-intensive applications,
energy consumption due to memory access can be more than 50%[16]. In this paper, we focus on
the problem of allocating variables in a program between registers and main memory to achieve
both short execution time and low energy consumption.
Register allocation for achieving the optimal execution time of a program on a given system
is a well known problem and has been studied extensively. In general, existing results can be
divided into two categories, local register allocation [5, 15, 18] and global register allocation
[2, 4, 11, 14, 22, 23, 27, 28, 29]. A local register allocator considers the code in one basic block
(a sequence of code without any branch) at a time and nds the best allocation of the variables
in that basic block to achieve the minimum execution time. A global allocator deals with code
containing branches, loops, and procedure calls. The global register allocation problems are in
general NP-hard [22] and can be modeled as a graph-coloring problem [1, 4, 6, 7, 11]. Integer
linear programming approaches and heuristics have been proposed to solve the global register
allocation problems [22, 14].
However, optimal-time register allocations do not necessarily consume the least amount of
energy [8, 19, 20]. Some researchers have recognized this challenge and have proposed interesting
approaches to deal with the optimal-energy register allocation problem [9, 13, 25]. Chang and
Pedram [9] gave an approach to solve the register assignment problem in the behavioral synthesis
process. They formulated the register assignment problem for minimum energy consumption
as a minimum cost clique covering problem and used max-cost
ow algorithm to solve it. But
memory allocation is not considered in [9]. Gebotys [13] modeled the problem of simultaneous
memory partitioning and register allocation as a network
ow problem and an ecient network
ow algorithm can be applied to nd the best allocation of variables in a basic block to registers
and memory. However, the work in [13] is only applicable to basic blocks.
In this paper, we extend the work in [13] by investigating the problem of register and memory
allocation for low energy beyond basic blocks. We consider programs that may contain any
combination of branches, merges, and loops. The basis of our approach is to perform the allocation
block by block. By carefully analyzing boundary conditions between consecutive blocks, we are
able to nd the best allocation for each block based on the allocation results from previous blocks.
In this way, we maintain the global information and make allocation decision to benet the whole
program, not just each basic block. Our approach can be applied to dierent energy and variable
access models. The time complexity of our algorithm is O(b l(n; k)), where b is the total number
of blocks and l(n; k) is the time complexity for register allocation in a single block that has n
variables and k available registers. The function l(n; k) is either O(nlog n), O(knlog n), or O(kn 2 ),
depending on the dierent energy and access models used.
The rest of the paper is organized as follows. Section 2 reviews the energy models and known
approaches for local register allocation for low energy. We also give an overview of how our
allocation approach works. Section 3 gives our approach to do the allocation for the branch
control structure. Section 4 presents our algorithm for low energy register allocation for the
merge structure in a control
ow graph. In section 5, we discuss how to treat loops to get better
register allocation results. Section 6 summarizes the experimental results and concludes with
some discussions.

Overview

Allocating variables to dierent levels of storage components is usually done by a compiler. Many
factors can aect the allocation results. There are a number of techniques that can be applied to
reduce the number of cycles needed to execute a program, including instructions reordering and
loop unrolling. In this paper, we assume that such optimization techniques have been applied to
the program and a satisfactory schedule of the program is already given.
2.1 Energy models and known approaches
be the set of variables in the program under consideration. Given a
schedule, the lifetime of a variable v in a basic block is well dened and is denoted by its starting
time, t s (v), and nishing time, t f (v). We use VR (resp., VM ) to represent the set of variables
assigned to the k available registers (resp., memory). Furthermore, let e M
wv ) be the
energy consumed by reading (resp., writing) variable v from (resp., to) memory and e R
wv ) be the energy consumed by reading (resp., writing) variable v from (resp., to) registers. If v
is not specied, e M
r
represents the energy consumed by one read (resp., write) access to
the memory and e R
r
represents the energy consumed by one read (resp., write) access
to registers. Denote the total energy consumed by a given program as E. Then the objective of
the register allocation problem is to map each variable v 2 V to register les or memory locations
in order to achieve the least energy consumption due to data accesses, that is, to minimize
v2VR
Dierent energy models and dierent data access models have been proposed in the literatures
[5, 8, 9, 13, 20]. Depending on the particular models used, the calculation of energy consumption
varies. One of the energy model is the static energy model SE, which assumes that references
to the same storage component consume the same amount of energy [8]. This model is like the
reference-time model, where accesses to the same storage component take the same amount of
time, no matter of what is the value of the referenced data. In [9, 20], the authors proposed a
more sophisticated energy model, called activity based energy model AE, capturing the actual
data conguration in a storage. Under this model, the energy consumed by a program is related to
the switched capacitance of successive accesses of data variables which share the same locations.
The switched capacitance varies for dierent access sequences. In particular, the product of the
Hamming distance, the number of bits two data items dier [10], or other measurements [9] and
the total capacitance of a storage is used to represent the switched capacitance for two consecutive
references.
Whether a data variable is read only once (SR) or multiple times (MR) after it is dened
(written) also has an eect on the overall energy estimation. Carlisle and Lloyd [5] presented
a greedy algorithm for putting the maximum number of variables into registers to minimize the
execution time of a basic block under the signal read model. Their approach also gives an optimal
energy consumption for the static energy model. It takes O(nlog n) time and is quite easy to
implement.
For the multiple-read case, the algorithm proposed in [13] uses a graph which can have O(n 2 )
edges in the worst case. A better graph model is given in [5], which has only O(n) edges. Applying
the minimum cost network
ow algorithm, the optimal-time solution, which is also the optimal-
energy solution, can be obtained in O(knlog n) time [5] rather than O(kn 2 ) as in [13].
As one can see, dierent models result in dierent computational overhead in computing
energy consumption. For example, the AE-MR model is the most comprehensive and also most
computationally expensive one. Depending on the availability of the models, the architecture
features of a system, and the computational overhead that one is willing to incur, any of the
above models may be used in energy consumption estimation. Therefore, we consider all the two
energy models and the two variable access models in our paper.
For the activity based energy model, we will only consider it for register le access to simplify
the problem formulation. (Adopting the activity based model for memory is a simple extension
to the algorithm discussed later in this paper.) Under this model, the total energy consumption
of a program can be calculated as
is the Hamming distance between v i and v j , designates that v j is accessed
immediately after v i and that v i and v j share the same register, C R
rw is the average switched
capacitance for register le reference and VR is the operational voltage of the register le.
The objective for optimal energy allocation is to minimize the objective function (2). For both
the single read and multiple read models, Gebotys [13] formulated the problem as a minimum
cost network
ow problem with a solution of O(kn 2 complexity. The cost for each edge in
the network
ow problem for dierent read models is also dierent.
In some designs, it is desirable to allow a variable to be assigned to registers in one time interval
and switched it to memory in another time interval, in order to minimize the total number of
accesses to memory. This is called split lifetime [11]. If the split lifetime model is used, the graph
model will need to accommodate all cases where a split occurs. Hence, O(n 2 ) graph edges will be
needed, and the algorithm in [5] has an O(kn 2 complexity, the same as that in [13].
The results we discussed above only apply to variables in a basic block, i.e., a piece of straight-line
code. But real application programs may contain some control structures, such as branches,
merges and loops. A merge is the case where one block has more than one parent blocks. Such
type of control
ows occurs when an instruction has more than one entry point (due to branching,
looping, or subroutine calls). To consider register allocation in a program with these control
structures, one must deal with those variables whose lifetimes extend beyond one basic block. A
straightforward way of applying the existing approaches to such programs would be to enumerate
all possible execution paths and treat each path as a piece of straight line code. Two problems
arise with this approach. First, the number of paths increases exponentially in the worst case
as the number of basic blocks increases. Secondly, each variable may have dierent lifetimes
in dierent paths. Hence such an approach would be computationally costly and be dicult to
obtain an optimal allocation. On the other hand, nding an optimal allocation for all the variables
in a general program has been known to be computational intractable (an NP-hard problem).
2.2 Overview of our approach
In the following, we outline our heuristic approach which can nd superior solutions for the
minimum energy register allocation problem. To avoid the diculties encountered by the known
approaches discussed above, we use an iterative approach to handle programs containing non-
straight-line code. Such program is modeled by a directed graph G in which each node represents
a basic block. Given the nature of a program, the corresponding graph always has a node whose
in-degree is zero. Furthermore, for each loop, the edges that branch backwards can be identied. A
topological order for the nodes in G can thus be established after removing those edges branching
backwards. To ease our explanation, we generalize the concept of parent and child used in trees.
A parent (resp., child) of a block B is a block whose corresponding node in G is an immediate
ancestor (resp., descendent) of the node corresponding to B. Hence, a block may have multiple
parents blocks (in the case of a merge) and it may be a parent block to itself (in the case of a
loop).
We solve the register allocation problem for each basic block in the topological order. The
allocation of variables within a block is based on the results from its parent blocks. Any assignment
of this variable in the current block must consider the eect of its initial assignment. Furthermore,
we do not allow the allocation result in a block to aect the result in its parent blocks. By
allowing the allocation results to propagate \downwards" without back-tracking, we eliminate
the excessive computational cost yet obtain superior allocations. A main challenge is how to
handle those variables whose lifetimes extend beyond a basic block such that the overall energy
consumption of the program is minimized. We have made several observations to help deal with
such variables. The key idea is to set up appropriate boundary conditions between parent and
child basic blocks and use these conditions to guide the register allocation procedure within the
child basic blocks.
We rst describe the graph model used in [13], and then introduce extensions to handle
variables beyond basic blocks. Consider a basic block B in G. A directed graph
which is a generalization of an interval graph, is associated with B. For each data variable
whose lifetime overlaps with the execution duration of B, two nodes, n s (v) and n f (v) are
introduced, which correspond to the starting time t s (v) (when v is rst written) and the nishing
time t f (v) (when v is last read), respectively. Note that v can be either a variable referenced in
B or a variable which will be referenced by B's descendents.
F
a b
c d
e
f
ns(a) ns(b)
ns(c)
ns(d)
nf(a)
nf(d)

Figure

1: The graph G for a basic block without considering other blocks in the program
Several dierent types of arcs are used in G. First, each pair of n s (v) and n f (v) is connected
by an arc a(n s (v); n f (v)). To dene the rest of the arcs, we introduce the concept of critical
set. A critical set, C i , is a set of variables with overlapping lifetimes to one another such that
the number of variables in the set is greater than k, the number of available registers. For each
pair of C i and C i+1 (the index ordering is based on scanning the variables from the beginning to
the end of block B), let D i be the set of variables whose lifetimes are in between the minimum
nishing time of all variables in C i and the maximum starting time of all variables in C i+1 . Note
that D 0 contains the variables whose lifetimes are in between the starting time of B and the
maximum starting time of all variables in C 1 , and that D g is the set of variables whose lifetimes
are in between the minimum nishing time of all variables in C g (the last critical set in B) and
the nishing time of B. Now, an arc is introduced from n f (u) for each u 2 (C i [D i ) to n s (v) for
each Intuitively, these arcs represent allowable register
sharing among subsequent data references.
Similar to [13], a source node, S, and a nish node, F , are introduced at the beginning and
end of B, respectively. Arcs are used to connect S to n s (v) for each v 2 (D 0 [C 1 ) and to connect
for each u 2 (C g [D g ) to F . The nodes S and F can be considered as the registers available
at the beginning and end of block B. An example graph is shown in Figure 1, where the solid lines
correspond to the arcs associated with variables in B and the dash lines are the arcs introduced
based on C i 's and D i 's. In this graph, variable b, c and d form the rst critical set, C 1 , while
variable a and b form the set D 0 .
To handle the allocation beyond a block boundary, the graph needs to be modied. Substantial
modications to the existing approaches as well as new ideas are proposed here in order to
eciently handle the branch, merge, and loop structures.
Bc

Figure

2: Four dierent allocation results for a cross-boundary variable
3 Register Allocation for the Branch Structure
In this section, we discuss in detail our algorithms of register allocation for the branch structure
for the two dierent energy models.
3.1 Beyond boundary allocation for the static energy model
We rst consider the case in which only single read is allowed, and then extend the result to the
multiple read case.
For a variable, v, if it is dened in a block B 0 and is also read in another block B, the lifetime
of v crosses the boundary of the two blocks. The block B 0 is the parent block, B p , of the block B.
We say v is in both B p and B. When our algorithm computes the allocation for B p , it performs
the computation as if v did not cross the boundary. When we come to the block B, we will make
the best allocation decision for v in B based on the allocation result of v in B p .
There are totally four dierent combinations of allocation results for v in the two consecutive
blocks: (1) v in register in both B p and B (R!R), (2) v in register in B p but in memory in B
(R!M), (3) v in memory in B p but in register in B (M!R), and (4) v in memory both in B p and
B (M!M), as shown in Figure 2. In Figure 2, solid line segments mean the variable is in register,
while dashed segments mean the variable is in memory. (We will use this convention throughout
the paper unless stated otherwise explicitly.)
We will analyze the energy consumption for all the four cases, R!R, R!M, M!R, and
M!M. For the R!R case, the energy consumed by v in block B p is e R w when it is dened, in
block B is e R r when it is read from the same register, and totally the energy consumed by v in the
two consecutive blocks,
r . By applying the same analysis to other three cases,
we obtain the amount of energy consumed by a crossing-boundary variable in dierent blocks, as
shown in the column R!R, R!M, M!R, and M!M in Table 1.
For a local variable of B, which is written and read only in block B, the energy consumed by

Table

1: Energy consumption in dierent blocks under dierent allocation results
Block R! R R! M M! R M! M Local R Local
w e R
r e R
r e R
r
r e R
r e R
r
it in B is e R
r or e M
r if it is assigned to a register (Local R) or a memory (Local M)
location. It consumes no energy in B p since it does not exist in B p . The energy consumed by a
local variable in B is shown in the last two columns (Local R and Local M) in Table 1.
From

Table

1, it is easy to see that, based on the allocation result for B p , the best choice for
a global variable in B should be:
is in memory in B p , it should stay in memory in B to achieve the lowest energy.
Comparing the two columns corresponding to the situation when v is in memory in B p ,
M!R and M!M, it is clear that if v is in memory in B p , assigned it to a register will cost
more energy than assign it to memory in B.
R!Local : If v is in register in B p , it should be treated as a brand new local variable in block
B to achieve the optimal energy. The energy data for block B and B in the columns
for R!R and Local R is same, while the data diers only by e R
r in the columns for
R!M and Local M in which the total amount of energy is much larger than the dierence.
So a simple way is to just treat this kind of global variable as a brand new local variable
whose allocation is to be determined in block B. If it turns out to be assigned to register
in B too, it should stay in the same register as it uses in B p .
Treating v, which extends beyond boundary and is assigned to a register in B p , as a brand
new variable in B is clearly an approximation. Another way is to assign the actual energy
saving, the energy saved by assigning a variable to register comparing with assigning it to
memory, as the weight of the variable and construct a network
ow and then use minimum-cost
network
ow algorithms to solve the problem as described in [5] for the weighted case.
A variable, v, can also be dened in B, not read in the child of B, but read in the grandchild
or even grand-grandchild of B. The analysis for this kind of variable is as same as the above
analysis for the variable that dened in B p and used in B, and same conclusion is drawn for the
allocation in the children blocks of B.
With these rules, we can execute the local register allocation algorithm on each of the blocks
in a program. For the simple case, the time complexity of the allocation for the whole program
is O(bnlog n), where n is the largest number of local variables in a basic block. For the more
complex case, the time complexity is O(bknlog n). The algorithm is shown in Algorithm 1.
As we discussed earlier in Section 2, a variable in a program may be read more than once
after it is written. In this case, we can use the same graph model as in [5] but modify the weights
Algorithm 1 Algorithm for low energy register allocation in static energy model
Input: A scheduled program with blocks, P g.
Output: The register assignment for every variable v in program P .
Denitions:
allocation result for variable v in block B i . B i (v) is 1 if v is in register, 0 if v is in
memory.
weight(v): the weight of variable v.
apply algorithm for the unweighted case in [5] to B 1
to m do
if using the simple way for approximation then
for all variables, v, live in B i p and B i do
else
v is treated the same as other local variables
end for
apply algorithm for the unweighted case in [5] to B i
else
for all variables, v, live in B i p and B i and is read in B i do
else
r
end for
for all variables, v, live in B i p and B i but not read in B i do
else
end for
for all variables written and read in B i do
end for
for all variables written but not read in B i do
w e R
end for
apply algorithm for the weighted case in [5] to B i
end for

Table

2: Weight for global variables and local variables in B
Block Global v in Register in B p Global v in Memory in B p Local
associated with certain graph edges. Specically, we assign the energy saving by assigning a
variable to a register as the weight for this variable. For the current block, B, the weight of a
variable dened in B is h v e M
r +e R
is the total number of read accesses to
v as dened in Section 2. If a variable is live in the parent block, B p , and is assigned to a register
in B p , the weight is for it in the current block B is h v e M
r ). Otherwise, if it
is allocated to memory in B p , the weight is h v e M
r ). Note that the weight is
the energy saving when v is allocated to a register in the current block B. Since the total energy
of accessing all the variabls from memory is xed for a basic block, the more energy saved by
allocating variables to registers, the less the energy the block consumes. The weight assignment
is summaried in Table 2.
By applying the network
ow approach in [5] for weighted intervals on each basic block one
after another, we can get a low energy allocation solution for the whole program in O(bknlog n)
time.
If splitting is allowed, the graph model in [5], which only allows the register transfered from
longer sucient. In this case, we can use the graph model (to
be described in the next section) and the network
ow approach presented in [13]. That is, we
assign weights as described in Table 2 and use a minimum-cost network
ow algorithm to solve
the problem in O(bkn 2 ) time.
3.2 Register allocation for branches for the activity-based energy model
To handle the allocation beyond a block boundary, our approach is to decide the register allocation
for block B based on the allocation result from B's parent block, B p . Depending on which variable
is assigned to which register prior to entering B, the amount of energy consumption by each
variable in B can be dierent. Therefore, simply using a single source S to represent the registers
available at the beginning of B is no longer sucient. We generalize the construction of graph G
for B, where B has both a parent and at least one child, as follows. (The graphs for the root and
leave blocks in T are simply special cases of the graph we discuss.)
For those variables that are referenced only in B, we introduce arcs and nodes associated with
them in the same way as we discussed above. The start and nish nodes, S and F , for B are
also maintained. Let the starting and nishing times of block B be t s (B) and t f (B), respectively.
For each variable v in B whose starting (resp. nishing) time is earlier (resp. later) than the
starting use two end
nodes n s (v) and n f (v) in G for the associated arc a(v) (which means that v is considered by all
e
f
c
np(a)
ns(c)
nf(c)
F

Figure

3: The graph G for block B based on the allocation of its parent block B p .
the graphs corresponding to the blocks with which the lifetime of v overlaps). The arcs between
these nodes and S or F are dened in the same ways as discussed in the previous paragraphs.
Furthermore, we introduce a register set, VRB , which contains the variables residing in registers
at the completion of the allocation process for block B. Note that VRB becomes uniquely dened
after the allocation process of B is completed, and that the size of VRB , jV RB j, is always less than
or equal to k, the number of available registers. We expand G by adding a node n p (v) for each
is the parent block of B. It is not dicult to see that the variables in VRBp
are the only variables which have a chance to pass on their register locations to variables in B
directly. Now, we insert an arc from each n p (u) to n s (v) for each v 2 (D
are as dened in the previous paragraphs). Comparing our generalized graph with
the original graph, one can see that at most k additional nodes and k  jD additional arcs
are used in the generalized graph. Figure 3 shows an example graph G for the current block B
assuming that there are three available registers.
Sometimes, a program may read a variable, v, more than once, In this case, we introduce an
additional node n r i (v) for each read of v except the last read. Additional arcs are also introduced
to model possible register sharing between variables. Due to the page limit, we omit the discussion
on this part.
Given the directed graph G for B, we are ready to construct the network
ow problem associated
with G. Let x(n f (u); n s (v)) and c(n f (u); n s (v)) be the amount of
ow and the cost of one
unit of
ow on arc a(n f (u); n s (v)), respectively. Denote the total amount of energy consumed by
B as E. The objective function of our network
ow problem can be written as:
v2Bjts (v)<ts (B)
a(p;q)2A
where A is the set of arcs in G. In (3), the rst three terms are the amount of energy consumed
by B if all the variables are assigned to memory, and the last term represents the energy saved by
allocating certain variables to registers. The values of x(p; q) are unknown and to be determined.
If corresponds to a variable v, then v will be assigned to a register. The
values of c(p; q) are dependent on the types of arcs associated with them, and can be categorized
into the following cases.
1) For an arc from a node of type n f to another node of type n s , i.e. a(n f (u); n s (v)), the cost
associated to the arc, c(n f (u); n s (v)), is computed by
r H(u; v)C R
where N is the set of nodes in G. This is the amount of energy saved by reading u from a register
and writing v to the same register.
For an arc from a node of type n p to another node of type n s , i.e. a(n p (u); n s (v)), the cost
associated to the arc, c(n p (u); n s (v)), is dened dierently. There are a total of 7 cases to be
considered.
2.1) If u is not in B(i.e., u's lifetime does not overlap with that of B), and v is written in B, the
cost c(n p (u); n s (v)) is computed by
2.2) If u is not in B, and v has been assigned to a register during the allocation process of B p ,
If u is not in B, and v has been assigned to memory during the allocation process of B p ,
r H(u; v)C R
If u is in B, and v is written in B, the cost c(n p (u); n s (v)) is the same as dened in (6) for
Case 2.2.
2.5) If u is in B, and v has been assigned to a register during the allocation process of B p ,
If u is in B, and v has been assigned to memory during the allocation process of B p ,
r H(u; v)C R
2.7) If u and v represent the same variable, the cost c(n p (u); n s (v)) is simply assigned to zero.
For an arc from start node S to another node of type n s , i.e.
need to have three dierent cost functions.
3.1) If v is written in B,
where H(0; v) is the average Hamming distance between 0 and a variable v, and is normally
assumed to be 0.5.
If v has been assigned to a register during the allocation process of B p ,
If v has been assigned to memory during the allocation process of B p ,
For an arc from a node of type n f to the nish node, F , i.e. a(n f (v); F ) for v 2 D g [ C g , we
need to have two dierent cost functions.
If v is read in B,
c(n f (v); F
r
4.2) If v is not read in B, the cost c(n f (v); F ) is simply assigned to zero.
5) For an arc from a node of type n s to another node of type n f , which is the arc corresponding
to the same variable, the cost associated to the arc is assigned to zero.
Using the above equations, the objective function for the network
ow problem will be uniquely
dened. The constraints for the network
ow problem is dened based on the number of registers
available to the arc. They are summarized as following:
Applying a network
ow algorithm such as the one in [21] to our network
ow problem instance,
we can obtain the value of each x(p; q) in O(kn 2 ) time for the block B, where k is the number of
available registers and n is the number of variables whose lifetimes overlap with the lifetime of B.
If the resulted x value of the arc associated with a variable in B is one, the variable is assigned
to the appropriate register based on the
ow information. The above formulation can then be
applied to each basic block in the program tree in the depth-rst search order as we discussed at
the beginning of this section.
Here we should point out that our method can also be used if one wishes to explore program
execution paths to determine the register allocation. For example, we can associate each execution
path of a program with a priority. One way to assign priorities is based on the execution frequency
of each path (obtained from proling). Another way is based on the timing requirements. To solve
the register allocation problem, one can start with the highest priority path, P 1 , and proceed to
the lower priority ones sequentially. For the rst path, form a super block for the path and use the
local register allocation algorithm in [13] to nd the best allocation for this single path. For the
next path, remove the basic blocks on this path whose register assignments have been determined.
Then form a super block B 0 for the rest of the basic blocks in this path. To construct the graph
for this super block B 0 , we need to consider all those B p 's that have a child in B 0 and introduce
the necessary n p nodes to complete the graph. The network
ow problem for the super block B 0
can use the same formulations as we discussed above. The process is repeated for all subsequent
paths. By applying our algorithm, the variable allocation decisions made for the higher priority
paths will not be changed by the allocation processes of the lower priority paths. Rather, the
results from the higher priority paths are used to insure that good allocations are found for the
lower priority paths based on these results. Hence, we have eectively eliminated the con
icting
assignments that can arise when solving the allocation problem for each path separately.
4 Register Allocation for Blocks with Merging Parent Blocks
In this section we present our approach to handle the merge case. The fact that the allocation
results from dierent parent blocks may be dierent makes the merge case more dicult to handle
than the branch case. If a variable, v, is alive in B but is not dened (written) in B, v must
be alive when leaving every B's parents. Since the allocation results for v in dierent parent
blocks may be dierent, we cannot simply do the allocation for v in B based on the allocation
result from one particular parent block. Hence our register allocation approach for programs with
branches, where each basic block has only one parent block, is not adequate for a block when more
than one blocks merging into it. To handle the control structure of merge blocks, we devise a
method to capture the non-unique assignments of variables to registers. Based on this approach,
we formulate the problem of register allocation for both the static energy model and the activity
based energy model as an instance of the network
ow problem.
Let the parent blocks of B be B assuming m is the total number of blocks
merge into B and m > 1. Each parent block, B p i is associated with a probability, P (B
indicating how frequently the block is executed. (Such probabilities can be obtained from proling
information.) After the allocation for a parent block is nished, the allocation decision for a
variable in B p i which goes beyond the boundary of B p i and B is xed. We dene the probability of
v allocated to a register (resp., memory) in B p i as P (v; R; B
let P (v; R be the probability of v being assigned to the register R j in block B p i . We also
dene P (v; R;
as the total probability of v allocated to a
register (resp., memory) in all the parent blocks, P (v; R
as the total probability of v
allocated to the register R j in all the parent blocks. The following relations hold for the variables
dened above, where k is the total number of registers.
We modify the
ow graph to be used in the merge case as follows. The source node, S, and the
nish node, F , are kept as the same. The nodes used to represent a variable, v, are still the same
as n s (v) for the starting node, and n f (v) for the nishing node. Because the register assignments
in dierent parent blocks may be dierent, a cross boundary variable may have dierent allocation
assignment in dierent parent blocks. To re
ect this fact, a critical set, C i , is dened as a set of
variables with overlapping lifetimes to one another such that the number of variables written in
B in the set is greater than the number k of available registers. Furthermore, we introduce a new
set of register nodes, n r (i), which correspond to the registers. In addition to all
the arcs dened in Section 2, we add new arcs from source node, S, to each register node, n r (i).
A complete bipartite graph is formed between the register nodes and the starting nodes for all
variables in the rst critical set C 1 or D 0 . An example
ow graph for a block B with multiple
parent blocks is shown in Figure 4, assuming that there are two registers, R 1 and R 2 , available
in the system.
In minimizing energy consumption by a single block with multiple blocks merging into it,
one should minimize the overall energy consumption under all execution scenarios for this block.
Thus, the objective function for the
ow problem needs to take into account the probabilities of
executing dierent parent blocks. For dierent energy models, static energy model and activity
based energy model, the objective function and the cost associated with arcs are slightly dierent.
To reduce repetition, we will integrate the presentation of the formulations for both models and
point out the dierences wherever necessary. The objective function can be written as:
F
a
b c d
e
f
ns(a)
nf(a)
ns(c) ns(d)
nf(c)
nf(d)

Figure

4: The graph G for a basic block with more than one parent blocks
v2Bjts (v)<ts (B)
a(p;q)2A
where
1 if static energy model
The rst three terms of computing the objective function (19) are the amount of energy
consumed by block B if all the variables are assigned to memory, while the last term represents
the energy saved by allocating certain variables to registers. The dierence in the  value is due
to the fact that in the activity based energy model, the energy consumption of register references
is computed by the switched capacitance between two consecutive accesses and is captured by the
cost, c(p; q), associated with corresponding arcs in the last term of (19). The values of x(p; q) are
unknown and to be determined. If x(p; corresponds to a variable v, then v
will be assigned to a register. The values of c(p; q) are dependent on the types of arcs associated
with them, and can be categorized into the following cases.
1) For an arc from a node of type n f to another node of type n s , i.e., a(n f (u); n s (v)), the cost
associated to the arc, c(n f (u); n s (v)), is computed dierently for two dierent kinds of energy
model. For the static energy model,
r
while for the activity based energy model,
r H(u; v)C R
where N is the set of nodes in G. This is the amount of energy saved by reading u from a register
and writing v to the same register.
For an arc from a node of type n r (i) to another node of type n s , i.e., a(n r (i); n s (v)), the cost
associated to the arc, c(n r (i); n s (v)), can take one of the following values.
2.1) If v is written in B, for the static energy model,
c(n r (i); n s
w e R
while for the activity based energy model,
c(n r (i); n s
For the static energy model, the energy saving is the energy of a memory write, e M
the energy of a register write, e R
w . On the other hand, for the activity based energy model,
the energy for writing v into a register is determined by the hamming distance between v and
the variable u that occupied R i at the entry of block B. Since the probability for variable
u occupying R i is P (u; R hamming distance would be the summation of
the hamming distance between v and all the u which has non-zero probability of occupying
R i in one of the parent blocks. The energy of writing variables in R i back to memory when
R i is assigned to v is already included in the objective function in the second item.
2.2) If v is not written in B, for the static energy model,
c(n r (i); n s
where the rst term is the energy consumption if v is assigned to a memory location, the
second is the energy of assigning v to R i in B if v is in memory in B 0 s parent blocks, and
the last term is the energy of assigning v to R i in B if v is already in a register other than
R i in B's parent blocks.
For the activity based energy model,
c(n r (i); n s
r
where the last term is the energy consumed by assigning v to R i which is determined by
the hamming distance of v and the variables that occupies R i in any of B's parent blocks .
For an arc from source node S to the node of type n r (i), i.e., a(S; n r (i)), the cost function
simply zero.
For an arc from a node of type n f to the nish node, F , i.e., a(n f (v); F ) for v 2 D g [ C g , we
need to have two dierent cost functions.
If v is read in B, for static energy model,
c(n f (v); F
r e R
while for the activity based energy model,
c(n f (v); F
r (27)
4.2) If v is not read in B, the cost c(n f (v); F ) is simply assigned to zero in both the static and
activity based energy model.
5) For an arc from a node of type n s to another node of type n f , which is the arc corresponding
to the same variable, the cost associated to the arc is assigned to zero.
Using the above c(p; q) denitions, the objective function for the network
ow problem is
uniquely dened. The constraints for the network
ow problem are dened based on the number
of registers available to dierent types of arcs. They are summarized in the following:
Applying a network
ow algorithm [21] to our network
ow problem instance, the value of
each x(p; q) can be obtained in O(kn 2 ) time for the block B, where k is the number of available
registers and n is the number of variables whose lifetimes overlap with the lifetime of B. If
the resulted x value of the arc associated with a variable is one, the variable is assigned to the
appropriate register based on the
ow information. The above formulation can then be applied
to each basic block in the program control
ow graph in the topological order.
5 Register Allocation for Loop
In this section, we extend our approach to handle programs with loops. A loop can be considered
as a control structure with more than one parent blocks merging into it. However, it presents
some unique challenges since one of its parent blocks is itself.
One way to solve the allocation problem for loops is to modify the
ow problem formulation
presented in the last section. Consider a loop with one basic block as shown in Figure 5, where
the dash lines represent those variables that are referenced in more than one iteration of the
loop execution. We refer to these variables as loop variables and the rest as non-loop variables.
The graph for modeling the allocation problem of a loop block can be built following the same
guidelines used for the merge case. The graph for the loop block in Figure 5 is shown in Figure 6.
(Note that the existence of loop variables does not change the graph since only register nodes
are needed to model parent block assignments.) Similar to the merge case, we associate certain
probabilities to the variables at the boundary of the loop block and its parent blocks to capture
potentially dierent assignments dictated by dierent parent blocks. For the example in Figure 5,
assuming that the loop has one parent block
corresponds to the
loop itself. It may seem that one can now simply use the
ow problem formulation for the merge
case to nd the allocation for a loop. However, the diculty is that the probabilities associated
with each loop variable (e.g., P are dependent on the allocation result of the loop
block which is yet to be determined.
a f
f
c
d
e
e
in-assignment
pre-assignment
post-assignment
loop variable
loop variable

Figure

5: A loop with one basic block, where e and f are loop variables, and a, b, c and d are
non-loop variables.
The optimization problem can still be solved but it is no longer a simple
ow problem. In
general, assume that B p l is the loop body itself and that the probability of this block loops back to
itself is P (B p l ). (P (B p l ) can be obtained from proling information.) The probability associated
with a loop variable v can be expressed as follows. If v is assigned to register R i upon exiting the
loop, i.e., x(n f (v); F
is assigned to memory upon exiting the loop, i.e., x(n f (v); F
then Consequently, the following expression can be
derived:
It follows that the
ow problem in (19) can be transformed to an integer quadratic programming
Loop Block
e
F
a
f
f
c
d
e
ns(c)
ns(d)
nf(a)
nf(c)
nf(d)

Figure

Flow graph for the loop in Figure 5.
problem. Integer quadratic programming problems are generally NP-hard and may be solved by
the branch-and-bound method [26].
We propose an ecient heuristic approach, which generally produces superior allocation re-
sults. Recall that our register allocation algorithm determines the variable allocation of a block
based on the allocation results of its parent blocks. Consider a loop variable, it may have some
initial assignments dictated by the allocation of its parent blocks (other than the loop block it-
self), another assignment before its rst reference in the loop block, and yet another assignment
upon leaving the block. To ease our explanation, we refer to these assignments as pre-assignment,
in-assignment, and post-assignment, respectively. In Figure 7(a), we show a possible assignment
result for the block in Figure 5, where for variable e, its pre-assignment is a register, its
in-assignment is memory, and its post-assignment is a register. The basis for our approach is
the following observations. In general, a loop body is executed frequently, i.e., P (B p l ) is relatively
close to one. If a loop variable's pre-assignment is dierent from its in-assignment, only
a single switching from memory to register or vise versa is required. However, if a loop vari-
able's in-assignment is dierent from its post-assignment, as many switchings as the number of
loop iterations would be needed. Hence, reducing the number of loop variables with dierent
in-assignment and post-assignment would tend to result in better allocations.
Our algorithm employs an iterative approach. With the rst allocation attempt, we ignore
the fact that the loop body is one of its parents and compute the allocation by simply using the
results from the other parent blocks. That is, the value of P (v; R; B in the
ow formulation in (19) are assumed to be zero if B p i is the loop body itself and v is a loop
variable. We refer to as the initialization phase ( 0 ).
The algorithm proceeds as follows. If there is no loop variable whose in-assignment is dierent
from its post-assignment, the optimal allocation is found and the algorithm exits. Otherwise,
we perform two more allocation phases: the second phase ( 1 ) and the third phase ( 2 ). In the
second phase, we let the in-assignment of each loop variable to be the value obtained from  0
and solve the resultant allocation problem. Since the values of P (v;
are unknown if v is a loop variable, it may seem that we still need to solve an integer quadratic
programming problem. However, applying some simple manipulations, we can avoid this diculty.
In particular, we modify the value of cost c(n f (v); F ) for each loop variable v. Instead of always
setting it to zero as in the merge case, it is dened according to the in-assignment of the same
loop variable as follows:
c(n f (v); F
in-assignment is register
e M e R otherwise
The value of P (v; R; B p l ) and P (v; M;B p l ) for each loop variable v are still assumed to be
zero. The modied
ow problem correctly captures the overall energy consumption when the
in-assignment of each loop variable is set to that obtained from  0 . The solution to the modied
ow problem leads to an improved allocation result.
In the third phase ( 2 ), we x the post-assignment of each loop variable to the value obtained
in  0 . Then, P (v; R; B p l ) and P (v; M;B p l ) can be computed by
post-assignment is register R
if v's post-assignment is memory:
By substituting in (19) the above probability values, we again reduce the allocation problem to
a min-cost
ow problem. Solving this
ow problem will result in an allocation that improves the
result obtained from  0 . The better one from  1 and  2 is kept as the best allocation result found
so far. Further improvement could be obtained if more iterations were carried out by treating the
current best allocation as the one obtained from  0 and following the same procedure as used in
In the following, we show that the optimal allocation for a loop block is obtained if our
algorithm exits after the initialization phase  0 . Furthermore, we show that if the second and
third phase are needed, their results always improve that from  0 .
be the energy consumption by loop block B p l and E 0 be the energy consumption
by l assuming that the loop variables do not loop back. Then, minE  minE 0 .
can be computed by setting in (19) P (v; R
to zero for each loop variable v. Then, E can be expressed as
r l )(e R
l ))(e R
where VL is the set of loop variables. It is not dicult to verify that E  E 0 for any combination
of x(n(R i values. Hence, minE  minE 0 . 2
Based on Lemma 1, we can prove the following theorem.
Theorem 1 If the allocation result from the initialization phase ( 0 ) makes the in-assignment of
each loop variable to be the same as its post-assignment, then
Proof: Consider a loop variable v in B p l . If its in-assignment and post-assignment are both
memory, we have x(n(R i contribution to E in
(31) reduces to zero. Similarly, if v's in-assignment and post-assignment are both register R i , we
have
v's contribution to E in (31) becomes zero. When more than one loop variable exists, the same
conclusion can be obtained. Therefore, if the in-assignment of each loop variable is the same as
its post-assignment, we have Ej  0
is the total energy consumption of B p l using
the same allocation as that obtained from  0 . Since minE  minE 0 by Lemma 1, we obtain
According to Theorem 1, if the in-assignment of each loop variable is the same as its post-
assignment, the allocation result from  0 is the optimal one for the loop block, and no more
allocation phases are needed.
When the in-assignment of some loop variable diers from its post-assignment, the result
from  0 is no longer optimal. The reason is that the problem formulation used in  0 fails to
account for the extra energy incurred by the loop variable switching its assignment at the loop
boundary. Our second and third phases aim at reducing such energy. In the second phase  1 , the
in-assignment of each loop variable is assumed to be the same as that obtained from  0 , and the
best allocation based on this assumption is identied. Let Ej  0
be the energy consumption of B p l
when the allocation result from  0 is used, and Ej  1
be the energy consumption of B p l when only
the in-assignments of loop variables obtained from  0 are used. After  1 , we obtain an allocation
result having minfEj  1
g as the energy consumption. Note that Ej  0
is simply one of the possible
values of Ej  1
. Hence, minfEj  1
. That is,  1 always improves the result from  0 . In
the third phase  2 , we x the post-assignments of loop variables to the values obtained from  0
and nd the corresponding best allocation. Similar to the statement made for  1 , the allocation
result from  2 also improves that of  0 .
If more allocation phases are carried out based on the better allocation from  1 and  2 , further
improvement may be obtained. Our approach is essentially a hill-climbing technique and could
settle to a suboptimal solution. However, observe that our incremental improvement is based on
the optimal allocation for the loop body itself and that there are usually only a small subset of
the variables in a loop are loop variables. Therefore, our approach tends to have a good chance
to obtain the optimal allocation. Our experimental results also support this observation.
We use the example in Figure 5 to illustrate how our algorithm works for a single-block loop.

Figure

7(a) depicts the allocation result after the initialization phase. Since the in-assignment and
post-assignment for loop variables e and f are dierent, the second and third phase are needed.
In the second phase, cost c(n f;2 (e); F ) of the
ow graph in Figure 6 is set to e M
w e R
r as the
in-assignment of e is memory, while cost c(n f;2 (f); F ) is set to zero as the in-assignment of f is
register. The allocation result after the second phase is shown in Figure 7(b). In the third phase,
we let P since the post-assignment of e
is register R 1 , and P (f; R; B p l since the post-assignment of f is memory.
The allocation result after the third phase is the same as that after  1 . Since the in-assignment
of e (resp., f) is the same as its post-assignment in the allocation result, our process stops. It is
obvious that the allocation result is optimal for this block.
Our algorithm can be readily extended to handle the case when there are more than one block
inside a loop body, i.e., the control structure inside a loop body contains branches and loops. For
branches and merges, each phase in our algorithm needs to solve the allocation problem for each
block in the loop body following the process discussed in Section 3 and 4. In  1 (resp.,  2 ), the
in-assignments (resp., post-assignments) of loop variables obtained from  0 are used to compute
the necessary cost or probability values. For loops inside a loop, the sequence of the allocation
is determined by the nested levels of loops. Since inner loops are executed more frequently than
outer loops, the inner-most loop is allocated rst and the result is used by the outer loops.
(a) (b)
e
a
e
c
d
f
f
e
a
e c
d
f
f

Figure

7: The allocation results of dierent allocation phases for a loop. The solid lines correspond
to variables in registers, while the dash lines correspond to variables in memory.
6 Experimental Results and Discussions
Graph-coloring based techniques such as the ones in [6] are most often used for solving the
register allocation problem. We compare our algorithm with a graph-coloring approach. We have
implemented a graph-coloring register allocator and our block-by-block register allocator in the
Tiger compiler presented in [1]. The modularity of the Tiger compiler makes it easy to x other
phases of the compiler, while only alternate the register allocation algorithms. The procedures for
nding the basic blocks, building the trace, and computing the lifetime of each variable are kept
the same in both allocators. In the implementation of the graph-coloring allocator, an interference
graph is built for each program. In applying the graph-coloring approach to color the graph, if
there is no node with degree less than the number of available registers in the graph, the node with
the highest degree will be spilled until all the nodes are colored or spilled. In the implementation
of our algorithm, a network
ow graph is built for each block. Then our algorithm for dierent
control structures is applied to each basic block in the topological order to nd the best allocation.
We compare the allocation results of the two dierent approaches for several real programs
containing complex control structures. The numbers of memory references by the two allocators
are summarized in Table 3. The improvement in the energy consumption and the number of
memory references by using our algorithm over the graph-coloring approach is summarized in

Table

4. According to data in [3, 17, 12], it is reasonable to assume that the ratio of the average
energy for memory reference over the average energy for register reference, e M =e R , is in the range
of 10 to 30. In Table 5, we summarize the sizes of allocation problems that the two approaches need
to solve. As stated at the beginning of the paper, the complexity of our algorithm is O(b l(n; k)),
where b is the total number of blocks and l(n; k) is the time complexity for solving the register
allocation problem for a single block that has n variables and k available registers. The function
l(n; is either O(nlog n) for the single-read static-energy model, O(knlog n) for the multiple-read
static-energy model, or O(kn 2 ) for the activity based energy model [5, 13].

Table

3: The number of memory references allocated by two approaches.
# of # of Our approach Graph-coloring
Example k register data # of spilled # of memory # of spilled # of memory
Programs candidates references candidates references candidates references
branch 14 28 67

Table

4: The improvement of results by our algorithm over graph-coloring
Energy improvement (%) Improvement of # of
Programs e M =e
factorial 72.8 80.7 89.6 29.8
branch 68.2 77.0 87.4 23.9

Table

5: The size of problems solved by two approaches.
Interference graph Network
ow
Benchmarks # of nodes # of edges # of blocks b max #of variables n
branch 28 293 4 26
The experiment results show that our algorithm can achieve more than 60% improvement
in the energy consumption due to data references of a program over a graph-coloring approach.
At the same time we also saved more than 20% of the memory references which will save the
execution time due to data references of a program. Furthermore, our approach is simple to use
and the running time is polynomial.
There are some other improved graph-coloring based algorithms, such as the one in [11].
The register allocation results by those improved algorithms are better than the simple graph-coloring
approach implemented here. But again, those algorithms are all proposed to optimize
the execution time, not the energy consumption, of a program.
Our algorithm proposed in this paper does not take into account any look ahead information
while doing register allocation. It also does not allow any backtracking. In some cases, our
approach may produce suboptimal allocation results. One simple extension of the algorithm
would be to change the cost c(n f (v); F ) associated with the arc a(n f (v); F ) for a cross boundary
variable v according to the possible allocation results of v in child blocks.
In this paper, we proposed a new algorithm to deal with those variables whose lifetimes
extend beyond basic blocks for low energy register allocation. Our algorithm has much less time
and space complexity than other approaches in doing register allocation for variables extending
beyond basic blocks. The experimental results by using our algorithm so far are very promising.
More experiments with larger code sizes are being conducted. We are also investigating on how
to deal with procedure calls.

Acknowledgment

This research was supported in part by the National Science Foundation under Grant CCR-
9623585 and MIP-9701416, and by an External Research Program Grant from Hewlett-Packard
Laboratories, Bristol, England.



--R

Modern Compiler Implementation in C








Digital Circuits with Microprocessor Applications






Computer Architecture: A Quantitative Approach



Networks and Matroids


Integer and






--TR
Combinatorial optimization: algorithms and complexity
On the Minimization of Loads/Stores in Local Register Allocation
The priority-based coloring approach to register allocation
Register allocation via hierarchical graph coloring
A global, dynamic register allocation and binding for a data path synthesis system
Allocation algorithms based on path analysis
On the <italic>k</italic>-coloring of intervals
Register allocation and binding for low power
Power minimization in IC design
Demand-driven register allocation
Low energy memory and register allocation using network flow
Optimal and near-optimal global register allocations using 0MYAMPERSANDndash;1 integer programming
The design and implementation of RAP
Computer architecture (2nd ed.)
Global register allocation for minimizing energy consumption
Modern Compiler Implementation in C
Digital Circuits with Microprocessor Applications
Global Register Allocation Based on Graph Fusion
Register allocation MYAMPERSANDamp; spilling via graph coloring
low energy;register allocation