CS 208 f21 — x86-64 Control Flow: Loops and Switch Statements

Table of Contents

1 Review

Take some time to practice translating assembly to C. There's no single correct C code for the given assembly code—multiple valid translations exist.

Exercise 1: long f(long x, long y) 1 

f(long, long):
        subq    %rsi, %rdi
        jne     .L3
        movq    %rdi, %rax
        ret
.L3:
        movq    %rsi, %rax
        ret

Exercise 2: long f(long x, long y) 2 

f(long, long):
        cmpq    $2, %rdi
        setle   %dl
        cmpq    %rsi, %rdi
        sete    %al
        testb   %al, %dl
        je      .L3
        movl    $1, %eax
        ret
.L3:
        movl    $2, %eax
        ret

Exercise 3: long f(long *p) 3 

f(long *p):
        testq   %rdi, %rdi
        je      .L4
        movq    (%rdi), %rax
        leaq    -10(%rax), %rdx
        testq   %rdx, %rdx
        jle     .L3
        addq    %rax, %rax
        ret
.L3:
        addq    $1, %rax
        ret
.L4:
        movl    $0, %eax
        ret

2 Loops

2.1 Example

int sum_x_to_y(int x, int y) {
    int sum = 0;
    while (x < y) {
        sum += x;
        x++;
    }
    return sum;
}

Loops don't require anything special beyond what we've already seen for conditionals: we have loop conditions (usually implemented via cmp) and jumps to get us back to the top of the loop. Consider the C code above, and fill in the assembly below. %edi will hold x and %esi will hold y. You will use two addl, a cmpl, a jl, a jmp, and a movl.4 

sum_x_to_y:
  // initialize sum

loop_body:


loop_test:


  ret

Just like conditionals, we can start the journey from C to assembly by translating loops to a form using explicit goto statements to show the necessary jumps.

2.2 do-while loops

do
    <body-statement>
    while (<test-expr>);

becomes 

loop:
    <body-statement>
    t = <test-expr>
    if (t)
        goto loop;

2.3 while loops

while (<test-expr>)
    <body-statement>

becomes 

    goto test;
loop:
    <body-statement>
test:
    t = <test-expr>
    if (t)
        goto loop;
  • note the jump-to-the-middle approach to loop implementation
  • On higher optimization settings, while loops get translated into a guarded-do form
    • a conditional branch followed by a do-while loop
    • can allow the initial check to be optimized away if the compiler can determine the condition will always hold
  • here's a C function that takes a number and uses a while loop to compute the factorial of it: 
long fact_while(long x){
    long result = 1;
    while (x > 1) {
        result = result * x;
        x = x - 1;
    }
    return result;
}

This function compiles to the following assembly (gcc version 7, -Og flag). It follows the jump-to-the-middle approach. 

fact_while:
        movl    $1, %eax
        jmp     .L2
.L3:
        imulq   %rdi, %rax
        subq    $1, %rdi
.L2:
        cmpq    $1, %rdi
        jg      .L3
        rep ret

If we increase the optimization to -O2, we can see how it changes to a guarded-do (initial comparison either jumps over the loop or proceeds directly into the loop body). 

fact_while:
        cmpq    $1, %rdi
        movl    $1, %eax
        jle     .L4
.L3:
        imulq   %rdi, %rax
        subq    $1, %rdi
        cmpq    $1, %rdi
        jne     .L3
        rep ret
.L4:
        rep ret

2.4 for loops

  • C language standard states that in the absence of continue 
for (<init-expr>; <test-expr>; <update-expr>)
    <body-statement>

is equivalent to 

<init-expr>;
while (<test-expr>) {
    <body-statement>
    <update-expr>;
}
  • hence, a for loop is then translated using jump-to-the-middle or guarded-do depending on the optimization level
  • changing the while loop to a for loop in our factorial function doesn't change the assembly at all: 
long fact_for(long x){
    long result = 1;
    for(long i = x; i > 1; i--) {
        result = result * i;
    }
    return result;
}

compiles to (gcc version 7, -Og flag) 

fact_for:
        movl    $1, %eax
        jmp     .L2
.L3:
        imulq   %rdi, %rax
        subq    $1, %rdi
.L2:
        cmpq    $1, %rdi
        jg      .L3
        rep ret

3 Switch

  • using a switch statement can make code more readable than a long chain of if/else if/else.
  • also allows for efficient implementation via a jump table
    • array where entry \(i\) is the address of the code to be executed when the switch value is \(i\)
    • because it's handled with a single array lookup and jump, the time to perform switch is constant regardless of the number of cases (as opposed to series of if-else)
    • best used when there are more than a few cases and where the values are not too far apart
  • see CSPP figures 3.22 and 3.23 (p. 234-5) for example implementation 
long switch_ex(long x, long y, long z) {
    long w = 1;
    switch(x) {
    case 1:
        w = y * z;
        break;
    case 2:
        w = y + z;
    case 3:
        w += z;
        break;
    case 5:
        return y + 7;
    case 6:
        w -= z;
        break;
    default:
        w = 2;
    }
    return w;
}

switch-jump-table.png 

switch_ex(long, long, long):
        cmpq    $6, %rdi            // compare x to 6
        ja      .L9                 // if x > 6, jump to the label for the default case
        jmp     *.L4(,%rdi,8)       // otherwise, use x as an offset from L4 to select a label to jump to
.L4:
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L10
        .quad   .L9
        .quad   .L5
        .quad   .L3
.L8:                                // x == 1
        movq    %rsi, %rax
        imulq   %rdx, %rax
        ret
.L7:                                // x == 2
        leaq    (%rsi,%rdx), %rax
        jmp     .L6
.L10:                               // x == 3, move 1 into w since that matters here
        movl    $1, %eax
.L6:                                // x == 3, fall-through from x == 2
        addq    %rdx, %rax
        ret
.L5:                                // x == 5
        leaq    7(%rsi), %rax
        ret
.L3:                                // x == 6
        movl    $1, %eax            // move 1 into w since that matters here
        subq    %rdx, %rax
        ret
.L9:                                // x == 0, x == 4, x > 6, x < 0
        movl    $2, %eax
        ret

4 Practice

Translate this assembly to C code:5 

.LC0:
        .string "Hello %d"
main:
        pushq   %rbx
        movl    $0, %ebx
        jmp     .L2
.L3:
        movl    %ebx, %esi
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
        addl    $1, %ebx
.L2:
        cmpl    $9, %ebx
        jle     .L3
        movl    $0, %eax
        popq    %rbx
        ret

CSPP practice problems 3.24 (p. 224), 3.26 (p. 228), and 3.30 (p. 236)

5 Background for Lab 2

See the slides here: ./lab2-background-slides.pdf (includes a walkthrough of the activity below)

  • register uses: %rax, %rsp, %rdi, %rsi, %rdx, %rcx, %r8, %r9
  • starting lab 2
    • hacking vs analyzing
    • either way, practice the skill of finding the relevant detail and ignoring the rest
  • basic commands: r(un), b(reak), stepi, nexti, c(ontinue), info reg, disas, p(rint), x, finish
  • blank line at the end of defuse.txt
  • push/pop/moving %rsp at the beginning and end of functions
  • sscanf

6 gdb activity

  • Get started with these commands: 
wget http://cs.carleton.edu/faculty/awb/cs208/f21/topics/gdb-activity.tar
tar xvf gdb-activity.tar
cd gdb-activity
make
  • Try running the program with ./gdb-activity, what happens?
  • Open gdb-activity.c 
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int compare(int a, int b);

int main(int argc, char** argv)
{
    int a, b, n;
    char input[100];
    printf("enter good args: ");
    if (fgets(input, 100, stdin) == NULL) {
        printf("I said good args\n");
    }

    n = sscanf(input, "%d %d", &a, &b);
    if (n == 2 && compare(a,b) == 1) {
        printf("good args!\n");
    }
    else {
        printf("bad args, try harder!\n");
    }
    return 0;
}

Observations:

  • four functions are called: printf, fgets, sscanf, and compare
    • the first three are C library functions (since they aren't declared anywhere, they must come from the #include of library headers)
    • look each library function up in the terminal with man 3 FUNCTION, or consult cplusplus.com/FUNCTION (the latter is often easier to understand)
  • to get the program to print "good args!", we need fgets to return something other than NULL, have sscanf return 2, and have compare(a, b) return 1
    • fgets will read from the command line (stdin) and store the string in input, up to 100 characters
      • only returns NULL on failure, so we probably don't have to worry about that
    • sscanf is a super useful function: it parses a string (the first parameter) according to a format string given by the second parameter
      • %d is the format specifier for an integer, so this sscanf call will parse input as two integers separated by a space
      • the parsed items (i.e., each %d) will be written to the corresponding pointers provided as arguments after the format string
        • so the first integer in input will be stored in a and the second will be stored in b
    • compare is actually implemented in raw assembly in gdb-activity.s
  • Lets use gdb to get a sense for how everything is fitting together. (This tutorial video goes over using gdb if you want to review.)
  • Running disas compare from within gdb gives 
0x00000000004006d7 <+0>:     push   %rbx
0x00000000004006d8 <+1>:     mov    %rdi,%rbx
0x00000000004006db <+4>:     add    $0x5,%rbx
0x00000000004006df <+8>:     add    %rsi,%rbx
0x00000000004006e2 <+11>:    cmp    $0xd0,%rbx
0x00000000004006e9 <+18>:    sete   %al
0x00000000004006ec <+21>:    movzbq %al,%rax
0x00000000004006f0 <+25>:    pop    %rbx
0x00000000004006f1 <+26>:    retq
  • We can reverse engineer the C code to be something like 
int compare(int a, int b) {
    return a + b + 5 == 0xd0; // we add %rdi, %rsi, and 5 together in %rbx and then compare it to $0xd0
                              // sete writes 1 to the given register if the cmp indicates the operands are equal
                              // since this is the return value, and we want compare to return 1, 
                              // we should choose inputs to make these equal
}

Footnotes:

1 
long f(long x, long y) {
    long z = x - y;
    if (z == 0) {
        return z;
    }
    return y;
}

f(long, long):
        subq    %rsi, %rdi  // compute x - y, ok to overwrite x since we don't use it again
        jne     .L3         // jump to L3 when %rdi != %rsi (i.e., x - y != 0)
        movq    %rdi, %rax  // copy z to the return value
        ret
.L3:
        movq    %rsi, %rax  // copy y to the return value
        ret
2 
long f(long x, long y) {
    if (x < 3 && x == y) {
        return 1;
    } else {
        return 2;
    }
}

f(long, long):
        cmpq    $2, %rdi    // perform x - 2, set condition codes
        setle   %dl         // write 1 to the lowest byte of %rdx when x <= 2 (i.e., %dl contains 1 when x < 3)
        cmpq    %rsi, %rdi  // perform x - y, set condition codes
        sete    %al         // write 1 to the lowest byte of %rax when x == y
        testb   %al, %dl    // perform %al & %dl, set condition codes
        je      .L3         // jump to L3 when %al & %dl == 0 (i.e., jump unless both previous set instructions
                            // wrote 1, meaning x < 3 and x == y)
        movl    $1, %eax    // make return value 1
        ret
.L3:
        movl    $2, %eax    // make return value 2
        ret
3 
#include <stdlib.h>  // to provide NULL
long f(long *p) {
    if (p == NULL) {
        return 0;
    }
    if (*p - 10 > 0) {
        return *p + *p;
    } else {
        return *p + 1;
    }
}

f(long *p):
        testq   %rdi, %rdi       // perform p & p, set condition codes
        je      .L4              // jump to L4 if p & p == 0 (i.e, jump if p is NULL)
        movq    (%rdi), %rax     // put *p in the return value
        leaq    -10(%rax), %rdx  // put *p - 10 in %rdx (remember lea uses the value in the register, not memory
        testq   %rdx, %rdx       // perform (*p - 10) & (*p - 10), set condition codes
        jle     .L3              // jump to L3 if (*p - 10) & (*p - 10) <= 0 (i.e., don't jump if *p - 10 > 0)
        addq    %rax, %rax       // return value is now *p + *p
        ret
.L3:
        addq    $1, %rax         // add 1 to return value
        ret
.L4:
        movl    $0, %eax         // set return value to 0
        ret
4 
sum_x_to_y:
        movl    $0, %eax
        jmp     .L2
.L3:
        addl    %edi, %eax
        addl    $1, %edi
.L2:
        cmpl    %esi, %edi
        jl      .L3
        ret
5 
#include <stdio.h>

int main() {
    for (int i = 0; i < 10; i++) {
        printf("Hello %d", i);
    }
}