In this lab we discuss subroutine structure. As you know, subroutines and functions are the primary mechanism for building programs out of smaller blocks. They also provide a means to interface programs to the operating system and program library. In assembly language, any program label can be a subroutine. Thus, any label you can jmp to, you can alternatively call as a subroutine. The difference is that when you call a subroutine, the computer saves the return address, so that later when a ret instruction is executed, the program returns to the instruction immediately after the call. Furthermore, the computer allows you to ``nest'' subroutine calls. This means one subroutine can call another, which in turn calls another, and so on. Each time a subroutine returns, it only returns to the subroutine that called it last. This is done by placing the return addresses in a special data structure called a ``stack''.
A stack can be though of as a data storage mechanism that has two basic functions: ``push'' and ``pop.'' Push adds a new data value to the data structure, and pop removes a data value. What makes a stack a stack is that the push and pop follow a ``last-in, first-out'' policy. Thus, if you push the numbers 10, 34, and 9 onto a stack, and then pop the stack three times, you will get the numbers 9, 34, and 10, in that order. The way this is used in implementing subroutines is as follows. Imagine that we have a program that has a call instruction at address 100 that jumps to a subroutine at address 200. When the call is made, the return address, which is the address 104 (the address of the next instruction after the call) is pushed on the stack. Now suppose that this new subroutine has a call instruction at address 220 that jumps to a third subroutine at address 300. When this call is made, the return address 224 is pushed onto the stack. Now, when this third subroutine executes a ret instruction, it pops the stack, which provides the address 224, so it returns to the second subroutine. When THAT subroutine executes a ret, it pops the address 104, so it returns to the first subroutine.
To implement subroutines in assembly language, all you really need is program labels, the call instruction and the ret instruction. However, there are a lot more things one can do. First of all, let's consider the stack where the return addresses are stored. The stack is just a section of memory. Exactly which memory is used is determined by the stack segment %ess register. In order for the stack to operate correctly, we need to know where the ``top'' of the stack is. The top of the stack is the location where the last value pushed (and the next value to be poped) is stored. This is determined by the stack pointer %esp register, which is an offset from the stack segment register, just like the instruction pointer is an offset from the code segment register. The stack pointer initially points to the highest address in the stack segment. When a push is performed, the stack pointer is first decremented, and then the value to be pushed is written into the location pointed to by the stack pointer. When the stack is poped, the location pointed to by the stack pointer is first read, and then the stack pointer is incremented. Here is the sequence of steps if we pushw $1000:
0| | <- %ess
4| |
8| |
12| |
16| XXXX | <- %esp before push
________________________________________
0| | <- %ess
4| |
8| |
12| | <- %esp first decrement SP
16| XXXX |
________________________________________
0| | <- %ess
4| |
8| |
12| 1000 | <- %esp finally, write 1000
16| XXXX |
Pops work just the opposite:
0| | <- %ess
4| |
8| |
12| 1000 | <- %esp before pop
16| XXXX |
________________________________________
0| | <- %ess
4| |
8| |
12| | <- %esp first read 1000
16| XXXX |
0| | <- %ess
4| |
8| |
12| | finally, increment SP
16| XXXX | <- %esp
Note that although the value 1000 seems to ``disappear'' from the stack,
in fact, as with most memory, that value is still there until something is
written over it. The value is removed from the diagram to make the point
that it is read from memory BEFORE %esp is adjusted.
The stack is used to store return addresses for subroutines, as has been pointed out, but it can also be used to store data for your program. The instructions call and ret are like a combination of a push or a pop and a jmp, but you can also perform push and pop operations directly with the push and pop instructions. In each case, data is moved between the stack and a register (specified as an operand) and the stack pointer is adjusted. The only concern is that the call and ret insructions can't tell if you have been pushing and poping, so if you push a value, and the do a ret without first poping the value, the ret instruction will pop the wrong value, and who know where your program will end up. Simillarly, if you pop the return address before you execute the ret, then you will return to the wrong place (actually you will return - not to the routine that called the current routine, but to the routine that called THAT routine). Thus, you must be very careful when you do pushes and pops.
Why would we want to push and pop anyway? The answer is the same reason we need to push and pop return addresses. Sometimes we need to store data for a subroutine while another subroutine is executing. For example, suppose we are executing a program, and we have some intermediate data stored in a register when we want to call a subroutine. We don't want to leave it in the register, because the subroutine might need that register, but we don't want to put it into our data memory, because it is not a variable, it is just some intermediate value. In this case we can push the register before we call the subroutine, and when the subroutine returns, we can pop it off again as follows:
.
.
pushl %eax
pushl %ebx
call my_routine
popl %ebx
popl %eax
.
.
Now the subroutine is free to modify any of the registers it chooses. In
fact, even if we aren't going to call a subroutine, but we need to store
an intermediate value because we have run out of registers, we can use the
stack as a temporary storage location in the same way. Many times, when we
write subroutines, we want to be sure that no matter what data is in the
CPU registers, that data is not changed when the subroutine returns. In
this case, the programmer may routinely push all registers his subroutine
is going to use before doing anything else, and then pop them all
again just
before returning. This way, we never have to push and pop before we call
the subroutine. The subroutines in some of our previous labs included this
code.
Finally, we come to the most complicated part about subroutines and the stack: local variables and parameters. In high level languages like Pascal and C, procedures and functions can have variables that are only visible inside of the procedure. In C, all blocks, like the bodies of for and while loops can also have local variables. The interesting thing about these variables, is it is possible for there to be more than one ``instance'' of these at any given time. This happens whenever a procedure calls itself. In this case, each instance of the procedure has its own copy of the local variable. This is done by putting the local variables on the stack. To support this, the 8086 includes a special base register that can be used to access the stack: the %ebp register. The %ebp register points to the stack, just like the %esp register, but it can be used as a base register just like the %ebx register. The %ebp register is typically used with the %esp register to set up what is called a ``stack frame'' which contains data for a single subroutine. Basicly, when the subroutine is entered, storage for all local variables is allocated on the stack by decrementing the stack pointer. The base pointer is set to point to the space, and each local variable is accessed as a constant offset from the base pointer. Here is an example:
main()
{
int a, b;
a = 10;
doubleit();
b = a;
}
doubleit()
{
int c, d;
c = 20;
halfit();
d = c * 2;
}
halfit()
{
int e, f;
e = 20;
f = e / 2;
}
Translated into assembly code, this looks as follows:
main: pushl %ebp
movl %esp, %ebp
subl $8, %esp;
movl $10, -4(%ebp) ; a
call doubleit
movl -4(%ebp), %eax ; a
movl %eax, -8(%ebp) ; b
movl %ebp, %esp
popl %ebp
ret
;
doubleit: pushl %ebp
movl %esp, %ebp
subl $8, %esp;
movl $20, -4(%ebp) ; c
call halfit
movl 4(%ebp), %eax ; c
shll $1, %eax ; c * 2
movl %ex, -8(%ebp) ; d
movl %ebp, %esp
popl %ebp
ret
;
halfit: pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl $20, -4(%ebp) ; e
shrl $1, %eax ; e / 2
movl %eax, -8(%ebp) ; f
movl %ebp, %esp
popl %ebp
ret
Notice that all of the references to the local variables become an offset from
the register %ebp. The first variable is %ebp minus 4, the second
variable is %ebp minus the size of the first variable plus 4,
the third variable is the %ebp minus the size of the first variable plus
the size of the second variable plus 4, and so on.
Let's look at the stack for this example.
| |
| RA | <- %ebp before main begins
| |
| | <- %esp
As with all subroutines, when main begins, the stack pointer points to the
return address. Next, we need to save the contents of the base pointer, so
that when we return, it will be correct for the previous subroutine. Next, we
set the base pointer to the current position of the stack pointer. The
local variable area will be right on top of the old base pointer value.
We see now
why the first local is %ebp minus 4, because %ebp points to the
the old value of %ebp. Next we need to move the stack pointer so
that subsequent
pushes won't overwrite the local data area. We do this by subtracting the
size of the local data area from the stack pointer. For main, there are
two integers, each of which is four bytes, so we adjust the stack pointer by
eight. After this, the stack looks as follows:
| |
| |
b | | <- %esp
a | |
|OLD_BP| <- %ebp
| RA |
| |
Notice that the stack pointer points to b. This is OK, because a push
will first decrement the stack pointer before data is written. Now subroutine
main begins, and we can see that %ebp minus 4 is a and %ebp
minus 8 is b. When we come to the call to doubleit, the call
instruction pushes the return address, so we have the following situation
at the beginning of subroutine doubleit:
| |
| RA | <- %esp
b | |
a | 10 |
|OLD_BP| <- %ebp
| RA |
| |
Now the process start over again, we save %ebp, set it to %esp and
then adjust %esp to get the following:
d | | <- %esp
c | |
|OLD_BP| <- %ebp
| RA |
b | |
a | 10 |
|OLD_BP|
| RA |
| |
and subroutine doubleit begins.
Once again, when halfit is called, the
same pattern repeats:
| |
| RA | <- %esp
d | |
c | |
|OLD_BP| <- %ebp
| RA |
b | |
a | 10 |
|OLD_BP|
| RA |
| |
And halfit performs a similar set of steps:
| |
f | | <- %esp
e | |
|OLD_BP| <- %ebp
| RA |
d | |
c | 20 |
|OLD_BP|
| RA |
b | |
a | 10 |
|OLD_BP|
| RA |
| |
| |
Now, when halfit returns, we need to restore the stack to the way it was
right after halfit was called, so that when the ret instruction is
executed, we will return to the state that doubleit was in. To do this.
we first have to restore the stack pointer. Right after halfit was called,
the stack pointer was pointing to the return address, and the base pointer
was pointing to the old base pointer from main. To do this, we first make
the stack pointer point to the base pointer, and then pop the base pointer,
which moves the stack pointer to point to the return address, and the base
pointer to its old position, and voila! We are ready to return!
| |
f | |
e | |
|OLD_BP|
| RA | <- %esp
d | |
c | 20 |
|OLD_BP| <- %ebp
| RA |
b | |
a | 10 |
|OLD_BP|
| RA |
| |
| |
After returning to doubleit,
the same steps prepare us to return to main
and so on, until the program is finished.
As we discussed in lab4, pointers generally use the %ebx register. We saw this in the different addressing modes. Notice that during your functions up until now you have been modifying the A, B, C, and D registers without saving their state prior to your function was called. We generally assume that the calling function has saved whatever they want saved. However, for some reason, the %ebx register is NOT saved in this way. This is why sometimes you may have seen segmentation faults at the end of your code even though it seemed to function correctly. We have attempted to fix this by changing the prolog and epilog to save the state and return the state of the B register. Therefore, while the saving and recovering of the %ebx register are not part of setting up a stack frame (which is what the prolog and epilog are doing) we show it here prevent this segmentation fault from occurring.
To summarize, we always begin a subroutine with a ``prolog'' which sets up our stack frame with the following three instructions:
subr: pushl %ebp
pushl %ebx
movl %esp, %ebp
subl $SIZE_OF_LOCAL_VARS, %esp
Similarly, just before we return from a subroutine, we execute an ``epilog''
to tear down the stack frame with the following two instructions:
movl %ebp, %esp
popl %ebx
popl %ebp
ret
Finally, we reference the local variables as a constant offset from the
base register. In addition, the prolog and epilog should push and pop any
registers that will be modified by the subroutine. This is done after
adjusting for space for the local variables. If any C routines are used,
C requires that %esi and %edi be saved, so those registers
should always be
pushed if they will be used, even if your program isn't using them.
/* begin assignment specification code lab5asm.s */
/* Convert the procedure exactly as given using the local variables
local_var and temp_var, not register variables */
void Fib(void)
{
int local_var;
int temp_var;
local_var = global_var;
if(local_var == 0) return;
else if(local_var == 1) return;
else {
global_var = local_var - 1;
Fib();
temp_var = global_var;
global_var = local_var - 2;
Fib();
temp_var = temp_var + global_var;
global_var = temp_var;
}
return;
}
/* end assignment specification code lab5asm.s */
----- BEGIN C CODE -----
/* begin driver code lab5drv.c */
/* This is the skeleton C program. It will input a number, then
* print the Fibonacci sequence up to that number.
* NOTE: You will need to use the stack for the local variables local_var
* and temp_var of the function Fib(). global_var is a global variable.
*/
#include <stdio.h>
int main(void);
void Fib(void);
int global_var; /* this is a GLOBAL variable */
int main(void)
{
int i;
int number;
int fib_subscript;
printf("Please enter a number: ");
scanf("%d",&number);
printf("Fibonacci sequence from subscript 0 to %d :\n", number);
for(i=0; i<=number; i++) {
global_var = i;
Fib();
fib_subscript = global_var;
printf("%3d ", fib_subscript);
}
printf("\n");
}
/* end driver code */
----- END C CODE -----
----- BEGIN ASSEMBLY CODE STUB ----- .globl Fib .type Fib,@function Fib: /* prolog */ /* put code here */ return: /* epilog */ ret ----- END ASSEMBLY CODE -----
Please enter a number: 1 Fibonacci sequence from subscript 0 to 1 : 0 1 [tung]~...fib > ./lab5 Please enter a number: 2 Fibonacci sequence from subscript 0 to 2 : 0 1 1 [tung]~...fib > ./lab5 Please enter a number: 3 Fibonacci sequence from subscript 0 to 3 : 0 1 1 2 [tung]~...fib > ./lab5 Please enter a number: 4 Fibonacci sequence from subscript 0 to 4 : 0 1 1 2 3 [tung]~...fib > ./lab5 Please enter a number: 5 Fibonacci sequence from subscript 0 to 5 : 0 1 1 2 3 5 [tung]~...fib > ./lab5 Please enter a number: 6 Fibonacci sequence from subscript 0 to 6 : 0 1 1 2 3 5 8 [tung]~...fib > ./lab5 Please enter a number: 7 Fibonacci sequence from subscript 0 to 7 : 0 1 1 2 3 5 8 13 [tung]~...fib > ./lab5 Please enter a number: 8 Fibonacci sequence from subscript 0 to 8 : 0 1 1 2 3 5 8 13 21 [tung]~...fib > ./lab5 Please enter a number: 9 Fibonacci sequence from subscript 0 to 9 : 0 1 1 2 3 5 8 13 21 34 [tung]~...fib > ./lab5 Please enter a number: 10 Fibonacci sequence from subscript 0 to 10 : 0 1 1 2 3 5 8 13 21 34 55
----- BEGIN ASSEMBLY CODE SOLUTION ----- .globl Fib .type Fib,@function Fib: /* prolog */ pushl %ebp pushl %ebx movl %esp,%ebp subl $8,%esp /* put code here */ movl global_var, %eax movl %eax, -4(%ebp) cmpl $0,-4(%ebp) je return cmpl $1,-4(%ebp) je return movl -4(%ebp), %eax subl $1, %eax movl %eax, global_var call Fib movl global_var, %eax movl %eax, -8(%ebp) movl -4(%ebp), %eax subl $2, %eax movl %eax, global_var call Fib movl global_var, %eax movl -8(%ebp), %ebx addl %ebx, %eax movl %eax, global_var return: /* epilog */ movl %ebp, %esp popl %ebx popl %ebp ret ----- END ASSEMBLY CODE -----