llvm / llvm/llvm-project

Proposal of a optimization of the switch operator.

Open
#195,453 1 comment 0 reactions 0 assignees View on GitHub
missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

I propose the optimization to improve the performance of the switch statement.

For convenience, the code examples are in C, but these optimizations are not specific to any particular language.

Example:
```
int foo(unsigned _BitInt(128) const value) {
switch (value){
case 0x9aaad5d1f1e7943a242691fc4b499d7uwb: return 1;
case 0x9acd009588af7eac2b617bfb8d8b89buwb: return 11;
case 0x9aef2b591f77691e329c65facfcd75fuwb: return 111;
case 0x9b11561cb63f539039d74ffa120f623uwb: return 2;
case 0x9b3380e04d073e02411239f954514e7uwb: return 22;
case 0x9b55aba3e3cf2874484d23f896933abuwb: return 222;
case 0x9b77d6677a9712e64f880df7d8d526fuwb: return 123;
case 0x9b9a012b115efd5856c2f7f71b17133uwb: return 321;
case 0x9bbc2beea826e7ca5dfde1f65d58ff7uwb: return 3;
case 0x9a8d490d1c78f2fa1dd8f3efcfe231fuwb: return 33;
case 0x9aaf73d0b340dd6c2513ddef12241e3uwb: return 333;
case 0x9ad19e944a08c7de2c4ec7ee54660a7uwb: return -1;
case 0x9af3c957e0d0b2503389b1ed96a7f6buwb: return -11;
default: return 0;
}
}
```
In such situations we can try to find a unique sequence of bits among the cases, apply the switch operator to that, and then compare for full equality with the original value.
In this example we have 13 cases, so we need to find at least 4 unique bits.
Here the unique bits are found at positions 79 through 82.
Here is the optimized code:
```
int foo_1(unsigned _BitInt(128) const value) {
switch ((char)(value >> 79 & 15)){
case 12:
if (value == 0x9aaad5d1f1e7943a242691fc4b499d7uwb) return 1;
goto default_label;
case 5:
if (value == 0x9acd009588af7eac2b617bfb8d8b89buwb) return 11;
goto default_label;
case 14:
if (value == 0x9aef2b591f77691e329c65facfcd75fuwb) return 111;
goto default_label;
case 7:
if (value == 0x9b11561cb63f539039d74ffa120f623uwb) return 2;
goto default_label;
case 0:
if (value == 0x9b3380e04d073e02411239f954514e7uwb) return 22;
goto default_label;
case 9:
if (value == 0x9b55aba3e3cf2874484d23f896933abuwb) return 222;
goto default_label;
case 2:
if (value == 0x9b77d6677a9712e64f880df7d8d526fuwb) return 123;
goto default_label;
case 11:
if (value == 0x9b9a012b115efd5856c2f7f71b17133uwb) return 321;
goto default_label;
case 4:
if (value == 0x9bbc2beea826e7ca5dfde1f65d58ff7uwb) return 3;
goto default_label;
case 15:
if (value == 0x9a8d490d1c78f2fa1dd8f3efcfe231fuwb) return 33;
goto default_label;
case 8:
if (value == 0x9aaf73d0b340dd6c2513ddef12241e3uwb) return 333;
goto default_label;
case 1:
if (value == 0x9ad19e944a08c7de2c4ec7ee54660a7uwb) return -1;
goto default_label;
case 10:
if (value == 0x9af3c957e0d0b2503389b1ed96a7f6buwb) return -11;
goto default_label;
default:
default_label:
return 0;
}
}
```
Benchmark (without the above functions):
```
int main(int const argc, const char* const argv[]) {
if (argc != 33) return 1;

[[gnu::aligned(alignof(_BitInt(128)))]]
int64_t items[32];

for (int idx = 0; idx < 16; idx += 1) {
sscanf(argv[idx * 2 + 1], "%"SCNi64, &items[idx * 2]);
sscanf(argv[idx * 2 + 2], "%"SCNi64, &items[idx * 2 + 1]);
}

// loading data into the processor cache
long product = 1;
for (size_t idx = 0; idx < 16; product *= foo(((const unsigned _BitInt(128)*)items)[idx]), idx += 1);
printf("product: %li\n", product);

// benchmark
long sum = 0;
unsigned long long const start = __builtin_readcyclecounter();
for (size_t idx = 0; idx < 16; sum += foo(((const unsigned _BitInt(128)*)items)[idx]), idx += 1);
unsigned long long const finish = __builtin_readcyclecounter();
unsigned long long const duration = finish - start;

printf("sum: %li\nduration:%llu\n", sum, duration);

return 0;
}
```
The benchmark was compiled with: `clang -std=c23 -O3 -march=znver1 bench.c -o bench`.
It was run with the command: `./bench -6754720905937249833 696559707847817539 232105937608540011 697843080028293925 -4416316272382789477 697160780894369770 2570510571163000367 698444153074846156 -2106298695945920345 697242006981741693 -2077911638828329121 697761853940922001 -4444703329500380701 696640933935189462 4908915204717460723 699045226121398387 260492994726131235 698362926987474233 -6783107963054841057 696039860888637231 2598897628280591591 698964000034026464 7247319838271921079 699646299167950618 -6494227911211118601 701368292220235388 4937302261835051947 699565073080578695 -8832632544765578957 700767219173683157 7275706895389512303 700166146127130926`
Each function was benchmarked 10 times; the 3 best and 3 worst results were discarded, and the average was calculated from the remaining 4. The duration values:
```
foo (default) – 4453
foo_1 (proposed) – 1890
```

Contributor guide

Open the contributing guide

Research direction

The issue names no source files or tests; start by reproducing the clang C23 benchmark and locating the compiler's switch-lowering implementation. Compare generated code and correctness for the proposed bit-selection approach, with the optimization and its performance validated before considering the work done.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.