--- title: Control Flow module: Machine-Level Programming moduleNumber: 1 lessonNumber: 4 order: 104 summary: > How a flat instruction stream realizes branches and loops. The conditional jumps read the condition-code flags; set instructions turn flags into a 0/1 byte. We translate if/else into the standard compare-and-branch pattern, while/for loops into the guarded-do form, and dense switches into jump tables that index a target directly. topics: [Machine-Level Programming] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §3.6 Control (Jump Instructions, Conditionals, Loops, Switch Statements)" --- 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](/computer-architecture/machine-level-x86-64/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. $$ % caption: A jump rewrites the program counter. Without a jump %rip advances to the % caption: next instruction; a taken jump overwrites %rip with the target address, % caption: so the processor fetches from the target instead of falling through. \begin{tikzpicture}[font=\footnotesize, >=stealth, ins/.style={draw, minimum width=26mm, minimum height=6mm, inner sep=2pt, align=left}] \definecolor{acc}{HTML}{2348F2} \node[ins] (i0) at (0,1.2) {$\mathtt{cmpq\ \%rsi,\%rdi}$}; \node[ins, draw=acc, thick] (i1) at (0,0.5) {$\mathtt{jl\ .Ltarget}$}; \node[ins] (i2) at (0,-0.2) {$\mathtt{addq\ {\char36}1,\%rax}$}; \node[ins] (i3) at (0,-1.6) {$\mathtt{\ .Ltarget:\ ...}$}; % fall-through, two-line label clear of the box edge and the taken arrow \draw[->, thick] (i1.south) -- (i2.north); \node[right, font=\scriptsize, align=left] at (1.55,-0.15) {not taken:\\fall through}; % taken jump rewrites rip; label sits to the right of the vertical run \draw[->, very thick, acc] (i1.east) -- (4.2,0.5) -- (4.2,-1.6) -- (i3.east); \node[right, font=\scriptsize, text=acc, align=left] at (4.35,-0.55) {taken:\\\%rip = target}; \end{tikzpicture} $$ ## 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.[^jumps] | Jump | Taken when | Flags read | | --- | --- | --- | | `je` / `jz` | equal / zero | ZF | | `jne` / `jnz` | not equal | $\sim$ZF | | `js` | negative | SF | | `jg` | greater (signed) | $\sim$(SF $\oplus$ OF) $\&\ \sim$ZF | | `jge` | $\geq$ (signed) | $\sim$(SF $\oplus$ OF) | | `jl` | less (signed) | SF $\oplus$ OF | | `jle` | $\leq$ (signed) | (SF $\oplus$ OF) $\vert$ ZF | | `ja` | above (unsigned) | $\sim$CF $\&\ \sim$ZF | | `jb` | below (unsigned) | CF | 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. ```asm [setcc.s] # 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 ``` $$ % caption: A set instruction reads the same flags a jump would and deposits a single % caption: byte: 1 if the predicate holds, 0 if not. Here setg writes %al, then a % caption: zero-extend widens it to a clean int. \begin{tikzpicture}[font=\footnotesize, >=stealth, flg/.style={draw, minimum width=8mm, minimum height=7mm, inner sep=0pt, font=\scriptsize}, box/.style={draw, minimum width=14mm, minimum height=8mm, align=center}] \definecolor{acc}{HTML}{2348F2} \node[flg, fill=acc!8] (zf) at (0,0.55) {ZF}; \node[flg, fill=acc!8] (sf) at (0,-0.4) {SF}; \node[flg, fill=acc!8] (of) at (1.1,0.55) {OF}; \node[font=\footnotesize, align=center] at (0.55,-1.25) {f\/lags from \texttt{cmp}}; \node[box, draw=acc, thick] (set) at (4.0,0.05) {$\mathtt{setg}$}; \draw[->, thick] (1.9,0.05) -- (set.west); \node[box, fill=acc!8] (al) at (7.6,0.05) {$\mathtt{\%al}=\mathtt{1}$}; \draw[->, thick, acc] (set.east) -- (al.west) node[midway, above, font=\scriptsize] {1 if $>$, else 0}; \end{tikzpicture} $$ 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. ```c [absdiff.c] long absdiff(long x, long y) { if (x < y) return y - x; else return x - y; } ``` ```asm [absdiff.s] 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. $$ % caption: CFG for absdiff. The test x=stealth, blk/.style={draw, minimum width=20mm, minimum height=8mm, align=center}, dec/.style={draw, diamond, aspect=2, minimum width=18mm, inner sep=1pt, align=center}] \definecolor{acc}{HTML}{2348F2} \node[dec] (t) at (0,0) {$x < y$ ?}; \node[blk] (then) at (-2.6,-2.0) {$y$ - $x$}; \node[blk] (else) at (2.6,-2.0) {$x$ - $y$}; \node[blk, draw=acc, thick] (ret) at (0,-4.0) {return}; \draw[->, thick] (t.west) -- node[above left, font=\scriptsize] {yes} (then.north); \draw[->, thick] (t.east) -- node[above right, font=\scriptsize] {no} (else.north); \draw[->, thick] (then.south) -- (ret.west); \draw[->, thick] (else.south) -- (ret.east); \end{tikzpicture} $$ ## 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. $$ % caption: The three loop shapes, differing only at entry. do-while falls straight % caption: into the body; jump-to-middle jumps to the bottom test first; guarded-do % caption: takes a conditional guard that skips the whole loop. All three share the % caption: same body-then-bottom-test core. \begin{tikzpicture}[font=\footnotesize, >=stealth, blk/.style={draw, minimum width=15mm, minimum height=6mm, align=center}, dec/.style={draw, diamond, aspect=2.2, minimum width=15mm, inner sep=0pt, align=center}] \definecolor{acc}{HTML}{2348F2} % -- do-while (left) -- \node[font=\scriptsize] at (0,1.7) {do-while}; \node[blk] (b1) at (0,0.7) {body}; \node[dec] (t1) at (0,-0.9) {test}; \draw[->, thick] (0,1.4) -- (b1.north); \draw[->, thick] (b1.south) -- (t1.north); \draw[->, thick] (t1.west) .. controls (-1.5,0.0) .. (b1.west) node[midway, left, font=\scriptsize] {yes}; % -- jump-to-middle (center) -- \node[font=\scriptsize] at (4.2,1.7) {jump-to-middle}; \node[blk] (b2) at (4.2,0.7) {body}; \node[dec] (t2) at (4.2,-0.9) {test}; \draw[->, thick] (5.9,0.9) -- (5.9,-0.9) -- (t2.east); \node[right, font=\scriptsize] at (5.9,0.1) {jmp}; \draw[->, thick] (b2.south) -- (t2.north); \draw[->, thick] (t2.west) .. controls (2.7,0.0) .. (b2.west) node[midway, left, font=\scriptsize] {yes}; % -- guarded-do (right) -- \node[font=\scriptsize] at (8.4,1.7) {guarded-do}; \node[dec] (g3) at (8.4,1.0) {guard}; \node[blk] (b3) at (8.4,-0.1) {body}; \node[dec] (t3) at (8.4,-1.6) {test}; \draw[->, thick] (g3.south) -- (b3.north); \draw[->, thick] (b3.south) -- (t3.north); \draw[->, thick] (t3.west) .. controls (6.9,-0.9) .. (b3.west) node[midway, left, font=\scriptsize] {yes}; \draw[->, thick] (g3.east) -- (9.9,1.0) node[right, font=\scriptsize] {skip}; \end{tikzpicture} $$ ### 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. ```c [dowhile.c] long sum_to(long n) { // assume n >= 1 long s = 0, i = 1; do { s += i; i++; } while (i <= n); return s; } ``` ```asm [dowhile.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: ```c [fact.c] long fact(long n) { long result = 1; for (long i = 2; i <= n; i++) result *= i; return result; } ``` ```asm [fact.s] 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. ```c [loop-shape.c] 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. $$ % caption: CFG of the factorial loop as jump-to-middle. Entry jumps to the test; % caption: the body falls into the test; the back edge re-enters the body while % caption: i <= n holds, and the false exit reaches the return. \begin{tikzpicture}[font=\footnotesize, >=stealth, blk/.style={draw, minimum width=22mm, minimum height=8mm, align=center}, dec/.style={draw, diamond, aspect=2, minimum width=20mm, inner sep=1pt, align=center}] \definecolor{acc}{HTML}{2348F2} \node[blk] (body) at (0,0) {body}; \node[dec] (test) at (0,-2.0) {$i \le n$ ?}; \node[blk, draw=acc, thick] (done) at (3.6,-2.0) {return}; \node[font=\footnotesize] (entry) at (-3.6,-2.0) {entry \texttt{jmp}}; \draw[->, thick] (entry) -- (test.west); \draw[->, thick] (body.south) -- (test.north); \draw[->, thick] (test.east) -- node[above, font=\scriptsize] {no} (done.west); % back edge routed around to the left, not through the boxes \draw[->, thick] (test.west) .. controls (-2.2,-1.0) .. (body.west) node[midway, left, font=\scriptsize] {yes}; \end{tikzpicture} $$ 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.[^cmov] ```c [absdiff.c] long absdiff(long x, long y) { return (x < y) ? y - x : x - y; } ``` ```asm [absdiff-cmov.s] 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. $$ % caption: A branch versus a conditional move. The branch picks one path and skips % caption: the other, so a wrong prediction wastes work; cmov computes both values % caption: and selects with the flags, a straight-line path with no misprediction. \begin{tikzpicture}[font=\footnotesize, >=stealth, blk/.style={draw, minimum width=20mm, minimum height=7mm, align=center}, dec/.style={draw, diamond, aspect=2, minimum width=18mm, inner sep=1pt, align=center}] \definecolor{acc}{HTML}{2348F2} % branch side \node[font=\scriptsize] at (-2.4,1.5) {branch}; \node[dec] (bt) at (-2.4,0.6) {test}; \node[blk] (bthen) at (-3.8,-0.9) {then}; \node[blk] (belse) at (-1.0,-0.9) {else}; \draw[->, thick] (bt.west) -- (bthen.north); \draw[->, thick] (bt.east) -- (belse.north); % cmov side \node[font=\scriptsize] at (3.2,1.5) {conditional move}; \node[blk] (cthen) at (2.0,0.6) {compute then}; \node[blk] (celse) at (2.0,-0.4) {compute else}; \node[blk, draw=acc, thick] (csel) at (4.9,0.1) {\texttt{cmov} selects}; \draw[->, thick] (cthen.east) -- (csel.west); \draw[->, thick] (celse.east) -- (csel.west); \node[font=\scriptsize, text=acc] at (3.2,-1.15) {no branch to mispredict}; \end{tikzpicture} $$ 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] ```asm [switch.s] # 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](/computer-architecture/machine-level-x86-64/data-movement) — each table entry is an 8-byte address, so the scale is 8 — to fetch the target. $$ % caption: A jump table. The switch value indexes an array of 8-byte target % caption: addresses; one indirect jump dispatches to the matching case in O(1). \begin{tikzpicture}[font=\footnotesize, >=stealth, cell/.style={draw, minimum width=20mm, minimum height=7mm, inner sep=0pt}, case/.style={draw, minimum width=18mm, minimum height=7mm, align=center}] \definecolor{acc}{HTML}{2348F2} % index source \node[cell, draw=acc, fill=acc!8] (idx) at (0,0) {$\mathtt{\%rdi} = 2$}; % the table \node[cell] (t0) at (4,1.5) {\texttt{.Lcase0}}; \node[cell] (t1) at (4,0.75) {\texttt{.Lcase1}}; \node[cell, draw=acc] (t2) at (4,0.0) {\texttt{.Lcase2}}; \node[cell] (t3) at (4,-0.75){\texttt{.Lcase3}}; \node[font=\scriptsize] at (4,2.3) {jump table}; % index arrow into the selected entry, edge-to-edge \draw[->, thick, acc] (idx.east) -- (t2.west) node[midway, above, font=\scriptsize] {index x 8}; % dispatch to target code block \node[case, draw=acc, thick] (code) at (8,0.0) {case 2 code}; \draw[->, thick, acc] (t2.east) -- (code.west) node[midway, above, font=\footnotesize] {\texttt{jmp *}}; \end{tikzpicture} $$ 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 $\mathtt{0x4000} + 2 \cdot 8 = \mathtt{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.[^predict] 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.[^pgo] > **Takeaway.** Control flow is `jmp` rewriting `%rip`. Conditional jumps read the > flags `cmp`/`test` set, with **signed** (`jg`/`jl`) and **unsigned** (`ja`/`jb`) > variants reading different flags; `set` instructions turn a flag predicate into a > 0/1 byte. `if/else` becomes invert-test-and-branch, or a branchless `cmov` when > the arms are cheap and the branch hard to predict. Loops become a do-while core > reached by one of three entry shapes (do-while, jump-to-middle, guarded-do); dense > `switch` becomes an indexed jump table. [^jumps]: **Bryant & O'Hallaron**, _CS:APP_, §3.6.1–3.6.4 — Jump instructions and their encodings; the conditional-jump suffixes and the flag combinations each reads for signed versus unsigned comparison. [^cmov]: **Bryant & O'Hallaron**, _CS:APP_, §3.6.6 — Implementing Conditional Branches with Conditional Moves: `cmov` computes both arms and selects on the flags, worthwhile when the branch is unpredictable but not when an arm is expensive or unsafe to execute. [^switch]: **Bryant & O'Hallaron**, _CS:APP_, §3.6.8 — Switch Statements: dense case ranges compile to a jump table indexed by the switch value with a single range check and indirect jump. [^predict]: **Hennessy & Patterson**, _Computer Architecture: A Quantitative Approach_, 6th ed. (2017), §3.3 and §C.2 — branch prediction, speculative execution, and the pipeline-refill penalty of a misprediction that makes branchless code (`cmov`) preferable for unpredictable branches. [^pgo]: **Intel**, _Intel 64 and IA-32 Architectures Optimization Reference Manual_ (2023), §3.4 — branch-prediction behavior and the use of profile-guided optimization to lay out hot paths as fall-through and steer the choice between branches and conditional moves.