Today in CS362: Stack Frames and More Admin No office hours today - Sam's mom arrives How's the project going? Warning! Type checker next. Overview Where we've been, where we're going Where do variables go? Stack Heap Stack Frames Non-Local Variables (maybe) Two big stages: Front end and back end We're ready to start moving on to the back end and think about generating code. Background knowledge: How are we organizing memory? What does our target language look like? Translation For each structure in a program, what do we do? Implement program sample(input,output); var i: integer; ip: pointer to integer; function factorial(n: integer); begin factorial := factorial(n-1)*n; end; begin writeln(factorial(i)); ip = new integer; end. Three kinds of variables: * Global variables, that aren't replicated * Parameters and local variables to procedure calls, which may be replicated in recursive calls * Variables allocated dynamically, such as ip How do we deal with these different kinds of variables? +-----+ |GLOBALS +-----+ |HEAP | +--v--+ | | +-----+ | | +--^--+ |STACK| +-----+ The heap is used for dynamically allocated and freed stuff. factorial(5) 5 * factorial(4) 5 * 4 * factorial(3) 5 * 4 * 3 * factorial(2) 5 * 4 * 3 * 2 * factorial(1) 5 * 4 * 3 * 2 * 1 5 * 4 * 3 * 2 5 * 24 120 We use a stack to keep track of local variables and parameters during procedure calls. What kinds of things will need to go on the stack during a recursive function call? (Assuming that we don't use registers for much.) All the parameters to the procedure Any local variables the procedure uses (Potentially, the return value) "Saved" registers Temporary values 3 * sqrt(i) - sqrt(j) * 10; For a call, the caller needs to: Push any registers the callee may destroy on the stack (Callee could instead push the registers it will destroy) Push all the parameters on the stack Push the return address on the stack (Alternative: Use a register) Jumps to the beginning of the callee For the start of a call, the callee needs to Push any local variables Execute, pushing temporary variables as necessary Shove result in "RETURN REGISTER" Pop anything its pushed Return to the caller The caller now needs to Pop off the parameters (unless we've had the callee do it) Do something appropriate with the return value Restore registers For each procedure, there is a natural set of stuff to have on the stack when the procedure begins. That set of stuff is called a "stack frame". Most architectures now provide two useful pointers to help with these operations. The stack pointer, SP, keeps track of the top of the stack The frame, FP, keeps track of the top of the frame A clever person (e.g., Daren) can easily restore the stack if the old frame pointer is on the stack. E.g., SP = (value stored at the top of the stack) In Pascal, you can nest procedures procedure alpha; var x, y: integer; procedure beta; var i,j : integer; begin i := x; end; Where can we find the variables from the enclosing scope on the stack? * One possibility: Somewhere in the previous frame (wrong) * A better possibility: Keep track of the frame of the enclosing procedure + On the stack * Reserve a small area of memory (size identifiable at compile time) for "stack of frame pointers to enclosing environments"