Control Flow

A program is stored as a linear sequence of instructions, yet it expresses branches, loops, and multi-way choices. The bridge is the jump: an instruction that overwrites %rip with a new address instead of letting it advance. Combined with the condition codes from arithmetic and logic, jumps let the machine choose its next instruction based on a comparison. This lesson shows how the compiler turns every C control structure into compares and jumps.

Normally %rip simply steps to the next instruction after each one finishes. A jump breaks that: it writes a different address into %rip, and the processor fetches from there instead. That single act — rewriting the program counter — is the whole machinery of every branch and loop you will see.

Jumps read the flags

An unconditional jump jmp always transfers control to its target label. A conditional jump transfers control only if the condition codes satisfy its predicate, and falls through to the next instruction otherwise. The predicate is encoded in the mnemonic's suffix, and the signed and unsigned comparisons read different flags.¹

The split is the entire reason C distinguishes int from unsigned at the machine level: a < b compiles to jl for signed operands but jb for unsigned, because less than is a sign-flag combination for signed values and a carry for unsigned. You almost never compute these flag formulas by hand; you read jl as jump if the signed comparison was less-than and trust that cmp set the flags so it works.

Set instructions

Sometimes a comparison's outcome is needed as a value rather than a branch — to store a C bool, say. The set instructions write a single byte, 1 if the flag predicate holds and 0 otherwise, using the same suffixes as the jumps.

# int gt(long x, long y): return x > y;  (x in %rdi, y in %rsi)
cmpq    %rsi, %rdi        # flags from x - y
setg    %al               # al = (x > y) ? 1 : 0
movzbl  %al, %eax         # zero-extend the byte to the int return
ret

The setg writes only the low byte %al, so the movzbl clears the upper bytes to produce a clean int. This compare / set / zero-extend sequence is the fingerprint of a boolean-valued comparison in compiled C.

Translating if/else

The standard compilation of if (test) then-body else else-body inverts the test, branches over the then-body to the else-body, and uses an unconditional jump to skip the else-body after the then-body runs.

long absdiff(long x, long y) {
    if (x < y)
        return y - x;
    else
        return x - y;
}

absdiff:
        cmpq    %rsi, %rdi        # compare x, y  (flags from x - y)
        jge     .Lelse            # if x >= y, take the else branch
        movq    %rsi, %rax        # rax = y
        subq    %rdi, %rax        # rax = y - x
        ret
.Lelse:
        movq    %rdi, %rax        # rax = x
        subq    %rsi, %rax        # rax = x - y
        ret

Trace one call to fix how the inverted test steers control. Call absdiff(3, 8), so %rdi = 3 and %rsi = 8. The cmpq %rsi, %rdi sets the flags from $3-8=-5$: the result is negative, so SF = 1, and no signed overflow occurred, so OF = 0; jge is taken only when $\sim (\text{SF}\oplus \text{OF})$ holds, and here $\text{SF}\oplus \text{OF}=1$, so jge is not taken. Control falls through to the then-branch, which computes %rax = y - x = 8 - 3 = 5, the correct $|3-8|$. Now call absdiff(8, 3): the compare sets the flags from $8-3=5$, positive, so SF = 0, OF = 0, jge is taken, and control jumps to .Lelse to compute %rax = x - y = 8 - 3 = 5. Same answer, opposite path — the inverted jge routes the fall-through to the then-body and the taken branch to the else-body, which is the shape the graph below draws.

The control-flow graph makes the shape explicit: one diamond test with two outgoing edges that reconverge at the return.

Three ways to compile a loop

Compilers never translate a while or for literally. Every loop is reshaped so the back-edge test sits at the bottom, executing one conditional jump per iteration instead of the two a top-tested loop would need. All three shapes below share this do-while core — a body followed by a bottom test — and differ only in how they handle entry, since a while or for may run its body zero times but a do-while runs it at least once.

do-while: test at the bottom

C's own do { body } while (test) is the direct case: run the body, then test at the bottom. One conditional jump per iteration, no entry code at all.

long sum_to(long n) {            // assume n >= 1
    long s = 0, i = 1;
    do { s += i; i++; } while (i <= n);
    return s;
}

sum_to:
        movl    $0, %eax          # s = 0
        movl    $1, %edx          # i = 1
.Lloop:
        addq    %rdx, %rax        # s += i
        addq    $1, %rdx          # i++
        cmpq    %rdi, %rdx        # compare i, n
        jle     .Lloop            # if i <= n, loop again
        ret                       # return s in %rax

jump-to-middle: jump to the test first

A while or for must test before the first body. The jump-to-middle form does this with an unconditional jmp to the bottom test on entry, then falls into the body only when the test passes. This is what gcc -Og emits. The factorial for (i = 2; i <= n; i++) compiles to it:

long fact(long n) {
    long result = 1;
    for (long i = 2; i <= n; i++)
        result *= i;
    return result;
}

fact:
        movl    $1, %eax          # result = 1
        movl    $2, %edx          # i = 2
        jmp     .Ltest            # jump to the test first
.Lloop:
        imulq   %rdx, %rax        # result *= i
        addq    $1, %rdx          # i++
.Ltest:
        cmpq    %rdi, %rdx        # compare i, n  (flags from i - n)
        jle     .Lloop            # if i <= n, loop again
        ret                       # return result in %rax

The entry jmp .Ltest costs one fetch, and the branch predictor handles it trivially. If n < 2 the body never runs, exactly as C requires.

guarded-do: guard, then do-while

At -O1 and above, gcc prefers the guarded-do shape: an initial conditional test that jumps past the entire loop when it fails, followed by a plain do-while body. This turns the entry jmp into a conditional branch but leaves the steady state a tight bottom-tested loop, which the predictor learns quickly.

    if (!test) goto done;     // entry guard: skip the loop entirely
loop:
    body;
    if (test) goto loop;      // bottom test, the back edge
done:

When the compiler can prove the loop runs at least once, it omits the guard and recovers the bare do-while.

Whichever shape the compiler chose, the recognition rule is the same: find the conditional back-edge jump and the test block it targets, and you have found the loop.

Conditional moves instead of branches

A branch is not the only way to compile an if. When both arms are cheap, gcc can emit branchless code: compute both results, then use a conditional move cmov to keep the right one. A cmov reads the same flags a jump would, but instead of redirecting control it copies its source to its destination only when the predicate holds, and does nothing otherwise.²

long absdiff(long x, long y) {
    return (x < y) ? y - x : x - y;
}

absdiff:
        movq    %rsi, %rax        # rax = y
        subq    %rdi, %rax        # rax = y - x   (the then-value)
        movq    %rdi, %rdx        # rdx = x
        subq    %rsi, %rdx        # rdx = x - y   (the else-value)
        cmpq    %rsi, %rdi        # compare x, y
        cmovge  %rdx, %rax        # if x >= y, rax = x - y
        ret                       # rax holds the selected value

Both differences are computed unconditionally, then cmovge overwrites %rax with the else-value only when x >= y. There is no branch to mispredict.

The compiler weighs a real cost. A cmov version always does both arms' work, so when the arms are expensive, or one arm must not run at all (a load that might fault, a division by a possibly-zero divisor, a side effect), branching is required or cheaper. gcc reaches for cmov when both arms are short and the branch is hard to predict — a data-dependent condition with no regular pattern — because there a mispredict costs more than the wasted arm. When the branch is predictable, the ordinary compare-and-branch wins, since the predictor makes it nearly free and only one arm runs.

Switch and jump tables

A switch over a dense range of integer cases compiles to a jump table: an array of code addresses, indexed by the switch value, so that all cases dispatch in constant time with a single indirect jump rather than a chain of comparisons.³

        # switch(n) with cases 0..3, n in %rdi
        cmpq    $3, %rdi          # range check the index
        ja      .Ldefault         # unsigned: catches n<0 and n>3 at once
        jmp     *.Ltab(,%rdi,8)   # indirect jump through table[n]
.Ltab:                            # in the read-only .rodata section
        .quad   .Lcase0
        .quad   .Lcase1
        .quad   .Lcase2
        .quad   .Lcase3

The single ja after cmpq $3 range-checks both ends at once: treating the index as unsigned makes any negative n wrap to a huge value above 3, so one unsigned-above test rejects n < 0 and n > 3 together. The indirect jmp *.Ltab(,%rdi,8) then uses the scaled-index addressing mode from data movement — each table entry is an 8-byte address, so the scale is 8 — to fetch the target.

Trace the dispatch for n = 2. The table .Ltab sits at some address, say 0x4000, and holds four 8-byte entries. The range check cmpq $3, %rdi / ja .Ldefault passes, since $2\le 3$. Then jmp *.Ltab(,%rdi,8) computes the operand address $0x4000+2\cdot 8=0x4010$, loads the 8-byte value stored there — the address of .Lcase2 — and jumps to it. No comparisons per case, no chain: one scaled load and one indirect jump land on the third entry regardless of how many cases the switch has. A ten-case or hundred-case switch dispatches in the same two instructions, which is the whole reason a compiler prefers a table once the cases are dense.

A sparse or small switch is compiled instead as a cascade of cmp/je tests, the if/else pattern repeated. The compiler chooses a table only when the case values are dense enough that the array is not mostly wasted.

Branches and the pipeline

CS:APP explains how conditional jumps and cmov compile; the reason the choice matters lives one level down, in the pipelined microarchitecture the machine-level chapter only sketches. A modern x86 core fetches and decodes instructions many stages ahead of the one it is executing, so when it reaches a conditional jump it cannot yet know whether the branch is taken — the flags may not be computed. Rather than stall, it predicts the outcome and speculatively runs down the predicted path. A correct prediction costs nothing; a misprediction discards all that speculative work and refills the pipeline, a penalty of roughly 15 to 20 cycles on current hardware. That penalty is precisely why cmov can win: a branchless sequence has nothing to mispredict, so for a data-dependent, unpredictable condition it beats a branch even though it always computes both arms.⁴

The same reasoning explains a compiler flag worth knowing: profile-guided optimization (PGO). If you compile once with instrumentation, run the program on representative input to record which way each branch actually went, then recompile feeding that profile back in, the compiler lays out the hot path as the fall-through, converts predictable branches away from cmov, and leaves cold paths out of line. The layout the earlier sections call the compiler inverts the test so the fall-through is the common case becomes data-driven rather than a fixed heuristic. This closes the loop between the control-flow shapes here and the branch-prediction hardware that runs them, and it is the standard treatment in the Intel optimization literature.⁵