Stack Frame (a.k.a Frame)

I had a lot of trouble understanding this, and how it was related to Chunk.

Maybe Ben Eater helps: What is a stack and how does it work?

Implement a Stack in Machine Language

We start to store the stack towards the end of the memory address.

Some Definitions

• The stack pointer is a register that stores the address of the word at the top of the stack (by convention stored at Register 30) (known at runtime)
• The Frame Pointer is a register that stores the memory location of the frame for the currently executing procedure (known at runtime)
  • IMPORTANT: Variables are accessed at constant offsets from the address in the frame pointer.
• Frame / Stack frame / activation record = The area of the stack reserved for the variable instances of an invocation of a procedure. the area of memory for values of locals of a procedure invocation
• The Symbol Table maps each local variable in the procedure to a constant offset from the frame pointer (fixed at compile time)

For a stack, variables are accessed at constant offsets from the address in the frame pointer.

title: Stack Pointer vs. Frame Pointer
Use the Frame Pointer to access your variables, NOT the Stack Pointer.
 
Why? To free up the stack pointer so that the stack can be used for other purposes within the procedure, such as storing temporary values, that are created within the procedure
- Think about it if you were to only use a Stack Pointer. Then, you push additional variables. Now you need to compensate for the extra offset. I guess that would still work. But everything is now shifted. Imagine that inside this procedure, another procedure is called. The problem of the frame pointer being overwritten is inside [[Procedure]]
 

Example of how this works in practice with stack frames:

• The program starts execution in main().
  • The control stack gets a stack frame for main().
• main() calls funcA().
  • A new stack frame for funcA() is pushed onto the control stack.
• funcA() calls funcB().
  • A new stack frame for funcB() is added to the control stack.

At this point, the control stack has three stack frames: one for main(), one for funcA(), and one for funcB(). Each function’s context is stored in its respective stack frame.

At Higher level

We have these functions

/** Generates a `VarAccess` that reads `variable` into `register`. */
def read(register: Reg, variable: Variable) = VarAccess(register, variable, read = true)  
  
/** Generates a `VarAccess` that writes `register` into `variable`. */
def write(variable: Variable, register: Reg) = VarAccess(register, variable, read = false)  
  
/** Generates an assignment statement that first evaluates `expr` (assuming its result is stored into `Reg.result`),  
  * then writes the result into `variable`.  
  */def assign(variable: Variable, expr: Code) = block(expr, write(variable, Reg.result))

VarExcess is an abstraction. When it comes to compile, we call eliminateVarAccess, which does the following:

def compilerA3(code: Code, variables: Seq[Variable]): MachineCode = {  
  val frame = Chunk(variables)  
  val code1 = eliminateVarAccessesA3(code, frame)  
  val code2 = allocateFrameOnStack(code1, frame)  
  toMachineCode(block(code2, JR(Reg.link)))  
}
.
.
.
 
def eliminateVarAccessesA3(code: Code, frame: Chunk): Code = {  
  def fun: PartialFunction[Code, Code] = {  
    case va: VarAccess =>  
      {  
        if (va.read) {  
          frame.load(Reg.framePointer, va.register, va.variable)  
        } else { // Write  
          frame.store(Reg.framePointer, va.variable, va.register)  
        }  
      }  
  }  
  transformCode(code, fun)  
}
  
/** Given a `body` of `Code` and a `frame` of variables that it uses, generates  
  * code that allocates space for the `frame` on the stack and sets `Reg.framePointer` to  
  * point to it, followed by the `body`, followed by code to free the space for the `frame` from the stack.  
  */def allocateFrameOnStack(body: Code, frame: Chunk): Code = {  
  block(Stack.allocate(frame), ADD(Reg.framePointer, Reg(0), Reg.stackPointer), body, Stack.pop)  
}

Loading and Storing Variables (with Stack Frames and Chunk)

As iterated above, we load and store variables using the frame pointer, not the Stack Pointer.

In CS241E , we never push or pop an individual word on the stack at a time. Instead, we organize all memory in Chunks, collections of some known number of words stored at consecutive memory locations. Each Chunk represents a Stack Frame that contains the variables.

We push enough space onto the stack to store a Chunk (which is a stack frame.). Then, to access the variables, we use the symbol table, and load the value with an offset from the base register (Reg.framePointer) and store that to a target register.

def load(baseRegister: Reg, register: Reg, variable: Variable): Code = {  
  LW(register, variableToOffset(variable), baseRegister)
}  
  
def store(baseRegister: Reg, variable: Variable, register: Reg): Code = {  
  SW(register, variableToOffset(variable), baseRegister)
}

In general, we have something like this:

LW(Reg(1), 8, Reg.framePointer) 
SW(Reg(1), 8, Reg.framePointer)

Push and Pop Stack Operations

The code below is not used in practice, just as a reference to give you a basic idea.

Pushing to the Stack

1. Subtract 4 from the stack pointer
2. store $w$ at the memory address in the new stack pointer

LIS(Reg.result) 
Word(encodeSigned(4)) 
SUB(Reg.stackPointer, Reg.stackPointer, Reg.result) 
SW(Reg (1) , 0, Reg.stackPointer)

Popping from the Stack

1. Load the word from the memory address given by the stack pointer
2. Add 4 to the stack pointer (this is the address of the next word on the stack)

LW(Reg(1), 0, Reg.stackPointer) 
LIS(Reg.result) 
Word(encodeSigned(4)) 
ADD(Reg.stackPointer, Reg.stackPointer, Reg.result)