The graph coloring here is like that we
discussed in the previous video doesn't
always succeed in coloring an arbitrary
graph. And it may well get stuck and not
be able to find a coloring. And so in that
case the only conclusion we can reach is
that we can't hold all the values that
we'd like to register. We have more
temporary values and we have registers to
hold them. And those temporary values have
to live somewhere so where should they
live? Well, they're going to have to live
in memory. That's the only other kind of
stories that we have. And so we're going
to pick some values and spill them into
memory. The ideas that we have, the
picture in your mind should be. A bucket
and it can hold a fixed amount of stuff.
Those are the registers and when it gets
too full, some of the stuff spills over
and, and ends up some place else. Now,
when does the graph coloring here do get
stuck? Well, this only situation which we
won't be able to make progress as if all
the notes have [inaudible] or more
neighbors. So, let's take a look at our
favorite register interference graph when
we will be using at our examples and now,
let's say that our, the machine we want to
use only has three registers and so we,
instead of finding a free coloring of this
graph, we need to find a free coloring. So
let's think about how to find the three
coloring of this graph. If we apply the
[inaudible], we'll remove A from the graph
but then we're going to get stuck. Because
once you take A out of the graph and it's
edge is out and every [inaudible] that's
left has more than has three or more
neighbors as at least three neighbors. So,
there's no, know that we can delete from
the graph and be guaranteed to be able to
find the coloring for it with [inaudible]
that we discussed in the previous video.
So, in this situation, what we're going to
do is we're going to pick and know that
there is a candidate for spilling. This is
a know that we or a temporary that we are
probably or we think we may have to assign
into a memory location rather than to our
register and let is assume for the sake of
this example that we pick f and we talk
later about how to choose a, the know to
spill, there's a number of different ways
to, to chose the particular know to spill
but for the illustration of this example,
it doesn't matter how pick, we just have
to pick one to remove from the. Graph. As
were going to say, we're going to remove,
that we going to spill F. So what we'll do
then is we'll remove f from the graph just
like before and then we'll continue with
our simplification and this will now
succeed because once we move F from the
graph we can see that all the nodes well,
actually several of the nodes have fewer
than three neighbors and so B, C, and D.
Sorry, B and D both only have two
neighbors when [inaudible] E and C will
only have one neighbor each and so clearly
coloring will now succeed and here's one
order that we'll succeed with this reduced
graph. After we decide to spill f and we
successfully color the sub-graph, now we
have to try to assign a color to f and it
could be, we could get lucky and discover
that even though f had more than there
neighbors or three or more neighbors when
we remove it from the graph, it could be
that when we go to construct the coloring
for the sub-graph that. Those neighbors
actually don't use all of the register. It
could wind up being at all those
neighbors, for example or assign to the
same register and so there are plenty of
registers left over to assign to f. And
so, this is called optimistic coloring. So
we pick a candidate for spilling. We tried
to color the sub-graph. Once we have a
coloring for the sub-graph, now we see if
we just get lucky. And are able to assign
a register to F. In which case we can just
go ahead and continue the color of the
rest of the graph as if nothing had
happened. So in this case let's take a
look what happens. We're going add F back
into the graph. And. And look at all, and
look at it's neighbors and we see that we
have a neighbor that's using r1. We have a
neighbor that's using r2 and we have a
neighbor that's using r2 and we have a
neighbor that's using r3. And so on in
this case, optimistic coloring will not
work so in fact F had more than K
neighbors and after we color the
sub-graph, it turns out that those
neighbors are using all K. In this case
three, all three of the register names.
And so F where there is no register left
over for F and we're going to have to
actually spill it and store in memory. So,
if optimistic coloring fails as it does in
this example, then we spill f. So, what
we're going to do is allocate the memory
location for f and typically, what that
means is that we'll allocate a position in
the current stack frame. Let's call this
address fa for the address of f. And then
we're going to modify the control flow
graph. We're going to change the code for
that compiling. So, before each operation
that reads f, we're going to insert a load
that loads from that address to current
value of f into a temporary name. Okay,
that makes sense because if the value is
out of memory, then if we have an
operation that needs to actually use the
value. We're going to have to load it from
a memory first then to the register. And
similarly after each operation that writes
F, we're going to insert the store so
we're going to save the current value of F
into it's location in memory. So, here is
the original code from which we
constructed the registry interference
graph and notice that there are few
references to f in here and we just
highlight them, alright. So, we have a
couple of [inaudible], we have a right and
so now, what are we going to do. So, here
we have the use of F, the read of F in
this statement and now we preceded that by
a load. And notice that I've given a new
name here. I called this F1. And, that's
because the different uses of F in the
control flow graph don't all have to have
the same temporary name. And actually it
would be a good idea to separate them so
each distinct to use of F will get it's
own name. So here we load the value of F
and then it get to use in the statement.
Here we have a right to f and so we store
the current value of f and those argument
to a different name, f2. So, that's
temporary is computed here as going to be
stored and it's called f2. And finally,
the third use of f there's another load of
f right here. Which is then used in this
computation here of b. Okay. So, that is
the systematic way to modify the code to
use f in storage. And now, we have to
recompute the aliveness of f. And so, what
happens there. Well, here is the original
aliveness information from which we
computed the register interference graph,
okay. And now notice that f is gone. We no
longer use f in the programs so we can
delete all the places where we mentioned
that f was live and now we have the three
new names, f1, f2, and f3. And we have to
add in their aliveness information so it
creates a new program points here where we
inserted statements. And of course, where
we have a load of the current value of f
that value if live right before the use in
the next statement. Here, we have the
right of the current value of f and that's
live right before the store and then
here's another load of the current value
of f which is live until the store, I'm
sorry, until the use in the next
statement. Okay. And so, now notice here
that f used to be live in many, many, many
places in the, in the code. And now not
only is f or the, the different versions
of f live in fewer places also we've
distinguish them. So, it actually separate
the different uses of f and so this will
have their own nodes in their own set of
interferences in the graph and they won't
share them with the other users of f and
that will actually also reduce the number
of edges in the graph. To summarize the
example on the previous slide, once we
have decided that we are actually going to
spill a temporary f, that means we're
going to change the program where have
loads and stores to the program and now
we're g oing to have a different program
and that's going to change our register
allocation problems. We're going to have
to recompute the aliveness of information,
we're have to rebuild the restrain
interference graph and then we're going to
have to try again to color that block
graph. Now, it turns out that this new
aliveness information is almost the same
as it was before. So, all the temporary
names other than f are not much affected
by the by the new statements that are
added. There are a few program points
where they might be live but I replaced
they were alive before and they're still
alive. And, F itself has changed fairly
dramatically. It's like this information
has changed really dramatically. Certainly
the old name F is no longer used and so
it's like this information goes away and
then we've also split F into three in this
case three different temporaries. One for
each of the different uses of F in the
control flow graph. And I noticed that
each of these new uses of F or these new
versions of F is live in a very, very
small area so a load. In this video, we
are going to continue our discussion of
register allocation and this time, we're
going to talk about what happens when we
can't successfully color the graph. In
which case, we have to do something known
as filling. For a load instruction The
thing that were loading the temporary that
we're loading fi is live only between the
load and the next instruction where it's
used and similarly for a store. It's score
of a temporary fi is live only between the
store itself and the proceeding
instruction. The one they created fi. And
the effective is, is to greatly reduce the
live range of the spilled variable. So,
whatever name we decide to spill by adding
the load and stores right next to the
places where those values are used We
dramatically reduced the live range and in
addition, as I mentioned in the previous
live by splitting the name f into multiple
different name, we also you know, avoid
sharing. Those different liv e ranges
between the different versions of F. So
because the live range of F is reduced by
spilling. It has fewer interferences in
the new program than it did in the old
program. And so what that means the
particulars in the rebuild [inaudible]
interference graph, F will have fewer
neighbors. Some of the neighbors that it
had before have gone away because it just
live in fewer places. So if we look at the
new register interference graph, we can
see that among all the different versions
of F. Remember that F has been split into
three temporaries in this graph. We see
that they only interfere with D and C.
Whereas, before f have several other
neighbors in the graph. And now, in fact
this new graph is three tolerable. Of
course it might be the case that we can't
just spill one name. We might have to have
just spill several different temporaries
before the coloring is found. And, the
tricky part is to siding what to spill.
So, this is the hard decision that has to
be made during restore allocation. Now any
choice is correct. It's only a question of
performance so you know some choices of
spilling will lead to better code than
others but any choice of spilling is going
to resolve in a correct program. And
there's heuristics that people use to pick
which temporaries to spill and here are a
few or I think three of the most popular
ones. One is to spill the temporaries and
have the most conflicts. And the reason
for that is that this is the temporary.
The one thing that you can move into
memory that will most affect the number of
interferences in the graph. So, the idea
is by possible spilling justice on
variable. We'll remove enough edges from
the graph that they becomes tolerable with
the number of registers we have. Another
possibility is a spilled temporaries that
have few definitions and uses. And, here
the idea is that by spilling those since
they're not used very much, the number of
lows in storage will have to add, will be
relatively small and so if a variable
[inaudible] man y places then the actual
cost in terms of, additional instructions
that are going to be executed to, spill it
is relatively small. And another one and
this is actually the one that I think that
all the compilers implement is to avoid
spilling an inner loops. So, if you have a
choice between spilling a variable that's
used within the. Innermost loop for the
program and one that is used some place
else. You probably preferred this that you
spill the one that is used not in the
innermost loop absolutely because again,
that will result in fewer loads in stores.
You really want to avoid adding additional
instructions to your inner loop. To
summarize this video, register allocation
is one of the most important jobs that a
compiler performs. And it's really, these
days they must have an any kind of
reasonable production compiler. And, the
reason you need it is because the
inter-media code just generally uses too
many temporaries. We're allowed to be
[inaudible] with inter-media code
precisely because we have good register
allocation algorithms. And the other
reason, registers are just a very
important resource in making good user
registers. Having some procedure for
making efficient use of the registers.
Leads to much, much better code in the
end, much more efficient code. Now. The
register allocation algorithm I described
here is really targeted at risk machine.
So, for risk machine reduce instruction
set computer what kind of machine. You can
pretty much take the register allocation
algorithm that I described and if any for
those machines it would work out of the
box. [inaudible] machines which stands for
complex instructions for computers. Often
have restrictions on how the register can
be used. Certain operation can only work
with certain registers. You may have
register to different sizes that can only
hold certain values. And so it becomes
more complicated to register allocation
for such machines. What people have done
is to adapt the graph coloring procedure
that I descri bed here. So, the basic idea
is exactly the same and you would
recognize those algorithms is being
primarily the graph color algorithms that
we discussed. There are just additional.
Steps in those algorithms and places where
the particular constraints are what
registers can be used have to be observed.