CS 208 s20 — 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. introduction & announcements (0:00)
  2. warmup (1:46)
  3. local variables on the stack (6:15)
  4. example of a pointer to a local variable (11:48)
  5. example of passing arguments on the stack (20:43)
  6. stack frames exercise (29:22)
  7. local variables in registers (31:31)
  8. example of callee-saved registers (33:46)
  9. recursive procedures (37:59)
  10. end notes (39:58)

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=e4368c56-cccd-4468-ae6a-abb501137a43

2 Annoucements

  • Thank you for submitting midterm evaluations!
    • Clarification: there won’t be any exams, just continued weekly quizzes
      • This week's will be posted later today
    • I have video office hours appointments!
      • Link here or on the course web page
      • Send me an email or Slack message to set up another time
    • VM window super small?
      • Likeliest solution is to install VirtualBox "Guest Additions" in your VM
        • Here are some ways of doing that:
          • link 1, link 2
          • For link 1, there's a note specifically for Xubuntu
      • Other possibilities:
        • Go to the VirtualBox Preferences » Display » Scale Factor = 200%.
        • Go to the VM Settings » Display » Screen » Graphics Controller = VBoxVGA

3 Warmup

        call next
        popq %rax
  1. What gets stored in %rax by these instructions?1
  2. Write down the different uses for the stack (i.e., what kinds of data gets stored there?).2

4 Procedures Continued

4.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

4.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)
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
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)
        .string "%d %d %d %d %d"
        .string "KABLOOEY!!!"
        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
        addq    $8, %rsp          // cleaning up the pushq %rax from before

4.3 Stack Frames


Each node in the above tree represents a function call. How many stack frames will be created? How many will be present on the stack at one time?3

4.4 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)


long P(long x, long y) {
    long u = Q(y);
    long v = Q(x);
    return u + v;
        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

4.5 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;
        result = n * fact_rec(n - 1);
    return result;
        cmpq    $1, %rdi
        jg      .L8
        movl    $1, %eax
        pushq   %rbx
        movq    %rdi, %rbx
        leaq    -1(%rdi), %rdi
        call    fact_rec
        imulq   %rbx, %rax
        popq    %rbx

4.6 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() {
        movq    (%rdi), %rax
        addq    %rax, %rsi
        movq    %rsi, (%rdi)
        subq    $16, %rsp
        movq    $208, 8(%rsp)
        movl    $124, %esi
        leaq    8(%rsp), %rdi
        call    increment
        addq    8(%rsp), %rax
        addq    $16, %rsp
        movl    $0, %eax
        call    call_incr
        movl    $0, %eax

5 Homework

  1. CSPP practice problems 3.34 (p. 252) and 3.35 (p. 255)
  2. The week 5 quiz has been posted. It is due 9pm Wednesday, May 13.
  3. If you have't posted in the lab 2 check-in forum, do so today!
    • DO NOT WAIT ANY LONGER TO START LAB 2 (if you haven't already started)



Those instructions store the address of the popq %rax instruction in %rax. call pushes the address of the next instruction (the return address) onto the stack and then jumps to the specified target. popq %rax is the next instruction, so call next pushes its address onto the stack, and then jumps to the next label, which happens to be at popq %rax. popq %rax then pops the value from the top of the stack into %rax.

  1. Arguments for a function call (beyond the first six)
  2. Saved registers (callee-saved)
  3. Local variables
  4. Return address

Six stack frames will be created, one for each call. Four will be on the stack at one time, (e.g., slorp, squish, splat, printf), since once squish calls slop, splat and the first printf will have returned and been popped off the stack.