MIPS - How does MIPS allocate memory for arrays in the stack?

Question

I'm quite new to the MIPS assembly language and am currently taking a class on computer architecture which has a large section on MIPS coding. I've studied several other high-level programming languages (C, C#, Python) in the past so have some bases in programming.

My question here specifically asks: How does MIPS allocate memory for arrays in the stack? I'm hoping that answering this question will hopefully give me a better total understanding of MIPS as I'm still a bit lot on conceptualizing the idea of the MIPS language and it's architecture. I don't quite understand how pointers work in this whole regard either...

Would be brilliant if someone could take the time to help out this confused student! :)

Answer 1

Well.. you should be aware that MIPS, like C, essentially has three different ways of allocating memory.

Consider the following C code:

int arr[2]; //global variable, allocated in the data segment

int main() {
    int arr2[2]; //local variable, allocated on the stack
    int *arr3 = malloc(sizeof(int) * 2); //local variable, allocated on the heap
}

MIPS assembly supports all these types of data.

To allocate an int array in the data segment you could use:

.data

arr: .word 0, 0 #enough space for two words, initialized to 0, arr label points to the first element 

To allocate an int array on the stack you could use:

#save $ra
addi $sp $sp -4  #give 4 bytes to the stack to store the frame pointer
sw   $fp 0($sp)  #store the old frame pointer
move $fp $sp     #exchange the frame and stack pointers
addi $sp $sp -12 #allocate 12 more bytes of storage, 4 for $ra and 8 for our array
sw   $ra  -4($fp)

# at this point we have allocated space for our array at the address -8($fp)

To allocate space on the heap, a system call is required. In the spim simulator this is system call 9:

li $a0 8 #enough space for two integers
li $v0 9 #syscall 9 (sbrk)
syscall
# address of the allocated space is now in $v0

Answer 2

MIPS unlike other archs doesn't have a push or pop register/immediate instruction. So you rely on managing the stack yourself. This is actually noted in most of the arch outside of mul/div where your registers don't have a specific use, just a suggested way to use it. Now if you used it however you wanted, you would break something if you tried to integrate with C for example.

In order to push something to the stack, you need to use a store instruction. These are sb, sh, sw, swl, swr. byte, half, word, word left, word right respectively.

addiu $sp, $sp, -4   # push stack 1 word
sw $t0, 0($sp)       # place item on newly pushed space

In order to pop something from the stack, you just need to deincrement it with addiu too. However, you may want to load the data from it using lb, lh, lw, lwl, lwr.

lw $t0, 0($sp)
addiu $sp, $sp, 4   # pop stack 1 word

Here is an example of using it with two word push.

addiu $sp, $sp, -8  # allocate two words
sw $t0, 0($sp)      # push two registers t0 t1
sw $t1, 4($sp)

lw $t1, 4($sp)      # pop two registers t0 t1
lw $t0, 0($sp)
addiu $sp, $sp, 8   # deallocate two words

Here is an example of using it for return addresses so calls to non-leaf functions don't mess you up.

# grab us a quick string
.data
example_str: .asciiz "hello world :^)"

# grab us a function
.text
    .globl example
    .type test, @function
test:
    addiu $sp, $sp, -4  # push stack for 1 word
    sw $ra, 0($sp)      # save return address
    
    la $a0, example_str # call puts and give it a string
    jal puts
    nop
    
    lw $ra, 0($sp)      # load return address
    addiu $sp, $sp, 4   # pop stack for 1 word
    
    jr $ra              # return from function to caller
    nop

Here is an example of pushing multiple elements in a row. Popping is the reverse of course.

.data
example_arr: .word 0, 0, 0, 0

.text
addiu $sp, $sp, -16
la $t0, example_arr
lw $t1, 0($t0)
sw $t1, 0($sp)
lw $t1, 0($t0)
sw $t1, 4($sp)
lw $t1, 0($t0)
sw $t1, 8($sp)
sw $t1, 12($sp)

Here is an example of using malloc/calloc thereof.

# grab us a function
.text
    .globl example
    .type test, @function
test:
    addiu $sp, $sp, -4  # push stack for 1 word
    sw $ra, 0($sp)      # save return address
    
    li $a0, 4           # allocate 4*4 bytes (16)
    li $a1, 4
    jal calloc
    nop
    
    addiu $sp, $sp, -4  # push stack for 1 word
    sw $v0, 0($sp)      # save calloc'd buffer
    
    move $t0, $v0       # get the buffer into a temp
    li $t1, 1           # fill some temps with numbers
    li $t2, 2
    li $t3, 3
    li $t4, 4
    sw $t1, 0($t0)      # save some temps to buffer
    sw $t2, 4($t0)
    sw $t3, 8($t0)
    sw $t4, 12($t0)
    
    ... do stuff with the buffer ...
    
    lw $a0, 0($sp)      # pop buffer from stack
    jal free            # run it through free
    nop
    addiu $sp, $sp, 4   # don't forget to decrement
    
    lw $ra, 0($sp)      # load return address
    addiu $sp, $sp, 4   # pop stack for 1 word
    
    jr $ra              # return from function to caller
    nop

Like I mentioned earlier, nothing has a hard defined specific use, so you can also use your own stack and forget about using $sp if you want. I shown examples where I was using $t* as $s*. This works in the case of forcing each function to have its own stack for instance or some other usecase you can think of. As one instance, Lua (https://lua.org) does this to some extent. However, not MIPS. Multiple stacks are lovely especially when dealing with multiple objectives.

Edit: I realized that I omitted the stack frame pointer. Be aware of that if your code is linked with something written in C, that you properly handle the stack frame pointer.

Answer 3

In MIPS we manage the stacks manually, hence we use the store instructions “sb sh sw swl swr”