Switch Lowering in GCC

Switch lowering in GCC

2024-01-14

Introduction

We have seen in a previous post that toggle statements are additional complex than they seem. The compiler is capable to execute them as a decision tree (even although perchance it shouldn't). Is that everything it can do?

In this post, I'll concentration on gcc. All optimizations, apart from the bitset lowering, translate to clang. I'll be using the -O3 optimization emblem unless indicated otherwise.

I've additionally slightly edited gcc code and removed certain assertions for brevity.

Examples

Let us commencement alongside a uncomplicated 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) alongside val as an disagreement and returns the result. Were we to execute this manually, we'd would use an gathering of function pointers, anywhere the input serves as the indicator 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 alongside this approach, and transforms the toggle declaration into a jump table.

Moreover, it is capable to acknowledge whenever 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 additional sparse the values, the small advantageous the jump array conversion is.

Through experimentation, we discover that gcc considers the threshold to be about eight jump array entries per case label.

In another 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 another 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 difference tree visualized for clarity:

A brace of observations:

1. We've lone tried likewise spaced values so far. Can the compiler acknowledge transformations that are profitable on a subset of all cases?
2. So far all case led to a distinct result. What if we had distinct cases alongside the identical result?
3. The toggle in sparse_8 could be simplified by dividing x by eight before the jump. Interestingly, gcc doesn't discover this simplification.

Let's dig into 1. and 2.

Outliers

Altering our archetypal example by including an outlier value shows that the compiler is capable to acknowledge compact 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 array for case 1 through 5.

Contiguous

In our examples so far, all case declaration guide to a distinct code block. Let's test what happens whenever multiple case labels invoke the identical 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, alongside values between 0 and 87. The compiler could lesser this toggle to a jump array alongside 88 entries. Our assumption for the heuristic is that a jump array conversion is profitable whenever its size is smaller than 8 * num_case_labels. Since 88 < 20 * 8, the conversion have to be profitable in this case, nevertheless gcc opted to lesser the toggle to a sequence of comparisons.

To improved comprehend why, let's analyze a particular obstacle 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 mov edi, esi cmp eax, 45 jg .L2 cmp eax, 41 jg .L3 .L2: .L3: jmp f3 

The compiler realizes that the cases are adjacent and can be implemented alongside two comparisons alternatively of four. If the input of the jump array heuristic is the figure of comparisons alternatively of case labels, things activity out:

We have a total of 10 comparisons. Since 10 * 8 < 88, our revised heuristic suggests that a jump array 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 device code. Why is there no cmp nor jump tables? Where does the changeless 2753205 arrive from?

An clue comes from the education bt. According to the Intel docs, bt:

Selects the bit in a bit cord (specified alongside the archetypal 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 analyze the binary depiction of 2753205, we discover that it is in fact a bitset. The bits that are set to one equivalent to the ASCII values of the case labels, all value being reduced by 48.

Implementation

We've encountered multiple distinct lowering strategies employed by gcc. For a additional in-depth understanding, we can delve into the compiler's origin code.

The compiler continue that liable for lowering toggle statements is the (appropriately named) pass_lower_switch, which in rotate calls analyze_switch_statement.

Since gcc origin can be daunting to follow, I'll provision a step-by-step commented type below. Following this, I volition interrupt downward all division to explain its functionality.

bool switch_decision_tree::analyze_switch_statement () { unsigned l = gimple_switch_num_labels (m_switch); auto_vec<cluster *> clusters; compute_cases_per_edge (); 

Some introduction code. m_switch points to a gimple object. Gimple is the inner depiction used by gcc. Through this, we extract the general figure of cases and the idiosyncratic counts of cases for all outgoing edge.

We additionally allocate a vector that volition document the lowering scheme chosen for all case label.

 for (unsigned i = 1; i < l; i++) { tree elt = gimple_switch_label (m_switch, i); tree low = CASE_LOW (elt); tree elevated = CASE_HIGH (elt); profile_probability p = case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)); clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest, p)); } 

More setup code. We notice that gimple has a idea of elevated and low value for all label. That is, adjacent case labels have already joined together at this stage.

For all case label, we allocate a simple_cluster. This collection serves as a record, capturing the range of values connected alongside the label, the applicable output edge, and the likelihood of this collection being chosen. This probability comes from profile-guided optimization. By default it is uniform among case labels.

 vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters); 

We change the vector of clusters we have created. The name bit_test_cluster hints to the bitset lowering scheme we saw before.

 vec<cluster *> output2; auto_vec<cluster *> tmp; for (unsigned i = 0; i < output.length (); i++) { collection *c = output[i]; if (c->get_type () != SIMPLE_CASE) { if (!tmp.is_empty ()) { tmp.truncate (0); } output2.safe_push (c); } else tmp.safe_push (c); } 

This division allocates a vector for the transformed cases and a scratch vector. Any case that wasn't altered during the bitset transformation procedure is gathered in this scratch vector. These cases are afterward processed and cleared whenever we arrive throughout an optimized cluster.

Essentially, in this division we are looking for sequences of case labels that couldn't be converted into bitset clusters.

 vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp); output2.safe_splice (n); n.release (); 

We attempt to change these successive labels into a jump array and add the outcome to the output.

 if (!tmp.is_empty ()) { vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp); output2.safe_splice (n); n.release (); } 

This is a coda for the iteration above.

 bool expanded = try_switch_expansion (output2); release_clusters(output2); come back expanded; } 

Whatever is remaining goes through another pass, which turns the toggle declaration into a decision tree. The bitsets and jump array are leaves of the decision tree.

Bitsets

Let's dig additional into bit_test_cluster::find_bit_tests. The elevated flat construction of the code is as follow.

Initially, we aim to discover the optimal method to bundle all clusters into bitsets. Optimality, in this context, refers to minimizing the figure of bitsets used. We do so using energetic programming.

Subsequently, we iterate complete the bitsets and use a profitability heuristic. If the bitsets encounter this heuristic, we emit a bit_test_cluster; otherwise, we keep the first simple_clusters.

vec<cluster *> bit_test_cluster::find_bit_tests (vec<cluster *> &clusters) { unsigned l = clusters.length (); auto_vec<min_cluster_item> min; min.quick_push (min_cluster_item (0, 0, 0)); for (unsigned i = 1; i <= l; i++) { min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX)); for (unsigned j = 0; j < i; j++) { if (min[j].m_count + 1 < min[i].m_count && can_be_handled (clusters, j, i - 1)) min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX); } gcc_checking_assert (min[i].m_count != INT_MAX); } 

For the energetic programming, we'll use a vector of min_cluster_item structures. Each min_cluster_item has three components:

• The archetypal records how many bitsets do we need to portray the archetypal i case labels, anywhere i is the indicator in the vector.
• The second records the start of the final bitset.
• The third is unused.

The energetic programming is as follows. We desire to discover the minimum figure of bitsets to portray the archetypal i case labels.

The basis case is straightforward, a sole case tag can be represented by a sole bitset.

Suppose we have already have established the optimal figure of bitsets for the archetypal j case label, for all . We define to be the optimal figure of splits for the archetypal i elements. This method we already computed , and are now seeking .

If the range of case labels can be represented as a bitset cluster, it must be true that

Conversely, assume we have the optimal project for the archetypal i labels. If the final bitset starts at tag , this project is additionally optimal whenever restricted to . Were this not the case, we could enhance the project on as well.

Therefore, it must be that:

These conditions are exactly what the if declaration in the code complete checks for.

The can_be_handled function controls whether a range of case labels can be turned into a bitset test. It tests two criteria:

• The combined range of all the case labels must be smaller than the width of a register. On contemporary systems, the blended range have to be small than 64.
• The case labels must have at most 3 unique outgoing edges.

If there is additional than one edge, we emit a cascade of bit tests.

 vec<cluster *> output; for (unsigned end = l;;) { int commencement = min[end].m_start; if (is_beneficial (clusters, start, end - 1)) { bool complete = commencement == 0 && end == clusters.length (); output.safe_push (new bit_test_cluster (clusters, start, end - 1, entire)); } else for (int i = end - 1; i >= start; i--) output.safe_push (clusters[i]); end = start; if (start <= 0) break; } output.reverse (); come back output; } 

Now we change lone bitsets that fulfill the is_beneficial test. In the code figure represents the figure of case labels handled by the cluster, during uniq denotes the figure of distinct outgoing edges.

bool bit_test_cluster::is_beneficial (unsigned count, unsigned uniq) { return (((uniq == 1 && figure >= 3) || (uniq == 2 && figure >= 5) || (uniq == 3 && figure >= 6))); } 

Jump tables

The logic for jump array conversion mirrors the one used for bit test conversion. It leverages energetic programming to acknowledge "clusters" that can be profitably converted to a jump table.

Let's delve into the code.

vec<cluster *> jump_table_cluster::find_jump_tables (vec<cluster *> &clusters) { if (!is_enabled ()) return clusters.copy (); unsigned l = clusters.length (); auto_vec<min_cluster_item> min; min.reserve (l + 1); 

We commencement by preallocating a vector of min_cluster_item. We'll use this vector to keep track of the finest jump array assignments for successive case clusters.

 min.quick_push (min_cluster_item (0, 0, 0)); 

We additionally shove the basis case for energetic programming. This corresponds to using a sole jump array for the entire switch.

Let's concentration now on the chief loop.

 unsigned HOST_WIDE_INT max_ratio = ; for (unsigned i = 1; i <= l; i++) { min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX)); HOST_WIDE_INT comparison_count = 0; for (unsigned k = 0; k <= i - 1; k++) { simple_cluster *sc = static_cast<simple_cluster *> (clusters[k]); comparison_count += sc->get_comparison_count (); } for (unsigned j = 0; j < i; j++) { unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases; if (i - j < case_values_threshold ()) s += i - j; if () { min[i] = min_cluster_item (min[j].m_count + 1, j, s ); } simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]); comparison_count -= sc->get_comparison_count (); } } 

The energetic programming iteration mirrors the one we used for bitsets. We desire to discover the minimum figure of jump tables to portray the archetypal i case labels.

We iterate complete splits at the j-th case label, for j < i. During all repeat we track the finest scoring split. The particular case j == 0 represents a sole jump array for the complete toggle statement.

Inside this inner iteration we additionally keep track of:

1. How many distinct jump tables we would need to lesser the switch.
2. The start of the last jump array of the decomposition.
3. How many cases cannot be handled by a jump table. In the code, this is the accumulator s.

Point 1. and 2. are akin to the bitset lowering pass, during 3. is new and particular to jump tables.

Namely, there is several overhead to dispatching to a jump table, because of the indirect jump and the need to inspect bounds. Therefore gcc requires a minimum amount of case labels to create a jump table.

If a divided would create a jump array that is too small, the size of the jump array is added to an accumulator s, which is used as a tie-breaker between distinct divided candidates.

To compute the scoring, we need the difference figure between j-th and the i-th case label. We compute it summing up the figure of comparisons for all labels, and decreasing the figure as we advancement in the inner loop.

We additionally need the figure of unhandled case labels. We decide it comparing the size of the jump array to the outcome of the case_values_threshold function. This function is architecture reliant and takes into document the existence of switch-case particular instructions, but on contemporary x64 and Arm64 machines, it defaults to 5.

unsigned int default_case_values_threshold (void) { return (targetm.have_casesi () ? 4 : 5); } 

Let's now concentration on the chief heuristic, starting alongside how max_ratio is computed. I've reproduced below the chief loop, omitting lines unrelated to the chief heuristic.

We've seen in the examples division that gcc uses the proportion between jump array entries and comparisons as a metric for the lowering the heuristic. The code below shows that distinct ratios are used whenever optimizing for speed (flags -O[123|fast]) or size (flag -Os). Specifically, a proportion of 8 is used whenever optimizing for speed, during a proportion of 2 is used whenever optimizing for size.

 unsigned HOST_WIDE_INT max_ratio = (optimize_insn_for_size_p () ? param_jump_table_max_growth_ratio_for_size : param_jump_table_max_growth_ratio_for_speed); for (unsigned i = 1; i <= l; i++) { min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX)); for (unsigned j = 0; j < i; j++) { if ((min[j].m_count + 1 < min[i].m_count)  || (min[j].m_count + 1 == min[i].m_count && s < min[i].m_non_jt_cases) && can_be_handled (clusters, j, i - 1, max_ratio, comparison_count)) { min[i] = min_cluster_item (min[j].m_count + 1, j, s ); } } } 

Now onto the chief loop. Given two splits, we favor the one that results in small jump tables being emitted. Or, if they would outcome in the identical figure of jump tables, we favor the one that handles the most case labels. We additionally disregard splits that would outcome in unprofitable jump tables, anywhere profitability is checked by the can_be_handled function.

The can_be_handled condition, checks for overflow and compares the proportion of case labels to jump array entries:

bool jump_table_cluster::can_be_handled (const vec<cluster *> &clusters, unsigned start, unsigned end, unsigned HOST_WIDE_INT max_ratio, unsigned HOST_WIDE_INT comparison_count) { if (start == end) return true; unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (), clusters[end]->get_high ()); return lhs <= max_ratio * comparison_count; } 

The coda of the function additionally mirrors the one for bitset clusters. It iterates complete all jump tables in reverse order, and prunes the ones that neglect the is_beneficial check.

 vec<cluster *> output; output.create (4); for (unsigned int end = l;;) { int commencement = min[end].m_start; if (is_beneficial (clusters, start, end - 1)) output.safe_push (new jump_table_cluster (clusters, start, end - 1)); else for (int i = end - 1; i >= start; i--) output.safe_push (clusters[i]); end = start; if (start <= 0) break; } output.reverse (); come back output; } 

The is_beneficial inspect for jump tables aims to prune small jump tables. It compares the figure of case labels to case_values_threshold.

bool jump_table_cluster::is_beneficial (const vec<cluster *> &, unsigned start, unsigned end) { if (start == end) return false; return end - commencement + 1 >= case_values_threshold (); } 

Binary tree

If gcc cannot emit a bitset collection or a jump table, it falls rear to a binary tree of comparison.

In emitting the tree, it takes into document the probability of all case label cluster. The probability can be obtained via profile-guided optimization, or with the __builtin_expect_with_probability builtin.

The code is beautiful straightforward.

void switch_decision_tree::balance_case_nodes (case_tree_node **head, case_tree_node *parent) { case_tree_node *np = *head; if (np) { int i = 0; case_tree_node **npp, *left; profile_probability prob = profile_probability::never (); 

Sum probability of all case labels.

 while (np) { i++; prob += np->m_c->m_prob; np = np->m_right; } 

Split the case tag catalog specified that the two halves have equal probability.

 if (i > 2) { npp = head; remaining = *npp; profile_probability pivot_prob = prob.apply_scale (1, 2); while (1) { prob -= (*npp)->m_c->m_prob; if ((prob.initialized_p () && prob < pivot_prob) || ! (*npp)->m_right) break; npp = &(*npp)->m_right; } np = *npp; *npp = 0; *head = np; np->m_parent = parent; np->m_left = remaining == np ? NULL : left; 

Recurse in the two halves to build the binary tree.

 balance_case_nodes (&np->m_left, np); balance_case_nodes (&np->m_right, np); np->m_c->m_subtree_prob = np->m_c->m_prob; if (np->m_left) np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob; if (np->m_right) np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob; } else { } } } 

Conclusion

We've seen the heuristics and lowering strategies gcc employs whenever compiling toggle statements, including:

• Compressing multiple case labels into a bitset.
• Transforming the toggle declaration into a jump table.
• Transforming the toggle declaration into a binary decision tree.

For anyone curious in delving deeper, I'd propose examining the gcc source code, and study this paper.

Finally, I desire to appreciate B.X.V., C.P., and V.P. for their feedback whenever penning this post