Problems visualing the stack in MIPS32![Resolved]

[voidflux]

Hello everyone i'm having problems visualing this stack. I'm use to a stack that grows upward, First one in, last one out. But its the opposite in this case, the stack grows downward, not upward.

We have the following code:

int leaf_example (int g, int h, int i , int j)
{

int f;
f = (g + h) - (i + j);
return f;
}

WHat is the compiled IMPS asm code?

THe parameter variables g, h, i , and j correspond to the argument registers $a0, $a1, $a2, and $a3, and f corresponds to $s0. The compiled program starts with the label:

leaf_example:

THe book says
the next step is to save the registers used by the prodedure. Thus, we need to save 3 registers.
$s0, $t0, and $t1.

What I don't understand is, why don't u need to safe the arguments as well? like $a0, $a1, $a2, and $a3?

This is the part that really confuses me though:
We "push" the old values onto the stack by creating space for three words on the stack and then store them.

addi $sp, $sp, -12 #adjust stack to make room for 3 items
sw $t1, 8($sp) #save registers for use afterwards
sw $t0, 4($sp)
sw $s0, 0($sp)

Why did u they add -12 to the stack pointer?
Why not 12?
I know each word is 4 bytes, so 4*3 = 12.

but if the stack grows downward, does that mean this is what the stack looks like after addi $sp,$sp, -12
[ ] <- $sp location -12
[ ] -8
[ ] -4
[ ] 0

but they don't use sw $t1, -8($sp) but instead use postive values, sw $t1,8($sp).

It says in the book,
Historical precedent, stacks grow from higher addresses to lower addresses. This convetion meanse that you push values onto the stack by subtracting from the stack pointer. Adding to the stack pointer shrinks the stac, thereby popping values off the stack.

So when they say, you "push" values onto the stack by subtracting from the stack pointer, do thy mean, since the stack point is at location -12, if u add 8, ur really subtracting since -12 is negative. and your adding a postive number to it?




[ ]

[CornedBee]

Whee, lot's of questions.

OK, first the register stuff. Architectures specify an ABI, an application binary interface. It specifies how, on a binary level, the application must behave outwardly. This especially concerns the interface between various compiled libraries and executables.
The ABI specifies the memory layout (like that stack growing up- or downward), the calling convention, and some other stuff. The calling convention is what interests us here.
A platform can have more than one calling convention. Let's take, for example, the x86 platform. Typically, you have two important calling conventions in Win32. There's the C (cdecl) convention, where arguments are pushed on the stack from last to first, and the caller is responsible for cleaning the stack. And there's the PASCAL (stdcall) convention where arguments are pushed from first to last, and the callee is responsible for the cleanup.

The ALPHA architecture, which by what I've seen is very similar to MIPS, has the following convention:
Arguments first fill up the argument registers (a0 - a5, alias $16 - $21), and then are pushed from last to first, I think. There's a total of 32 registers, 4 of which always have special meaning (3 more can have). In the remaining 28, $0 (v0) is the function result, the mentioned a* registers are for parameter passing. There are 7 callee-saved registers (s0 - s6) and 14 temporary caller-saved registers (t0 - t12, AT).
What does caller-saved respectively callee-saved mean? It indicates what state the register is in after a call. Take a simple function call on an Alpha:

lda sp, -8(sp) # Create stack frame
stq ra, 0(sp) # Save return address
jsr ra, callee # Call function

What state are the registers in once the call returns?
Well, all callee-saved registers are in the same state as before. The callee must guarantee that, either by not using them or saving them before use and restoring them afterwards.
The caller-saved registers, on the other hand, are in an unknown state. The callee can have done whatever it wants with them. If the caller wants their state preserved, it must save them itself, which is why they are called caller-saved.
Caller-saved registers are also known as temporary, callee-saved simply as saved.

So now you know why you need to save some registers. I should point out that I doubt that $t1 and $t0 are callee-saved (the t most likely stands for temporary) and that you need to save them. I think you only need to save $s0. The argument registers are definitely temporary, so you don't need to save those, either.

I'll start a new post for the stack stuff.

[CornedBee]

Ah, stack layout. Let me start by explaining the historical precedent for a downward-growing stuff. It's always useful to know why things are so complicated.

Early computers didn't have much memory, and that which they had, they had to divide into some areas: the program code, the free store, and the stack.
Typically, the program code would be loaded into very low addresses, usually just above the OS code, which started at address 0 or close to there. The free store, due to its nature, could be anywhere and didn't present a problem. But the stack needed space to grow. It needed to be at one of the two ends of the remaining space, as any gap would be wasted memory.
Placing it on top of the program code and let it grow upward would pose some problems, mostly with loader-to-program jumps: the loader, which itself is a program with a stack, would need to temporarily relocate its own stack, which would probably lie just above its program code, i.e. the best place for it to load the program's code. Then it would need to create a new stack for the program and somehow modify the stack pointer just as it calls the program's entry function. And on program exit, this process would have to be reversed.
Very complicated. It's much easier to just put the stack on the other end of the address space, where it gets in no one's way.
So this is why the stack grows downward. Now let's take a closer look at what that means.

Here's memory. For simplicity, I'll address them word-wise, i.e. multiply the values here by 4 to get "real" addresses. The computer has 1000 words of memory (4k is enough for everyone ). The stack grows from 1000 downward. A few bytes have been used by earlier functions, so here is what a segment of the memory looks like before the function call.

980 <undefined>
981 <undefined>
982 <undefined>
983 <undefined>
984 <undefined>
985 <undefined>
986 <undefined>
987 <undefined>
988 'x' <local of current function> <-- $sp
989 3 <local of current function>
990 214 <return address of current function>

$sp = 988

Now the call to leaf_example is prepared and executed. For this, the return address is pushed on the stack.

980 <undefined>
981 <undefined>
982 <undefined>
983 <undefined>
984 <undefined>
985 <undefined>
986 <undefined>
987 280 <return address of leaf_example> <-- $sp
988 'x' <local of current function>
989 3 <local of current function>
990 214 <return address of current function>

$sp = 987

Enter leaf_example. It makes some space on the stack for the callee-saved registers and its own local variables. For this, it subtracts 3 from $sp (12/4 in your example).

980 <undefined>
981 <undefined>
982 <undefined>
983 <undefined>
984 <undefined> <-- $sp
985 <undefined>
986 <undefined>
987 280 <return address of leaf_example>
988 'x' <local of current function>
989 3 <local of current function>
990 214 <return address of current function>

$sp = 984

Finally, it stores the values, with positive offsets because of where $sp points now:

sw $t1, 2($sp)
sw $t0, 1($sp)
sw $s0, 0($sp)

980 <undefined>
981 <undefined>
982 <undefined>
983 <undefined>
984 0 <previous value of $s0> <-- 0($sp)
985 4692294 <previous value of $t0> <-- 1($sp)
986 3851 <previous value of $t1> <-- 2($sp)
987 280 <return address of leaf_example>
988 'x' <local of current function>
989 3 <local of current function>
990 214 <return address of current function>

$sp = 984

Clear?

[Al42]

Next time you're in a cheap diner (or all-you-can-eat restaurant), look at the way the plates are stored - last in-first out. That plate storage mechanism looks just like a CPU's LIFO stack.

[CornedBee]

Not quite. A large stack of plates differs from an OS stack in a few very important details, the most important of which is that you can read values from deeper in the stack in the OS stack, while accessing a plate in a plate stack is impossible without taking off all the plates above. That more closely resembles the stack of a stack-based language, such as the theoretical Java Virtual Machine, or the Flash ActionScript execution context.

Besides, the OP didn't ask about the theory behind LIFO, but about some details of the MIPS stack implementation.

[voidflux]

thanks a ton CornedBee that does make alot of sense now that I can see whats going on! You explain it alot better than the book does!