1 00:00:02,680 --> 00:00:08,068 This video is a continuation of the previous video where we'll be finishing up 2 00:00:08,068 --> 00:00:13,184 co-generation for the simple language dealing with function calls, function 3 00:00:13,184 --> 00:00:20,452 definitions and variable references. So just to remind you what we're working on, 4 00:00:20,452 --> 00:00:24,827 here is the simple language And again, we have a bunch of different kinds of 5 00:00:24,827 --> 00:00:29,662 expressions And we dealt with all of these last time except for variable references 6 00:00:29,662 --> 00:00:34,267 and function calls And of course, we also have function definitions. So, as I said 7 00:00:34,267 --> 00:00:38,814 in the introduction these are the three constructs we'll be looking at in this 8 00:00:38,814 --> 00:00:44,598 video. >> The main issue in designing the co-generation for function calls and 9 00:00:44,598 --> 00:00:49,368 function definitions is that both of these will depend intimately on the layout of 10 00:00:49,368 --> 00:00:53,104 the activation record. So really, co-generation for function calls, 11 00:00:53,104 --> 00:00:57,875 co-generation for function definitions and the layout of the activation record all 12 00:00:57,875 --> 00:01:02,243 need to be designed together. Now for this particular language, a very simple 13 00:01:02,243 --> 00:01:06,491 activation record will be sufficient. Because we are using a stack machine, we 14 00:01:06,491 --> 00:01:10,894 are modeling a stack machine in our code generation. The results of a function call 15 00:01:10,894 --> 00:01:15,085 will always be in the accumulator and that means there is no need to store the 16 00:01:15,085 --> 00:01:19,122 results of the function call in the activation record And furthermore, the 17 00:01:19,122 --> 00:01:23,577 activation record will hold the actual parameters. So when we go to computer 18 00:01:23,577 --> 00:01:28,501 function call with arguments X1 through XN, we will push those arguments onto the 19 00:01:28,501 --> 00:01:33,132 stack And as it happens, these are the only variables in this language that are 20 00:01:33,132 --> 00:01:38,173 no local or global variables other than the arguments to a function call And so 21 00:01:38,173 --> 00:01:42,569 those are the only variables that will need to be stored in the activation 22 00:01:42,569 --> 00:01:46,706 record. Now recall that the stack machine discipline guarantees that the stack 23 00:01:46,706 --> 00:01:50,484 pointer is preserved across function calls. So the stack pointer will be 24 00:01:50,484 --> 00:01:54,525 exactly the same when we exit from a function call, as it was when we entered 25 00:01:54,525 --> 00:01:58,724 the function call And this means we won't need a control link in our activation 26 00:01:58,724 --> 00:02:03,027 record. The point of a control link is to help us find the previous activat ion, and 27 00:02:03,027 --> 00:02:07,435 since, the stack pointer is preserved, it will have no trouble finding it when we 28 00:02:07,435 --> 00:02:11,686 return from our function call, and we'll never need to look at another activation 29 00:02:11,686 --> 00:02:16,650 during a function call since there are no non-local variables in the language. We 30 00:02:16,650 --> 00:02:20,765 will however need the return address and that will need to be stored somewhere in 31 00:02:20,765 --> 00:02:25,371 the activation record And, one more thing. It turns out that a pointer to the current 32 00:02:25,371 --> 00:02:29,607 activation will be useful. Now this is to the current activation, not to the 33 00:02:29,607 --> 00:02:34,295 previous activation And this pointer will live in the register, FP, which stands for 34 00:02:34,295 --> 00:02:38,587 Frame Pointer. This is a conventional, this is a, this is the register name on 35 00:02:38,587 --> 00:02:42,936 the [inaudible] And the name is chosen, to denote the frame pointer And by 36 00:02:42,936 --> 00:02:47,568 convention, the compilers put the frame pointer there. What the frame pointer is 37 00:02:47,568 --> 00:02:52,256 good for, well it points to the current frame, so that's what the name comes from. 38 00:02:52,256 --> 00:02:57,736 But, what it's good for, we'll see in a few minutes. Right so to summarize for 39 00:02:57,736 --> 00:03:02,454 this language an activation record that has the caller's frame pointer, The actual 40 00:03:02,454 --> 00:03:07,115 parameters and the return address will be sufficient. So let's consider a call to 41 00:03:07,115 --> 00:03:12,121 the function F and has two arguments X and Y. Then at the time the call is performed 42 00:03:12,121 --> 00:03:16,840 before we start executing the body of the function this is what the activation 43 00:03:16,840 --> 00:03:21,385 record will look like, So we'll have the old frame pointer. So this is the frame 44 00:03:21,385 --> 00:03:25,989 pointer that points to the caller's frame. Not to the frame of the function that 45 00:03:25,989 --> 00:03:30,019 we're executing And the reason that it does that is that we have to save it 46 00:03:30,019 --> 00:03:33,854 somewhere because the frame pointer register will be overwritten with the 47 00:03:33,854 --> 00:03:38,310 frame pointer for the current activation so we have to save the old one, so that we 48 00:03:38,310 --> 00:03:42,715 can restart the caller when we return to it, from the current function. And then 49 00:03:42,715 --> 00:03:46,757 there the arguments of the function and those that are pushed on the stack in 50 00:03:46,757 --> 00:03:50,903 reverse order. So the last argument is pushed on first and the first argument is 51 00:03:50,903 --> 00:03:54,997 at the top of the stack And the reason for doing it this way is it'll make the 52 00:03:54,997 --> 00:03:59,350 indexing to find the a rguments a little bit easier. A little bit simpler And then 53 00:03:59,350 --> 00:04:04,230 We have the stack pointer so there's a, there's nothing here. What will go here is 54 00:04:04,230 --> 00:04:08,749 the callee, the function that we're calling, will push on the return address. 55 00:04:08,749 --> 00:04:13,629 So this is where the return address will go And these elements, the callers frame 56 00:04:13,629 --> 00:04:18,569 pointer, the arguments to the function and the return address of the call function 57 00:04:18,569 --> 00:04:25,315 will make up the activation record of F. A bit of terminology, the calling sequence 58 00:04:25,315 --> 00:04:30,771 is the sequence of instructions that both the caller and callee to set up a function 59 00:04:30,771 --> 00:04:36,162 invocation, okay? So that's referred to in compiler lingo as the calling sequence And 60 00:04:36,162 --> 00:04:41,681 we're going to need a new instruction to show the calling sequence for this for, 61 00:04:41,681 --> 00:04:46,688 for function calls. And that will be the jump and link instruction. So jump and 62 00:04:46,688 --> 00:04:52,049 link what it does is it jumps to the label that it's given as [inaudible] And it 63 00:04:52,049 --> 00:04:56,905 saves the address of the next instruction after the jump in link, in the register 64 00:04:56,905 --> 00:05:01,522 R.A. Which stands for, return address. So, what would happen in the jump in link 65 00:05:01,522 --> 00:05:05,809 instructions, if I have jump in link to label L And then there's an add 66 00:05:05,809 --> 00:05:10,522 instruction that comes next. I don't know what it is. It's the address of this 67 00:05:10,522 --> 00:05:15,542 instruction, the one after the jump in the link that will be stored in the ret-, in 68 00:05:15,542 --> 00:05:20,317 the, in the register RA. So this instruction will jump to L. It will store 69 00:05:20,317 --> 00:05:25,459 the address of this add instruction in RAb And it will execute whatever code is at L. 70 00:05:25,459 --> 00:05:30,356 And then the code that's at L can execute a jump back to the address in here to 71 00:05:30,356 --> 00:05:36,540 execute the return, to the caller. So now we're ready to actually generate code for 72 00:05:36,540 --> 00:05:41,961 a function call expression. So let's say we have the call, F of E1 To EN Where of 73 00:05:41,961 --> 00:05:47,186 course E1 through EN are expressions. And let me change colors here. So these are 74 00:05:47,186 --> 00:05:52,259 expressions, here, not values. So how are we going to do that? >> Well, the first 75 00:05:52,259 --> 00:05:56,436 thing we're going to do is we're going to start building, the activation record And 76 00:05:56,436 --> 00:06:00,664 so we save the current frame pointer. This is the frame pointer for the collar. >> 77 00:06:00,664 --> 00:06:04,788 Okay. >> This is pointing to th e collars frame. >> Right >> And we store that at 78 00:06:04,788 --> 00:06:09,900 the stack pointer. We have to bump the stack pointer. And then we generate code 79 00:06:09,900 --> 00:06:15,902 for the last argument, for EN, right? And so that code gets inserted here And then 80 00:06:15,902 --> 00:06:21,326 we push it on the stack. So we store the results of EN which will be in the 81 00:06:21,326 --> 00:06:27,292 accumulator A0 on the stack and then we, bump the stack pointer. Alright, and we'll 82 00:06:27,292 --> 00:06:32,856 do that for all the arguments finishing up with E-1. So, we generate code for E-1 and 83 00:06:32,856 --> 00:06:38,421 we push it onto the stack. So, now all the arguments are on the stack and now we just 84 00:06:38,421 --> 00:06:43,521 do the jump in link. So, we've done as much of the work or much of the calling 85 00:06:43,521 --> 00:06:48,556 sequence as we can do on the caller's side. So, this code is executing in the 86 00:06:48,556 --> 00:06:54,073 function in the caller. Okay, so this is the caller side of the calling sequence, 87 00:06:54,073 --> 00:06:58,579 and it builds up as much of the activation record as it can. In particular it's 88 00:06:58,579 --> 00:07:03,084 evaluating the actual parameters and pushing them on to the stack to form part 89 00:07:03,084 --> 00:07:07,646 of the activation record, for the called function, and then we do the jump and 90 00:07:07,646 --> 00:07:12,209 link. And we jump to the entry point of the function that we're calling. So we're, 91 00:07:12,209 --> 00:07:17,891 this is a call to, to F, and so we jump to F's entry point. So a few more things to 92 00:07:17,891 --> 00:07:23,080 note, First of all, as we discussed on the previous slide When we execute the jump in 93 00:07:23,080 --> 00:07:28,210 link instruction that is going to save the return address in the register RA And that 94 00:07:28,210 --> 00:07:33,100 address will be this address here, the one that comes after the, the address of the 95 00:07:33,100 --> 00:07:37,872 next instruction, after the jump in link instruction And you'll notice also that 96 00:07:37,872 --> 00:07:42,703 the activation record we've built so far is four times N plus four bytes. So this 97 00:07:42,703 --> 00:07:46,938 is where N here is the number of arguments. Each argument takes up four 98 00:07:46,938 --> 00:07:52,298 bytes, and then four bytes for the old frame pointer. Now we're ready to talk 99 00:07:52,298 --> 00:07:56,729 about the callee side of the calling sequence And we're going to need one new 100 00:07:56,729 --> 00:08:01,279 instruction for that. The JR instruction stands for jump register. And it just 101 00:08:01,279 --> 00:08:05,769 jumps to the address in its register argument. So now, the callee side is the 102 00:08:05,769 --> 00:08:10,555 code for the function definition, okay? So this is the co de that actually executes 103 00:08:10,732 --> 00:08:15,700 the body of the function. And how do we generate code for that? Well let's take a 104 00:08:15,700 --> 00:08:20,840 look. Now actually the very first thing that should be here is that this first 105 00:08:20,840 --> 00:08:26,044 instruction of the [inaudible] side is the entry point. So, we're missing the label 106 00:08:26,044 --> 00:08:30,888 here So this would be labeled F entry. Okay So this is the target of the jump in 107 00:08:30,888 --> 00:08:35,174 link instruction. And then the very first thing we do is we set up the frame 108 00:08:35,174 --> 00:08:39,742 pointer. So we copy the current value of the stack pointer into the frame pointer. 109 00:08:39,742 --> 00:08:44,141 That sets, that points to the end of the frame for the [inaudible], for the new 110 00:08:44,141 --> 00:08:48,707 function that's being executed. We also save the return address at the current 111 00:08:48,707 --> 00:08:53,383 position on the stacks. Remember there was one more thing to do one thing one thing 112 00:08:53,383 --> 00:08:57,947 that was missing. On the caller side on the caller side of the sequences which is 113 00:08:57,947 --> 00:09:02,230 the return address. We don't know the return address until after the jumping 114 00:09:02,230 --> 00:09:06,624 link instructions executes And so the callee is the one that has to save that 115 00:09:06,624 --> 00:09:11,357 value. Okay so after the jumping link the RA register contains the return address 116 00:09:11,357 --> 00:09:17,393 and that we save it into the frame. All right, and then we push the stack pointer. 117 00:09:17,393 --> 00:09:22,246 'Kay. And now we just generate code for the body of the function. So now the, at 118 00:09:22,246 --> 00:09:26,794 this point the activation record is completely set up, and now we can just 119 00:09:26,794 --> 00:09:31,465 generate code for the function body. And after the function body executes, of 120 00:09:31,465 --> 00:09:36,012 course, the stack pointer will be preserved, and, and that means that the 121 00:09:36,012 --> 00:09:41,298 return address will be at four offset from the stack pointer, so we can load the 122 00:09:41,298 --> 00:09:46,535 return address back into the return address register And then we can pop the 123 00:09:46,535 --> 00:09:51,083 stack So here we're going to pop off The current frame from the stack And that's 124 00:09:51,083 --> 00:09:55,293 going to be song size, z. Which we I haven't shown you what it is yet But, 125 00:09:55,461 --> 00:10:00,121 we'll calculate The size of z in just a minute? This is going to be an immediate 126 00:10:00,121 --> 00:10:06,160 value. So it's a constant that we plug in there And then we load the old frame 127 00:10:06,160 --> 00:10:12,472 pointer. Okay So once we've incremented the stacks we popped off the existing 128 00:10:12,472 --> 00:10:17,745 frame, and so now we're pointing at the frame pointer at the first we're, we're, 129 00:10:17,745 --> 00:10:22,282 we're pointing at the first thing beyond the previous stack frame, and, what was 130 00:10:22,282 --> 00:10:26,761 that, well, that was the first thing that we saved in the stack frame for F, and 131 00:10:26,761 --> 00:10:31,585 that's the old frame pointer. So now we restore the old frame pointer so that the 132 00:10:31,585 --> 00:10:36,524 call, the function that called us, we'll have its frame pointer back, and then now 133 00:10:36,524 --> 00:10:41,405 we're ready to return it resume execution of the calling function. We just do that 134 00:10:41,405 --> 00:10:46,065 by a jump register to the return address, All right? So note here that the frame 135 00:10:46,065 --> 00:10:50,329 pointer points to the top of the frame, not the bottom of the frame. Okay? So that 136 00:10:50,329 --> 00:10:54,752 will actually be important when we talk about how we use the frame pointer When we 137 00:10:54,752 --> 00:10:59,176 get to talking about the variable references next And the callee pops the 138 00:10:59,176 --> 00:11:03,493 return address, The actual arguments in the saved value of the frame pointer from 139 00:11:03,493 --> 00:11:07,331 the stacks. So the callee pops off the entire activation record, and also 140 00:11:07,331 --> 00:11:12,206 restores the caller's frame pointer And what's the value of Z? Well, there are N 141 00:11:12,206 --> 00:11:16,825 arguments. Each of which take up four bytes So there's at, so the size of the 142 00:11:16,825 --> 00:11:21,445 activation record is four times N. Plus, there are two other values. In the 143 00:11:21,445 --> 00:11:27,138 activation record One is the return address. And the other one is the old 144 00:11:27,138 --> 00:11:31,825 frame pointer. Okay and the space for two more words is eight bytes. So that's the 145 00:11:31,825 --> 00:11:36,281 size of the activation record. So that's how much we have to add to the stack 146 00:11:36,281 --> 00:11:41,947 pointer to pop the activation record for F off the stack. Just to give you a sketch 147 00:11:41,947 --> 00:11:47,125 of, what this looks like before the call. We have the frame pointer for the caller, 148 00:11:47,125 --> 00:11:52,686 and we have the, The current value of the stack pointer And on entry to the 149 00:11:52,686 --> 00:11:57,735 function. Okay, after the calling after the calling functions side of the calling 150 00:11:57,735 --> 00:12:01,459 sequence has completed what's on the stack, well, we have the old frame 151 00:12:01,459 --> 00:12:05,560 pointer, and the two arguments, and then the stack pointer points to the next 152 00:12:05,560 --> 00:12:09,878 unused, location. Which is where the return address will go Alright, then we do 153 00:12:09,878 --> 00:12:13,980 the jump and link. We jump over, and the return address gets pushed on to the 154 00:12:13,980 --> 00:12:18,297 stack, a nd the frame pointer gets moved to point two, the current value of the 155 00:12:18,297 --> 00:12:22,722 frame. Okay, you've got [inaudible] to the top of the frame. Okay? And then after the 156 00:12:22,722 --> 00:12:26,608 call, what has happened? Well, we've popped everything off the stack, we've 157 00:12:26,608 --> 00:12:31,883 popped the entire. Your activation record for the call function off of the stack And 158 00:12:31,883 --> 00:12:36,873 so now notice that we're back in the same state. So again, function calls have to 159 00:12:36,873 --> 00:12:41,665 preserve the invariant that. The stack is preserved across the call so the stack 160 00:12:41,665 --> 00:12:48,058 should be exactly the same after the call, as it was on entry to the call. So we are 161 00:12:48,058 --> 00:12:52,098 almost done with code generation for simple language. The last construct we 162 00:12:52,098 --> 00:12:56,676 need to talk about is how we generate code for variable references. Now the variables 163 00:12:56,676 --> 00:13:01,255 of a function again are just its arguments just the parameters to the function. There 164 00:13:01,255 --> 00:13:05,564 are no other kinds of variables in this simple language And these variables are 165 00:13:05,564 --> 00:13:10,142 all in the activation record. So we really all we have to do is generate code to look 166 00:13:10,142 --> 00:13:14,620 up a variable in its appropriate place in the activation record But there is one 167 00:13:14,620 --> 00:13:19,471 problem, and that's that the stack does grow and shrink with intermediate values. 168 00:13:19,471 --> 00:13:24,685 So when you call a function and you begin executing its body values will be popped 169 00:13:24,867 --> 00:13:29,657 and pushed onto the stack beside the activation record. So think back to the 170 00:13:29,657 --> 00:13:34,871 code generation for plus and minus and if then else intermediate values were being 171 00:13:34,871 --> 00:13:39,722 pushed and popped from the stack And so what this means is that these variables 172 00:13:39,722 --> 00:13:45,211 that are in the activation record are not at a fixed offset From the stack pointer. 173 00:13:45,211 --> 00:13:50,408 So we can't use the stack point very easily to the side or to find those 174 00:13:50,408 --> 00:13:56,418 variables. So the solution is to use the frame pointer. The frame pointer always 175 00:13:56,418 --> 00:14:01,294 points to the return address in the activation record and because it doesn't 176 00:14:01,294 --> 00:14:06,549 move during the execution of the function body, we can always find the variables at 177 00:14:06,549 --> 00:14:11,045 the same place relative to the frame pointer. So, how do we do that? Well, 178 00:14:11,045 --> 00:14:16,553 let's consider the [inaudible] argument, X of I and does the [inaudible] argument to 179 00:14:16,553 --> 00:14:22,341 the, to the function. So where is that going to be relative to the frame pointer? 180 00:14:22,550 --> 00:14:28,093 That will be at offset Z from the frame pointer And Z is just four times I. Right, 181 00:14:28,093 --> 00:14:32,490 and this is actually the reason here for generating for pushing the arguments on 182 00:14:32,490 --> 00:14:36,684 the stack in reverse order, starting with the last argument to the function, because 183 00:14:36,684 --> 00:14:40,424 it just makes this index calculation simple. It wouldn't be that much more 184 00:14:40,424 --> 00:14:44,821 complicated if we pushed the arguments in the other order. It just makes it a little 185 00:14:44,821 --> 00:14:48,864 easier to see how the indexing works And anyway this index, this offset, is being 186 00:14:48,864 --> 00:14:52,654 calculated at compile time. So, notice that this number, this four times I, is 187 00:14:52,654 --> 00:14:56,546 something that the compiler knows, and what we're putting in the code here is 188 00:14:56,546 --> 00:15:00,387 just a fixed offset. So, we are not actually doing that multiplication at run 189 00:15:00,387 --> 00:15:05,409 time. See here is just a number, as computed statically by the compiler. So 190 00:15:05,409 --> 00:15:12,392 anyway We just load and off send Z which is the four times I where I is the index, 191 00:15:12,392 --> 00:15:18,545 the position of the variable in the list of parameters. At that offset from the 192 00:15:18,545 --> 00:15:23,074 frame pointer, that's where XI is stored in the activation record And we just load 193 00:15:23,074 --> 00:15:27,327 it into the accumulator. So that is the entire code generation for a variable 194 00:15:27,327 --> 00:15:34,321 reference. Here's a little example. So for the function, the hypothetical function 195 00:15:34,321 --> 00:15:39,529 that we've been looking at, with two parameters x and y. X is going to be at 196 00:15:39,529 --> 00:15:45,630 the frame pointer +four and y will be at the frame pointer +eight. So to summarize 197 00:15:45,630 --> 00:15:50,200 the main point's one very important thing is that the activation record has to be 198 00:15:50,200 --> 00:15:54,226 designed together with the code generation. So you have to do these things 199 00:15:54,226 --> 00:15:58,470 at the same time. You can't just design the activation record without thinking 200 00:15:58,470 --> 00:16:02,823 about what code you're going to generate And you can't just think about generating 201 00:16:02,823 --> 00:16:07,175 code without making some decisions about where the data is going to be lived. So 202 00:16:07,175 --> 00:16:11,528 the code and the data it manipulates, have to be designed simultaneously. Code 203 00:16:11,528 --> 00:16:15,935 generation can be done by a recursive [inaudible] of the abstract syntax street, 204 00:16:15,935 --> 00:16:20,709 so just like type checking. Cogeneration can be expressed as a r ecursive tree-walk 205 00:16:20,709 --> 00:16:25,632 And that's a very handy way to think about cogeneration because it allows you to 206 00:16:25,632 --> 00:16:30,497 think about one case at a time without having to get mixed up thinking about all 207 00:16:30,497 --> 00:16:35,352 the different constructs at one time. >> And finally I recommend that you use a 208 00:16:35,352 --> 00:16:40,655 stack machine for your compiler. So if you're implementing a course project, the 209 00:16:40,655 --> 00:16:45,598 stack machine is the simplest discipline and it gives you a nice framework for 210 00:16:45,598 --> 00:16:50,419 think, for breaking up the project into manageable pieces. And because of that 211 00:16:50,419 --> 00:16:56,849 simplicity, I think it's a really good way to learn about writing compilers. Now, it 212 00:16:56,849 --> 00:17:01,863 is important to realize that production compilers do, do some different things. 213 00:17:02,055 --> 00:17:07,647 They're not quite as simple as, the stack machine cogeneration that we have outlined 214 00:17:07,647 --> 00:17:12,339 in the last few videos. So, the main differences, or, or, the main difference, 215 00:17:12,339 --> 00:17:17,159 is that the big emphasis in a production compiler is on keeping values and 216 00:17:17,159 --> 00:17:22,301 registers. It's much more efficient to do operations out of registers than to be 217 00:17:22,301 --> 00:17:27,250 saving and loading values from the stack And so, especially the values in the 218 00:17:27,250 --> 00:17:32,616 current activation record or current stack frame. It, in production compiler we try 219 00:17:32,616 --> 00:17:39,463 to keep those in registers instead of on the stack And also, typically a pressure 220 00:17:39,463 --> 00:17:43,645 compiler, to the extent that it has to use temporaries, in the activation record. 221 00:17:43,645 --> 00:17:47,674 These would be resolved, laid out directly in the activation record, not pushed and 222 00:17:47,674 --> 00:17:51,805 popped from the stack. That means they'd be assigned, pre-assigned locations in the 223 00:17:51,805 --> 00:17:56,241 activation record, just like, the function arguments in the simple language we looked 224 00:17:56,241 --> 00:18:00,117 at are assigned fixed positions in the activation record. So those temporary 225 00:18:00,117 --> 00:18:04,146 values would also be assigned fixed positions, so you could save the trouble 226 00:18:04,146 --> 00:18:05,880 of manipulating the stack pointer.