Activation Record (AR)

  When a subprogram is invoked (or activated, or called), it needs memory
space to support its parameters, local variables, return address, and other
temporary variables. This piece of memory is called an Activation Record.

  One function may call other function and the latter, before it is finished,
may call another function again. So it is nature that there are many 
subprogram activated at the same time. By the definition of AR, each activated 
function needs its own unique AR. So there are many ARs existed at the same 
time.

Two problem arise: where do we allocate memory for such ARs, and how do we
manage them? 


Allocation of ARs
  1) static 
     The early Fortran uses this approach. 
     Since allocation is done before run time and is fixed during run time,
     there is no need to manage! 
     However, recursive invocation is not supported. (Why? )

  2) dynamic
     The space for an AR is allocated at run time. 
     When a function is activated, an AR is allocated before its execution 
     begins.  And when a function is finished, its AR ``may'' be deallocated. 
     For normal function invocation, the last called function is the first to
     finish. This LIFO behavior suggests using a stack to store ARs.

How to access the variables stored in an AR ? (dynamic allocation)
  For a variable, its offset to the base of its AR is fixed and known at 
  compiling time. If the base of AR is stored in a register, register relative
  addressing mode can be applied. 

  But how to maintain the base of an AR in a register? 

  If foo() invokes goo(a,b), the detail calling sequence may be as follows.
     foo()
     {
        ....                    ========+
        goo(a,b);                      ||
        ....                           ||
     }                                 \/
  ---------------------------------------------------------------------------
     foo()
     {
        ....                       <------- (1)
        push a
        push b        goo()
        jsr  g   ------>           <------- (2)
                      push BP
                      BP = SP
                      SP = SP - size    <------ (3)
                      g() begins ---+
                      .....         |
                      g() ends   ---+
                      SP = BP                           <---- (4)
                      BP = pop()     BP is restored     <---- (5)
                      rsub           
               <--------                                <---- (6)
        pop                          SP is also restored. 
        pop                                             <---- (7) == (1)
        ......
     }
  ---------------------------------------------------------------------------

  The snapshots of stack corresponding to the time indicated are as follows.

   (1) 
 <------------ AR of foo ---------->
 | ... ra  BP  L1 L2 ..............|
           |   ^-- current BP       ^-- SP
           +---- saved previous BP
   (2)
 <------------ AR of foo ---------->
 | ... ra  BP  L1 L2 ..............| a b ra 
           |   ^-- current BP               ^-- SP
           +---- saved previous BP
   (3)
 <------------ AR of foo ----------><----------- AR of goo ---------->
 | ... ra  BP  L1 L2 ..............| a b ra BP ..............        |
                                            |   ^-- current BP        ^-- SP
                                            +---- saved previous BP
   (4)
 <------------ AR of foo ----------><----------- AR of goo ---------->
 | ... ra  BP  L1 L2 ..............| a b ra BP ..............        |
                                            |  ^-- BP==SP
                                            +---- saved previous BP
   (5)
 <------------ AR of foo ----------><----------- AR of goo ---------->
 | ... ra  BP  L1 L2 ..............| a b ra BP ..............        |
               |                            ^-- SP
               +------------------------- BP
   (6)
 <------------ AR of foo ----------><----------- AR of goo ---------->
 | ... ra  BP  L1 L2 ..............| a b ra BP ..............        |
               |                          ^-- SP
               +------------------------- BP
===============================================================================
#include <stdio.h>                 goo:
                                   	pushl	%ebp
void goo(int a, int b)             	movl	%esp, %ebp
{                                  	subl	$16, %esp
   int c;                          	movl	12(%ebp), %eax
                                   	addl	8(%ebp), %eax
   c = a + b;                      	movl	%eax, -4(%ebp)
   return;                         	leave
}                                  	ret
                                   foo:
void foo()                         	pushl	%ebp
{                                  	movl	%esp, %ebp
    int L1, L2;                    	subl	$16, %esp
    goo(L1, L2);                   	pushl	-4(%ebp)
}                                  	pushl	-8(%ebp)
                                   	call	goo
main()                             	addl	$8, %esp
{                                  	leave
  foo();                           	ret                      
}