Frames
******

Recursion requires dynamically allocated memory for local variables and parameters.  The natural and efficient implementation of this memory is stack like.

Stack Frames
============

Stack Frame, or Frame for short, and Activation Record denote the same thing: the room reserved in the stack for the current function.

There are several things that needs to be stored in the stack:

arguments

local variables
     aka automatic variables (automatically allocated when entering in the function).

return address
     where to go back on return.

saved registers
     i.e., save the environment of the caller to be able to restore it.

temp
     i.e., automatic variables that the compiler needs when there are not enough registers.

static link
     when needed

Since most call and return instructions do not influence the stack, you are quite free with the order in which you store the various items.  Nevertheless, it is desirable to follow the conventions given by the manufacturer, so that objects from different compilers are inter-operable.

On MIPS:

            |      ...        |
            +=================+    High addresses
     fp ->  |     Arg 6       |
            |     Arg 5       |
            |    Arg 1-4      |
            +-----------------+
            |      ...        |
            | Saved Registers |
            |      ...        |
            +-----------------+
            |      ...        |
            | Local Variables |
            |      ...        |
            +-----------------+
            |      ...        |
            |   Temporaries   |
            |      ...        |
            +=================+    Low addresses
     sp ->  |      ...        |

Frame Pointer
-------------

As one can see, different functions have different storage needs, therefore we will need two informations: where the stack frame starts (the frame pointer, fp), and where it ends (the stack pointer, sp).

Registers
---------

Modern architecture have a set of caller-save registers and callee-save registers.  Of course this is just a convention: the microprocessor itself has no preference.

Suppose f uses X before calling g, and no longer needs it afterwards, where is it going to be stored?

Suppose X is used before calling several functions, and reused afterwards, what's the best thing to do?

Call Conventions
----------------

Although you may have to save arguments on the stack, using registers saves time:

  - Dynamically, more leaf functions than others.  They can even avoid allocating a frame.

  - Not all the registers need to be saved.

  - Inter-procedural register allocation.

  - SPARC's register windows.

Variables Allocated on the Stack
--------------------------------

In particular those which escape.

Static Link
-----------

When f is called, it is given a pointer to the activation record of the current frame of the function that immediately encloses f.

Examples
========

     static int
     id (int x)
     {
       int res = x;
       return x;
     }

     int
     sum (int x, int y)
     {
       int res = id (x + y);
       return res;
     }

     bash$ cc -O0 -S foo.c -O
     bash$ cat foo.s

             .verstamp       2 11
             .text
             .align  2
             .file   2 "foo.c"
             .loc    2 3

      #   1  static int
      #   2  id (int x)
      #   3  {
             .ent    $$3 2
     $$3:
             .option O0
             subu    $sp, 8
             .frame  $sp, 8, $31
             .loc    2 4
      #   4    int res = x;
             sw      $4, 4($sp)
             .loc    2 5
      #   5    return x;
             move    $2, $4
             b       $32
             .loc    2 6
      #   6  }
             b       $32
     $32:
             addu    $sp, 8
             j       $31
             .end    id
             .text
             .align  2
             .file   2 "foo.c"
             .globl  sum
             .loc    2 10

      #   7
      #   8  int
      #   9  sum (int x, int y)
      #  10  {
             .ent    sum 2
     sum:
             .option O0
             subu    $sp, 32
             sw      $31, 20($sp)
             sd      $4, 32($sp)
             .mask   0x80000000, -12
             .frame  $sp, 32, $31
             .loc    2 11
      #  11    int res = id (x + y);
             lw      $14, 32($sp)
             lw      $15, 36($sp)
             addu    $4, $14, $15
             .livereg        0x800ff0e,0xfff
             jal     $$3
             sw      $2, 28($sp)
             .loc    2 12
      #  12    return res;
             lw      $2, 28($sp)
             b       $33
             .loc    2 13
      #  13  }
             b       $33
     $33:
             lw      $31, 20($sp)
             addu    $sp, 32
             j       $31
             .end    sum

     bash$ cc -S -O1 foo.c
     bash$ cat foo.s
             .verstamp       2 11
             .text
             .align  2
             .file   2 "foo.c"
             .loc    2 3

      #   1  static int
      #   2  id (int x)
      #   3  {
             .ent    $$3 2
     $$3:
             .option O1
             subu    $sp, 8
             .frame  $sp, 8, $31
             .loc    2 4
      #   4    int res = x;
             sw      $4, 4($sp)
             .loc    2 5
      #   5    return x;
             move    $2, $4
             addu    $sp, 8
             j       $31
             .end    id
             .text
             .align  2
             .file   2 "foo.c"
             .globl  sum
             .loc    2 10
      #   6  }
      #   7

      #   8  int
      #   9  sum (int x, int y)
      #  10  {
             .ent    sum 2
     sum:
             .option O1
             subu    $sp, 32
             sw      $31, 20($sp)
             sd      $4, 32($sp)
             .mask   0x80000000, -12
             .frame  $sp, 32, $31
             .loc    2 11
      #  11    int res = id (x + y);
             lw      $14, 32($sp)
             lw      $15, 36($sp)
             addu    $4, $14, $15
             .livereg        0x800ff0e,0xfff
             jal     $$3
             sw      $2, 28($sp)
             .loc    2 12
      #  12    return res;
             lw      $2, 28($sp)
             lw      $31, 20($sp)
             addu    $sp, 32
             j       $31
             .end    sum

     bash$ cc -S -O2 foo.c
     bash$ cat foo.s
             .verstamp       2 11
             .text
             .align  2
             .file   2 "foo.c"
             .loc    2 3

      #   1  static int
      #   2  id (int x)
      #   3  {
             .ent    $$3 2
     $$3:
             .option O2
             .frame  $sp, 0, $31
             .loc    2 4
      #   4    int res = x;
             .loc    2 5
      #   5    return x;
             move    $2, $4
             j       $31
             .end    id
             .text
             .align  2
             .file   2 "foo.c"
             .globl  sum
             .loc    2 10
      #   6  }
      #   7

      #   8  int
      #   9  sum (int x, int y)
      #  10  {
             .ent    sum 2
     sum:
             .option O2
             subu    $sp, 24
             sw      $31, 20($sp)
             .mask   0x80000000, -4
             .frame  $sp, 24, $31
             move    $3, $4
             .loc    2 11
      #  11    int res = id (x + y);
             addu    $4, $3, $5
             .livereg        0x800ff0e,0xfff
             jal     $$3
             .loc    2 12
      #  12    return res;
             lw      $31, 20($sp)
             addu    $sp, 24
             j       $31
             .end    sum

In the following example, there are too many incoming arguments.

     int
     sum8 (int x1, int x2, int x3, int x4,
           int x5, int x6, int x7, int x8)
     {
       return x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8;
     }

     bash$ cc -S foo.c -O2
             .verstamp       2 11
             .text
             .align  2
             .file   2 "foo.c"
             .globl  sum8
             .loc    2 4
      #   1  int
      #   2  sum8 (int x1, int x2, int x3, int x4,
      #   3        int x5, int x6, int x7, int x8)
      #   4  {
             .ent    sum8 2
     sum8:
             .option O2
             .frame  $sp, 0, $31
             .loc    2 5
      #   5    return x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8;
             addu    $14, $4, $5
             addu    $15, $14, $6
             addu    $24, $15, $7
             lw      $25, 16($sp)
             addu    $8, $24, $25
             lw      $9, 20($sp)
             addu    $10, $8, $9
             lw      $11, 24($sp)
             addu    $12, $10, $11
             lw      $13, 28($sp)
             addu    $2, $12, $13
             j       $31
             .end    sum8