Control flow: if, loops, switch

The CPU has no if, no for and no switch. It runs instructions one after another, and the only way to change that order is a jump, conditional or not. Every structured statement in C is a pattern of compares and jumps. The flags chapter showed the building block: cmp sets the flags, a conditional jump reads them, and the jump usually tests the opposite of the C condition, to skip over the "then" block. This chapter assembles those blocks into every C control structure, and shows what an optimizing compiler does with them. Recognizing these shapes is most of the work of reading a disassembly.

if and else

if (cond) A; else B;

becomes:

    ; evaluate cond
    j<not cond> else     ; skip A if the condition is false
    A
    jmp end              ; skip B
else:
    B
end:

Without an else, the jmp end and the else block disappear. An else if chain is just another if inside the else block. In a disassembly, a forward conditional jump over a block followed by an unconditional jump over a second block is the signature of an if/else.

Loops

A loop is an if whose last instruction jumps back up. The only question is where to put the test. Tanenbaum describes both options: test at the beginning (while, for), which correctly runs zero times if the condition is false from the start, and test at the end (do … while), which always runs the body at least once. His Figure 5-29 has a small slip here: the test-at-the-end version counts i from 1 and loops back while i < n, so it runs one iteration fewer than the test-at-the-beginning version next to it, which runs n times. It should test i <= n.

The simulator's compiler, like clang -O0, compiles a for as test-at-the-beginning, with the increment at the bottom:

It returns 10. Zoom in to the assembly and you'll see the shape: cmp [i], 4 / jg out of the loop at the top, the body, add [i], 1, and a jmp back to the test. That's two jumps per iteration: the conditional one at the top, and the unconditional one at the bottom. gcc -O0 lays it out the other way round: one jmp straight to a test placed after the body, which then jumps back up while the condition holds.

Optimizing compilers rotate the loop to save one of them: a single test before the loop to handle the zero-iteration case, then a test-at-the-end loop. It's the combination the book recommends when the compiler can't prove the loop runs at least once. clang -O2 for for (int i = 0; i < n; i++) work(i);:

loop:
    test edi, edi
    jle  .done            ; n <= 0: don't enter the loop at all
    …                     ; save registers, i = 0 in ebp, n in ebx
.body:
    mov  edi, ebp
    call work
    inc  ebp              ; i++
    cmp  ebx, ebp
    jne  .body            ; test at the end: one jump per iteration
    …
.done:
    ret

A backward conditional jump — a jump to a lower address — is how you spot a loop in machine code. The branch predictor relies on the same fact: backward branches are usually taken.

break, continue, goto

break is a jump to the instruction after the loop, and continue a jump to the loop's increment or test. They have no special machine form, which is also why C has goto: it's the one C statement that maps to a single instruction. It's still useful for jumping to a common cleanup block at the end of a function, as the Linux kernel does everywhere.

It returns 2: the loop stops at 15, and 23 is never examined.

&& and || are jumps too

In C, a && b doesn't evaluate b if a is false, and a || b doesn't evaluate b if a is true. That's short-circuit evaluation, and it's what makes p != NULL && p->x > 0 safe. It means && and || compile to jumps, not to an and or or instruction. return x >= 10 && x <= 20; becomes two compares, each jumping straight to "false" if it fails:

    cmp DWORD PTR [rbp-4], 10
    jl  .false            ; x < 10: the whole && is false, skip the second test
    cmp DWORD PTR [rbp-4], 20
    jg  .false
    mov eax, 1
    jmp .end
.false:
    mov eax, 0

You can watch the second operand being skipped:

It returns 2. check(0) && … stops after its first call because the left side is false, and check(1) || … stops after its first call because the left side is true. Four calls are written; two run.

Four ways to compile a switch

A switch compares one value against many constants. Compilers pick among several strategies depending on how the case values are spread out — and the choice is visible in the binary.

A compare chain. For a few cases, or values far apart, the compiler just tests them one by one: cmp eax, 1 / je, cmp eax, 100 / je, and so on. That's what clang -O0 does for cases 1, 100, 1000 and 10000.

A jump table. When the cases are dense — 0 to 4, or 1 to 6 — the compiler builds a table of code addresses in .rodata, one per value, and jumps through it in one step, whatever the number of cases. clang does this even at -O0, and so does the simulator's compiler. gcc's threshold depends on the target and the optimization level: for the five-case switch below, gcc 12 at -O0 for ARM64 still emits a chain of compares.

It returns 42. Zoom in to the assembly to see the table:

    mov eax, DWORD PTR [rbp-4]     ; k
    cmp eax, 4
    ja  .default                   ; k < 0 or k > 4 (unsigned compare catches both)
    lea rdx, [rip+.table]
    jmp QWORD PTR [rdx+rax*8]      ; jump to table[k]
    …
.table:
    .quad .case0, .case1, .case2, .case3, .case4

One trick is worth noticing: ja, an unsigned comparison, rejects negative values too, since −1 as unsigned is 4,294,967,295. If the cases start at 1 instead of 0, the compiler first subtracts 1. Holes in the range point to default. In a disassembly, this sequence — a bounds check, then an indirect jmp through [table + index × 8] — means switch, and the table tells you where every case is.

A binary search. For sparse values, optimizing compilers sort the cases and search them: clang -O2 compiles the 1/100/1000/10000 switch as cmp edi, 999 / jg first, splitting the cases in two, then tests within each half. That's log₂ n comparisons instead of n.

A lookup table of values. When every case just returns a constant, clang -O2 doesn't jump at all. The days-per-month switch below becomes one bounds check and one load:

int days(int month) {
    switch (month) {
    case 1: return 31;  case 2: return 28;  case 3: return 31;
    case 4: return 30;  case 5: return 31;  case 6: return 30;
    default: return 0;
    }
}

days:
    dec  edi                                  ; month - 1
    xor  eax, eax                             ; default: 0
    cmp  edi, 5
    ja   .done
    mov  eax, DWORD PTR [.table + 4*rdi]      ; table = {31, 28, 31, 30, 31, 30}
.done:
    ret

Sometimes, no branch at all

Branches are cheap when predicted, but a mispredicted one costs a pipeline flush, 15 to 20 cycles on current cores. When both sides of a choice are cheap, optimizing compilers compute both and select one, with no jump. return a > b ? a : b; at clang -O2:

max:
    mov    eax, esi       ; assume b
    cmp    edi, esi
    cmovg  eax, edi       ; if a > b, take a instead
    ret

cmovg — conditional move if greater — reads the flags like a jump would, but never changes the instruction flow, so there's nothing to mispredict. The days lookup table above is the same idea: turn control flow into data flow. For a reverse engineer, it means an if in the source can show up with no jump at all in the binary.

Takeaways

• Every C control structure is compares and jumps. The jump usually tests the opposite of the C condition, to skip the block it guards.
• if/else is a forward jump over "then" plus a jump over "else". A backward jump means a loop.
• Loops test at the beginning (while, for) or at the end (do … while). Optimizers rotate loops: one guard test, then a test at the bottom, one jump per iteration.
• && and || short-circuit: they compile to jumps, and their right side may never run.
• A switch becomes a compare chain, a jump table (dense cases: bounds check with ja, then jmp [table + index × 8]), a binary search (sparse cases), or a lookup table of values.
• Optimizers remove some branches entirely with cmov and tables, so the machine code may have fewer jumps than the source.