# Class 29: Stack Frames (2)

Back to Stack Frames (1). On to A Sample Pascal Parser.

Held: Friday, 9 April 2004

Summary: Today we continue our investigation of stack frames by considering some particular examples.

Related Pages:

Overview:

• Quiz: Dealing with Scope.
• Dealing with Scope, Revisited.
• An Example.

## Dealing with Scopes

• We know how to deal with global variables. They're in fixed areas of memory.
• We know how to deal with variables local to a procedure. They're at some offset from the start of the frame pointer.
• What do we do about other variables?
• There are two perspectives, dynamic and static
• We'll discuss details in class.

## An Example

• Let us continue our discussion of stack frames with a simple example.
• Everyone's favorite recursive procedure is `factorial`, so we'll try that first.
• I've written slightly more explicit code than is normal to help you think about what is happening.
```function factorial(n: integer): integer;
var
tmp: integer;
begin
if (n = 0) then
factorial := 1
else
begin
tmp := factorial(n-1);
factorial := n * tmp;
end
end;
```
• What will the stack frame for this procedure look like? Here's one simple possibility (along with an indication as to where we hope to have the frame pointer and stack pointer, assuming stacks grow downward):
```    |     used     |
+--------------+
FP  |   old FP     |
+--------------+
| return value |
+--------------+
+--------------+
SP  |      n       |
+--------------+
|    unused    |
```
• We'll assume that the local procedure immediately pushes room for a local variable and a temporary, giving us the following stack.
```    |     used     |
+--------------+
FP  |   old FP     |
+--------------+
| return value |
+--------------+
+--------------+
|      n       |
+--------------+
|     tmp      |
+--------------+
SP  |    extra     |
+--------------+
|    unused    |
```
• After a recursive call finishes, we expect to have
```    |     used     |
+--------------+
FP  |   old FP     |
+--------------+
| return value |
+--------------+
+--------------+
|      n       |
+--------------+
|     tmp      |
+--------------+
SP  |    extra     |
+--------------+
|   our FP     |
+--------------+
| rec. result  |
+--------------+
|    unused    |
```
• What does the assembly code for `factorial` look like? In a generic language with four bytes per word
```BEGIN_FACTORIAL:
# Do anything appropriate for the beginning of a procedure call
...
# if (n = 0)
PUSH 8			  # Space for temps
START_FACTORIAL_CODE:
COMPARE MEM[FP+12], CONSTANT[0]
JUMP IF EQUAL TO BASE_CASE
JUMP RECURSIVE_CASE
# factorial := 1
BASE_CASE:
STORE INTO MEM[FP+4] FROM CONSTANT[1]
JUMP END_FACTORIAL
# tmp := factorial(n-1)
RECURSIVE_CASE:
# Compute n-1
SUBTRACT CONSTANT[1] FROM MEM[FP+12], STORE IN MEM[SP]
# Call factorial
...
# Copy the value back
STORE INTO MEM[SP-4] FROM MEM[SP+8]
# factorial := n * tmp
MULTIPLY MEM[FP+12] BY MEM[SP-8], STORE IN MEM[FP+4]
JUMP END_FACTORIAL
# Clean up
END_FACTORIAL:
...
```
• Okay, what do we have to do at the beginning of a procedure? If a procedure knows how much local memory it needs, the procedure should increment the stack pointer
```# Do anything appropriate for the beginning of a procedure call
```
• At the end, the procedure should undo what it just did.
```END_FACTORIAL:
SUBTRACT CONSTANT[8] from SP
```
• It needs to restore the frame pointer
```  SET FP to MEM[FP]
```
• It also needs to return to the place that it started.
```  JMP MEM[FP+8]
```
• Now to the hard part. What do we do for a recursive procedure call?
• Before jumping to the code for the procedure, we need to store the parameter.
```  STORE INTO MEM[?] FROM MEM[?]
```
• We may update the frame pointer, so we store it in the next frame.
```  STORE INTO MEM[?] FROM FP
```
• We also need to update the frame pointer. (We assume that procedures update their own stack pointers.) Conveniently, the end of one frame (given by the stack pointer) is the same as the beginning of the next frame (given by the frame pointer).
```  SET FP to SP
```
• We have to advance the stack pointer beyond the pushed stuff
```  ADD CONSTANT[16] to SP
```
```  STORE INTO MEM[?], RETURN_HERE
```
• We need to call the procedure. Generically,
```  JUMP BEGIN_FACTORIAL
RETURN_HERE:
```
• We need to recover from the procedure. That means that we need to update the stack pointer to where it was before.
```  SUBTRACT CONSTANT[16] from SP
```
• We'll go through an example (and work out the kinks) in class.

Back to Stack Frames (1). On to A Sample Pascal Parser.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 5 11:47:11 2004.
The source to the document was last modified on Tue Jan 20 23:06:46 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.29.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu