CS 208 s20 — x86-64 Control Flow: Loops and Switch Statements
Table of Contents
1 Review
- write one sentence on the difference between
leaandmovinstructions1
2 Practice
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)2
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)3
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)4
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
3 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
- introduction (0:00)
- while loops using goto (2:00)
- while loops in assembly (7:48)
- optimized while loops (guarded-do) (11:28)
- for loops with goto (16:12)
- for loops in assembly (20:22)
- background on switch statements (22:28)
- why we would use a switch statement (25:30)
- switch implementation using a jump table (27:13)
- switch statements in assembly (31:05)
- end notes (37:08)
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=08be5fa6-95eb-4196-ab72-abae00f5dbd1
4 Loops
Just like conditionals, we will start by translating loops to a form using explicite goto statements to show the necessary jumps.
4.1 do-while loops
do <body-statement> while (<test-expr>);
becomes
loop: <body-statement> t = <test-expr> if (t) goto loop;
4.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
4.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
5 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
6 Homework
- CSPP practice problems 3.24 (p. 224), 3.26 (p. 228), and 3.30 (p. 236)
- Please fill out an anonymous mid-term evalution. I really want to hear from you about how the course is going.
Have a great mid-term break!
Footnotes:
1
mov copies the source to the destination, possibly computing a memory address and reading or writing a value there, while lea computes a memory address and stores that address in a register (instead of going to memory)
2
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
3
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
4
#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