Subroutine call stack / Execution stack P.J. Drongowski 2 October 2004 (revised 9 October 2004) Call / execution stack * This is a simplified, stack-based model that is similar to execution stacks for different compilers / runtime environments * Compiler writers and architects must customize this approach to the target platform (instruction set and compiler) * Stack naturally accommodate nesting of procedure calls and recursion * Complications: Jump out of nesting (exceptions, setjmp/longjmp) Function (subroutine, procedure) call convention * There are two sides to every story: The function call and the function to be called * There must be agreement between the function call and the function -- how do the caller and the callee communicate? * Function call convention should be standardized * Until call conventions were standardized, communications between subroutines (modules) was non-uniform, buggy * The compiler imposes a de facto standard * Chaos reigns when rules are violated (WINDOWS is a cesspool) What are the parts of a function call? + Arguments to be passed - Arguments are pushed onto the stack before the call - Call by value * The actual argument value is copied to the stack * Can be expensive if the argument is physically big (e.g., an object) * The function can do what it wants to the value on the stack without affecting other parts of memory; effects are contained or localized - Call by reference * A reference to the argument is pushed on the stack * The reference is usually represented as a memory address (where the argument is located in primary memory) * Eliminates the expense of copying large data structures (e.g., objects) to the stack * Since the reference is an address, the function can modify the value of the argument in memory; This is called a side-effect * Unintended side-effects can wreak havoc + The call to the function itself - Usually implemented with a subroutine call instruction - Must remember where to restart execution in the caller - The restart address is called the "return address" - The return address can be saved on the stack + Value to be returned - If the value is a primitive datatype, it's usually returned in a machine register What is the sequence of events in making a function call? + Push arguments onto the stack + Call the function + Pop arguments from the stack to discard them + Use the return value, if one is returned What are parts of a function? + Prelude (preamble) - Saves machine registers on the stack - Allocates local storage on the stack * This is accomplished by adjusting the stack pointer * Local storage is *not* initialized * This is why local variables return junk if they are not explicitly initialized by the programmer + Function body - Uses the arguments and local variables on the stack - Puts the return value into register (or whatever) as determined by the call convention + Postlude - Deallocates (releases) local storage on the stack (re-adjusts the stack pointer) - Restores the values of saved registers from the stack - Executes a return from subroutine instruction What happens when a function is called and executed? + Step through a call/execute/return sequence example Exceptions and exception handling + What is an exception? - Java: try-catch block - C++: try-catch-throw + A major complication + A caller can register interest in catching an exception thrown by a callee, or, an exception thrown by any function that gets called by functions called by the callee + Requires "stack unwinding" to communicate a thrown exception to the registered handler(s) + Examine the assembler code for a C++ function -- half the generated stuff are tables for stack unwinding + Stack unwinding is difficult to get correct -- thank goodness the compiler and runtime system handle it! + setjmp/longjmp is an early primitive attempt to implement exceptions in C programs ************************************************************************* Example: factorial int factorial(int n) { int result ; if (n == 1) { return( 1 ) ; } else { result = n * factorial(n - 1) ; return( result ) ; } } factorial__Fi: pushl %ebp // Save stack frame pointer movl %esp,%ebp // Make SP the new frame pointer subl $24,%esp // Allocate local storage cmpl $1,8(%ebp) // Compare 1 and n jne more // Jump if (n != 1) movl $1,%eax // Move 1 to return register jmp done // Jump to postlude more: addl $-12,%esp // Allocate space on stack movl 8(%ebp),%eax // Move n to register eax decl %eax // Decrement n by one pushl %eax // Push (n - 1) call factorial__Fi // Call factorial addl $16,%esp // Release space on stack movl %eax,%eax // Kind of a waste, huh? movl 8(%ebp),%edx // Move n to register edx imull %eax,%edx // Multiply n * factorial(n-1) movl %edx,-4(%ebp) // Move product to result movl -4(%ebp),%edx // Move result to register edx movl %edx,%eax // Move edx to return register done: movl %ebp,%esp // Restore stack pointer popl %ebp // Restore frame pointer ret int call_factorial(int n) { return( factorial(n) ) ; } call_factorial__Fi: pushl %ebp // Save frame pointer movl %esp,%ebp // Make SP the new frame pointer subl $8,%esp // Allocate local storage addl $-12,%esp // Allocate space on stack movl 8(%ebp),%eax // Move n to register eax pushl %eax // Push n for call to factorial call factorial__Fi // Call factorial addl $16,%esp // Deallocate space on stack movl %eax,%edx // Kind of a waste, huh? movl %edx,%eax // Return result in register eax movl %ebp,%esp // Restore stack pointer popl %ebp // Restore frame pointer ret ************************************************************************* Example: distance x86 floating point operations * Are performed on a VVV entry, rotating FP stack * Floating point values are returned on top of FP stack * Compiler must move FP arguments to call stack before call double distance(double x1, double y1, double x2, double y2) { double dx, dy ; dx = x2 - x1 ; dy = y2 - y1 ; return( sqrt( (dx*dx) + (dy*dy) ) ) ; } distance__Fdddd: pushl %ebp // Save stack frame pointer movl %esp,%ebp // Move stack pointer to frame pointer subl $24,%esp // Allocate local storage fldl 24(%ebp) // Push x2 on FP stack fsubl 8(%ebp) // Subtract x1 from FP stack top fstpl -8(%ebp) // Pop and store dx fldl 32(%ebp) // Push y2 on FP stack fsubl 16(%ebp) // Subtract y1 from FP stack top fstpl -16(%ebp) // Pop and store dy addl $-8,%esp // Allocate space on stack fldl -8(%ebp) // Push dx fmull -8(%ebp) // Multiple by dx fldl -16(%ebp) // Push dy fmull -16(%ebp) // Multiply by dy faddp %st,%st(1) // Add dx and dy subl $8,%esp // Push sum on call stack fstpl (%esp) call sqrt // Call library function addl $16,%esp // Deallocate arguments movl %ebp,%esp // Restore old stack pointer popl %ebp // Restore old frame pointer ret double call_distance() { double ax, ay, bx, by ; double result ; ax = 0.0 ; ay = 0.0 ; bx = 10.0 ; by = 10.0 ; result = distance(ax, ay, bx, by) ; return( result ) ; } call_distance__Fv: pushl %ebp // Save stack frame pointer movl %esp,%ebp // Make SP the new frame pointer subl $56,%esp // Allocate local storage movl $0,-8(%ebp) // Set ax to 0.0 movl $0,-4(%ebp) movl $0,-16(%ebp) // Set ay to 0.0 movl $0,-12(%ebp) fldl .LC0 // Get 10.0 fstpl -24(%ebp) // Store 10.0 in bx fldl .LC0 // Get 10.0 fstpl -32(%ebp) // Store 10.0 in by fldl -32(%ebp) // Get by subl $8,%esp // Push by fstpl (%esp) fldl -24(%ebp) // Get bx subl $8,%esp // Push bx fstpl (%esp) fldl -16(%ebp) // Get ay subl $8,%esp // Push ay fstpl (%esp) fldl -8(%ebp) // Get ax subl $8,%esp // Push ax fstpl (%esp) call distance__Fdddd // Call distance function addl $32,%esp // Discard arguments fstpl -40(%ebp) // Put return value in result fldl -40(%ebp) // Push result on FP stack movl %ebp,%esp // Postlude popl %ebp ret