A switch statement is not a branching instruction. It is a small optimization problem that you hand to the compiler: here is a set of integer values, here is what each value should do, now figure out the cheapest machine code that respects the semantics. GCC treats that problem seriously enough to maintain three distinct lowering strategies, a dynamic programming pass to partition your case labels, and a profitability heuristic that is counted in comparisons rather than in case labels. If you write interpreters, parsers, protocol handlers, or any hot dispatch loop, the difference between those three outcomes is the difference between one indirect jump and a walk down a binary tree.
This article walks through what GCC actually emits for each shape of switch, why the heuristic fires when it does, and how to check which machine your own switch became. The examples are C compiled with -O3, and everything described here lives in one pass in the GCC source tree: pass_lower_switch in tree-switch-conversion.cc, which drives analyze_switch_statement.
The three machines GCC can build
Given a switch, GCC has three realistic outputs.
The first is a jump table: bounds-check the input, subtract the lowest case value, and index into an array of code pointers. One indirect jump, constant time, and a table whose size is proportional to the range of values rather than the number of cases.
The second is a bitset test. When several case labels all lead to the same destination and the values fit in a machine word, GCC can compress the entire switch into a constant integer, a bt (bit test) instruction, and a single conditional jump. No table in memory, no indirect branch at all.
The third is a binary decision tree of comparisons, which is the fallback when neither of the first two pays off. This tree is not balanced by value; it is balanced by probability, so profile data changes its shape.
Which machine you get is decided per cluster of case labels, not per switch. A single switch can be split: GCC can peel off an outlier into a plain comparison, turn the dense core into a jump table, and leave the rest to the tree. Understanding the heuristics means understanding what the compiler is counting.
Jump tables and the constant-offset trick
Start with the textbook case: five case labels with consecutive values, each calling a different function.
int compact(int x, int val) {
switch (x) {
case 0: return f0(val);
case 1: return f1(val);
case 2: return f2(val);
case 3: return f3(val);
case 4: return f4(val);
default: return 0;
}
}
GCC emits exactly what you would write by hand with a function-pointer array: compare against 4, bail to the default if above, otherwise index the table.
compact:
mov eax, edi
mov edi, esi
cmp eax, 4
ja .L2
jmp [QWORD PTR .L4[0+rax*8]]
.L4:
.quad .L8
.quad .L7
.quad .L6
.quad .L5
.quad .L3
Two details are worth noting. First, the default case is handled by the unsigned ja bounds check, so negative inputs fall through to the default for free. Second, the compiler spots a constant offset. If the cases run from 97 to 101 instead of 0 to 4, the only change is a leading lea eax, [rdi-97] to rebase the index. The table stays five entries long. You do not need to normalize your enum to zero to get the dense table.
This is the outcome most programmers assume they always get. The interesting question is when GCC refuses to build it.
The heuristic counts comparisons, not case labels
Intuition says jump tables are about density: the sparser the values, the more table entries get wasted on the default label. That intuition is right, but the quantity GCC measures is not what most people guess.
Experimentally, the threshold is around eight table entries per unit of work. The subtlety is in the unit. Take a switch with five cases at values 0, 8, 16, 24, 40. The range is 41 entries for five labels, a ratio above eight, so GCC emits a comparison tree instead. Drop to values 0, 7, 14, 21, 34 and the range is 35, the ratio drops below eight, and the jump table comes back, padded with default-label entries in the gaps.
Now the twist. Consider twenty case labels arranged in five contiguous runs, each run of four consecutive values jumping to the same function:
int blocks_2(int x, int val) {
switch (x) {
case 0: case 1: case 2: case 3:
return f1(val);
case 21: case 22: case 23: case 24:
return f2(val);
/* ... three more blocks ... */
default: return 0;
}
}
The values span 0 to 87, so a jump table would need 88 entries. The naive heuristic says 88 is less than 20 labels times 8, so the table should win. It does not. GCC emits comparisons, because each contiguous run has already been merged into a single range in the Gimple intermediate representation, with a low and a high value per label. A range takes two comparisons to test, not four. The whole switch costs 10 comparisons, and 10 times 8 is 80, which is less than 88. The table is unprofitable once you count what the tree would actually cost.
So the real rule is: a jump table cluster is worthwhile when its entry count stays under roughly eight times the number of comparisons the alternative would need. Case labels that collapse into ranges make the comparison tree look cheap, which makes the jump table harder to justify. If you want the table, contiguous runs of equal destination are working against you.
When your switch becomes a single bt instruction
The strangest lowering is the bitset. Take a switch whose cases all share one destination, say classifying characters:
int bittest(int x, int val) {
switch (x) {
case '0': case '2': case '4':
case '5': case '7': case '9':
case 'A': case 'C': case 'E':
return f1(x);
default: return 0;
}
}
GCC compiles this without a single cmp against the case values and without a table:
bittest:
lea eax, [rdi-48]
cmp eax, 21
ja .L1
mov edx, 2753205
bt rdx, rax
jc .L7
.L1:
xor eax, eax
ret
.L7:
jmp f1
The constant 2753205 is the entire switch, folded into one integer. Rebase the input by 48 (the ASCII value of '0'), bounds-check against 21, then use the x86 bt instruction to test bit number rax of that constant. Each set bit corresponds to one case label: bits 0, 2, 4, 5, 7, 9 for the digits and 17, 19, 21 for the letters 'A', 'C', 'E' after the subtraction. One load, one bit test, one conditional jump.
This lowering has hard prerequisites: every label in the cluster must jump to the same destination, and the values must fit within a word after rebasing. When several groups of labels each share a destination, GCC faces a partitioning problem: which labels go into which bitset to minimize the number of bitsets emitted. That is solved with an honest dynamic programming pass over the clusters, after which each candidate bitset still has to pass a profitability check before it replaces the original comparisons. If the bitset fails the check, the labels fall back into the pool that feeds the jump-table analysis.
The decision tree is balanced by probability, not by value
Whatever survives the bitset and jump-table passes becomes a binary tree of comparisons. The natural way to build that tree is to split the value range in half at each node. GCC does something different: it splits so that both halves carry equal probability.
Each cluster enters the pass with a profile_probability. By default the probability is uniform across labels, but it responds to profile-guided optimization data, and you can set it by hand with __builtin_expect_with_probability. The balancing routine walks the case list accumulating probability until it crosses half the total, splits there, and recurses on both halves.
The practical consequence is that the hot case in your switch should be marked hot. A probability-balanced tree puts the likely destination at depth one or two, while a value-balanced tree can bury it at depth five just because of where its integer happens to sit. If your dispatch loop has a dominant opcode, that annotation is worth real branch-mispredictions, and it costs one line.
What GCC will not do for you
The pass is clever, but it is locally clever. Recall the sparse switch with cases at 0, 8, 16, 24, and 40. A human sees immediately that dividing the input by eight yields the dense values 0 through 5, at which point a six-entry jump table is obvious. GCC does not find this. There is no transform that divides the switch value to shrink the table range, even when the division is exact for every case label.
That gap is a lever you can pull yourself. If you control the values being dispatched on, choose them to be dense. If you do not control them, but they are affine, do the rescaling in code before the switch. The compiler's cost model only sees the values it is given; normalization is your job. The same argument applies to the comparison-counting heuristic from earlier: merging case labels into shared destinations changes what the compiler counts, which changes what it emits. You are not writing a switch, you are writing input to an optimizer, and the optimizer's arithmetic is knowable.
How to check which machine you got
You do not need to guess. Compile with -O3 -S or run objdump -d on the binary and look at the function. The three outcomes have distinct fingerprints. A jump table shows a bounds check followed by an indirect jump through a table of .quad entries. A bitset shows a mov of an unexplained constant immediately followed by bt and a carry-flag jump. A decision tree shows a ladder of cmp instructions whose order, if you have profile data, follows probability rather than numeric order.
When the output is not what you wanted, the fixes follow directly from the heuristics: make the values dense or dense after a rebasing you write yourself, merge destinations where the semantics allow it to trigger range collapsing, annotate the hot destination so the tree balances around it, or replace the switch with an explicit table of function pointers when you know better than the cost model. None of these require guessing at the compiler's internals; each one moves a number that the pass actually reads.
The contract you actually signed
The switch statement reads like a control-flow primitive, but it behaves like a declarative constraint. You describe a mapping from integers to actions, and GCC's pass_lower_switch chooses between a memory-resident table, a single bit test, and a probability-shaped tree, cluster by cluster, using heuristics that count comparisons and entries rather than labels. The eight-to-one density rule, the range-collapsing that feeds it, the dynamic programming behind bitset partitioning, and the probability-balanced tree are all visible in the source and predictable from your case values.
Once you know the machinery, reading the disassembly stops being an audit and starts being a confirmation. And when the confirmation fails, you know exactly which input to change.
Primary source: xoranth's "Switch lowering in GCC" walkthrough and the GCC source file gcc/tree-switch-conversion.cc, which contains pass_lower_switch, bit_test_cluster::find_bit_tests, jump_table_cluster::can_be_handled, and switch_decision_tree::balance_case_nodes.
Originally published on Dispatch.
Top comments (0)