next up previous contents
Next: 8 Intermediate Code Up: 7 Activation Records Previous: 7.1 Run-Time Storage Organization   Contents

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:

mips_call.gif

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
(where $v0 is set by the caller - see below) and should end with the following code (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. Lets say that caller_level and callee_level are the nesting levels of the caller and the callee procedures (recall that the nesting level of a top-level procedure is 0, while the nesting level of a nested procedure embedded inside another procedure with nesting level l, is l + 1). When the callee is lexically inside the caller's body, that is, when callee_level=caller_level+1, we have:
        move    $v0, $fp
The call Q(x,c) in P is such a case because the nesting levels of P and Q are 0 and 1, respectively. Otherwise, we follow the static link of the caller d + 1 times, where d=caller_level-callee_level (the difference between the nesting level of the caller from that of the callee). For d=0, that is, when both caller and callee are at the same level, we have
        lw        $v0, -8($fp)
For d=2 we have
        lw        $t1, -8($fp)
        lw        $t1, -8($t1)
        lw        $v0, -8($t1)
These cases are shown in the following figure:

static_link.gif

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.


next up previous contents
Next: 8 Intermediate Code Up: 7 Activation Records Previous: 7.1 Run-Time Storage Organization   Contents
fegaras 2012-01-10