7.2 Case Study: Activation Records for the MIPS Architecture

The following describes a function call abstraction for the MIPS architecture. This may be slightly different from the one you will use for the project.

MIPS uses the register $sp as the stack pointer and the register $fp as the frame pointer. In the following MIPS code we use both a dynamic link and a static link embedded in the activation records.

Consider the previous program:

procedure P ( c: integer )
  x: integer;

  procedure Q ( a, b: integer )
  i, j: integer;
  begin
    x := x+a+j;
  end;

begin
  Q(x,c);
end;

The activation record for P (as P sees it) is shown in the first figure below:

The activation record for Q (as Q sees it) is shown in the second figure above. The third figure shows the structure of the run-time stack at the point where x := x+a+j is executed. This statement uses x, which is defined in P. We can't assume that Q called P, so we should not use the dynamic link to retrieve x; instead, we need to use the static link, which points to the most recent activation record of P. Thus, the value of variable x is computed by:

        lw        $t0, -8($fp)                # follow the static link of Q
        lw        $t1, -12($t0)               # x has offset=-12 inside P

Function/procedure arguments are pushed in the stack before the function call. If this is a function, then an empty placeholder (4 bytes) should be pushed in the stack before the function call; this will hold the result of the function.

Each procedure/function should begin with the following code (prologue):

        sw      $fp, ($sp)      # push old frame pointer (dynamic link)
        move    $fp, $sp        # frame pointer now points to the top of stack
        subu    $sp, $sp, 500   # allocate say 500 bytes in the stack (for frame size = 500)
        sw      $ra, -4($fp)    # save return address in frame
        sw      $v0, -8($fp)    # save static link in frame

and should end with (epilogue):

        lw      $ra, -4($fp)    # restore return address
        move    $sp, $fp        # pop frame
        lw      $fp, ($fp)      # restore old frame pointer (follow dynamic link)
        jr      $ra             # return

For each procedure call, you need to push the arguments into the stack and set $v0 to be the right static link (very often it is equal to the static link of the current procedure; otherwise, you need to follow the static link a number of times). For example, the call Q(x,c) in P is translated into:

        lw      $t0, -12($fp)
        sw      $t0, ($sp)        # push x
        subu    $sp, $sp, 4
        lw      $t0, 4($fp)
        sw      $t0, ($sp)        # push c
        subu    $sp, $sp, 4
        move    $v0, $fp          # load static link in $v0
        jal     Q                 # call procedure Q
        addu    $sp, $sp, 8       # pop stack

Note that there are two different cases for setting the static link before a procedure call. When the callee is lexically inside the caller's body, we have:

        move    $v0, $fp

otherwise, we follow the static link of the caller d times, where d is the difference between the lexical level of the caller from that of the callee. For d=1 we have

        lw        $v0, -8($fp)

For d=3 we have

        lw        $t1, -8($fp)
        lw        $t1, -8($t1)
        lw        $v0, -8($t1)

Note also that, if you have a call to a function, you need to allocate 4 more bytes in the stack to hold the result.

See the factorial example for a concrete example of a function expressed in MIPS code.