CS 208 s21 — Implementing Procedure Calls

Table of Contents

1 Video

Here is a video lecture for the material outlined below. It covers CSPP sections 3.7.3 through 3.7.6 (p. 245–254). It contains sections on

  1. local variables on the stack (0:22)
  2. example of a pointer to a local variable (5:33)
  3. example of passing arguments on the stack (14:18)
  4. local variables in registers (22:56)
  5. example of callee-saved registers (25:11)
  6. recursive procedures (29:24)

The Panopto viewer has table of contents entries for these sections. Link to the Panopto viewer: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=cc1f6a57-c4f1-4e91-95db-ac50011403ba

2 Procedures Continued

2.1 Local Storage on the Stack

  • not all local variables are necessarily stored on the stack
    • accessing registers is much faster than accessing memory, so the compiler will use a register for a local variable whenever possible
  • sometimes we have to store things on the stack:
    • when we run out of registers (we only have a fixed number of them, after all), we'll have to start using the stack
    • if code generates a pointer to a local variable (via & operator), we have to store that variable on the stack
      • why? Because a register doesn't have an address, only a name.
      • In order to have a pointer to something (i.e., a memory address for it), the value has to be in memory somewhere
    • if our local variables are data structures like arrays or structs that don't make sense to store in a register

2.2 Examples

void swap(long *xp, long *yp) {
    long t = *xp;
    *xp = *yp;
    *yp = t;
}

long f(long x, long y) {
    swap(&x, &y);
    return x - y;
}

swap(long*, long*):
        movq    (%rdi), %rax
        movq    (%rsi), %rdx
        movq    %rdx, (%rdi)
        movq    %rax, (%rsi)
        ret
f(long, long):
        subq    $16, %rsp            // allocate space on the stack by moving the stack pointer (grows DOWN)
        movq    %rdi, 8(%rsp)        // move x onto the stack
        movq    %rsi, (%rsp)         // move y onto the stack
        movq    %rsp, %rsi           // copy the stack address for y to rsi
        leaq    8(%rsp), %rdi        // copy the stack address for x in rdi
        call    swap(long*, long*)
        movq    8(%rsp), %rax
        subq    (%rsp), %rax
        addq    $16, %rsp            // free stack space by moving the stack pointer back up
        ret

void parse_five_numbers(char *input, int numbers[])
{
  int numScanned = sscanf(input, "%d %d %d %d %d",
                          &(numbers[0]), &(numbers[1]), &(numbers[2]),
                          &(numbers[3]), &(numbers[4]));
  if (numScanned < 5)
    printf("KABLOOEY!!!");
}

.LC0:
        .string "%d %d %d %d %d"
.LC1:
        .string "KABLOOEY!!!"
parse_five_numbers:
        subq    $16, %rsp         // allocate stack frame
        movq    %rsi, %rdx        // address of numbers[0] as third arg
        leaq    16(%rsi), %rax    // load address of numbers[4] into rax
        leaq    4(%rsi), %rcx     // address of numbers[1] as fourth arg
        pushq   %rax              // push address of numbers[4] onto the stack as seventh arg
        leaq    12(%rsi), %r9     // address of numbers[3] as sixth arg
        leaq    8(%rsi), %r8      // address of numbers[2] as fifth arg
        movl    $.LC0, %esi       // address of format string as second arg
        movl    $0, %eax
        call    __isoc99_sscanf   // never loaded something into %rdi (first arg), why?
                                  // it's the same as the first arg to parse_five_numbers, so we just keep it
        addq    $16, %rsp         // deallocate stack frame
        cmpl    $4, %eax
        jg      .L1
        movl    $.LC1, %edi
        movl    $0, %eax
        call    printf
.L1:
        addq    $8, %rsp          // cleaning up the pushq %rax from before
        ret

2.3 Local Storage in Registers

  • The compiler has to make sure callee does not overwrite register values the caller plans to use later
  • x86-64 has uniform conventions that all procedures must adhere to
    • %rbx, %rbp, and %r12– %r15 are callee-saved registers (when P calls Q, Q must preserve these values)
      • preserving means not writing to that register or pushing its value onto the stack and popping it off to restore before returning (saved registers portion of the stack frame)
    • all other registers besides the stack pointer %rsp are caller-saved (when P calls Q, Q is free to modify these registers, so P must save any that it needs)

reg-conventions.png 

long P(long x, long y) {
    long u = Q(y);
    long v = Q(x);
    return u + v;
}

P:
        pushq   %rbp        // save value of callee-saved register this procedure will use
        pushq   %rbx        // save value of callee-saved register this procedure will use
        movq    %rdi, %rbp  // %rdi is a caller-saved register, we'll need its value later so we
                            // save it in a callee-saved register that Q will have to preserve
        movq    %rsi, %rdi
        call    Q
        movq    %rax, %rbx  // %rax is also caller-saved, so put in it callee-saved %rbx for 
                            // later use
        movq    %rbp, %rdi
        call    Q
        addq    %rbx, %rax
        popq    %rbx        // restore value of callee-saved register this procedure used
        popq    %rbp        // restore value of callee-saved register this procedure used
        ret

2.4 Recursive Procedures

  • the stack and register conventions facilitate recursion without needing any extra apparatus 
long fact_rec(long n) {
    long result;
    if (n <= 1)
        result = 1;
    else 
        result = n * fact_rec(n - 1);
    return result;
}

fact_rec:
        cmpq    $1, %rdi
        jg      .L8
        movl    $1, %eax
        ret
.L8:
        pushq   %rbx
        movq    %rdi, %rbx
        leaq    -1(%rdi), %rdi
        call    fact_rec
        imulq   %rbx, %rax
        popq    %rbx
        ret

2.5 Example in gdb

  • Not in today's video, included here for completeness
  • using -tui
  • layout asm then layout regs to get assembly and register views
  • focus cmd to have arrows go through command history
  • winheight regs -LINES to have registers take up less of the screen
  • note %rip changes each step
  • %rsp changes when we call call_inrc even before sub $0x10,%rsp—why?
  • Print vs eXamine
    • display the value of an expression vs use the value of an expression as a memory address and display the value stored in memory there
    • p $rsp displays the address of the top of the stack
    • x $rsp displays the value stored at the top of the stack 
long increment(long* p, long val) {
    long x = *p;
    long y = x + val;
    *p = y;
    return x;
}

long call_incr() {
    long v1 = 208;
    long v2 = increment(&v1, 124);
    return v1+v2;
}

int main() {
    call_incr();
}

increment:
        movq    (%rdi), %rax
        addq    %rax, %rsi
        movq    %rsi, (%rdi)
        ret
call_incr:
        subq    $16, %rsp
        movq    $208, 8(%rsp)
        movl    $124, %esi
        leaq    8(%rsp), %rdi
        call    increment
        addq    8(%rsp), %rax
        addq    $16, %rsp
        ret
main:
        movl    $0, %eax
        call    call_incr
        movl    $0, %eax
        ret