glaurung

Fixture 37

heapsort

C · 1 functions · 4 lanes · 4 of 4 function-lanes behave identically

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

In-place heapsort: sift-down with two child indices and a trailing swap loop. The child-index arithmetic (2i+1, 2i+2) and its bounds test are a compact strength-reduction target at -O2.

tests/decompiler_fixtures/src/37_heapsort.c source 
#include <stdint.h>

/* In-place heapsort: sift-down with two child indices and a trailing swap
 * loop.  The child-index arithmetic (2i+1, 2i+2) and its bounds test are a
 * compact strength-reduction target at -O2. */

#define HS_MAX 16

static void sift_down(int32_t *values, int32_t root, int32_t count) {
    int32_t guard;
    for (guard = 0; guard < HS_MAX; ++guard) {
        int32_t left = 2 * root + 1;
        int32_t right = left + 1;
        int32_t largest = root;
        int32_t swap;
        if (left < count && values[left] > values[largest]) {
            largest = left;
        }
        if (right < count && values[right] > values[largest]) {
            largest = right;
        }
        if (largest == root) {
            return;
        }
        swap = values[root];
        values[root] = values[largest];
        values[largest] = swap;
        root = largest;
    }
}

__attribute__((noinline)) int32_t
heapsort_i32(int32_t *values, int32_t count) {
    int32_t index;
    if (values == 0 || count < 0 || count > HS_MAX) {
        return -1;
    }
    for (index = count / 2 - 1; index >= 0; --index) {
        sift_down(values, index, count);
    }
    for (index = count - 1; index > 0; --index) {
        int32_t swap = values[0];
        values[0] = values[index];
        values[index] = swap;
        sift_down(values, 0, index);
    }
    for (index = 1; index < count; ++index) {
        if (values[index - 1] > values[index]) {
            return 0;
        }
    }
    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.

clang -O0

1/1
heapsort_i32 pass 56 lines 
// glaurung: heapsort_i32 @ 0x1100
int32_t heapsort_i32(int32_t * arg0, int32_t arg1) {
    extern void sift_down(int *, int, int);
    int index;
    int swap;
    int local_4;
    long t158;
    long var33;
    if ((arg0 != 0)) {
        if ((0 <= (long)(arg1))) {
            if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                goto L_113a;
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_113a: ;
    index = (((int)((((long long)(int)((((unsigned long)((long)((int)((unsigned long)((unsigned int)(arg1))))) >> 32) & 0xffffffff)) * (((long long)1) << 32)) + (unsigned int)((unsigned long)((unsigned int)(arg1)))) / (int)(2))) - 1);
    L_114b: ;
    if ((0 <= (long)(index))) {
        sift_down((int *)(arg0), (unsigned long)((unsigned int)(index)), (unsigned long)((unsigned int)(arg1)));
        index = ((unsigned int)(index) - 1);
        goto L_114b;
    }
    index = ((unsigned int)(arg1) - 1);
    L_117b: ;
    if (((((unsigned long)((unsigned int)(index)) == 0) | ((long)(index) < 0)) == 0)) {
        swap = *(int *)((long)arg0);
        *(int *)((long)arg0) = arg0[(long)(index)];
        arg0[(long)(index)] = swap;
        sift_down((int *)(arg0), 0, (unsigned long)((unsigned int)(index)));
        index = ((unsigned int)(index) - 1);
        goto L_117b;
    }
    index = 1;
    L_11d0: ;
    if ((arg1 <= index)) {
        goto L_121c;
    }
    var33 = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)(index)) - 1)))]));
    t158 = arg0[(long)(index)];
    if (((((unsigned int)(var33) == (unsigned int)(t158)) | ((long)((int)(var33)) < (long)((int)(t158)))) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    goto L_120e;
    L_120e: ;
    index = ((unsigned int)(index) + 1);
    goto L_11d0;
    L_121c: ;
    local_4 = arg1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

1/1
heapsort_i32 pass 177 lines 
// glaurung: heapsort_i32 @ 0x1100
int32_t heapsort_i32(int32_t * arg0, int32_t arg1) {
    int left;
    int right;
    int swap;
    int index;
    int largest;
    long ret;
    long t11;
    long t158;
    long t159;
    long t160;
    long var0;
    long var1;
    long var10;
    int var12;
    long var13;
    long var14;
    long var16;
    long var18;
    long var2;
    int var22;
    long var23;
    long var24;
    long var26;
    long var29;
    long var3;
    int var33;
    long var37;
    long var38;
    long var39;
    long var41;
    int var43;
    long var45;
    long var47;
    long var49;
    int var53;
    long var55;
    long var57;
    int var64;
    long var65;
    long var68;
    long var9;
    ret = 0xffffffff;
    if ((arg0 == 0)) {
        goto L_1284;
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        goto L_1284;
    }
    if (((unsigned long)(2) <= (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        goto L_11d0;
    }
    L_1124: ;
    if (((long)(arg1) < 2)) {
        goto L_1282;
    }
    var0 = (unsigned long)((unsigned int)(arg1));
    var1 = (unsigned long)((unsigned int)(arg1));
    goto L_114a;
    L_1140: ;
    if ((var2 <= 2)) {
        goto L_125a;
    }
    L_114a: ;
    var2 = var1;
    var1 = (var1 - 1);
    var3 = (unsigned long)((unsigned int)(*(int *)(((long)arg0))));
    *(int *)(((long)arg0)) = arg0[(unsigned long)((unsigned int)(var1))];
    arg0[(unsigned long)((unsigned int)(var1))] = var3;
    var9 = 16;
    var10 = 0;
    do {
        var12 = ((unsigned int)((var10 + var10)) + 1);
        var13 = (unsigned long)((unsigned int)(var12));
        var14 = (long)((int)(var10));
        var16 = (unsigned long)((unsigned int)(var10));
        if (((long)((int)(var12)) < (long)((int)(var1)))) {
            var18 = (unsigned long)((unsigned int)(arg0[(long)((int)(var13))]));
            t11 = *(int *)(((long)arg0 + var14 * 4));
            if (((((unsigned int)(var18) == (unsigned int)(t11)) | ((long)((int)(var18)) < (long)((int)(t11)))) != 0)) {
                var13 = (unsigned long)((unsigned int)(var10));
            }
            var16 = (unsigned long)((unsigned int)(var13));
        }
        var22 = ((unsigned int)((var10 + var10)) + 2);
        var23 = (unsigned long)((unsigned int)(var22));
        var24 = var16;
        if (((long)((int)(var22)) < (long)((int)(var1)))) {
            var26 = (unsigned long)((unsigned int)(arg0[(long)((int)(var23))]));
            t158 = arg0[(long)((int)(var16))];
            if (((((unsigned int)(var26) == (unsigned int)(t158)) | ((long)((int)(var26)) < (long)((int)(t158)))) != 0)) {
                var23 = (unsigned long)((unsigned int)(var16));
            }
            var24 = (unsigned long)((unsigned int)(var23));
        }
        if (((unsigned int)(var24) == (unsigned int)(var10))) {
            goto L_1140;
        }
        var29 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var14 * 4))));
        *(int *)(((long)arg0 + var14 * 4)) = arg0[(long)((int)(var24))];
        arg0[(long)((int)(var24))] = var29;
        var33 = (var9 - 1);
        var9 = (unsigned long)((unsigned int)(var33));
        var10 = (unsigned long)((unsigned int)(var24));
    } while (((unsigned long)((unsigned int)(var33)) != 0));
    goto L_1140;
    L_11d0: ;
    var37 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) >> 1)));
    goto L_11ea;
    L_11e0: ;
    if ((((unsigned long)((unsigned int)(var38)) == 1) | ((long)((int)(var38)) < 1))) {
        goto L_1124;
    }
    L_11ea: ;
    var38 = (unsigned long)((unsigned int)(var37));
    var37 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var37)) - 1)));
    var39 = 16;
    var41 = (unsigned long)((unsigned int)(var37));
    do {
        var43 = ((unsigned int)((var41 + var41)) + 1);
        left = (unsigned long)((unsigned int)(var43));
        var45 = (long)((int)(var41));
        var47 = (unsigned long)((unsigned int)(var41));
        if ((var43 < arg1)) {
            var49 = (unsigned long)((unsigned int)(arg0[(long)(left)]));
            t159 = *(int *)(((long)arg0 + var45 * 4));
            if (((((unsigned int)(var49) == (unsigned int)(t159)) | ((long)((int)(var49)) < (long)((int)(t159)))) != 0)) {
                left = (unsigned long)((unsigned int)(var41));
            }
            var47 = (unsigned long)((unsigned int)(left));
        }
        var53 = ((unsigned int)((var41 + var41)) + 2);
        right = (unsigned long)((unsigned int)(var53));
        var55 = var47;
        if ((var53 < arg1)) {
            var57 = (unsigned long)((unsigned int)(arg0[(long)(right)]));
            t160 = arg0[(long)((int)(var47))];
            if (((((unsigned int)(var57) == (unsigned int)(t160)) | ((long)((int)(var57)) < (long)((int)(t160)))) != 0)) {
                right = (unsigned long)((unsigned int)(var47));
            }
            var55 = (unsigned long)((unsigned int)(right));
        }
        if (((unsigned int)(var55) == (unsigned int)(var41))) {
            goto L_11e0;
        }
        swap = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var45 * 4))));
        *(int *)(((long)arg0 + var45 * 4)) = arg0[(long)((int)(var55))];
        arg0[(long)((int)(var55))] = swap;
        var64 = (var39 - 1);
        var39 = (unsigned long)((unsigned int)(var64));
        var41 = (unsigned long)((unsigned int)(var55));
    } while (((unsigned long)((unsigned int)(var64)) != 0));
    goto L_11e0;
    L_125a: ;
    if (((long)(arg1) < 2)) {
        goto L_1282;
    }
    var65 = (unsigned long)((unsigned int)(*(int *)(((long)arg0))));
    index = 1;
    do {
        var68 = (unsigned long)((unsigned int)(var65));
        var65 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + index * 4))));
        if (((((unsigned int)(var68) == (unsigned int)(var65)) | ((long)((int)(var68)) < (long)((int)(var65)))) == 0)) {
            goto L_1289;
        }
        index = (index + 1);
    } while ((var0 != index));
    L_1282: ;
    ret = (unsigned long)((unsigned int)(arg1));
    L_1284: ;
    // x86-64 epilogue: tear down frame
    return ret;
    L_1289: ;
    ret = 0;
    goto L_1284;
}

gcc -O0

1/1
heapsort_i32 pass 55 lines 
// glaurung: heapsort_i32 @ 0x122d
int32_t heapsort_i32(int32_t * arg0, int32_t arg1) {
    extern void sift_down(int *, int, int);
    int index;
    int swap;
    long var41;
    long var47;
    if ((arg0 != 0)) {
        if ((0 <= (long)(arg1))) {
            if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                goto L_125d;
            }
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_125d: ;
    index = ((unsigned int)(((int)(((unsigned long)((unsigned int)(arg1)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) >> 31))))) >> 1)) - 1);
    goto L_1289;
    L_1271: ;
    sift_down((int *)(arg0), (unsigned long)((unsigned int)(index)), (unsigned long)((unsigned int)(arg1)));
    index = (index - 1);
    L_1289: ;
    if ((0 <= (long)(index))) {
        goto L_1271;
    }
    index = ((unsigned int)(arg1) - 1);
    goto L_12f0;
    L_129a: ;
    swap = *(int *)((long)arg0);
    *(int *)((long)arg0) = arg0[(long)(index)];
    arg0[(long)(index)] = swap;
    sift_down((int *)(arg0), 0, (unsigned long)((unsigned int)(index)));
    index = (index - 1);
    L_12f0: ;
    if (((((unsigned long)((unsigned int)(index)) == 0) | ((long)(index) < 0)) == 0)) {
        goto L_129a;
    }
    index = 1;
    goto L_133a;
    L_12ff: ;
    var41 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + (((long)(index) << 2) - 4)))));
    var47 = (unsigned long)((unsigned int)(arg0[(long)(index)]));
    if (((((unsigned int)(var41) == (unsigned int)(var47)) | ((long)((int)(var41)) < (long)((int)(var47)))) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    index = (index + 1);
    L_133a: ;
    if ((index < arg1)) {
        goto L_12ff;
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(arg1);
}

gcc -O2

1/1
heapsort_i32 pass 75 lines 
// glaurung: heapsort_i32 @ 0x1190
int32_t heapsort_i32(int32_t * arg0, int32_t arg1) {
    extern void sift_down(int *, int, int);
    int index;
    int swap;
    long cf_5;
    long local_18;
    long local_8;
    long t10;
    long var0;
    long var1;
    long var11;
    long var14;
    long var2;
    long var20;
    long var22;
    long var23;
    long var7;
    int var9;
    local_8 = var0;
    local_18 = var1;
    if ((arg0 == 0)) {
        var2 = 0xffffffff;
        // x86-64 epilogue: tear down frame
        return 0xffffffff;
    }
    var2 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        var2 = 0xffffffff;
        // x86-64 epilogue: tear down frame
        return 0xffffffff;
    }
    var7 = (long)arg0;
    var9 = ((int)(arg1) >> 1);
    var11 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var9)) - 1)));
    if (((unsigned long)((unsigned int)(var9)) != 0)) {
        do {
            sift_down((int *)(var7), (unsigned long)((unsigned int)(var11)), (unsigned long)((unsigned int)(var2)));
            cf_5 = ((unsigned long)((unsigned long)((unsigned int)(var11))) < (unsigned long)(1));
            var11 = (unsigned long)((unsigned int)((var11 - 1)));
        } while ((cf_5 == 0));
    }
    var14 = (unsigned long)((unsigned int)((var2 - 1)));
    if (((((unsigned long)((unsigned int)(var14)) == 0) | ((long)((int)(var14)) < 0)) == 0)) {
        index = (long)((int)(var14));
        do {
            swap = (unsigned long)((unsigned int)(*(int *)((var7))));
            *(int *)((var7)) = *(int *)((var7 + index * 4));
            var20 = (unsigned long)((unsigned int)(index));
            *(int *)((var7 + index * 4)) = swap;
            index = (index - 1);
            sift_down((int *)(var7), 0, var20);
        } while (((((unsigned long)((unsigned int)(index)) == 0) | ((long)(index) < 0)) == 0));
    }
    if ((((unsigned long)((unsigned int)(var2)) == 1) | ((long)((int)(var2)) < 1))) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var2);
    }
    var22 = ((var7 + ((unsigned long)((unsigned int)((var2 - 2))) * 4)) + 4);
    while (1) {
        var23 = (unsigned long)((unsigned int)(*(int *)((var7 + 0x4))));
        t10 = *(int *)((var7));
        if (((((unsigned int)(t10) == (unsigned int)(var23)) | ((long)((int)(t10)) < (long)((int)(var23)))) == 0)) {
            break;
        }
        var7 = (var7 + 4);
        if ((var22 == var7)) {
            // x86-64 epilogue: tear down frame
            return (unsigned int)(var2);
        }
    }
    var2 = 0;
    // x86-64 epilogue: tear down frame
    return 0;
}

← 213 fixtures