In this video, we're going to begin a
discussion of Register Allocation which is
one of the most sophisticated things that
compilers do to optimize performance and
also involves many of the concepts that
we've been discussing in global flow
analysis. Recall that intermediate code
can use unlimited numbers of temporaries
and this simplifies a number of things.
Particularly it simplifies optimization so
we don't have to worry about preserving
the right number of registers in the code.
But, it does complicate the final
translation into assembly code cuz we
might be using too many temporaries and
this is actually a problem in practice.
So, it's not uncommon at all for
intermediate code to use more temporaries
than there are registers on the target
machine. The problem then is to rewrite
the intermediate code to use no more
temporaries than there are machine
registers and the way we're going to do
that is we're going to assign multiple
temporaries to each register. So, we're
going to have a many-one mapping. A many
to one mapping from temporaries to
registers, okay? And, clearly there's a
little bit of an issue here if we really
are using many temporaries, we will not be
able to fit them all into a single
register. So there needs to be some kind
of a trick and we'll say what that trick
is in a few minutes and there will be
situations actually when this will fail,
we'll have to have some kind of back up
plan. But our default plan is to try to
put as many temporaries as possible into
the same machine register. And doing all
of this without changing the behavior of
the program. So, how can we do this? Magic
thing. How can we actually make a single
register hold multiple values? Well, the
trick is that it's fine for registers to
have local values as long as it only has
one value at a time. So, let's consider
this program, I'm going to switch colors
here. Okay. Simple three statement program
and notice here that a is used in the
first two statements. So it's written in
the first statement, read in the second
stateme nt e is written in the second
statement and read in the third statement
and that is only written in the third
statement. And actually, these three
values a, e and f, they don't ever really
co-exist at the same time but at the time
we've read a we are really done with it.
We've all the uses that they are going to
have in this little code fragment. Here,
I'm assuming that a and effort are not
used anywhere else and so it turns out
that a, e, and f could all actually live
in the same register. Alright, that's
assuming that a and e are dead after their
uses. And what will that look like, well
let's allocate them all to a particular
register r1 and let's assign c, d, and b
into their own individual registers and
the code would like this, r1 would be r2 +
r3, and then r1 would be r1 + r4 and r1
would be r1 - one. And so now notice how
this is just a transliteration of the code
over here into registers but there is a
many one mapping of names on the left to
register names on the right. A register
allocation is an old problem. In fact, it
was first recognized way back in the 1950s
in the original Fortran project but
originally, register allocation was done
with a fairly crude algorithms and who is
rapidly or very quickly noticed that was
actually a bottle neck in the quality of
code generation that actually limitations
on the ability of register allocation and
do a good job have a really significant
effect on the overall equality, overall
quality of the code that compilers could
produce. And then about 30 years later, in
1980, a breakthrough occurred where people
discovered or a group of researchers at
IBM discovered a register allocation
scheme based on graph coloring. And the
great thing about this scheme is that it's
pretty simple. It's easy to explain. It's
global, meaning it takes advantage of
information from the entire control flow
graph at the same time and also happens to
work well in practice. And here's the
basic principle that underlies the modern
register allocation algorithms. So, if I
have two temporaries t1 and t2, I want to
know when they can share register. So,
they're allowed to share a register and
they're allowed to be in the same register
if they are not live at the same time,
okay? So like I said, any point in the
program in most one of t1 or t2 as live.
And we are more concise which I already
said was partially is, is that if t2, t1
and t2 are live at the same time, okay?
Meaning that there's, there's some program
point were both are live then they cannot
share a register, alright? So this is the
negative form of the statement and it just
tells you that if, if you need two values
at the same moment in time, then they have
to be in separate registers. Let's take a
look at a control flow graph and now, we
know the [inaudible] register allocation
to solve register allocation at least in
this in this way, we're going to need
liveness information. So, let's compute
the live variables for each point of this
program. So, here it is and I'll just walk
through it very quickly. Let's assume that
on exit from this loop that only b is
live. So b is the output of this piece of
the code and it's used elsewhere but none
of the other variables are live. So, now
if we work backwards, remember that line
is a backward analysis. We'll see here
that b is written so it's not live before
the statement but f and c are read. So,
both c and f are live before this basic
block. Okay, and similarly if we, if we go
up another level here, here we see that e
is now alive and f is dead because f was
written here and e was read. And over on
this path, here we have another exit where
b is live and now at this point here right
after this basic block the set of lot
variables that are live is b, c, and f
because b is live on one path and c and f
are live on the other path. Remember for
something to be live, it only has to be
live on some, in some future possible
evolution of the execution. So, on some
path out of this node is a variables live,
then it's live at the exit from this.
Working backwards here. B, c, and f are
live here because e is read. And b, c, and
f are not referred to in this statement
and so they just propagate upwards. Here b
is removed from the live f because it's
written but d is added and set here and
similarly, for the other edges in this
graph. If you go and check all the other
edges you will see that the live set is
correct and it just follows from the
simple rules we gave in the previous
video. But how are going to use the
liveness information to do register
allocation? Well, we're going to construct
and undirected graph and in this graph,
there will be a node for each temporaries
so each variable will have a node in the
graph and there'll be an edge between two
temporaries if they are live
simultaneously at some point in the
program, alright? So backing up and
looking at our little example here, we can
see for example at this point in the
program c and e are both live. They're
both in the live set after this basic
block executes. So c and e cannot be in
the same register. Alright, continuing on,
this is called, this data structure, this
graph is called the Register Interference
Graph or RIG for short. And again, the
basic idea is that two temporaries can be
allocated in the same register if there is
no edge connecting them in the register
interference graph. So, here's a register
interference graph for our example. This
is the graph constructed from the code and
the line analysis that we're given a few
slides ago and you know, it's easy to read
off from the graph what the constraints
are. So, for example b and c cannot be in
the same register because b and c are
connected by an edge. Okay, seeing that
they're live simultaneously at some part,
some point in the program and so they have
to live in different registers. On the
other hand, there is at, there is no edge
between b and d, okay. So, this edge is
missing and therefore, it's possible that
b and d could be allocated in the same
register. They are live ranges all the
times in which they are alive do not
overlapped. So a great thing about the
register interference graph is that it
extracts exactly the information needed to
characterize a legal register assignment.
So, it gives us a representation of all
the possible legal register assignments.
Now, I haven't said I haven't actually get
a register assignment out of the register
interference graph, but the first step is
to characterize the problem in some kind
of precise way. And the graph of, cannot
live in the same register constraints does
that for us. The other thing that is good
about is a, is a global view of the
register requirements meaning it's over
the entire control flow graphs. So, takes
into account information from every part
of control flow graph which will help us
to make good global decisions about what
value is very important to live in
registers. And finally, the other thing to
notice is that, that after reconstruction,
the register allocation for algorithm is
going, is architecture independent. I
haven't shown you the algorithm so you
just have to believe the statement for the
moment but it's going to turn out that
were not going to depend on any property
of the machine except for the number of
registers. So, that's the only thing we
need to know about the machine in order to
take a RIG and, and do register allocation
using it.