Xoranth's musings

Switch lowering in GCC 2024-01-14 Introduction We have seen in a previous post that switch statements are more complex than they seem. The compiler is able to implement them as a decision tree (even though maybe it shouldn't). Is that everything it can do? In this post, I'll focus on gcc. All optimizations, except the bitset lowering, translate to clang. I'll be using the -O3 optimization flag unless indicated otherwise. I've also slightly edited gcc code and removed certain assertions for brevity. Examples Let us start with a simple example. A function that takes two integers x and val. Depending on the value of x, it calls a corresponding function (f0, f1, and so forth) with val as an argument and returns the result. Were we to implement this manually, we'd would use an array of function pointers, where the input serves as the index into the array. int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); 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; } return 0; } 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 .L5: jmp f3 .L3: jmp f4 .L8: jmp f0 .L7: jmp f1 .L6: jmp f2 .L2: xor eax, eax ret The compiler agrees with this approach, and transforms the switch statement into a jump table. Moreover, it is able to identify when the values are offset by a constant: int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); int compact(int x, int val) { switch (x) { case 97: return f0(val); case 98: return f1(val); case 99: return f2(val); case 100: return f3(val); case 101: return f4(val); default: return 0; } return 0; } compact: lea eax, [rdi-97] cmp eax, 4 ja .L2 mov edi, esi jmp [QWORD PTR .L4[0+rax*8]] .L4: .quad .L8 .quad .L7 .quad .L6 .quad .L5 .quad .L3 .L5: jmp f3 .L3: jmp f4 .L8: jmp f0 .L7: jmp f1 .L6: jmp f2 .L2: xor eax, eax ret Our intuition suggests that the more sparse the values, the less advantageous the jump table conversion is. Through experimentation, we find that gcc considers the threshold to be around eight jump table entries per case label. In other words, the following function compiles to a jump table: int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); int compact_7(int x, int val) { switch (x) { case 0: return f0(val); case 7: return f1(val); case 14: return f2(val); case 21: return f3(val); case 34: return f4(val); default: return 0; } return 0; } compact_7: mov eax, edi mov edi, esi cmp eax, 34 ja .L2 jmp [QWORD PTR .L4[0+rax*8]] .L4: .quad .L8 .quad .L2 ; ... .quad .L2 .quad .L7 .quad .L2 ; ... .quad .L2 .quad .L6 .quad .L2 ; ... .quad .L2 .quad .L5 .quad .L2 ; ... .quad .L2 .quad .L3 .L2: xor eax, eax ret .L8: jmp f0 .L7: jmp f1 .L6: jmp f2 .L5: jmp f3 .L3: jmp f4 But this other function is expanded as a tree of comparisons: int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); int sparse_8(int x, int val) { switch (x) { case 0: return f0(val); case 8: return f1(val); case 16: return f2(val); case 24: return f3(val); case 40: return f4(val); default: return 0; } return 0; } sparse_8: mov eax, edi mov edi, esi cmp eax, 16 je .L2 jle .L10 cmp eax, 24 je .L7 cmp eax, 40 jne .L1 jmp f4 .L10: test eax, eax je .L4 cmp eax, 8 jne .L1 jmp f1 .L1: xor eax, eax ret .L4: jmp f0 .L7: jmp f3 .L2: jmp f2 Here's the comparison tree visualized for clarity: G ret 0 ret 0 call f0 call f0 call f1 call f1 call f2 call f2 cmp eax, 24 cmp eax, 24 call f3 call f3 call f4 call f4 cmp eax, 16 cmp eax, 16 cmp eax, 16->call f2 je test eax, eax test eax, eax cmp eax, 16->test eax, eax jle cmp eax, 16->cmp eax, 24 test eax, eax->call f0 je cmp eax, 8 cmp eax, 8 test eax, eax->cmp eax, 8 cmp eax, 24->call f3 je cmp eax, 40 cmp eax, 40 cmp eax, 24->cmp eax, 40 cmp eax, 40->ret 0 jne cmp eax, 40->call f4 cmp eax, 8->ret 0 jne cmp eax, 8->call f1 A couple of observations: We've only tried equally spaced values so far. Can the compiler identify transformations that are profitable on a subset of all cases? So far each case led to a different result. What if we had different cases with the same result? The switch in sparse_8 could be simplified by dividing x by eight before the jump. Interestingly, gcc doesn't find this simplification. Let's dig into 1. and 2. Outliers Altering our first example by including an outlier value shows that the compiler is able to recognize dense subsets of cases. int f0(int val); int f1(int val); int f2(int val); int f3(int val); int f4(int val); int f5(int val); int outlier(int x, int val) { switch (x) { case 1: return f0(val); case 2: return f1(val); case 3: return f2(val); case 4: return f3(val); case 5: return f4(val); case 100: return f5(val); default: return 0; } return 0; } outlier: mov eax, edi mov edi, esi cmp eax, 5 jg .L2 test eax, eax jle .L1 cmp eax, 5 ja .L4 jmp [QWORD PTR .L6[0+rax*8]] .L6: .quad .L4 .quad .L4 .quad .L9 .quad .L8 .quad .L7 .quad .L5 .L2: cmp eax, 100 jne .L1 jmp f5 .L7: jmp f3 .L5: jmp f4 .L9: jmp f1 .L8: jmp f2 .L4: jmp f0 .L1: xor eax, eax ret The compiler emits a branch for case 100, but emits a jump table for case 1 through 5. Contiguous In our examples so far, each case statement lead to a different code block. Let's test what happens when multiple case labels invoke the same function. int f1(int val); int f2(int val); int f3(int val); int f4(int val); int f5(int val); int blocks_2(int x, int val) { switch (x) { case 0: case 1: case 2: case 3: return f1(val); case 21: ... case 24: return f2(val); case 42: ... case 45: return f3(val); case 63: ... case 66: return f4(val); case 84: ... case 87: return f5(val); default: return 0; } return 0; } blocks_2: mov eax, edi mov edi, esi cmp eax, 45 jg .L2 cmp eax, 41 jg .L3 cmp eax, 3 jg .L4 test eax, eax js .L1 jmp f1 .L2: cmp eax, 66 jg .L8 cmp eax, 62 jle .L1 jmp f4 .L4: sub eax, 21 cmp eax, 3 ja .L1 jmp f2 .L8: sub eax, 84 cmp eax, 3 ja .L1 jmp f5 .L3: jmp f3 .L1: xor eax, eax ret We have 20 case labels, with values between 0 and 87. The compiler could lower this switch to a jump table with 88 entries. Our hypothesis for the heuristic is that a jump table conversion is profitable when its size is smaller than 8 * num_case_labels. Since 88 < 20 * 8, the conversion should be profitable in this case, however gcc opted to lower the switch to a sequence of comparisons. To better understand why, let's examine a specific block of case labels. int blocks_2(int x, int val) { switch (x) { case 42: case 43: case 44: case 45: return f3(val); } return 0; } blocks_2: mov eax, edi ; Move `val` to $eax mov edi, esi cmp eax, 45 ; If val <= 45, do _not_ jump jg .L2 cmp eax, 41 ; If val >= 42, jump to L3 jg .L3 ; ... .L2: ; ... .L3: ; We reach L3 only if 42 <= val <= 45 jmp f3 ; Call f3(val) ; ... The compiler realizes that the cases are contiguous and can be implemented with two comparisons instead of four. If the input of the jump table heuristic is the number of comparisons instead of case labels, things work out: We have a total of 10 comparisons. Since 10 * 8 < 88, our revised heuristic suggests that a jump table transformation is unprofitable. Non-contiguous Let us try a non-contiguous case. int f1(int val); 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; } return 0; } 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 compiler emits non-intuitive machine code. Why is there no cmp nor jump tables? Where does the constant 2753205 come from? An hint comes from the instruction bt. According to the Intel docs, bt: Selects the bit in a bit string (specified with the first operand, called the bit base) at the bit-position designated by the bit offset (specified by the second operand) and stores the value of the bit in the CF flag. If we examine the binary representation of 2753205, we find that it is in fact a bitset. The bits that are set to one correspond to the ASCII values of the case labels, each value being reduced by 48. Simd ops chars 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G Cases ... edx 1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 mov edx, 2753205 edx:p0--chars:p0 edx:p2--chars:p2 edx:p4--chars:p4 edx:p5--chars:p5 edx:p7--chars:p7 edx:p9--chars:p9 edx:p17--chars:p17 edx:p19--chars:p19 edx:p21--chars:p21 Implementation We've encountered several distinct lowering strategies employed by gcc.

The compiler pass that responsible for lowering switch statements is the (appropriately named) pass_lower_switch, which in turn calls analyze_switch_statement. Since gcc source can be daunting to follow, I'll provide a step-by-step commented version below.

bool switch_decision_tree::analyze_switch_statement () { unsigned l = gimple_switch_num_labels (m_switch); auto_vec<cluster *> clusters; ... compute_cases_per_edge (); Some preamble code. m_switch points to a gimple object. Gimple is the internal representation used by gcc.

Through this, we extract the overall count of cases and the individual counts of cases for each outgoing edge.

We also allocate a vector that will record the lowering strategy chosen for each case label.