Class 22: Stack frames

Held Monday, October 26, 1998

Notes

• I've begun looking over the exams, but prefer to wait until everyone turns in their exams until I do the full grading. I've written up a set of notes on grading, but those won't be available until everyone turns in their exams. Everything should be back to you at the end of class on
• A reminder: Dr. Borenstein will be visiting for the next two weeks. Events you should remember:
  • Tuesday, 4:15, lecture on "Kiss Privacy Goodbye"
  • Wednesday, 1:15, teaches CSC362 (on the future of compilers)
  • Wednesday, 3:15, teaches CS301 (on MIME!)
  • Wednesday, 4:15, discussion on Internet and society course
  • Thursday, 11:00, convocation
  • Thursday, 4:15, discussion on HCI course
  • Friday, 8:00am, CS213 (on the Andrew Operating System)
• There's also a cool student math talk Thursday at 4:15. (Isn't it great that we have so many cool things to do in this department?) It looks like this one will even be understandable to CS students.
• It looks like I will be able to be in class on Friday, November 13. (Just noting a change in the outline).
• It appears that I've fixed the search engine. If it doesn't seem to work appropriately, please let me know ASAP.
• Today we turn our attention to back-end issues, rather than the front-end issues we discussed the first half of the seminar.

Storing variables

• A first consideration is how to handle the storage of variables and parameters in memory.
• As you know, in most modern languages it is possible to call procedures recursively and create new instantiations of the local variables.
• In addition, when a function exits you no longer need access to its local variables.
• However, in languages that support the dynamic allocation of memory (e.g., most object-oriented languages), there are also some values that live beyond the function that created them.
• Typically, values that are only active during the lifetime of a procedure are allocated on a stack and values that are independent of procedure lifetime are allocated on a heap.
• In modern architectures, some variables should be stored in registers to improve performance.

The stack

• At the machine level, the stack is simply an area of memory that is allocated and deallocated in a stack-like manner.
• Typically, the stack starts at the high end of memory and the heap starts at the low end of memory.
  • This design makes it possible to delay the decision of how much memory to use for heap and how much for stack until run time (i.e., you can grow either heap or stack until the two cross).
  • This design suggests that stacks grown downward and shrink upwards, like bungie cords.
• A designated register called the stack pointer keeps track of the end of the stack.

Stack frames

• Since a function will often require space for many variables (parameters, local variables, temporaries, etc.) it is more convenient to allocate all of that space at once.
  • This means that we should predetermine the maximum amount of space a function will use.
  • As long as we've determined that space, we might as well lay out the data in that space.
• The organization of local data for the invocation of a function is typically called a stack frame.
  • Appel provides a typical stack frame in Figure 6.2
• A frame pointer indicates the beginning of the frame.
• What goes in a frame (or in accompanying registers)?
  • Any local variables
  • Parameters (subject to the caveats below)
  • The return address (what statement to branch to when the method exits)
  • Any temporaries
  • Saved registers
  • Space for the return value
  • Other things

Accessing nonlocal variables

• In nested languages, like Tiger, 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 current 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.

Function calls

• How do we call a function?
  • We'll assume we are using static links
• The caller places some of the formal parameters on the stack (often, in its own stack frame).
• The caller places some of the formal parameters in registers.
  • If those registers are currently in use, the caller must store their current
• The caller places a return address and static link on the stack (often, in the next stack frame).
• The caller branches to the beginning of the called function.
• The called function allocates a new stack frame, updating the stack pointer.
• The called function executes.
• The called function stores its result in a register (or on the stack, in a more primitive implementation).
• The called function deallocates its stack frame.
• The called function branches back to the return address.
• The caller makes use of the result value.
• The caller restores any registers necessary.

History

• Created Sundary, October 25, 1998, primarily from extra notes taken in the previous outline (continuing a long-standing trend).