Lesson 11.3 — Switch lowering: jump tables, binary search, bit tests, and LLVM's `switch`¶

Techniques: jump tables — one range check and an indirect jump through a table indexed by the value (Sale 1981; Bernstein 1985); binary search trees of comparisons over the sorted cases (Hennessy & Mendelsohn 1982; Bernstein 1985); bit tests — one shift and one mask test per destination when the cases fit in a machine word (LLVM, GCC); LLVM's switch instruction plus back-end lowering, which partitions the cases into clusters of each kind (Kannan & Proebsting 1994) and searches over the clusters · Pebble implements: PIR's switch terminator becomes an LLVM switch in the code generator (E5); all four strategies in the comparison lab (labs/ch11-lowering, part B) · Prerequisites: Lesson 11.2 (branch costs) · Time: 4–5 hours

A switch (C's switch, Rust's match on integers, PIR's switch terminator) selects one of several destinations by the value of an integer. Pebble's surface language has no switch, but PIR does (pir-spec §11) — a Rust front end lowers match to it (Ch 24) — and the shared back end (E5) must compile it. The question is how: $n$ comparisons in a row cost $O(n)$ per dispatch; the alternatives trade table space or word-sized masks for $O(1)$ or $O(\log n)$ dispatch. This lesson uses three running switches, all measured in the lab and compiled by Clang and GCC in §7:

name	cases (value → destination)	what LLVM picks
`chars`	9, 10, 13, 32 → A (space); 48…57 → B (digit); 43, 45 → C (sign)	bit tests
`op`	0, 1 → A; 2, 3 → B; 4 → C; 6 → D	one jump table
`sparse`	3 → A, 70 → B, 911 → C, 1200 → D, 5000 → E	a binary tree

1. Problem and motivation¶

Jump tables¶

A table with one code address per value in $[\min, \max]$ turns dispatch into a bounds check and an indirect jump, whatever the number of cases. Pascal compilers used it for dense case statements; Sale discussed when a table is worth its space [Sal81], and Bernstein gave the classic heuristic of splitting a sparse switch into dense tables joined by comparisons [Ber85]. It is the fastest dispatch for dense switches, but its size is the range, not the number of cases, and an indirect branch is harder to predict than a conditional one. The lab's JumpTable builds it in IR with blockaddress constants and indirectbr.

Binary search trees¶

Sorting the case values and comparing against the median halves the candidates with each comparison, so a sparse switch of $n$ cases costs $O(\log n)$ comparisons and $O(n)$ code, independent of the range [HM82, Ber85]. It is the fallback when no dense range exists (sparse above), and LLVM uses it to combine the other kinds: its tree is built over clusters, not single values.

Bit tests¶

When all case values fit in a word ($\max - \min < 64$) and there are few destinations, the test "is $x$ one of the values going to $d$?" is one AND of $1 \ll (x - \min)$ with a precomputed mask. Three destinations with 16 values cost one range check and at most three tests: chars classifies characters this way in both Clang and GCC (§7). LLVM builds them in buildBitTests [LLVM-SwitchLowering]; GCC in its bit_test_cluster [GCC-SwitchConv].

LLVM's `switch` and back-end lowering¶

LLVM IR keeps a switch as one instruction until instruction selection, where SelectionDAGBuilder::visitSwitch partitions the sorted cases into clusters — ranges, jump tables and bit tests — and emits a balanced binary tree over the clusters [LLVM-SDB]. The partition into the fewest jump-table-dense pieces is Kannan and Proebsting's dynamic program [KP94]. A front end should therefore emit switch and let the back end choose; the lab's LLVMSwitch strategy is ten lines, and the lab measures how close each hand-written strategy gets to it. Pebble's code generator emits switch for PIR's terminator (FunctionLowering::emitTerminator).

2. Definitions and algorithms¶

Definition 11.3.1 (Switch, range, density, cluster)

A switch on an integer $x$ of $w$ bits is a set of cases $\{(v_1, d_1), \dots, (v_n, d_n)\}$ with distinct values $v_i$ and destinations $d_i$, plus a default destination $d_0$ for every other value. With $\min$, $\max$ the least and greatest case value, the range is $R = \max - \min + 1$ and the density is $n / R$. A cluster is a set of cases with consecutive sorted values that is dispatched as a unit: a range cluster (consecutive values, one destination), a jump-table cluster or a bit-test cluster.

Lemma 11.3.2 (One unsigned comparison is a range check)

For $w$-bit two's-complement $x$ and case bounds $\min \le \max$, let $\mathit{idx} = (x - \min) \bmod 2^w$ (a wrapping sub). Then $\min \le x \le \max$ (signed) iff $\mathit{idx} \le \max - \min$ (unsigned).

Proof

Write values as mathematical integers with $-2^{w-1} \le x, \min, \max < 2^{w-1}$. If $\min \le x \le \max$, then $0 \le x - \min \le \max - \min \le 2^w - 1$, so the subtraction does not wrap and $\mathit{idx} = x - \min \le \max - \min$. If $x > \max$, then $\max - \min < x - \min \le 2^w - 1$, so again no wrap and $\mathit{idx} > \max - \min$. If $x < \min$, then $x - \min < 0$ and $\mathit{idx} = x - \min + 2^w$; since $x \ge -2^{w-1}$ and $\max < 2^{w-1}$, $\mathit{idx} - (\max - \min) = x + 2^w - \max > -2^{w-1} + 2^w - 2^{w-1} = 0$, so $\mathit{idx} > \max - \min$.

Algorithm 11.3.3 (Jump table)

Input: a switch with $n \ge 1$ cases, range $R$.
Output: code that jumps to the destination of $x$.
Precondition: $R$ is small enough to allocate (LLVM: density $\ge 10\,\%$; the lab: $R < 4096$).
Postcondition: control reaches $d_i$ iff $x = v_i$, and $d_0$ for every other $x$.
Invariant: $\mathit{table}[k]$ is the destination of $\min + k$ (or $d_0$) for $0 \le k < R$.

function JumpTable(cases, d0):
    table[0 .. R-1] ← d0
    for (v, d) in cases: table[v - min] ← d
    emit:  idx ← x - min                       # wrapping
           if idx >u R - 1: goto d0             # Lemma 11.3.2
           goto *table[idx]                     # indirectbr / jmpq *

Algorithm 11.3.4 (Balanced binary search)

Input: the cases sorted by value, $c_{lo} \dots c_{hi-1}$ ($hi - lo \ge 1$).
Output: a tree of comparisons whose leaves are equality tests.
Precondition: values are distinct and sorted.
Postcondition: control reaches $d_i$ iff $x = v_i$, else $d_0$; at most $\lceil \log_2 n \rceil + 1$ comparisons on any path (Theorem 11.3.5).
Invariant: when $\mathrm{Search}(lo, hi)$ runs, every case that $x$ could still equal is in $c_{lo} \dots c_{hi-1}$.

function Search(lo, hi):
    if hi - lo = 1:  emit  if x = v[lo]: goto d[lo] else goto d0
    else:
        mid ← lo + ⌊(hi - lo) / 2⌋
        emit  if x <s v[mid]: goto L else goto G
        in L: Search(lo, mid);   in G: Search(mid, hi)

Theorem 11.3.5 (Correctness and depth of the search)

Algorithm 11.3.4 dispatches every $x$ correctly and executes at most $\lceil \log_2 n \rceil + 1$ comparisons.

Proof

Correctness by induction on $hi - lo$, using the invariant. One case: the equality test is exact. More cases: if $x < v_{mid}$ then, the values being sorted, $x$ can only equal a case in $[lo, mid)$; otherwise only one in $[mid, hi)$; both halves are non-empty since $lo < mid < hi$, and the hypothesis applies. Depth: let $C(m)$ be the worst-case number of comparisons for $m$ cases: $C(1) = 1$ and $C(m) = 1 + C(\lceil m / 2 \rceil)$, the larger half having $\lceil m/2 \rceil$ cases. By induction $C(m) = \lceil \log_2 m \rceil + 1$: for $m \ge 2$, $\lceil \log_2 \lceil m/2 \rceil \rceil = \lceil \log_2 m \rceil - 1$.

Algorithm 11.3.6 (Bit tests)

Input: cases with $\max - \min < w$ and $D$ destinations (LLVM: $D \le 3$).
Output: a range check and $D$ mask tests.
Precondition: $\max - \min < w$ (the masks fit in a word).
Postcondition: control reaches $d$ iff $x$ is a case value of $d$, else $d_0$.
Invariant: bit $k$ of $\mathit{mask}_d$ is 1 iff $\min + k$ is a case of destination $d$.

function BitTests(cases, d0):
    for each destination d: mask_d ← Σ { 2^(v - min) : (v, d) ∈ cases }
    emit:  idx ← x - min;  if idx >u max - min: goto d0          # Lemma 11.3.2
           bit ← 1 << idx
           for d in destinations, most bits first:
               if bit & mask_d ≠ 0: goto d
           goto d0

Algorithm 11.3.7 (LLVM's switch lowering: clusters, then a tree)

Input: the cases of an LLVM switch on a 64-bit target, at -O1 or above.
Output: a sequence of clusters and a binary tree over them.
Precondition: no profile (equal case probabilities); not optimizing for size.
Postcondition: the clusters partition the cases in sorted order; each jump-table cluster has density $\ge 10\,\%$ and $\ge 4$ range clusters and does not suit bit tests; each bit-test cluster spans $\le 64$ values, $\le 3$ destinations and passes isSuitableForBitTests.
Invariant (dynamic program): $\mathit{MinPart}[i]$ is the least number of partitions of clusters $i \dots N-1$ into pieces that are single clusters or dense enough for a table; ties prefer the partition with the higher score (a table of $\ge 4$ clusters or a piece of $\le 2$ clusters scores 1, a single cluster 2).

function LowerSwitch(cases):
    C ← SortAndRangeify(cases)                 # merge adjacent values with one destination
    C ← FindJumpTables(C)
    C ← FindBitTestClusters(C)
    EmitTree(C)                                # balanced by probability, ≤ 3 clusters per leaf

function Suitable(i, j):                       # TargetLoweringBase::isSuitableForJumpTable
    cases ← number of case values in C[i..j];  range ← C[j].hi - C[i].lo + 1
    return cases · 100 ≥ range · 10

function BitsSuit(C[i..j]):                    # TargetLowering::isSuitableForBitTests
    cmps[d] ← Σ over clusters of d: (1 if a single value else 2)
    return j > i and C[j].hi - C[i].lo < 64 and max(cmps) ≥ 2 and
           (D = 1 and Σcmps ≥ 3 or D = 2 and Σcmps ≥ 5 or D = 3 and Σcmps ≥ 6)

function FindJumpTables(C):                    # N = |C|
    if N < 4: return C
    if Suitable(0, N-1) and not BitsSuit(C[0..N-1]): return [table C[0..N-1]]
    MinPart[N-1] ← 1; Last[N-1] ← N-1; Score[N-1] ← 2
    for i from N-2 down to 0:
        MinPart[i] ← MinPart[i+1] + 1; Last[i] ← i; Score[i] ← Score[i+1] + 2
        for j from N-1 down to i+1:
            if not Suitable(i, j): continue
            parts ← 1 + (0 if j = N-1 else MinPart[j+1])
            score ← (0 if j = N-1 else Score[j+1]) + (1 if j-i+1 ≤ 2 or j-i+1 ≥ 4 else 0)
            if parts < MinPart[i] or (parts = MinPart[i] and score > Score[i]):
                MinPart[i] ← parts; Last[i] ← j; Score[i] ← score
    result ← []; i ← 0
    while i < N:
        j ← Last[i]
        if j - i + 1 ≥ 4 and not BitsSuit(C[i..j]): result.add(table C[i..j])
        else: result.add(C[i..j] as they are)
        i ← j + 1
    return result

function FindBitTestClusters(C):               # the same DP, pieces of ≤ 64 values, ≤ 3 destinations
    (fewest pieces of range clusters with span ≤ 64 and ≤ 3 destinations, scanning j downward and
     stopping at the first piece that contains a non-range cluster or a 4th destination;
     each piece of ≥ 2 clusters for which BitsSuit holds becomes one bit-test cluster)

Theorem 11.3.8 (The partition is minimal)

FindJumpTables returns a partition of the clusters with the fewest pieces, where a piece is either one cluster or a run of clusters that is Suitable.

Proof

By induction on $i$ from $N - 1$ down to 0, $\mathit{MinPart}[i]$ is the minimum over all such partitions of the suffix $C[i..N-1]$. Base: one cluster, one piece. Step: an optimal partition of the suffix starts with a first piece $C[i..j]$; if $j = i$ it costs $1 + \mathit{MinPart}[i+1]$ (the baseline), otherwise the piece must be Suitable and the rest is optimally partitioned in $\mathit{MinPart}[j+1]$ pieces by the hypothesis (optimal substructure: replacing the rest by a better partition would improve the whole). The loop tries every $j$, so it finds the minimum; the score only breaks ties. Following $\mathit{Last}$ from 0 reconstructs one minimal partition. [KP94] proves the same recurrence for Bernstein's heuristic.

3. Worked example¶

Jump tables¶

op: clusters $[0..1 \to A], [2..3 \to B], [4 \to C], [6 \to D]$ (4 clusters, 6 cases, range 7). Suitable(0, 3): $6 \cdot 100 = 600 \ge 7 \cdot 10 = 70$, and bit tests do not apply (4 destinations), so the whole switch is one table of 7 entries: A A B B C d0 D. At run time: idx = x - 0; idx >u 6 → default; else jmp *table[idx]. The PIR box in §7 shows exactly this code from pebblec.

Binary search trees¶

sparse: 5 clusters, 5 cases, range 4998: $500 < 49\,980$, not suitable; every sub-run is sparse too (e.g. 3..70: $2 \cdot 100 < 68 \cdot 10$), so FindJumpTables returns the 5 clusters and no piece suits bit tests. The tree (equal probabilities) splits 2 | 3: test $x < 911$; left leaf: compare 3, then 70; right leaf: compare 911, 1200, 5000 — at most 1 + 3 = 4 comparisons. The lab's BinarySearch (Algorithm 11.3.4) on 8 cases needs at most $\lceil \log_2 8 \rceil + 1 = 4$ (the lab's sparse, maxcmp = 4).

Bit tests¶

chars: SortAndRangeify gives 6 clusters $[9..10 \to A], [13 \to A], [32 \to A], [43 \to C], [45 \to C], [48..57 \to B]$: 16 cases over a range of 49. A table would be dense enough ($1600 \ge 490$), but BitsSuit holds for the whole run: $57 - 9 < 64$, $D = 3$, comparisons $A: 2 + 1 + 1 = 4$, $C: 1 + 1 = 2$, $B: 2$, total $8 \ge 6$. So buildJumpTable declines and the six clusters become one bit-test cluster. Since $0 < 9$ and $57 < 64$, LLVM skips the subtraction (LowBound = 0) and tests 1 << x directly:

destination	values	mask (hex)
B	48–57	`0x3FF000000000000`
A	9, 10, 13, 32	`0x100002600`
C	43, 45	`0x280000000000`

These are the three movabsq constants of the Clang box in §7, tested most-cases-first. GCC reports the same cluster: BT(values:16 comparisons:8 range:49 …).

LLVM's switch and back-end lowering¶

A switch where the dynamic program matters — 16 cases, 9 clusters, range 1006, so no single table:

$i$	cluster	$\mathit{MinPart}[i]$	$\mathit{Last}[i]$	$\mathit{Score}[i]$	why
8	1005 → H	1	8	2	base
7	1003 → G	1	8	1	7..8: 2 cases over 3 values, suitable, $\le 2$ clusters
6	1002 → F	1	8	0	6..8: 3 clusters (score +0)
5	1001 → E	1	8	1	5..8: 4 clusters, a table
4	1000 → D	1	8	1	4..8: 5 cases over 6 values
3	103 → A	2	3	3	alone; 3..8 spans 903 values for 6 cases
2	100..101 → C	2	3	2	2..3: 3 cases over 4 values
1	4..7 → B	3	1	4	1..3 spans 100 values for 7 cases: too sparse
0	0..3 → A	2	3	2	0..3: 11 cases over 104 values, $1100 \ge 1040$

Reconstruction from $\mathit{Last}[0] = 3$: pieces $C[0..3]$ (4 clusters: a table over 0..103) and $C[4..8]$ (5 clusters: a table over 1000..1005). Two jump tables and a comparison between them — clang -O2 emits .LJTI0_0 and .LJTI0_1 for this switch (last box of §7).

Try it

./course drill switch-lowering --seed 5 --difficulty medium --solution runs Algorithm 11.3.7 on a random switch; --difficulty hard also asks for the bit-test masks.

4. Invariants and correctness¶

Jump tables¶

Correct by the table invariant and Lemma 11.3.2: the range check sends every value outside $[\min, \max]$ to the default, and every value inside to its table entry. The precondition that breaks is the range: sparse would need a 4998-entry table for 5 cases (the lab's JumpTable returns nullptr above 4096 entries).

Binary search trees¶

Theorem 11.3.5. The invariant needs signed comparisons for signed case values: an unsigned < would order −1 after 5 and send it down the wrong subtree (the lab's random switches include negative values for this reason).

Bit tests¶

By the mask invariant, bit & mask_d ≠ 0 iff $x - \min$ is the offset of a case of $d$; the range check guarantees the shift amount is below $w$ (a larger shift is poison in LLVM IR, undefined in C). The precondition $\max - \min < w$ is essential.

LLVM's switch and back-end lowering¶

Theorem 11.3.8 gives the fewest pieces; each piece is then dispatched correctly by the arguments above, and the tree over clusters is Algorithm 11.3.4 with clusters as leaves (up to three per leaf, tested in order). At -O0 LLVM runs only the whole-switch table check: the dynamic program and the bit tests are skipped (TM->getOptLevel() == CodeGenOptLevel::None), which is why pebblec -O0 and -O2 can dispatch the same switch differently.

5. Complexity¶

$n$ = cases, $N$ = range clusters, $R$ = range, $D$ = destinations, $w$ = word size.

Technique	Dispatch time	Code / data size	Build time	Justification
Jump table	$O(1)$: 1 compare + 1 indirect jump	$R$ table entries	$O(n + R)$	Algorithm 11.3.3 fills the table once
Binary search	$\lceil \log_2 n \rceil + 1$ compares	$O(n)$	$O(n \log n)$ (sort)	Theorem 11.3.5
Bit tests	1 range compare + $\le D$ tests	$D$ masks	$O(n)$	Algorithm 11.3.6; $R \le w$
LLVM clustering	$O(\log N)$ tree levels + per-cluster cost	$O(n)$ code + tables	$O(N^2)$ for `FindJumpTables`, $O(N \cdot w)$ for bit tests	the DP tries every $j > i$; the bit-test search stops after $w$ clusters

Pathological family. $n$ cases at $0, 10, 20, \dots, 10(n - 1)$: the range is $10n - 9$ and the density just above 10 %, so the whole switch is one table of $10n - 9$ entries of which 90 % point to the default — the price of LLVM's density threshold. Cases at $0, 11, 22, \dots$ fall below it as a whole, but not piecewise: a run of $j$ consecutive cases spans $11j - 10$ values, which is dense enough ($100j \ge 10(11j - 10)$) for every $j \le 10$, so the dynamic program still carves out tables of 4 to 10 clusters (12 cases at spacing 11 give one table over 0…99 plus two lone cases; llvm_switch_clusters and clang -O2 agree). Only from spacing 14 on ($4 \cdot 100 < 10 \cdot 43$) does no table form at all, and dispatch is a tree of $\lceil \log_2 n \rceil + 1$ levels. A second family, cases at the powers of two $8, 16, 32, \dots, 2^{k}$ with distinct destinations, defeats the back end's tables (four consecutive cases span at least 57 values) and its bit tests (more than three destinations) — yet clang -O2 still emits a jump table for it, because SimplifyCFG's simplifySwitchOfPowersOfTwo runs first at the IR level and rewrites the switch into one on cttz(x) (guarded by ctpop(x) == 1), whose cases $3, 4, \dots, k$ are dense. The back end's clustering is only the last word when the IR-level passes leave the switch alone.

Measured (the lab, x86-64, ns per call; half the inputs hit a case): dense16 — LLVM switch 8.27, hand jump table 7.73, search 9.59, bit tests 4.07; bits3 — switch 2.34, table 5.27, search 11.16, bits 2.93; sparse — switch 3.84, search 3.25 (labs/ch11-lowering/SPEC.md).

Jump tables¶

Relative entries (.long .LBB0_2-.LJTI0_0 in §7): 4-byte offsets from the table instead of 8-byte addresses — half the size and position-independent, one extra add.
Lookup tables instead of jumps: when every destination only produces a constant, SimplifyCFG's simplifySwitchLookup replaces the switch by a load from a constant array, with no indirect branch at all [LLVM-SimplifyCFG].

Binary search trees¶

Probability-balanced trees: LLVM splits a work item where the case probabilities (from profiles or the default's share) balance, not at the median (computeSplitWorkItemInfo) [LLVM-SwitchLowering].
Leaves of up to three clusters tested linearly, because a comparison chain of three is cheaper than another tree level ([LLVM-SDB], visitSwitch); and peeling a dominant case to test it first (peelDominantCaseCluster).

Bit tests¶

Skipping the subtraction when $0 < \min$ and $\max < w$ (LowBound = 0, the chars example): the mask is shifted by $\min$ instead.
Contiguous ranges: when the clusters cover the whole range, the default test after the last mask is unnecessary (ContiguousRange).

LLVM's switch and back-end lowering¶

Kannan–Proebsting partitioning [KP94] replaced Bernstein's greedy splitting [Ber85]; LLVM adds the score to prefer partitions with more tables among equally small ones.
Target and size knobs: -jump-table-density (10 %), -optsize-jump-table-density (40 %), -min-jump-table-entries (4), and targets that disallow tables (areJTsAllowed).
GCC's switch conversion (pass_convert_switch, pass_lower_switch) forms jump-table and bit-test clusters with its own dynamic program [GCC-SwitchConv]; Go's walk phase uses binary search plus jump tables when -d=jumptables allows [GO-Switch].

7. In real compilers¶

Jump tables¶

LLVM: SwitchCG::SwitchLowering::findJumpTables and buildJumpTable in llvm/lib/CodeGen/SwitchLoweringUtils.cpp [LLVM-SwitchLowering]. GCC: jump_table_cluster::can_be_handled in gcc/tree-switch-conversion.cc [GCC-SwitchConv]. Pebble: a PIR switch goes to LLVM as switch (E5), and the back end builds the table.

A PIR switch through pebblec: LLVM switch, then a jump table

Reproduce (pebblec from this repository built with -DPEBBLE_USE_SOLUTION=all, LLVM 23.1.2; llvm-objdump 23.1.2):

cat > op.pir <<'EOF'
pir 1.0
source "op.pbl"

fn @cost(_0: i64 "op") -> i64 {
bb0:
  switch _0, [0: bb1, 1: bb1, 2: bb2, 3: bb2, 4: bb3, 6: bb4] otherwise bb5
bb1:
  return 1
bb2:
  return 3
bb3:
  return 20
bb4:
  return 40
bb5:
  return 0
}

fn @main() -> i64 {
  let _0: i64
bb0:
  _0 = call @cost(4)
  return _0
}
EOF
pebblec --emit=llvm op.pir -o - | grep -A7 'switch i64'
pebblec -O2 --passes='function(mem2reg)' --emit=obj op.pir -o op.o
llvm-objdump -d --no-show-raw-insn op.o | sed -n '/<cost>:/,/^$/p' | head -7

Output:

  switch i64 %0, label %bb5 [
    i64 0, label %bb1
    i64 1, label %bb1
    i64 2, label %bb2
    i64 3, label %bb2
    i64 4, label %bb3
    i64 6, label %bb4
  ]
0000000000000000 <cost>:
       0:       cmpq    $0x6, %rdi
       4:       ja  0x22 <cost+0x22>
       6:       leaq    (%rip), %rax            # 0xd <cost+0xd>
       d:       movslq  (%rax,%rdi,4), %rcx
      11:       addq    %rax, %rcx
      14:       jmpq    *%rcx

What to notice: the code generator only translated PIR's terminator into one switch; the back end applied Algorithm 11.3.7 and chose a table: 4 clusters, 6 cases over 7 values, 4 destinations (no bit tests). cmpq $6; ja is Lemma 11.3.2's unsigned range check (min = 0, so no subtraction), and the table holds 4-byte relative offsets (movslq, addq, §6). --passes='function(mem2reg)' keeps -O2 code generation but no inlining, so cost survives.

Binary search trees¶

LLVM: SelectionDAGBuilder::visitSwitch and splitWorkItem in llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp [LLVM-SDB]. Go: binarySearch in src/cmd/compile/internal/walk/switch.go [GO-Switch]. GCC: switch_decision_tree in gcc/tree-switch-conversion.cc [GCC-SwitchConv].

Clang and GCC on a sparse switch: a tree of comparisons

Reproduce (clang 23.1.2, gcc 14.2.0):

cat > sparse.c <<'EOF'
int add(void), sub(void), mul(void), dvd(void), neg(void), bad(void);
int sparse(int k) {
  switch (k) {
  case 3: return add();
  case 70: return sub();
  case 911: return mul();
  case 1200: return dvd();
  case 5000: return neg();
  default: return bad();
  }
}
EOF
clang-23 -O2 -S sparse.c -o - | sed -n '/^sparse:/,/^\.Lfunc_end0/p' | grep -v '^\s*\.\(cfi\|p2align\)'
gcc-14 -O2 -fdump-tree-switchlower1-details -c sparse.c && grep clusters sparse.c.*switchlower1

Output:

sparse:                                 # @sparse
# %bb.0:
    cmpl    $910, %edi                      # imm = 0x38E
    jle .LBB0_1
# %bb.3:
    cmpl    $911, %edi                      # imm = 0x38F
    je  mul@PLT                         # TAILCALL
# %bb.4:
    cmpl    $1200, %edi                     # imm = 0x4B0
    je  dvd@PLT                         # TAILCALL
# %bb.5:
    cmpl    $5000, %edi                     # imm = 0x1388
    jne bad@PLT                         # TAILCALL
# %bb.6:
    jmp neg@PLT                         # TAILCALL
.LBB0_1:
    cmpl    $3, %edi
    je  add@PLT                         # TAILCALL
# %bb.2:
    cmpl    $70, %edi
    je  sub@PLT                         # TAILCALL
# %bb.7:
    jmp bad@PLT                         # TAILCALL
.Lfunc_end0:
;; GIMPLE switch case clusters: 3 70 911 1200 5000

What to notice: no table and no bit tests (§3): LLVM splits the five clusters 2 | 3 at 911 (cmpl $910; jle is $x < 911$) and tests each leaf's clusters linearly — at most four comparisons. GCC's cluster list is five single values as well.

Bit tests¶

LLVM: SwitchCG::SwitchLowering::findBitTestClusters and buildBitTests in SwitchLoweringUtils.cpp [LLVM-SwitchLowering], with TargetLowering::isSuitableForBitTests in llvm/include/llvm/CodeGen/TargetLowering.h. GCC: bit_test_cluster::find_bit_tests [GCC-SwitchConv].

Clang and GCC classify characters with three bit tests

Reproduce (clang 23.1.2, gcc 14.2.0):

cat > cls.c <<'EOF'
int digit(void), space(void), sign(void), other(void);
int classify(int c) {
  switch (c) {
  case '\t': case '\n': case '\r': case ' ':
    return space();
  case '0': case '1': case '2': case '3': case '4':
  case '5': case '6': case '7': case '8': case '9':
    return digit();
  case '+': case '-':
    return sign();
  default:
    return other();
  }
}
EOF
clang-23 -O2 -S cls.c -o - | sed -n '/^classify:/,/Lfunc_end/p' | grep -v '^\s*\.\(cfi\|p2align\)'
gcc-14 -O2 -fdump-tree-switchlower1-details -c cls.c && grep clusters cls.c.*switchlower1

Output:

classify:                               # @classify
# %bb.0:
    cmpl    $57, %edi
    ja  other@PLT                       # TAILCALL
# %bb.1:
    movl    %edi, %eax
    movabsq $287948901175001088, %rcx       # imm = 0x3FF000000000000
    btq %rax, %rcx
    jb  digit@PLT                       # TAILCALL
# %bb.2:
    movabsq $4294977024, %rcx               # imm = 0x100002600
    btq %rax, %rcx
    jb  space@PLT                       # TAILCALL
# %bb.3:
    movabsq $43980465111040, %rcx           # imm = 0x280000000000
    btq %rax, %rcx
    jae other@PLT                       # TAILCALL
# %bb.4:
    jmp sign@PLT                        # TAILCALL
.Lfunc_end0:
;; GIMPLE switch case clusters: BT(values:16 comparisons:8 range:49 density: 16.33%):9-57

What to notice: the three masks of §3, tested most-bits-first (digits: 10 bits), one btq each; the range check is cmpl $57 with no subtraction because $0 < 9$ and $57 < 64$. The last test inverts to jae other and falls through to sign (contiguity is not needed for that). GCC counts the same 8 comparisons as isSuitableForBitTests (§3).

LLVM's switch and back-end lowering¶

LLVM: SelectionDAGBuilder::visitSwitch calls sortAndRangeify, findJumpTables, findBitTestClusters and then lowers the work list; the thresholds are TargetLoweringBase::isSuitableForJumpTable and the -jump-table-density/-min-jump-table-entries options in llvm/lib/CodeGen/TargetLoweringBase.cpp [LLVM-TLB]. The IR-level simplifySwitchLookup in SimplifyCFG runs earlier, at -O2 [LLVM-SimplifyCFG].

Two jump tables from one switch (the dynamic program of §3)

Reproduce (clang 23.1.2):

cat > mix.c <<'EOF'
int a(void), b(void), c(void), d(void), e(void), f(void), g(void), h(void), z(void);
int mix(int x) {
  switch (x) {
  case 0: case 1: case 2: case 3: return a();
  case 4: case 5: case 6: case 7: return b();
  case 100: case 101: return c();
  case 103: return a();
  case 1000: return d();
  case 1001: return e();
  case 1002: return f();
  case 1003: return g();
  case 1005: return h();
  default: return z();
  }
}
EOF
clang-23 -O2 -S mix.c -o - | grep -E '^\.LJTI|cmpl|ja|jmpq\s+\*'

Output:

    cmpl    $103, %edi
    ja  .LBB0_3
    jmpq    *%rax
    cmpl    $5, %edi
    ja  z@PLT                           # TAILCALL
    jmpq    *%rcx
.LJTI0_0:
.LJTI0_1:

What to notice: the partition of §3 — a table over 0…103 (range check cmpl $103) and one over 1000…1005 (after subtracting 1000, cmpl $5) — found by findJumpTables; neither piece suits bit tests: the first spans 104 values, more than a 64-bit word, and the second has 5 destinations.

Find where LLVM does it. In llvm/lib/CodeGen/SwitchLoweringUtils.cpp, which function refuses to build a jump table for a range that bit tests could handle, and which TargetLowering predicate does it ask? (Quiz llvm-where-jt-vs-bits.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Jump table	Any dense switch; size grows with the range	$O(1)$ · one indirect branch (hard to predict when targets vary)	Compact code, data table in `.rodata`	Low (plus a range check)	Dense switches, interpreters' opcode dispatch, `dense16`
Binary search tree	Any switch	$O(\log n)$ · predictable when inputs are skewed	Code grows linearly with cases	Low	Sparse switches (`sparse`), and the glue between clusters
Bit tests	$\max - \min < 64$, few destinations	$O(D)$ · a few ALU ops, no memory	Tiny: $D$ 64-bit constants	Low	Character classes (`chars`), flag sets (`bits3`)
LLVM `switch` + back end	All of the above, chosen per cluster (Theorem 11.3.8)	$O(\log N)$ + cluster cost · matches the best hand lowering in the lab except on unpredictable dense switches	One IR instruction; the choice is visible in the assembly	None for the front end; the DP lives in LLVM	Every LLVM front end, including Pebble's code generator

Choose a jump table when the cases are dense and many; a binary tree when they are sparse; bit tests when they fit in a word with few destinations; and emit switch and let LLVM choose when you target LLVM. In the lab its choice was the fastest, or within 0.6 ns of the fastest hand lowering, on bits3, chars, sparse and clustered; on dense16 with random inputs its jump table (8.27 ns) lost to the lab's eight bit tests (4.07 ns), because the indirect jump mispredicts and LLVM's static cost model does not know the input distribution — a profile (!prof weights) or a different density threshold is the remedy.

9. Assessment¶

Quiz (./course quiz 11): jt-density, jt-range-check (tag jump-table); bst-depth, bst-signed (tag binary-search); bits-mask, bits-suitable (tag bit-tests); llvm-switch-clusters, llvm-where-jt-vs-bits (tag llvm-switch).
Drill: ./course drill switch-lowering (clusters, density, the final partition; hard: masks).
Flashcards: tags jump-table, binary-search, bit-tests, llvm-switch.
Exercises: E5 (PIR switch → LLVM switch); lab part B.

References¶

See the chapter references.

Technique	Dispatch time	Code / data size	Build time	Justification
Jump table	\(O(1)\): 1 compare + 1 indirect jump	\(R\) table entries	\(O(n + R)\)	Algorithm 11.3.3 fills the table once
Binary search	\(\lceil \log_2 n \rceil + 1\) compares	\(O(n)\)	\(O(n \log n)\) (sort)	Theorem 11.3.5
Bit tests	1 range compare + \(\le D\) tests	\(D\) masks	\(O(n)\)	Algorithm 11.3.6; \(R \le w\)
LLVM clustering	\(O(\log N)\) tree levels + per-cluster cost	\(O(n)\) code + tables	\(O(N^2)\) for `FindJumpTables`, \(O(N \cdot w)\) for bit tests	the DP tries every \(j > i\); the bit-test search stops after \(w\) clusters

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Jump table	Any dense switch; size grows with the range	\(O(1)\) · one indirect branch (hard to predict when targets vary)	Compact code, data table in `.rodata`	Low (plus a range check)	Dense switches, interpreters' opcode dispatch, `dense16`
Binary search tree	Any switch	\(O(\log n)\) · predictable when inputs are skewed	Code grows linearly with cases	Low	Sparse switches (`sparse`), and the glue between clusters
Bit tests	\(\max - \min < 64\), few destinations	\(O(D)\) · a few ALU ops, no memory	Tiny: \(D\) 64-bit constants	Low	Character classes (`chars`), flag sets (`bits3`)
LLVM `switch` + back end	All of the above, chosen per cluster (Theorem 11.3.8)	\(O(\log N)\) + cluster cost · matches the best hand lowering in the lab except on unpredictable dense switches	One IR instruction; the choice is visible in the assembly	None for the front end; the DP lives in LLVM	Every LLVM front end, including Pebble's code generator

Lesson 11.3 — Switch lowering: jump tables, binary search, bit tests, and LLVM's switch¶

1. Problem and motivation¶

Jump tables¶

Binary search trees¶

Bit tests¶

LLVM's switch and back-end lowering¶

2. Definitions and algorithms¶

3. Worked example¶

Jump tables¶

Binary search trees¶

Bit tests¶

LLVM's switch and back-end lowering¶

4. Invariants and correctness¶

Jump tables¶

Binary search trees¶

Bit tests¶

LLVM's switch and back-end lowering¶

5. Complexity¶

6. Variants and refinements¶

Jump tables¶

Binary search trees¶

Bit tests¶

LLVM's switch and back-end lowering¶

7. In real compilers¶

Jump tables¶

Binary search trees¶

Bit tests¶

LLVM's switch and back-end lowering¶

8. Comparison¶

9. Assessment¶

References¶

Lesson 11.3 — Switch lowering: jump tables, binary search, bit tests, and LLVM's `switch`¶

LLVM's `switch` and back-end lowering¶