Part ofSystems Programming Companion, week 4
Control Flow in Machine Code
You write if, else, for, while, switch. The CPU has none of those. Its entire control-flow vocabulary boils down to a single primitive: the conditional jump. Every C construct above compiles into comparisons and jumps. Once you see the mapping, you'll know why some patterns run faster than others and how the branch predictor shapes the speed of your code.
How if/else Becomes Conditional Jumps
Consider a simple conditional:
int abs_val(int x) { if (x < 0) { return -x; } else { return x; }}Compiled at -O0:
abs_val: push rbp mov rbp, rsp mov DWORD PTR [rbp-4], edi ; Store x cmp DWORD PTR [rbp-4], 0 ; Compare x with 0 jge .L2 ; Jump to .L2 if x >= 0 (skip the if-body) mov eax, DWORD PTR [rbp-4] ; Load x neg eax ; eax = -x jmp .L3 ; Jump past the else-body.L2: mov eax, DWORD PTR [rbp-4] ; Load x (this is the else-body).L3: pop rbp retThe key instructions:
cmp- Subtracts the second operand from the first WITHOUT storing the result. It only sets CPU flags (Zero Flag, Sign Flag, Overflow Flag, Carry Flag).jge(Jump if Greater or Equal) - Checks the flags and jumps if the result of the comparison was >= 0.jmp- Unconditional jump. Always taken.
Shape: compare, conditionally jump past the if-body, run the else-body, fall through. The jmp .L3 at the tail of the if-body hops over the else block. Every if/else you write produces this pattern.
Common Conditional Jump Instructions
The jumps you'll bump into most:
| Instruction | Meaning | Flags Checked |
|---|---|---|
je / jz | Jump if Equal / Zero | ZF=1 |
jne / jnz | Jump if Not Equal / Not Zero | ZF=0 |
jg | Jump if Greater (signed) | ZF=0 and SF=OF |
jge | Jump if Greater or Equal (signed) | SF=OF |
jl | Jump if Less (signed) | SF!=OF |
jle | Jump if Less or Equal (signed) | SF!=OF or ZF=1 |
ja | Jump if Above (unsigned) | CF=0 and ZF=0 |
jae / jnb | Jump if Above or Equal (unsigned) | CF=0 |
jb | Jump if Below (unsigned) | CF=1 |
jbe | Jump if Below or Equal (unsigned) | CF=1 or ZF=1 |
js / jns | Jump if Sign / Not Sign | SF=1 / SF=0 |
Signed vs unsigned really matters here. jg/jl lean on the Sign and Overflow flags for signed comparisons; ja/jb watch the Carry flag for unsigned ones. Write if (i >= n) with signed ints and the compiler reaches for jge (or its opposite, jl, to skip the body). Make them size_t and you'll see jae or jb instead. Don't test this by comparing an unsigned value with 0, though: x >= 0 is always true for an unsigned x, so the compiler simply deletes the comparison.
Loops as Backward Jumps
Strip a for loop down and what's left is a conditional jump pointing backwards:
int sum(int *arr, int n) { int total = 0; for (int i = 0; i < n; i++) { total += arr[i]; } return total;}sum: push rbp mov rbp, rsp mov QWORD PTR [rbp-24], rdi ; Store arr pointer mov DWORD PTR [rbp-28], esi ; Store n mov DWORD PTR [rbp-4], 0 ; total = 0 mov DWORD PTR [rbp-8], 0 ; i = 0 jmp .Lcond ; Jump to the condition check.Lbody: mov eax, DWORD PTR [rbp-8] ; Load i cdqe ; Sign-extend to 64 bits lea rdx, [0+rax*4] ; rdx = i * 4 (byte offset) mov rax, QWORD PTR [rbp-24] ; Load arr base pointer add rax, rdx ; rax = &arr[i] mov eax, DWORD PTR [rax] ; eax = arr[i] add DWORD PTR [rbp-4], eax ; total += arr[i] add DWORD PTR [rbp-8], 1 ; i++.Lcond: mov eax, DWORD PTR [rbp-8] ; Load i cmp eax, DWORD PTR [rbp-28] ; Compare i with n jl .Lbody ; If i < n, jump back to loop body mov eax, DWORD PTR [rbp-4] ; Load total into return register pop rbp retLoop shape:
- Jump to the condition check (
.Lcond) - Check the condition (
cmp+jl) - True? Jump backward to the body (
.Lbody) - False? Fall through past the loop
Disassemblers and decompilers draw this as a control-flow graph: straight-line runs of instructions (basic blocks) joined by jumps. Here's sum in that form. The only edge pointing back up the graph is the jl, and that one edge is the whole loop.
while compiles to the same thing. do...while is the odd cousin: it enters at the body instead of the condition, shaving one jump on the way in.
The CPU doesn't twiddle its thumbs waiting for a conditional jump to resolve. It guesses which way the branch will go and starts speculatively running instructions down the predicted path. For loops, the guess is almost always "take the backward jump and keep looping," which holds true every iteration but the last. That's why loops fly — the branch predictor wins nearly every coin flip.
Switch Statements: Jump Tables vs Chained Comparisons
A switch can come out of the compiler looking like one of two completely different beasts, depending on the cases.
Dense cases produce a jump table:
int day_type(int day) { switch (day) { case 0: return 1; // Sunday - weekend case 1: return 0; // Monday - weekday case 2: return 0; // Tuesday case 3: return 0; // Wednesday case 4: return 0; // Thursday case 5: return 0; // Friday case 6: return 1; // Saturday - weekend default: return -1; }}With optimisation, this becomes a jump table:
day_type: cmp edi, 6 ja .Ldefault ; If day > 6, go to default lea rax, [rip+.Ljumptable] ; Load address of jump table movsxd rdx, DWORD PTR [rax+rdi*4] ; Load offset from table add rax, rdx ; Compute target address jmp rax ; Jump to the right case
.Ljumptable: .long .Lcase0 - .Ljumptable .long .Lcase1 - .Ljumptable .long .Lcase2 - .Ljumptable ; ... one entry per caseA jump table is just an array of addresses. The CPU treats the switch value as the index, plucks out the matching address, and jumps. Constant time regardless of how many cases sit in the table.
Sparse cases produce chained comparisons:
int classify(int code) { switch (code) { case 100: return 1; case 200: return 2; case 500: return 3; case 1000: return 4; default: return 0; }}classify: cmp edi, 200 je .Lcase200 cmp edi, 500 je .Lcase500 cmp edi, 100 je .Lcase100 cmp edi, 1000 je .Lcase1000 xor eax, eax ; default: return 0 retSpread the cases far apart — 100, 200, 500, 1000 — and a jump table would waste preposterous amounts of memory on empty slots. The compiler bails out to a chain of comparisons, basically a string of if/else checks. With many cases, it'll sometimes order them by frequency or fall into a binary-search shape.
How the Compiler Optimizes Branches
A handful of control-flow tricks the compiler reaches for:
Conditional moves (avoiding branches entirely):
int max(int a, int b) { return a > b ? a : b;}At -O2:
max: cmp edi, esi mov eax, esi ; Assume b is the answer cmovg eax, edi ; If a > b, overwrite with a retcmovg (conditional move if greater) sidesteps the branch entirely. It reads both values and picks one based on the flags. No branch, no prediction, no misprediction penalty. The compiler reaches for this when both arms of a conditional are cheap to compute.
Branch-free boolean conversion:
int is_positive(int x) { return x > 0;}is_positive: xor eax, eax ; eax = 0 test edi, edi ; Set flags based on x setg al ; al = 1 if x > 0, else 0 retsetg writes 0 or 1 into a byte register based on flags. No jump required.
Loop unrolling:
for (int i = 0; i < 4; i++) { arr[i] = 0;}At -O2, the compiler removes the loop completely. You might expect four separate stores:
mov DWORD PTR [rdi], 0 mov DWORD PTR [rdi+4], 0 mov DWORD PTR [rdi+8], 0 mov DWORD PTR [rdi+12], 0Current GCC and Clang go one better and merge them into a single 16-byte SSE store:
xorps xmm0, xmm0 ; 16 zero bytes movups XMMWORD PTR [rdi], xmm0 ; arr[0..3] = 0 in one storeNo loop, no counter, no branch. For longer runs of zeroes they'll often just call memset. For bigger loops the compiler often partially unrolls — chewing through 4 iterations per pass instead of 1 — knocking branch instructions down by roughly 75%.
The Cost of Misprediction
When the predictor flubs it, the CPU has to:
- Throw away every speculatively executed instruction (a full pipeline flush)
- Restart fetching from the correct path
On modern hardware that's roughly 15-20 cycles down the drain. For code with unpredictable branches — say, processing genuinely random data — that cost can swallow the bulk of execution time.
// Predictable branch - fastfor (int i = 0; i < n; i++) { if (arr[i] > 0) sum += arr[i]; // Usually true for positive data}
// Unpredictable branch - slowfor (int i = 0; i < n; i++) { if (arr[i] > threshold) sum += arr[i]; // 50/50 for random data}For the unpredictable case, the compiler at -O2 will sometimes lean on cmov to dodge the branch altogether:
; Branchless version of the unpredictable case mov eax, DWORD PTR [rdi+rcx*4] ; Load arr[i] cmp eax, edx ; Compare with threshold cmovle eax, r8d ; If <= threshold, replace with 0 add esi, eax ; sum += (arr[i] or 0)Time it. This runs the same loop over the same 32,768 values twice, first shuffled and then sorted:
Sorting changes nothing about the work, only how predictable the if is, yet the sorted pass usually finishes in a fraction of the time. Your exact timings and ratio will vary. The runner compiles with no flags, so you're at -O0 and the branch stays a branch. Build it yourself with gcc -O2 and the gap can shrink to nothing, because the compiler may swap the branch for cmov (or vectorise the loop) and there's nothing left to mispredict.
Reading control flow at machine level explains things you'd otherwise just have to take on faith: why sorted data races through a loop quicker than random data, why a small lookup table sometimes beats a chain of conditionals, why the compiler twists your carefully written logic into something almost unrecognisable in assembly. The compiler is tuning for how the silicon really behaves.