The basics of programming embedded processors: Part 5
Two important aspects of the code compilation phase in embedded
program development are register allocation and schedule.
Given a block of code, we want to choose assignments of variables (both declared and temporary) to registers to minimize the total number of required registers. Example 5-5 illustrates the importance of proper register allocation.
Example 5-5 Register
To keep the example small, we assume that we can use only four of the ARM's registers. In fact, such a restriction is not unthinkable - programming conventions can reserve certain registers for special purposes and significantly reduce the number of general-purpose registers available.
Consider the following C code:
w = a + b; /* statement 1 */
x = c + w; /* statement 2 */
y = c + d; /* statement 3 */
A naive register allocation, assigning each variable to a separate register, would require seven registers for the seven variables in the above code. However, we can do much better by reusing a register once the value stored in the register is no longer needed.
To understand how to do this, we can draw a lifetime graph that shows the statements on which each statement is used. Appearing below is a lifetime graph in which the x axis is the statement number in the C code and the y axis shows the variables.
A horizontal line stretches from the first statement
where the variable is used to the last use of the variable; a variable
is said to be live during this interval. At each statement, we can
determine every variable currently in use. The maximum number of
variables in use at any statement determines the maximum number of
In this case, statement two requires three registers: c, w, and x. This fits within the four registers limitation. By reusing registers once their current values are no longer needed, we can write code that requires no more than four registers. Appearing below is one register assignment.
The ARM assembly code that uses the above register assignment follows:
If a section of code requires more registers than are
available, we must spill
some of the values out to
memory temporarily. After computing some values, we write the values to
temporary memory locations, reuse those registers in other
computations, and then reread the old values from the temporary
locations to resume work.
Spilling registers is problematic in several respects. For example, it requires extra CPU time and uses up both instruction and data memory. Putting effort into register allocation to avoid unnecessary register spills is worth your time.
We can solve register allocation problems by building
a conflict graph and solving a graph coloring
problem. As shown in Figure 5-19
below, each variable in the high-level
language code is represented by a node. An edge is added between two
nodes if they are both live at the same time.
The graph coloring problem is to use the smallest number of distinct colors to color all the nodes such that no two nodes are directly connected by an edge of the same color. The figure shows a satisfying coloring that uses three colors. Graph coloring is NP-complete, but there are efficient heuristic algorithms that can give good results on typical register allocation problems.
|Figure 5-19. Using graph coloring to solve the problem of Example 5-5.|
Lifetime analysis assumes that we have already determined the order in which we will evaluate operations. In many cases, we have freedom in the order in which we do things. Consider the following expression:
(a + b) * (c - d)
We have to do the multiplication last, but we can do
either the addition or the subtraction first. Different orders of
loads, stores, and arithmetic operations may also result in different
execution times on pipelined machines.
If we can keep values in registers without having to reread them from main memory, we can save execution time and reduce code size as well. Example 5-6 illustrates how proper operator scheduling can improve register allocation.
Example 5-6.Operator Scheduling
for Register Allocation
Here is sample C code fragment:
w = a + b; /* statement 1 */
x = c + d; /* statement 2 */
y = x + e; /* statement 3 */
z = a ' b; /* statement 4 */
If we compile the statements in the order in which they were written, we get the register graph below.
Since w is needed until the last statement, we need five registers at statement 3, even though only three registers are needed for the statement at line 3. If we swap statements 3 and 4 (renumbering them)we reduce our requirements to three registers. The modified C code follows:w = a + b; /* statement 1 */
w = a - b; /* statement 2' */
w = c + d; /* statement 3' */
w = x + e; /* statement 4' */
The lifetime graph for the new code appears below.
Compare the ARM assembly code for the two code fragments. We have written both assuming that we have only four free registers. In the before version, we do not have to write out any values, but we must read a and b twice. The after version allows us to retain all values in registers as long as we need them.
Before version After version
LDR r0,a LDR r0,a
LDR r1,b LDR r1,b
ADD r2,r0,r1 ADD r2,r1,r0
STR r2,w ; w = a + b STR r2,w ; w = a + b
LDRr r0,c SUB r2,r0,r1
LDR r1,d STR r2,z ; z = a ' b
ADD r2,r0,r1 LDR r0,c
STR r2,x ; x = c + d LDR r1,d
LDR r1,e ADD r2,r1,r0
ADD r0,r1,r2 STR r2,x ; x = c + d
STR r0,y ; y = x + e LDR r1,e
LDR r0,a ; reload a ADD r0,r1,r2
LDR r1,b ; reload b STR r0,y ; y = x + e
STR r2,z ; z = a " b
We have some freedom to choose the order in which operations will be performed. We can use this to our advantage—for example, we may be able to improve the register allocation by changing the order in which operations are performed, thereby changing the lifetimes of the variables.
We can solve scheduling problems by keeping track of
resource utilization over time. We do not have to know the exact
microarchitecture of the CPU - all we have to know is that, for
instruction types 1 and 2 both use resource A while instruction types 3
and 4 use resource B.
CPU manufacturers generally disclose enough information about the microarchitecture to allow us to schedule instructions even when they do not provide a detailed description of the CPU's internals.
We can keep track of CPU resources during instruction
scheduling using a reservation table. As
illustrated in Figure 5-20 below,
rows in the table represent instruction
execution time slots and columns represent resources that must be
Before scheduling an instruction to be executed at a
particular time, we check the reservation table to determine whether
all resources needed by the instruction are available at that time.
Upon scheduling the instruction, we update the table to
resources used by that instruction. Various algorithms can be used for
the scheduling itself, depending on the types of resources and
instructions involved, but the reservation table provides a good
summary of the state of an instruction scheduling problem in progress.
We can also schedule instructions to maximize
performance. When an instruction that takes more cycles than
normal to finish is in the pipeline, pipeline bubbles appear that
reduce performance. Software pipelining is a technique for reordering
instructions across several loop iterations to reduce pipeline bubbles.
Software pipelining is illustrated in Example 5-7.
|Figure 5-20. A reservation table for instruction scheduling.|