glaurung

Fixture 18

binary heap

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

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

tests/decompiler_fixtures/src/18_binary_heap.c source 
#include <stdint.h>

__attribute__((noinline)) int32_t heap_push(int32_t *heap, int32_t n,
                                            int32_t capacity, int32_t value) {
    int32_t child;
    if (heap == 0 || n < 0 || capacity < 0 || capacity > 16 || n >= capacity) {
        return -1;
    }
    child = n;
    heap[child] = value;
    while (child > 0) {
        int32_t parent = (child - 1) / 2;
        int32_t tmp;
        if (heap[parent] <= heap[child]) {
            break;
        }
        tmp = heap[parent];
        heap[parent] = heap[child];
        heap[child] = tmp;
        child = parent;
    }
    return n + 1;
}

__attribute__((noinline)) int32_t heap_pop(int32_t *heap, int32_t n,
                                           int32_t *removed) {
    int32_t parent = 0;
    if (heap == 0 || removed == 0 || n <= 0 || n > 16) {
        return -1;
    }
    removed[0] = heap[0];
    heap[0] = heap[n - 1];
    --n;
    for (;;) {
        int32_t left = parent * 2 + 1;
        int32_t right = left + 1;
        int32_t child;
        int32_t tmp;
        if (left >= n) {
            break;
        }
        child = (right < n && heap[right] < heap[left]) ? right : left;
        if (heap[parent] <= heap[child]) {
            break;
        }
        tmp = heap[parent];
        heap[parent] = heap[child];
        heap[child] = tmp;
        parent = child;
    }
    return n;
}

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
heap_pop pass 58 lines 
// glaurung: heap_pop @ 0x11f0
int32_t heap_pop(int32_t * arg0, int32_t arg1, int32_t * arg2) {
    int parent;
    int left;
    int right;
    int child;
    int tmp;
    int local_38;
    int local_4;
    long t167;
    long var33;
    parent = 0;
    if ((arg0 != 0)) {
        if ((arg2 != 0)) {
            if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
                if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                    goto L_123c;
                }
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_123c: ;
    *(int *)((long)arg2) = *(int *)((long)arg0);
    *(int *)((long)arg0) = arg0[(long)((int)(((unsigned long)((unsigned int)(arg1)) - 1)))];
    arg1 = ((unsigned int)(arg1) - 1);
    L_1267: ;
    left = ((unsigned int)(((unsigned long)((unsigned int)(parent)) << 1)) + 1);
    right = ((unsigned int)(left) + 1);
    if ((arg1 <= left)) {
        goto L_132a;
    }
    if ((right < arg1)) {
        if (((long)((int)(arg0[(long)(right)])) < (long)((int)(arg0[(long)(left)])))) {
            local_38 = right;
            goto L_12c6;
        }
    }
    local_38 = left;
    L_12c6: ;
    child = local_38;
    var33 = (unsigned long)((unsigned int)(arg0[(long)(parent)]));
    t167 = arg0[(long)(child)];
    if (((((unsigned int)(var33) == (unsigned int)(t167)) | ((long)((int)(var33)) < (long)((int)(t167)))) != 0)) {
        goto L_132a;
    }
    tmp = arg0[(long)(parent)];
    arg0[(long)(parent)] = arg0[(long)(child)];
    arg0[(long)(child)] = tmp;
    parent = child;
    goto L_1267;
    L_132a: ;
    local_4 = arg1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
heap_push pass 54 lines 
// glaurung: heap_push @ 0x1100
int32_t heap_push(int32_t * arg0, int32_t arg1, int32_t arg2, int32_t arg3) {
    int child;
    int parent;
    int tmp;
    int local_4;
    long t157;
    long var14;
    long var7;
    // x86-64 prologue: save rbp
    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 (((long)(arg2) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg2)) == 16) | ((long)(arg2) < 16)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if ((arg2 <= arg1)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    child = arg1;
    arg0[(long)(child)] = arg3;
    while (((((unsigned long)((unsigned int)(child)) == 0) | ((long)(child) < 0)) == 0)) {
        var7 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(child)) - 1)));
        parent = ((int)((((long long)(int)((((unsigned long)((long)((int)(var7))) >> 32) & 0xffffffff)) * (((long long)1) << 32)) + (unsigned int)(var7)) / (int)(2)));
        var14 = (unsigned long)((unsigned int)(arg0[(long)(parent)]));
        t157 = arg0[(long)(child)];
        if (((((unsigned int)(var14) == (unsigned int)(t157)) | ((long)((int)(var14)) < (long)((int)(t157)))) != 0)) {
            break;
        }
        tmp = arg0[(long)(parent)];
        arg0[(long)(parent)] = arg0[(long)(child)];
        arg0[(long)(child)] = tmp;
        child = parent;
    }
    local_4 = ((unsigned int)(arg1) + 1);
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

2/2
heap_pop pass 79 lines 
// glaurung: heap_pop @ 0x1160
int32_t heap_pop(int32_t * arg0, int32_t arg1, int32_t * arg2) {
    int tmp;
    int left;
    int child;
    int right;
    long ret;
    long var10;
    long var11;
    long var12;
    long var13;
    int var18;
    long var4;
    long var7;
    long var9;
    ret = 0xffffffff;
    if (((unsigned long)((unsigned long)((unsigned int)((arg1 - 17)))) < (unsigned long)(0xfffffff0))) {
        // x86-64 epilogue: tear down frame
        return ret;
    }
    if ((arg0 == 0)) {
        // x86-64 epilogue: tear down frame
        return ret;
    }
    if ((arg2 == 0)) {
        // x86-64 epilogue: tear down frame
        return ret;
    }
    *(int *)(((long)arg2)) = *(int *)(((long)arg0));
    ret = (unsigned long)((unsigned int)((arg1 - 1)));
    tmp = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + ret * 4))));
    *(int *)(((long)arg0)) = tmp;
    if (((unsigned long)((unsigned long)((unsigned int)(arg1))) < (unsigned long)(3))) {
        // x86-64 epilogue: tear down frame
        return ret;
    }
    var4 = 0;
    var7 = 2;
    left = 1;
    L_11a0: ;
    if (((long)((int)(var7)) < (long)((int)(ret)))) {
        var9 = (long)((int)(var7));
        var10 = (unsigned long)((unsigned int)(arg0[(long)((int)(var7))]));
        var11 = (long)(left);
        var12 = (unsigned long)((unsigned int)(arg0[(long)(left)]));
        var13 = (unsigned long)((unsigned int)(var7));
        if (((long)((int)(var12)) <= (long)((int)(var10)))) {
            goto L_11c6;
        }
        child = var13;
        if (((((unsigned int)(tmp) == (unsigned int)(var10)) | ((long)(tmp) < (long)((int)(var10)))) == 0)) {
            goto L_11d3;
        }
        // x86-64 epilogue: tear down frame
        return ret;
    }
    var11 = (long)(left);
    var12 = (unsigned long)((unsigned int)(arg0[(long)(left)]));
    L_11c6: ;
    var10 = (unsigned long)((unsigned int)(var12));
    var9 = var11;
    child = (unsigned long)((unsigned int)(left));
    if ((((unsigned int)(tmp) == (unsigned int)(var12)) | ((long)(tmp) < (long)((int)(var12))))) {
        // x86-64 epilogue: tear down frame
        return ret;
    }
    L_11d3: ;
    arg0[(long)((int)(var4))] = var10;
    *(int *)(((long)arg0 + var9 * 4)) = tmp;
    var18 = ((unsigned int)((child + child)) + 1);
    left = (unsigned long)((unsigned int)(var18));
    var7 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)((child + child))) + 2)));
    var4 = (unsigned long)((unsigned int)(child));
    if (((long)((int)(var18)) < (long)((int)(ret)))) {
        goto L_11a0;
    }
    // x86-64 epilogue: tear down frame
    return ret;
}
heap_push pass 44 lines 
// glaurung: heap_push @ 0x1100
int32_t heap_push(int32_t * arg0, int32_t arg1, int32_t arg2, int32_t arg3) {
    int parent;
    int tmp;
    long ret;
    long var12;
    long var4;
    long var5;
    long var6;
    ret = 0xffffffff;
    if ((arg2 <= arg1)) {
        return ret;
    }
    if (((((unsigned long)((unsigned int)(arg2)) == 16) | ((long)(arg2) < 16)) == 0)) {
        return ret;
    }
    if ((arg0 == 0)) {
        return ret;
    }
    if (((long)((int)((arg2 | arg1))) < 0)) {
        return ret;
    }
    arg0[(long)(arg1)] = arg3;
    if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
        var4 = (unsigned long)((unsigned int)(arg1));
        while (1) {
            var5 = (unsigned long)((unsigned int)((var4 - 1)));
            var6 = (unsigned long)((unsigned int)(var4));
            parent = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var5)) >> 1)));
            tmp = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + parent * 4))));
            var12 = (unsigned long)((unsigned int)(arg0[(unsigned long)((unsigned int)(var4))]));
            if (((((unsigned int)(tmp) == (unsigned int)(var12)) | ((long)(tmp) < (long)((int)(var12)))) != 0)) {
                break;
            }
            *(int *)(((long)arg0 + parent * 4)) = var12;
            *(int *)(((long)arg0 + var6 * 4)) = tmp;
            var4 = (unsigned long)((unsigned int)(parent));
            if (((unsigned long)((unsigned long)((unsigned int)(var5))) <= (unsigned long)(1))) {
                break;
            }
        }
    }
    return (unsigned int)((arg1 + 1));
}

gcc -O0

2/2
heap_pop pass 54 lines 
// glaurung: heap_pop @ 0x1219
int32_t heap_pop(int32_t * arg0, int32_t arg1, int32_t * arg2) {
    int parent;
    int left;
    int right;
    int child;
    int tmp;
    long var33;
    long var39;
    long var45;
    parent = 0;
    if ((arg0 != 0)) {
        if ((arg2 != 0)) {
            if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
                if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                    goto L_1257;
                }
            }
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_1257: ;
    *(int *)((long)arg2) = *(int *)((long)arg0);
    *(int *)((long)arg0) = *(int *)(((long)arg0 + (((long)(arg1) << 2) - 4)));
    arg1 = (arg1 - 1);
    L_1283: ;
    left = ((unsigned int)(((unsigned long)((unsigned int)(parent)) + (unsigned long)((unsigned int)(parent)))) + 1);
    right = ((unsigned int)(left) + 1);
    if ((arg1 <= left)) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(arg1);
    }
    if ((right < arg1)) {
        if (((long)((int)(arg0[(long)(right)])) < (long)((int)(arg0[(long)(left)])))) {
            var33 = (unsigned long)((unsigned int)(right));
            goto L_12e3;
        }
    }
    var33 = (unsigned long)((unsigned int)(left));
    L_12e3: ;
    child = var33;
    var39 = (unsigned long)((unsigned int)(arg0[(long)(parent)]));
    var45 = (unsigned long)((unsigned int)(arg0[(long)(child)]));
    if ((((unsigned int)(var39) == (unsigned int)(var45)) | ((long)((int)(var39)) < (long)((int)(var45))))) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(arg1);
    }
    tmp = arg0[(long)(parent)];
    arg0[(long)(parent)] = arg0[(long)(child)];
    arg0[(long)(child)] = tmp;
    parent = child;
    goto L_1283;
}
heap_push pass 45 lines 
// glaurung: heap_push @ 0x10f9
int32_t heap_push(int32_t * arg0, int32_t arg1, int32_t arg2, int32_t arg3) {
    int child;
    int parent;
    int tmp;
    long var10;
    long var25;
    long var31;
    if ((arg0 != 0)) {
        if ((0 <= (long)(arg1))) {
            if ((0 <= (long)(arg2))) {
                if (((((unsigned long)((unsigned int)(arg2)) == 16) | ((long)(arg2) < 16)) != 0)) {
                    if ((arg1 < arg2)) {
                        goto L_1139;
                    }
                }
            }
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_1139: ;
    child = arg1;
    arg0[(long)(child)] = arg3;
    goto L_1204;
    L_115d: ;
    var10 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(child)) - 1)));
    parent = ((int)((var10 + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var10)) >> 31))))) >> 1);
    var25 = (unsigned long)((unsigned int)(arg0[(long)(parent)]));
    var31 = (unsigned long)((unsigned int)(arg0[(long)(child)]));
    if ((((unsigned int)(var25) == (unsigned int)(var31)) | ((long)((int)(var25)) < (long)((int)(var31))))) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(((unsigned long)((unsigned int)(arg1)) + 1));
    }
    tmp = arg0[(long)(parent)];
    arg0[(long)(parent)] = arg0[(long)(child)];
    arg0[(long)(child)] = tmp;
    child = parent;
    L_1204: ;
    if (((((unsigned long)((unsigned int)(child)) == 0) | ((long)(child) < 0)) == 0)) {
        goto L_115d;
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)((unsigned int)(arg1)) + 1));
}

gcc -O2

2/2
heap_pop pass 74 lines 
// glaurung: heap_pop @ 0x1160
int32_t heap_pop(int32_t * arg0, int32_t arg1, int32_t * arg2) {
    int right;
    int left;
    int child;
    int parent;
    long var0;
    long var11;
    long var12;
    long var13;
    long var14;
    long var16;
    long var20;
    long var22;
    long var23;
    long var3;
    long var4;
    if ((arg0 == 0)) {
        goto L_1201;
    }
    if ((arg2 == 0)) {
        goto L_1201;
    }
    var0 = (unsigned long)((unsigned int)((arg1 - 1)));
    if (((unsigned long)(15) < (unsigned long)((unsigned long)((unsigned int)(var0))))) {
        goto L_1201;
    }
    var3 = (unsigned long)((unsigned int)(var0));
    *(int *)(((long)arg2)) = *(int *)(((long)arg0));
    var4 = (unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(arg1) * 4)) - 4))));
    *(int *)(((long)arg0)) = var4;
    if ((((unsigned long)((unsigned int)(var0)) == 1) | ((long)((int)(var0)) < 1))) {
        goto L_11fa;
    }
    right = 2;
    left = 1;
    var11 = 0;
    goto L_11c7;
    L_11b0: ;
    *(int *)((var12)) = var13;
    var14 = (unsigned long)((unsigned int)((child + child)));
    left = (unsigned long)((unsigned int)((var14 + 1)));
    *(int *)((var16)) = var4;
    right = (unsigned long)((unsigned int)((var14 + 2)));
    if ((((unsigned int)(var0) == (unsigned int)(left)) | ((long)((int)(var0)) < (long)(left)))) {
        goto L_11fa;
    }
    var11 = (unsigned long)((unsigned int)(child));
    L_11c7: ;
    var20 = (unsigned long)((unsigned int)(left));
    var16 = (long)(((long)arg0 + ((long)(left) * 4)));
    var13 = (unsigned long)((unsigned int)(*(int *)((var16))));
    child = (unsigned long)((unsigned int)(left));
    if (((((unsigned int)(var0) == (unsigned int)(right)) | ((long)((int)(var0)) < (long)(right))) == 0)) {
        var22 = (long)(((long)arg0 + ((long)(right) * 4)));
        var23 = (unsigned long)((unsigned int)(*(int *)((var22))));
        child = var20;
        if (((long)((int)(var23)) < (long)((int)(var13)))) {
            var13 = (unsigned long)((unsigned int)(var23));
            var16 = var22;
            child = (unsigned long)((unsigned int)(right));
        }
    }
    var12 = (long)(((long)arg0 + ((long)((int)(var11)) * 4)));
    if (((((unsigned int)(var4) == (unsigned int)(var13)) | ((long)((int)(var4)) < (long)((int)(var13)))) == 0)) {
        goto L_11b0;
    }
    L_11fa: ;
    // x86-64 epilogue: tear down frame
    return (unsigned int)(var3);
    L_1201: ;
    var3 = 0xffffffff;
    goto L_11fa;
}
heap_push pass 51 lines 
// glaurung: heap_push @ 0x1100
int32_t heap_push(int32_t * arg0, int32_t arg1, int32_t arg2, int32_t arg3) {
    int parent;
    int tmp;
    long var0;
    long var1;
    long var12;
    int var3;
    long var4;
    long var5;
    long var7;
    var0 = (long)arg0;
    var1 = (unsigned long)((unsigned int)(arg1));
    if ((arg0 == 0)) {
        return 0xffffffff;
    }
    if (((long)(arg1) < 0)) {
        return 0xffffffff;
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
        return 0xffffffff;
    }
    if ((arg2 <= arg1)) {
        return 0xffffffff;
    }
    arg0[(long)(arg1)] = arg3;
    if (((unsigned long)((unsigned int)(arg1)) == 0)) {
        var3 = (var1 + 1);
        return (unsigned int)(var3);
    }
    var4 = (long)(arg1);
    var5 = (unsigned long)((unsigned int)(arg3));
    while (1) {
        var7 = (var0 + (var4 * 4));
        parent = (unsigned long)((unsigned int)(((int)((var4 - 1)) >> 1)));
        var12 = (var0 + ((long)(parent) * 4));
        tmp = (unsigned long)((unsigned int)(*(int *)((var12))));
        if (((((unsigned int)(tmp) == (unsigned int)(var5)) | ((long)(tmp) < (long)((int)(var5)))) != 0)) {
            break;
        }
        *(int *)((var12)) = var5;
        *(int *)((var7)) = tmp;
        if (((unsigned long)((unsigned int)(parent)) == 0)) {
            break;
        }
        var5 = (unsigned long)((unsigned int)(*(int *)((var12))));
        var4 = (long)(parent);
    }
    var3 = (var1 + 1);
    return (unsigned int)(var3);
}

← 213 fixtures