1 00:00:02,580 --> 00:00:07,652 In this video, we are going to move beyond our discussion of Run-time Organization 2 00:00:07,652 --> 00:00:12,415 and begin talking about code generation And in this first you know, it was 3 00:00:12,415 --> 00:00:17,488 probably quite a long series of videos on code generation, we are gonna talk about 4 00:00:17,488 --> 00:00:25,180 the simplest model for code generation which is called a stack machine. So, in a 5 00:00:25,180 --> 00:00:30,520 stack machine, you might guess that the primary storage is some kind of a stack 6 00:00:30,520 --> 00:00:36,062 and you would be right. In fact, the only storage that the stack machine has is the 7 00:00:36,062 --> 00:00:41,536 stack And the way the stack machine works is that it executed an instruction, and 8 00:00:41,536 --> 00:00:46,875 all instruction have the form. There's some function of some arguments and they 9 00:00:46,875 --> 00:00:52,835 produce one result. And what that does is it'll pop in upper hands for the stack so 10 00:00:52,835 --> 00:00:59,192 the arguments a1 through an are stored at the top of the stack. It will then compute 11 00:00:59,192 --> 00:01:05,621 the function f using those operands and it will push the result r back on top of the 12 00:01:05,621 --> 00:01:11,747 stack. Okay, So, let's take a look at a simple example. Let's see how we would 13 00:01:11,747 --> 00:01:17,576 compute seven plus five using a stack machine. So, we would have our stack And 14 00:01:17,576 --> 00:01:22,239 initially the stack might have, already have some stuff on it but we don't care 15 00:01:22,239 --> 00:01:26,902 what that stuff is and so it will execute seven plus five. What we would do, well 16 00:01:26,902 --> 00:01:31,565 first we will have to get the seven and the five out of the stack so as we get 17 00:01:31,565 --> 00:01:36,287 pushed on stack and we'll see more about how that happens in a minute. And let's 18 00:01:36,287 --> 00:01:41,187 say that seven and five were both on the stack. And so now we wanted to compute the 19 00:01:41,187 --> 00:01:46,027 addition on seven and five so, addition takes two arguments so we would pop the 20 00:01:46,027 --> 00:01:52,385 two arguments off the stack. And we wined up with the five and the seven Pop-up the 21 00:01:52,385 --> 00:01:58,461 stack. We will perform the operation plus and then the result will get push back 22 00:01:58,461 --> 00:02:04,764 under the stack. So this would be good to twelve and then twelve will get push back 23 00:02:04,764 --> 00:02:10,615 on to our stack. Okay. And I noticed that I did indicate that there might be some 24 00:02:10,615 --> 00:02:15,530 other stuff on this stack already. Let me give that stuff a name. And let me talk 25 00:02:15,530 --> 00:02:20,567 about one very important property of the stack machine. So, those we have evaluated 26 00:02:20,567 --> 00:02:25,359 seve n+5, we round up in the situation where the results of that operation was on 27 00:02:25,359 --> 00:02:30,212 top of the stop of the stack. Okay, and the initial stack contents was unchanged. 28 00:02:30,212 --> 00:02:35,311 This stack, the stack that was below the arguments that we are interested in didn't 29 00:02:35,311 --> 00:02:40,470 get modified. Okay. So, we have survived through all the operations unchanged. And 30 00:02:40,470 --> 00:02:45,930 this is an important property of the stack machine. That we will exploit and the 31 00:02:45,930 --> 00:02:51,547 general to say what the general property is when you evaluate an expression the 32 00:02:51,547 --> 00:02:56,968 result of the expression will be on top of the stack and the contents of the stack 33 00:02:56,968 --> 00:03:03,515 prior to the beginning evaluation of the expression will be preserved. So, now 34 00:03:03,515 --> 00:03:08,746 let's take by how we could program a stack machine. So, let's have a language with 35 00:03:08,746 --> 00:03:13,665 just two instructions in it. We can push an engine run to the stack and then we 36 00:03:13,665 --> 00:03:18,833 have the operation add which will add the two integers on the top of the stack. And 37 00:03:18,833 --> 00:03:23,876 now, let's take a look at this program which pushes seven and then pushes five 38 00:03:23,876 --> 00:03:28,546 and then does an add. So, let's think about how this program would work. Okay, 39 00:03:28,546 --> 00:03:33,832 so we have our stack contents and now, and the first instruction is to push seven. So 40 00:03:33,832 --> 00:03:40,300 wined up with the seven on the stack, added to the stack and now we push five. 41 00:03:41,400 --> 00:03:47,054 Okay. And so the next step, we'll have five and seven on top of the stack then 42 00:03:47,054 --> 00:03:53,076 we'll perform the add and then we'll pop these two elements off the stack and add 43 00:03:53,076 --> 00:04:00,625 them and push the result back on. And we'll wind up with twelve on the stack and 44 00:04:00,625 --> 00:04:08,260 again the original stack contents are preserved. Now, what interesting property 45 00:04:08,260 --> 00:04:13,221 of stack machine code is that the location of the upper hands and result is not 46 00:04:13,221 --> 00:04:18,369 exquisitely stated in the instruction. And that's because these instructions always 47 00:04:18,369 --> 00:04:23,177 refer to the top of the stack. And this is in contrast were register machine or 48 00:04:23,177 --> 00:04:28,351 register instructions that explicitly name where they take their upper hands from and 49 00:04:28,351 --> 00:04:33,224 where they put the results. So for example you might be familiar from seeing some 50 00:04:33,224 --> 00:04:38,218 machine code or assembly code in the past or and add instruction by typically take 51 00:04:38,218 --> 00:04:42,610 three regis ters, two for the arguments [inaudible] two for the registered 52 00:04:42,610 --> 00:04:47,663 arguments are gonna be added together and one for the destination for the result 53 00:04:47,663 --> 00:04:52,956 where in the stack machine we just have. A single word add and no explicit naming of 54 00:04:52,956 --> 00:04:57,379 the arguments because it's fixed, where the arguments will come from. The 55 00:04:57,379 --> 00:05:02,538 arguments will always be popped from the stack and the result will always be placed 56 00:05:02,538 --> 00:05:06,964 back on top of the stack. And. The interesting property here is that it leads 57 00:05:06,964 --> 00:05:11,634 to more compact programs because we have to say less in the instructions the 58 00:05:11,634 --> 00:05:15,853 programs themselves are actually quite a bit smaller than register machine 59 00:05:15,853 --> 00:05:21,253 programs. And this is one of the reason, reasons that Java bytecode uses a stack 60 00:05:21,253 --> 00:05:26,915 evaluation model because it leads to more compact programs and especially in the 61 00:05:26,915 --> 00:05:32,437 early days of Java when it was very expensive to ship these programs around 62 00:05:32,437 --> 00:05:38,100 the Internet to download them, having very small compact code was a good property. 63 00:05:38,820 --> 00:05:43,330 And by we might wonder why would we prefer register machine and the answer is that 64 00:05:43,330 --> 00:05:47,678 register machine code is generally faster because we can place the data exactly 65 00:05:47,678 --> 00:05:52,243 where we wanted to be. We will generally have fewer, you know, immediate operations 66 00:05:52,243 --> 00:05:56,319 and less manipulation of the stack, pushing and popping stuff to get to the 67 00:05:56,319 --> 00:06:00,830 data that we want. And then it turns out that there isn't inter-media point between 68 00:06:00,830 --> 00:06:04,960 a pure stack machine and a pure register machine, that's interesting. This is 69 00:06:04,960 --> 00:06:09,253 called an N register stack machine. And conceptually, the idea of the N register 70 00:06:09,253 --> 00:06:15,082 stack machine is to keep the. Top end locations of the stack in registers. And 71 00:06:15,082 --> 00:06:19,941 the particular variant of the un-resourced stack machine that we particularly 72 00:06:19,941 --> 00:06:24,925 interested in is the one register stack machine because the terms that you get 73 00:06:24,925 --> 00:06:29,910 widely benefit by even having a single register that's dedicated to the top of 74 00:06:29,910 --> 00:06:35,021 the stack. This register is called the accumulator so the dedicated registry here 75 00:06:35,021 --> 00:06:39,943 is called the accumulator. It's called that because intuitively it accumulates 76 00:06:39,943 --> 00:06:45,371 the results of operations and then all the other data lives on the stack. So, what is 77 00:06:45,371 --> 00:06:51,118 the advantage of a one register stack machine? Well, let's think about the add 78 00:06:51,118 --> 00:06:56,641 instruction and how it works in a pure stack machine? So, in the pure stack 79 00:06:56,641 --> 00:07:03,209 machine, what is the add instruction going to do it's going to pop two arguments from 80 00:07:03,209 --> 00:07:09,106 the stacks, a five and seven. And it's going to add them and then it's gonna put 81 00:07:09,106 --> 00:07:14,925 the result back onto the stack. And let's just name the rest of the stack contents 82 00:07:14,925 --> 00:07:20,217 there. And that requires three memory operations. After load, two arguments and 83 00:07:20,217 --> 00:07:24,979 then store one result. But in the one razor stack machine, the add operation 84 00:07:24,979 --> 00:07:30,260 actually does a lot of its work out of the one register. So, the one of the arguments 85 00:07:30,260 --> 00:07:35,135 is already stored in the register because that's the conceptually the top of the, of 86 00:07:35,135 --> 00:07:39,836 the stack. And, the result will be pushed back on the top of the stack which again 87 00:07:39,836 --> 00:07:44,711 is just the accumulated register. So here, one of the arguments in the right are both 88 00:07:44,711 --> 00:07:49,237 taking from registers and there's only one memory reference to get the second 89 00:07:49,237 --> 00:07:54,633 argument from the portion of the stack that's stored in the memory. So in 90 00:07:54,633 --> 00:07:59,399 general, let's think about how we would evaluate and arbitrary expression using a 91 00:07:59,399 --> 00:08:04,106 stack machine. So now this isn't I should say, you know, just stack machine called 92 00:08:04,106 --> 00:08:08,695 like we're looking at it before. This is not just a sequence of bytecode level 93 00:08:08,695 --> 00:08:13,108 operations, this is actually a full expression as you might find in Kuhl so 94 00:08:13,108 --> 00:08:17,987 there are other complex expressions nested inside of some operation. All right. And 95 00:08:17,987 --> 00:08:22,435 so, forget the operation that takes N arguments and those arguments are 96 00:08:22,435 --> 00:08:27,572 expression that themselves needs to be evaluated so here's a general strategy for 97 00:08:27,572 --> 00:08:32,396 doing that with the stack machines. So, for each of the sub-expression, each of 98 00:08:32,396 --> 00:08:37,596 the arguments in order we're going to evaluate it recursively using the same 99 00:08:37,596 --> 00:08:42,984 stack machine strategy and that will end up putting the result when we evaluate EI, 100 00:08:42,984 --> 00:08:48,142 recursively the results will be in the accumulator. And so the results is in the 101 00:08:48,142 --> 00:08:53,421 accumulator, alright. And then we're going to push that results onto the memory 102 00:08:53,421 --> 00:08:58,158 stack. So we'r e going to take that results and we're gonna free up the 103 00:08:58,158 --> 00:09:03,572 accumulator and save it on the stack, the portion of stack that's in memory, okay. 104 00:09:03,572 --> 00:09:08,038 So we do this evaluating the sub-expressions for the first and -one 105 00:09:08,038 --> 00:09:13,046 arguments. So everything except the last one, okay. We're gonna use the same 106 00:09:13,046 --> 00:09:19,858 strategy, for the last one, for en. We just evaluate. We don't push the result on 107 00:09:19,858 --> 00:09:24,924 the stack. That just means that the result is left in the accumulator okay so now we 108 00:09:24,924 --> 00:09:29,446 have one of the arguments of the accumulator. The last one we evaluated and 109 00:09:29,446 --> 00:09:34,512 the other in line as one are o the top of the portion of the stack that's in memory. 110 00:09:34,512 --> 00:09:39,457 So that what we all have to do is we pop in -one values from the stack and combine 111 00:09:39,457 --> 00:09:44,462 any compute up using the -one values plus the value of the accumulator and we store 112 00:09:44,462 --> 00:09:49,105 the result back into the accumulator, okay. So that's the general strategy for 113 00:09:49,105 --> 00:09:54,765 evaluating an expression using a stack machine. So let's do this now for a simple 114 00:09:54,765 --> 00:09:59,970 example. Let's take our same example that we've been using and let's evaluate the 115 00:09:59,970 --> 00:10:04,983 expression seven plus five. So, how we're gonna do that? Well, we're evaluating a 116 00:10:04,983 --> 00:10:09,739 plus expression and that takes two arguments, two expression as the way to 117 00:10:09,739 --> 00:10:14,366 evaluate each of those. So first we evaluate the expression seven. Let me 118 00:10:14,366 --> 00:10:20,140 actually, let me draw our stack here. Okay, so we have our initial content to 119 00:10:20,140 --> 00:10:24,304 the stack, we have our initial accumulator. And so now we're evaluating 120 00:10:24,304 --> 00:10:29,004 seven, okay? And of course a constant loose evaluate to itself and the result is 121 00:10:29,004 --> 00:10:33,763 toward the accumulator, okay? So that's the first step after evaluating seven. And 122 00:10:33,763 --> 00:10:38,344 now because that's the first argument to plus, it has to get pushed on to the 123 00:10:38,344 --> 00:10:44,302 stack, the portion of the stack in main memory. So. Now, we have a situation that 124 00:10:44,302 --> 00:10:50,354 looks like this. All right, in the course to seven is still in the accumulator but 125 00:10:50,354 --> 00:10:55,024 we're now about to override it, we're not gonna use that value again. Because the 126 00:10:55,024 --> 00:10:59,870 next thing we're gonna do is evaluate the second argument to plus and that happens 127 00:10:59,870 --> 00:11:04,073 to be in this case also a constant expression five and so that will get 128 00:11:04,073 --> 00:11:08,334 evaluated and then stored in the accumulator. Okay, so I will override the 129 00:11:08,334 --> 00:11:12,794 seven. This will be five there, all right? And now, we have evaluated both arguments. 130 00:11:12,794 --> 00:11:17,042 Okay, remember in the case of just having two arguments. The first argument gets 131 00:11:17,042 --> 00:11:21,134 evaluated and saved on the stack so it doesn't, so we don't lose the value when 132 00:11:21,134 --> 00:11:25,434 we evaluate the second argument. And the second argument we uses is the last one we 133 00:11:25,434 --> 00:11:31,730 can just leave in the accumulator And that way actually evaluates the plus. Okay, so 134 00:11:31,730 --> 00:11:41,188 we do the accumulator gets the accumulator plus the top of the memory stack. So in 135 00:11:41,188 --> 00:11:48,871 this case, that results in adding seven and five. And we line up and of course we 136 00:11:48,871 --> 00:11:55,141 pop the argument from the memory stack, right. So we have just the original 137 00:11:55,141 --> 00:12:03,002 contents there and now the value twelve in the accumulator. So, as I think you would 138 00:12:03,002 --> 00:12:08,648 see from the example, the invariant that we're gonna maintain with the stack 139 00:12:08,648 --> 00:12:14,293 machine is that after we evaluate an expression e, the accumulator holds the 140 00:12:14,293 --> 00:12:20,236 value of e so the result of evaluating [inaudible] accumulator and the stack is 141 00:12:20,236 --> 00:12:26,252 unchanged. And so the stack, the memory portion of the stack is whatever it was 142 00:12:26,252 --> 00:12:32,044 before we start of evaluating e. And this is a very, very important property, 143 00:12:32,044 --> 00:12:42,071 expression evaluation preserves the stack. So, now let's look at a more elaborated 144 00:12:42,071 --> 00:12:48,862 example, just slightly more elaborate, three+7+5. And the interesting thing about 145 00:12:48,862 --> 00:12:53,609 this example. Is that now one of the arguments to the other plus is itself a 146 00:12:53,609 --> 00:12:57,857 compound expression. So it would have to be, that would have to be evaluated 147 00:12:57,857 --> 00:13:02,276 recursively as part of evaluating the entire expression so let's see how this 148 00:13:02,276 --> 00:13:06,978 works. So the first thing that's going to happen or evaluating the outer plus, we're 149 00:13:06,978 --> 00:13:11,567 gonna evaluate the first argument to that plus that's just the constant three so 150 00:13:11,567 --> 00:13:16,731 we're gonna load it into the accumulator. And that's the result of evaluating three. 151 00:13:16,731 --> 00:13:22,481 And now because it's the first argument to the plus, we have to save it before we can 152 00:13:22,481 --> 00:13:27,894 get around to evaluating the addition itself. So that result is pushed on to the 153 00:13:27,894 --> 00:13:34,098 stack. And now we're g onna evaluate the second argument to the outer plus and that 154 00:13:34,098 --> 00:13:38,666 itself has two arguments. And the first argument to that, to the inner plus is 155 00:13:38,666 --> 00:13:43,347 seven. And so that winds up getting stored in the accumulator, that's the result of 156 00:13:43,347 --> 00:13:47,800 evaluating seven. And then because the inner plus has two arguments, we have to 157 00:13:47,800 --> 00:13:52,425 evaluate the second, evaluate the second argument to the inner plus, the seven has 158 00:13:52,425 --> 00:13:56,935 to get saved to the stack. So now, the stack has seven three and whenever it had 159 00:13:56,935 --> 00:14:04,679 before we start it. Next, we're gonna evaluate the second argument to the inner 160 00:14:04,679 --> 00:14:09,800 plus And so evaluating a constant five will result in five being loaded in the 161 00:14:09,800 --> 00:14:14,922 accumulator and now, we have evaluated all the arguments to the inner plus, okay. And 162 00:14:14,922 --> 00:14:20,043 so we know from our stack discipline that the last arguments is in the accumulator 163 00:14:20,043 --> 00:14:25,231 and the first argument will be on top of the stack. So the next thing that will 164 00:14:25,231 --> 00:14:30,626 happen is that we'll pop that second argument from the stack added to the 165 00:14:30,626 --> 00:14:36,386 accumulator and store back into the accumulator and so now we have the results 166 00:14:36,386 --> 00:14:42,219 of the inner plus in the accumulator. We also have the pop, the seven from the 167 00:14:42,219 --> 00:14:47,979 stack, okay and finally now we've evaluated the second argument to the outer 168 00:14:47,979 --> 00:14:52,950 plus. So now we can perform the outer edition. And what is that involve that 169 00:14:52,950 --> 00:14:57,628 takes the stack contents then adds it to the value that is currently on the top of 170 00:14:57,628 --> 00:15:02,362 the stack which is the value three which is what we saved a long time ago now to, 171 00:15:02,362 --> 00:15:07,033 to remember it from what it was to do the other addition and we wind up. After we 172 00:15:07,033 --> 00:15:11,945 pop the stack with fifteen in the accumulator, that's the results of the 173 00:15:11,945 --> 00:15:17,265 entire expression, and notice it's the same stack that we started with. Okay? So 174 00:15:17,265 --> 00:15:22,449 evaluating this entire expression, resulted in the, result in any accumulator 175 00:15:22,449 --> 00:15:28,111 and the stack being unchanged And if you looked at that the sub-expression, you can 176 00:15:28,111 --> 00:15:33,295 see that the same things happened. So let's take a look at the evaluation of 177 00:15:33,295 --> 00:15:39,394 seven plus five. So where that take place that started here. Okay. Started at this 178 00:15:39,394 --> 00:15:44,754 instruction. And, it lasted down to here and you can see that the evaluation of 179 00:15:44,754 --> 00:15:49,715 seven + five which encompasses these five expressions resulted in twelve being put 180 00:15:49,715 --> 00:15:54,434 on top of the stack, that's the result of seven + five and it didn't affect the 181 00:15:54,434 --> 00:15:59,455 contents I'm sorry. It resulted in twelve being placed in the accumulator and it 182 00:15:59,455 --> 00:16:04,355 will left the stack unchanged to where it was when the evaluation of seven plus five 183 00:16:04,355 --> 00:16:09,377 began. So here is where it began and the value we had saved three was on the top of 184 00:16:09,377 --> 00:16:13,975 the stack and when we're done evaluating seven plus five indeed again the value 185 00:16:13,975 --> 00:16:19,580 three and. All the other stuff that was there before are still on the stack.