Fixture 215
switch on wide selector
C · 5 functions · 4 lanes · 17 of 20 function-lanes behave identically
2 of 4 lanes have a function that returns a different result after decompilation: clang-O2 (3/5), gcc-O2 (4/5).
A switch whose selector is 64 bits wide, with case labels above 2^32.
WHY THE WIDTH MATTERS. Every part of dispatch recovery is 32-bit-shaped by habit: the guard that proves a range bound reads a 32-bit compare, the table index is a 32-bit register, and DispatchTracker::bounded maps a register to a u64 bound that is nevertheless only ever ESTABLISHED from a 32-bit comparison. A 64-bit selector changes three things at once — the compare is against a wide immediate (often itself from a literal pool), the index must be truncated before it can address a table, and a case label above 2^32 cannot be a table offset at all, so the compiler must emit a comparison tree for the high labels and may emit a table for a dense low cluster.
That mixture — a tree over clusters, with a table inside one cluster — is the shape where a recogniser that assumes "one dispatch per switch" loses the arms it did not expect.
Every existing switch fixture is 32-bit: 04_switch_shapes, 106_switch_shapes_dense_sparse, 154_wide_switch (wide in ARM COUNT, not in selector width), 186_defaultless_guarded_switch, 204_adjacent_dispatch_tables. None declares a uint64_t selector, and none has a label that does not fit in 32 bits.
115_enum_semantics covers the underlying type of an enum, which is a different question: an enum's constants are small.
#include <stdint.h>
/* A `switch` whose selector is 64 bits wide, with case labels above 2^32.
*
* WHY THE WIDTH MATTERS. Every part of dispatch recovery is 32-bit-shaped by
* habit: the guard that proves a range bound reads a 32-bit compare, the table
* index is a 32-bit register, and `DispatchTracker::bounded` maps a register to
* a `u64` bound that is nevertheless only ever ESTABLISHED from a 32-bit
* comparison. A 64-bit selector changes three things at once — the compare is
* against a wide immediate (often itself from a literal pool), the index must
* be truncated before it can address a table, and a case label above 2^32
* cannot be a table offset at all, so the compiler must emit a comparison tree
* for the high labels and may emit a table for a dense low cluster.
*
* That mixture — a tree over clusters, with a table inside one cluster — is the
* shape where a recogniser that assumes "one dispatch per switch" loses the
* arms it did not expect.
*
* Every existing switch fixture is 32-bit: `04_switch_shapes`,
* `106_switch_shapes_dense_sparse`, `154_wide_switch` (wide in ARM COUNT, not
* in selector width), `186_defaultless_guarded_switch`,
* `204_adjacent_dispatch_tables`. None declares a `uint64_t` selector, and none
* has a label that does not fit in 32 bits.
*
* `115_enum_semantics` covers the underlying type of an enum, which is a
* different question: an enum's constants are small.
*/
/* Dense 64-bit labels in the low range: a table is legal here, and the selector
* must be truncated to index it. */
__attribute__((noinline)) int32_t wide_selector_dense(uint64_t op) {
switch (op) {
case 0: return 10;
case 1: return 11;
case 2: return 12;
case 3: return 13;
case 4: return 14;
case 5: return 15;
case 6: return 16;
case 7: return 17;
default: return -1;
}
}
/* Labels ABOVE 2^32: no table can address these, so every target emits
* comparisons against wide constants. */
__attribute__((noinline)) int32_t wide_selector_high_labels(uint64_t op) {
switch (op) {
case 0x100000000ull: return 20;
case 0x100000001ull: return 21;
case 0x200000000ull: return 22;
case 0xFFFFFFFFFFFFFFFFull: return 23;
default: return -1;
}
}
/* A dense low cluster AND high labels in one switch — a comparison tree whose
* leaves include a jump table. */
__attribute__((noinline)) int32_t wide_selector_mixed(uint64_t op) {
switch (op) {
case 0: return 30;
case 1: return 31;
case 2: return 32;
case 3: return 33;
case 4: return 34;
case 5: return 35;
case 0x100000000ull: return 36;
case 0x8000000000000000ull: return 37;
default: return -1;
}
}
/* A SIGNED 64-bit selector with negative labels, so the guard is a signed
* comparison and an unsigned range proof would be wrong. */
__attribute__((noinline)) int32_t signed_wide_selector(int64_t op) {
switch (op) {
case -3: return 40;
case -2: return 41;
case -1: return 42;
case 0: return 43;
case 1: return 44;
case 2: return 45;
default: return -1;
}
}
/* CONTROL: the identical dense switch with a 32-bit selector. It must recover
* at least as well as the 64-bit version; if the wide one regresses and this
* does not, the width is the cause. */
__attribute__((noinline)) int32_t narrow_selector_control(uint32_t op) {
switch (op) {
case 0: return 10;
case 1: return 11;
case 2: return 12;
case 3: return 13;
case 4: return 14;
case 5: return 15;
case 6: return 16;
case 7: return 17;
default: return -1;
}
}Recovered C
Generated by glaurung decompile --style decbench at b47f6b43.
baseline.json records the result after recompiling the C and calling it beside the
original with seeded inputs.
clang -O2
3/5narrow_selector_control pass 4 lines
// glaurung: narrow_selector_control @ 0x1200
int32_t narrow_selector_control(uint32_t arg0) {
return (((unsigned long)((unsigned long)(arg0)) < (unsigned long)(8)) ? (unsigned long)((unsigned int)((arg0 + 10))) : 0xffffffff);
}signed_wide_selector pass 6 lines
// glaurung: signed_wide_selector @ 0x11e0
int32_t signed_wide_selector(int64_t arg0) {
long var0;
var0 = (arg0 + 3);
return (((unsigned long)(var0) < (unsigned long)(6)) ? (unsigned long)((unsigned int)((var0 + 40))) : 0xffffffff);
}wide_selector_dense pass 4 lines
// glaurung: wide_selector_dense @ 0x1100
int32_t wide_selector_dense(uint64_t arg0) {
return (((unsigned long)(arg0) < (unsigned long)(8)) ? (unsigned long)((unsigned int)((arg0 + 10))) : 0xffffffff);
}wide_selector_high_labels fail 21 lines
// glaurung: wide_selector_high_labels @ 0x1110
int32_t wide_selector_high_labels(uint64_t arg0) {
long var0;
var0 = 0x100000000;
if ((arg0 <= 0x100000000)) {
if ((arg0 == -1)) {
return 23;
}
if ((arg0 != var0)) {
return 0xffffffff;
}
return 20;
}
if ((arg0 == 0x200000000)) {
return 22;
}
if ((arg0 != 0x100000001)) {
return 0xffffffff;
}
return 21;
}wide_selector_mixed fail 13 lines
// glaurung: wide_selector_mixed @ 0x1170
int32_t wide_selector_mixed(uint64_t arg0) {
if (((unsigned long)(arg0) <= (unsigned long)(5))) {
/* unrecovered indirect jump through ((long)((int)(((arg0 == 0) ? 0xfffff1d8 : ((arg0 == 1) ? 0xfffff18b : ((arg0 == 2) ? 0xfffff1b5 : ((arg0 == 3) ? 0xfffff1bb : ((arg0 == 4) ? 0xfffff1c1 : ((arg0 == 5) ? 0xfffff1c7 : *(int *)((0x2000 + (arg0 * 4))))))))))) + 0x2000) */
}
if ((arg0 == (-0x7fffffffffffffffLL - 1LL))) {
return 37;
}
if ((arg0 != 0x100000000)) {
return 0xffffffff;
}
return 36;
}gcc -O2
4/5narrow_selector_control pass 4 lines
// glaurung: narrow_selector_control @ 0x1260
int32_t narrow_selector_control(uint32_t arg0) {
return (((unsigned long)(8) <= (unsigned long)((unsigned long)(arg0))) ? 0xffffffff : (unsigned long)((unsigned int)((arg0 + 10))));
}signed_wide_selector pass 4 lines
// glaurung: signed_wide_selector @ 0x1240
int32_t signed_wide_selector(int64_t arg0) {
return (((unsigned long)((arg0 + 3)) < (unsigned long)(6)) ? (unsigned long)((unsigned int)((arg0 + 43))) : 0xffffffff);
}wide_selector_dense pass 4 lines
// glaurung: wide_selector_dense @ 0x1100
int32_t wide_selector_dense(uint64_t arg0) {
return (((unsigned long)(8) <= (unsigned long)(arg0)) ? 0xffffffff : (unsigned long)((unsigned int)((arg0 + 10))));
}wide_selector_high_labels pass 15 lines
// glaurung: wide_selector_high_labels @ 0x1120
int32_t wide_selector_high_labels(uint64_t arg0) {
long ret;
if ((arg0 == 0x200000000)) {
return 22;
}
if (((unsigned long)(0x200000000) < (unsigned long)(arg0))) {
return ((arg0 == -1) ? 23 : 0xffffffff);
}
ret = 20;
if ((arg0 == 0x100000000)) {
return ret;
}
return ((arg0 == 0x100000001) ? 21 : 0xffffffff);
}wide_selector_mixed fail 10 lines
// glaurung: wide_selector_mixed @ 0x1190
int32_t wide_selector_mixed(uint64_t arg0) {
if (((unsigned long)(arg0) <= (unsigned long)(5))) {
/* unrecovered indirect jump through ((long)((int)(((arg0 == 0) ? 0xfffff1e0 : ((arg0 == 1) ? 0xfffff1f0 : ((arg0 == 2) ? 0xfffff200 : ((arg0 == 3) ? 0xfffff210 : ((arg0 == 4) ? 0xfffff220 : ((arg0 == 5) ? 0xfffff230 : *(int *)((0x2000 + (arg0 * 4))))))))))) + 0x2000) */
}
if ((arg0 != 0x100000000)) {
return ((arg0 == (-0x7fffffffffffffffLL - 1LL)) ? 37 : 0xffffffff);
}
return 36;
}clang -O0
5/5narrow_selector_control pass 25 lines
// glaurung: narrow_selector_control @ 0x1410
int32_t narrow_selector_control(uint32_t arg0) {
// x86-64 prologue: save rbp
switch (arg0) {
case 0:
return (unsigned int)(10);
case 1:
return (unsigned int)(11);
case 2:
return (unsigned int)(12);
case 3:
return (unsigned int)(13);
case 4:
return (unsigned int)(14);
case 5:
return (unsigned int)(15);
case 6:
return (unsigned int)(16);
case 7:
return (unsigned int)(17);
default:
return (unsigned int)(-1);
}
// x86-64 epilogue: restore rbp
}signed_wide_selector pass 23 lines
// glaurung: signed_wide_selector @ 0x1380
int32_t signed_wide_selector(int64_t arg0) {
long var1;
// x86-64 prologue: save rbp
var1 = (arg0 + 3);
switch (var1) {
case 0:
return (unsigned int)(40);
case 1:
return (unsigned int)(41);
case 2:
return (unsigned int)(42);
case 3:
return (unsigned int)(43);
case 4:
return (unsigned int)(44);
case 5:
return (unsigned int)(45);
default:
return (unsigned int)(-1);
}
// x86-64 epilogue: restore rbp
}wide_selector_dense pass 25 lines
// glaurung: wide_selector_dense @ 0x1100
int32_t wide_selector_dense(uint64_t arg0) {
// x86-64 prologue: save rbp
switch (arg0) {
case 0:
return 10;
case 1:
return 11;
case 2:
return 12;
case 3:
return 13;
case 4:
return 14;
case 5:
return 15;
case 6:
return 16;
case 7:
return 17;
default:
return (unsigned int)(-1);
}
// x86-64 epilogue: restore rbp
}wide_selector_high_labels pass 17 lines
// glaurung: wide_selector_high_labels @ 0x11a0
int32_t wide_selector_high_labels(uint64_t arg0) {
// x86-64 prologue: save rbp
switch (arg0) {
case -1:
return 23;
case 4294967296:
return 20;
case 4294967297:
return 21;
case 8589934592:
return 22;
default:
return (unsigned int)(-1);
}
// x86-64 epilogue: restore rbp
}wide_selector_mixed pass 25 lines
// glaurung: wide_selector_mixed @ 0x1250
int32_t wide_selector_mixed(uint64_t arg0) {
// x86-64 prologue: save rbp
switch (arg0) {
case -9223372036854775808:
return 37;
case 0:
return 30;
case 1:
return 31;
case 2:
return 32;
case 3:
return 33;
case 4:
return 34;
case 5:
return 35;
case 4294967296:
return 36;
default:
return (unsigned int)(-1);
}
// x86-64 epilogue: restore rbp
}gcc -O0
5/5narrow_selector_control pass 25 lines
// glaurung: narrow_selector_control @ 0x1308
int32_t narrow_selector_control(uint32_t arg0) {
// x86-64 prologue: save rbp
switch (arg0) {
case 0:
return 10;
case 1:
return 11;
case 2:
return 12;
case 3:
return 13;
case 4:
return 14;
case 5:
return 15;
case 6:
return 16;
case 7:
return 17;
default:
return 0xffffffff;
}
// x86-64 epilogue: restore rbp
}signed_wide_selector pass 21 lines
// glaurung: signed_wide_selector @ 0x129c
int32_t signed_wide_selector(int64_t arg0) {
// x86-64 prologue: save rbp
switch ((arg0 + 3)) {
case 0:
return 40;
case 1:
return 41;
case 2:
return 42;
case 3:
return 43;
case 4:
return 44;
case 5:
return 45;
default:
return 0xffffffff;
}
// x86-64 epilogue: restore rbp
}wide_selector_dense pass 25 lines
// glaurung: wide_selector_dense @ 0x10f9
int32_t wide_selector_dense(uint64_t arg0) {
// x86-64 prologue: save rbp
switch (arg0) {
case 0:
return 10;
case 1:
return 11;
case 2:
return 12;
case 3:
return 13;
case 4:
return 14;
case 5:
return 15;
case 6:
return 16;
case 7:
return 17;
default:
return 0xffffffff;
}
// x86-64 epilogue: restore rbp
}wide_selector_high_labels pass 25 lines
// glaurung: wide_selector_high_labels @ 0x1170
int32_t wide_selector_high_labels(uint64_t arg0) {
// x86-64 prologue: save rbp
if ((arg0 == -1)) {
return 23;
} else {
if ((arg0 == 0x200000000)) {
return 22;
} else {
if (((unsigned long)(0x200000000) < (unsigned long)(arg0))) {
// x86-64 epilogue: restore rbp
return 0xffffffff;
}
if ((arg0 == 0x100000000)) {
return 20;
} else {
if ((arg0 == 0x100000001)) {
return 21;
} else {
return 0xffffffff;
}
}
}
}
}wide_selector_mixed pass 36 lines
// glaurung: wide_selector_mixed @ 0x11e8
int32_t wide_selector_mixed(uint64_t arg0) {
// x86-64 prologue: save rbp
if ((arg0 == (-0x7fffffffffffffffLL - 1LL))) {
return 37;
}
if (((unsigned long)((-0x7fffffffffffffffLL - 1LL)) < (unsigned long)(arg0))) {
// x86-64 epilogue: restore rbp
return 0xffffffff;
}
if (((unsigned long)(5) < (unsigned long)(arg0))) {
if ((arg0 == 0x100000000)) {
return 36;
} else {
return 0xffffffff;
}
}
switch (arg0) {
case 0:
return 30;
case 1:
return 31;
case 2:
return 32;
case 3:
return 33;
case 4:
return 34;
case 5:
return 35;
default:
// x86-64 epilogue: restore rbp
return 0xffffffff;
}
// x86-64 epilogue: restore rbp
}