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

1. Video
2. Loops
3. Switch

1 Video

Here is a video lecture for the material outlined below. It covers CSPP sections 3.6.7 and 3.6.8 (p. 220–236). It contains sections on

while loops using goto (0:29)
while loops in assembly (6:02)
optimized while loops (guarded-do) (9:42)
for loops with goto (14:26)
for loops in assembly (18:22)
background on switch statements (20:25)
why we would use a switch statement (23:27)
switch implementation using a jump table (25:10)
switch statements in assembly (28:57)

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=54a26cd1-ddd0-493c-bde6-ac470130ef15

2 Loops

Just like conditionals, we will start by translating loops to a form using explicite goto statements to show the necessary jumps.

2.1 do-while loops

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

becomes

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

2.2 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.3 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:
    case 6:
        w -= z;
        break;
    default:
        w = 2;
    }
    return w;
}

switch_ex(long, long, long):
        cmpq    $6, %rdi            // compare x to 6
        ja      .L8                 // 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   .L8
        .quad   .L3
        .quad   .L5
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L7
.L3:                                // x == 1
        movq    %rsi, %rax
        imulq   %rdx, %rax
        ret
.L5:                                // x == 2
        leaq    (%rsi,%rdx), %rax
        jmp     .L6
.L9:                                // 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
.L7:                                // x == 5, x == 6
        movl    $1, %eax            // move 1 into w since that matters here
        subq    %rdx, %rax
        ret
.L8:                                // x == 0, x == 4, x > 6, x < 0
        movl    $2, %eax
        ret