Execution (call) stack
P.J. Drongowski
24 February 2005

*************************************************
Call site (function call)
*************************************************

  c = f(a, b) ;                     To do list

  PUSH a  // Push arguments           1. Pass arguments
  PUSH b                              2. Invoke the function (start the
  CALL f  // Invoke function             function executing)
  POP     // Clean up stack           3. Return control to the caller (restart
  POP                                    the caller)
                                      4. Receive the return value

                  ------------
                 |  Ret Addr  | <--- Stack pointer
                  ------------
                 |      a     |
                  ------------
                 |      b     |
                  ------------
                 |     ...    |


*************************************************
Building blocks (machine resources)
*************************************************

  Registers                  IA-32
  -------------------------  ------------------
    Program counter          pc
    Stack pointer            esp
    Frame pointer            ebp
    General registers
      All purpose registers  eax, ebx, ecx, edx
      Return value register  eax

  Memory / execution stack

  Instructions
  ---------------   --------------------------
    PUSH value      Push value on execution stack
    POP reg         Pop value from execution stack
    CALL fun        Save return address; Jump to function
    RETURN          Pop return address; Jump to return address


*************************************************
Function definition
*************************************************

Function definition
                                   To do list
  int f(int a, int b)                1. Save general registers
  {                                  2. Establish a frame pointer
    int x, y, z ;  // Local vars     3. Allocate local storage
    ...                              4. Execute function body
  }                                  5. Deallocate local storage
                                     6. Restore frame pointer
                                     7. Restore general registers
                                     8. Return

  The frame pointer refers to the function's execution context --
  everything that the function body needs to execute. The frame pointer
  is a kind of an "anchor" point.

  Restoring the frame pointer returns the execution context to
  the previous function (the caller)

       ------------
      |      z     | <--- Stack pointer
       ------------
      |      y     |                        PUSH greg0
       ------------                         PUSH greg1
      |      x     |                        PUSH frame pointer
       ------------                         SP <- SP + 3
      | Prev Frame |                          ... function body ...
       ------------                         SP <- SP - 3
      | Prev greg2 |                        POP frame pointer
       ------------                         POP greg1
      | Prev greg1 |                        POP greg0
       ------------                         RETURN
      |  Ret Addr  | <--- Frame pointer
       ------------
      |      a     |
       ------------
      |      b     |
       ------------
      |     ...    |

How does the function body refer to arguments and local variables?

  * Uses "base + offset" addressing
  * Compiler knows the offset to the argument or local variable
  * Generates instructions that add offset to frame pointer to compute
    the address of the desired data item

    x = 37 ;       Memory[frame pointer + offset] <- 37

Summary

  * Execution stack provides a common place to pass arguments,
    save return address, etc.
  * A lot of work goes on to perform a function call
    + Takes time - Must execute instructions to save/restore, etc.
    + Takes space - Each call consumes space on the execution stack