glaurung

Fixture 39

counting radix sort

C · 2 functions · 4 lanes · 7 of 8 function-lanes behave identically

One lane has a function that returns a different result after decompilation: gcc-O2 (1/2).

Counting sort over a small key domain and an LSD radix sort over 4-bit digits. Both build a prefix-sum histogram and then scatter in reverse to remain stable; the scatter is an indirect write whose index is loaded.

tests/decompiler_fixtures/src/39_counting_radix_sort.c source 
#include <stdint.h>

/* Counting sort over a small key domain and an LSD radix sort over 4-bit
 * digits.  Both build a prefix-sum histogram and then scatter in reverse to
 * remain stable; the scatter is an indirect write whose index is loaded. */

#define RADIX_MAX 16
#define RADIX_BUCKETS 16

__attribute__((noinline)) int32_t
counting_sort_u8(uint8_t *values, int32_t count) {
    int32_t histogram[256];
    int32_t index;
    int32_t bucket;
    int32_t out;
    if (values == 0 || count < 0 || count > RADIX_MAX) {
        return -1;
    }
    for (bucket = 0; bucket < 256; ++bucket) {
        histogram[bucket] = 0;
    }
    for (index = 0; index < count; ++index) {
        histogram[values[index]] += 1;
    }
    out = 0;
    for (bucket = 0; bucket < 256; ++bucket) {
        int32_t remaining = histogram[bucket];
        while (remaining > 0 && out < count) {
            values[out] = (uint8_t)bucket;
            out += 1;
            remaining -= 1;
        }
    }
    return count;
}

__attribute__((noinline)) int32_t
radix_sort_u32(uint32_t *values, int32_t count) {
    uint32_t scratch[RADIX_MAX];
    int32_t histogram[RADIX_BUCKETS];
    int32_t shift;
    int32_t index;
    int32_t bucket;
    if (values == 0 || count < 0 || count > RADIX_MAX) {
        return -1;
    }
    for (shift = 0; shift < 32; shift += 4) {
        int32_t running = 0;
        for (bucket = 0; bucket < RADIX_BUCKETS; ++bucket) {
            histogram[bucket] = 0;
        }
        for (index = 0; index < count; ++index) {
            histogram[(values[index] >> shift) & 0xFu] += 1;
        }
        for (bucket = 0; bucket < RADIX_BUCKETS; ++bucket) {
            int32_t occupancy = histogram[bucket];
            histogram[bucket] = running;
            running += occupancy;
        }
        for (index = 0; index < count; ++index) {
            int32_t slot = (int32_t)((values[index] >> shift) & 0xFu);
            scratch[histogram[slot]] = values[index];
            histogram[slot] += 1;
        }
        for (index = 0; index < count; ++index) {
            values[index] = scratch[index];
        }
    }
    return count;
}

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.

gcc -O2

1/2
counting_sort_u8 pass 82 lines 
// glaurung: counting_sort_u8 @ 0x1140
int32_t counting_sort_u8(uint8_t * arg0, int32_t arg1) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int bucket;
    int remaining;
    int out;
    int index;
    long df_1;
    long local_10;
    unsigned char local_418[1024];
    long t1;
    long t136;
    long t153;
    long var11;
    long var12;
    int var13;
    long var17;
    long var19;
    long var2;
    long var21;
    long var22;
    long var3;
    long var31;
    long var32;
    long var5;
    df_1 = 0;
    local_10 = (long)(0x28);
    var2 = 0;
    if ((arg0 == 0)) {
        L_121a: ;
        var3 = 0xffffffff;
    } else {
        var3 = (unsigned long)((unsigned int)(arg1));
        if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
            goto L_121a;
        } else {
            var5 = (long)arg0;
            t136 = (long)(&local_418[0]);
            t1 = 128;
            while ((t1 != 0)) {
                *(long *)(t136) = var2;
                t136 = (t136 + ((df_1 != 0) ? -8 : 8));
                t1 = (t1 - 1);
            }
            if (((unsigned long)((unsigned int)(arg1)) != 0)) {
                var11 = var5;
                var12 = ((var5 + (unsigned long)((unsigned int)((arg1 - 1)))) + 1);
                do {
                    var13 = (unsigned int)((unsigned char)(*(char *)((var11))));
                    var11 = (var11 + 1);
                    *(int *)((&local_418[0] + (var13 * 4))) = (*(int *)((&local_418[0] + (var13 * 4))) + 1);
                } while ((var12 != var11));
            }
            bucket = 0;
            var17 = 0;
            do {
                remaining = (unsigned long)((unsigned int)(*(int *)((&local_418[0] + (bucket * 4)))));
                var19 = var17;
                if ((((((unsigned int)(var3) == (unsigned int)(var17)) | ((long)((int)(var3)) < (long)((int)(var17)))) == 0) && ((((unsigned long)((unsigned int)(remaining)) == 0) | ((long)(remaining) < 0)) == 0))) {
                    var21 = (unsigned long)((unsigned int)(bucket));
                    var22 = (unsigned long)((unsigned int)((var17 + remaining)));
                    out = (long)((int)((var17 + 1)));
                    do {
                        *(signed char *)((var5 + out - 0x1)) = var21;
                        var19 = (unsigned long)((unsigned int)(out));
                        t153 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var22)) - out)));
                        var31 = ((((unsigned int)(var3) == (unsigned int)(out)) | ((long)((int)(var3)) < (long)(out))) == 0);
                        out = (out + 1);
                    } while (((unsigned long)((unsigned char)((((((unsigned long)((unsigned int)(t153)) == 0) | ((long)((int)(t153)) < 0)) == 0) & (var31 & 255)))) != 0));
                }
                var32 = ((unsigned long)((unsigned int)(bucket)) + 1);
                bucket = var32;
                var17 = var19;
            } while ((var32 != 256));
        }
    }
    if ((local_10 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: tear down frame
    return (unsigned int)(var3);
}
radix_sort_u32 fail 104 lines 
// glaurung: radix_sort_u32 @ 0x1230
int32_t radix_sort_u32(uint32_t * arg0, int32_t arg1) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    extern void * memcpy(void *, const void *, __SIZE_TYPE__);
    int occupancy;
    int bucket;
    int index;
    int running;
    int shift;
    long local_40;
    unsigned char local_88[64];
    unsigned char local_c8[64];
    int local_cc;
    long var10;
    long var12;
    long var13;
    long var19;
    long var21;
    long var26;
    long var27;
    long var3;
    long var30;
    long var34;
    long var36;
    long var37;
    long var43;
    long var44;
    void * var50;
    int var53;
    long var8;
    local_40 = (long)(0x28);
    if ((arg0 == 0)) {
        L_1372: ;
        var3 = 0xffffffff;
    } else {
        var3 = (unsigned long)((unsigned int)(arg1));
        if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
            goto L_1372;
        } else {
            var8 = (long)((((long)arg0 + ((unsigned long)((unsigned int)((arg1 - 1))) * 4)) + 4));
            var10 = (long)((&local_88[0] + 64));
            var12 = 0;
            var13 = (long)arg0;
            do {
                var19 = var13;
                *(int *)(&local_88[0]) = 0;
                *(int *)((&local_88[0] + 4)) = 0;
                *(int *)((&local_88[0] + 8)) = 0;
                *(int *)((&local_88[0] + 12)) = 0;
                *(int *)((&local_88[0] + 16)) = 0;
                *(int *)((&local_88[0] + 20)) = 0;
                *(int *)((&local_88[0] + 24)) = 0;
                *(int *)((&local_88[0] + 28)) = 0;
                *(int *)((&local_88[0] + 32)) = 0;
                *(int *)((&local_88[0] + 36)) = 0;
                *(int *)((&local_88[0] + 40)) = 0;
                *(int *)((&local_88[0] + 44)) = 0;
                *(int *)((&local_88[0] + 48)) = 0;
                *(int *)((&local_88[0] + 52)) = 0;
                *(int *)((&local_88[0] + 56)) = 0;
                *(int *)((&local_88[0] + 60)) = 0;
                if (((unsigned long)((unsigned int)(var3)) != 0)) {
                    do {
                        var21 = (unsigned long)((unsigned int)(*(int *)((var19))));
                        var19 = (var19 + 4);
                        var26 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var21)) >> (var12 & 31)))) & 15)));
                        *(int *)((&local_88[0] + (var26 * 4))) = (*(int *)((&local_88[0] + (var26 * 4))) + 1);
                    } while ((var8 != var19));
                }
                var27 = (long)(&local_88[0]);
                var30 = 0;
                do {
                    occupancy = (unsigned long)((unsigned int)(*(int *)((var27))));
                    *(int *)((var27)) = var30;
                    var27 = (var27 + 4);
                    var30 = (unsigned long)((unsigned int)((var30 + occupancy)));
                } while ((var27 != var10));
                var34 = var12;
                if (((unsigned long)((unsigned int)(var3)) != 0)) {
                    var36 = var13;
                    do {
                        var37 = (unsigned long)((unsigned int)(*(int *)((var36))));
                        var36 = (var36 + 4);
                        var43 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var37)) >> (var12 & 31)))) & 15)));
                        var44 = (long)((int)(*(int *)((&local_88[0] + (var43 * 4)))));
                        *(int *)((&local_c8[0] + (var44 * 4))) = var37;
                        *(int *)((&local_88[0] + (var43 * 4))) = (var44 + 1);
                    } while ((var8 != var36));
                    local_cc = var12;
                    var50 = ((void * (*)(void))memcpy)();
                    var13 = (long)var50;
                    var34 = (unsigned long)((unsigned int)(local_cc));
                }
                var53 = (var34 + 4);
                var12 = (unsigned long)((unsigned int)(var53));
            } while (((unsigned long)((unsigned int)(var53)) != 32));
        }
    }
    if ((local_40 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: tear down frame
    return (unsigned int)(var3);
}

clang -O0

2/2
counting_sort_u8 pass 66 lines 
// glaurung: counting_sort_u8 @ 0x1100
__attribute__((no_stack_protector)) int32_t counting_sort_u8(uint8_t * arg0, int32_t arg1) {
    int bucket;
    int index;
    int out;
    int remaining;
    int local_4;
    unsigned char local_420[1024];
    signed char local_431;
    long var15;
    int var7;
    if ((arg0 != 0)) {
        if ((0 <= (long)(arg1))) {
            if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                goto L_113d;
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_113d: ;
    bucket = 0;
    L_1147: ;
    if (((long)(bucket) < 256)) {
        *(int *)((&local_420[0] + ((long)(bucket) * 4))) = 0;
        bucket = ((unsigned int)(bucket) + 1);
        goto L_1147;
    }
    index = 0;
    L_1187: ;
    if ((index < arg1)) {
        var7 = (unsigned int)((unsigned char)(arg0[index]));
        *(int *)((&local_420[0] + (var7 * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_420[0] + (var7 * 4))))) + 1);
        index = ((unsigned int)(index) + 1);
        goto L_1187;
    }
    out = 0;
    bucket = 0;
    L_11de: ;
    if ((256 <= (long)(bucket))) {
        goto L_128e;
    }
    var15 = (unsigned long)((unsigned int)(*(int *)((&local_420[0] + ((long)(bucket) * 4)))));
    remaining = var15;
    L_1202: ;
    local_431 = 0;
    if (((((unsigned long)((unsigned int)(remaining)) == 0) | ((long)(remaining) < 0)) == 0)) {
        local_431 = (out < arg1);
    }
    if (((unsigned long)((unsigned char)((local_431 & 1))) != 0)) {
        arg0[out] = bucket;
        out = ((unsigned int)(out) + 1);
        var15 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(remaining)) - 1)));
        remaining = var15;
        goto L_1202;
    }
    goto L_127a;
    L_127a: ;
    bucket = ((unsigned int)(bucket) + 1);
    goto L_11de;
    L_128e: ;
    local_4 = arg1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
radix_sort_u32 pass 57 lines 
// glaurung: radix_sort_u32 @ 0x12a0
__attribute__((no_stack_protector)) int32_t radix_sort_u32(uint32_t * arg0, int32_t arg1) {
    int shift;
    int running;
    int bucket;
    int index;
    int occupancy;
    int slot;
    int local_4;
    unsigned char local_60[64];
    unsigned char local_a0[64];
    long var14;
    // x86-64 prologue: save rbp, frame 64 bytes
    if ((arg0 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((long)(arg1) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    shift = 0;
    while (((long)(shift) < 32)) {
        running = 0;
        for (bucket = 0; ((long)(bucket) < 16); bucket++) {
            *(int *)((&local_a0[0] + ((long)(bucket) * 4))) = 0;
        }
        for (index = 0; (index < arg1); index++) {
            var14 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0[(long)(index)])) >> ((unsigned long)((unsigned int)(shift)) & 31)))) & 15)));
            *(int *)((&local_a0[0] + (var14 * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_a0[0] + (var14 * 4))))) + 1);
        }
        for (bucket = 0; ((long)(bucket) < 16); bucket++) {
            occupancy = *(int *)((&local_a0[0] + ((long)(bucket) * 4)));
            *(int *)((&local_a0[0] + ((long)(bucket) * 4))) = running;
            running = ((unsigned int)(occupancy) + running);
        }
        for (index = 0; (index < arg1); index++) {
            slot = ((unsigned int)(((unsigned long)((unsigned int)(arg0[(long)(index)])) >> ((unsigned long)((unsigned int)(shift)) & 31))) & 15);
            *(int *)((&local_60[0] + ((long)((int)(*(int *)((&local_a0[0] + ((long)(slot) * 4))))) * 4))) = arg0[(long)(index)];
            *(int *)((&local_a0[0] + ((long)(slot) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_a0[0] + ((long)(slot) * 4))))) + 1);
        }
        for (index = 0; (index < arg1); index++) {
            arg0[(long)(index)] = *(int *)((&local_60[0] + ((long)(index) * 4)));
        }
        shift = ((unsigned int)(shift) + 4);
    }
    local_4 = arg1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

2/2
counting_sort_u8 pass 125 lines 
// glaurung: counting_sort_u8 @ 0x1120
__attribute__((no_stack_protector)) int32_t counting_sort_u8(uint8_t * arg0, int32_t arg1) {
    extern void * memset(void *, int, __SIZE_TYPE__);
    int index;
    int out;
    int remaining;
    int bucket;
    unsigned char local_438[1080];
    long of_45;
    long rbp;
    long ret;
    long sf_45;
    long var1;
    void * var10;
    long var12;
    long var13;
    long var17;
    long var2;
    int var21;
    int var22;
    int var23;
    int var24;
    long var25;
    long var28;
    long var3;
    long var30;
    int var31;
    long var32;
    long var35;
    long var38;
    long var39;
    long var4;
    void * var46;
    long var48;
    long var49;
    long var5;
    int var50;
    long var6;
    long var8;
    ret = 0xffffffff;
    if ((arg0 == 0)) {
        return ret;
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return ret;
    }
    *(long *)((&local_438[0] + 1072)) = rbp;
    *(long *)((&local_438[0] + 1064)) = var1;
    *(long *)((&local_438[0] + 1056)) = var2;
    *(long *)((&local_438[0] + 1048)) = var3;
    *(long *)((&local_438[0] + 1040)) = var4;
    *(long *)((&local_438[0] + 1032)) = var5;
    var6 = (long)arg0;
    var8 = 0;
    var10 = memset((void *)(&local_438[0]), 0, (__SIZE_TYPE__)(1024));
    var12 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)((unsigned int)(arg1)) != 0)) {
        var13 = (unsigned long)((unsigned int)(var12));
        var17 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var12)) & 3)));
        if (((unsigned long)(3) <= (unsigned long)(((unsigned long)((unsigned int)(var12)) - 1)))) {
            var13 = (unsigned long)((unsigned int)((var13 & -4)));
            index = 0;
            do {
                var21 = (unsigned int)((unsigned char)(*(char *)((var6 + index))));
                *(int *)((&local_438[0] + (var21 * 4))) = (*(int *)((&local_438[0] + (var21 * 4))) + 1);
                var22 = (unsigned int)((unsigned char)(*(char *)((var6 + index + 0x1))));
                *(int *)((&local_438[0] + (var22 * 4))) = (*(int *)((&local_438[0] + (var22 * 4))) + 1);
                var23 = (unsigned int)((unsigned char)(*(char *)((var6 + index + 0x2))));
                *(int *)((&local_438[0] + (var23 * 4))) = (*(int *)((&local_438[0] + (var23 * 4))) + 1);
                var24 = (unsigned int)((unsigned char)(*(char *)((var6 + index + 0x3))));
                *(int *)((&local_438[0] + (var24 * 4))) = (*(int *)((&local_438[0] + (var24 * 4))) + 1);
                index = (index + 4);
                var25 = (unsigned long)((unsigned int)(index));
            } while ((var13 != index));
        } else {
            var25 = 0;
        }
        if ((var17 != 0)) {
            var28 = (var25 + var6);
            var30 = 0;
            while ((var17 != var30)) {
                var31 = (unsigned int)((unsigned char)(*(char *)((var28 + var30))));
                *(int *)((&local_438[0] + (var31 * 4))) = (*(int *)((&local_438[0] + (var31 * 4))) + 1);
                var30 = (var30 + 1);
            }
        }
    }
    var32 = (long)((int)(var12));
    var35 = 0;
    out = var8;
    do {
        remaining = (unsigned long)((unsigned int)(*(int *)((&local_438[0] + (var35 * 4)))));
        if (((((unsigned long)((unsigned int)(remaining)) == 0) | ((long)(remaining) < 0)) == 0)) {
            if (((long)(out) < (long)((int)(var12)))) {
                var38 = (long)(out);
                var39 = (unsigned long)((unsigned int)((remaining - 1)));
                var46 = memset((void *)((var6 + (long)(out))), (int)((unsigned long)((unsigned int)(var35))), (__SIZE_TYPE__)(((((unsigned long)((unsigned int)(var39)) == 0) ? var39 : (((unsigned long)((unsigned long)((unsigned int)(var39))) <= (unsigned long)((unsigned long)((unsigned int)(((~(unsigned long)((unsigned int)(out))) + var12))))) ? var39 : (unsigned long)((unsigned int)(((~(unsigned long)((unsigned int)(out))) + var12))))) + 1)));
                var12 = (unsigned long)((unsigned int)(arg1));
                var48 = (var38 + 1);
                var49 = (unsigned long)((unsigned int)(out));
                while (1) {
                    var50 = (var49 + 1);
                    var49 = (unsigned long)((unsigned int)(var50));
                    out = (unsigned long)((unsigned int)(var50));
                    if (((unsigned long)((unsigned long)((unsigned int)(remaining))) < (unsigned long)(2))) {
                        break;
                    }
                    remaining = (unsigned long)((unsigned int)((remaining - 1)));
                    sf_45 = ((var48 - var32) < 0);
                    of_45 = ((var48 < var32) ^ ((var48 - var32) < 0));
                    var48 = (var48 + 1);
                    if (((sf_45 ^ of_45) == 0)) {
                        out = var49;
                        break;
                    }
                }
            }
        }
        bucket = (var35 + 1);
        var35 = (unsigned long)((unsigned int)(bucket));
    } while ((bucket != 256));
    ret = (unsigned long)((unsigned int)(var12));
    // x86-64 epilogue: tear down frame
    return (unsigned int)(var12);
}
radix_sort_u32 pass 255 lines 
// glaurung: radix_sort_u32 @ 0x1270
__attribute__((no_stack_protector)) int32_t radix_sort_u32(uint32_t * arg0, int32_t arg1) {
    extern void * memcpy(void *, const void *, __SIZE_TYPE__);
    int shift;
    int bucket;
    int index;
    int occupancy;
    int running;
    int slot;
    long cf_44;
    unsigned char local_78[120];
    unsigned char local_d8[96];
    unsigned char local_e8[16];
    long ret;
    long var0;
    long var1;
    int var10;
    long var103;
    long var104;
    long var109;
    int var11;
    long var110;
    long var113;
    long var118;
    long var119;
    int var12;
    long var122;
    long var127;
    long var128;
    int var13;
    void * var131;
    long var25;
    long var26;
    long var27;
    long var28;
    long var29;
    long var30;
    long var31;
    long var32;
    long var33;
    long var34;
    long var35;
    long var38;
    long var43;
    long var49;
    long var53;
    long var55;
    long var56;
    long var57;
    long var58;
    long var59;
    long var6;
    long var60;
    long var61;
    long var62;
    long var65;
    long var69;
    int var70;
    int var72;
    int var74;
    int var76;
    int var78;
    int var80;
    int var82;
    int var84;
    int var86;
    int var88;
    int var91;
    int var93;
    int var96;
    int var99;
    // x86-64 prologue: save callee registers, frame 48 bytes
    ret = 0xffffffff;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var0 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var1 = (long)arg0;
    *(long *)((&local_d8[0] + 88)) = ((unsigned long)((unsigned int)(var0)) * 4);
    *(long *)((&local_d8[0] + 72)) = ((unsigned long)((unsigned int)(var0)) - 1);
    *(long *)((&local_d8[0] + 80)) = (unsigned int)(var0);
    var6 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var0)) & -2)));
    var10 = 0;
    var11 = 0;
    var12 = 0;
    var13 = 0;
    *(int *)((&local_d8[0] + 64)) = var0;
    shift = 0;
    do {
        *(int *)((&local_d8[0] + 48)) = var10;
        *(int *)((&local_d8[0] + 52)) = var11;
        *(int *)((&local_d8[0] + 56)) = var12;
        *(int *)((&local_d8[0] + 60)) = var13;
        *(int *)((&local_d8[0] + 32)) = var10;
        *(int *)((&local_d8[0] + 36)) = var11;
        *(int *)((&local_d8[0] + 40)) = var12;
        *(int *)((&local_d8[0] + 44)) = var13;
        *(int *)((&local_d8[0] + 16)) = var10;
        *(int *)((&local_d8[0] + 20)) = var11;
        *(int *)((&local_d8[0] + 24)) = var12;
        *(int *)((&local_d8[0] + 28)) = var13;
        *(int *)(&local_d8[0]) = var10;
        *(int *)((&local_d8[0] + 4)) = var11;
        *(int *)((&local_d8[0] + 8)) = var12;
        *(int *)((&local_d8[0] + 12)) = var13;
        *(int *)((&local_e8[0] + 12)) = 0;
        *(int *)((&local_e8[0] + 8)) = 0;
        var25 = 0;
        *(int *)((&local_e8[0] + 4)) = 0;
        *(int *)(&local_e8[0]) = 0;
        var26 = 0;
        var27 = 0;
        var28 = 0;
        var29 = 0;
        var30 = 0;
        var31 = 0;
        var32 = 0;
        var33 = 0;
        var34 = 0;
        var35 = 0;
        if (((unsigned long)((unsigned int)(var0)) != 0)) {
            if ((*(long *)((&local_d8[0] + 72)) == 0)) {
                var38 = 0;
                if (((unsigned long)((unsigned char)((*(char *)((&local_d8[0] + 80)) & 1))) != 0)) {
                    L_139f: ;
                    var43 = (unsigned long)((unsigned int)((((unsigned long)((unsigned int)(*(int *)((var1 + var38 * 4)))) >> ((unsigned long)((unsigned int)(shift)) & 63)) & 15)));
                    *(int *)((&local_d8[0] + (var43 * 4))) = (*(int *)((&local_d8[0] + (var43 * 4))) + 1);
                } else {
                }
            } else {
                var38 = 0;
                do {
                    var49 = (unsigned long)((unsigned int)((((unsigned long)((unsigned int)(*(int *)((var1 + var38 * 4)))) >> ((unsigned long)((unsigned int)(shift)) & 63)) & 15)));
                    *(int *)((&local_d8[0] + (var49 * 4))) = (*(int *)((&local_d8[0] + (var49 * 4))) + 1);
                    var53 = (unsigned long)((unsigned int)((((unsigned long)((unsigned int)(*(int *)((var1 + var38 * 4 + 0x4)))) >> ((unsigned long)((unsigned int)(shift)) & 63)) & 15)));
                    *(int *)((&local_d8[0] + (var53 * 4))) = (*(int *)((&local_d8[0] + (var53 * 4))) + 1);
                    var38 = (var38 + 2);
                } while ((var6 != var38));
                if (((unsigned long)((unsigned char)((*(char *)((&local_d8[0] + 80)) & 1))) == 0)) {
                    goto L_13af;
                }
                goto L_139f;
            }
            L_13af: ;
            *(int *)((&local_e8[0] + 4)) = *(int *)(&local_d8[0]);
            var25 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 4))));
            var55 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 8))));
            var56 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 12))));
            var57 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 16))));
            var58 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 20))));
            var59 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 24))));
            var60 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 28))));
            var61 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 32))));
            var62 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 36))));
            *(int *)((&local_d8[0] + 68)) = *(int *)((&local_d8[0] + 40));
            *(int *)((&local_e8[0] + 8)) = *(int *)((&local_d8[0] + 44));
            var65 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 48))));
            *(int *)((&local_e8[0] + 12)) = *(int *)((&local_d8[0] + 52));
            *(int *)(&local_e8[0]) = *(int *)((&local_d8[0] + 56));
            var26 = var57;
            var27 = var65;
            var28 = var58;
            var29 = var56;
            var30 = var55;
            var31 = var62;
            var32 = var61;
            var33 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 68))));
            var34 = var60;
            var35 = var59;
        }
        var69 = (unsigned long)((unsigned int)(*(int *)((&local_e8[0] + 4))));
        var70 = (var25 + var69);
        *(int *)(&local_d8[0]) = 0;
        *(int *)((&local_d8[0] + 4)) = var69;
        var72 = (var30 + (unsigned int)(var70));
        *(int *)((&local_d8[0] + 8)) = var70;
        var74 = (var29 + (unsigned int)(var72));
        *(int *)((&local_d8[0] + 12)) = var72;
        var76 = (var26 + (unsigned int)(var74));
        *(int *)((&local_d8[0] + 16)) = var74;
        var78 = (var28 + (unsigned int)(var76));
        *(int *)((&local_d8[0] + 20)) = var76;
        var80 = (var35 + (unsigned int)(var78));
        *(int *)((&local_d8[0] + 24)) = var78;
        var82 = (var34 + (unsigned int)(var80));
        *(int *)((&local_d8[0] + 28)) = var80;
        var84 = (var32 + (unsigned int)(var82));
        *(int *)((&local_d8[0] + 32)) = var82;
        var86 = (var31 + (unsigned int)(var84));
        *(int *)((&local_d8[0] + 36)) = var84;
        var88 = (var33 + (unsigned int)(var86));
        *(int *)((&local_d8[0] + 40)) = var86;
        var91 = ((unsigned int)(*(int *)((&local_e8[0] + 8))) + (unsigned int)(var88));
        *(int *)((&local_d8[0] + 44)) = var88;
        var93 = (var27 + (unsigned int)(var91));
        *(int *)((&local_d8[0] + 48)) = var91;
        var96 = ((unsigned int)(*(int *)((&local_e8[0] + 12))) + (unsigned int)(var93));
        *(int *)((&local_d8[0] + 52)) = var93;
        var99 = ((unsigned int)(*(int *)(&local_e8[0])) + (unsigned int)(var96));
        *(int *)((&local_d8[0] + 56)) = var96;
        *(int *)((&local_d8[0] + 60)) = var99;
        var0 = (unsigned long)((unsigned int)(*(int *)((&local_d8[0] + 64))));
        if (((unsigned long)((unsigned int)(var0)) != 0)) {
            if ((*(long *)((&local_d8[0] + 72)) == 0)) {
                var103 = 0;
                if (((unsigned long)((unsigned char)((*(char *)((&local_d8[0] + 80)) & 1))) != 0)) {
                    L_14fd: ;
                    var104 = (unsigned long)((unsigned int)(*(int *)((var1 + var103 * 4))));
                    var109 = (unsigned long)((unsigned int)((((unsigned long)(var104) >> ((unsigned long)((unsigned int)(shift)) & 63)) & 15)));
                    var110 = (long)((int)(*(int *)((&local_d8[0] + (var109 * 4)))));
                    *(int *)((&local_78[0] + (var110 * 4))) = var104;
                    *(int *)((&local_d8[0] + (var109 * 4))) = (var110 + 1);
                } else {
                }
            } else {
                var103 = 0;
                do {
                    var113 = (unsigned long)((unsigned int)(*(int *)((var1 + var103 * 4))));
                    var118 = (unsigned long)((unsigned int)((((unsigned long)(var113) >> ((unsigned long)((unsigned int)(shift)) & 63)) & 15)));
                    var119 = (long)((int)(*(int *)((&local_d8[0] + (var118 * 4)))));
                    *(int *)((&local_78[0] + (var119 * 4))) = var113;
                    *(int *)((&local_d8[0] + (var118 * 4))) = (var119 + 1);
                    var122 = (unsigned long)((unsigned int)(*(int *)((var1 + var103 * 4 + 0x4))));
                    var127 = (unsigned long)((unsigned int)((((unsigned long)(var122) >> ((unsigned long)((unsigned int)(shift)) & 63)) & 15)));
                    var128 = (long)((int)(*(int *)((&local_d8[0] + (var127 * 4)))));
                    *(int *)((&local_78[0] + (var128 * 4))) = var122;
                    *(int *)((&local_d8[0] + (var127 * 4))) = (var128 + 1);
                    var103 = (var103 + 2);
                } while ((var6 != var103));
                if (((unsigned long)((unsigned char)((*(char *)((&local_d8[0] + 80)) & 1))) == 0)) {
                    goto L_151b;
                }
                goto L_14fd;
            }
            L_151b: ;
            if (((unsigned long)((unsigned int)(var0)) != 0)) {
                var131 = memcpy((void *)(var1), (const void *)(&local_78[0]), (__SIZE_TYPE__)(*(long *)((&local_d8[0] + 88))));
                var10 = 0;
                var11 = 0;
                var12 = 0;
                var13 = 0;
            }
        }
        cf_44 = ((unsigned long)((unsigned long)((unsigned int)(shift))) < (unsigned long)(28));
        shift = (unsigned long)((unsigned int)((shift + 4)));
    } while ((cf_44 != 0));
    ret = (unsigned long)((unsigned int)(var0));
    // x86-64 epilogue: restore callee registers
    return (unsigned int)(var0);
}

gcc -O0

2/2
counting_sort_u8 pass 43 lines 
// glaurung: counting_sort_u8 @ 0x1119
int32_t counting_sort_u8(uint8_t * arg0, int32_t arg1) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int bucket;
    int index;
    int out;
    int remaining;
    unsigned char local_410[1024];
    long local_8;
    long ret;
    // x86-64 prologue: save rbp, frame 1072 bytes
    local_8 = (long)(0x28);
    if ((((arg0 == 0) || ((long)(arg1) < 0)) || (((unsigned long)((unsigned int)(arg1)) != 16) && (16 <= (long)(arg1))))) {
        ret = 0xffffffff;
    } else {
        for (bucket = 0; ((((unsigned long)((unsigned int)(bucket)) == 255) | ((long)(bucket) < 255)) != 0); bucket++) {
            *(int *)((&local_410[0] + ((long)(bucket) * 4))) = 0;
        }
        for (index = 0; (index < arg1); index++) {
            *(int *)((&local_410[0] + ((long)((int)((unsigned char)(((unsigned int)((unsigned char)(arg0[index])) & 255)))) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_410[0] + ((long)((int)((unsigned char)(((unsigned int)((unsigned char)(arg0[index])) & 255)))) * 4))))) + 1);
        }
        out = 0;
        bucket = 0;
        while (((((unsigned long)((unsigned int)(bucket)) == 255) | ((long)(bucket) < 255)) != 0)) {
            remaining = *(int *)((&local_410[0] + ((long)(bucket) * 4)));
            while (((((unsigned long)((unsigned int)(remaining)) == 0) | ((long)(remaining) < 0)) == 0)) {
                if ((arg1 <= out)) {
                    break;
                }
                arg0[out] = bucket;
                out = (out + 1);
                remaining = (remaining - 1);
            }
            bucket = (bucket + 1);
        }
        ret = (unsigned long)((unsigned int)(arg1));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}
radix_sort_u32 pass 50 lines 
// glaurung: radix_sort_u32 @ 0x12a0
int32_t radix_sort_u32(uint32_t * arg0, int32_t arg1) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int shift;
    int running;
    int bucket;
    int index;
    int occupancy;
    int slot;
    unsigned char local_50[64];
    long local_8;
    unsigned char local_90[64];
    long ret;
    // x86-64 prologue: save rbp, frame 192 bytes
    local_8 = (long)(0x28);
    if ((((arg0 == 0) || ((long)(arg1) < 0)) || (((unsigned long)((unsigned int)(arg1)) != 16) && (16 <= (long)(arg1))))) {
        ret = 0xffffffff;
    } else {
        shift = 0;
        while (((((unsigned long)((unsigned int)(shift)) == 31) | ((long)(shift) < 31)) != 0)) {
            running = 0;
            for (bucket = 0; ((((unsigned long)((unsigned int)(bucket)) == 15) | ((long)(bucket) < 15)) != 0); bucket++) {
                *(int *)((&local_50[0] + ((long)(bucket) * 4))) = 0;
            }
            for (index = 0; (index < arg1); index++) {
                *(int *)((&local_50[0] + ((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0[(long)(index)])) >> ((unsigned long)((unsigned int)(shift)) & 31)))) & 15))) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_50[0] + ((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0[(long)(index)])) >> ((unsigned long)((unsigned int)(shift)) & 31)))) & 15))) * 4))))) + 1);
            }
            for (bucket = 0; ((((unsigned long)((unsigned int)(bucket)) == 15) | ((long)(bucket) < 15)) != 0); bucket++) {
                occupancy = *(int *)((&local_50[0] + ((long)(bucket) * 4)));
                *(int *)((&local_50[0] + ((long)(bucket) * 4))) = running;
                running = (running + (unsigned int)(occupancy));
            }
            for (index = 0; (index < arg1); index++) {
                slot = ((unsigned int)(((unsigned long)((unsigned int)(arg0[(long)(index)])) >> ((unsigned long)((unsigned int)(shift)) & 31))) & 15);
                *(int *)((&local_90[0] + ((long)((int)(*(int *)((&local_50[0] + ((long)(slot) * 4))))) * 4))) = arg0[(long)(index)];
                *(int *)((&local_50[0] + ((long)(slot) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_50[0] + ((long)(slot) * 4))))) + 1);
            }
            for (index = 0; (index < arg1); index++) {
                arg0[(long)(index)] = *(int *)((&local_90[0] + ((long)(index) * 4)));
            }
            shift = (shift + 4);
        }
        ret = (unsigned long)((unsigned int)(arg1));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}

← 213 fixtures