Skip to main content
Engineering LibreTexts

8.2: The Program Stack

  • Page ID
    27142
  • This section will cover the reason why non-reentrant subprograms are a problem. A special type of stack, the program stack, will be introduced to resolve this problem. This stack will allow memory for a subprogram to be allocated when the subprogram is entered, and freed when the program is exited.

    The chapter will first show why a stack is needed by showing why subprograms are non- reentrant. It will then show how to solve the problem using a stack. The sections after this one will continue to develop the concept of a program stack, and showing how it can be used to implement programming concepts like recursion.

    8.2.1 The non-reentrant subprogram problem

    The subprograms presented in Chapter 3 had a limitation that they could not call other subprograms. The problem is illustrated in the following example.

    .text
    .globl main
    main:
        jal BadSubprogram
        
        la $a0, string3
        jal PrintString
    
        jal Exit
    
    BadSubprogram:
        la $a0, string1
        jal PrintString
        
        li $v0, 4
        la $a0, string2
        syscall
        jr $ra
    
    .data
    string1: .asciiz "\nIn subprogram BadSubprogram\n"    
    string2: .asciiz "After call to PrintString\n"
    string3: .asciiz "After call to BadSubprogram\n"
    .include "utils.asm"
    

    The programmer who wrote this appears to the jal and jr operators to act like subprogram call and return statements. Therefor the expected output is:

    In subprogram BadSubprogram
    After call to PrintString
    After call to example
    

    However when this program runs, what appears to be an infinite loop appears, and the output is:

    In subprogram BadSubprogram
    After call to PrintString
    After call to PrintString
    ...
    

    In the example subprogram BadSubprogram above, the subprogram is making a call to another subprogram, PrintString. To see what is happening, set 2 break points, one at the "jal PrintString" instruction, and one at the following statement “li $v0, 4”, and run the program. You should get a MARS screen that looks like the following image.

    Screen Shot 2020-07-02 at 1.12.34 PM.png

    From this MARS screen image, note that before the call to PrintString the value of the $ra register is address 0x00400004. This is the address which was set when the subprogram BadProgram was called, and is the address the subprogram BadProgram should return to when it completes execution. Now click the green arrow key to continue running the program and it should stop at the statement after the "jal Subprogram" statement, as shown below.

    Screen Shot 2020-07-02 at 1.14.23 PM.png

    Note that now the $ra register points to the current statement address, 0x00400020. What has happened is that the PrintString subprogram needed to have a return address, and so when the "jal PrintString" instruction was executed, it wrote over the address in the $ra register. When this register was overwritten, the subprogram BadSubprogram lost its link back to the main subprogram. Now when “jr $ra” instruction runs to return to the main, the $ra is incorrect, and the program keeps going back to the same spot in the middle BadSubprogram. This is in fact an infinite loop, though it was achieved through a strange mechanism. So the jal and jr operators cannot be thought of as call and return statements. These two operators simply transfer control of the program, and a call and return mechanism is more complicated to implement than these simple operators in assembly.

    8.2.2 Making subprograms re-entrant

    About the only good thing about the BadSubprogram example is that it identifies the problem with the subprogram calling mechanisms is assembly, that the $ra needs to be stored when the subprogram is entered and restored just before the program leaves. But the problem with the $ra is also a problem with any registers that the program uses, as well as any variables that are defined in the subprogram. Space is needed in memory to store these variables.

    The space to store variables and registered which need to be saved for a subprogram is called a stack. When the program begins to run, memory at a high address, in this case 0x7ffffe00, is allocated to store the stack. The stack then grows downward in memory. Generally the area allocated to the stack is sufficient for any properly executing program, though it is common for incorrect programs to reach the limit of the stack memory segment. If a properly running program reaches the limit of the stack memory segment, it can always allocate larger segments of memory.

    When a subprogram is entered, it pushes (or allocates) space on the stack for any registers it needs to save, and any local variables it might need to store. When the subprogram is exited, it pops this memory off of the stack, freeing any memory that it might have allocated, and restoring the stack to the state it was in before the subprogram was called. The following program, using the subprogram Good Subprogram, highlights how the $ra register while the subprogram is running and then restored just before the it is used to return from the subprogram.

    .text
    .globl main
    main:
        jal GoodSubprogram
        
        la $a0, string3
        jal PrintString
    
        jal Exit
    
    GoodSubprogram:
        addi $sp, $sp, -4  # save space on the stack (push) for the $ra
        sw $ra, 0($sp)     # save $ra
        la $a0, string1
        jal PrintString
        li $v0, 4
        la $a0, string2
        syscall
    
        lw $ra, 0($sp)     # restore $ra
        addi $sp, $sp, 4   # return the space on the stack (pop)
        jr $ra
    
    .data
    string1: .asciiz "\nIn subprogram GoodExample\n"
    string2: .asciiz "After call to PrintString\n"
    string3: .asciiz "After call to GoodExample\n"
    .include "utils.asm"
    

    This program will work as expected, and the infinite loop is gone. To show why this program works, the highlighted in lines the program are explained. The first set of highlighted lines are the following.

    addi $sp, $sp, -4     # save space on the stack (push) for the $ra
    sw $ra, 0($sp)        # save $ra
    

    This is an example of the type of code that should be placed at the start of a reentrant subprogram. When the subprogram is entered, the stack pointer ($sp) register points to the current end of the stack. All subprograms before this one have incremented the $sp to allocate space for their automatic variables, so all previous subprograms have stack frames (or activiation records) on the stack for their execution. So all space above the stack pointer is taken, but the space below the $sp is open, and this is where this subprogram allocates its space to place it variables.

    Remember that the stack grows downward, which is why 4 is subtracted from $sp when the space is allocated. The allocation of 4 bytes is the amount needed to store the $ra.

    When the GoodSubprogram is run, and execution stopped immediately after the $ra is written to the stack, the MARS screen would look as follows.

    Screen Shot 2020-07-02 at 1.26.12 PM.png

    Now the select box for the memory to view is not "data", but "current $sp", or stack. Looking at the value of $sp of 0x7ffefff8, it can be seen that the correct return address from GoodSubprogram has been saved.

    The second set of highlighted code, shown below, is an example of the type of code which should be placed just before the last statement in a subprogram. In this code the $ra is restored to the value that it contained when the subprogram was called, so the subprogram can return to the correct line in the calling program. The stack frame for this subprogram is then popped by adding the amount of memory used back to the stack.

    lw $ra, 0($sp)    # restore $ra
    addi $sp, $sp, 4  # return the space on the stack (pop)  
    

    Note that when using a HLL compiler, the compiler will decide if the overhead of a stack is needed or not, and will handle any the mechanics of including code to handle the program stack. In assembly, this is up to the programmer. If the program does not need to share any data or transfer control outside of the subprogram, the allocation of the stack frame can be avoided.

    • Was this article helpful?