Part 7 - The Stack and Subroutine Linkage

Programs are divided into sections called subroutines. At run time, the stack is used to save and to restore a subroutine's values.

The Run-time Stack

This chapter discusses the run-time stack and the stack pointer register $sp.

Chapter Topics:

• Stacks
• The stack pointer register $sp
• Push and Pop stack operations
• The MIPS runtime stack
• Compiler use of stacks
• String reversal example

Note: for the example programs in this chapter, assume that the SPIM simulator has been set so that pseudoinstructions are ON, delayed branches are OFF, and delayed loading is OFF.

Question 1

Say that you need to get a plate from a stack of dinner plates. Which one do you normally get?

Answer

The top plate.

Stack

A stack is a way of organizing data in memory. Data items are visualized as behaving like a stack of physical items. Often a stack is visualized as behaving like a stack of dinner plates. Data are added and removed from the stack data structure in a way analogous to placing plates on the stack of plates and removing them.

Normally with a stack of dinner plates all operations take place at the top of the stack. If you need a plate, you take the one at the top of the stack. If you add a plate to the stack, you place it on top of the stack.

Question 2

Which plate is the last one that was added to the stack? Which plate will be the first one removed?

Answer

The plate at the top of the stack was the last one added. It will also be the first one removed.

Upside-down MIPS stack

Stack-like behavior is sometimes called "LIFO" for Last In First Out.

The data elements in our stacks are 32-bit words. In general, stacks can be used for all types of data. But in these chapters, stacks contain only 32-bit MIPS full words.

The picture shows a stack of MIPS full words. The stack pointer register $sp by convention points at the top item of the stack. The stack pointer is register $29. The mnemonic register name $sp is used by the extended assembler.

In the usual way of drawing memory the stack is upside-down. In the picture, the top item of the stack is 81. The bottom of the stack contains the integer -92.

Before the operating system starts your program it ensures that there is a range of memory for a stack and puts a suitable address into $sp.

Question 3

If an item of data (say the value 103) is added to the stack, where will it go?

Answer

After the 81. The 103 is now the top of the stack.

Push

By software convention, $sp always points to the top of the stack. Also by convention, the stack grows downward (in terms of memory addresses). So, for our stack of 4-byte (full word) data, adding an item means subtracting four from $sp and storing the item in that address. This operation is called a push operation.

To push an item onto the stack, first subtract 4 from the stack pointer, then store the item at the address in the stack pointer.

Here is what that looks like in code. Say that the value to push on the stack is in register $t0:

                    # PUSH the item in $t0:
subu $sp,$sp,4      #   point to the place for the new item,
sw   $t0,($sp)      #   store the contents of $t0 as the new top.

The extended assembler allows you to write ($sp) for 0($sp). The machine instruction will have the displacement of zero filled in.

Question 4

In the new stack (shown above) if one item is removed, which will it be?

Answer

103

Pop

Removing an item from a stack is called a pop operation. In the real-world analogy an item is actually removed: a dish is physically moved from the stack. In a software stack, "removal" of an item means it is copied to another location and the stack pointer is adjusted.

The picture shows a pop operation. The data is first copied from the top of stack to the new location and then the stack pointer is increased by four.

To pop the top item from a stack, copy the item pointed at by the stack pointer, then add 4 to the stack pointer.

Here is what that looks like in code. Say that we want the value to be popped into $t0:

                    # POP the item into $t0:
lw   $t0,($sp)      #   Copy top item to $t0.
addu $sp,$sp,4      #   Point to the item beneath the old top.

As above, ($sp) means the same as 0($sp).

Question 5

When a software stack is popped, does the popped item remain in memory?

Answer

Yes. The data is copied to a new location, but the old location is not changed. However, since the stack pointer is moved, "logically" the data is no longer on the stack.

Example

The stack is often used to hold temporary values when most registers are already in use. An example of this is how a compiler translates an arithmetic expression into machine codes that uses a stack. Say that the arithmetic expression is ab - 12a + 18b - 7.

Say that only $t0 and $t1 are available. Perhaps only two registers are available because the compiler has already output code that uses all the others.

Before SPIM starts running a program it initializes the stack pointer $sp appropriately. On a computer with a full operating system, the stack pointer is initialized by the operating system before control is passed to a user program.

Here is the start of the program:

Question 6

Fill in the blanks.

Answer

See below.

Program continued

Terms of the expression are pushed onto the stack as they are evaluated. Then the sum is initialized to -7 and the terms on the stack are popped one by one and added to the sum.

Question 7

Fill in the blanks to pop the 18b term.

Answer

See below.

Finished program

Here is the finished program. If you had plenty of registers available you would use them to hold the terms of the expressions, and not use the stack. But in a large program, with many registers in use, you might do it this way.

# Evaluate the expression ab - 12a + 18b - 7
#
# Settings: Load delays OFF; Branch delays OFF,
#           Trap file    ON; Pseudoinstructions ON   

        .globl  main

main:   
        lw      $t0,a          # get a
        lw      $t1,bb         # get b
        mul     $t0,$t0,$t1    # a*b
        subu    $sp,$sp,4      # push a*b onto stack
        sw      $t0,($sp)
        
        lw      $t0,a          # get a
        li      $t1,-12        # 
        mul     $t0,$t0,$t1    # -12a
        subu    $sp,$sp,4      # push -12a onto stack
        sw      $t0,($sp)
        
        lw      $t0,bb         # get b
        li      $t1,18         # 
        mul     $t0,$t0,$t1    # 18b
        subu    $sp,$sp,4      # push 18b onto stack
        sw      $t0,($sp)

        li      $t1,-7         # init sum to -7
        lw      $t0,($sp)      # pop 18b
        addu    $sp,$sp,4
        addu    $t1,$t1,$t0    # 18b -7
                
        lw      $t0,($sp)      # pop -12a
        addu    $sp,$sp,4
        addu    $t1,$t1,$t0    # -12a + 18b -7
                
        lw      $t0,($sp)      # pop ab
        addu    $sp,$sp,4
        addu    $t1,$t1,$t0    # ab - 12a + 18b -7
         
done:   li      $v0,1          # print sum
        move    $a0,$t1
        syscall
        li      $v0,10         # exit
        syscall   

        .data
a:      .word  0
bb:     .word  10

Question 8

(Thought Question:) Is it possible to run out of memory if too many things are pushed onto the stack?

Answer

Yes.

Runtime stack

There is a finite amount of memory, even in the best computer systems. So it is possible to push more words than there are words of memory. Usually this would be the result of an infinite loop because when a program is first entered the operating system gives it space for a very large stack.

The picture shows how a typical operating system arranges memory when a program starts. There are four gigabytes of (virtual) memory available in total. The section of memory from 0x10000000 to 0x7FFFFFFF is available for the data segment and the stack segment. This is 1.8 Gigabytes of space.

When the program is started the stack pointer ($sp) is initialized to 0x7FFFFFFC (the address of the last fullword of user memory). As the program runs, the stack grows downward into the available space. The data segment grows upward as the program runs. (This is the subject of chapter 33.)

In a dynamic program, the segments grow and shrink. If the combined size of the segments exceeds the available space their boundaries will meet somewhere in the middle of the range. When this happens there is no memory left.

Another (inferior) way of arranging memory might be to divide the space above the text segment so the stack gets half and the data segment gets half. But now the stack could grow too large for its allocated space, even if there was a tiny data segment that used little of its space.

Question 9

Which segment is for the machine instructions?

Answer

The text segment.

Runtime stack

Traditionally a segment containing machine instructions is called "text". A process is when the processor is actively executing those machine instructions. (This is analogous to the phrase "text of a play" and "performance of a play").

Here is a classic example of how a stack is used. The user enters a string, which is stored as a null-terminated string in a character buffer. The program then reverses the order of the characters in the buffer, and then writes out the reversed buffer. To understand how the program works inspect the following diagram. The string "Hello" is pushed onto the stack, from the buffer, character by character, starting with the 'H'. Then the characters are then popped from the stack back into the original string buffer. The last character pushed is the first one out. This reverses the order of the characters.

We will always push and pop full words (four bytes). Each character on the stack will be contained in the low order byte of a fullword.

Question 10

(Review:) What does the following instruction do? lbu $t0,string

Answer

It loads one byte (located at symbolic address string) into the low order byte of register $t0. The other bytes of $t0 are filled with zero.

Outline

Here is the outline of the program. The comments show the major sections of the program.

        .text
        .globl  main
main:  
        # _____

        # _____

        # _____

        # _____

        .data
str:    .space  128     # character buffer   

Not much of an outline. Luckily, here are some phrases you can use to fill in the blanks:

• print the reversed string
• push each character onto the stack
• input the string into a buffer
• pop chars from stack back into the buffer

Question 11

Fill the blanks with the correct phrases. (You can do this by using your mouse with copy and paste from the Edit menu of the browser.)

Answer

        .text
        .globl  main
main:  
        # input the string

        # push each character onto the stack

        # pop chars from stack back into the buffer

        # print the reversed string

        .data
str:    .space  128     # character buffer   

First section

The first section of the program reads a line from the terminal in the usual way. To shorten the program, there is no user prompt.

Next, the stack is initialized. The program itself does not initialize the stack pointer because this is done by the operating system when it before it passes control to the program. (In our case, the stack pointer is initialized by SPIM.) Null is pushed onto the stack. Later on, the stack will be popped until this null is encountered.

Question 12

Fill in the blanks of the program.

Answer

See below.

Pushing characters

In the next stage, characters from the character buffer are pushed one by one onto the stack. The first instruction (at pushl:) uses indexed addressing to load the current character from the buffer (str:) into the least significant byte of $t0.

Next, the current character is tested. If it is null (zero) then control branches out of the loop. Otherwise the character is pushed onto the stack. Then the process is repeated.

Question 13

Fill in the blanks.

Answer

See below.

Popping characters

When the null byte of the null-terminated input string is encountered, the first loop exits and the next loop begins. This next loop pops characters (contained in full words) off of the stack until the null at the bottom of the stack is encountered. Each character popped off the stack is placed into the string buffer, overwriting the character originally there.

The null at the end of the input string is not overwritten. It will remain there as part of the null-terminated result string.

Question 14

You know the drill: fill in those blanks.

Answer

See below.

Final phase

The last phase of the program prints out the result string. There is nothing new here. If you want to see the complete program, copy and paste the several above sections into a text file.

Question 15

Would it be easier to do this program with arrays?

Answer

Probably not. It would call for some tricky code array indexing code.

Chapter quiz

Instructions: For each question, choose the single best answer. Make your choice by clicking on its button. You can change your answers at any time. When the quiz is graded, the correct answers will appear in the box after each question.

Question 1

What phrase matches how a stack behaves?

• (A) First In First Out
• (B) First Out First In
• (C) Last In First Out
• (D) Last In Last Out

Answer

C

Question 2

Adding an item to a stack is called:

• (A) pop
• (B) push
• (C) insert
• (D) add

Answer

B

Question 3

Removing an item from the top of the stack is called:

• (A) pop
• (B) push
• (C) remove
• (D) delete

Answer

A

Question 4

Assume that the stack pointer has already been set up. Which of the following code fragments pushes a word of data from register $t0?

• (A)

  subu  $sp,$sp,4
  lw    $t0,($sp)

• (B)

  addu $sp,$sp,4
  lw   $t0,($sp)

• (C)

  sw    $t0,($sp)
  subu  $sp,$sp,4

• (D)

  subu  $sp,$sp,4
  sw    $t0,($sp)

Answer

D

Question 5

As data is added to the MIPS stack, how does it grow?

• (A) It grows upward toward higher addresses.
• (B) In grows downward toward lower addresses.
• (C) It grows toward the address in the stack pointer.
• (D) It grows in whichever direction is available.

Answer

B

Question 6

Assume that the stack pointer has already been set up and that the stack contains data. Which of the following code fragments POPS a word of data to register $t0?

• (A)

  sw    $t0,($sp)
  addu  $sp,$sp,4

• (B)

  lw    $t0,($sp)
  subu  $sp,$sp,4

• (C)

  lw    $t0,($sp)
  addu  $sp,$sp,4

• (D)

  addu  $sp,$sp,4
  lw    $t0,($sp)

Answer

C

Question 7

How much total virtual memory is available with a MIPS processor?

• (A) 32 Megabytes
• (B) 512 Megabytes
• (C) 2 Gigabytes
• (D) 4 Gigabytes

Answer

D

Question 8

Does the stack contain data that was declared in the .data section of a program?

• (A) No. That goes in the data segment of memory.
• (B) No. That goes in the text segment of memory.
• (C) Yes. The stack contains all the data of the program.
• (D) Yes. The .data section goes in the start of the stack.

Answer

A

Question 9

What does the instruction lbu $t0,string do?

• (A) It copies a word of memory from symbolic address string into $t0.
• (B) It copies one byte of memory from symbolic address string into the low order byte $t0, leaving the other bytes of $t0 unchanged.
• (C) It copies one byte of memory from symbolic address string into the low order byte $t0, and zeros the remaining bytes of $t0.
• (D) It copies one byte of memory from symbolic address string into the low order byte $t0, and extends bit 7 into the remaining bytes of $t0.

Answer

C

Question 10

Must a stack-based algorithm (such as string reversal) start out with an empty stack?

• (A) No. The algorithm is not affected by data already on the stack.
• (B) No. The algorithm will clear old data left on the stack.
• (C) Yes. If there is data already on the stack it will be inappropriately used.
• (D) Yes. Each program must have its own stack.

Answer

A

Programming exercises

In the Settings menu of SPIM set Bare Machine OFF, Allow Pseudo Instructions ON, Load Trap File ON, Delayed Branches ON, Delayed Loads ON, Mapped IO ON, Quiet OFF.

Exercise 1 - arithmetic evaluation (stack-based)

Write a program to evaluate 3ab - 2bc - 5a + 20ac - 16

Prompt the user for the values a, b, and c. Try to use a small number of registers. Use the stack to hold intermediate values. Write the final value to the monitor.

Exercise 2 - string reversal (stack-based)

Write a program that asks the user for a string. Read the string into a buffer, then reverse the string using the stack. However, unlike the example in the chapter, don't push a null character on the stack. Keep track of the number of characters on the stack by incrementing a count each time a character is pushed, and decrementing it each time a character is popped. Write out the reversed string.

Exercise 3 - vowel removal (stack-based)

Write a program that asks the user for a string. Read the string into a buffer. Now scan the string from right to left starting with the right-most character (this is the one just before the null termination.) Push each non-vowel character onto the stack. Skip over vowels.

Now pop the stack character by character back into the buffer. Put characters into the buffer from right to left. End the string with a null byte. The buffer will now contain the string, in the correct order, without vowels.

Write out the final string.

Simple Subroutine Linkage

All high level languages have the concept of a subroutine (sometimes called procedure, function, or method). A subroutine is a logical division of the code that may be regarded as a self-contained operation. For example, the sine function is usually implemented as a subroutine. It can be regarded as an operation that can be used as needed in a program.

This chapter looks at a simple implementation in assembly language of this idea. The simple implementation is not adequate for the full power of subroutines (as implemented in high level languages), but is a good starting point. It corresponds to the type of subroutines implemented in the early days of programming.

Chapter Topics:

• Subroutine call
• Caller and Callee routines
• jal and jr instructions
• The $ra register
• The simple linkage calling convention
• Register use in subroutines

The two chapters after this one discuss subroutine call methods that are similar to those of modern languages.

Question 1

(Review:) What instructions unconditionally transfer control from one address to another?

Answer

The j (jump) instruction or the b (branch) instruction.

Passing control with a jump instruction

At right is a sketch of what you can do with the j instruction. (The same could be done with the b instruction.) If the main routine needs to start up ("to call") a subroutine sub it can jump to it with a j instruction. At the end of the subroutine, control can be returned with another j instruction.

The subroutine returns to a statement in main labeled ret. The subroutine is called at just one point in main and it returns to an address a few instructions after that point.

The subroutine is only used once in the main program because it always returns to the same location. (You could write some tricky code to overcome this limitation. But it is much better to follow a subroutine linkage convention such as is about to be discussed.)

A subroutine call is when a main routine (or other routine) passes control to a subroutine. The main routine is said to be the CALLER and the subroutine is said to be the CALLEE. A return from a subroutine is when a subroutine passes control back to its CALLER. When a CALLEE finishes execution it nearly always returns control to its CALLER.

Question 2

Is it normal that a subroutine can be used in only one place in a program?

Answer

No. You would like to call a useful subroutine from many locations in a program.

Especially useful subroutines are put into subroutine libraries and can be called from many locations in many programs, and so, of course, they must return to many different locations.

There seems to be a problem with using j for the call of and return from a subroutine.

Jump instruction does not work for a subroutine call

The problem is illustrated at right. The main routine is written to call a useful subroutine sub at several locations in the code. But, as it is written, sub always returns control to the same location. Usually this will not work.

In the past, before the concept was completely understood, hardware support for subroutines was missing. Various nasty software tricks were used to implement the idea.

What is needed is a way to send a return address to the subroutine when it is called. Now when the subroutine finishes, it passes control to that return address.

Of course, "passing control to a return address" means that the subroutine loads the PC (program counter) with the return address. The next instruction fetch of the machine cycle will get the instruction from that address.

Question 3

(Hardware Design Question:) How should the return address be passed to the subroutine? (i) By placing it in main memory somewhere, or (ii) By placing it in a register designated for this purpose.

Answer

(ii) By placing it in a register designated for this purpose.

The jal instruction

The register that is used for linkage is register $31, which is called $ra by the extended assembler. It holds the return address for a subroutine. The instruction that puts the return address into $ra is (usually) the jal instruction.

Register $31 is one of the two "general purpose registers" that behave differently from the others. (The other one is register $0.) The jal instruction and register $31 provide the hardware support necessary to elegantly implement subroutines.

To understand how jal works, review the machine cycle. The MIPS endlessly cycles through three basic steps. Each cycle executes one machine instruction. (This is a somewhat simplified view, but sufficient for now).

The jal instruction does the following in the execute phase of the machine cycle:

jal sub    # $ra <- PC+4  (the address 8 bytes away from the jal) 
           # PC  <- sub   load the PC with the subroutine entry point
           # a branch delay slot follows this instruction

Very Tricky: the middle step of the machine cycle has already incremented the PC by four. At this point the PC holds the address of the instruction just after the jal instruction. Now the execute phase of the jal instruction adds four to that address and puts the result in $ra. So now $ra holds the address of the second instruction after the jal instruction.

The correct return address is "address of the jal plus eight". This is because: (i) returning from the subroutine to the jal instruction would be a disaster (since it would execute again, sending control back to the subroutine), and (ii) the instruction following the jal is a branch delay slot.

Question 4

What instruction is usually placed in the branch delay slot?

Answer

Usually the branch delay slot is filled with a nop instruction. This does nothing.

Example jal instruction

It would not be a disaster to return control to an instruction that does nothing. But sometimes programmers or compilers put something clever in the branch delay slot, so it is best not to pass control to it.

The diagram shows the execution of a jal instruction. The jal is at address 0x00400014. The return address is 0x0040001C which is the address of the jal plus eight. (The addu instruction there is just used as an example of what might be at the return address).

Return from the subroutine to the caller is done with a jr instruction. This will be discussed in a few pages.

Here is how the jal instruction works in general:

jal sub    # $ra <- PC+4  (the address 8 bytes away from the jal) 
           # PC  <- sub   load the PC with the subroutine entry point
           # a branch delay slot follows this instruction

Here is how it works in this example. The entry point of sub is 0x00400100.

Fetch:      When the jal is fetched the PC has 0x00400014.

Increment:  The PC is incremented to 0x00400018.
            
Execute:    $ra <- 0x004001C = 0x0040018+4 
            PC  <- 0x00400100

The nop instruction in the branch delay slot is executed. Then execution continues with the first instruction of the subroutine at 0x00400100. Control has been passed to the subroutine and the return address in $ra.

Question 5

The subroutine has the return address in $ra. Can an ordinary jump instruction be used to return to the caller?

Answer

No. An ordinary jump instruction has its target encoded as an unchanging part of the instruction. (like j someSpot).

The jr instruction

The jr instruction returns control to the caller. It copies the contents of $ra into the PC:

jr  $ra      # PC <- $ra 
             # A branch delay 
             # slot follows this instruction.

Usually you think of this as "jumping to the address in $ra."

To make the instruction more general, it can be used with any register, not just $ra. Like all jump and branch instructions, the jr instruction is followed by a branch delay.

The diagram shows the subroutine returning to the return address that was loaded into $ra by the jal instruction in the caller.

Question 6

Do we now have a mechanism that enables us to call the same subroutine from many points in a program?

Answer

Yes.

Calling convention

The diagram shows the subroutine sub being called from three different points in the main routine. Each time the subroutine is called it returns to the appropriate return address.

A calling convention is an agreement about how subroutines are called and how control is returned to the caller. Mostly (as we will later see) this is an agreement about how software will work. In processors (like MIPS) that have hardware features that support subroutines, the convention says how those features are used.

Different languages and different operating systems for the same processor usually have different calling conventions. A "C" program compiled for Linux on a MIPS processor will not work correctly with Irix on a MIPS processor. This is largely because the calling conventions are different. These chapters discuss several calling conventions that show what calling conventions are about, but are not the calling convention of any particular operating system.

There is more to a calling convention than how to pass control, as the next question shows:

Question 7

Is subroutine sub free to use any of the 32 registers?

Answer

No. Typically the caller has important information in some registers, and others (such as the stack pointer) are used for special purposes.

Register use

To answer the question, you could look at the code for main to determine which registers contain information and so can not be altered. Do this every place in main that sub is called, because different registers are likely to be in use at different places. Now write sub using only those registers that are not in use before any call.

This is tedious and error prone. Worse, if you make a change to main, you now might have to re-code sub using different registers.

One of the goals in writing a subroutine is to create a module that is independent of the rest of the code. We have not achieved that, yet.

Another issue is how data is passed into and out of the subroutine. Often data is in registers, and the results are in registers. Which registers?

By software convention (not by hardware) registers have been assigned different roles:

• $t0 - $t9 — The subroutine is free to change these registers.
• $s0 - $s7 — The subroutine must not change these registers.
• $a0 - $a3 — These registers contain arguments for the subroutine. The subroutine can change them.
• $v0 - $v1 — These registers contain values returned from the subroutine.

Question 8

Is the following code fragment correct?

add    $t0,$s5,$s3   # calculate an important sum in $t0
jal    somesub       # call a subroutine
nop                  # branch delay
mul    $s4,$t0,$v1   # multiply the sum

Answer

No. The value in $t0 might have been changed by somesub, since $t0 (according to convention) is a register that a subroutine is free to use.

add    $t0,$s5,$s3   # calculate an important sum
jal    somesub       # call a subroutine
nop                  # branch delay
mul    $s4,$t0,$v1   # multiply the sum by the result

Simple linkage convention

Here is an example of a calling convention. This convention is very simple and is not suitable for a serious program. But it illustrates some ideas that will be used later on in more complex conventions. Let us call it the Simple Linkage Convention. You have already seen most of the rules of this convention:

1. A subroutine is called using jal (which puts the return address in $ra.)
2. A subroutine will NOT call another subroutine.
3. The subroutine returns to its caller using jr $ra.
4. Registers are used as follows:

• $t0 - $t9 — The subroutine is free to change these registers.
• $s0 - $s7 — The subroutine must not change these registers.
• $a0 - $a3 — These registers contain arguments for the subroutine. The subroutine can change them.
• $v0 - $v1 — These registers contain values returned from the subroutine.

5. The main routine returns control by using the exit service (service 10) of the SPIM exception handler.

Since a subroutine may not call another subroutine (in this Simple Linkage Convention) programs will consist of a main routine that calls any number of subroutines. But the subroutines do not call other subroutines and always return directly to main.

Question 9

(Thought Question:) Consider rule number 2. Why must not a subroutine call another subroutine?

Answer

Because there is no place to put the return address. The register $ra is already in use.

Pictorial summary

The picture shows main calling mySub. Two arguments are passed in $a0 and $a1. The subroutine uses the arguments in those registers.

In the picture, the arguments are set up with move and li instructions, but any means of loading the argument registers can be used.

The Simple Linkage Convention is limited in some obvious ways. A more advanced calling convention is discussed in the next chapter.

The caller passes arguments to the subroutine by placing them in registers. This is the only way that data is passed to the subroutine. The subroutine returns values to the caller in registers. This is the only way the subroutine returns data to the caller. The subroutine should not look at any memory used by the caller, and the caller should not look at any memory used by the subroutine.

Question 10

Should a code module know about the inner workings of another module?

Answer

No. This means that routines should not look at each other's memory. In terms of the assembly language source code, this means that subroutines and main should not use each other's symbolic addresses.

Example program

Let us write a program that uses the Simple Linkage convention. The program is to read three integers from the user and compute the sum. The outline of the program is:

# read first integer

# read second integer

# read third integer

# compute the sum

# write out the result

Of course, the user will enter integers as characters from the keyboard. The program uses the exception handler service number five to read the characters and convert them into a 32-bit integer.

Question 11

Examine the outline for the program. What do you think would be a useful subroutine?

Answer

It would be useful to have a read integer subroutine.

Prompt for and read integer

The subroutine prompts the user for an integer and reads it in. The integer is returned in $v0. Here is a start on the subroutine:

Question 12

Fill in the blanks.

Answer

# pread -- prompt for and read an integer
#
# on entry:
#    $ra -- return address
#
# on exit:
#    $v0 -- the integer

pread:   
         la    $a0,prompt        # print string
         li    $v0,4             # service 4
         syscall
        
         li    $v0,5             # read int into $v0
         syscall                 # service 5
        
         jr    $ra               # return
         nop                     # branch delay slot
        
         .data
prompt:
         .asciiz "Enter an integer: "

Main program

Once the subroutine is written, you can use it whenever you need the function it performs. Now finish the main program:

Question 13

Fill in the blanks.

Answer

         .text
         .globl  main

main:
         jal     pread            # read first integer
         nop                      #  
         move    $s0,$v0          # save it in $s0
         jal     pread            # read second integer
         nop                      # 
         move    $s1,$v0          # save it in $s1
         jal     pread            # read third integer
         nop                      #  
         move    $s2,$v0          # save it in $s2
         
         addu    $s0,$s0,$s1      # compute the sum
         addu    $s3,$s0,$s2      # result in $s3
 
         li      $v0,4            # print a heading
         la      $a0,heading         
         syscall

         move    $a0,$s3          # move sum into parameter
         li      $v0,1            # print the sum
         syscall
        
         li      $v0,10           # exit
         syscall
          
         .data
heading:
         .asciiz "The sum is: " 

Global symbols

Recall that modules (for us, subroutines) should not know about each other's symbolic addresses. It would violate the idea of modularity for main to do something to pread's prompt, for example.

But some symbolic addresses need to be used between modules. For example, pread is a symbolic address, and main must know about it and use it in the jal instruction.

A symbol that a subroutine makes visible to other subroutines is a global symbol. Global symbols often label entry points. Symbols that are not global are called local symbols. A symbol is made global by placing it in a list of symbols following the .globl directive. Some languages use the word external for what we are calling global.

         .globl  main

In the language C, a symbol that is visible to another module is called an external symbol. For example, the names of functions in C are external symbols.

Source programs for PC-SPIM (the older version of SPIM) are contained in a single file, which includes all subroutines. However, in professional software development each subroutine might be placed in a separate source file. Each file must say which of its symbolic addesses are global and might be referenced by other source files.

With QtSpim (the most recent version of SPIM) you can create separate source files and load them separately. For this example program:

1. Create separate source files addthree.asm and pread.asm (see next page)
2. Start QtSPIM. Check the settings.
3. Click "File"
4. Select the "Reinitalize and Load File" menu, then pick addThree.asm
5. Click "File"
6. Select the "Load File" menu, then pick pread.asm
7. You will now have the two files linked together in memory, with one text section and one data section
8. Click "Run" (as always)

Question 14

What global symbols are in the subroutine pread?

Answer

The entry point for the subroutine: pread.

Complete program

Here is the complete example program. The global symbols have been correctly declared. Study how each module uses the directives .text and .data to describe its sections.

As you "Load" each file from the file menu, QtSpim will ensure that the text sections are placed into the single text section of (simulated) main storage and that the data sections are placed into the data section. In a real operating system, this is the job of the linker and loader.

# addthree.asm --- read in three integers and print their sum
#
# This program uses simple linkage.  
#
# Settings: Load delays  ON;  Branch delays ON
#           Trap file    ON;  Pseudoinstructions ON   
#

         .text
         .globl  main
main:
         jal     pread            # read first integer
         nop                      #  
         move    $s0,$v0          # save it in $s0

         jal     pread            # read second integer
         nop                      #  
         move    $s1,$v0          # save it in $s1

         jal     pread            # read third integer
         nop                      #  
         move    $s2,$v0          # save it in $s2
         
         addu    $s0,$s0,$s1      # compute the sum
         addu    $s3,$s0,$s2      # result in $s3
 
         li      $v0,4            # print a heading
         la      $a0,heading         
         syscall

         move    $a0,$s3          # move sum into parameter
         li      $v0,1            # print the sum
         syscall
        
         li      $v0,10           # exit
         syscall
          
         .data
heading:
         .asciiz "The sum is: "        
        
 

# pread.asm -- prompt for and read an integer
#
# on entry:
#    $ra -- return address
#
# on exit:
#    $v0 -- the integer

         .text
         .globl  pread
pread:   
         la    $a0,prompt        # print string
         li    $v0,4             # service 4
         syscall
        
         li    $v0,5             # read int into $v0
         syscall                 # service 5
        
         jr    $ra               # return
         nop                     #  
        
         .data
prompt:
         .asciiz "Enter an integer: "

Here is a picture of the console window after the program has run:

Question 15

Could pread be used as-is in other programs?

Answer

Yes, as long as they followed the simple linkage convention.

Chapter quiz

Instructions: For each question, choose the single best answer. Make your choice by clicking on its button. You can change your answers at any time. When the quiz is graded, the correct answers will appear in the box after each question.

Question 1

What is the major limitation in using a jump instruction to pass control to a subroutine?

• (A) The subroutine can not be passed any arguments.
• (B) The jump instruction is too slow for subroutine calls.
• (C) Subroutines are often distant in memory from the main routine, and the jump instruction can not reach them.
• (D) The jump instruction gives the subroutine no information about how to return to the caller.

Answer

D

Question 2

A main routine passes control to a subroutine subA. Which of the following is usually true?

• (A) When subA is done it returns control to main a few statements after where it was called.
• (B) When subA is done it returns control to the the start of main.
• (C) When subA is done it returns control to the operating system.
• (D) When subA is done the whole program is finished.

Answer

A

Question 3

What is a return address?

• (A) the address in the subroutine that gets control.
• (B) the address of the instruction that calls a subroutine.
• (C) the address of the instruction in the caller to which the subroutine returns control.
• (D) the address in the subroutine of the instruction that returns control to the caller.

Answer

C

Question 4

Recall how the jal instruction works:

jal sub    # $ra <— PC+4  $ra <— address 8 bytes away from the jal 
           # PC  <— sub   load the PC with the subroutine entry point

Say that the jal instruction is at address 0x400000. The subroutine sub is at address 0x400300.

What is in $ra after the jal instruction executes?

• (A) $ra == 0x400004
• (B) $ra == 0x400008
• (C) $ra == 0x400300
• (D) $ra == 0x400308

Answer

B

Question 5

Is the jal instruction followed by a branch delay?

• (A) No.
• (B) Yes.

Answer

B

Question 6

What does the following instruction do? jr $s0

• (A) It immediately jumps to the address in $s0 with no branch delay.
• (B) It jumps to the address in $ra after a one instruction branch delay.
• (C) It jumps to the address in $s0 after a one instruction branch delay.
• (D) The instruction is illegal.

Answer

C

Question 7

By software convention, which registers must a subroutine NOT change?

• (A) $t0 — $t9
• (B) $s0 — $s7
• (C) $a0 — $a3
• (D) $v0 — $v1

Answer

B

Question 8

By software convention, which registers MAY a subroutine change?

• (A) $t0 — $t9
• (B) $s0 — $s7
• (C) $at — $gp
• (D) $k0 — $k1

Answer

A

Question 9

What is the name for a symbol in a subroutine that is made visible to other routines?

• (A) local symbol
• (B) express symbol
• (C) global symbol
• (D) universal symbol

Answer

C

Question 10

With the simple linkage convention, is it possible for main to call a subroutine which then calls another subroutine?

• (A) Yes. Subroutines will return to their caller in the opposite order they were called.
• (B) Yes. The jal and jr instructions automatically allow this.
• (C) No. The first subroutine can't use a jal instruction without destroying the return address to main.
• (D) No. This is never done in programming.

Answer

C

Programming exercises

NOTE: The example programs in the chapter included load and branch delays to show how actual MIPS hardware works. However, for these exercises you can turn them off (or leave them on if you prefer.)

In the Settings menu of SPIM set Bare Machine OFF, Allow Pseudo Instructions ON, Load Trap File ON, Delayed Branches ON, Delayed Loads ON, Mapped IO ON, Quiet OFF.

Exercise 1 - arithmetic expression

Write a subroutine that takes three arguments, A, X, and Y. It then computes A*X*Y and returns it.

Use the subroutine to evaluate the following for various values of u and v: 5u2 - 12uv + 6v2

The main method, in a loop, prompts the user for values of u and v and prints out the result. End the loop when the user enters zero for both u and v.

Exercise 2 - user prompt

Write a subroutine that prompts the user for an integer. The subroutine reads the string the user enters as a string (using trap handler service 8). Then, if the string forms a proper integer, it is converted to two's complement form and returned in register $v0.

If the input was converted, set register $v1 to one. If the input was not converted, set register $v1 to zero, and set $v0 to zero. If the user enters "done", set register $v1 to two, and set $v0 to zero.

Use the subroutine in a program that computes the sum of a list of integers that the user enters. The user signals the end of input by typing "done".

Exercise 3 - arithmetic evaluation with user prompt

Combine the previous two programs:

Write a program that evaluate the following for various values of u and v: 5u2 - 12uv + 6v2

The values for u and v are prompted for in a loop. The user enters the values and the value of the expression is printed out. If illegal characters are entered for either u or v, print out an error message and continue.

End the loop when the user enters "done" for the value of u.

Stack-based Linkage Convention

The Simple Linkage Convention of the previous chapter lacked some features of high level languages. This chapter adds some of these features in a new Stack-based Linkage Convention.

Chapter Topics:

• Saving registers on the stack
• The Stack-based Linkage Convention
• The prolog and epilog of the called subroutine
• The call and return of the caller
• Nested subroutine calls and the chain of activation
• History of linkage conventions
• Example program: converting user input to upper case

Question 1

In the Simple Linkage Convention of the previous chapter, can a subroutine call another subroutine?

Answer

No.

Pushing the return address

To return to the caller a subroutine must have the correct return address in $ra when the jr instruction is performed. But this address does not have to remain in $ra all the time the subroutine is running. It works fine to save the value in $ra somewhere. The value can be restored, later on, when it is time to return to the caller.

In the picture, the operating system calls main. The return address to the operating system is in $ra. As soon as it gets control, main pushes the return address on the stack (step 1). The return address that main should use when it returns to the operating system is now on the top of the stack.

The "push" and "pop" instructions in the picture are conceptual. Actual code does these operations in the usual way.

After pushing the return address, main computes for a bit, and then calls subC using a jal instruction (step 2). This puts the return address to main in $ra. Luckily, it does not matter that $ra has been changed because the return address that main will use to return to the operating system is safely on the stack.

subC receives control and computes for a while. Because it does not call another subroutine, subC does not alter $ra and does not need to save it on the stack. When subC returns to main it uses a jr $ra instruction (step 3).

Control returns to main, which computes for a while longer. It returns to the OS by popping the stack into $ra and executing a jr $ra instruction (step 4).

Exception handler service 10 is another way to return to the OS. For this example let us not do that.

Question 2

Is there room on the stack for additional addresses?

Answer

Yes. The same trick (pushing the return address onto the stack) can be repeated many times.

Chain of subroutine call

Now let us look at an example where subroutines call other subroutines. A subroutine that might call another subroutine must push the return address it gets onto the stack. When it returns to its caller, it pops the stack to get the return address.

In the picture, main is called by the OS. As soon as main gets control it pushes $ra onto the stack (step 1). main computes for a while and then calls subA. subA immediately pushes the contents of $ra onto the stack (step 2). The return address that subA will use when it returns control to main is now on the top of the stack.

Next subA calls subB which pushes the contents of $ra onto the stack (step 3). The return address that subB should use when it returns to its caller is now on the top of the stack.

Now subB calls subC (step 4). subC does not call any subroutine so $ra does not have to be saved. subC computes for a while, and then returns to its caller with a jr $ra instruction (step 5).

Now subB has control again. The return address it needs to use is at the top of the stack. subB returns to its caller by popping the stack into $ra and executing jr $ra (step 6).

Now subA has control again. The return address it needs to use is at the top of the stack. subA returns to its caller by popping the stack into $ra and executing jr $ra (step 7).

Finally, main has control. After a computing for a while it returns to the OS by popping the stack into $ra and using the jr $ra instruction (step 8).

Question 3

After subA returns control to main, could main call another subroutine?

Answer

Sure. And that new subroutine can call another one and so on.

Register problem

In the Simple Linkage convention of the previous chapter, registers $s0-$s7 must not be altered by a subroutine. But this restriction creates a problem when subroutines call other subroutines.

Say that main calls subA and that subA calls subB. subA can't save any values in $s0-$s7 (because it is not allowed to alter them). But any values it saves in $t0-$t9 might be clobbered by subB (because subB is allowed to alter them). In effect, subA can't use any registers! Not good.

The solution is to allow subA to use $s0-$s7. However, before using one of these registers, subA must save its value on the stack. Later, when subA returns to its caller, it must restore the register to its initial state.

Question 4

Is it safe to store $s0-$s7 and $ra on the stack?

Answer

Yes. Just be sure to synchronize the pushes and pops so the the correct values go into the correct registers.

Pushing and popping registers

Here is a rule: if a subroutine is expected to alter any of the S registers, it must first push their values onto the stack. Just before returning to the caller it must pop these values from the stack back into the registers they came from.

Here is an example program fragment. Subroutine subB calls subC which uses two S registers.

Question 5

Fill in the blanks so that subB sees its S registers when it regains control.

Answer

# subC expects to use $s0 and $s1         
# subC does not call another subroutine
#       
subC:             
         sub    $sp,$sp,4    # push $s0
         sw     $s0,($sp)
         sub    $sp,$sp,4    # push $s1
         sw     $s1,($sp)

         . . . .             # statements using $s0 and $s1

         lw     $s1,($sp)    # pop s1
         add    $sp,$sp,4
         lw     $s0,($sp)    # pop s0
         add    $sp,$sp,4

         jr     $ra          # return to subB 
         nop       

The registers are popped in the opposite order that they were pushed.

Stack-based linkage convention

The Simple Linkage Convention can be extended into a Stack-based Linkage Convention. This is not an official convention. However it could be used for a small assembly language project because it is not very complicated and does nearly everything you need. If you want to link assembly language routines to "C" programs or to use routines from program libraries you need to use the full, official, linkage rules. (But on the SPIM simulator you can't do that, anyway.) Here are our much simpler rules:

Subroutine Call (done by the caller):

1. Push onto the stack any registers $t0-$t9 that contain values that must be saved. The subroutine might change these registers.
2. Put argument values into $a0-$a3.
3. Call the subroutine using jal.

Subroutine Prolog (done by the subroutine at its beginning):

4. If this subroutine might call other subroutines, push $ra onto the stack.
5. Push onto the stack any registers $s0-$s7 that this subroutine might alter.

Subroutine Body:

6. The subroutine may alter any T or A register, or any S register that it saved in the prolog (step 5).
7. If the subroutine calls another subroutine, then it does so by following these rules.

Subroutine Epilog (done by the subroutine just before it returns to the caller):

8. Put returned values in $v0-$v1
9. Pop from the stack (in reverse order) any registers $s0-$s7 that were pushed in the prolog (step 5).
10. If it was pushed in the prolog (step 4), pop the return address from the stack into $ra.
11. Return to the caller using jr $ra.

Regaining Control from a subroutine (done by the caller):

12. Pop from the stack (in reverse order) any registers $t0-$t9 that were previously pushed (step 1).

Question 6

Why do you think there are both T and S registers? Why not just have S registers and make it a rule that a subroutine must save (and later restore) each one that it uses?

Answer

This is an optimization for speed. Many subroutines need to use only a few registers for temporary values. They can use the T registers without the added expense of saving and restoring them. A subroutine that needs more registers or that needs to have values saved across a subroutine call may use some S registers, but must pay for them by saving and restoring them.

Diagram

These rules are somewhat complicated. Here is a picture. It shows the four sections of subroutine linkage. The basic tasks of each section are:

Subroutine Call: Push all T registers that contain values that will be needed after the call. Put arguments in A registers. jal to the subroutine.

Prolog: If this subroutine calls other subroutines, push $ra. Push all S registers that the subroutine alters.

Body: Normal code, except that it must follow these conventions if it calls a subroutine. T registers and A registers can be used freely, as can any S registers that were saved in the prolog.

Epilog: Put return values in V registers. Pop any S registers. Pop $ra if it was pushed in the prolog. jr $ra back to the caller.

Regaining Control: Pop any T registers that were previously pushed.

Question 7

Is there any limit in these rules about how many levels deep subroutine calls may be?

Answer

No.

Nested subroutine calls

The diagram at right shows the main routine linking to subroutine A, which links to subroutine B, which links to subroutine C. The subroutines link together like beads on a double string. Control is passed from the call to prolog, and from epilog back to the caller. All subroutines in a calling chain (except the one at the bottom) have all five sections (call, prolog, body, epilog, and regaining control).

Each time another subroutine is added to the chain, more data is pushed onto the run-time stack. At the end of the chain of calls the run-time stack has a section of data (saved register values) from each of the subroutines (including main). The currently active subroutine is the one whose data is at the top of the stack (subroutine C, in our upside-down stack).

As each subroutine returns to its caller, its section of data is popped from the stack.

A subroutine does not "know" anything about the stack other than its own section. It pushes its data onto the stack, and later on pops exactly that data back into registers. It does not look at any other data in the stack. It does not even know how deep the stack is.

Sometimes instead of saying "calling a subroutine" people say "activating a subroutine." Each bead in the picture and each section of the stack corresponds to one subroutine activation.

Question 8

After subroutine B returns control to subroutine A, might subroutine A call another subroutine (say subroutine X)?

Answer

Yes. The chain does not need to unwind completely back to main before it starts growing again.

Linear activation chain

A particular subroutine (say A) may call several other subroutines in succession (say B, then X, then Y, then Z). But at any moment, it will have only one subroutine linked to it in the chain of activation. The calls in most modern programming languages follow this stack-based behavior. The currently executing subroutine is at the end of a linear chain of activations that link back to the operating system that first started main.

The run-time stack has the same form as the chain of activation. The top of the stack is for the currently running subroutine. When that subroutine is finished its stack data is popped.

• Stacks are Last In, First Out data structures.
• Subroutines are activated in a Last Called, First Finished order.

When a subroutine reaches its end, it returns to its caller, and the chain is shortened. Its caller might then call another subroutine, and the chain is lengthened again.

While a program that contains many subroutines is executing, the activation chain grows up and down like a yo-yo. Ultimately the chain is of length zero when the main routine returns control to the operating system.

Question 9

Does your brain feel like a yo-yo?

Answer

Uhh.

Programming language history

Well... this is not easy stuff. As proof of that statement, look at computer history. It took several decades before modern high level languages were established. The first one of any importance was Algol, created about 1960. Algol established stack-based subroutine linking. But Algol never quite caught on.

Pascal (created about 1974) was a milestone. It became highly popular and used this stack-based idea of subroutines (which it called procedures and functions). Programming languages can be classified as "Before Pascal" and "After Pascal."

But let us return to the MIPS processor (created in the year 10 AP).

Question 10

Is the MIPS instruction set (its machine instructions) optimized for subroutine call and return?

Answer

Yes.

Example program

Say that you have been given this task:

Write a subroutine that computes the maximum of its two integer arguments. The integers use two's complement representation. Use stack-based linking.

In C, the subroutine prototype would look like this:

int maxInt(int x, int y);

With our stack-based linkage convention this is:

Subroutine maxInt
  Input:   $a0 -- a two's complement integer
           $a1 -- a two's complement integer
  Returns: $v0 -- the maximum of the two integers

The subroutine must be written with no knowledge of what is in any register other than $ra, $a0, and $a1. Indeed, since the subroutine might be used in many different programs, the contents of the other registers cannot be known.

Question 11

Can you write this subroutine without knowing about the caller's registers?

Answer

Yes. That is one of ideas of modularity. You want to write a subroutine without the need to look inside other modules.

Prolog of the subroutine

The subroutine looks something like this:

## maxInt -- compute the maximum of two integer arguments
##
## Input:
## $a0 -- a signed integer
## $a1 -- a signed integer
##
## Returns:
## $v0 -- maximum

         .text
         .globl maxInt

maxInt:

         # prolog


         # body


         # epilog

This subroutine does not call another subroutine.

Question 12

According to the rules of stack-based linking, does this subroutine's prolog need to push the return address?

Answer

No.

Prolog

A prolog is required to push $ra if the subroutine calls another subroutine, and must push any S registers the subroutine uses. But our subroutine does neither. So, the prolog pushes nothing at all.

The body computes the maximum of the two arguments and puts it in $v0.

Question 13

According to the rules of Stack-based Linkage, what should the epilog of this subroutine do?

Answer

The return value (the maximum) is already in $v0. So all the epilog needs to do is return to the caller.

Epilog

It is OK if the return value is already in $v0 when the epilog is reached. Here is the complete subroutine:

## maxInt -- compute the maximum of two integer arguments
##
## Input:
## $a0 -- a signed integer
## $a1 -- a signed integer
##
## Returns:
## $v0 -- maximum

         .text
         .globl maxInt

maxInt:
          # body
          move   $v0,$a0          # max = $a0
          bgt    $a0,$a1,endif    # if $a1 > $a0  
          nop
          move   $v0,$a1          #    max = $a1
endif:                            # endif 
          # epilog
          jr     $ra              # return to caller
          nop

Conceptually, this subroutine could be put in its own file, perhaps maxInt.asm, and separately assembled. Later on it could be used with programs we don't even know about, as long as they follow the Stack-based Linkage Convention. However, with SPIM, all the subroutines for a program must be contained in one big file.

Question 14

Must the nop follow the jr?

Answer

Yes. (Assuming a real MIPS chip with branch delays.) This subroutine will be linked with other subroutines so we better be careful. It is likely that the linker will put another subroutine immediately after this one in memory, and that subroutine's prolog starts with:

sub     $sp,$sp,4      # push the return address
sw      $ra,($sp)

It would be disastrous to unintentionally execute that first instruction when our subroutine returns to its caller.

Maximum of three expressions

Say that some other programmer has been assigned this task:

Write a subroutine that returns the maximum of three expressions: x*x, x*y, and 5*y for integer arguments x and y. The integers use two's complement representation. Use stack-based linking.

With our stack-based linkage convention this is:

Subroutine maxExp
  Input:   $a0 -- x, a two's complement integer
           $a1 -- y, a two's complement integer
           
  Returns: $v0 -- the maximum of x*x, x*y, or 5*y

Question 15

Can this other programmer use the subroutine maxInt you have just written?

Answer

Of course, if linkage conventions are followed.

maxExp

The subroutine looks something like this:

## maxExp -- compute the maximum of three expressions
##
## Input:
## $a0 -- a signed integer, x
## $a1 -- a signed integer, y
##           
##  Returns: 
## $v0 -- the maximum of x*x,  x*y, or 5*y

         .text
         .globl maxExp

maxExp:
         # prolog


         # body

         # subroutine maxInt call
         # subroutine maxInt return

         # subroutine maxInt call
         # subroutine maxInt return

         # epilog

This subroutine has all four parts of the linkage convention.

Question 16

According to the rules of stack-based linking, does this subroutine's prolog need to push the return address?

Answer

Yes — since this subroutine calls another subroutine.

More work from the prolog

maxExp will need to compute three values: x*x, x*y, and 5*y, and so will need to use S registers to hold them in.

Question 17

Since this subroutine uses S registers, what else must its prolog do?

Answer

The S registers used by the subroutine must be saved on the stack.

Pushing S registers

The subroutine now looks like:

## maxExp -- compute the maximum of three expressions
##
## Input:
## $a0 -- a signed integer, x
## $a1 -- a signed integer, y
##           
## Returns: 
## $v0 -- the maximum of x*x,  x*y, or 5*y
##
## Registers:
## $s0 --  x*x
## $s1 --  x*y
## $s2 --  5*y

         .text
         .globl maxExp

maxExp:
         # prolog
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
         
         sub     $sp,$sp,4        # push $s0
         sw      $s0,($sp)
         
         sub     $sp,$sp,4        # push $s1
         sw      $s1,($sp)
         
         sub     $sp,$sp,4        # push $s2
         sw      $s2,($sp)
         
         # body

         # subroutine maxInt call
         # subroutine maxInt return

         # subroutine maxInt call
         # subroutine maxInt return

         # epilog

Question 18

Do you now know what the epilog looks like?

Answer

Yes — it pops what the prolog pushed, and then does a jr.

Popping S registers

The epilog must also ensure that the correct return value is in $v0. That will be done later. Here is the code so far:

## maxExp -- compute the maximum of three expressions
##
## Input:
## $a0 -- a signed integer, x
## $a1 -- a signed integer, y
##           
## Returns: 
## $v0 -- the maximum of x*x,  x*y, or 5*y
##
## Registers:
## $s0 --  x*x
## $s1 --  x*y
## $s2 --  5*y

         .text
         .globl maxExp

maxExp:
         # prolog
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        # push $s0
         sw      $s0,($sp)
         sub     $sp,$sp,4        # push $s1
         sw      $s1,($sp)
         sub     $sp,$sp,4        # push $s2
         sw      $s2,($sp)
         
         # body

         # subroutine maxInt call
         # subroutine maxInt return

         # subroutine maxInt call
         # subroutine maxInt return

         # epilog
         lw      $s2,($sp)        # pop $s2 
         add     $sp,$sp,4                                    
         lw      $s1,($sp)        # pop $s1 
         add     $sp,$sp,4                                    
         lw      $s0,($sp)        # pop $s0 
         add     $sp,$sp,4                                    
         lw      $ra,($sp)        # pop return address
         add     $sp,$sp,4         
         jr      $ra              # return to caller 
         nop

Question 19

Have the pops been done in the correct order?

Answer

Yes. The S registers are popped in the reverse of the order in which they were pushed.

Body

Here is the body filled in:

## maxExp -- compute the maximum of three expressions
##
## Input:
## $a0 -- a signed integer, x
## $a1 -- a signed integer, y
##           
## Returns: 
## $v0 -- the maximum of x*x,  x*y, or 5*y
##
## Registers:
## $s0 --  x*x
## $s1 --  x*y
## $s2 --  5*y

         .text
         .globl maxExp

maxExp:
         # prolog
         
         # body
         mul     $s0,$a0,$a0      # x*x
         mul     $s1,$a0,$a1      # x*y
         li      $t0,5
         mul     $s2,$t0,$a1      # 5*y
         
         # subroutine maxInt call
         move    $a0,$s0          # compute max of x*x
         move    $a1,$s1          # and x*y
         jal     maxInt           # max returned in $v0
         nop
         # subroutine maxInt return

         # subroutine maxInt call
         move    $a0,$v0          # compute max of
         move    $a1,$s2          # current max, and 5*y 
         jal     maxInt           # total max will be in $v0
         nop
         # subroutine maxInt return

         # epilog

Question 20

After the return from the second call to maxInt, the maximum of the three expressions will be in $v0. Is this where we want it?

Answer

Yes. The returned value from maxExp should be in $v0, and it is.

Complete MaxExp

Here is the complete subroutine:

## maxExp -- compute the maximum of three expressions
##
## Input:
## $a0 -- a signed integer, x
## $a1 -- a signed integer, y
##           
## Returns: 
## $v0 -- the maximum of x*x,  x*y, or 5*y
##
## Registers:
## $s0 --  x*x
## $s1 --  x*y
## $s2 --  5*y

         .text
         .globl maxExp

maxExp:
         # prolog
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        # push $s0
         sw      $s0,($sp)
         sub     $sp,$sp,4        # push $s1
         sw      $s1,($sp)
         sub     $sp,$sp,4        # push $s2
         sw      $s2,($sp)

         # body
         mul     $s0,$a0,$a0      # x*x
         mul     $s1,$a0,$a1      # x*y
         li      $t0,5
         mul     $s2,$t0,$a1      # 5*y
         
         move    $a0,$s0          # compute max of x*x
         move    $a1,$s1          # and x*y
         jal     maxInt           # current max in $v0
         nop

         move    $a0,$v0          # compute max of
         move    $a1,$s2          # current max, and 5*y 
         jal     maxInt           # total max will be in $v0
         nop
         
         # epilog
         lw      $s2,($sp)        # pop $s2 
         add     $sp,$sp,4                                    
         lw      $s1,($sp)        # pop $s1 
         add     $sp,$sp,4                                    
         lw      $s0,($sp)        # pop $s0 
         add     $sp,$sp,4                                    
         lw      $ra,($sp)        # pop return address
         add     $sp,$sp,4         
         jr      $ra              # return to caller 
         nop         

Question 21

Conceptually, could this subroutine be put into its own source file and separately assembled from maxInt?

Answer

Yes.

Complete program

Here is the complete (and completely useless) program that asks the user for two integers, x and y, and then prints out the maximum of x*x, x*y, or 5*y. Copy the program to one big file to run it with SPIM. Conceptually, though, each subroutine should go into a separate file.

## Driver --  main program for the application

         .text
         .globl main
 
main:
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        # push $s0
         sw      $s0,($sp)
         
         la      $a0,xprompt      # prompt the user
         li      $v0,4            # service 4
         syscall
         li      $v0,5            # service 5 -- read int
         syscall                  # $v0 = integer
         move    $s0,$v0          # save x
         
         la      $a0,yprompt      # prompt the user
         li      $v0,4            # service 4
         syscall
         li      $v0,5            # service 5 -- read int
         syscall                  # $v0 = integer
         
                                  # prepare arguments
         move    $a0,$s0          # x         
         move    $a1,$v0          # y
         jal     maxExp           # maximum expression
         nop                      # returned in $v0
         move    $s0,$v0          # keep it safe

         la      $a0,rprompt      # output title
         li      $v0,4            # service 4
         syscall

         move    $a0,$s0          # get maximum
         li      $v0,1            # print it out
         syscall
                                                      
         lw      $ra,($sp)        # pop $s0
         add     $s0,$sp,4
         lw      $ra,($sp)        # pop return address
         add     $sp,$sp,4
         
         jr      $ra              # return to OS 
         nop
         
         .data
xprompt: .asciiz  "Enter a value for x --> "
yprompt: .asciiz  "Enter a value for y --> "
rprompt: .asciiz  "The maximum expression is: "

## maxInt -- compute the maximum of two integer arguments
##
## Input:
## $a0 -- a signed integer
## $a1 -- a signed integer
##
## Returns:
## $v0 -- maximum

         .text
         .globl maxInt

maxInt:
         # body
         move   $v0,$a0          # max = $a0
         bgt    $a0,$a1,endif    # if $a1 > $a0  
         nop
         move   $v0,$a1          #    max = $a1
endif:                           # endif 
         # epilog
         jr     $ra              # return to caller
         nop
          
## maxExp -- compute the maximum of three expressions
##
## Input:
## $a0 -- a signed integer, x
## $a1 -- a signed integer, y
##           
## Returns: 
## $v0 -- the maximum of x*x,  x*y, or 5*y
##
## Registers:
## $s0 --  x*x
## $s1 --  x*y
## $s2 --  5*y

         .text
         .globl maxExp

maxExp:
         # prolog
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        # push $s0
         sw      $s0,($sp)
         sub     $sp,$sp,4        # push $s1
         sw      $s1,($sp)
         sub     $sp,$sp,4        # push $s2
         sw      $s2,($sp)

         # body
         mul     $s0,$a0,$a0      # x*x
         mul     $s1,$a0,$a1      # x*y
         li      $t0,5
         mul     $s2,$t0,$a1      # 5*y
         
         move    $a0,$s0          # compute max of x*x
         move    $a1,$s1          # and x*y
         jal     maxInt           # current max in $v0
         nop

         move    $a0,$v0          # compute max of
         move    $a1,$s2          # current max, and 5*y 
         jal     maxInt           # total max will be in $v0
         nop
         
         # epilog
         lw      $s2,($sp)        # pop $s2 
         add     $sp,$sp,4                                    
         lw      $s1,($sp)        # pop $s1 
         add     $sp,$sp,4                                    
         lw      $s0,($sp)        # pop $s0 
         add     $sp,$sp,4                                    
         lw      $ra,($sp)        # pop return address
         add     $sp,$sp,4         
         jr      $ra              # return to caller 
         nop         

Run the program using SPIM settings: Bare machine (off), Allow pseudo instructions (on), load exception file (on), delayed branches (on) delayed load (on), mapped I/O (off), Quiet (off). Run the program after loading it with Simulator/Go.

Question 22

Would you like to skip to the end of the chapter?

Answer

Yes.

That probably would not hurt. But the next long example has a few points of interest.

Another long example program

Some computers, such as the Digital Equipment Corporation (DEC) Vax, have specialized call and return machine instructions. But experimentally these add little to performance. The general purpose instructions of a reduced instruction set proved to be faster.

Here is an example program: the program is to read in lines of text from the user. Lower case characters from each line are converted to upper case. The user quits the program by entering a single character 'Q' at the start of a line.

Question 23

How can character 'a' be converted to character 'A'?

Answer

'a' - ('a' - 'A') == 'A', or, 'a' - 32 == 'A'. Subtracting 32 from a lower case character results in the corresponding upper case character (in ASCII).

Complete program design

Here is the complete design of the program. Glance over it to get the general idea. Its individual routines are explained in the following pages. This design uses more subroutines than usual because its purpose is to show subroutine linkage.

A subroutine starts with a pill-shaped box that shows the name of the subroutine. A box with double vertical lines for its sides (like doLines in main) designates a subroutine call. The program starts execution with main.

Question 24

At the maximum, how many levels deep is subroutine nesting in this program?

Answer

Four levels deep: main calls doLines which calls convert which calls conCh.

main subroutine

An advantage of modular programming is that each subroutine can be displayed and explained independently of the others. Here is the design of main.

To simplify the discussion, branch delays and load delays have been turned OFF in SPIM.

         .text
         .globl  main
main:
         ??????                   # what goes here?
         
         la      $a0,mainPr       # prompt the user
         li      $v0,4            # service 4
         syscall

         jal     doLines          # process lines of input
         
         ??????                   # what goes here?
         
         jr      $ra              # return to OS 

         .data
mainPr:  .ascii  "Type each line of text followed by ENTER.\n"
         .asciiz "Type Q at the start of a line to finish.\n"

Question 25

According to the Stack-based Linking convention does main need to push and later pop the return address?

Answer

Yes, because main calls a subroutine. The completed code for main is below.

         .text
         .globl  main
main:
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
         
         la      $a0,mainPr       # prompt the user
         li      $v0,4            # service 4
         syscall

         jal     doLines          # process lines of input
         
         lw      $ra,($sp)        # pop return address
         add     $sp,$sp,4
         
         jr      $ra              # return to OS 

         .data
mainPr:  .ascii  "Type each line of text followed by ENTER.\n"
         .asciiz "Type Q at the start of a line to finish.\n"

Subroutine doLines

The main routine calls doLines. The flowchart shows the design for that routine. Below is its (incomplete) code.

Question 26

No time like the present to fill in those blanks.

Answer

The relevant section is filled in, below.

loop:                             # get a line
         la      $a0,line         # argument: address of buffer
         li      $a1,132          # argument: length of buffer
         jal     getline          # get line from user
         
         la      $a0,line         # if "Q"
         jal     testEnd          # return to caller
         beqz    $v0,endloop          

                                  # convert to capitals
         la      $a0,line         # argument: address of buffer
         li      $a1,132          # argument: length of buffer
         jal     convert          # convert

Subroutine getLine

Subroutine getLine reads a line into a buffer. The buffer is in the data section of the caller. The address of the buffer is passed as a parameter.

# getLine -- read in a line of user input
#
# on entry:
#    $a0 -- address of input buffer
#    $a1 -- length of buffer
#
# on exit:
#    no return values

         .text
         .globl  getLine
getLine:   
         move    $t0,$a0          # save buffer address          
         la      $a0,prompt       # prompt the user
         li      $v0,4            # service 4
         syscall

         move    $a0,$t0          # restore buffer address
         li      $v0,8            # service 8
         syscall                  # read in a line to the buffer
         
         jr      $ra              # return to caller 

         .data
prompt:
         .asciiz ">"

Notice how getLine reads data into an input buffer defined externally to itself. The parameters in $a0 and $a1 specify this buffer. It would be a design mistake to have getLine read into its own buffer or to hard-code the symbolic address of a buffer in another subroutine.

The buffer address parameter and the length parameter are similar to the parameters used in many "C" functions. Study this example to help in your future (or present) understanding of "C" pointer variables.

Question 27

Does getLine need to store a return address on the stack?

Answer

No. It does not call a subroutine and so can leave the return address in $ra.

Subroutine convert

After reading in a line, doLines calls convert to convert the entire line to upper case. convert calls conChar for each character in the line.

convert needs a register to hold a character pointer that moves through the line. It can't use a T register for this because it calls another subroutine. So it uses an S register. But it must restore the S register to its original state when it returns to its caller.

This is the situation that calls for pushing an S register on the stack, using it in the subroutine body, and then popping it from the stack before returning to the caller.

Question 28

Fill in the missing code.

Answer

See below.

Complete convert

The subroutine convert uses $s0 as a character pointer because $a0 might be changed by conChar. You might think that it would be a good idea to look inside conChar to see if, in fact, it actually changes $a0. But this is a violation of modularity. It is much better to have a calling convention, and to follow it, than to make modules depend critically on each other's quirks.

For example, conChar doesn't actually alter $a0. At least not now, but later on, conChar might be changed. Then you (or the unfortunate programmer that inherited your program) would have to look everywhere conChar was used to see what assumptions were made.

# convert -- convert a line to all capitals
#
# on entry:
#    $a0 -- address of input buffer
#    $a1 -- length of input buffer
#
# register use:
#    $s0 -- pointer into character buffer
#
# on exit:
#    no return values
         .text
         .globl  convert
convert:   
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        # push $s0
         sw      $s0,($sp)

                                  # for ( p=buffer; *p!=0; p++ )
         move    $s0,$a0          # p=buffer

cloop:   lbu     $a0,($s0)        # get a char from the string
         beqz    $a0,endC         # exit if null byte
                                  # argument a0: char to convert
         jal     conChar          # convert character
         sb      $v0,($s0)        # put converted char into string                 
         addu    $s0,$s0,1        # p++
         b       cloop         
 
endC:   
         lw      $s0,($sp)        # pop $s0 
         add     $sp,$sp,4                                    
         lw      $ra,($sp)        # pop return address
         add     $sp,$sp,4         
         jr      $ra              # return to caller 

Question 29

Would it be a good idea to look into doLines to see if $s0 is important and actually needs to be saved?

Answer

No.

Complete capitalize program

Here is the complete program. It would be useful to copy it to a file and to run it with SPIM.

# capitalize.asm --- convert user input to capitals and discard punctuation
#
# This program uses stack-based linkage.  SPIM Settings: allow pseudoinstructions,
# disable delayed branches and disable delayed load, load trap file.
#
         .text
         .globl  main

main:
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
         
         la      $a0,mainPr       # prompt the user
         li      $v0,4            # service 4
         syscall

         jal     doLines          # process lines of input
         
         lw      $ra,($sp)        # pop return address
         add     $sp,$sp,4
         
         jr      $ra              # return to OS 

         .data
mainPr:  .ascii  "Type each line of text followed by ENTER.\n"
         .asciiz "Type Q at the start of a line to finish.\n"
         
# doLines -- read in and process each line of user input
#
# on entry:
#    $a0 -- address of the prompt text
#
# on exit:
#    no return values

         .text
         .globl  doLines
doLines:   
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
 
loop:                             # get a line
         la      $a0,line         # argument: address of buffer
         li      $a1,132          # argument: length of buffer
         jal     getLine          # get line from user
         
         la      $a0,line         # if "Q"
         jal     testEnd          # return to caller
         beqz    $v0,endloop          

                                  # convert to capitals
         la      $a0,line         # argument: address of buffer
         la      $a1,132          # argument: length of buffer
         jal     convert
         
         la      $a0,outline      # print out the result
         li      $v0,4
         syscall
         
         b       loop             # continue with next line
         
endloop:          
         lw      $ra,($sp)        # pop return address
         add     $sp,$sp,4         
         jr      $ra              # return to caller 

         .data
outline: .ascii  ":"              # padding so output lines up with input
line:    .space  132              # input buffer
         
# getLine -- read in a line of user input
#
# on entry:
#    $a0 -- address of input buffer
#    $a1 -- length of buffer
#
# on exit:
#    no return values

         .text
         .globl  getLine
getLine:   
         move    $t0,$a0          # save buffer address          
         la      $a0,prompt       # prompt the user
         li      $v0,4            # service 4
         syscall

         move    $a0,$t0          # restore buffer address
         li      $v0,8            # service 8
         syscall                  # read in a line to the buffer
         
         jr      $ra              # return to caller 

         .data
prompt:
         .asciiz ">"
              
# testEnd -- check if a line is 'Q'
#
# on entry:
#    $a0 -- address of input buffer
#
# on exit:
#    $v0 -- 0 if line is equal to Q, 1 if not

         .text
         .globl  testEnd
testEnd:   
         li      $v0,1            # assume not equal
         
         lbu     $t0,0($a0)       # get first char of line
         li      $t1,'Q'          # get 'Q'
         bne     $t0,$t1,endT     # if not equal, end the test
         
         lbu     $t0,1($a0)       # get second char of line
         li      $t1,'\n'         # it should be CR
         bne     $t0,$t1,endT     # if not equal, end the test
          
         li      $v0,0            # 'Q' has been found

endT:                       
         jr      $ra              # return to caller        
         
# convert -- convert a line to all capitals
#
# on entry:
#    $a0 -- address of input buffer
#    $a1 -- length of input buffer
#
# register use:
#    $s0 -- pointer into character buffer
#
# on exit:
#    no return values

         .text
         .globl  convert
convert:   
         sub     $sp,$sp,4        # push the return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        # push $s0
         sw      $s0,($sp)

                                  # for ( p=buffer; *p!=0; p++ )
         move    $s0,$a0          # p=buffer

cloop:   lbu     $a0,($s0)        # get a char from the string
         beqz    $a0,endC         # exit if null byte
                                  # argument a0: char to convert
         jal     conChar          # convert character
         sb      $v0,($s0)        # put converted char into string                 
         addu    $s0,$s0,1        # p++
         b       cloop         
 
endC:   
         lw      $s0,($sp)        # pop $s0 
         add     $sp,$sp,4                                    
         lw      $ra,($sp)        # pop return address
         add     $sp,$sp,4         
         jr      $ra              # return to caller 
       
# conChar -- convert a character to a capital
#
# on entry:
#    $a0 -- character
#
# on exit:
#    $v0 -- converted character

         .text
         .globl  conChar
conChar:   
         move    $v0,$a0          # assume ch will not change
                                  # is ch in 'a' .. 'z' &
         li      $t0,'a'          # ch < 'a' ?
         blt     $a0,$t0,outc    
         li      $t0,'z'          # 'z' < ch ?
         blt     $t0,$a0,outc                     
         sub     $v0,$a0,32       # convert ch to upper case

outc:    jr      $ra              # return to caller 

Question 30

In which subroutine is the buffer for the input characters? Is a copy of those characters made when other subroutines operate on them?

Answer

The string buffer line is defined in doLines. No copy is made of the characters in the buffer. However, other subroutines have access to the buffer since its address is passed as an argument (in $a0) to them. This technique is very common in "C" although, of course, the syntax for doing it is different.

Chapter quiz

Instructions: For each question, choose the single best answer. Make your choice by clicking on its button. You can change your answers at any time. When the quiz is graded, the correct answers will appear in the box after each question.

Question 1

In the stack-based linkage convention, what subroutines must save the return address to their caller on the stack?

• (A) all subroutines
• (B) only main
• (C) any subroutine that calls another subroutine.
• (D) any subroutine that does not call another subroutine.

Answer

C

Question 2

Which of the following code fragments saves the return address?

• (A)

  sub $ra,$ra,4
  sw  $sp,($ra)

• (B)

  sub $sp,$sp,4
  sw  $ra,($sp)

• (C)

  add $ra,$ra,4
  sw  $sp,($ra)

• (D)

  sw  $ra,($sp)
  sub $sp,$sp,4

Answer

B

Question 3

When an operating system calls a main routine, what is in $ra?

• (A) $ra is all zeros to indicate the beginning of the call chain.
• (B) The return address to a point in the operating system.
• (C) The entry point to main
• (D) Random information.

Answer

B

Question 4

Subroutine A calls subroutine B. Subroutine A has information in $t0 that it needs preserved. All the S registers are in use. What can be done?

• (A) Subroutine A saves $t0 in a V register.
• (B) Subroutine B saves $t0 on the stack.
• (C) Subroutine A saves $t0 on the stack after calling subroutine B.
• (D) Subroutine A saves $t0 on the stack before calling subroutine B.

Answer

D

Question 5

What are the two jobs of a subroutine's prolog?

• (A) Save the return address (if needed) and save any S registers it might use.
• (B) Initialize variables and retrieve arguments.
• (C) Save the return address (if needed) and save any T registers it might use.
• (D) Put return values in V registers and restore S registers.

Answer

A

Question 6

What are the jobs of a subroutine's epilog?

• (A) (i) put returned values in S registers, (ii) pop the return address, if needed, (iii) jr back to the caller.
• (B) (i) pop the return address, if needed, (ii) jr back to the caller.
• (C) (i) put returned values in V registers, (ii) pop any S registers that were pushed, (iii) pop the return address, if needed, (iv) jr back to the caller.
• (D) (i) put returned values in A registers, (ii) pop any T registers that were pushed, (iii) pop the return address, if needed, (iv) jr back to the caller.

Answer

C

Question 7

In what order are registers popped off the stack when they are being restored?

• (A) The same order that they were pushed.
• (B) The reverse of the order that they were pushed.
• (C) Alphabetical order.
• (D) Numerical order.

Answer

B

Question 8

Is there any limit to how deep subroutine calls can be nested?

• (A) Yes. Only main can call a subroutine, the the nesting is one level deep.
• (B) Yes. Calls can be nested no more than 8 levels deep.
• (C) No, as long as there is memory for the stack, calls can be nested any level deep.
• (D) No, as long as there is memory on the hard disk to give each subroutine a virtual address space.

Answer

C

Question 9

During execution of an application made up of many subroutines, how does the activation chain behave?

• (A) It repeatedly grows and shrinks depending on what subroutines are active.
• (B) It constantly grows longer and longer.
• (C) It grows longer and develops branches as subroutines call different subroutines.
• (D) It grows to its maximum length and then stays there until the program is over.

Answer

A

Question 10

What was the first prominent programming language that used stack-based subroutine linking?

• (A) FORTRAN
• (B) Algol
• (C) COBAL
• (D) C

Answer

B

Programming exercises

NOTE: Use the Stack-based Linkage Convention for these programs.

In the Settings menu of SPIM set Bare Machine OFF, Allow Pseudo Instructions ON, Load Trap File ON, Delayed Branches ON, Delayed Loads ON, Mapped IO ON, Quiet OFF.

Exercise 1 - same string

Write a program that prompts the user for a string. The program reads in the string and then prompts for another string and reads it in. Then the program writes a message that says if the two strings are character-by-character identical.

Use at least three routines (counting main) for this.

Exercise 2 - same string, improved

Modify the program in Exercise 1 that the program inputs two strings and writes out a third string. The third string has a blank in positions where the two characters are identical and has a "*" in positions where the characters are not identical.

Exercise 3 - triangle or square

Write a program that asks if the user wants a triangle or a square. It then prompts for the size of the object (the number of lines it takes to draw the object). The program then writes a triangle or a square of stars ("*") to the monitor.

*******
*******
*******
*******
*******
*******
*******

or

*
**
***
****
*****
******
*******

Write a subroutine for each figure. In them, use a subroutine starline that writes a line of a given number of stars.

Frame-based Linkage Convention, Variables, and Recursion

This chapter builds further on the stack-based linkage convention to create a frame-based linkage convention. A stack frame is the section of the run-time stack that holds the data of a subroutine.

Chapter Topics:

• Stack frames and the frame pointer
• Local variables
• Simplified Frame-based Linkage Convention
• Compiler optimizations
• Recursion
• Storage classes: static, automatic, dynamic
• Entry points

Question 1

(Thought Question:) What is a local variable in a higher level language?

Answer

A local variable holds values for a subroutine while the subroutine is active.

For example, in the following function (written in C), b and c are local variables.

int mysub( int arg )
{
  int b, c;  
  
  b = arg*2;
  c = b + 7;
  return c;  
}

(Other programming languages have the same idea, implemented with different syntax.)

Implementation of local variables

In a high-level language a local variable is implemented as a location on the run-time stack. Each time a subroutine is activated, new locations for variables are pushed onto the stack. The section of the stack for each activation is called a stack frame or an activation record. A frame pointer holds the address of the stack frame for a subroutine.

When a subroutine returns to its caller the stack frame is popped from the stack. Thus, local variables only exist as memory locations while a subroutine is active. A subroutine is active if it is currently executing, or if a subroutine it has called is active.

The format of a stack frame used by MIPS language processors is complicated. There are many situations that must be handled and many optimizations. It takes a compiler to do it correctly. These notes describe a much simplified stack frame.

The important part is to understand what a local variable is, in general: a location on the run-time stack. This is an important idea in computer science, one you will run into repeatedly as you study advanced topics.

Question 2

In a high-level language are there variables that are not local?

Answer

Yes.

Variables

Programming languages have global variables. Also, a program block nested within other program blocks can use variables of the outer blocks. Let us skip these details and implement local variables, only. The details may be covered in a course on compilers or in a course on programming languages.

The picture shows a stack frame of an active subroutine. As always (for these notes), each item on the stack is four bytes long.

As previously, the caller pushes values from T registers that it will need to restore when control returns. The subroutine (the callee) pushes values from S registers that it might change.

In this example, space is reserved in the stack for implementing four local variables a, b, i and j. In the picture, the space reserved for variable a is labeled "a", but of course what is in that space is the 32-bit pattern that the variable holds. Usually our variables will be integer variables.

A variable is a location in the run-time stack that is used to store data. The values stored in a variable may change as the program executes.

Variable a is the space on the stack. There is no other "thing" that implements the variable. In the program, manipulating a variable is done by using registers to load and store values from the variable's space in the stack. However, the variable is the space in the stack, not a register.

Question 3

When the stack frame is popped, what happens to the local variables?

Answer

Conceptually, the local variables cease to exist when the stack frame that implements them is popped.

Frame pointer

Register $30 is reserved, by software convention, for use as a frame pointer. In the extended assembler it has the mnemonic name $fp. When a subroutine starts running, the frame pointer and the stack pointer contain the same address.

While the subroutine is active, the frame pointer, points at the top of the stack. (Remember, our stacks grow downward, so in the picture $fp is correctly pointing at the last word that was pushed onto the stack, the top of the stack.)

But the stack (and the stack pointer) may be involved in arithmetic expression evaluation. This often involves pushing and popping values onto and off of the stack. If $sp keeps changing, it would be hard to access a variable at a fixed location on the stack.

To make things easy for compilers (and for human assembly language programmers) it is convenient to have a frame pointer that does not change its value while a subroutine is active. The variables will always be the same distance from the unchanging frame pointer.

In the subroutine prolog, the caller's frame pointer is pushed onto the stack along with the stack pointer and any S registers. Now the subroutine makes room on the stack for variables and points the frame pointer to the top of the stack frame.

Question 4

Write the instruction that loads register $t5 with the value held in the variable a:

lw $t5, ______ ( ______ )

(Hint: use $fp as a base register.)

Answer

lw $t5,12( $fp )

Sample code

Imagine that the following statement is part of the subroutine whose stack frame is at right:

a = b + i + j;

This is how a compiler might implement that statement:

lw    $t0,8($fp)     # get b
lw    $t1,4($fp)     # get i
lw    $t2,0($fp)     # get j
addu  $t3,$t0,$t1    # b + i
addu  $t3,$t3,$t2    # b + i + j
sw    $t3,12($fp)    # a =    

The particular registers used to temporarily hold values from the local variables are arbitrary. In another section of code, a different register might be used with variable b than is used here.

Question 5

Play compiler: translate the following statement into assembly language:

a = a + 1;

Use register $t0 to temporarily hold the value in a.

Answer

lw      $t0,12($fp)    # get a
addiu   $t0,$t0,1      # a + 1
sw      $t0,12($fp)    # a = 

Frame-based linkage convention

A real-world linkage convention allows many types of objects to go into a stack frame. The following rules assume that the stack only stores 32-bit values. There are other features of real-world linkage that the following does not have.

Calling a Subroutine (done by the caller):

1. Push any registers $t0-$t9 that contain values that must be saved. Push the registers in numerical order.
2. Put argument values into $a0-$a3.
3. Call the subroutine using jal.

Subroutine Prolog (done by the subroutine):

4. Push $ra (always).
5. Push the caller's frame pointer $fp.
6. Push any of the registers $s0-$s7 that the subroutine might alter.
7. Initialize the frame pointer: $fp = $sp - space_for_variables. The "space for variables" is four times the number of local variables. (Remember that subtracting from $sp grows the stack, and that our variables are always four bytes wide).
8. Initialize the stack pointer: $sp = $fp.

Subroutine Body:

9. At this point the stack looks like the picture.
10. The subroutine may alter any T, A, or V register, or any S register that it saved in the prolog.
11. The subroutine refers to local variables as disp($fp).
12. The subroutine may push and pop values on the stack using $sp.
13. If the subroutine calls another subroutine, then it does so by following these rules.

Subroutine Epilog (done at the end of the subroutine):

14. Put return values in $v0-$v1
15. $sp = $fp + space_for_variables.
16. Pop into $s0-$s7 any values for them that were previously saved in the frame (in step6).
17. Pop the caller's frame pointer into $fp.
18. Pop $ra (always).
19. Return to the caller using jr $ra.

Regaining Control from a Subroutine (done by the caller):

20. Pop any registers $t0-$t9 that the caller previously pushed.

Question 6

When the caller gets control back, are its frame pointer and stack pointer the same as when it called the subroutine?

Answer

Yes.

Diagram

Those rules are complicated. In broad outline it works the same way as the previous chapter's stack-based linkage convention. But now, the subroutine prolog pushes room on the stack for local variables, and the epilog pops that room.

Here is a picture. It shows the sections of subroutine linkage. The basic tasks of each section are:

Subroutine Call: Push any T registers that contain values that are needed. Put arguments in A registers. jal to the subroutine.

Prolog: Push $ra and the caller's $fp. Push any S register the subroutine will alter. Initialize the subroutine's $fp and $sp.

Body: Normal code, except it must follow these conventions if it calls another subroutine. T and A registers can be used freely, as can any S registers that were saved in the prolog. Variables on the stack are accessed using disp($fp).

Epilog: Put return values in V registers. Reset $sp. Pop any S registers. Pop the caller's $fp and $ra. jr $ra back to the caller.

Regaining Control: Pop any previously pushed T registers.

Question 7

Is there a limit to how many variables a subroutine may have?

Answer

No.

Example program

The number of registers that MIPS (or other processor) has does not limit the number of variables that subroutines can have. As many variables as you want can be allocated on the stack. Here is an example program, written in a C-like language.

main()
{
  int a;
  a = mysub( 6 );
  print( a );
}

int mysub( int arg )
{
  int b,c;
  
  b = arg*2;
  c = b + 7;
  
  return c;  
}

To the operating system, main() is a subroutine. When main() first gets control it must follow the rules under "subroutine prolog".

Question 8

How much space on the stack is needed for the variables in main()? _____

Answer

Four bytes, for the single variable a.

main()

Here is the code for main(), with some blanks. The rules for the subroutine prolog are copied from above.

Recall that

sw      $ra,($sp)

is shorthand for

sw      $ra,0($sp)

The instruction stores the contents of $ra at the address in the stack pointer. (The contents are stored on the top of the stack.)

Question 9

Fill in the blanks as the comments suggest.

Answer

See below.

Subroutine call

At this point we have "compiled" into assembly language the first three lines of the "C" program. Next, the program calls the subroutine mysub(). This is shown, in outline form, in the following code.

Question 10

Fill in the blanks.

Answer

#  main()
#  {
#    int a;
#    a = mysub( 6 );
#    print( a );
#  }
         .text
         .globl  main
main:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)

                                  #   3. No S registers to push

         addiu   $fp,$sp,4        #   4. $fp = $sp + space_for_variables

         move    $sp,$fp          #   5. $sp = $fp

                                  # subroutine call
                                  #   1. No T registers to push
         li      $a0,6            #   2. Put argument into $a0
         jal     mysub            #   3. Jump and link to subroutine
         
                                  # return from subroutine   
         
         . . . .     
         
                                  # epilog
         jr      $ra              # return to OS 

Prolog for mysub()

Of course, mysub starts with a subroutine prolog. There are two variables, so space is assigned to them on the stack.

The subroutine could be written without using $s1. It is used to show how linkage works.

Question 11

Fill in those blanks.

Answer

See below.

Using variables

The subroutine uses two variables so there are eight bytes of space on the stack frame for them.

The program is not very efficient, as written. There is no need to store and then load b. A non-optimizing compiler might do just that, however.

Question 12

Fill in the blanks. Assume that b is at displacement 0 and that c is at displacement 4.

Answer

See below.

Subroutine epilog

The epilog of a subroutine prepares the values that are returned to the caller. It then restores the registers and stack to how they were when the subroutine first got control. Finally it returns to the caller.

Question 13

Those blanks need filling.

Answer

See below.

Complete mysub()

Here is the complete program. Notice that the code in the body of the subroutine is only five statements long. But the entire subroutine, including the code for subroutine linkage, is 22 statements long! Subroutine linkage can be expensive.

#  int mysub( int arg )
#  {
#    int b,c;                     // b: 0($fp)
#                                 // c: 4($fp)
#    b = arg*2;
#    c = b + 7;
#    
#    return c;  
#  }
         .text
         .globl  mysub
mysub:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
         sub     $sp,$sp,4        #   3. Push register $s1
         sw      $s1,($sp)
         sub     $fp,$sp,8        #   4. $fp = $sp - space_for_variables
         move    $sp,$fp          #   5. $sp = $fp
         
                                  # body of subroutine     
         mul     $s1,$a0,2        #     arg*2
         sw      $s1,0($fp)       # b = "   "
         
         lw      $t0,0($fp)       # get b
         add     $t0,$t0,7        #     b+7
         sw      $t0,4($fp)       # c = "  "
         
                                  # epilog
         lw      $v0,4($fp)       #   1. Put return value in $v0        
         add     $sp,$fp,8        #   2. $sp = $fp + space_for_variables
         lw      $s1,($sp)        #   3. Pop register $s1
         add     $sp,$sp,4        #          
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #            
         jr      $ra              #   6. return to caller 

Question 14

What must the caller do when control returns to it?

Answer

The caller must restore any T registers it saved.

Back to main()

In this example, main() did not save any T registers. There is nothing to do when it regains control from the subroutine other than to use the value returned in $v0.

Look down to the section where main regains control. Fill in the blanks that follow so that the value returned by the subroutine (contained in $v0) is copied to the variable a on the stack.

The next few statements load $a0 with the value of a from the stack, and then print that value by using a SPIM service. Again, this could have been done without involving the stack, but this example shows the type of code that a non-optimizing compiler might produce.

Question 15

Fill in the blanks.

Answer

See below.

Complete main()

Here is the complete main() routine. Nearly all of the code is concerned with subroutine linkage. This is typical.

#  main()
#  {
#    int a;                      // a: 0($fp)
#    a = mysub( 6 );
#    print( a );
#  }
         .text
         .globl  main
main:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
                                  #   3. No S registers to push
         sub     $fp,$sp,4        #   4. $fp = $sp - space_for_variables
         move    $sp,$fp          #   5. $sp = $fp

                                  # subroutine call
                                  #   1. No T registers to push
         li      $a0,6            #   2. Put argument into $a0
         jal     mysub            #   3. Jump and link to subroutine
         
                                  # return from subroutine 
                                  #   1. No T registers to restore
                                  
         sw     $v0,0($fp)        # a = mysub( 6 )
        
                                  # print a
         lw     $a0,0($fp)        # load a into $a0
         li     $v0,1             # print integer service
         syscall                                  
                                  # epilog
                                  #   1. No return value         
         add     $sp,$fp,4        #   2. $sp = $fp + space_for_variables       
                                  #   3. No S registers to pop      
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #                                    
         jr      $ra              # return to OS 

If you wish to run the program, copy and paste main() and mysub() into one file.

Question 16

Rewrite the following code so that it does the same thing as the original but without using a variable.

main()
{
  int a;   
  a = mysub( 6 );
  print( a );
}

Answer

An optimizing compiler might output assembly code that eliminates the intermediate variable a, as if the programmer had written:

main()
{
  print(  mysub( 6 ) );
}

Example program: factorial(N)

The next example program prompts the user for an integer, reads in the integer, and prints the factorial. The SPIM console window shows the output of several runs of the program. The pseudo-code for the program is:

#  main()
#  {
#    int a, b;  // a: 0($fp),  b: 4($fp)
#    write("enter an int:")
#    read( a );
#    b = fact( a );
#    write("factorial is:")
#    print( b );
#  }

#  int fact( int n )
#  {
#    if ( n <= 1 )
#      return 1;
#    else
#      return n*fact(n-1);
#  }

The math definition of factorial is:

fact( n ) = 1, if n <= 1
  
          = n * fact( n-1 ), otherwise

Question 17

You have very likely seen the factorial function before (and are very likely sick of it!) But just in case:

What is the factorial of 5? _____

Answer

fact(5) == 5*fact(4)
        == 5*( 4*fact(3) ) 
        == 5*( 4*( 3*fact(2)) )
        == 5*( 4*( 3*(2*fact(1))) ) 
        == 5*( 4*( 3*(2*1)) ) 
        == 5*4*3*2*1 
        == 120

Activation chain

If the subroutine fact() is called with an argument greater than one, it calls itself, fact(), with a new argument. This is a new activation of the same code. This is not a problem because the data for the first activation of fact() is pushed onto the stack. The new activation has a fresh stack frame for its data.

When the first activation gets control again, its data is available at the top of the stack. This process is illustrated at right. Each activation is represented as a green circle. Each activation works with its own data in its own stack frame. The activations do not interfere with each other.

#  int fact( int n )
#  {
#    if ( n <= 1 )
#      return 1;
#    else
#      return n*fact(n-1);
#  }

Each bead on the activation chain represents an activation of a subroutine. The label on a downward arc is the argument to an activation. The label on an upward arc is the returned value.

Each bead on the activation chain corresponds to one stack frame. The picture of the stack shows what it looks like when the activation fact(1) is running.

When the value 120 is returned to main, only main is active, the stack contains only its stack frame, and the activation chain consists only of main.

Question 18

A downward arc corresponds to a _____ of one stack frame. An upward arc corresponds to a _____ of one stack frame.

Answer

A downward arc corresponds to a push of one stack frame. An upward arc corresponds to a pop of one stack frame.

Prolog of main()

Here is the main routine's pseudocode and prolog. Notice that there are two variables.

Question 19

Fill in the blanks.

Answer

#  main()
#  {
#    int a, b;                      // a: 0($fp),  b: 4($fp)
#    write("enter an int:")
#    read( a );
#    b = fact( a );
#    write("factorial is:")
#    print( b );
#  }
         .text
         .globl  main
main:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
                                  #   3. No S registers to push
         sub     $fp,$sp,8        #   4. $fp = $sp - space_for_variables
         move    $sp,$fp          #   5. $sp = $fp

Guts of main()

The next part of main() is straightforward. The SPIM services four and five for writing a string and reading an integer are used. The integer is returned in $v0. It is saved in the variable a (on the stack).

                                  # write("enter an int:")
         li     $v0,4             #   print string service
         la     $a0,prompt1       #   address of prompt
         syscall
                                  # read( a )
         li     $v0,5             #   read integer service
         syscall                  #   $v0 gets the integer
         sw     $v0,0($fp)        #   save in variable a

Next the code implements b = fact( a ). This is done by following the protocol for a subroutine call, then storing the returned value into the variable b:

Question 20

Fill in the blanks.

Answer

                       
                                  # subroutine call: b = fact( a )
                                  #   1. No T registers to push
         lw      $a0,0($fp)       #   2. Put argument into $a0
         jal     fact             #   3. Jump and link to subroutine
         
                                  # return from subroutine 
                                  #   1. No T registers to restore
                                  
         sw     $v0,4($fp)        # b = fact( a )

More main()

Next main() does some utterly routine things:

                                  # print( b )
         lw     $a0,4($fp)        # load b into $a0
         li     $v0,1             # print integer service
         syscall                                  
                                  # end the print line
         li     $v0,4             #   print string service
         la     $a0,lf            #   address of line feed
         syscall

Finally, main() ends with a subroutine epilog.

                                  # epilog
                                  #   1. No return value         
         add     $sp,$fp,8        #   2. $sp = $fp + space_for_variables       
                                  #   3. No S registers to pop      
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #                                    
         jr      $ra              # return to OS 

The data for the prompts is not stored on the stack.

         .data
prompt1: .asciiz "enter an int:"
prompt2: .asciiz "factorial is:"
lf:      .asciiz "\n"

Question 21

How do the variables a and b differ from the data prompt1 and prompt2?

Answer

a and b: (1) Storage for them exists only while the subroutine is active (while it has not yet returned control to its caller). (2) When it exists, the storage is on the run-time stack.

prompt1 and prompt2: (1) Storage for them exists while the program is in main storage. (2) Storage is in the data section of memory.

Storage classes

There are three places in memory where data may be placed: in the data section (declared with .data in assembly language), on the run-time stack, and on the heap.

A subroutine other than main() can have data in the .data section. In high-level programming languages, such as "C", this type of storage is called static.

Variables whose storage is allocated on the run-time stack are (sometimes) called automatic variables. This is because their storage is "automatically" pushed and popped as a subroutine is entered and exited. Usually the word "variable" means "automatic variable".

A variable whose memory is located in the heap is called a dynamic variable. Chapter 33 of these notes discusses the heap. The heap is where memory for objects is found (using the new operation in Java or C++). In "C" dynamic memory is allocated using the malloc operation (or similar).

The heap is on top of the data segment. As dynamic variables are created it grows upward (towards the stack)

Question 22

(Review:) What happens if the stack and heap get larger and larger?

Answer

If the combined size of the stack, the data, and the heap is less than the total available memory, then there is no problem.

Complete main()

Back to the example program (you were probably hoping that I'd forget). Here is the complete main(). There is nothing new in it; its listed here so you can see all the parts in place.

#  main()
#  {
#    int a, b;    // a: 0($fp),  b: 4($fp)
#    write("enter an int:")
#    read( a );
#    b = fact( a );
#    write("factorial is:")
#    print( b );
#  }
         .text
         .globl  main
main:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
                                  #   3. No S registers to push
         sub     $fp,$sp,8        #   4. $fp = $sp - space_for_variables
         move    $sp,$fp          #   5. $sp = $fp

                                  # write("enter an int:")
         li     $v0,4             #   print string service
         la     $a0,prompt1       #   address of prompt
         syscall
                                  # read( a )
         li     $v0,5             #   read integer service
         syscall                  #   $v0 gets the integer
         sw     $v0,0($fp)        #   save in variable a
                        
                                  # subroutine call
                                  #   1. No T registers to push
         lw      $a0,0($fp)       #   2. Put argument into $a0
         jal     fact             #   3. Jump and link to subroutine
         
                                  # return from subroutine 
                                  #   1. No T registers to restore
                                  
         sw     $v0,4($fp)        # b = fact( a )
        
                                  # write("factorial is:")
         li     $v0,4             #   print string service
         la     $a0,prompt2       #   address of prompt
         syscall
                                  # print( b )
         lw     $a0,4($fp)        # load a into $a0
         li     $v0,1             # print integer service
         syscall                                  

                                  # end the print line
         li     $v0,4             #   print string service
         la     $a0,lf            #   address of line feed
         syscall
                                  # epilog
                                  #   1. No return value         
         add     $sp,$fp,8        #   2. $sp = $fp + space_for_variables       
                                  #   3. No S registers to pop      
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #                                    
         jr      $ra              # return to OS 

         .data
prompt1: .asciiz "enter an int:"
prompt2: .asciiz "factorial is:"
lf:      .asciiz "\n"

Question 23

What subroutine does main() call?

Answer

fact

Entry point

On to the subroutine. The first address in this subroutine is called fact. Of course, fact will correspond to a main storage address at run-time. That address is determined by the assembler, the linker, and the loader.

#  int fact( int n )
#  {
#    if ( n<=1)
#      return 1;
#    else
#      return n*fact(n-1);
#  }
         .text
         .globl  fact
fact:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
         sub     $sp,$sp,4        #   3. Push register $s1
         sw      $s1,($sp)
         sub     $fp,$sp,0        #   4. $fp = $sp - space_for_variables (==0)
         move    $sp,$fp          #   5. $sp = $fp
         
                                  # body of subroutine
        . . . . . .
                            
epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         add     $sp,$fp,0        #   2. $sp = $fp + space_for_variables (==0)
         lw      $s1,($sp)        #   3. Pop register $s1
         add     $sp,$sp,4        #          
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #            
         jr      $ra              #   6. return to caller 

The symbol fact is a global symbol (also called an external symbol) so that the assembler, linker, and loader can use that symbol to refer to the same place in memory.

A location such as fact that is a target of a subroutine call is called an entry point. Sometimes a subroutine has several entry points, one for each of several related functions.

Question 24

(Thought Question:) Does a global symbol always correspond to an entry point?

Answer

No. Sometimes a global symbol is used to label data that several modules may refer to.

Body of fact()

Here is part of the body of the subroutine:

The argument in $a0 is saved in register $s1 because later on $a0 may be altered. (Since this subroutine uses $s1 the contents of $s1 is saved on the stack in the prolog).

The if statement checks if the argument (in $a0) is 1 or less. If so, it loads register $v0 with the value to return to the caller, one. Otherwise, the other branch is taken.

Question 25

Fill in the blank.

Answer

See below.

More fact()

The alternate branch of the if statement (at symbolic address recurse) has the job of calculating n*fact(n-1). It does this by first calculating the argument n-1.

Then it calls the subroutine fact() in the normal way. It does not hurt for fact() to call fact() because each activation has its own data on the stack.

On return from the (inner) call to fact(), register $v0 has the returned value, and register $s1 has the argument n. Now the return value from the current activation must be placed in $v0 to be returned to the caller.

Question 26

Fill in the blanks. (Hint: study the last paragraph).

Answer

See below.

Recursive call

         . . . . . .

recurse:                          # else
                                  #   return n*fact(n-1);
         sub     $a0,$s1,1        #     argument0 = n-1
                       
                                  # subroutine call
                                  #   1. No T registers to push
                                  #   2. Argument is in $a0 
         jal     fact             #   3. Jump and link to subroutine

         mul     $v0,$v0,$s1      # n*fact(n-1)

epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         . . . . . .
         jr      $ra              #

Recursion has been implemented by using: (1) the normal machine operations of sequential execution, testing, and branching, and (2) the run-time stack.

This is (yet another) example of a new level of abstraction being build upon a foundation level. Have I mentioned that this is one of the most stunningly important ideas of Computer Science?

Question 27

The programming language FORTRAN IV did not have support for recursion. Was it possible to write a recursive program in FORTRAN IV?

Answer

Yes. FORTRAN had sequential execution, testing, and branching, as do all languages. To write a recursive program the programmer had to create and manage a run time stack, just as in assembly language. Modern high level languages do this automatically.

Complete fact()

Here is the complete code for fact():

#  int fact( int n )
#  {
#    if ( n<=1)
#      return 1;
#    else
#      return n*fact(n-1);
#  }
         .text
         .globl  fact
fact:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
         sub     $sp,$sp,4        #   3. Push register $s1
         sw      $s1,($sp)
         sub     $fp,$sp,0        #   4. $fp = $sp - space_for_variables (==0)
         move    $sp,$fp          #   5. $sp = $fp
         
                                  # body of subroutine
         move    $s1,$a0          # save argument in $s1
         li      $t1,1            # get a 1
         bgt     $s1,$t1,recurse  # if ( n<=1)
         li      $v0,1            #   return 1
         b       epilog    

recurse:                          # else
                                  #  return n*fact(n-1)
         sub     $a0,$s1,1        #     n-1
                       
                                  # subroutine call
                                  #   1. No T registers to push
                                  #   2. Argument is in $a0 
         jal     fact             #   3. Jump and link to subroutine

         mul     $v0,$v0,$s1      # n*fact(n-1)
                            
epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         add     $sp,$fp,0        #   2. $sp = $fp + space_for_variables (==0)
         lw      $s1,($sp)        #   3. Pop register $s1
         add     $sp,$sp,4        #          
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #            
         jr      $ra              #   6. return to caller 

Question 28

Is a different subroutine linkage convention followed for recursive subroutines than for non-recursive subroutines?

Answer

No. The same convention is followed by both. There is nothing special about a recursive subroutine except that it calls itself.

Chapter quiz

Instructions: For each question, choose the single best answer. Make your choice by clicking on its button. You can change your answers at any time. When the quiz is graded, the correct answers will appear in the box after each question.

Question 1

In a high-level language, how is a local variable implemented?

• (A) As a section of global memory.
• (B) On the run-time heap.
• (C) As a slot in an array.
• (D) As a location on a subroutine's stack-frame.

Answer

D

Question 2

What registers are the caller-saved registers?

• (A) The T registers.
• (B) The V registers.
• (C) The S registers.
• (D) The A registers.

Answer

A

Question 3

In this calling convention, how many bytes are in each item on the stack?

• (A) 1
• (B) 2
• (C) 4
• (D) 8

Answer

C

Question 4

What is the role of $fp with a stack frame?

• (A) $fp is used when values are popped and pushed during arithmetic evaluation.
• (B) $fp points at the section of the stack that does not change as a subroutine executes.
• (C) $fp is used to access values that the caller saved on the stack.
• (D) $fp points at global values all subroutines may access.

Answer

B

Question 5

Does the number of registers that MIPS has limit the number of variables that a subroutine may have?

• (A) No, because each register may be used for any number of variables.
• (B) No, because variables are implemented as locations on the stack.
• (C) Yes, there may be only 32 variables in a program, minus the number of registers used for special purposes.
• (D) Yes, there may be only 8 variables in a program.

Answer

B

Question 6

In the programming language C, what is the name for variables implemented as sections of the run-time stack?

• (A) automatic
• (B) dynamic
• (C) stack
• (D) heap

Answer

A

Question 7

What is it called when a subroutine may call itself?

• (A) automatic
• (B) dynamic
• (C) static
• (D) recursive

Answer

D

Question 8

When is space made on the stack for the local variables of a subroutine?

• (A) In the subroutine call of the caller.
• (B) In the subroutine's prolog.
• (C) In the subroutine's main body.
• (D) In the subroutine's epilog.

Answer

B

Question 9

Say that a subroutine has just one variable. How is that variable copied into $t0 in the subroutine's body?

• (A) lw $t0,0($fp)
• (B) lw $t0,0($sp)
• (C) lw $t0,4($fp)
• (D) lw $t0,-4($fp)

Answer

A

Question 10

Say that a subroutine has 3 local variables. How does it allocate space on the stack for these variables?

• (A) addu $fp,$sp,12
• (B) addu $fp,$sp,3
• (C) subu $fp,$sp,12
• (D) addu $sp,$fp,12

Answer

C

Programming exercises

NOTE: Use the Frame-based Linkage Convention for these programs.

In the Settings menu of SPIM set Bare Machine OFF, Allow Pseudo Instructions ON, Load Trap File ON, Delayed Branches OFF, Delayed Loads OFF, Mapped IO ON, Quiet OFF.

Exercise 1 (**) - play compiler

Translate the following little program into MIPS assembly language. Do a line-by-line translation as a simple compiler might do (as done in the chapter). Use stack-based variables for the program's local variables. Assemble and run your program under SPIM

main()
{
  int f;
  int c;
  
  f = 50;
  c = toCent( f );
  
  print( "f=", f, "c=", c );
}

int toCent( int x )
{
  int v;
  v =  x - 32;
  v =  5*v
  v =  v/9;
  return v;
}

You could, of course, write the program without using variables since there are plenty of "T" registers available. But practice using local variables as in the chapter. For each assignment statement, for each variable on the right of the equal sign retrieve a value from a variable on the stack. For the variable on the left of an assignment statement, store a value into the variable, even if the very next statement requires that the value be retrieved.

Exercise 2 (***) - triangle numbers

Write a program that computes the value of triangle numbers using a recursive subroutine. The definition of triangle numbers is:

Triangle( 1 ) = 1

Triangle( N ) = N + Triangle( N-1 )

For examples:

Triangle( 1 ) = 1

Triangle( 2 ) = 3

Triangle( 3 ) = 6

Triangle( 4 ) = 10