IA32 Stack Frame, Procedure Calls

Stack Frames (Activation Records)

int h( int x )
{
    int a, b, c; // local variables
    a = x + 3;
    b = 4 * x;
    c = a + b;
    return c;
}

int g( int y )
{
    int d, e; // local variables
    d = h( y );
    e = h( d );
    return e;
}

In C and Java, local variables are only required during execution of functions and methods. Each function/method call must remember where it was called from in order to return. The local variables, return information, and arguments are stored on the runtime stack. The FIFO (First In First Out) nature of the calls allows a stack to be used. 

    foo = g( 7 );
    printf("%d\n", foo );
The g(7) call results in
saved PC 
y = 7
d
e
Inside g, the first call to h results in
saved PC 
y = 7
d
e
saved PC 
x = 7
a
b
c
When the first call to h returns and the second call occurs, the stack now contains
saved PC 
y = 7
d
e
saved PC 
x = 38
a
b
c

gcc frame

The following IA32 instructions are used to implement subroutine calls and returns. 

    call label
push %eip on to the stack and jump to label, 
    call *S
push %eip on to the stack and jump to *S, 
    ret  ; assumes %esp points to the return address
pop the return address from the stack and jump to it.

The general frame layout looks like

Every frame has a common prologue that saves the callee frame pointer, and sets up the frame pointer for the current frame. 

    pushl   %ebp         ; save old fp
    movl    %esp, %ebp   ; set current fp
At the end of any routine, we must restore the fp to its old value and set the sp to the start of the frame, and then return to the caller. 
    movl    %ebp, %esp    ; restore %esp not necessay
    popl    %ebp          ; restore old fp
    ret

The swap_add routine has two arguments and two local variables. 

int swap_add(int *xp, int *yp)
{
    int x = *xp;
    int y = *yp;

    *xp = y;
    *yp = x;
    return x + y;
}
We can see the prologue and finish of the swap_add routine. 
swap_add:
    pushl   %ebp         ; save old fp
    movl    %esp, %ebp   ; set current fp

    pushl   %ebx         ; save %ebx

    movl    12(%ebp), %ebx ; get yp
    movl    8(%ebp), %ecx  ; get xp
    movl    (%ebx), %edx   ; get *yp
    movl    (%ecx), %eax   ; get *xp
    movl    %edx, (%ecx)   ; update *xp
    movl    %eax, (%ebx)   ; update *yp
    addl    %edx, %eax     ; return dum in %eax

    popl    %ebx          ; restore %ebx

    movl    %ebp, %esp    ; restore %esp not necessay
    popl    %ebp          ; restore old fp
    ret
The %ebx register is saved since by convention it is a callee save register. The other callee save registers are %esi and %edi. The caller registers are %eax, %edx, and %ecx

An example caller could be 

int caller()
{
    int arg1 = 534;
    int arg2 = 1057;
    int sum = swap_add(&arg1, &arg2);
    int diff = arg1 - arg2;

    return sum * diff;
}
The relavent assembly code is 
        subl    $16, %esp       ; reserve space on stack
        movl    $534, -8(%ebp)
        movl    $1057, -4(%ebp)
        leal    -4(%ebp), %eax
        pushl   %eax
        leal    -8(%ebp), %eax
        pushl   %eax
        call    swap_add

Recursion

Consider the following rescursive routine 

int
rbits( int bits, int k ) {
    if ( k < 0 ) return 0;
    return (bits&1) + rbits( bits>>1, k-1);
}

void
test( void )
{
    int x = rbits( 0x123, 4 );
}
The resulting assembler is: 
        .type   rbits, @function
rbits:
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ebx
        movl    8(%ebp), %ecx
        movl    12(%ebp), %edx
        movl    $0, %eax
        testl   %edx, %edx
        js      .L1
        movl    %ecx, %ebx
        andl    $1, %ebx
        subl    $8, %esp
        leal    -1(%edx), %eax  ; k - 1
        pushl   %eax
        movl    %ecx, %eax      ; bits >> 1
        sarl    %eax
        pushl   %eax
        call    rbits
        leal    (%eax,%ebx), %eax
.L1:
        movl    -4(%ebp), %ebx
        movl    %ebp, %esp       ; save as leave
        popl    %ebp             ;
        ret

test:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $16, %esp
        pushl   $4
        pushl   $291
        call    rbits
        leave
        ret