1 00:00:03,600 --> 00:00:07,922 In the last couple of videos we have talked about code generation for simple 2 00:00:07,922 --> 00:00:12,470 programming language and I mentioned at the end of the last video that realistic 3 00:00:12,470 --> 00:00:16,961 compilers do things a bit differently and in particular they do a better job of 4 00:00:16,961 --> 00:00:21,284 keeping values and registers and of managing the temporaries that have to be 5 00:00:21,284 --> 00:00:25,832 stored in the activation record. We're actually going to talk about both of those 6 00:00:25,832 --> 00:00:30,323 problems. In this particular video, we're only going to talk about the second one 7 00:00:30,323 --> 00:00:34,927 and so we're going to be covering a better ways for compilers to manage temporary 8 00:00:34,927 --> 00:00:41,401 values. So the biggest idea which we've already seen is to keep temporaries in the 9 00:00:41,401 --> 00:00:45,354 activation record. Now, this is not as efficient as keeping temporaries in 10 00:00:45,354 --> 00:00:49,253 registers but that's the subject of a future video, we're not going to talk 11 00:00:49,253 --> 00:00:53,640 about that today. What we're going to talk about is improving the language we manage 12 00:00:53,640 --> 00:00:58,026 temporaries that happened to be in the activation record for whatever reasons. So 13 00:00:58,026 --> 00:01:02,521 why, it doesn't matter why we want them to be into activation record, but given that 14 00:01:02,521 --> 00:01:07,016 it's there, that's the most efficient code that we can generate And, the improvement 15 00:01:07,016 --> 00:01:12,570 that we're going to make Is have the co-generator assign a fixed location In 16 00:01:12,570 --> 00:01:17,316 the activation record for each temporaries. We're going to pre-allocate 17 00:01:17,316 --> 00:01:22,729 memory or a spot in the activation record for each temporary and then we will be 18 00:01:22,729 --> 00:01:28,143 able to save and restore the temporary without having to do the stack pointer 19 00:01:28,344 --> 00:01:33,383 manipulations. So, let's take a look at the [inaudible] program for a simple 20 00:01:33,383 --> 00:01:38,206 programming language. Here is the Fibonacci function again and let me change 21 00:01:38,206 --> 00:01:42,967 colors to something that says more contrast and let's think about how many 22 00:01:42,967 --> 00:01:47,851 temporaries we need to evaluate this functions. So, this function body when it 23 00:01:47,851 --> 00:01:52,490 executes we'll need a certain number of temporaries and if we know how many 24 00:01:52,490 --> 00:01:57,618 temporaries that needs in advance then we could allocate the space for those in the 25 00:01:57,618 --> 00:02:02,502 activation record rather having to do push and pop, pushing and popping from the 26 00:02:02,502 --> 00:02:07,006 stack at runtime. So, let's take a look and if then else is going t o involve a 27 00:02:07,006 --> 00:02:11,142 temporary because it always do this predicate comparison here, we're going to 28 00:02:11,142 --> 00:02:15,894 have to evaluate the, the first argument to the predicate and then save the result 29 00:02:15,894 --> 00:02:20,255 of that while we evaluate the second argument to the predicate. So this one 30 00:02:20,255 --> 00:02:24,503 involve one temporary, we'll need one temporary for that predicate. Similarly 31 00:02:24,503 --> 00:02:28,584 for this predicate, to evaluate it since it's a two argument operation in 32 00:02:28,584 --> 00:02:33,143 comparison, we'll also need one temporary for that. 1010. There's this expression 33 00:02:33,143 --> 00:02:37,704 over here which is kind of complicated. How many temporaries will we need for 34 00:02:37,704 --> 00:02:42,569 these? Well, remember how this works. So, evaluate the first expression and then we 35 00:02:42,569 --> 00:02:47,312 save the results of that so this will require one temporary for the result of 36 00:02:47,312 --> 00:02:52,055 the called fib going to have to be saved and only evaluate the plus And while we 37 00:02:52,055 --> 00:02:57,224 are evaluating the call, the fib though is actually, before we evaluate to call the 38 00:02:57,224 --> 00:03:02,150 fib, we have to evaluate the argument of fib and that involve the subtractions. We 39 00:03:02,150 --> 00:03:08,413 also need one temporary here for the subtraction. Okay And now we have about 40 00:03:08,413 --> 00:03:18,020 the second side of the, this edition here. Well this also involves a subtraction. 41 00:03:18,020 --> 00:03:23,741 Okay So, we got to have one temporary here to hold on to the value x while we're 42 00:03:23,741 --> 00:03:28,961 evaluating the minus to compute the value of the argument before we call 43 00:03:28,961 --> 00:03:33,952 [inaudible]. Okay? So how many temporaries do we need in total? While we need one 44 00:03:33,952 --> 00:03:38,700 here for the predicate, but notice that once the predicate is decided, once we 45 00:03:38,700 --> 00:03:43,511 know the answer to whether this predicate is true or false, we don't need that 46 00:03:43,511 --> 00:03:48,136 temporary anymore. So in fact, that temporary can be reclaimed; we don't need 47 00:03:48,136 --> 00:03:53,070 the space for that temporary anymore by the time we get to the false branch. And 48 00:03:53,070 --> 00:03:58,128 again, once this predicate is evaluated, we don't need the space for that temporary 49 00:03:58,128 --> 00:04:02,933 anymore, okay? So now we're down to the plus. The first thing that happens is we 50 00:04:02,933 --> 00:04:07,856 evaluate the argument to this first call the fib. Once that's evaluated, we don't 51 00:04:07,856 --> 00:04:13,333 need the temporary for it anymore. Now the results of fib has to be saved somewhere 52 00:04:13,333 --> 00:04:18,071 while we do the plus, okay? And then we'r e going to have to evaluate the argument 53 00:04:18,071 --> 00:04:23,301 to the second call of fib and then notice that this happens while we still need this 54 00:04:23,301 --> 00:04:28,337 temporary here so in fact, we need both of these temporaries at the same time. Okay 55 00:04:28,337 --> 00:04:32,911 because while we're evaluating this argument, the second call of fib, we still 56 00:04:32,911 --> 00:04:37,427 need to be holding on to the first argument to the plus. And so in fact this 57 00:04:37,427 --> 00:04:43,278 particular function can be evaluated with just two temporaries. So all the space we 58 00:04:43,278 --> 00:04:53,402 need to compute the value of this function body. So in general, we can define a 59 00:04:53,402 --> 00:05:04,480 function nt of e that computes a number of temporaries needed to evaluate e1 + e2. 60 00:05:04,480 --> 00:05:09,167 So, that's going to need at least as many temporaries as e1. Okay, so if we need a 61 00:05:09,167 --> 00:05:13,794 number of temporary's k to evaluate e1, let's have at least k temporaries to 62 00:05:13,794 --> 00:05:18,177 evaluate the whole expression And then, we'll also need at least as many 63 00:05:18,177 --> 00:05:22,865 temporaries as it's needed to evaluate the two+1 because we have to hold on to the 64 00:05:22,865 --> 00:05:27,918 value of e2 while we are evaluating so we have to hold on the value of e1 while 65 00:05:27,918 --> 00:05:33,660 we're evaluating the two. Okay And it's going to be the maximum. Over these two so 66 00:05:33,660 --> 00:05:39,058 it'll be the maximum number with between the maximum number of temporaries need to 67 00:05:39,058 --> 00:05:44,260 evaluate a one and one + the number of temporaries to evaluate two. That would be 68 00:05:44,260 --> 00:05:49,203 the total number of temporaries, the minimum number of temporaries needed to 69 00:05:49,203 --> 00:05:54,176 evaluate e1 + e2 And the reason is a max instead of a sum. Is that once we've 70 00:05:54,176 --> 00:05:59,775 evaluate e1 we don't need any of the space that was used to evaluate e1 anymore. All 71 00:05:59,775 --> 00:06:05,174 those temporaries are done. All we need is the answer. We don't need the immediate 72 00:06:05,174 --> 00:06:10,107 results and that means that the temporaries that were used to evaluate e1 73 00:06:10,107 --> 00:06:16,915 can be reused to evaluate e2. So, generalizing from that one example, here 74 00:06:16,915 --> 00:06:21,848 is the system of equations that subscribes the number of temporaries needed to 75 00:06:21,848 --> 00:06:26,718 evaluate every kind of expression in our little language. So, let's take a look. 76 00:06:26,718 --> 00:06:31,714 So, we already talked about e1+e2 is just the max of over the number or temporaries 77 00:06:31,714 --> 00:06:36,273 to value of e1 and one + number of temporaries to value of e2. So, e1-e2 is 78 00:06:36,273 --> 00:06:40,956 exactly the same thing because the same structure is a different computational 79 00:06:40,956 --> 00:06:45,827 operation but is a binary operation and we have to save the value of e1 while 80 00:06:45,827 --> 00:06:52,189 evaluated e2. So, it's the same formula. [inaudible] Now for if and else well what 81 00:06:52,189 --> 00:06:59,053 do we need? We need one, I'm sorry we need, it's going to max again. It's going 82 00:06:59,053 --> 00:07:05,341 to be max over some number of different quantities. How many temporaries might we 83 00:07:05,341 --> 00:07:09,434 need? Well, we might need as many temporaries or as needed to evaluate the 84 00:07:09,434 --> 00:07:14,031 value of e1 and we certainly need at least as many, alright. So, if you want to take 85 00:07:14,031 --> 00:07:18,460 a certain number of temporaries, the whole f and l is going to require at least as 86 00:07:18,460 --> 00:07:22,721 many temporaries. Now of course, once e1 is done evaluating, we don't need its 87 00:07:22,721 --> 00:07:26,589 temporaries anymore. And, and we can evaluate e2, okay. And while we are 88 00:07:26,589 --> 00:07:30,874 evaluating e2, we have to hold on. To the results of e1, that's where the one plus 89 00:07:30,874 --> 00:07:34,966 comes from. So, to that, while we're evaluating e2, we need one plus the number 90 00:07:34,966 --> 00:07:39,110 of temporaries to evaluating two to hold all the temporaries of the computation. 91 00:07:39,110 --> 00:07:43,450 And then once the predicate is done, we don't need any of those temporaries 92 00:07:43,450 --> 00:07:48,253 anymore at all ad we're going to evaluate either e3 or e4. And so then, we just need 93 00:07:48,253 --> 00:07:53,114 however many temporaries each of those requires and whatever the maximum is over 94 00:07:53,114 --> 00:07:57,975 these four quantities, that's the minimum number of temporaries we can get away with 95 00:07:57,975 --> 00:08:02,754 to evaluate the entire if then else. Let's take a look at a function call. So that 96 00:08:02,754 --> 00:08:08,373 the space needed for the function call is number of temporaries, the max over the 97 00:08:08,373 --> 00:08:14,060 number of temporaries to evaluate anyone of the arguments and this is actually an 98 00:08:14,060 --> 00:08:19,511 interesting case because notice. That we don't need, we don't have anywhere in this 99 00:08:19,511 --> 00:08:24,875 formula space for the results for the e1 through en Of course once we've evaluated 100 00:08:24,875 --> 00:08:30,175 the e1 then we need to save it somewhere and so you would think that we might see 101 00:08:30,175 --> 00:08:35,281 some numbers in here representing the temporary space needed to hold on to the 102 00:08:35,281 --> 00:08:39,999 results of the evaluating these expressions. And the reason that we don't 103 00:08:39,999 --> 00:08:44,850 have that in here is that. Even though those values are saved, they are indeed 104 00:08:44,850 --> 00:08:49,638 saved; they're not saved in the current activation record The space where the 105 00:08:49,638 --> 00:08:54,674 results of e1 and the results of all, any of the arguments. Yeah, again, is saved in 106 00:08:54,674 --> 00:08:59,524 the new activation record that we're building And so, the space for the, the 107 00:08:59,524 --> 00:09:04,622 results of e1 through en is that those values are stored in new activation record 108 00:09:04,622 --> 00:09:09,472 and that storage of current activation record and we're trying to compute the 109 00:09:09,472 --> 00:09:14,763 number of temporaries needed to evaluate inside of the current activation And then 110 00:09:14,763 --> 00:09:19,291 for integer, that doesn't take any space at all to require any temporaries I mean. 111 00:09:19,291 --> 00:09:23,930 So there's zero temporaries required for that and also for a variable reference so 112 00:09:23,930 --> 00:09:29,664 it requires no temporaries. So now let's go through our example and work out 113 00:09:29,664 --> 00:09:35,551 systematically using the equations. How many temporaries we will need? Okay? So, 114 00:09:35,791 --> 00:09:42,844 here for this if then else, remember it was going to be the max over the number 115 00:09:42,844 --> 00:09:49,656 required to evaluate e1, well that zero. One + the number to evaluate e2 which is 116 00:09:49,656 --> 00:09:56,548 the second expression in the predicate so that would be one, because the number one 117 00:09:56,548 --> 00:10:03,521 requires zero temporaries and the one, the we have one hold on to x, all right? And 118 00:10:03,521 --> 00:10:10,203 then max over the branches. So, to evaluate zero requires Zero temporaries 119 00:10:10,203 --> 00:10:15,957 and now. We have to compute. The number required here. Okay so once again to 120 00:10:15,957 --> 00:10:22,593 evaluate the first expression if and else requires zero temporaries to evaluate the 121 00:10:22,593 --> 00:10:28,596 second one we require one. One + the number required, one + zero to evaluate 122 00:10:28,596 --> 00:10:35,232 that constant we got zero temporaries and now for the last expression how many will 123 00:10:35,232 --> 00:10:42,654 this one will require. Well this is going to require zero for this guy. One for the 124 00:10:42,654 --> 00:10:49,421 second argument so to evaluate fib is going to require one temporary, okay and 125 00:10:49,421 --> 00:10:56,730 then it's going to be one plus over here. We have to hold on to the results there. 126 00:10:57,000 --> 00:11:03,846 The value of x - two so how much that going to require? That is going to require 127 00:11:03,846 --> 00:11:11,053 the max of zero and one + zero okay so this would be one alright so we have over 128 00:11:11,053 --> 00:11:18,784 here we have one + one = two okay and now we're taking the max over two and one. So 129 00:11:18,784 --> 00:11:23,817 that's two, okay? And this is the last expression in the, our if and else. So 130 00:11:23,817 --> 00:11:28,783 clearly, this if then else here will require two temporaries okay? Because the 131 00:11:28,783 --> 00:11:34,361 max over the number required for either part of the predicate, the then branch and 132 00:11:34,361 --> 00:11:40,368 the else branch And now, this whole expression. Requires two temporaries and 133 00:11:40,368 --> 00:11:47,923 that'll be the max of the four components of the outer if then else And so then for, 134 00:11:47,923 --> 00:11:56,379 for the entire expression we get two temporaries. Once it computed the number 135 00:11:56,379 --> 00:12:01,415 of temporaries required to evaluate the function value, we can add that much space 136 00:12:01,415 --> 00:12:06,020 to the activation record. So, now our activation record is going to require two 137 00:12:06,020 --> 00:12:10,258 + n + nt (e) elements And so, the two of course are for the return address for the 138 00:12:10,258 --> 00:12:15,293 frame pointer. The n is for the n argument of the function And then, the rest of it 139 00:12:15,293 --> 00:12:21,205 is just the space required for the temporaries And now we can talk about how 140 00:12:21,205 --> 00:12:26,553 we're going to layout the activation record. We'll leave the first part of it 141 00:12:26,553 --> 00:12:32,035 the same, so everything up to the return address is laid out just before. First the 142 00:12:32,035 --> 00:12:37,183 color string pointer then the and arguments in reverse order, and then the 143 00:12:37,183 --> 00:12:42,665 return address. And then after the return address come the and locations or the 144 00:12:42,665 --> 00:12:48,804 nt(e), excuse me, locations for the temporaries. Now, that we know how many 145 00:12:48,804 --> 00:12:53,860 temporaries or intermediate values we need to evaluate a function and we also know 146 00:12:53,860 --> 00:12:58,734 where those intermediate value is going to be stored in activation record. The last 147 00:12:58,734 --> 00:13:03,669 thing we need to know in order to code generation is how many temporaries are in 148 00:13:03,669 --> 00:13:09,358 use at each point in the program. Change colors here and so the way we're going to 149 00:13:09,358 --> 00:13:13,856 do that is we're going to add a new argument to co-generation which is the 150 00:13:13,856 --> 00:13:18,474 position of the next available temporary. So as temporaries gets used up, this 151 00:13:18,474 --> 00:13:23,092 argument, the co-generation will change while other expressions to save their 152 00:13:23,092 --> 00:13:28,190 values and save places without stepping on temporaries that are already having saved 153 00:13:28,190 --> 00:13:32,868 by all other expressions. And as you'll see in a, in a moment here when we do an 154 00:13:32,868 --> 00:13:36,882 example, the temporary area of the activation r ecord is going to be used 155 00:13:36,882 --> 00:13:40,674 like a small fixed size stack. Essentially, we're going to have the same 156 00:13:40,674 --> 00:13:45,246 stack discipline that we had before only all the computation on the stack pointer, 157 00:13:45,246 --> 00:13:50,153 all the discussion, all the computation of what all sets to use has already been done 158 00:13:50,153 --> 00:13:55,004 by the compiler. So, what we used to do by pushing and popping element from the stack 159 00:13:55,004 --> 00:13:58,851 in the generated code allow that computation has been moved into the 160 00:13:58,851 --> 00:14:03,943 compiler and all that happens now is a bunch of stores and load. To fix off that 161 00:14:04,229 --> 00:14:09,765 from the frame pointer So let's take a look at how this works. Here's the code 162 00:14:09,765 --> 00:14:14,571 that we had for e1 + e2 under the old scheme where we didn't have a separate 163 00:14:14,571 --> 00:14:19,133 area in the activation records for temporaries. So we would generate a code 164 00:14:19,133 --> 00:14:24,243 for e1, and then we would save the results of e1 on the stack, and that would be done 165 00:14:24,243 --> 00:14:29,170 by saving the value of the accumulator under the stack and then we would have to 166 00:14:29,170 --> 00:14:34,280 adjust the stack pointer And then after we had evaluated the two, then we would load 167 00:14:34,462 --> 00:14:39,356 the results of e1 back into a temporary register, we could do the add And then we 168 00:14:39,356 --> 00:14:44,471 could pop the value off of the stack, the intermediate value off of the stack Down 169 00:14:44,471 --> 00:14:50,304 to the new scheme. Co-generations going to take a second argument saying what is the 170 00:14:50,304 --> 00:14:55,817 position of the next available temporary so what is the position of the next unused 171 00:14:55,817 --> 00:15:01,329 temporary inside of the activation record and so now we generate code for e1 and we 172 00:15:01,329 --> 00:15:06,645 pass along the argument okay because e1 may itself have some temporaries that it 173 00:15:06,645 --> 00:15:11,758 needs to store And, and then after you [inaudible] to evaluating, now we just do 174 00:15:11,758 --> 00:15:16,853 a direct store into, into the activation record at all set empty from the frame 175 00:15:16,853 --> 00:15:21,820 pointer And so now as we have to do in store, we have to save e1 in the 176 00:15:21,820 --> 00:15:27,174 activation record so we have it for later on but we have to do any manipulation of 177 00:15:27,174 --> 00:15:31,689 the stacks. So, we could place two instructions here by one And then we 178 00:15:31,689 --> 00:15:38,028 generate code for e2 but now. We just save the temporary value at position at, at all 179 00:15:38,028 --> 00:15:43,959 set empty from the frame pointer so the next available temporary would be of 180 00:15:43,959 --> 00:15:49,504 address empty o r offset, excuse me, nt+4 And then after each was evaluating, now we 181 00:15:49,504 --> 00:15:54,894 have to load the value of e1 back into a temporary and again that was all set NT 182 00:15:54,894 --> 00:15:59,963 from the frame pointer of the current activation record and then we can do the 183 00:15:59,963 --> 00:16:04,455 add and once again we saved the manipulation of the stack pointers. So 184 00:16:04,455 --> 00:16:09,075 this code sequence here is two instructions shorter than the one we had 185 00:16:09,075 --> 00:16:12,540 before and this actually substantially more efficient.