# Class 23: More Stack Frames

Back to Stack Frames. On to Pause For Breath.

Held Wednesday, March 14, 2001

Summary

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

Assignments

Due

Notes

• Don't forget: No lab tomorrow, no class Friday. Have a great break!
• Mr. Stone is giving a talk today at 4:15 on preserving electronic documents. Mr. Stone is a fun speaker, and I encourage you to attend.
• Are there questions on homework 2?
• Rachel has finished grading homework 1, but I haven't had a chance to look at all of it.

Overview

## 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
tmp1: 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):
```+--------------+  <- FP
|   old FP     |
+--------------+
| return value |
+--------------+
+--------------+
|      n       |
+--------------+
|     tmp      |
+--------------+
|    extra     |
+--------------+  <- SP
```
• 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)
START_FACTORIAL_CODE:
COMPARE MEM[SP-12], CONSTANT[0]
JUMP IF EQUAL 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[SP-12], STORE IN MEM[SP-8]
# Call factorial
...
# Copy the value back
STORE INTO MEM[SP-8] FROM MEM[SP+4]
# factorial := n * tmp
MULTIPLY MEM[SP-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 only a procedure knows how big its stack frame is, then 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[24] from SP
```
• It also needs to return to the place that it started.
```  JMP MEM[SP+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[SP+12] FROM MEM[SP-4]
```
• We may update the frame pointer, so we store it in the next frame.
```  STORE INTO MEM[SP] 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
```
```  STORE INTO MEM[SP+8], 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 frame pointer to where it was before.
```  STORE INTO FP FROM MEM[FP]
```
• We'll go through an example (and work out the kinks) in class.

## Accessing Non-Local Variables

• In nested languages, like Pascal, it is possible to refer to a variable from a non-local scope. How do you get access to that variable?
• One possibility is to have every frame include a pointer to the frame of the enclosing scope (not necessarily the caller). This means that you have to trace backward an appropriate amount, but that amount can be computed at compile time. Such a pointer is typically called a static link.
• Another possibility is to use a global display which maps each scope to the appropriate stack frame.
• A third possibility is to pass all of the variables to the function and restore them afterwards. This can be particularly difficult to implement.

## History

Monday, 22 January 2001

• Created as a blank outline.

Back to Stack Frames. On to Pause For Breath.

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

This page was generated by Siteweaver on Mon Apr 30 10:52:03 2001.
This page may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2001S/outline.23.html`.