glaurung

Fixture 106

switch shapes dense sparse

C · 3 functions · 4 lanes · 12 of 12 function-lanes behave identically

All 4 lanes recompile and return the same results as the original.

Three switch shapes that lower differently: a dense contiguous range becomes a jump table, a sparse one becomes a comparison tree, and a range with a single outlier becomes a hybrid.

tests/decompiler_fixtures/src/106_switch_shapes_dense_sparse.c source 
#include <stdint.h>

/* Three switch shapes that lower differently: a dense contiguous range becomes
 * a jump table, a sparse one becomes a comparison tree, and a range with a
 * single outlier becomes a hybrid. */

__attribute__((noinline)) int32_t dense_switch(int32_t selector) {
    switch (selector) {
    case 0: return 11;
    case 1: return 22;
    case 2: return 33;
    case 3: return 44;
    case 4: return 55;
    case 5: return 66;
    case 6: return 77;
    case 7: return 88;
    default: return -1;
    }
}

__attribute__((noinline)) int32_t sparse_switch(int32_t selector) {
    switch (selector) {
    case -1000: return 1;
    case 7: return 2;
    case 1009: return 3;
    case 65536: return 4;
    case 1000000: return 5;
    default: return -1;
    }
}

__attribute__((noinline)) int32_t hybrid_switch(int32_t selector) {
    int32_t total = 0;
    switch (selector) {
    case 1:
    case 2:
    case 3:
        total = 10;
        break;
    case 4:
        total = 20;
        __attribute__((fallthrough));
    case 5:
        total += 5;
        break;
    case 999999:
        total = 30;
        break;
    default:
        total = -1;
        break;
    }
    return total;
}

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 -O0

3/3
dense_switch pass 25 lines 
// glaurung: dense_switch @ 0x1100
int32_t dense_switch(int32_t arg0) {
    // x86-64 prologue: save rbp
    switch ((unsigned int)(arg0)) {
        case 0:
            return (unsigned int)(11);
        case 1:
            return (unsigned int)(22);
        case 2:
            return (unsigned int)(33);
        case 3:
            return (unsigned int)(44);
        case 4:
            return (unsigned int)(55);
        case 5:
            return (unsigned int)(66);
        case 6:
            return (unsigned int)(77);
        case 7:
            return (unsigned int)(88);
        default:
            return (unsigned int)(-1);
    }
    // x86-64 epilogue: restore rbp
}
hybrid_switch pass 27 lines 
// glaurung: hybrid_switch @ 0x1250
int32_t hybrid_switch(int32_t arg0) {
    int total;
    int var9;
    // x86-64 prologue: save rbp
    total = 0;
    if (((unsigned long)((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 1)))) < (unsigned long)(3))) {
        return 10;
    } else {
        if (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 4))) == 0)) {
            var9 = 25;
            return 25;
        } else {
            if (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 5))) == 0)) {
                var9 = ((unsigned int)(total) + 5);
                total = var9;
                // x86-64 epilogue: restore rbp
                return (unsigned int)(total);
            }
            if (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 0xf423f))) == 0)) {
                return 30;
            } else {
                return (unsigned int)(-1);
            }
        }
    }
}
sparse_switch pass 25 lines 
// glaurung: sparse_switch @ 0x11a0
int32_t sparse_switch(int32_t arg0) {
    // x86-64 prologue: save rbp
    if (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) + 1000))) == 0)) {
        return 1;
    } else {
        if (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 7))) == 0)) {
            return 2;
        } else {
            if (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 1009))) == 0)) {
                return 3;
            } else {
                if (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 0x10000))) == 0)) {
                    return 4;
                } else {
                    if (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 0xf4240))) == 0)) {
                        return 5;
                    } else {
                        return (unsigned int)(-1);
                    }
                }
            }
        }
    }
}

clang -O2

3/3
dense_switch pass 4 lines 
// glaurung: dense_switch @ 0x1100
int32_t dense_switch(int32_t arg0) {
    return (((unsigned long)((unsigned long)((unsigned int)(arg0))) < (unsigned long)(8)) ? (unsigned long)((unsigned int)(((arg0 + ((unsigned long)((unsigned int)((arg0 + (arg0 * 4)))) * 2)) + 11))) : 0xffffffff);
}
hybrid_switch pass 22 lines 
// glaurung: hybrid_switch @ 0x1170
int32_t hybrid_switch(int32_t arg0) {
    int total;
    long var2;
    if (((((unsigned long)((unsigned int)(arg0)) == 3) | ((long)(arg0) < 3)) != 0)) {
        if (((unsigned long)(3) <= (unsigned long)((unsigned long)((unsigned int)((arg0 - 1)))))) {
            return 0xffffffff;
        }
        return 10;
    }
    if (((unsigned long)((unsigned int)(arg0)) == 0xf423f)) {
        return 30;
    }
    var2 = (unsigned long)((unsigned int)(arg0));
    if (((unsigned long)((unsigned int)(arg0)) != 5)) {
        if (((unsigned long)((unsigned int)(arg0)) != 4)) {
            return 0xffffffff;
        }
        var2 = 25;
    }
    return (unsigned int)(var2);
}
sparse_switch pass 24 lines 
// glaurung: sparse_switch @ 0x1120
int32_t sparse_switch(int32_t arg0) {
    long ret;
    if (((((unsigned long)((unsigned int)(arg0)) == 1008) | ((long)(arg0) < 1008)) == 0)) {
        if (((unsigned long)((unsigned int)(arg0)) == 1009)) {
            return 3;
        }
        if (((unsigned long)((unsigned int)(arg0)) == 0x10000)) {
            return 4;
        }
        if (((unsigned long)((unsigned int)(arg0)) != 0xf4240)) {
            return 0xffffffff;
        }
        return 5;
    }
    ret = 1;
    if (((unsigned long)((unsigned int)(arg0)) == 0xfffffc18)) {
        return ret;
    }
    if (((unsigned long)((unsigned int)(arg0)) != 7)) {
        return 0xffffffff;
    }
    return 2;
}

gcc -O0

3/3
dense_switch pass 25 lines 
// glaurung: dense_switch @ 0x10f9
int32_t dense_switch(int32_t arg0) {
    // x86-64 prologue: save rbp
    switch ((unsigned long)((unsigned int)(arg0))) {
        case 0:
            return 11;
        case 1:
            return 22;
        case 2:
            return 33;
        case 3:
            return 44;
        case 4:
            return 55;
        case 5:
            return 66;
        case 6:
            return 77;
        case 7:
            return 88;
        default:
            return 0xffffffff;
    }
    // x86-64 epilogue: restore rbp
}
hybrid_switch pass 43 lines 
// glaurung: hybrid_switch @ 0x11e9
int32_t hybrid_switch(int32_t arg0) {
    int total;
    long t136;
    // x86-64 prologue: save rbp
    total = 0;
    if (((unsigned long)((unsigned int)(arg0)) == 0xf423f)) {
        return 30;
    }
    if (((((unsigned long)((unsigned int)(arg0)) == 0xf423f) | ((long)(arg0) < 0xf423f)) == 0)) {
        L_124e: ;
        total = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(total);
    }
    if (((unsigned long)((unsigned int)(arg0)) == 5)) {
        t136 = ((unsigned long)((unsigned int)(total)) + 5);
        total = t136;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(total);
    }
    if (((((unsigned long)((unsigned int)(arg0)) == 5) | ((long)(arg0) < 5)) == 0)) {
        total = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(total);
    }
    if (((((unsigned long)((unsigned int)(arg0)) == 3) | ((long)(arg0) < 3)) == 0)) {
        if (((unsigned long)((unsigned int)(arg0)) == 4)) {
            t136 = 25;
            total = 25;
        } else {
            total = -1;
        }
    } else {
        if (((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0)) == 0)) {
            total = 10;
        } else {
            goto L_124e;
        }
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(total);
}
sparse_switch pass 20 lines 
// glaurung: sparse_switch @ 0x116d
int32_t sparse_switch(int32_t arg0) {
    // x86-64 prologue: save rbp
    switch (arg0) {
        case 1000000:
            return 5;
        case 65536:
            return 4;
        case 1009:
            return 3;
        case -1000:
            return 1;
        case 7:
            return 2;
        default:
            // x86-64 epilogue: restore rbp
            return 0xffffffff;
    }
    // x86-64 epilogue: restore rbp
}

gcc -O2

3/3
dense_switch pass 11 lines 
// glaurung: dense_switch @ 0x1100
int32_t dense_switch(int32_t arg0) {
    long ret;
    int var0;
    ret = 0xffffffff;
    if (((unsigned long)((unsigned long)((unsigned int)(arg0))) <= (unsigned long)(7))) {
        var0 = (arg0 + 1);
        ret = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var0)) + ((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var0)) + ((unsigned long)((unsigned int)(var0)) * 4)))) * 2))));
    }
    return ret;
}
hybrid_switch pass 13 lines 
// glaurung: hybrid_switch @ 0x1180
int32_t hybrid_switch(int32_t arg0) {
    if (((unsigned long)((unsigned int)(arg0)) == 5)) {
        return 5;
    }
    if (((((unsigned long)((unsigned int)(arg0)) == 5) | ((long)(arg0) < 5)) == 0)) {
        return (((unsigned long)((unsigned int)(arg0)) == 0xf423f) ? 30 : 0xffffffff);
    }
    if (((unsigned long)((unsigned int)(arg0)) != 4)) {
        return (((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0)) == 0) ? 10 : 0xffffffff);
    }
    return 25;
}
sparse_switch pass 23 lines 
// glaurung: sparse_switch @ 0x1120
int32_t sparse_switch(int32_t arg0) {
    long ret;
    long t33;
    long var5;
    t33 = ((unsigned long)((unsigned int)(arg0)) - 1009);
    if (((unsigned long)((unsigned int)(arg0)) == 1009)) {
        return 3;
    }
    if (((((unsigned long)((unsigned int)(arg0)) == 1009) | ((long)(arg0) < 1009)) == 0)) {
        ret = 4;
        if (((unsigned long)((unsigned int)(arg0)) == 0x10000)) {
            return ret;
        }
        return (((unsigned long)((unsigned int)(arg0)) == 0xf4240) ? 5 : 0xffffffff);
    }
    ret = 1;
    if (((unsigned long)((unsigned int)(arg0)) == 0xfffffc18)) {
        return ret;
    }
    var5 = ((unsigned long)((unsigned int)(arg0)) == 7);
    return (unsigned int)(((var5 + (var5 * 2)) - 1));
}

← 213 fixtures