1 00:00:03,360 --> 00:00:07,771 In the next two videos, we're going to be looking at code generation for a language 2 00:00:07,771 --> 00:00:12,293 that's higher level than a simple stack machine language we've been talking about 3 00:00:12,293 --> 00:00:21,057 so far. So here's a language with integers and integer operation and this was the 4 00:00:21,057 --> 00:00:26,163 grammar. So a program consists of a list of declarations, and what's a declaration? 5 00:00:26,163 --> 00:00:31,288 A declaration is a function definition so it has a function name, the function takes 6 00:00:31,288 --> 00:00:35,620 a list of arguments which are just identifiers, and the function has an 7 00:00:35,620 --> 00:00:40,379 expression, which is the body of the function And what in function bodies look 8 00:00:40,379 --> 00:00:45,565 like, well they expressions can be integers identifiers if then else, and the 9 00:00:45,565 --> 00:00:50,568 only predicate that we're going to allow is an equality test between integers and 10 00:00:50,568 --> 00:00:56,800 then sums of expressions, differences of expressions, and function calls. Now we'll 11 00:00:56,800 --> 00:01:01,153 just say that the first function definition in the list is the entry point. 12 00:01:01,153 --> 00:01:05,622 This will be the main routine, or the function that gets run when the program 13 00:01:05,622 --> 00:01:10,381 starts And this language is expressive enough to write a [inaudible] function And 14 00:01:10,381 --> 00:01:15,082 here it is And this is just a standard definition, if X is one then the result is 15 00:01:15,082 --> 00:01:19,492 zero. If X is two, the result is one. Otherwise it's the sum of fib of X minus 16 00:01:19,492 --> 00:01:25,615 one and fib of X minus two. Now, it's a two code generation for this language. We 17 00:01:25,615 --> 00:01:30,422 need to generate code for each expression E; we need to produce MIPS code for each 18 00:01:30,422 --> 00:01:34,935 expression E that accomplishes two things. First of all, that code is going to 19 00:01:34,935 --> 00:01:39,778 compute the value of E, and leave it in the accumulator A zero. Right? So when the 20 00:01:39,778 --> 00:01:45,416 code for E is done, the value of E will be stored in the accumulator And furthermore, 21 00:01:45,618 --> 00:01:50,719 E is going to, the code for E, excuse me, the generated code for E is going to 22 00:01:50,719 --> 00:01:55,888 preserve the stack pointer and the contents of the stack. That means whatever 23 00:01:55,888 --> 00:02:01,258 the stack is when we started executing E, or the code for E, the stack will be 24 00:02:01,258 --> 00:02:06,461 exactly the same after we're done, executing the code for E And we're going 25 00:02:06,461 --> 00:02:11,862 to write a code generation function C-gen of E that produces code. Okay? So C-gen 26 00:02:11,862 --> 00:02:16,417 would be something that produces a program. It produces code that will 27 00:02:16,417 --> 00:02:22,113 accomplish these two things. Now our co-generation function is just going to 28 00:02:22,113 --> 00:02:26,815 work by cases And to begin with let's focus on the expressions, and we're just 29 00:02:26,815 --> 00:02:32,059 going to have, different kind of code or a certain kind of code that's generated for 30 00:02:32,059 --> 00:02:36,882 each kind of expression in the language. So to evaluate an expression, which is a 31 00:02:36,882 --> 00:02:41,403 just an integral constant, all we have to do is load that constant into the 32 00:02:41,403 --> 00:02:45,321 accumulator. So, the code generation for ‘I', for the constant, ‘I', is the 33 00:02:45,321 --> 00:02:49,556 instruction, load immediate into the accumulator the value of ‘I' And it's 34 00:02:49,556 --> 00:02:53,709 easy to see that this preserves the stack as required, so this doesn't modify the 35 00:02:53,709 --> 00:02:57,965 stack pointer or the contents of the stack at all, so the stack is exactly the same 36 00:02:57,965 --> 00:03:02,435 before and after the execution of this instruction. >> And another thing I want 37 00:03:02,435 --> 00:03:07,937 to point out or I want to emphasize here, is I'm going to be following a convention 38 00:03:07,937 --> 00:03:13,239 that things that are in red, are things that are done at compile time And things 39 00:03:13,239 --> 00:03:18,675 that are in blue are things that are going to be done in run time. So in this case, 40 00:03:18,675 --> 00:03:24,165 at compile time we execute the function C gen of I And that produces code. Here that 41 00:03:24,165 --> 00:03:28,792 will run at run time, okay. So, C gen of I, something that would execute a compile 42 00:03:28,792 --> 00:03:33,476 time, and it produces a program that will be executed at run time And this is to 43 00:03:33,476 --> 00:03:38,454 help you separate in your mind, and, and to develop a very, firm grip on the idea 44 00:03:38,454 --> 00:03:43,256 that we have a real division of time in these programs, There's stuff that happens 45 00:03:43,256 --> 00:03:47,649 inside the compiler, and then there's computation that's deferred until the 46 00:03:47,649 --> 00:03:53,074 program that we are producing, actually executes. All right, now let's look at 47 00:03:53,074 --> 00:03:57,918 another example. Let's, let's take on the addition of two expressions and think 48 00:03:57,918 --> 00:04:02,142 about the code that gets generated for that. So, what are we going to do? Well 49 00:04:02,142 --> 00:04:05,876 the first thing that happens when we execute E1+E2 is that we have to compute 50 00:04:05,876 --> 00:04:10,007 the values of the sum expressions, we have to know what integers we're going to add. 51 00:04:10,007 --> 00:04:13,845 So we better generate code for E1. And that's going to happen at com pile time. 52 00:04:13,845 --> 00:04:17,886 We're definitely going to generate that code at compile time. And then, once we've 53 00:04:17,886 --> 00:04:21,878 got the value of E1, well, remember we only have one, register stack machine, so 54 00:04:21,878 --> 00:04:25,769 we're going to have to save that value somewhere until we also know the value of 55 00:04:25,769 --> 00:04:29,611 E2 and where we're going to put it. We'll do what we always do; we'll put it on a 56 00:04:29,611 --> 00:04:35,120 stack. So, E1 The, the, the code for E1 is guaranteed to leave the value of E1 and 57 00:04:35,120 --> 00:04:40,763 the accumulator. So what we're going to store the value of E1 onto the stack. And 58 00:04:40,763 --> 00:04:46,553 we know how to do that. We store A0 onto the stack, and then we have to bump the 59 00:04:46,553 --> 00:04:53,676 stack pointer. >> And then we can generate code for E2. Okay and again, this stuff in 60 00:04:53,676 --> 00:04:59,114 blue is a part of the program that will be executed at, at run time. These are calls 61 00:04:59,114 --> 00:05:04,748 to the co-generator that are happening at compile time. And so we generate the code 62 00:05:04,748 --> 00:05:10,316 for E2, and then that goes here after this code for pushing the value of E1 on the 63 00:05:10,316 --> 00:05:16,007 stack And once we have the value for E2, now we can perform the add, So how do we 64 00:05:16,007 --> 00:05:22,247 do that? Well, first we retrieve the value of E1. So we load the value of E1 Which is 65 00:05:22,465 --> 00:05:27,358 on the stack. And notice that. This works because E2 is guaranteed the code for E2 66 00:05:27,358 --> 00:05:31,541 is guaranteed to preserve the stack. You know this code for E2 here, and let me 67 00:05:31,541 --> 00:05:35,992 digress for a moment; this code for E2 can be arbitrarily complicated. This could be 68 00:05:35,992 --> 00:05:39,693 a whole program. It could go call functions. It could allocate data 69 00:05:39,693 --> 00:05:44,036 structures. It could print things out. It could do all kinds of complicated things 70 00:05:44,036 --> 00:05:48,487 But because we have this invariant that all code generation for all expressions 71 00:05:48,487 --> 00:05:52,724 will preserve the stack, we know that no matter how complicated this is and how 72 00:05:52,724 --> 00:05:56,961 long it takes. When it's done executing, the stack will be in the same state. And 73 00:05:56,961 --> 00:06:01,548 that's what allows us to know. Where to find the value of E1 that we stored away 74 00:06:01,548 --> 00:06:06,605 It's going to be at the top of the stack, Okay, so we load the value B one back into 75 00:06:06,605 --> 00:06:11,651 a temporary register, now we can do the add Okay, so we add T1 and A0 together, 76 00:06:11,651 --> 00:06:17,339 and store that back in the accumulator And now we have to pop the stack And now 77 00:06:17,339 --> 00:06:22,360 notice that this is all the code, here, for E1+E2, and when we're done, we've, 78 00:06:22,573 --> 00:06:28,089 established our the value of E1+E2 is in the accumulator. That was established by 79 00:06:28,089 --> 00:06:33,464 this instruction. And this pop here restores the state of the stacks. Now, the 80 00:06:33,464 --> 00:06:39,334 state of the stacks here is exactly what it was when we entered this block of code 81 00:06:39,334 --> 00:06:46,834 up here. Now to be completely precise I really should write this code generation 82 00:06:46,834 --> 00:06:52,661 function out a slightly different way And that would be like this. So what we're 83 00:06:52,661 --> 00:06:58,207 really doing here is we are generating code for E1 and then we're printing out 84 00:06:58,207 --> 00:07:03,581 into a file or something like that the code to do the push. Okay, and then we 85 00:07:03,762 --> 00:07:08,209 generate the code for U2 And now, these calls, the code generation, are also 86 00:07:08,209 --> 00:07:12,777 printing in to the same file, okay. So, here [inaudible], they just printed out 87 00:07:12,777 --> 00:07:16,985 the instructions, whatever the instructions are, like security one, this 88 00:07:16,985 --> 00:07:21,974 is printing out the code to execute, to do the push. You print out the code to do U2 89 00:07:21,974 --> 00:07:27,498 And then, we print out the code to do the ad and the pop Fence. Yes, The add and the 90 00:07:27,498 --> 00:07:31,694 pop. Okay, and this is just a, this is much more verbose over here, and so I'm 91 00:07:31,694 --> 00:07:36,429 trying to go in and leave out the prints and just indicate in blue the instructions 92 00:07:36,429 --> 00:07:40,456 that are deferred, but I hope you understand what this means. Everything in 93 00:07:40,456 --> 00:07:44,538 red here, of course is being done in compile time so you know, we're calling 94 00:07:44,538 --> 00:07:48,675 these co-generation functions a compile time. The print statements are being 95 00:07:48,675 --> 00:07:52,811 executed in compile time and then we're accumulating somewhere in some data 96 00:07:52,811 --> 00:07:56,947 structure or in a file, all the instructions that will be executed at run 97 00:07:56,947 --> 00:08:02,941 time. So let's think about a possible optimization to this code. Instead of 98 00:08:02,941 --> 00:08:08,142 pushing the result of E1 on the stack, what if we stored the result of E1 in a 99 00:08:08,142 --> 00:08:13,704 temporary register T1. What would the code for that look like? >> Well in that world, 100 00:08:13,704 --> 00:08:19,275 to generate code for E1 plus E2, what would we do? We'd generate code for E1 and 101 00:08:19,275 --> 00:08:24,846 that would be followed now by instead of pushing the result on the stack, we would 102 00:08:24,846 --> 00:08:30,349 take the result of E1, which of course is in the accumul ator A0, we would store it 103 00:08:30,349 --> 00:08:35,617 in a temporary register And then we would generate code for E2. Alright, that we 104 00:08:35,617 --> 00:08:40,679 followed by the code for E2, and then we could just do the add. We would, take the 105 00:08:40,679 --> 00:08:45,433 result of E2, which is in the accumulator A0, add it to the contents of T1, and 106 00:08:45,433 --> 00:08:50,680 store that into the accumulator A0, and of course there's no pushing and popping from 107 00:08:50,680 --> 00:08:55,681 the stack here, so this code preserves the stack, and it looks like, anyway, that it 108 00:08:55,681 --> 00:09:00,681 actually puts the value of E1 plus E2, into, the accumulator. Unfortunately, this 109 00:09:00,681 --> 00:09:05,615 code is incorrect, so this is actually wrong, and you don't want to do this And 110 00:09:05,615 --> 00:09:14,492 to see why, let's consider what would happen. If, E2 Was itself the actually, 111 00:09:14,492 --> 00:09:21,960 let's do it for a concrete example. Let's do the example one plus two Plus three 112 00:09:22,340 --> 00:09:28,723 Parenthesize like that, okay. So what's going to happen, so E1 here, so we're 113 00:09:28,723 --> 00:09:35,366 doing one plus two plus three. So this will be a load immediate, the first, the 114 00:09:35,366 --> 00:09:43,520 code for E1 will be a load immediate into A0 of the number one. Okay, and then we'll 115 00:09:43,520 --> 00:09:52,415 have the move. We'll try to save that value I, in, temporary register T1. And 116 00:09:52,415 --> 00:09:58,046 now we're going to generate code for E2. And what's E2? Well, E2 is itself, a plus 117 00:09:58,046 --> 00:10:03,890 expression. So we're going to recursively call the code generator to generate code 118 00:10:03,890 --> 00:10:09,450 for two+3. So we generate code for the new first, expression. So that will be a 119 00:10:09,450 --> 00:10:15,152 [inaudible] immediate, into A0 of the value two And now you should be able to 120 00:10:15,152 --> 00:10:20,983 see what's going to go wrong, because. >> Since this uses the same co-generation 121 00:10:21,211 --> 00:10:27,445 strategy, it's also going to try to use T-1 to hold the temporary value. So it's 122 00:10:27,445 --> 00:10:33,603 going to move the accumulator into T-1, thereby clobbering the value of the 123 00:10:33,603 --> 00:10:39,534 previous self expression that we had evaluated, the number one. Okay, so that 124 00:10:39,534 --> 00:10:50,711 value's going to be overwritten and then we're going to do and add And oops I may 125 00:10:50,711 --> 00:10:56,239 have made a mistake, we're not going to do an ad, let me erase that Forgot to 126 00:10:56,239 --> 00:11:03,126 generate the code for the three, so now we load the value of three. I, in to the 127 00:11:03,126 --> 00:11:12,523 accumulator And now we can do the add, now comes the add And so we do A0 T1 A0 and 128 00:11:12,523 --> 00:11:21,921 when you execute this what do you get. You get two + three which is five and that's 129 00:11:21,921 --> 00:11:28,915 fine but now, Now we have the value of this sub expression. In the accumulator 130 00:11:28,915 --> 00:11:33,732 and now ready to do the outer add. So that generates another add instruction. Which 131 00:11:33,732 --> 00:11:40,037 is exactly the same But unfortunately, the first value of T1, the first temporary we 132 00:11:40,037 --> 00:11:45,947 tried to restore has been overwritten And so what's in that, what's in T1 at this 133 00:11:45,947 --> 00:11:50,910 point is the value two, instead of the value one, and we get that one+2+3=7. 134 00:11:51,080 --> 00:11:55,458 Which is not what we wanted And so the problem here of course is that in the 135 00:11:55,458 --> 00:11:59,836 presence of nested expressions, and particularly nested expressions of the 136 00:11:59,836 --> 00:12:04,555 same kind, if the expressions try to use a fixed [inaudible] for their temporary 137 00:12:04,555 --> 00:12:09,331 values, then if you try to generate a code for two different expressions that are 138 00:12:09,331 --> 00:12:13,823 [inaudible], sorry two expressions of the same kind that are nested beside each 139 00:12:13,823 --> 00:12:18,258 other, they will step on each other's temporary intermediate results And so 140 00:12:18,258 --> 00:12:24,431 that's why we have to use a stack to store intermediate values. So this example 141 00:12:24,431 --> 00:12:29,204 illustrates a couple of features of code generation that I just want to emphasize. 142 00:12:29,378 --> 00:12:33,977 First of all, notice that the code for plus is really a template that has holes 143 00:12:33,977 --> 00:12:38,925 in it for the code, for evaluating E1, E2, that is there are some fixed instructions, 144 00:12:38,925 --> 00:12:43,960 that we admit And then there are places where we plug in the code for E one and 145 00:12:43,960 --> 00:12:49,204 the code for E two, okay, so that's what I mean by a template, so there's some fixed 146 00:12:49,204 --> 00:12:54,063 stuff which are the instructions that actually do the ad, and then there's a 147 00:12:54,063 --> 00:12:59,243 place where we can just plug directly in, arbitrary code, whatever it is for 148 00:12:59,243 --> 00:13:04,295 implementing E one and E two, and we'll see the same pattern with all the other 149 00:13:04,487 --> 00:13:08,975 kinds of expressions. The other important point is that stack machine code, 150 00:13:08,975 --> 00:13:13,861 generation is recursive. That is you know the code for E1 plus E2 is code for E1 and 151 00:13:13,861 --> 00:13:18,129 E2 glued together and recursively regenerate code E1 and E2 which will have 152 00:13:18,129 --> 00:13:22,735 their own templates and may even be other expressions of the same kind as we just 153 00:13:22,735 --> 00:13:28,713 saw And what this means is that code generation can be written as a recursive 154 00:13:28,713 --> 00:13:34,385 descent of the abstract syntax tree, at least for the expressions. Alright so 155 00:13:34,385 --> 00:13:39,660 let's consider another new instruction. Let's add the subtraction instruction And 156 00:13:39,660 --> 00:13:45,133 this is just like addition instruction so sub just subtraction to register instead 157 00:13:45,133 --> 00:13:50,408 of adding them. And code generation then for subtraction expression as you might 158 00:13:50,408 --> 00:13:55,288 imagine look and awful like code generation for a plus expression. So what 159 00:13:55,288 --> 00:14:00,897 do we have first we have a place where we plug in the code for E1. >> Then we have 160 00:14:00,897 --> 00:14:06,591 to store the value of E1 on the stack. We have to remember that intermediate result 161 00:14:06,591 --> 00:14:12,152 And then we can go off and compute the value of E2. So this is where the code for 162 00:14:12,152 --> 00:14:17,978 E2 gets plugged in And then at the end, we load the value of E1 back into a temporary 163 00:14:17,978 --> 00:14:23,251 register. I actually do the operation, the subtraction, and then pop the stack And 164 00:14:23,251 --> 00:14:28,208 the thing to do note about this code is that it's exactly the same as the code for 165 00:14:28,208 --> 00:14:33,346 addition except for this instruction right here where we do a subtraction instead of 166 00:14:33,346 --> 00:14:37,987 an add. So next we're going to talk about code generation for if then else 167 00:14:37,987 --> 00:14:43,085 expressions And to do that we're going to need some control flow instructions. So 168 00:14:43,085 --> 00:14:47,932 we'll have, we'll need two in fact. So here's the branch equal instruction, and 169 00:14:47,932 --> 00:14:52,967 this jumps to a label if the contents of two registers are equal And then we'll 170 00:14:52,967 --> 00:14:57,876 also need an unconditional jump. So this just does an unconditional branch, not 171 00:14:57,876 --> 00:15:04,569 branch, an unconditional jump to a particular assembly instruction. So let's 172 00:15:04,569 --> 00:15:10,325 look at the code generation for the expression if E1 is equal to E2 then 173 00:15:10,325 --> 00:15:16,115 evaluate three otherwise evaluate four. So first we have to evaluate the predicate 174 00:15:16,115 --> 00:15:21,610 and in order to evaluate the predicate, we first have to evaluate E1. And by now this 175 00:15:21,610 --> 00:15:26,220 pattern for binary operation should be familiar. So we evaluate the first 176 00:15:26,220 --> 00:15:31,336 sub-expression we save the result on a stack, so we push it on to the stack. It 177 00:15:31,336 --> 00:15:36,199 takes two operations, one to save the result of the cumulate on the stack and 178 00:15:36,199 --> 00:15:41,209 the other cumulate stack later. Then we evaluate E2. Now we have evaluate d both 179 00:15:41,209 --> 00:15:46,777 of the arguments to the predicate. The result of E2 is in the accumulator and the 180 00:15:46,777 --> 00:15:52,080 result of E1 is at the top of the stack because again, the evaluation of E2 will 181 00:15:52,080 --> 00:15:56,774 preserve the stack. So now we load the value of E One back into a temporary 182 00:15:56,774 --> 00:16:01,865 register. And we pop the stack And then we can actually do the comparison. So now we 183 00:16:01,865 --> 00:16:06,710 do a branch equal. So if the value of E One is equal. Sorry this is actually the 184 00:16:06,710 --> 00:16:11,372 value of E Two and E Zero and if that's equal to the value of E One. Then we 185 00:16:11,372 --> 00:16:16,340 branch to the true branch. Otherwise we're going to fall through if there not equal. 186 00:16:16,680 --> 00:16:21,358 Okay And so we'll call that the false branch And what are we going to do if we 187 00:16:21,358 --> 00:16:25,918 fall through, if this test fails, well then we want to evaluate E4. And that will 188 00:16:25,918 --> 00:16:30,952 leave the value of E4 in the accumulator and that will be the value of the entire 189 00:16:30,952 --> 00:16:35,098 [inaudible] in the case where the predacious falls. So when we're done, 190 00:16:35,098 --> 00:16:39,776 we're going to branch now to some code that we'll just clean up and end the if 191 00:16:39,776 --> 00:16:44,159 statement. We'll see what that does in a moment. Otherwise, we still need to 192 00:16:44,159 --> 00:16:48,909 implement the true branch, so we'll stick the label for the true branch here And 193 00:16:48,909 --> 00:16:53,776 what do we do on the [inaudible]? We just evaluate E3. Okay And then the and if, 194 00:16:53,776 --> 00:16:59,069 Well, actually, there is no cleanup to do Because, E3 and E4 both preserve the 195 00:16:59,069 --> 00:17:03,925 stack, and they leave the result of their expressions of the accumulator. So we 196 00:17:03,925 --> 00:17:09,218 reach and if, from E3 if we executed the true branch And then, in which case, the 197 00:17:09,218 --> 00:17:14,386 value in the accumulator is the value of E3 And we reach and if, through this 198 00:17:14,386 --> 00:17:19,616 branch if we executed the false branch And then the value in the accumulator is the 199 00:17:19,616 --> 00:17:24,100 value of E4 And so this correctly implements an if then else expression.