Transcript


Search in video
0:00
all right good afternoon everybody let's get started so welcome to 6a before
0:07
lecture ten procedures and stacks so in the last lecture we shifted gears from
0:14
combinational and sequential logic and started discussing and learning about
0:19
programmable architectures and in particular the RISC 5 instructions that architecture and so I Sabina described
0:26
last lecture remember that an ISA is basically two things it specifies both the set of storage locations that you
0:33
have in your machine so in the case of RISC 5 we had registers and you had
0:38
memory and it also specifies the set of instructions that essentially let you
0:46
manipulate and process data in these different locations and so you know we
0:51
saw there were computational instructions loads and stores to access memory and move data from and to
0:57
registers and memory and then control instructions to affect the path of execution throughout the code so what
1:05
we're going to do today is is dive deeper and essentially derive a
1:11
systematic procedure to translate high-level programs or programs we're in a high-level language into assembly
1:19
right and so this this procedure this method is called compilation and is what
1:24
a compiler does all the time automatically we're going to do this in three different parts so first we'll
1:31
take a look at how to compile simple code fragments and things like individual expressions conditional
1:38
statements like even if else and then loops like while for and so on
1:43
and then we will spend the second part of the lecture essentially looking at
1:50
how to compile procedures of subroutines function calls essentially procedures
1:55
are a key building block or the key building block of modern programs
2:01
they're essentially reusable code fragments and we'll see how we can essentially establish a convention that
2:08
lets us compile its procedure individually and have these different procedures understand
2:14
each other and call each other and finally we'll see how you know this all comes together by looking at how the
2:19
memory looks the memory of the machine looks during the execution of a program
2:25
okay so let's start with you know compiling simple code fragments and particularly with simple expressions and
2:32
so we'd already mention how to how to do this in a good degree last time but
2:38
basically let's let's go through it again as a reminder so if I give you
2:43
some high-level code right that just has some segments like this one over here this is this is some C code where X Y
2:51
and C are 32-bit integer values and there are some expressions that assign
2:57
you know some computations to Y and C so
3:03
basically what you have to do to produce to translate this to assembly is essentially we need to assign the
3:10
different variables different registers and then we'll go translating the different operations one by one right so
3:16
you know we don't have an instruction that can do all these operations or at once but we do have instructions that
3:22
let us do you know most binary operations so one by one will go translating those into individual risk
3:29
five instructions by the way I mentioned compiling into high-level languages you
3:35
know it'd be great if we could compile Python into assembly unfortunately Python has several features that are not
3:43
that make it hard to compile so for example you know variables are not typed you don't have an explicit type and that
3:50
introduces a lot of complexity on the on the compiler side and in fact you know there are there are some techniques that
3:56
will let you compile parts of Python but these are far beyond the scope of of
4:02
this class and so the language high-level language that we're going to use is C C is essentially the most
4:08
widely used systems language and we're going to use a very small subset of C so
4:14
we'll we'll post a handout on the website that will very quickly give you
4:19
an overview of the subset of C that we will be using okay so starting from
4:25
these from this C code you know the first step is again we need to assign some
4:32
variables register for its variable and when we have complex expressions we also need some registers all temporaries
4:39
because sometimes we're going to need to store the result of part of these operations in in some location that's
4:47
not either of these variables and so then we can go essentially expression by expression
4:53
statement by statement compiling each individual operation right so for
4:58
example how would you compile X plus 3 so we say that X then Racer X then halls
5:05
variable X can anybody tell me what instruction you would use to compute X
5:11
plus 3 all right yes so we can take our
5:17
I you can write a die into X 13 which is
5:22
one one temporal register one of our temporal registers and a source operands
5:28
we use extend right and then the immediate three right so because three
5:33
is a small constant we can write it directly in the instruction so let's go
5:40
to this other side so how do you compute y plus one two three four five six
5:47
can I write a die let's say x 14 X 11
5:53
one two three four five six is there any problem with that
6:03
right exactly so remember that these constants these
6:10
instructions with an immediate operand only have 12 bits to support you know to
6:16
encode the immediate and so if you have something that's smaller than minus 2048 or larger than 2047
6:23
we need some other way to load the value into a register the value our register first
6:28
and so one convenient way that risk five risk five assembly has to do this is
6:34
through the load immediate pseudo pseudo instruction and so we basically can
6:39
write load immediate x14 one two three four five six and that will put this
6:45
32-bit constant into X 14 and then we can use a normal our instruction
6:50
remember that the difference between our I and add is that I operates on a
6:55
register and an immediate encoding encoded directly directly in the instruction add operates on to register
7:02
sources and produces the result in a different register okay now we have
7:09
these two parts of the expression how do we put it all together can anybody tell
7:14
me how to execute this you know what instruction do we need to run this final or operation and produce the value into
7:21
the register that holds why
7:30
yes sorry
7:35
it is doing bitwise or so this is exactly like this back so so it's bit by
7:42
bit doing the or of both operands on both sides and so in this guy in this case
7:49
risk 5 has an or instruction we can use right essentially ordering the contents
7:56
of X 13 and X 14 and produce any result in register X 11 right okay how about x
8:04
times four unfortunately for us as
8:10
programmers but fortunately for us when we get to implement the risk 5 processor we don't have a multiply instruction and
8:18
so yes yes exactly very good so you can
8:24
shift left by two positions and that will multiply the number by 4 and then
8:32
we XOR with the contents of register Y and so we can do this with the XOR
8:37
instruction right so bitwise yes
8:55
thinks things are happening here yes so I am assuming that someone has already
9:00
stored something in them in X&Y yes so
9:12
you could yes but that would be three instructions so that it's it's nicer if
9:19
we can do it with one okay any other questions okay so if I give you some
9:28
straight line code that consists of simple consists of simple operations now you should be able to go on produce the
9:33
assembly for it right but what about conditional statements right what about constructs like if this expression where
9:43
we have some you know conditional expression and only if this expression
9:48
is true we will execute the body of the loop and so for this we can use a very
9:57
simple recipe very systematic recipe to translate this code into prescribed
10:02
assembly essentially you know we first compile this conditional expression
10:09
which we will return you know either true or false into X and some some
10:15
register which is some register to hold the result and then we do this branch instruction over here where if X n is 0
10:23
we will jump or we will branch to this end if location over here and otherwise
10:29
will fall through we will not take the branch and then we will run through the instructions following the branch which
10:37
essentially have the body of of the if right and so one thing to emphasize here
10:46
is you see this label right when whenever we we write this statement like
10:52
n if and then and then a colon basically an assembly this is a label and a label
10:57
is doesn't take any space it's just an abstraction for addresses it's simply because we
11:03
want to you know when we when we load values or when we branch to different
11:09
locations we want to represent the location in the particular location in the code in a more symbolic way you know
11:16
be it'd be very hard if we were to manually you know specify all the
11:23
offsets and all the addresses in all of the branches right and so assembly lets us do you know by by introducing this
11:29
notion of labels we can essentially code this in a simpler way right okay yes no
11:42
it can be anything it can be absolutely anything
11:47
yes tell goatees it's its although this in the end so okay so if I give you this
11:57
this seeker right this simple if statement if X is less than Y then you
12:05
store Y minus X into y how do we compile this so we can start following the
12:13
recipe and so if we say that X 10 holds X and X 11 holes why then what
12:21
instructions should we use you know we have the NDF label how do we compile
12:28
these different statements you might be thinking of a sophisticated way to do it but let's just first follow the recipe
12:34
so we're going to first compile this expression right X is less than Y we
12:40
have one instruction that gives us 1 if X is less than Y and 0 otherwise
12:48
yes it's goal said if less than right so we have a temporary x12 is 1 if X 10 is
12:56
less than X 11 right and then we put the branch like this one above right we
13:07
simply branch to end if if X 12 is 0 right and then we compile the body of
13:15
the loop y equals y minus x how do we do this one instruction can we use subtract
13:26
yes so we simply we can simply write sub X 11 X 11 X 10 right okay
13:35
can we do better there so that often
13:41
times you can actually combine the expression with the branch so R is 5 has
13:47
different branches and so in this case you basically want to branch if X is not
13:56
less than Y which is which means that if X is greater or equal than than Y right
14:02
so we have a branch if greater or equal instruction and so with a single instruction we can do the same thing so
14:09
sometimes you can do this optimization if your branch condition is simple not all the time ok yes
14:24
now this is simply an indentation thing so what you'll see is that we indent all
14:31
the instructions one one level and then the labels are not indented that's just
14:36
a matter of code style yep okay so if
14:41
else statements very much the same right instead of having so we have if some
14:48
expression we run if body otherwise if that expression is not true then we run
14:54
we run else body and so the way we can implement this is through a slight
14:59
variation of the template in the previous slide where we compile the expression just like before we branch
15:06
just like before and if we don't branch then we essentially run through the if
15:12
body but here you can see that we have two labels right so when we branch we're going to branch to the else part of the
15:19
loop and then once we go through the if body with brand unconditionally we jump
15:25
to ended right so there are two possible paths of execution through this code either you go through you fall through
15:33
these branches branch is not-taken in which case you go directly to end if and skip the else otherwise you go these
15:41
branch branches to the elf side of of the code and then you run only through
15:47
the else right any questions yes
15:59
sorry after he finishes el else you're
16:09
going to go down through el and live anyway right so you could you could write jump and if here but why would you
16:18
you're already you know by default you're going to execute instructions in sequence right ah yes we do because
16:31
whatever follows you know and if is whatever follows this code right so
16:40
whether you go through if or else you you want to run whatever's below here
16:46
right and so you want to when you're done with with the with the else part of
16:52
of Dave you want to go down right and keep executing instructions all right so
17:00
let's talk about loops so so far we've seen branches that essentially go
17:06
forward in a code to skip some some code but loops we compile using what we call
17:14
backward branches branches that jump back to code that we've executed previously and so the simplest loop in C
17:22
and you can then express all these other loops in terms of this loop is what we call the while loop so while the syntax
17:30
here is while this expression is true evaluate or run the body and then come
17:37
back and evaluate the expression again right and so this will loop until this
17:42
expression is false at which case we'll go to the code below and so the way we
17:51
can compile this is essentially by first just like before compiling the expression the conditional expression
17:57
into X N and then branching today to
18:03
this n wild label that follows the whole body of the loop we compile the body of the loop and then
18:08
we branch back to the wild label right so what this code is going to do is it
18:16
will run through this set of instructions a number of times and then
18:23
it will eventually come evaluate this expression see that it's false and jump
18:30
to an pile right okay can you do better
18:37
you know this is this is okay and this is very simple but every loop iteration
18:44
we actually are taking two branches right we're taking a conditional branch here and then we're branching back so in
18:52
steady state let's say that this loop runs for for a long time we're actually spending a long time you know we're in
18:59
steady state we're running two branches when in fact you can actually do it with one right and so to do it with one you
19:09
can flip the condition and and the body
19:15
so if you put the body of the loop first and then do the comparison
19:23
unconditionally jump back or conditionally branch back and at the
19:30
beginning first need to evaluate the condition so you jump to compare go through here and then go back to loop
19:36
and so on right so this is simply a trick to save you one instruction in steady-state and of course you know we
19:43
have one instruction one jump there but we only execute that jump at the beginning of them okay any questions yes
19:56
across across iterations so if the if
20:04
the body of the loop changes xn we don't care because we're producing a fresh value for xn here right so ok so so far
20:16
we've seen how to compile simple expressions let's move on to two
20:23
procedures so large programs always consist consist of multiple procedures
20:30
multiple functions or subroutines essentially a procedure is a fragment of reusable code that performs a specific
20:36
task so you can see one particular example with with GCD write this this
20:43
code implements Euclid's algorithm for finding the greatest common denominator between two integers and so you know
20:51
we've seen different combinations of GCD before but in this particular case you know you can you you already know how to
20:58
do this loop right this is else statement but you know what about
21:03
everything else right so basically we have multiple elements in this GCD
21:08
function there's that named entry point right this function has a name so that
21:15
other parts of the code other functions or subroutines can invoke it it has some
21:21
arguments or parameters in this case two integers a and B it also has some local storage we can define new variables x
21:29
and y which in this case we initialized a and B right and this will only be
21:35
visible to the code within this this procedure and finally when the procedure
21:42
finishes execution it returns control to the color and might return some values so in this case this GCD method or this
21:50
GCD procedure is producing some result that its source in X and when it's done
21:56
it returns it to whoever invoke this method okay so this is great for two
22:01
things right we can abstract the implementation details of you know
22:08
particular algorithms and then we can reuse them across many other procedures
22:14
and so for example we can write this bull Co Prime's function that returns
22:19
true if the GCD of a and B is 1 right if they have no common factors and so you
22:29
know you can then elsewhere in the program called Co primes with different arguments and it will do the right thing
22:34
and when you call Co Prime's you don't you're not concerned with whether this
22:40
uses GCD or what the implementation of GCD even is right we're essentially
22:45
abstracting the details of the implementation okay so there's two
22:52
general ways to implement procedures we can do essentially if we have a program
23:00
with multiple procedures one simple thing would be to inline them for every call that we find the compiler could go
23:07
and substitute the call with the body of the procedure right and so we'd end up
23:14
with one giant chunk of code that then we would we would run right okay so this
23:24
is actually what you expect that's right when talking about circuits but this in the context of programs this has a
23:30
couple of problems can anybody venture a guess like what what are we some issues of this approach
23:41
yeah so recursion is one big issue code
23:47
size is another one right if you have a procedure and you're using it a hundred times and you're gonna have a hundred
23:52
copies of the procedure so recursion is
23:57
is a more fundamental right so recursive procedures are procedures that
24:03
essentially invoke invoke themselves and so factorial here is is one simple
24:08
example so we can compute the factorial of some integer by multiplying by the
24:14
integer and then calling factorial of n minus 1 all right and so this is this is
24:19
a very simple very elegant implementation however you know if you were to try to do inlining here it turns
24:26
out that doesn't work not only because you'd end up in lining you know a lot of a lot of factorial calls but you don't
24:32
even know how many times to mean line because you don't you know how many times how many calls to factorial you
24:38
know are going to take place depends on the value that you call factorial with
24:44
so to solve this problem what compilers typically do or the default option with
24:51
compilers is what we call linking so we're going to produce separate code separate piece of code for each
24:57
procedure separate assembly for its procedure and then we're going to establish a colon convention that
25:03
essentially lets multiple methods call each other and interact with each other
25:08
in a very standard way so in this in this world essentially we're going to
25:15
have a caller and our Kali so the procedure that invokes a different procedure we call it the color
25:21
and the procedure being in call being invoked we call the colleague and so the
25:27
Kali is basically going to evaluate all the input arguments store them somewhere
25:32
where the colleague can receive can can read them and then transfer control to the to the Kali and then the Kali is
25:38
going to produce you know whatever results it needs and transfer control back to the caller when it's done ok any
25:47
questions so there are many issues and many
25:55
problems that we need to solve to do this correctly right so how can we
26:01
establish a convention that let us lets us reliably communicate arguments and return values across procedures how can
26:08
we transfer control between the caller and the callee also how should the
26:15
caller and callee share registers right we need some sort of convention that lets us know which registers are ok to
26:22
use and then if we need more registers than then we actually have how can we
26:28
let each procedure use more storage than we have available in the register file right and what are some conventions to
26:34
do that in a in a very orchestrated way and so you know to make sense of all of
26:42
these essentially each system will
26:47
specify its own calling convention right it's basically a set of rules that specify how procedures interact and one
26:56
of them both basic things of a coding convention is specifying their rules for register usage right you're going to
27:02
want to pass values pass arguments and results through some particular registers use or use some registers with
27:09
some particular semantics and so there are multiple dimensions here but one very important one is the difference
27:16
between what we call Coley saved registers and color saved registers so
27:21
Coley save registers are preserved across function calls right across
27:28
procedure implications so if you're we in a procedure in a function and you
27:34
invoke similar function you expect when that function returns that all call your registers locally save registers will be
27:41
as they where where for you called the the procedure right and so it's Kali
27:48
saved it called Kali saved because if the colleague wants to actually use the register it needs to save it it needs to
27:55
save its content somewhere else and really needs to restore those contents before returning control
28:00
and also you know by symmetry a color save register is not preserve records
28:06
across function calls so the collie is free to override that register and do whatever it wants with
28:11
it and that means that if the color one super service its contents that it needs to save that register or the value of
28:18
that register somewhere else and then load it back when it when it needs it right because there are no guarantees
28:23
that this value will be preserved so the risk five : convention actually not only
28:30
specifies which registers are Calise versus color saved but it actually gives
28:35
its register its you know it divides registers x 0 3 X 31 into groups and it
28:43
gives them different symbolic names that denote their function there's no their role in this in this calling convention
28:52
and so there are multiple classes here and there's a lot of information so here you know I'm gonna show you an overview
28:57
fairly quickly and then we'll go dissect the different parts but basically we have registers X 10 2 X 17 are arguing
29:08
symbolic names a 0 to a 7 and they're used to pass arguments so we'll those
29:13
are the registers that will put arguments into when we want to invoke some other procedure and then from those
29:19
registers a CRNA 1 are also used to return values so when the when the Kali
29:25
is done it will store the result in those two registers we also need to
29:30
figure out how do we control transfers and the important thing there is you know when you invoke a procedure when a
29:37
caller invokes a colleague it also needs to tell the Kali where to jump back once it's done right and so we'll use
29:43
register x1 which we renamed as RA for return address to store the address that
29:50
we want to go back to there's also two other classes of registers that we will
29:55
use for internal storage within the procedure so we have registers T 0 to T
30:00
6 and s 0 to s 11 the difference between these two classes is that these the the
30:06
T registers are caller saved and the S registers are Coley saved they are preserved across function
30:13
calls and finally there are some registers that have you know different
30:18
different use it so the stack pointer we will see in a few slides and then we have the global pointer thread and
30:24
thread pointer which are constant so there are neither Coley saved nor caller saves because they're not supposed to be
30:30
written to and finally the ABI or the calling convention also specifies that you know you can instead of so as you've
30:38
seen x0 is hardwired to zero every time that you read x0 you're gonna get the value 0 so they might as well call it
30:44
zero rather than x0 okay so just as an example if I give you an
30:51
instruction at t0 s 3 a zero what does this mean right can you give me an
30:58
equivalent instruction with registers X 0 to X 31 so what is what is registered
31:09
t0 in this case looking at this table right and so you can go register by
31:16
register and essentially translated back to the actual register in this right
31:24
okay so to call a procedure basically we
31:29
or the caller first places all the arguments in in registers a phase 0
31:34
through a 7 and then it transfers control to the colleague and to transfer
31:40
control to the colleague we have this helpful instruction called jump and Link register right so we have jump and Link
31:49
is the actual instruction right this instruction stores PC plus 4 to whatever
31:56
destination register we give it and then it jumps to some label you know the
32:03
contents of the location to some location in the code so we generally
32:09
want to abstract the fact that we're
32:15
using array and so you you'll often see our aving omitted so when you see jump
32:21
and link to label this translates to the instruction and jump and Link are a label
32:26
okay then the collie runs on places the results in registers AC or on a one
32:34
maybe that's not pretty any result in which case it's not going to override these registers anyway in any way but
32:40
now the key thing is we're gonna use the value of register R a which remember
32:46
stores PC plus 4 from from the color right the instruction following the jump and Link instruction and we do this with
32:53
essentially this jump and Link register instruction right so the jump and Link register instruction has these semantics
33:01
and so in our particular case we don't actually need to store anything in Rd
33:07
because we don't care about the address that we're using so you know that the
33:14
address that we're currently ad we care where we're jumping back and so we'll right jump on link register 2 X 0 and
33:22
then RS 1 basically is yeah the source register that we want to jump to so this
33:29
is this is commonly abbreviated as jump register and because we don't even want
33:36
to see our a here we'll just right red which translates to jump register our a
33:42
which translates to jump and Link register X 0 0 alright and so although
33:47
this is a fairly complicated dance of pseudo instructions the point is that you know the important point here is
33:54
that when you talk when when you write jump on link and read you need to
34:00
remember that you're actually writing and reading register RA ok so let's see
34:06
this with with a concrete example suppose that we have code for the color here right so this is a very simple
34:15
color that you know takes X set sets X to 1 Y 2 2 and then calls some of x and
34:24
y of x and y and once the result in variable C so we can compile this
34:33
expression by essentially loading immediate 1 into a 0
34:39
- into a one right which are the first and second arguments of the some
34:44
procedure and then running jump and link to some and then what the procedure the
34:51
some procedure will return control to the instruction following this one right
34:57
with the right value stored in a zero now we already have Z in a zero so we
35:04
need to load a one with value two again and then we can again jump on link to
35:10
some and that is it that's how you compile this code now some has a very
35:16
simple implementation so basically we take both arguments is you run a 1 and
35:22
store the result in a 0 and then we simply return so what's going on here is
35:27
each invocation is returning control to the right address so we're invoking this procedure twice
35:33
so this jump and Link is storing PC plus 4 the address of this instruction in RA
35:41
and then some you know when it runs this read instruction here is jumping back to
35:47
this li instruction and then when the caller keeps going and calls
35:55
jump on link some again then some is returning to the instruction following
36:01
this second call to some right so this return address allows a single procedure
36:06
to return to whoever invoked it yes
36:14
both a 0 and a 1 are also result registers so you can use a 0 through a 7
36:21
for arguments and you return results in a 0 to a 0 and a 1 right so in this case
36:29
we expect the result to be in a 0 just by the calling convention ok question
36:34
yes if that Colie does not preserve a
36:47
Calise register then basically in general all hell breaks loose so follow the convention because you know
36:54
difference here you know between this and Python is that there are no no seat
37:00
belts here so if you if you start getting wrong addresses you know or
37:06
wrong values all bets are off in general this is different from the
37:19
processor right this is this is a convention that you know different systems will in fact have different
37:24
conventions so this is the risk 5 you know the risk 5 designers also establish
37:29
this convention but some other architectures have different conventions so for example if you look at x86 Linux
37:35
has a different convention from Windows and Windows has different three different conventions and it's all it's all MS but you know it's not tied to the
37:43
processor C compilers enforce it but when you start compiling with different
37:50
conventions there's there's a lot of there are a lot of problems
37:58
if you if you wrote everything and you chose a different convention yes but you
38:03
will lose the capability of linking to any other code that's produced by a compiler okay so one important need here
38:11
so you know here the caller is loading 2 into a 1 again why yes exactly exactly
38:24
because some is unknown to the caller right sound for all we know could be
38:31
over writing a 1 could be overriding open color save registers and so we need
38:36
to load a 1 again even though you know if you look at the whole code you'll sleep well a 1 it's not being modified why are we loading it again but again
38:43
the color the color doesn't know anything about the Akali ok so the last
38:49
problem that we need to solve is that procedures often need store it's beyond registers so registers in general are
38:57
not sufficient to support arbitrary
39:02
sequences of calls among procedures and so these these extra storage needs might
39:10
happen because you need to save Kali save registers or you need to save color
39:16
save registers or because you need to pass more arguments or results than fit in in 8 or 2 registers or that you know
39:25
because you need to store a large amount of local data that doesn't fit in registers and so in general you know one
39:32
thing to take into account is that you know of course the general solution is going to be well if it doesn't create
39:37
registers use memory but one simple thing you might think about is hey what
39:43
why not for each function specify some storage right then that the function can use its time it runs you know some fixed
39:50
addresses in in our program well the problem with that is that you can call
39:55
the same method multiple times right so for example we have a recursive method you know you can't have some
40:03
fixed locations all right because that storage is not associated with the procedure it needs to be associated with this
40:09
specific invocation of the procedure with the specific activation of a
40:14
procedure but the good news is that we only need to access the local storage of
40:20
the currently executing procedure and once we're done with that procedure we can basically just throw all those
40:26
procedures procedure local storage all those variables away we can discard them
40:31
safely and so the right data structure to do this is a stack right because we
40:37
have a stack of procedure invocations we're going to use a stack to store this extra data and so a stack is a lasting
40:45
first out queue so basically you can push data into a stack right you can pop data you can pop the top element from
40:51
the stack and then you can access the top element so different architectures
40:57
have many different conventions to access the unit to access the stack so
41:03
for example x86 will have specific instructions to push and pop data but you know we're gonna do something much
41:10
much more simple on essentially we're just gonna keep this stack in a pretty
41:17
specified and pre-allocated reasoning memory that's so the only thing that we need is essentially a register to point to it we're going to call these the
41:24
stack pointer which if you go back to the table before that's register x2 and
41:31
by convention we're going to have a stack that grows down which we call this
41:37
convention growing down because it goes from higher to lower addresses right so you know one weird thing is because we
41:44
represent memory with lower addresses at the top and higher addresses at the bottom of course you know you can see
41:50
that the stack is growing down right that's all very logical so as you push
41:56
you know you you start using lower addresses and so again this can be a bit
42:01
confusing because it looks like it's going up but we say that it's going down so we have the stack pointer pointing to
42:10
the last element we pushed the last valid location of the stack and then
42:17
every time we we push we're going to decrease the stack pointer and every time we pop we're going to increase the
42:24
stack pointer and we can use the stack anytime we need it but we're going to
42:29
follow a very strict discipline which is that whenever we use it we're going to leave it when we return control as we
42:37
found it so that then you know the the colleague or sorry that color can go
42:44
back to its own stack data so let's see how this works with a simple example
42:50
suppose that we want to use s 0 and s 1 which are called lis save registers within the implementation of these
42:56
procedures so this is the same sequence of instructions that I showed before in
43:03
the first slide but now we're using registers s 0 and s 1 through here right
43:11
and so we need to do something with the stack to be able to use these registers right we need to first save them to the
43:18
stack and then we store them before we return so we do the first you know we
43:24
save them essentially by first decreasing the stack pointer by 8 which
43:30
essentially allocates 2 words or 8 bytes of data on the stack and then we save s
43:36
0 and s 1 in the two locations that we just allocated right then at the end of
43:43
the execution we restore these values essentially we do the inverse procedure we load them from the locations that we
43:50
saved them to and then we restored the stack pointer to its all value by adding
43:55
8 to it right ok so pictorially this is how it looks like before the procedure
44:02
invocation you have some a new space in the stack right and then once the once F
44:09
starts running it stores you know it increases the stack pointer by 2 words or 8 bytes it saves as c1 it's one
44:16
then once it returns it has restored the stack pointer back to where it was and now these locations you know right when
44:24
it returns of course this locations still hold the old data but they might be overwritten
44:29
okay any questions so save or collusive
44:38
registers are one example of how to use the stack but there are other pieces of
44:43
data we need to store in the stack and in particular one important case is the return address if you have a nested
44:49
procedure so far we've seen calls to procedures that don't invoke other
44:55
procedures but suppose that you have a procedure that involves a different procedure like the Coe crimes one that
45:02
we showed at the beginning of the of the discussion of procedures so here you
45:09
know the compilation of this statement is is pretty simple we're essentially
45:14
calling GCD with the two arguments which are already a 0 and a 1 and then we're
45:21
comparing with with 0 and then returning if you know whether this this number
45:28
this whether the GCD call returns 1 right so the important part is not these three instructions but the fact that
45:35
this call to GCD over writes array and this return here needs the original
45:42
value of array so we need to save array in the stack right and how how do you do
45:49
this
45:55
this sorry sorry RA is the return
46:05
address remember that every time we invoke a procedure these return instruction or this return pseudo
46:11
instruction is actually jumping to the contents of the register all right and
46:16
so we need to save our a to the top of
46:23
the stack and then restore it before we return right okay so that's how we can
46:32
have procedures invoke other procedures while still keeping track of all the
46:38
stack of return addresses right where do we need to jump back once we're done so
46:44
in general you can have an unbounded number of of return locations
46:50
okay so recursive procedures are nothing special in this model once we've solved nested procedures recursive procedures
46:56
are just a special case of nested procedures so I give you these Fibonacci method here which essentially computes
47:03
the N Fibonacci number it invokes itself twice except if n is less than 2 and so
47:11
you can compile you know the easy case first so if n is less than 2 then you
47:17
directly temp 2 to return otherwise you
47:22
know this code implements these 2 calls using using some cohesive registers and
47:28
we need to in this particular case because we're using colleague safe register s0 and because we're using
47:35
because we're invoking Fibonacci or fib again we need to also save register RA
47:44
and we store it one word right okay so this again is another
47:54
instance of a very simple recipe whatever you need to save you know the beginning of the procedure you allocate
47:59
space for it in the stack you save it and then you restore it before you return now in general compilers use a
48:07
consistent stack frame convention which you do not need to learn but it it's useful if you're looking at a particular
48:13
stack dump if something has gone wrong in the program to know how the different
48:18
pieces of data are stored so basically for each function invocation if we need
48:24
arguments that don't fit in the stack we will get them from the color in the stack and then the column will store
48:32
first the saved argument registers then the save return address then any local registers and then any other any other
48:39
saved s registers and then any other local variables that don't fit in
48:45
registers and basically when the procedure is done we unwind the stack
48:50
you know we we store the stack to the stack pointer to where it was before we call it okay so just to wrap things up
48:56
to put it all together you know we've talked about the stack and the stack occupies a region in memory but there's
49:02
basically three different kinds of storage in in most programs including C
49:09
and including Python and so the stack holds data used by procedure calls we
49:15
also have typically some static data that's essentially active and exists
49:20
during the whole execution of the program these are things like global variables and finally we have data that
49:26
survived Sakura's procedure calls but doesn't necessarily exist for the whole
49:32
lifetime of the program and so this is starting what we call the heap and so this data needs to be dynamically
49:37
allocated and different programming languages have very different conventions on how they allocate it so
49:43
in C and C++ and there are low-level languages we have what we call manual memory management where every piece of
49:51
dynamically allocated data that is you know every chunk of data needs to survive across procedure calls needs to
49:57
be explicitly allocated I'm free by calling this case Malcolm three two meters that are provided to you by you know some
50:03
low-level runtime but most of their languages essentially do automatic
50:10
memory management so you can create any objects like you know writing equals dick in Python but the system will free
50:17
them automatically so you don't need to concern yourself with when this variables fall out of scope and finally
50:23
the text region holds the program code so in RISC five main memory is laid out
50:30
this way so Ted the text region starts first starting at address zero and then
50:35
the static and heap the static region and the heap region are cons are allocated consecutively the heap grows
50:42
down towards higher addresses and then the stack is allocated at the end of the address space and grows up towards lower
50:48
addresses so basically you can have both a bunch of stack and a bunch of heap
50:53
without then conflicting until you use your whole space and then you know these three pointers that I mentioned before
50:59
so the stack pointer always points to the top of the stack the global pointer points to the static region so that we
51:05
know what global variable how to access global variables and then the program counter will be somewhere in the text
51:12
region all right that's all for today next lecture will start actually seeing
51:18
how to implement a risk five processor that executes your risk by programs good luck on the quiz