Switch Lowering in GCC

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.

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. For a more in-depth understanding, we can delve into the compiler's source code.

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. Following this, I will break down each section 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 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.

for (unsigned i = 1; i < l; i++) { tree elt = gimple_switch_label (m_switch, i); // ... tree low = CASE_LOW (elt); tree high = 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 concept of high and low value for each label. That is, contiguous case labels have already joined together at this stage.

For each case label, we allocate a simple_cluster. This cluster serves as a record, capturing the range of values associated with the label, the relevant output edge, and the likelihood of this cluster 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 transform the vector of clusters we have created. The name bit_test_cluster hints to the bitset lowering strategy we saw before.

/* Find jump table clusters. */ vec<cluster *> output2; auto_vec<cluster *> tmp; // ...

for (unsigned i = 0; i < output.length (); i++) { cluster *c = output[i]; if (c->get_type () != SIMPLE_CASE) { if (!tmp.is_empty ()) { // ... See below for what's here tmp.truncate (0); } output2.safe_push (c); } else tmp.safe_push (c); }

This section allocates a vector for the transformed cases and a scratch vector. Any case that wasn't altered during the bitset transformation process is gathered in this scratch vector. These cases are then processed and cleared whenever we come across an optimized cluster.

Essentially, in this section 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 convert these consecutive labels into a jump table and add the outcome to the output.

/* We still can have a temporary vector to test. */ 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 loop above.

// ...

bool expanded = try_switch_expansion (output2); release_clusters(output2); return expanded; }

Whatever is left goes through another pass, which turns the switch statement into a decision tree. The bitsets and jump table are leaves of the decision tree.

Let's dig further into bit_test_cluster::find_bit_tests. The high level structure of the code is as follow.

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

Subsequently, we iterate over the bitsets and apply a profitability heuristic. If the bitsets meet this heuristic, we emit a bit_test_cluster; otherwise, we keep the original 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++) { /* Set minimal # of clusters with i-th item to infinite. */ 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 dynamic programming, we'll use a vector of min_cluster_item structures. Each min_cluster_item has three components:

The dynamic programming is as follows. We want to find the minimum number of bitsets to represent the first i case labels.

The base case is straightforward, a single case label can be represented by a single bitset.

Suppose we have already have found the optimal number of bitsets for the first j case label, for all . We define to be the optimal number of splits for the first i elements. This means 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 assignment for the first i labels. If the last bitset starts at label , this assignment is also optimal when restricted to . Were this not the case, we could improve the assignment on as well.