1 00:00:02,980 --> 00:00:10,525 In this video we're going to generate code for a small example program. The program 2 00:00:10,525 --> 00:00:16,697 we'll take a look at takes a positive imaginary X and sums all the numbers from 3 00:00:16,697 --> 00:00:23,177 O up to X. So if X is O then the result is O. Otherwise it is X plus the sum of all 4 00:00:23,177 --> 00:00:29,194 the numbers up to X minus one. So this isn't a interesting program but it does 5 00:00:29,194 --> 00:00:35,520 illustration all of the features that we discuss in the previous couple of videos. 6 00:00:36,880 --> 00:00:42,192 So let's dive right in and talk about how we're going to generate code for sum two. 7 00:00:42,192 --> 00:00:47,704 So we begin by giving it a label for the entry point to the function, so that'll be 8 00:00:47,704 --> 00:00:54,420 the sum two entries. Alright and now we have to generate code for the caller's 9 00:00:54,420 --> 00:01:00,217 side, call, callee side excuse me, of the calling sequence. So what was that? So the 10 00:01:00,217 --> 00:01:05,944 first thing we have to do is we have to set up the frame pointer, which would just 11 00:01:05,944 --> 00:01:11,112 be the value of the stack pointer. So that's the frame pointer for this 12 00:01:11,322 --> 00:01:16,653 activation, and. Then we're going to have to store the return address at the current 13 00:01:16,653 --> 00:01:21,118 value of the stack pointer. And then we're going to move the stack pointer 14 00:01:21,118 --> 00:01:26,198 [inaudible]. Whenever we store something on the stack we have to. >> The Seg 15 00:01:26,198 --> 00:01:31,993 pointer is the next unused location. >> Alright. Okay And so now we have to 16 00:01:31,993 --> 00:01:37,291 generate code, for this if then else All right? And the very first thing if you go 17 00:01:37,291 --> 00:01:42,401 back and look at the code for if then else is to generate code for the first sub 18 00:01:42,401 --> 00:01:47,069 expression of the predicate. So we're going to generate code for X, and that's 19 00:01:47,069 --> 00:01:52,305 really easy And we're generating code for a variable, just looks up the variable in 20 00:01:52,305 --> 00:01:58,909 the current position of the frame. Sorry, at the correct offset from the frame 21 00:01:58,909 --> 00:02:04,530 pointer, alright? Alright so once we do that now we are generating code for the 22 00:02:04,530 --> 00:02:09,102 predicate And how do we do that? Well we generate code for this first sub 23 00:02:09,102 --> 00:02:14,487 expression, and now we have to save that sub expression somewhere Because we are 24 00:02:14,487 --> 00:02:19,309 going to generate code for another sub expression. So the equality there is a 25 00:02:19,309 --> 00:02:24,444 binary operator, so we have to save the value we just computed somewhere on the 26 00:02:24,444 --> 00:02:29,580 stack Alright? So we'll do that, so we'll st ore the value of a zero on the stack. 27 00:02:29,940 --> 00:02:41,046 And that will involve, as always, moving the side pointer. Okay and now we generate 28 00:02:41,046 --> 00:02:46,943 code for the second sub-expression of the predicate. All right, that's also easy. 29 00:02:46,943 --> 00:02:52,541 That's just load the immediate of the immediate value into the accumulator, 30 00:02:52,541 --> 00:02:58,587 alright. And now I'm going to load the value that we said, the first or we move 31 00:02:58,587 --> 00:03:04,260 the predicate back into a temporary register and actually do the comparison. 32 00:03:04,260 --> 00:03:10,306 So this is more code, as actually part of the conditional, alright, so we do a load 33 00:03:10,306 --> 00:03:24,380 word Entity one Of the value that we saved before. Okay and now we need to pop the 34 00:03:24,380 --> 00:03:40,984 stack okay. We'll do that here because we're done with that value. Alright, and 35 00:03:40,984 --> 00:03:47,646 now we're going to do the branch. So now we test whether. The two sub-expressions 36 00:03:47,646 --> 00:03:52,484 of the predicate are equal or not, and if they are, then we jump to the true branch. 37 00:03:52,484 --> 00:03:57,263 And here I'm going to give the true branch a unique label, because this might be part 38 00:03:57,263 --> 00:04:02,101 of a larger program where there are many if-then-else's, and so I'm going to append 39 00:04:02,101 --> 00:04:06,526 some identifying number on the end. Instead of writing out true branch, I'll 40 00:04:06,526 --> 00:04:11,128 call this true one Alright? Okay, and then if we fall through, then we're on the 41 00:04:11,128 --> 00:04:15,765 false branch, we'll call that false one And now we're generating code for the 42 00:04:15,765 --> 00:04:20,806 false branch, which is this summation here Alright? And how are we going to do that? 43 00:04:20,806 --> 00:04:24,925 Well this, whole thing is a plus expression, which means we have the 44 00:04:24,925 --> 00:04:29,535 generic code first. For the first sub-expression which is just X. Alright? 45 00:04:29,535 --> 00:04:34,432 So what do we do? Well we load. To generate code for x we look up x at its 46 00:04:34,432 --> 00:04:39,176 current offset. And [inaudible] that is appropriate offset in the frame, using the 47 00:04:39,176 --> 00:04:43,393 frame pointer. Okay? It is the only argument, and so it's at four from the 48 00:04:43,393 --> 00:04:48,254 frame pointer. I'm sorry the only argument to the procedure, and so that's stored at 49 00:04:48,254 --> 00:04:53,174 the first position for arguments, which is always four from the frame pointer in our 50 00:04:53,174 --> 00:04:57,801 scheme. All right, and now that we've loaded it we have to save it because it is 51 00:04:57,801 --> 00:05:07,324 part of a binary operation so we're going to save that value on the stack. Kay. And 52 00:05:07,324 --> 00:05:22,220 now we will. Adjust the [inaudible]. Okay. And what are we going to do next? Well, 53 00:05:22,220 --> 00:05:26,687 now we've, we've, we computed this sub-expression, this X. We can't do the 54 00:05:26,687 --> 00:05:31,270 plus yet until we compute the second sub-expression which is the function call 55 00:05:31,270 --> 00:05:35,738 Alright? So now we have the generate code for the function call and I'm going to 56 00:05:35,738 --> 00:05:40,379 move up here to the other side of the screen here to, to show the rest of the 57 00:05:40,379 --> 00:05:46,034 code. Okay And the first thing we do, to generate code, for the function call Is to 58 00:05:46,034 --> 00:05:51,399 start setting up our activation record Alright? This is even setting up the new 59 00:05:51,399 --> 00:05:56,900 activation record for the function, call that we're about to make Alright? So what 60 00:05:56,900 --> 00:06:02,733 do we do there? We store The frame pointer. 'Kay, use this to our old frame 61 00:06:02,733 --> 00:06:14,802 pointer. Add the stack on the stack. [sound] Alright, and now, we have to 62 00:06:14,802 --> 00:06:19,369 compute the argument All right? We have to compute the x-1. So that code gets 63 00:06:19,369 --> 00:06:24,056 inserted here in the template for our function call. So, what's going to happen 64 00:06:24,056 --> 00:06:28,683 there? Well, we're completing subtraction, so the template for subtraction is to 65 00:06:28,683 --> 00:06:33,190 first generate code for the first sub-expression, then generate code for the 66 00:06:33,190 --> 00:06:37,636 second sube-xpression, and then subtract them. All right, so let's do that. So, 67 00:06:37,636 --> 00:06:48,039 first we generate code for x again. Okay, and now, since it's the first argument of 68 00:06:48,039 --> 00:07:04,701 a binary operation, we're going to save it on stack. Alright now we generate code for 69 00:07:04,701 --> 00:07:10,968 the second argument of the subtraction. Okay, and now we perform the subtractions 70 00:07:10,968 --> 00:07:19,195 so we have to load the first argument back into a temporary register. Have to 71 00:07:19,195 --> 00:07:33,802 actually do the subtraction. Excuse me here. Alright, and then we can pop the 72 00:07:33,802 --> 00:07:45,138 temporary value off the stack. Okay, now we have actually done subtraction. Let me 73 00:07:45,138 --> 00:07:52,930 see that. There is everything, from about here to down there is computing x minus y. 74 00:07:52,930 --> 00:07:59,108 Okay... So this is computing x And this was computing one And then this whole 75 00:07:59,108 --> 00:08:03,907 thing is computing the subtraction Alright? So now we compute the argument. 76 00:08:03,907 --> 00:08:09,226 What are we going to do? Well we save it on the stack. So now we save the result on 77 00:08:09,226 --> 00:08:14,220 the stack. We're saving it into the new activat ion record that we're building 78 00:08:15,860 --> 00:08:22,924 Alright? And then we have to advance this, or move the stack pointers as always And 79 00:08:22,924 --> 00:08:29,158 now we're ready, we have to do the function calls And now we do the jump in 80 00:08:29,158 --> 00:08:37,735 the link to the entry point of sum two Okay? And now when this returns, what it's 81 00:08:37,735 --> 00:08:41,811 going to return with, it's going to return what the result of computing the sum to in 82 00:08:41,811 --> 00:08:45,836 the accumulator, all right? And so then, we're ready to perform the addition And 83 00:08:45,836 --> 00:08:50,067 now we've computed the second argument to the addition and how do we do that? Well, 84 00:08:50,067 --> 00:08:54,401 look back at the template for addition the next thing what happens is we reload the 85 00:08:54,401 --> 00:09:03,630 temporary value that we saved on the stack. Alright and now we got actually 86 00:09:03,630 --> 00:09:18,520 perform the edition. Okay? And then we could pop the temporary value of the stack 87 00:09:23,120 --> 00:09:29,880 Alright And that actually ends the, the else branch, the false branch of the 88 00:09:29,880 --> 00:09:36,986 entire if and else And there's now a branch around the rest of the if and else 89 00:09:36,986 --> 00:09:45,726 code And we'll call that label if and one And now comes the code for the true 90 00:09:45,726 --> 00:09:53,960 branch. And what we are going to put there, well, it's not very complicated 91 00:09:54,157 --> 00:09:59,940 because all we're doing true branch is loading or generating codes for zero which 92 00:09:59,940 --> 00:10:06,520 is a single load immediate, load immediate Alright And that's the entire true branch 93 00:10:06,520 --> 00:10:12,129 is [inaudible] where it is there [inaudible] excuse me, and in fact I can 94 00:10:12,129 --> 00:10:18,336 just raise that a little bit Alright And now we're at and actually I see it notice 95 00:10:18,336 --> 00:10:24,115 in the wrong place so let's fix that so this is a branch at the end of the false 96 00:10:24,115 --> 00:10:29,181 branch, at the end of the else, part of the if and we're going to, to branch 97 00:10:29,181 --> 00:10:35,077 around per quote for the two branch which is only one instruction. And so the very 98 00:10:35,077 --> 00:10:41,240 next instruction is the label end if. So now what's left [inaudible] if and else so 99 00:10:41,240 --> 00:10:46,883 now it goes here is the rest of the template for the function definition so 100 00:10:46,883 --> 00:10:52,972 now we have to generate the code returns back to the caller and how do we do well 101 00:10:52,972 --> 00:11:00,665 we have to load. The return address The on the stack, okay? And now we pop the stacks 102 00:11:00,665 --> 00:11:05,401 so we pop the entire activation record off the stack and now because of the 103 00:11:05,401 --> 00:11:10,137 activation reco rd well remember, there's always two words. One for the return 104 00:11:10,137 --> 00:11:15,060 address and one for the frame pointer and then a number of words equals to the 105 00:11:15,060 --> 00:11:20,233 number of arguments where there's only one argument here, so we have three words, so 106 00:11:20,233 --> 00:11:24,969 it's twelve bytes. So we increment the stack pointer by twelve, all right? And 107 00:11:24,969 --> 00:11:34,003 then we load the old frame pointer, we store the frame pointer. Okay, and then we 108 00:11:34,003 --> 00:11:39,710 return. So, one more instruction, we'll do a jump register to the return address And 109 00:11:39,710 --> 00:11:45,417 that is the entire code for this simple functions sum2 And there's a couple of 110 00:11:45,417 --> 00:11:51,055 things to point out. So, first of all the, the code is constructed as a bunch of 111 00:11:51,055 --> 00:11:56,763 templates pasted together and I try to point out as we go [inaudible] how that 112 00:11:56,763 --> 00:12:02,194 works But we do lined up with one linear sequence of code. Alright and if, if 113 00:12:02,194 --> 00:12:07,640 you're all confused as we work as to go back and look at those templates and look 114 00:12:07,640 --> 00:12:12,887 at this example and understand how the code all fits together and how it works. 115 00:12:12,887 --> 00:12:17,801 And the other thing I would point out is just that this is your extremely 116 00:12:17,801 --> 00:12:23,712 inefficient code so later here where we were generating code to check whether x=0. 117 00:12:23,712 --> 00:12:30,463 Notice here that we, we load x so this is a load Of x And then we immediately store 118 00:12:30,463 --> 00:12:34,633 the x again into the stacks, we just loaded it now from the frame then we 119 00:12:34,633 --> 00:12:39,603 immediately store it back in the memory and then we and load the immediate value 120 00:12:39,603 --> 00:12:43,944 then we reload the value of x here. So, you know, moving the value of x we you 121 00:12:43,944 --> 00:12:48,571 know, all around. So we load it, we store it, we load it again and this was a lot of 122 00:12:48,571 --> 00:12:53,369 wasted motion here and that's a result of this very simple cogeneration strategy 123 00:12:53,369 --> 00:12:58,282 where we want to be able to compose code together. We will be able to compose these 124 00:12:58,282 --> 00:13:02,830 templates in a way that it will work properly. This code does not have to be 125 00:13:02,830 --> 00:13:07,135 this inefficient in a lot of the techniques of what we discussed in 126 00:13:07,135 --> 00:13:12,023 sub-sequential lectures we talked about in a smarter code generation techniques and 127 00:13:12,023 --> 00:13:15,340 also optimizations like even improve the code further.