• 博客访问： 2094721
• 博文数量： 505
• 博客积分： 1552
• 博客等级： 上尉
• 技术积分： 2514
• 用 户 组： 普通用户
• 注册时间： 2007-09-23 18:24

2019年（12）

2018年（15）

2017年（1）

2016年（17）

2015年（14）

2014年（93）

2013年（233）

2012年（108）

2011年（1）

2009年（11）

2013-04-18 09:44:14

## 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
```
(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
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
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: 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.