1
00:00:03,031 --> 00:00:07,020
In this video, we're going to begin a
discussion of Register Allocation which is

2
00:00:07,020 --> 00:00:11,087
one of the most sophisticated things that
compilers do to optimize performance and

3
00:00:11,087 --> 00:00:15,024
also involves many of the concepts that
we've been discussing in global flow

4
00:00:15,024 --> 00:00:20,803
analysis. Recall that intermediate code
can use unlimited numbers of temporaries

5
00:00:20,803 --> 00:00:26,072
and this simplifies a number of things.
Particularly it simplifies optimization so

6
00:00:26,072 --> 00:00:31,030
we don't have to worry about preserving
the right number of registers in the code.

7
00:00:31,030 --> 00:00:34,618
But, it does complicate the final
translation into assembly code cuz we

8
00:00:34,618 --> 00:00:40,177
might be using too many temporaries and
this is actually a problem in practice.

9
00:00:40,177 --> 00:00:44,609
So, it's not uncommon at all for
intermediate code to use more temporaries

10
00:00:44,609 --> 00:00:50,393
than there are registers on the target
machine. The problem then is to rewrite

11
00:00:50,393 --> 00:00:55,522
the intermediate code to use no more
temporaries than there are machine

12
00:00:55,522 --> 00:01:00,040
registers and the way we're going to do
that is we're going to assign multiple

13
00:01:00,040 --> 00:01:05,749
temporaries to each register. So, we're
going to have a many-one mapping. A many

14
00:01:05,749 --> 00:01:12,195
to one mapping from temporaries to
registers, okay? And, clearly there's a

15
00:01:12,195 --> 00:01:18,126
little bit of an issue here if we really
are using many temporaries, we will not be

16
00:01:18,126 --> 00:01:22,003
able to fit them all into a single
register. So there needs to be some kind

17
00:01:22,003 --> 00:01:25,507
of a trick and we'll say what that trick
is in a few minutes and there will be

18
00:01:25,507 --> 00:01:29,610
situations actually when this will fail,
we'll have to have some kind of back up

19
00:01:29,610 --> 00:01:34,620
plan. But our default plan is to try to
put as many temporaries as possible into

20
00:01:34,620 --> 00:01:41,145
the same machine register. And doing all
of this without changing the behavior of

21
00:01:41,145 --> 00:01:48,349
the program. So, how can we do this? Magic
thing. How can we actually make a single

22
00:01:48,349 --> 00:01:53,228
register hold multiple values? Well, the
trick is that it's fine for registers to

23
00:01:53,228 --> 00:01:57,852
have local values as long as it only has
one value at a time. So, let's consider

24
00:01:57,852 --> 00:02:02,952
this program, I'm going to switch colors
here. Okay. Simple three statement program

25
00:02:02,952 --> 00:02:07,355
and notice here that a is used in the
first two statements. So it's written in

26
00:02:07,355 --> 00:02:11,262
the first statement, read in the second
stateme nt e is written in the second

27
00:02:11,262 --> 00:02:15,378
statement and read in the third statement
and that is only written in the third

28
00:02:15,378 --> 00:02:19,982
statement. And actually, these three
values a, e and f, they don't ever really

29
00:02:19,982 --> 00:02:25,289
co-exist at the same time but at the time
we've read a we are really done with it.

30
00:02:25,289 --> 00:02:29,016
We've all the uses that they are going to
have in this little code fragment. Here,

31
00:02:29,016 --> 00:02:32,769
I'm assuming that a and effort are not
used anywhere else and so it turns out

32
00:02:32,769 --> 00:02:37,364
that a, e, and f could all actually live
in the same register. Alright, that's

33
00:02:37,364 --> 00:02:42,454
assuming that a and e are dead after their
uses. And what will that look like, well

34
00:02:42,454 --> 00:02:48,026
let's allocate them all to a particular
register r1 and let's assign c, d, and b

35
00:02:48,026 --> 00:02:53,509
into their own individual registers and
the code would like this, r1 would be r2 +

36
00:02:53,509 --> 00:02:59,371
r3, and then r1 would be r1 + r4 and r1
would be r1 - one. And so now notice how

37
00:02:59,371 --> 00:03:05,892
this is just a transliteration of the code
over here into registers but there is a

38
00:03:05,892 --> 00:03:13,278
many one mapping of names on the left to
register names on the right. A register

39
00:03:13,278 --> 00:03:20,046
allocation is an old problem. In fact, it
was first recognized way back in the 1950s

40
00:03:20,046 --> 00:03:24,990
in the original Fortran project but
originally, register allocation was done

41
00:03:24,990 --> 00:03:29,971
with a fairly crude algorithms and who is
rapidly or very quickly noticed that was

42
00:03:29,971 --> 00:03:35,152
actually a bottle neck in the quality of
code generation that actually limitations

43
00:03:35,152 --> 00:03:39,384
on the ability of register allocation and
do a good job have a really significant

44
00:03:39,384 --> 00:03:44,308
effect on the overall equality, overall
quality of the code that compilers could

45
00:03:44,308 --> 00:03:51,001
produce. And then about 30 years later, in
1980, a breakthrough occurred where people

46
00:03:51,001 --> 00:03:54,689
discovered or a group of researchers at
IBM discovered a register allocation

47
00:03:54,689 --> 00:03:59,035
scheme based on graph coloring. And the
great thing about this scheme is that it's

48
00:03:59,035 --> 00:04:03,091
pretty simple. It's easy to explain. It's
global, meaning it takes advantage of

49
00:04:03,091 --> 00:04:08,024
information from the entire control flow
graph at the same time and also happens to

50
00:04:08,024 --> 00:04:17,084
work well in practice. And here's the
basic principle that underlies the modern

51
00:04:17,084 --> 00:04:23,019
register allocation algorithms. So, if I
have two temporaries t1 and t2, I want to

52
00:04:23,019 --> 00:04:27,005
know when they can share register. So,
they're allowed to share a register and

53
00:04:27,005 --> 00:04:32,065
they're allowed to be in the same register
if they are not live at the same time,

54
00:04:32,065 --> 00:04:37,086
okay? So like I said, any point in the
program in most one of t1 or t2 as live.

55
00:04:37,086 --> 00:04:43,217
And we are more concise which I already
said was partially is, is that if t2, t1

56
00:04:43,217 --> 00:04:47,076
and t2 are live at the same time, okay?
Meaning that there's, there's some program

57
00:04:47,076 --> 00:04:53,097
point were both are live then they cannot
share a register, alright? So this is the

58
00:04:53,097 --> 00:04:57,730
negative form of the statement and it just
tells you that if, if you need two values

59
00:04:57,730 --> 00:05:04,682
at the same moment in time, then they have
to be in separate registers. Let's take a

60
00:05:04,682 --> 00:05:08,854
look at a control flow graph and now, we
know the [inaudible] register allocation

61
00:05:09,062 --> 00:05:14,039
to solve register allocation at least in
this in this way, we're going to need

62
00:05:14,039 --> 00:05:18,884
liveness information. So, let's compute
the live variables for each point of this

63
00:05:18,884 --> 00:05:25,564
program. So, here it is and I'll just walk
through it very quickly. Let's assume that

64
00:05:25,564 --> 00:05:30,624
on exit from this loop that only b is
live. So b is the output of this piece of

65
00:05:30,624 --> 00:05:35,135
the code and it's used elsewhere but none
of the other variables are live. So, now

66
00:05:35,135 --> 00:05:40,702
if we work backwards, remember that line
is a backward analysis. We'll see here

67
00:05:40,702 --> 00:05:46,566
that b is written so it's not live before
the statement but f and c are read. So,

68
00:05:46,566 --> 00:05:52,128
both c and f are live before this basic
block. Okay, and similarly if we, if we go

69
00:05:52,128 --> 00:05:57,287
up another level here, here we see that e
is now alive and f is dead because f was

70
00:05:57,287 --> 00:06:03,356
written here and e was read. And over on
this path, here we have another exit where

71
00:06:03,356 --> 00:06:08,316
b is live and now at this point here right
after this basic block the set of lot

72
00:06:08,316 --> 00:06:13,858
variables that are live is b, c, and f
because b is live on one path and c and f

73
00:06:13,858 --> 00:06:19,515
are live on the other path. Remember for
something to be live, it only has to be

74
00:06:19,515 --> 00:06:24,108
live on some, in some future possible
evolution of the execution. So, on some

75
00:06:24,108 --> 00:06:30,114
path out of this node is a variables live,
then it's live at the exit from this.

76
00:06:30,358 --> 00:06:38,062
Working backwards here. B, c, and f are
live here because e is read. And b, c, and

77
00:06:38,062 --> 00:06:45,010
f are not referred to in this statement
and so they just propagate upwards. Here b

78
00:06:45,010 --> 00:06:49,082
is removed from the live f because it's
written but d is added and set here and

79
00:06:49,082 --> 00:06:54,049
similarly, for the other edges in this
graph. If you go and check all the other

80
00:06:54,049 --> 00:06:58,087
edges you will see that the live set is
correct and it just follows from the

81
00:06:58,087 --> 00:07:04,072
simple rules we gave in the previous
video. But how are going to use the

82
00:07:04,072 --> 00:07:09,049
liveness information to do register
allocation? Well, we're going to construct

83
00:07:09,049 --> 00:07:14,004
and undirected graph and in this graph,
there will be a node for each temporaries

84
00:07:14,004 --> 00:07:18,060
so each variable will have a node in the
graph and there'll be an edge between two

85
00:07:18,060 --> 00:07:22,099
temporaries if they are live
simultaneously at some point in the

86
00:07:22,099 --> 00:07:29,041
program, alright? So backing up and
looking at our little example here, we can

87
00:07:29,041 --> 00:07:33,059
see for example at this point in the
program c and e are both live. They're

88
00:07:33,059 --> 00:07:39,047
both in the live set after this basic
block executes. So c and e cannot be in

89
00:07:39,047 --> 00:07:46,038
the same register. Alright, continuing on,
this is called, this data structure, this

90
00:07:46,038 --> 00:07:53,026
graph is called the Register Interference
Graph or RIG for short. And again, the

91
00:07:53,026 --> 00:07:57,047
basic idea is that two temporaries can be
allocated in the same register if there is

92
00:07:57,047 --> 00:08:03,044
no edge connecting them in the register
interference graph. So, here's a register

93
00:08:03,044 --> 00:08:10,332
interference graph for our example. This
is the graph constructed from the code and

94
00:08:10,332 --> 00:08:15,311
the line analysis that we're given a few
slides ago and you know, it's easy to read

95
00:08:15,311 --> 00:08:19,895
off from the graph what the constraints
are. So, for example b and c cannot be in

96
00:08:19,895 --> 00:08:24,516
the same register because b and c are
connected by an edge. Okay, seeing that

97
00:08:24,516 --> 00:08:28,042
they're live simultaneously at some part,
some point in the program and so they have

98
00:08:28,042 --> 00:08:32,046
to live in different registers. On the
other hand, there is at, there is no edge

99
00:08:32,046 --> 00:08:37,063
between b and d, okay. So, this edge is
missing and therefore, it's possible that

100
00:08:37,063 --> 00:08:41,083
b and d could be allocated in the same
register. They are live ranges all the

101
00:08:41,083 --> 00:08:48,032
times in which they are alive do not
overlapped. So a great thing about the

102
00:08:48,032 --> 00:08:52,064
register interference graph is that it
extracts exactly the information needed to

103
00:08:52,064 --> 00:08:57,033
characterize a legal register assignment.
So, it gives us a representation of all

104
00:08:57,033 --> 00:09:01,006
the possible legal register assignments.
Now, I haven't said I haven't actually get

105
00:09:01,006 --> 00:09:04,082
a register assignment out of the register
interference graph, but the first step is

106
00:09:04,082 --> 00:09:10,022
to characterize the problem in some kind
of precise way. And the graph of, cannot

107
00:09:10,022 --> 00:09:15,023
live in the same register constraints does
that for us. The other thing that is good

108
00:09:15,023 --> 00:09:19,036
about is a, is a global view of the
register requirements meaning it's over

109
00:09:19,036 --> 00:09:23,081
the entire control flow graphs. So, takes
into account information from every part

110
00:09:23,081 --> 00:09:28,032
of control flow graph which will help us
to make good global decisions about what

111
00:09:28,032 --> 00:09:32,422
value is very important to live in
registers. And finally, the other thing to

112
00:09:32,422 --> 00:09:36,073
notice is that, that after reconstruction,
the register allocation for algorithm is

113
00:09:36,073 --> 00:09:40,051
going, is architecture independent. I
haven't shown you the algorithm so you

114
00:09:40,051 --> 00:09:44,059
just have to believe the statement for the
moment but it's going to turn out that

115
00:09:44,059 --> 00:09:48,007
were not going to depend on any property
of the machine except for the number of

116
00:09:48,007 --> 00:09:51,076
registers. So, that's the only thing we
need to know about the machine in order to

117
00:09:51,076 --> 00:09:55,029
take a RIG and, and do register allocation
using it.