glaurung

Fixture 38

insertion shell sort

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

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

Insertion sort and Shell sort with the Knuth 3h+1 gap sequence. Both are inner loops whose trip count depends on the data, and Shell's outer gap loop divides by three, which lowers to a multiply-high sequence at -O2.

tests/decompiler_fixtures/src/38_insertion_shell_sort.c source 
#include <stdint.h>

/* Insertion sort and Shell sort with the Knuth 3h+1 gap sequence.  Both are
 * inner loops whose trip count depends on the data, and Shell's outer gap loop
 * divides by three, which lowers to a multiply-high sequence at -O2. */

#define SORT_MAX 16

__attribute__((noinline)) int32_t
insertion_sort_i32(int32_t *values, int32_t count) {
    int32_t index;
    if (values == 0 || count < 0 || count > SORT_MAX) {
        return -1;
    }
    for (index = 1; index < count; ++index) {
        int32_t key = values[index];
        int32_t scan = index - 1;
        while (scan >= 0 && values[scan] > key) {
            values[scan + 1] = values[scan];
            scan -= 1;
        }
        values[scan + 1] = key;
    }
    return count;
}

__attribute__((noinline)) int32_t
shell_sort_i32(int32_t *values, int32_t count) {
    int32_t gap = 1;
    int32_t index;
    if (values == 0 || count < 0 || count > SORT_MAX) {
        return -1;
    }
    while (gap < count / 3) {
        gap = 3 * gap + 1;
    }
    while (gap >= 1) {
        for (index = gap; index < count; ++index) {
            int32_t key = values[index];
            int32_t scan = index - gap;
            while (scan >= 0 && values[scan] > key) {
                values[scan + gap] = values[scan];
                scan -= gap;
            }
            values[scan + gap] = key;
        }
        gap = gap / 3;
    }
    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

2/2
insertion_sort_i32 pass 48 lines 
// glaurung: insertion_sort_i32 @ 0x1100
int32_t insertion_sort_i32(int32_t * arg0, int32_t arg1) {
    int index;
    int key;
    int scan;
    signed char local_21;
    int local_4;
    long var11;
    long var6;
    if ((arg0 != 0)) {
        if ((0 <= (long)(arg1))) {
            if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                goto L_1136;
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1136: ;
    index = 1;
    L_113d: ;
    if ((arg1 <= index)) {
        goto L_11dd;
    }
    key = arg0[(long)(index)];
    var6 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(index)) - 1)));
    scan = var6;
    L_1160: ;
    local_21 = 0;
    if ((0 <= (long)(scan))) {
        var11 = (unsigned long)((unsigned int)(arg0[(long)(scan)]));
        local_21 = ((((unsigned int)(var11) == (unsigned int)(key)) | ((long)((int)(var11)) < (long)(key))) == 0);
    }
    if (((unsigned long)((unsigned char)((local_21 & 1))) != 0)) {
        arg0[(long)((int)(((unsigned long)((unsigned int)(scan)) + 1)))] = arg0[(long)(scan)];
        var6 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(scan)) - 1)));
        scan = var6;
        goto L_1160;
    }
    arg0[(long)((int)(((unsigned long)((unsigned int)(scan)) + 1)))] = key;
    index = ((unsigned int)(index) + 1);
    goto L_113d;
    L_11dd: ;
    local_4 = arg1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
shell_sort_i32 pass 84 lines 
// glaurung: shell_sort_i32 @ 0x11f0
int32_t shell_sort_i32(int32_t * arg0, int32_t arg1) {
    int gap;
    int index;
    int key;
    int scan;
    int local_28;
    signed char local_29;
    int local_4;
    long t177;
    long var18;
    long var23;
    long var59;
    gap = 1;
    if ((arg0 != 0)) {
        if ((0 <= (long)(arg1))) {
            if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                goto L_122d;
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_122d: ;
    goto L_1232;
    L_1232: ;
    local_28 = gap;
    if (((long)(local_28) < (long)((int)(((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)(3))))))) {
        gap = ((gap * 3) + 1);
        goto L_1232;
    }
    goto L_1264;
    L_1264: ;
    if (((long)(gap) < 1)) {
        goto L_1329;
    }
    index = gap;
    L_1274: ;
    if ((arg1 <= index)) {
        goto L_1316;
    }
    key = arg0[(long)(index)];
    var18 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(index)) - gap)));
    scan = var18;
    L_1297: ;
    local_29 = 0;
    if ((0 <= (long)(scan))) {
        var23 = (unsigned long)((unsigned int)(arg0[(long)(scan)]));
        local_29 = ((((unsigned int)(var23) == (unsigned int)(key)) | ((long)((int)(var23)) < (long)(key))) == 0);
    }
    if (((unsigned long)((unsigned char)((local_29 & 1))) != 0)) {
        arg0[(long)((int)(((unsigned long)((unsigned int)(scan)) + gap)))] = arg0[(long)(scan)];
        var18 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(scan)) - (unsigned long)((unsigned int)(gap)))));
        scan = var18;
        goto L_1297;
    }
    arg0[(long)((int)(((unsigned long)((unsigned int)(scan)) + gap)))] = key;
    index = ((unsigned int)(index) + 1);
    goto L_1274;
    L_1316: ;
    gap = ((int)((((long long)(int)((((unsigned long)((long)((int)((unsigned long)((unsigned int)(gap))))) >> 32) & 0xffffffff)) * (((long long)1) << 32)) + (unsigned int)((unsigned long)((unsigned int)(gap)))) / (int)(3)));
    goto L_1264;
    L_1329: ;
    index = 1;
    L_1330: ;
    if ((arg1 <= index)) {
        goto L_137c;
    }
    var59 = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)(index)) - 1)))]));
    t177 = arg0[(long)(index)];
    if (((((unsigned int)(var59) == (unsigned int)(t177)) | ((long)((int)(var59)) < (long)((int)(t177)))) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    goto L_136e;
    L_136e: ;
    index = ((unsigned int)(index) + 1);
    goto L_1330;
    L_137c: ;
    local_4 = arg1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

2/2
insertion_sort_i32 pass 43 lines 
// glaurung: insertion_sort_i32 @ 0x1100
int32_t insertion_sort_i32(int32_t * arg0, int32_t arg1) {
    int key;
    int index;
    long ret;
    long var0;
    long var2;
    long var4;
    long var5;
    long var7;
    ret = 0xffffffff;
    if ((arg0 == 0)) {
        return ret;
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return ret;
    }
    if (((unsigned long)(2) <= (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        var0 = (unsigned long)((unsigned int)(arg1));
        var2 = 1;
        do {
            key = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var2 * 4))));
            var4 = var2;
            while (1) {
                var5 = (var4 - 1);
                var7 = (unsigned long)((unsigned int)(arg0[(unsigned long)((unsigned int)(var5))]));
                if (((((unsigned int)(var7) == (unsigned int)(key)) | ((long)((int)(var7)) < (long)(key))) != 0)) {
                    break;
                }
                *(int *)(((long)arg0 + var4 * 4)) = var7;
                var4 = var5;
                if (((var5 + 1) <= 1)) {
                    var4 = 0;
                    break;
                }
            }
            arg0[(long)((int)(var4))] = key;
            index = (var2 + 1);
            var2 = (unsigned long)((unsigned int)(index));
        } while ((index != var0));
    }
    return (unsigned int)(arg1);
}
shell_sort_i32 pass 109 lines 
// glaurung: shell_sort_i32 @ 0x1170
int32_t shell_sort_i32(int32_t * arg0, int32_t arg1) {
    int gap;
    int key;
    int index;
    int scan;
    long local_8;
    long ret;
    long t21;
    long var0;
    long var13;
    long var14;
    long var16;
    int var18;
    long var23;
    long var3;
    long var34;
    long var36;
    int var38;
    long var4;
    long var40;
    long var41;
    long var43;
    long var44;
    long var6;
    long var8;
    local_8 = var0;
    ret = 0xffffffff;
    if ((arg0 == 0)) {
        // x86-64 epilogue: tear down frame
        return ret;
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        // x86-64 epilogue: tear down frame
        return ret;
    }
    var3 = 1;
    if (((unsigned long)((unsigned long)((unsigned int)(arg1))) < (unsigned long)(6))) {
        L_11c4: ;
        var4 = (long)(arg1);
        gap = var3;
        do {
            var6 = (long)(gap);
            if ((gap < arg1)) {
                var8 = var6;
                do {
                    key = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var8 * 4))));
                    var13 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var8)) - gap)));
                    while (1) {
                        var14 = (unsigned long)((unsigned int)((gap + var13)));
                        var16 = (unsigned long)((unsigned int)(arg0[(unsigned long)((unsigned int)(var13))]));
                        if (((((unsigned int)(var16) == (unsigned int)(key)) | ((long)((int)(var16)) < (long)(key))) != 0)) {
                            break;
                        }
                        arg0[(long)((int)(var14))] = var16;
                        var18 = (var13 - gap);
                        var13 = (unsigned long)((unsigned int)(var18));
                        if (((long)((int)(var18)) < 0)) {
                            var14 = (unsigned long)((unsigned int)((var13 + gap)));
                            break;
                        }
                    }
                    arg0[(long)((int)(var14))] = key;
                    index = (var8 + 1);
                    var8 = (unsigned long)((unsigned int)(index));
                } while ((index != var4));
            }
            var23 = (var6 * 0x55555556);
            t21 = (((unsigned long)((unsigned int)(gap)) == 2) | ((long)(gap) < 2));
            gap = (unsigned long)((unsigned int)((((unsigned long)(var23) >> 32) + ((unsigned long)(var23) >> 63))));
        } while ((t21 == 0));
    } else {
        var34 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)((unsigned char)((arg1 & 255))) * 171))) >> 9)));
        var3 = 1;
        do {
            var36 = (unsigned long)((unsigned int)(var3));
            var38 = ((unsigned int)(((unsigned long)((unsigned int)(var3)) + ((unsigned long)((unsigned int)(var3)) * 2))) + 1);
            var3 = (unsigned long)((unsigned int)(var38));
        } while (((long)((int)(var38)) < (long)((int)(var34))));
        if (((long)((int)(var36)) < 0)) {
            goto L_123e;
        }
        goto L_11c4;
    }
    L_123e: ;
    if (((long)(arg1) < 2)) {
        ret = (unsigned long)((unsigned int)(arg1));
        // x86-64 epilogue: tear down frame
        return (unsigned int)(arg1);
    }
    var40 = (unsigned long)((unsigned int)(arg1));
    var41 = (unsigned long)((unsigned int)(*(int *)(((long)arg0))));
    var43 = 1;
    while (1) {
        var44 = (unsigned long)((unsigned int)(var41));
        var41 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var43 * 4))));
        if (((((unsigned int)(var44) == (unsigned int)(var41)) | ((long)((int)(var44)) < (long)((int)(var41)))) == 0)) {
            break;
        }
        var43 = (var43 + 1);
        if ((var40 == var43)) {
            ret = (unsigned long)((unsigned int)(arg1));
            // x86-64 epilogue: tear down frame
            return (unsigned int)(arg1);
        }
    }
    // x86-64 epilogue: tear down frame
    return 0;
}

gcc -O0

2/2
insertion_sort_i32 pass 35 lines 
// glaurung: insertion_sort_i32 @ 0x10f9
int32_t insertion_sort_i32(int32_t * arg0, int32_t arg1) {
    int index;
    int key;
    int scan;
    // x86-64 prologue: save rbp
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((long)(arg1) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    index = 1;
    while ((index < arg1)) {
        key = arg0[(long)(index)];
        scan = ((unsigned int)(index) - 1);
        while ((0 <= (long)(scan))) {
            if (((long)((int)(arg0[(long)(scan)])) <= (long)(key))) {
                break;
            }
            arg0[((long)(scan) + 1)] = arg0[(long)(scan)];
            scan = (scan - 1);
        }
        arg0[((long)(scan) + 1)] = key;
        index = (index + 1);
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(arg1);
}
shell_sort_i32 pass 69 lines 
// glaurung: shell_sort_i32 @ 0x11dd
int32_t shell_sort_i32(int32_t * arg0, int32_t arg1) {
    int gap;
    int index;
    int key;
    int scan;
    long var77;
    long var83;
    gap = 1;
    if ((arg0 != 0)) {
        if ((0 <= (long)(arg1))) {
            if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                goto L_121f;
            }
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_1210: ;
    gap = ((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(gap)) + (unsigned long)((unsigned int)(gap))))) + (unsigned long)((unsigned int)(gap)))) + 1);
    L_121f: ;
    if (((long)(gap) < (long)((int)(((unsigned long)((unsigned int)(((unsigned long)(((long)(arg1) * 0x55555556)) >> 32))) - (unsigned long)((unsigned int)(((int)(arg1) >> 31)))))))) {
        goto L_1210;
    }
    goto L_1316;
    L_1243: ;
    index = gap;
    goto L_12ed;
    L_124e: ;
    key = arg0[(long)(index)];
    scan = ((unsigned int)(index) - gap);
    goto L_12aa;
    L_1272: ;
    arg0[(long)((int)(((unsigned long)((unsigned int)(gap)) + (unsigned long)((unsigned int)(scan)))))] = arg0[(long)(scan)];
    scan = (scan - (unsigned int)(gap));
    L_12aa: ;
    if ((0 <= (long)(scan))) {
        if (((long)(key) < (long)((int)(arg0[(long)(scan)])))) {
            goto L_1272;
        }
    }
    arg0[(long)((int)(((unsigned long)((unsigned int)(gap)) + (unsigned long)((unsigned int)(scan)))))] = key;
    index = (index + 1);
    L_12ed: ;
    if ((index < arg1)) {
        goto L_124e;
    }
    gap = ((unsigned int)(((unsigned long)(((long)(gap) * 0x55555556)) >> 32)) - (unsigned int)(((int)(gap) >> 31)));
    L_1316: ;
    if (((((unsigned long)((unsigned int)(gap)) == 0) | ((long)(gap) < 0)) == 0)) {
        goto L_1243;
    }
    index = 1;
    goto L_1364;
    L_1329: ;
    var77 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + (((long)(index) << 2) - 4)))));
    var83 = (unsigned long)((unsigned int)(arg0[(long)(index)]));
    if (((((unsigned int)(var77) == (unsigned int)(var83)) | ((long)((int)(var77)) < (long)((int)(var83)))) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    index = (index + 1);
    L_1364: ;
    if ((index < arg1)) {
        goto L_1329;
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(arg1);
}

gcc -O2

2/2
insertion_sort_i32 pass 54 lines 
// glaurung: insertion_sort_i32 @ 0x1100
int32_t insertion_sort_i32(int32_t * arg0, int32_t arg1) {
    int key;
    int index;
    int scan;
    long ret;
    long var0;
    long var11;
    long var3;
    long var6;
    long var7;
    long var8;
    long var9;
    ret = (unsigned long)((unsigned int)(arg1));
    if ((arg0 == 0)) {
        return 0xffffffff;
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return 0xffffffff;
    }
    var0 = (unsigned long)((unsigned int)((arg1 - 2)));
    if ((((unsigned long)((unsigned int)(arg1)) == 1) | ((long)(arg1) < 1))) {
        return ret;
    }
    var3 = 0;
    L_1120: ;
    key = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var3 * 4 + 0x4))));
    var6 = var3;
    do {
        var7 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var6 * 4))));
        var8 = (unsigned long)((unsigned int)(var6));
        if ((((unsigned int)(var7) == (unsigned int)(key)) | ((long)((int)(var7)) < (long)(key)))) {
            goto L_1160;
        }
        *(int *)(((long)arg0 + var6 * 4 + 0x4)) = var7;
        var9 = (var6 - 1);
        var6 = var9;
    } while (((unsigned long)((unsigned int)(var9)) != 0xffffffff));
    *(int *)((long)arg0) = key;
    var11 = (var3 + 1);
    if ((var0 == var3)) {
        return ret;
    }
    L_1157: ;
    var3 = var11;
    goto L_1120;
    L_1160: ;
    arg0[(long)((int)((var8 + 1)))] = key;
    var11 = (var3 + 1);
    if ((var0 != var3)) {
        goto L_1157;
    }
    return ret;
}
shell_sort_i32 pass 125 lines 
// glaurung: shell_sort_i32 @ 0x1180
int32_t shell_sort_i32(int32_t * arg0, int32_t arg1) {
    int gap;
    int key;
    int scan;
    long t10;
    long var0;
    long var10;
    long var11;
    long var12;
    long var14;
    long var15;
    long var22;
    long var23;
    long var25;
    long var26;
    long var29;
    long var3;
    long var30;
    long var31;
    long var32;
    long var33;
    int var34;
    int var35;
    long var38;
    long var40;
    long var41;
    long var42;
    int var45;
    if ((arg0 == 0)) {
        goto L_12a1;
    }
    var0 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        goto L_12a1;
    }
    var3 = (long)arg0;
    var10 = (unsigned long)((unsigned int)((((unsigned long)(((long)(arg1) * 0x55555556)) >> 32) - (unsigned long)((unsigned int)(((int)(arg1) >> 31))))));
    if ((((unsigned long)((unsigned int)(arg1)) == 5) | ((long)(arg1) < 5))) {
        goto L_1297;
    }
    var11 = 1;
    do {
        var12 = (unsigned long)((unsigned int)(((var11 + (var11 * 2)) + 1)));
        var11 = 4;
        var14 = var12;
    } while (((((unsigned int)(var10) == (unsigned int)(var12)) | ((long)((int)(var10)) < (long)((int)(var12)))) == 0));
    L_11dd: ;
    var15 = 0xaaaaaaab;
    gap = var14;
    L_11e8: ;
    if ((((unsigned int)(var0) == (unsigned int)(gap)) | ((long)((int)(var0)) < (long)(gap)))) {
        goto L_1234;
    }
    var22 = 0;
    var23 = ((long)(gap) << 2);
    var25 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var0)) - gap)));
    var26 = (var3 + var23);
    L_1200: ;
    key = (unsigned long)((unsigned int)(*(int *)((var26))));
    var29 = (unsigned long)((unsigned int)(var22));
    var30 = var26;
    var31 = (var26 - var23);
    do {
        var32 = (unsigned long)((unsigned int)(*(int *)((var31))));
        var33 = var31;
        if ((((unsigned int)(var32) == (unsigned int)(key)) | ((long)((int)(var32)) < (long)(key)))) {
            goto L_1280;
        }
        *(int *)((var30)) = var32;
        var31 = (var31 - var23);
        var30 = (var30 - var23);
        var34 = (var29 - gap);
        var29 = (unsigned long)((unsigned int)(var34));
    } while ((0 <= (long)((int)(var34))));
    var35 = (var22 + 1);
    var22 = (unsigned long)((unsigned int)(var35));
    *(int *)((var33)) = key;
    var26 = (var26 + 4);
    if (((unsigned int)(var25) != (unsigned int)(var35))) {
        goto L_1200;
    }
    L_1234: ;
    var38 = ((unsigned long)(((unsigned long)((unsigned int)(gap)) * var15)) >> 33);
    gap = var38;
    if (((unsigned long)((unsigned int)(var38)) != 0)) {
        goto L_11e8;
    }
    if ((((unsigned long)((unsigned int)(var0)) == 1) | ((long)((int)(var0)) < 1))) {
        goto L_1273;
    }
    var40 = var3;
    var41 = ((var3 + ((unsigned long)((unsigned int)((var0 - 2))) * 4)) + 4);
    goto L_1269;
    L_1260: ;
    var40 = (var40 + 4);
    if ((var40 == var41)) {
        goto L_1273;
    }
    L_1269: ;
    var42 = (unsigned long)((unsigned int)(*(int *)((var40 + 0x4))));
    t10 = *(int *)((var40));
    if ((((unsigned int)(t10) == (unsigned int)(var42)) | ((long)((int)(t10)) < (long)((int)(var42))))) {
        goto L_1260;
    }
    var0 = 0;
    L_1273: ;
    // x86-64 epilogue: tear down frame
    return (unsigned int)(var0);
    L_1280: ;
    var45 = (var22 + 1);
    var22 = (unsigned long)((unsigned int)(var45));
    var26 = (var26 + 4);
    *(int *)(var30) = key;
    if (((unsigned int)(var25) != (unsigned int)(var45))) {
        goto L_1200;
    }
    goto L_1234;
    L_1297: ;
    var14 = 1;
    goto L_11dd;
    L_12a1: ;
    var0 = 0xffffffff;
    goto L_1273;
}

← 213 fixtures