CS 451 - 651 Lecture 25 - Dec 1


Overview

1.  Automatic storage:  activation records and function-call/return linkage

2.  General discussion of optimizations:  Scalar (mainly), and Vector
  (incl: different ways of looking at them, various advantages and problems)


Automatic storage:  activation records and function-call/return linkage

Local variables live on the stack, in the function's "activation record", also known as a "stack frame".
  (general reference:  C&T chapter 6

Two registers typically control the stack:
  rFP  (Frame Pointer): base of current frame
  rSP  (Stack Pointer): top of stack -- first free location

Typically, rFP+0 addresses the first word in the current frame.  (Note, though, there is often linkage data there;  the first user variable will be a little further along, perhaps at rFP+8)

rSP can either point to the last used word on the stack, or the first free one (i.e., 4 bytes further along).  We'll point at the first free slot.  (hw note...)

When a function call happens, a new frame will be added to the stack (to form the new activation record), and rFP and rSP will be adjusted accordingly.  Since we'll want to restore the previous situation when the function returns, the old information will need to be saved.  The stack provides a natural place!   This work is typically done by the function, in a "prologue" executed before anything else, and an epilogue at the end.  (hw note...)  Usually, the function's return address is also saved and restored as part of this sequence.

Rough picture:   ... f() has called g()
  rSP --> 
         +---------------+
         |               |
         |               |
         | local         |
         |   variables   |   current function's activation record
         |               |
         | (function g)  |
         |               |
  rFP--> |               |
         +---------------+
         |               |
         |               |
         | local         |
         |   variables   |   PREVIOUS function's activation record
         | (function f)  |
         |               |
         +---------------+

another call occurs, to h():
 

  rSP --> 
         +---------------+
         |               |
         |               |
         | local         |
         |   variables   |   current function's activation record
         |               |
         | (function h)  |
         |               |
  rFP--> |               | <-- previous rSP
         +---------------+
         |               |
         |               |
         | local         |
         |   variables   |   PREVIOUS function's activation record
         | (function g)  |
         |               | <- previous rFP 
         +---------------+
         |               |
         |               |
         | local         |
         |   variables   |   PREVIOUS function's activation record
         | (function f)  |
         |               |
         +---------------+


When we remove the current record, we'll want to restore
  previous rFP  -- better be saved somewhere
  previous rSP -- same as current rFP, can restore from there
and for the control linkage,
  previous rRA (return address) -- better be saved

Zooming in:
  rSP --> 
         +----------------+
         |                |
         |                |
         | local          |
         |   variables    |   current function's activation record
         |                |
         | (function h)   |
         |                |
         |                |
         |                |
         |<previous rRA>  |
  rFP--> |<previous rFP>  | 
         +----------------+

The prolog code looks something like:
         [SP] = FP
         FP = SP
         [FP+4] = rRA
         SP = SP + size  (curOffset)

Here it is from an actual program:

 [5] Inst: STOREAI rFP => rSP, 0
 [6] Inst: I2I rSP => rFP
 [7] Inst: STOREAI rRA => rFP, 4
 [8] Inst: ADDI rSP, 16 => rSP

The frame size is the total required for local variables... which in our implementation turns out to be the same as the counter that's determining where the declaration process will assign new variables.


The epilog just reverses that sequence:

        rRA = [FP + 4]
        SP = FP
        FP = [FP]
        RETURN

From an actual program:
 [31] Inst: LOADAI rFP, 4 => rRA
 [32] Inst: I2I rFP => rSP
 [33] Inst: LOADAI rFP, 0 => rFP
 [34] Inst: RETURN rRA



There are some interesting cases -- see C&T.  In particular, if the language allows you to declare one function inside of another, then there are problems when the inside function tries to access local data from the outside one.   (Hint: the problem is occurs if the inner function is recursive)  This is called the "up-level referencing problem."

There are several possible solutions:
  1. forbid inner functions (what C does)
  2. allow inner functions but no "up-level" referencing.  (hist: B5000 Algol)
  3. restrict things in some other clever way
  4. maintain a "display" to allow this kind of addressing
  5. pass in hidden arguments to inner functions to provide the necessary info