1 00:00:17,280 --> 00:00:21,370 The graph coloring here is like that we discussed in the previous video doesn't 2 00:00:21,370 --> 00:00:25,460 always succeed in coloring an arbitrary graph. And it may well get stuck and not 3 00:00:25,460 --> 00:00:29,704 be able to find a coloring. And so in that case the only conclusion we can reach is 4 00:00:29,704 --> 00:00:33,487 that we can't hold all the values that we'd like to register. We have more 5 00:00:33,487 --> 00:00:37,782 temporary values and we have registers to hold them. And those temporary values have 6 00:00:37,782 --> 00:00:41,821 to live somewhere so where should they live? Well, they're going to have to live 7 00:00:41,821 --> 00:00:45,911 in memory. That's the only other kind of stories that we have. And so we're going 8 00:00:45,911 --> 00:00:49,695 to pick some values and spill them into memory. The ideas that we have, the 9 00:00:49,695 --> 00:00:54,128 picture in your mind should be. A bucket and it can hold a fixed amount of stuff. 10 00:00:54,128 --> 00:00:58,779 Those are the registers and when it gets too full, some of the stuff spills over 11 00:00:58,779 --> 00:01:03,612 and, and ends up some place else. Now, when does the graph coloring here do get 12 00:01:03,612 --> 00:01:08,277 stuck? Well, this only situation which we won't be able to make progress as if all 13 00:01:08,277 --> 00:01:12,497 the notes have [inaudible] or more neighbors. So, let's take a look at our 14 00:01:12,497 --> 00:01:16,856 favorite register interference graph when we will be using at our examples and now, 15 00:01:16,856 --> 00:01:21,266 let's say that our, the machine we want to use only has three registers and so we, 16 00:01:21,266 --> 00:01:25,691 instead of finding a free coloring of this graph, we need to find a free coloring. So 17 00:01:25,691 --> 00:01:30,204 let's think about how to find the three coloring of this graph. If we apply the 18 00:01:30,204 --> 00:01:35,003 [inaudible], we'll remove A from the graph but then we're going to get stuck. Because 19 00:01:35,003 --> 00:01:39,744 once you take A out of the graph and it's edge is out and every [inaudible] that's 20 00:01:39,744 --> 00:01:44,200 left has more than has three or more neighbors as at least three neighbors. So, 21 00:01:44,200 --> 00:01:48,885 there's no, know that we can delete from the graph and be guaranteed to be able to 22 00:01:48,885 --> 00:01:53,570 find the coloring for it with [inaudible] that we discussed in the previous video. 23 00:01:56,140 --> 00:02:00,679 So, in this situation, what we're going to do is we're going to pick and know that 24 00:02:00,679 --> 00:02:05,555 there is a candidate for spilling. This is a know that we or a temporary that we are 25 00:02:05,555 --> 00:02:10,319 probably or we think we may have to assign into a memory location rather than to our 26 00:02:10,319 --> 00:02:15,139 register and let is assume for the sake of this example that we pick f and we talk 27 00:02:15,139 --> 00:02:19,678 later about how to choose a, the know to spill, there's a number of different ways 28 00:02:19,678 --> 00:02:24,442 to, to chose the particular know to spill but for the illustration of this example, 29 00:02:24,442 --> 00:02:29,076 it doesn't matter how pick, we just have to pick one to remove from the. Graph. As 30 00:02:29,076 --> 00:02:33,687 were going to say, we're going to remove, that we going to spill F. So what we'll do 31 00:02:33,687 --> 00:02:39,108 then is we'll remove f from the graph just like before and then we'll continue with 32 00:02:39,108 --> 00:02:44,078 our simplification and this will now succeed because once we move F from the 33 00:02:44,078 --> 00:02:49,371 graph we can see that all the nodes well, actually several of the nodes have fewer 34 00:02:49,371 --> 00:02:53,953 than three neighbors and so B, C, and D. Sorry, B and D both only have two 35 00:02:53,953 --> 00:02:59,311 neighbors when [inaudible] E and C will only have one neighbor each and so clearly 36 00:02:59,311 --> 00:03:04,732 coloring will now succeed and here's one order that we'll succeed with this reduced 37 00:03:04,732 --> 00:03:11,774 graph. After we decide to spill f and we successfully color the sub-graph, now we 38 00:03:11,774 --> 00:03:17,533 have to try to assign a color to f and it could be, we could get lucky and discover 39 00:03:17,533 --> 00:03:23,154 that even though f had more than there neighbors or three or more neighbors when 40 00:03:23,154 --> 00:03:28,844 we remove it from the graph, it could be that when we go to construct the coloring 41 00:03:28,844 --> 00:03:33,864 for the sub-graph that. Those neighbors actually don't use all of the register. It 42 00:03:33,864 --> 00:03:37,906 could wind up being at all those neighbors, for example or assign to the 43 00:03:37,906 --> 00:03:42,396 same register and so there are plenty of registers left over to assign to f. And 44 00:03:42,396 --> 00:03:46,830 so, this is called optimistic coloring. So we pick a candidate for spilling. We tried 45 00:03:46,830 --> 00:03:50,869 to color the sub-graph. Once we have a coloring for the sub-graph, now we see if 46 00:03:50,869 --> 00:03:55,698 we just get lucky. And are able to assign a register to F. In which case we can just 47 00:03:55,698 --> 00:04:00,207 go ahead and continue the color of the rest of the graph as if nothing had 48 00:04:00,207 --> 00:04:04,958 happened. So in this case let's take a look what happens. We're going add F back 49 00:04:04,958 --> 00:04:11,583 into the graph. And. And look at all, and look at it's neighbors and we see that we 50 00:04:11,583 --> 00:04:16,273 have a neighbor that's using r1. We have a neighbor that's using r2 and we have a 51 00:04:16,273 --> 00:04:20,731 neighbor that's using r2 and we have a neighbor that's using r3. And so on in 52 00:04:20,731 --> 00:04:24,958 this case, optimistic coloring will not work so in fact F had more than K 53 00:04:24,958 --> 00:04:28,837 neighbors and after we color the sub-graph, it turns out that those 54 00:04:28,837 --> 00:04:33,295 neighbors are using all K. In this case three, all three of the register names. 55 00:04:33,295 --> 00:04:37,869 And so F where there is no register left over for F and we're going to have to 56 00:04:37,869 --> 00:04:42,965 actually spill it and store in memory. So, if optimistic coloring fails as it does in 57 00:04:42,965 --> 00:04:47,876 this example, then we spill f. So, what we're going to do is allocate the memory 58 00:04:47,876 --> 00:04:53,038 location for f and typically, what that means is that we'll allocate a position in 59 00:04:53,038 --> 00:04:58,654 the current stack frame. Let's call this address fa for the address of f. And then 60 00:04:58,839 --> 00:05:03,950 we're going to modify the control flow graph. We're going to change the code for 61 00:05:03,950 --> 00:05:09,000 that compiling. So, before each operation that reads f, we're going to insert a load 62 00:05:09,000 --> 00:05:13,989 that loads from that address to current value of f into a temporary name. Okay, 63 00:05:13,989 --> 00:05:18,546 that makes sense because if the value is out of memory, then if we have an 64 00:05:18,546 --> 00:05:23,842 operation that needs to actually use the value. We're going to have to load it from 65 00:05:23,842 --> 00:05:29,633 a memory first then to the register. And similarly after each operation that writes 66 00:05:29,633 --> 00:05:35,172 F, we're going to insert the store so we're going to save the current value of F 67 00:05:35,172 --> 00:05:41,257 into it's location in memory. So, here is the original code from which we 68 00:05:41,257 --> 00:05:45,657 constructed the registry interference graph and notice that there are few 69 00:05:45,657 --> 00:05:49,939 references to f in here and we just highlight them, alright. So, we have a 70 00:05:49,939 --> 00:05:54,758 couple of [inaudible], we have a right and so now, what are we going to do. So, here 71 00:05:54,758 --> 00:05:59,600 we have the use of F, the read of F in this statement and now we preceded that by 72 00:05:59,600 --> 00:06:04,262 a load. And notice that I've given a new name here. I called this F1. And, that's 73 00:06:04,262 --> 00:06:09,104 because the different uses of F in the control flow graph don't all have to have 74 00:06:09,104 --> 00:06:13,946 the same temporary name. And actually it would be a good idea to separate them so 75 00:06:13,946 --> 00:06:18,728 each distinct to use of F will get it's own name. So here we load the value of F 76 00:06:18,728 --> 00:06:23,814 and then it get to use in the statement. Here we have a right to f and so we store 77 00:06:23,814 --> 00:06:28,025 the current value of f and those argument to a different name, f2. So, that's 78 00:06:28,025 --> 00:06:32,517 temporary is computed here as going to be stored and it's called f2. And finally, 79 00:06:32,517 --> 00:06:38,881 the third use of f there's another load of f right here. Which is then used in this 80 00:06:39,186 --> 00:06:47,439 computation here of b. Okay. So, that is the systematic way to modify the code to 81 00:06:47,439 --> 00:06:54,845 use f in storage. And now, we have to recompute the aliveness of f. And so, what 82 00:06:54,845 --> 00:06:59,958 happens there. Well, here is the original aliveness information from which we 83 00:06:59,958 --> 00:07:05,398 computed the register interference graph, okay. And now notice that f is gone. We no 84 00:07:05,398 --> 00:07:10,710 longer use f in the programs so we can delete all the places where we mentioned 85 00:07:10,902 --> 00:07:16,022 that f was live and now we have the three new names, f1, f2, and f3. And we have to 86 00:07:16,022 --> 00:07:21,590 add in their aliveness information so it creates a new program points here where we 87 00:07:21,590 --> 00:07:26,836 inserted statements. And of course, where we have a load of the current value of f 88 00:07:27,021 --> 00:07:32,349 that value if live right before the use in the next statement. Here, we have the 89 00:07:32,349 --> 00:07:37,547 right of the current value of f and that's live right before the store and then 90 00:07:37,547 --> 00:07:42,940 here's another load of the current value of f which is live until the store, I'm 91 00:07:42,940 --> 00:07:47,547 sorry, until the use in the next statement. Okay. And so, now notice here 92 00:07:47,547 --> 00:07:53,245 that f used to be live in many, many, many places in the, in the code. And now not 93 00:07:53,245 --> 00:07:58,607 only is f or the, the different versions of f live in fewer places also we've 94 00:07:58,607 --> 00:08:04,104 distinguish them. So, it actually separate the different uses of f and so this will 95 00:08:04,104 --> 00:08:09,870 have their own nodes in their own set of interferences in the graph and they won't 96 00:08:09,870 --> 00:08:15,434 share them with the other users of f and that will actually also reduce the number 97 00:08:15,434 --> 00:08:21,190 of edges in the graph. To summarize the example on the previous slide, once we 98 00:08:21,190 --> 00:08:25,104 have decided that we are actually going to spill a temporary f, that means we're 99 00:08:25,104 --> 00:08:28,969 going to change the program where have loads and stores to the program and now 100 00:08:28,969 --> 00:08:32,883 we're g oing to have a different program and that's going to change our register 101 00:08:32,883 --> 00:08:36,894 allocation problems. We're going to have to recompute the aliveness of information, 102 00:08:36,894 --> 00:08:40,710 we're have to rebuild the restrain interference graph and then we're going to 103 00:08:40,710 --> 00:08:44,811 have to try again to color that block graph. Now, it turns out that this new 104 00:08:44,811 --> 00:08:49,401 aliveness information is almost the same as it was before. So, all the temporary 105 00:08:49,401 --> 00:08:54,165 names other than f are not much affected by the by the new statements that are 106 00:08:54,165 --> 00:08:58,639 added. There are a few program points where they might be live but I replaced 107 00:08:58,639 --> 00:09:03,644 they were alive before and they're still alive. And, F itself has changed fairly 108 00:09:03,644 --> 00:09:09,472 dramatically. It's like this information has changed really dramatically. Certainly 109 00:09:09,472 --> 00:09:15,230 the old name F is no longer used and so it's like this information goes away and 110 00:09:15,230 --> 00:09:21,200 then we've also split F into three in this case three different temporaries. One for 111 00:09:21,200 --> 00:09:26,673 each of the different uses of F in the control flow graph. And I noticed that 112 00:09:26,673 --> 00:09:32,217 each of these new uses of F or these new versions of F is live in a very, very 113 00:09:32,217 --> 00:00:06,380 small area so a load. In this video, we are going to continue our discussion of 114 00:00:06,380 --> 00:00:10,415 register allocation and this time, we're going to talk about what happens when we 115 00:00:10,415 --> 00:00:14,351 can't successfully color the graph. In which case, we have to do something known 116 00:00:14,351 --> 00:09:39,378 as filling. For a load instruction The thing that were loading the temporary that 117 00:09:39,378 --> 00:09:44,002 we're loading fi is live only between the load and the next instruction where it's 118 00:09:44,002 --> 00:09:49,324 used and similarly for a store. It's score of a temporary fi is live only between the 119 00:09:49,324 --> 00:09:53,865 store itself and the proceeding instruction. The one they created fi. And 120 00:09:53,865 --> 00:09:58,910 the effective is, is to greatly reduce the live range of the spilled variable. So, 121 00:09:58,910 --> 00:10:04,019 whatever name we decide to spill by adding the load and stores right next to the 122 00:10:04,019 --> 00:10:09,316 places where those values are used We dramatically reduced the live range and in 123 00:10:09,316 --> 00:10:14,929 addition, as I mentioned in the previous live by splitting the name f into multiple 124 00:10:14,929 --> 00:10:20,924 different name, we also you know, avoid sharing. Those different liv e ranges 125 00:10:20,924 --> 00:10:27,522 between the different versions of F. So because the live range of F is reduced by 126 00:10:27,522 --> 00:10:32,415 spilling. It has fewer interferences in the new program than it did in the old 127 00:10:32,415 --> 00:10:37,057 program. And so what that means the particulars in the rebuild [inaudible] 128 00:10:37,057 --> 00:10:41,888 interference graph, F will have fewer neighbors. Some of the neighbors that it 129 00:10:41,888 --> 00:10:47,232 had before have gone away because it just live in fewer places. So if we look at the 130 00:10:47,232 --> 00:10:52,604 new register interference graph, we can see that among all the different versions 131 00:10:52,604 --> 00:10:57,909 of F. Remember that F has been split into three temporaries in this graph. We see 132 00:10:57,909 --> 00:11:03,010 that they only interfere with D and C. Whereas, before f have several other 133 00:11:03,010 --> 00:11:09,814 neighbors in the graph. And now, in fact this new graph is three tolerable. Of 134 00:11:09,814 --> 00:11:14,705 course it might be the case that we can't just spill one name. We might have to have 135 00:11:14,705 --> 00:11:19,246 just spill several different temporaries before the coloring is found. And, the 136 00:11:19,246 --> 00:11:23,903 tricky part is to siding what to spill. So, this is the hard decision that has to 137 00:11:23,903 --> 00:11:28,794 be made during restore allocation. Now any choice is correct. It's only a question of 138 00:11:28,794 --> 00:11:33,393 performance so you know some choices of spilling will lead to better code than 139 00:11:33,393 --> 00:11:38,001 others but any choice of spilling is going to resolve in a correct program. And 140 00:11:38,001 --> 00:11:43,688 there's heuristics that people use to pick which temporaries to spill and here are a 141 00:11:43,688 --> 00:11:48,648 few or I think three of the most popular ones. One is to spill the temporaries and 142 00:11:48,648 --> 00:11:53,701 have the most conflicts. And the reason for that is that this is the temporary. 143 00:11:53,701 --> 00:11:58,684 The one thing that you can move into memory that will most affect the number of 144 00:11:58,684 --> 00:12:03,306 interferences in the graph. So, the idea is by possible spilling justice on 145 00:12:03,306 --> 00:12:08,469 variable. We'll remove enough edges from the graph that they becomes tolerable with 146 00:12:08,469 --> 00:12:13,527 the number of registers we have. Another possibility is a spilled temporaries that 147 00:12:13,527 --> 00:12:18,710 have few definitions and uses. And, here the idea is that by spilling those since 148 00:12:18,710 --> 00:12:24,124 they're not used very much, the number of lows in storage will have to add, will be 149 00:12:24,124 --> 00:12:29,274 relatively small and so if a variable [inaudible] man y places then the actual 150 00:12:29,274 --> 00:12:34,753 cost in terms of, additional instructions that are going to be executed to, spill it 151 00:12:34,753 --> 00:12:40,233 is relatively small. And another one and this is actually the one that I think that 152 00:12:40,233 --> 00:12:45,580 all the compilers implement is to avoid spilling an inner loops. So, if you have a 153 00:12:45,580 --> 00:12:50,661 choice between spilling a variable that's used within the. Innermost loop for the 154 00:12:50,661 --> 00:12:55,286 program and one that is used some place else. You probably preferred this that you 155 00:12:55,286 --> 00:12:59,530 spill the one that is used not in the innermost loop absolutely because again, 156 00:12:59,530 --> 00:13:04,318 that will result in fewer loads in stores. You really want to avoid adding additional 157 00:13:04,318 --> 00:13:11,220 instructions to your inner loop. To summarize this video, register allocation 158 00:13:11,220 --> 00:13:15,932 is one of the most important jobs that a compiler performs. And it's really, these 159 00:13:15,932 --> 00:13:20,238 days they must have an any kind of reasonable production compiler. And, the 160 00:13:20,238 --> 00:13:24,602 reason you need it is because the inter-media code just generally uses too 161 00:13:24,602 --> 00:13:28,733 many temporaries. We're allowed to be [inaudible] with inter-media code 162 00:13:28,733 --> 00:13:33,155 precisely because we have good register allocation algorithms. And the other 163 00:13:33,155 --> 00:13:37,344 reason, registers are just a very important resource in making good user 164 00:13:37,344 --> 00:13:41,650 registers. Having some procedure for making efficient use of the registers. 165 00:13:41,650 --> 00:13:47,246 Leads to much, much better code in the end, much more efficient code. Now. The 166 00:13:47,246 --> 00:13:51,880 register allocation algorithm I described here is really targeted at risk machine. 167 00:13:51,880 --> 00:13:57,137 So, for risk machine reduce instruction set computer what kind of machine. You can 168 00:13:57,137 --> 00:14:01,828 pretty much take the register allocation algorithm that I described and if any for 169 00:14:01,828 --> 00:14:06,802 those machines it would work out of the box. [inaudible] machines which stands for 170 00:14:06,802 --> 00:14:12,145 complex instructions for computers. Often have restrictions on how the register can 171 00:14:12,145 --> 00:14:16,907 be used. Certain operation can only work with certain registers. You may have 172 00:14:16,907 --> 00:14:21,920 register to different sizes that can only hold certain values. And so it becomes 173 00:14:21,920 --> 00:14:26,933 more complicated to register allocation for such machines. What people have done 174 00:14:26,933 --> 00:14:32,008 is to adapt the graph coloring procedure that I descri bed here. So, the basic idea 175 00:14:32,008 --> 00:14:36,394 is exactly the same and you would recognize those algorithms is being 176 00:14:36,394 --> 00:14:41,470 primarily the graph color algorithms that we discussed. There are just additional. 177 00:14:41,470 --> 00:14:46,118 Steps in those algorithms and places where the particular constraints are what 178 00:14:46,118 --> 00:14:48,590 registers can be used have to be observed.