Chapter: Compilers : Principles, Techniques, & Tools : Code Generation
A Simple Code Generator
A Simple Code Generator
1 Register and Address
Descriptors
2 The Code-Generation Algorithm
3 Design of the Function getReg
4 Exercises for Section 8.6
In this section, we shall consider an algorithm that generates code for
a single basic block. It considers each three-address instruction in turn, and
keeps track of what values are in what registers so it can avoid generating
unnecessary loads and stores.
One of the primary issues during code generation is
deciding how to use registers to best advantage. There are four principal uses
of registers:
In most machine architectures, some or all of the operands of an
operation must be in registers in order to perform the operation.
Registers make good temporaries — places to hold
the result of a subex-pression while a larger expression is being evaluated, or
more generally, a place to hold a variable that is used only within a single
basic block.
Registers are used to hold (global)
values that are computed in one basic block and used in other blocks, for
example, a loop index that is incre-
mented going around the loop and is used several
times within the loop.
Registers are often used to help with run-time storage management, for
example, to manage the run-time stack, including the maintenance of stack
pointers and possibly the top elements of the stack itself.
These are competing needs, since
the number of registers available is limited. The algorithm in this section
assumes that some set of registers is available to hold the values that are
used within the block. Typically, this set of regis-ters does not include all
the registers of the machine, since some registers are reserved for global
variables and managing the stack. We assume that the basic block has already
been transformed into a preferred sequence of three-address instructions, by
transformations such as combining common subexpressions. We further assume that
for each operator, there is exactly one machine instruc-tion that takes the
necessary operands in registers and performs that operation, leaving the result
in a register. The machine instructions are of the form
LD reg, mem
ST mem, reg
OP reg, reg, reg
1. Register and Address
Descriptors
Qur code-generation algorithm
considers each three-address instruction in turn and decides what loads are
necessary to get the needed operands into registers. After generating the
loads, it generates the operation itself. Then, if there is a need to store the
result into a memory location, it also generates that store.
In order to make the needed
decisions, we require a data structure that tells us what program variables
currently have their value in a register, and which register or registers, if
so. We also need to know whether the memory location for a given variable
currently has the proper value for that variable, since a new value for the
variable may have been computed in a register and not yet stored. The desired
data structure has the following descriptors:
For each available register, a register descriptor keeps track of the
variable names whose current value is in that register. Since we shall use only
those registers that are available for local use within a basic block, we
assume
that initially, all register descriptors are empty.
As the code generation progresses, each register will hold the value of zero or
more names.
For each program variable, an address descriptor keeps track of the loca-tion or locations where
the current value of that variable can be found. The location might be a
register, a memory address, a stack location, or some set of more than one of
these. The information can be stored in the symbol-table entry for that
variable name.
2. The Code-Generation Algorithm
An essential part of the
algorithm is a function getReg(I),
which selects regis-ters for each memory location associated with the
three-address instruction I. Function getReg
has access to the register and address descriptors for all the variables of the
basic block, and may also have access to certain useful data-flow information
such as the variables that are live on exit from the block. We shall discuss getReg after presenting the basic algorithm.
While we do not know the total number of registers available for local data
belonging to a basic block, we assume that there are enough registers so that,
after freeing all available regis-ters by storing their values in memory^ there
are enough registers to accomplish any three-address operation.
In a three-address instruction such as x = y + z, we shall
treat + as a generic operator and ADD as the equivalent machine instruction. We do not, therefore, take
advantage of commutativity of +. Thus, when we implement the operation, the
value of y must be in the second register mentioned in the ADD
instruction, never the third. A possible improvement to the algorithm is to
generate code for both x = y + z and x = z + y whenever + is a commutative operator, and pick the better code
sequence.
Machine Instructions
for Operations
For a three-address instruction such as x = y + z, do the following:
1. Use getReg(x = y + z) to select registers for x,
y, and z. Call these Rx, Ry, and Rz.
2. If y is not in Ry (according to the register
descriptor for Ry), then issue an instruction LD Ry,y', where y' is one of the
memory locations for y (according to the address descriptor for y).
Similarly,
if z is not in Rz, issue and instruction LD Rz,z', where z' is a location for
z.
Issue the
instruction ADD Rx,Ry,Rz.
Machine
Instructions for Copy Statements
There is an important special case: a three-address
copy statement of the form x = y. We assume that getReg will always choose the
same register for both x and y. If y is not already in that register Ry, then
generate the machine instruction LD Ry, y. If y was already in Ry, we do
nothing. It is only necessary that we adjust the register description for Ry so
that it includes x as one of the values found there.
Ending the Basic
Block
As we have described the algorithm, variables used by the block may wind
up with their only location being a register. If the variable is a temporary
used only within the block, that is fine; when the block ends, we can forget
about the value of the temporary and assume its register is empty. However, if
the variable is live on exit from the block, or if we don't know which
variables are live on exit, then we need to assume that the value of the
variable is needed later. In that case, for each variable x whose location descriptor does not say that its value is located
in the memory location for x, we must
generate the instruction ST x, R, where R is a register in which #'s value
exists at the end of the block.
Managing
Register and Address Descriptors
As the code-generation algorithm
issues load, store, and other machine instruc-tions, it needs to update the
register and address descriptors. The rules are as follows:
For the instruction LD R:x
Change the register descriptor
for register R so it holds only x.
Change the address descriptor for
x by adding register R as an ad-ditional location.
For the instruction ST x, R, change the address descriptor for x to include its own memory location.
For an operation such as ADD Rx,Ry,Rz implementing a three-address instruction x — y + z
Change the register descriptor
for Rx so that it holds only x.
Change the address descriptor for
x so that its only location is Rx. Note that the memory location for x
is not now in the address de-scriptor
for x.
(c) Remove Rx from the address descriptor of
any variable other than x.
When we process a copy statement x = y, after generating the load for y into register Ry, if
needed, and after managing descriptors as for all load statements (per rule 1):
(a) Add x to the register descriptor for
Ry.
(b) Change the address descriptor for x so that its only location is Ry.
Example 8.16 : Let us translate the basic block
consisting of the three-address statements
t = a - b
u = a
- c
v = t + u
a = d
d = v + u
Here we assume that t, u, and v are
temporaries, local to the block, while a, b, c, and d are
variables that are live on exit from the block. Since we have not yet
discussed how the function getReg
might work, we shall simply assume that there are as many registers as we need,
but that when a register's value is no longer needed (for example, it holds
only a temporary, all of whose uses have been passed), then we reuse its
register.
A summary of all the machine-code
instructions generated is in Fig. 8.16. The figure also shows the register and
address descriptors before and after the translation of each three-address
instruction.
For the first three-address instruction, t = a - b we need
to issue three in-structions, since nothing is in a register initially. Thus,
we see a and b loaded into registers Rl and R2, and the value t produced in register R2. Notice that we can use R2 for t because the value b previously in R2 is not
needed within the block. Since b is presumably live on exit from the block, had
it not been in its own memory location (as indicated by its address
descriptor), we would have had to store R2 into b
first. The decision to do so, had we needed R2, would be
taken by getReg.
The second instruction, u = a - c ,
does not require a load of a, since it is already in register Rl. Further,
we can reuse Rl for the result, u, since the value of a,
previously in that register, is no longer needed within the block, and its
value is in its own memory location if a is
needed outside the block. Note that we change the address descriptor for a to
indicate that it is no longer in Rl, but is in the memory location called a.
The third instruction, v = t + u,
requires only the addition. Further, we can use R3 for the
result, v, since the value of c in that register is no longer needed within the
block, and c has its value in its own memory location.
The copy instruction, a = d, requires a load of d, since it is not in memory. We show register R2's
descriptor holding both a and d. The addition of a to the register descriptor is the result of our processing the copy
statement, and is not the result of any machine instruction.
The fifth instruction, d = v + u, uses two values that are in registers.
Since u is a temporary whose value is no longer needed, we have chosen to reuse
its register Rl for the new value of d. Notice that d is now in only Rl, and is
not in its own memory location. The same holds for a, which is
in R2 and not in the memory location called a. As a
result, we need a "coda" to the machine code for the basic block that
stores the live-on-exit variables a and d into their memory locations. We show these as the last two
instructions.
3. Design of the Function getReg
Lastly, let us consider how to
implement getReg(I), for a
three-address in-struction /. There are many options, although there are also
some absolute prohibitions against choices that lead to incorrect code due to
the loss of the value of one or more live variables. We begin our examination
with the case of an operation step, for which we again use x = y + z as the generic example. First, we must pick a register
for y and a register for z. The issues are the same, so we shall
concentrate on picking register Ry for y. The rules are as
follows:
1. If 2/ is currently in a register, pick a register already containing
y as Ry. Do not issue a machine instruction to load this register, as none is
needed.
2. If y is not in a register, but
there is a register that is currently empty, pick one such register as Ry.
The difficult case occurs when y is not in a register, and there is no
register that is currently empty. We need to pick one of the allowable
registers anyway, and we need to make it safe to reuse. Let R be a candidate register, and suppose v is one of the variables that the
register descriptor for R says is in R. We need to make sure that u's value
either is not really needed, or that there is somewhere else we can go to get
the value of R. The possibilities
are:
If the address descriptor for v says that v is somewhere besides R,
then we are OK.
(b) If v is x, the value being computed by instruction /,
and x is not also one of the other operands of instruction 7 (z in this
example), then we are OK. The reason is that in this case, we know this value
of x is never again going to be used, so we are free to ignore it.
(c) Otherwise, if v is not used later (that is, after the instruction /,
there are no further uses of v, and if v is live on exit from the block, then v
is recomputed within the block), then we are OK.
If we are not OK by
one of the first two cases, then we need to generate the store
instruction ST v, R to place a copy
of v in its own memory location. This
operation is called a spill.
Since R may hold several variables at the moment, we repeat the above
steps for each such variable v. At
the end, R's "score" is the
number of store instructions we needed to generate. Pick one of the registers
with the lowest score.
Now, consider the selection of the register Rx. The issues and options are almost as for y, so we shall only mention the differences.
1. Since a new value of x is being computed, a register that
holds only x is always an acceptable
choice for Rx. This statement holds even if x
is one of y and z, since our machine instructions allows two registers to be the
same in one instruction.
2. If y is not used after instruction I,
in the sense described for variable v
in item (3c), and Ry holds only y after being
loaded, if necessary, then Ry can also be used as Rx. A similar option holds regarding z
and Rz.
The last matter to consider
specially is the case when I is a
copy instruction x — y. We pick the
register Ry as above. Then, we always choose Rx = Ry.
4. Exercises for Section 8.6
Exercise 8.6.1 : For each of the
following C assignment statements
a) x = a
+ b*c;
b) x =
a/(b+c) - d * ( e + f ) ;
c) x =
a[i] +
1;
d) a [ i ]
= b [ c [ i ] ] ;
e) a [ i
] [ j ] = b [ i ] [ k ] +
c[k][j];
f) *p++ = *q++;
generate
three-address code, assuming that all array elements are integers tak-ing four
bytes each. In parts (d) and (e), assume that a, b, and c are constants giving the
location of the first (Oth) elements of the arrays with those names, as in all
previous examples of array accesses in this chapter.
! Exercise 8.6.2: Repeat
Exercise 8.6.1 parts (d) and (e), assuming that the arrays a,
b, and c are located via pointers, pa,
pb, and pc, respectively, pointing to the
locations of their respective first elements.
Exercise 8.6.3: Convert
your three-address code from Exercise 8.6.1 into ma-chine code for the machine
model of this section. You may use as many registers as you need.
Exercise 8.6.4: Convert your three-address code
from Exercise 8.6.1 into ma-chine code, using the simple code-generation
algorithm of this section, assuming three registers are available. Show the
register and address descriptors after each step.
Exercise 8.6.5:
Repeat Exercise 8.6.4, but assuming only two registers are available.
Related Topics