CSE logo University of Washington Department of Computer Science & Engineering
 CSE 378, Winter 2007
 Machine Organization and Assembly Language Programming
  CSE Home  About Us    Search    Contact Info 

Mechanics
 Home
 Overview
 Academic (Mis)Conduct
 Course wiki
 Mailing list
Schedule
 Lectures and readings
 Lab hours
Assignments
 Homeworks
 Your Grades
Documentation
 Cebollita
 Miscellaneous
Anonymous Feedback
 Submit Feedback
 Read Feedback
   
Printable view

Procedure Call Conventions

Lecture Key Points

    Critical points:
    • the stack
    • the convention for the use of registers $sp, $fp, $ra
    • the steps required in procedure linkage
    • "stack frame"
    • Cebollita linkage
    • caller-saved vs. callee-saved registers
    • the heap
    Other points of interest:
    • MIPS linkage
    • the use of registers $v0, $v1, and $a0-$a3
    • the use of registers $s0-$s7 and $t0-$t9
    • how do you pass an array? a structure? a function?
    • "call by value" vs. "call by reference"
    • stack frame traceback: debugging and exception handling
    • stack overflow security vulnerability
    • Hey, main() is just a subroutine! But, who calls it?

The Problem

    Imagine these two routines are presented to the compiler.
    CallerCallee
        main() {
           int result;
           result = max( 10, 2 );
           printInt( result  );
        }
        
        int max(int a, int b) {
            int result;
    
    	if ( a < b ) {
    	    result = b;
    	} else {
    	    result = a;
    	}
    	return result;
        }
        
    Of course, this code must be turned into assembly language. Here's a generic view of what happens at the assembler level:
    1. The CPU is happily fetching instructions in the caller, ta-de-dum.
    2. The caller enters a "pre-call" sequence of instructions that sets things up. Among other things, it puts the arguments of the call somewhere the callee will be able to find them.
    3. The caller executes a jal max instruction to simultaneously (a) put the current PC in register $ra, and (b) jump to the memory location corresponding to symbol max.
    4. Now the subroutine (max) is executing. The first thing it does is execute some "subroutine entry" code. Among other things, it makes space on the stack for its own local variables (in this case, result).
    5. max executes - ta-de-dum
    6. max is done. It executes some "subroutine exit" code - among other things, it places the return value somewhere the caller can find it, and frees the stack space it allocated for its own use.
    7. The callee returns to the caller with the instruction jr $ra.
    8. Now we're back to the caller, at the instruction following the jal. The caller executes a "post-call" sequence of instructions.

    Exactly how things are done at each step is decided by convention, an agreement among all software components on how they use the hardware resources. (The hardware doesn't care - it just fetch-increment-execute's.)  There are multiple such conventions in the course materials, unfortunately - the book has two or three, and Cebollita uses a different one.

    To help fill in what all the decisions are a convention must make, let's examine the Cebollita one in more detail.

Cebollita Procedure Linkage

    Caller: Prepare for Call
    • Some registers may contain values that you want to use after making the call.  When you invoke the subroutine, it may use those registers and those values will be gone.  For the registers/values you want to preserve, allocate space on the stack using
          addiu $sp, $sp, -<4 * #regs saved>
      Copy the registers/values to be saved there.
    • If the subroutine takes arguments, allocate space on the stack for them, and then copy the values to be passed into that memory.
    • jal <subroutine-entry-point>

    Callee: Procedure Entry

    • I'm required to save the return address register, $ra, and the frame pointer register, $fp.  I also need to allocate space for all my local variables.  Allocate space on the stack for all of these, and copy $ra/$fp them there. 
    • Set $fp to the current value of $sp, i.e., remember where the stack pointer is right now. 
    • If this routine needs to access either a local variable or a passed argument, it is addressed by its known offset from $fp.

    Callee: Procedure Exit

    • Load any result to be returned in register $v0 (and $v1, if needed).
    • Load registers $ra and $fp with the values previously saved on the stack.
    • addiu to $sp to free the space allocated on entry.
    • jr $ra

    Caller: Call Cleanup

    • Free up the stack space you allocated to pass arguments.
    • Restore any registers saved before the call, and free the stack space allocated for them.
    • Start using the return value (in $v0)...

Cebollita Linkage in Pictures

    Start condition:

    Caller saves registers:

    Caller pushes arguments:

    Callee saves $ra/$fp and allocates space for local vars:

    At this point, $sp may move, but $fp is fixed (so long as the callee is executing). Its local variables and arguments are both accessible at known, constant offsets from $fp.

    When the callee returns, the stack is adjusted in the opposite order, passing through the stages shown above from bottom to top. The result is that it the caller ends up with memory looking like it was when the call was made, and all registers that are important to it having the values they did just before the call (except $v0 (and possibly $v1), which hold the function return value).

Cebollita Linkage in Code

(Other) Procedure Linkage Options: MIPS

    Reading and writing memory is slow - you'd like to operate out of registers as much as you can. For that reason, "the MIPS subroutine linkage convention" (described in a couple of variants in the book) differs from the Cebollita one.  First, rather that passing all arguments using space allocated on the stack, MIPS always puts the up-to-first-four arguments in registers (named $a0 through $a3). The callee knows to look for them there. If there are more than four arguments, the callee pushes the extras onto the stack.

    Second, the MIPS convention distinguishes caller-saved from callee-saved resgisters. (In Cebollita, all registers are caller-saved.) Registers $s0-$s7 are callee-saved: if the callee uses them, it has the responsiblity to save the original values no the stack at entry and to restore them on exit. (If it can avoid using them, it avoids having to save them, which is the point.) Registers $t0-$t9 are caller-saved: the callee is free to write into them without preserving their contents, so the caller must save them if it wants to keep the values they hold.

    Additionally, the MIPS linkage differs in where it points $fp, and in the locations within the call frame of local storage and saved registers. (Finally, the two versions of the MIPS convention differ in that one of them doesn't use $fp at all - it makes do with just $sp.)


Creative Commons License
This work is licensed under a Creative Commons Attribution-Share Alike 2.5 License.
Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to zahorjan]