Quick Answer: GCC switch lowering turns a switch into one of several shapes: a jump table, a binary tree of comparisons, a bit test against a constant, or a mix of these. The compiler picks by estimating cost. In the GCC behavior Xoranth measured, a jump table is chosen when its size stays under roughly eight entries per case label.

Most developers picture a switch as a tidy if-else chain. The compiler sees something else entirely. In a write-up on GCC's switch handling, the author showed that identical-looking switch blocks can compile to a table lookup, a tree of cmp and jcc instructions, or a shift-and-test against a magic constant. Understanding GCC switch lowering helps you predict the machine code you'll get, and it explains a few results that look wrong until you see the cost model behind them.

Dense Cases Become Jump Tables (And Offsets Are Free)

Start with the simplest case: five consecutive values, 0 through 4, each calling a different function. GCC emits a bounds check (cmp eax, 4 followed by ja) and then an indirect jmp through a table of code addresses. Nothing surprising there.

Now shift the values to 97 through 101. The compiler emits lea eax, [rdi - 97] to normalize the index, then the same bounds check and the same table. The offset costs one instruction, and the generated code is essentially identical.

Here's the counter-intuitive part. A lot of performance advice says to replace switch with an array of function pointers because it's faster. For dense, contiguous cases, GCC already builds that array for you. Writing it by hand gains you nothing in codegen and adds a maintenance burden: the array and the case labels can drift apart, and the compiler can no longer check that every value is handled.

The Threshold: Roughly Eight Entries Per Case

Density is what matters, not just the number of cases. The author tested sparse layouts and found that GCC's cutoff sits near eight jump-table entries per case label. Five cases at 0, 7, 14, 21, and 34 produce a 35-entry table, mostly pointing at the default. Since 35 is less than 5 × 8 = 40, GCC builds the table. Most of its entries just jump to the default return path, but that's a cheap price for a single indirect jump.

Push the same five cases out to 0, 8, 16, 24, and 40, and the table would need 41 entries. That's over the 40-entry budget, so GCC abandons the table and emits a comparison tree.

Two caveats matter here. First, this is an empirical threshold from one GCC version and one set of flags (the author used -O3), not a documented constant. Second, the exact number can change between releases. If a performance decision depends on it, check the generated assembly with gcc -O3 -S rather than trusting a rule of thumb.

Outliers: GCC Splits the Switch

What happens when one case is far away from the rest? Take cases 1 through 5 plus a lone case at 100. A naive table would need 101 entries for six labels, which blows the budget. GCC doesn't give up on the dense part. It builds a six-entry jump table for 1 through 5, then emits a single compare for 100 (cmp eax, 100 followed by jne).

This is a real trade-off. The hot path for the dense range pays only the bounds check and the indirect jump. The outlier pays an extra branch to get to its own case. If that outlier is on a hot path, you may want to restructure the code so it isn't mixed into a switch with a dense range.

Contiguous Ranges Count Differently Than You'd Expect

Here's where most mental models of switch lowering break. The author built a function with 20 case labels covering values 0 through 87. A table of 88 entries is well within the budget of 20 × 8 = 160, so you'd expect a jump table. GCC emits a sequence of comparisons instead.

The reason is that GCC merges contiguous labels into ranges before estimating cost. Labels 42, 43, 44, and 45 all call f3, so GCC treats them as one range and needs only two comparisons for it (a lower bound and an upper bound), not four. Across the five ranges in the example, that's 10 comparisons total.

Now the arithmetic flips. Ten comparisons × 8 = 80, which is less than 88. The table is no longer profitable, so the compiler chooses the comparison tree. The lesson: the cost model counts the work the machine will actually do, not the number of labels you wrote. Groups of consecutive labels with the same body are cheap, even if they look expensive in the source.

Bit Tests: The Strange Constant in Your Assembly

The most surprising output comes from a function that switches on a character. The cases are '0', '2', '4', '5', '7', '9', 'A', 'C', and 'E'. Instead of a table or a tree, GCC emits this:

  1. Subtract 48 (the ASCII value of '0') to normalize the index.
  2. Compare the result against 21 and jump to the default if it's larger.
  3. Load the constant 2753205 into a register and run bt (bit test) on it.
  4. Jump to the case body if the carry flag is set.

The constant is a bitset. Its set bits sit at positions 0, 2, 4, 5, 7, 9, 17, 19, and 21, which correspond to the case labels after subtracting 48. Adding those powers of two gives exactly 2753205. Bit test lowering replaces a series of comparisons or a memory load with one register test.

This strategy depends on the range fitting in a register. Values 0 through 21 fit comfortably in a 64-bit register, so the bitset works. A wider range wouldn't, and the compiler would fall back to another strategy. It's also the one part of the optimization the author noted doesn't translate to Clang, so don't assume the same codegen across compilers.

How GCC Makes These Decisions Internally

If you want to go deeper, the work happens in a pass called pass_lower_switch, which calls analyze_switch_statement. The flow is roughly:

  • GCC reads the switch in its internal representation, GIMPLE, and counts cases per outgoing edge.
  • It creates a simple_cluster for each label, recording its value range, destination, and probability. Without profile data, probabilities are uniform.
  • It runs bit_test_cluster::find_bit_tests first, so bitset candidates are pulled out before anything else.
  • It then searches the remaining simple clusters for jump-table candidates and applies the cost threshold.
  • Anything left over becomes a balanced decision tree.

The order matters. Bit tests get first claim on the cases they can handle, which explains why the character example never reached the table stage. The author's version was edited and had assertions removed, so treat it as a guide to the logic, not a copy of current GCC source.

Frequently Asked Questions

What is GCC switch lowering?

GCC switch lowering is the compiler step that converts a switch statement into machine code. It chooses between a jump table, a binary decision tree of comparisons, a bit test against a constant bitset, or a combination. The choice depends on how dense the case values are and on how many comparisons the code would need.

When does GCC turn a switch into a jump table?

GCC builds a jump table when the table size is small relative to the number of case labels. In the author's tests, the cutoff was close to eight entries per label. Dense, contiguous values qualify easily. Sparse values with large gaps usually don't, so the compiler emits a comparison tree instead.

Why does GCC use comparisons instead of a jump table for a dense switch?

GCC counts contiguous labels as ranges and then estimates the number of comparisons those ranges need. If the comparison count multiplied by eight is smaller than the table size, the tree wins. A switch that looks dense in the source can still compile to comparisons if its labels are grouped into several short ranges.

How can I get a switch to compile to a jump table?

Keep case values close together, and normalize offsets so the smallest value is near zero. Avoid one far-off outlier that inflates the table. Then verify the result by running gcc -O3 -S and looking for an indirect jmp. Don't rewrite the switch as a function-pointer array unless you've measured a benefit, since GCC often builds an equivalent table on its own.

Does Clang lower switch statements the same way?

Mostly, according to the author, who reported that all the optimizations examined except bitset lowering also appear in Clang. The exact thresholds and code shapes may differ, so compare the generated assembly for your specific switch if the output matters to you.

Put This to Work on Your Own Code

Pick the hottest switch in your codebase, compile it with gcc -O3 -S, and check whether you got a jump table, a comparison tree, or a bt instruction. Then try moving one outlier case out or renumbering a sparse set, and recompile to see what changes. Pass this to someone wrestling with a mysterious constant in their assembly, because GCC switch lowering is usually the explanation.