glaurung

Fixture 20

graph bfs

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

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

tests/decompiler_fixtures/src/20_graph_bfs.c source 
#include <stdint.h>

__attribute__((noinline)) int32_t graph_bfs(const int32_t *adjacency, int32_t n,
                                             int32_t start, int32_t *order) {
    int32_t queue[16];
    uint8_t seen[16] = {0};
    int32_t head = 0;
    int32_t tail = 0;
    int32_t count = 0;
    if (adjacency == 0 || order == 0 || n <= 0 || n > 4 || start < 0 ||
        start >= n) {
        return 0;
    }
    queue[tail++] = start;
    seen[start] = 1;
    while (head < tail) {
        int32_t vertex = queue[head++];
        int32_t next;
        order[count++] = vertex;
        for (next = 0; next < n; ++next) {
            if (adjacency[vertex * n + next] != 0 && seen[next] == 0) {
                seen[next] = 1;
                queue[tail++] = next;
            }
        }
    }
    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
graph_bfs pass 71 lines 
// glaurung: graph_bfs @ 0x1110
__attribute__((no_stack_protector)) int32_t graph_bfs(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    extern void * memset(void *, int, __SIZE_TYPE__);
    int head;
    int tail;
    int count;
    int vertex;
    int next;
    int local_4;
    unsigned char local_60[64];
    unsigned char local_70[16];
    void * var1;
    long var12;
    long var20;
    long var37;
    long var5;
    // x86-64 prologue: save rbp, frame 144 bytes
    var1 = memset((void *)(&local_70[0]), 0, (__SIZE_TYPE__)(16));
    head = 0;
    tail = 0;
    count = 0;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if ((arg3 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if ((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0))) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 4) | ((long)(arg1) < 4)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((long)(arg2) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if ((arg1 <= arg2)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    var5 = (unsigned long)((unsigned int)(tail));
    tail = ((unsigned int)(tail) + 1);
    *(int *)((&local_60[0] + ((long)((int)(var5)) * 4))) = arg2;
    *(signed char *)((&local_70[0] + (long)(arg2))) = 1;
    while ((head < tail)) {
        var12 = (unsigned long)((unsigned int)(head));
        head = ((unsigned int)(head) + 1);
        vertex = *(int *)((&local_60[0] + ((long)((int)(var12)) * 4)));
        var20 = (unsigned long)((unsigned int)(count));
        count = ((unsigned int)(count) + 1);
        arg3[(long)((int)(var20))] = vertex;
        for (next = 0; (next < arg1); next++) {
            if (((unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(vertex)) * arg1))) + next)))])) != 0)) {
                if (((unsigned long)((unsigned int)((unsigned char)(*(char *)((&local_70[0] + (long)(next)))))) == 0)) {
                    *(signed char *)((&local_70[0] + (long)(next))) = 1;
                    var37 = (unsigned long)((unsigned int)(tail));
                    tail = ((unsigned int)(tail) + 1);
                    *(int *)((&local_60[0] + ((long)((int)(var37)) * 4))) = next;
                }
            }
        }
    }
    local_4 = count;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

1/1
graph_bfs pass 113 lines 
// glaurung: graph_bfs @ 0x1100
__attribute__((no_stack_protector)) int32_t graph_bfs(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    int count;
    int tail;
    int vertex;
    int next;
    unsigned char local_58[88];
    unsigned char local_68[16];
    long var11;
    long var13;
    long var16;
    long var21;
    long var22;
    long var25;
    long var28;
    long var31;
    long var35;
    long var5;
    long var9;
    // x86-64 prologue: save callee registers, frame 16 bytes
    *(int *)(&local_68[0]) = 0;
    *(int *)((&local_68[0] + 4)) = 0;
    *(int *)((&local_68[0] + 8)) = 0;
    *(int *)((&local_68[0] + 12)) = 0;
    var5 = 0;
    count = 0;
    if ((arg1 <= arg2)) {
        // x86-64 epilogue: restore callee registers
        return count;
    }
    count = var5;
    if (((long)(arg2) < 0)) {
        // x86-64 epilogue: restore callee registers
        return count;
    }
    count = var5;
    if (((unsigned long)((unsigned long)((unsigned int)((arg1 - 5)))) < (unsigned long)(0xfffffffc))) {
        // x86-64 epilogue: restore callee registers
        return count;
    }
    count = var5;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return count;
    }
    count = var5;
    if ((arg3 == 0)) {
        // x86-64 epilogue: restore callee registers
        return count;
    }
    *(int *)(&local_58[0]) = arg2;
    *(signed char *)((&local_68[0] + (unsigned long)((unsigned int)(arg2)))) = 1;
    var9 = (*(char *)(&local_68[0]) & 255);
    var11 = (*(char *)((&local_68[0] + 1)) & 255);
    var13 = (*(char *)((&local_68[0] + 2)) & 255);
    count = 1;
    var16 = (*(char *)((&local_68[0] + 3)) & 255);
    tail = 1;
    vertex = arg2;
    L_1170: ;
    *(int *)(((long)arg3 + count * 4 - 0x4)) = vertex;
    var21 = (long)((int)((vertex * arg1)));
    if (((unsigned long)((unsigned int)(*(int *)(((long)arg0 + var21 * 4)))) != 0)) {
        if (((unsigned long)((unsigned char)((var9 & 255))) == 0)) {
            var22 = (long)(tail);
            tail = (unsigned long)((unsigned int)((tail + 1)));
            *(int *)((&local_58[0] + (var22 * 4))) = 0;
            var9 = 1;
        }
    }
    if (((unsigned long)((unsigned int)(arg1)) != 1)) {
        if (((unsigned long)((unsigned int)(*(int *)(((long)arg0 + var21 * 4 + 0x4)))) != 0)) {
            if (((unsigned long)((unsigned char)((var11 & 255))) == 0)) {
                var25 = (long)(tail);
                tail = (unsigned long)((unsigned int)((tail + 1)));
                *(int *)((&local_58[0] + (var25 * 4))) = 1;
                var11 = 1;
            }
        }
        if (((unsigned long)((unsigned int)(arg1)) != 2)) {
            if (((unsigned long)((unsigned int)(*(int *)(((long)arg0 + var21 * 4 + 0x8)))) != 0)) {
                if (((unsigned long)((unsigned char)((var13 & 255))) == 0)) {
                    var28 = (long)(tail);
                    tail = (unsigned long)((unsigned int)((tail + 1)));
                    *(int *)((&local_58[0] + (var28 * 4))) = 2;
                    var13 = 1;
                }
            }
            if (((unsigned long)((unsigned int)(arg1)) != 3)) {
                if (((unsigned long)((unsigned int)(*(int *)(((long)arg0 + var21 * 4 + 0xc)))) != 0)) {
                    if (((unsigned long)((unsigned char)((var16 & 255))) == 0)) {
                        var31 = (long)(tail);
                        tail = (unsigned long)((unsigned int)((tail + 1)));
                        *(int *)((&local_58[0] + (var31 * 4))) = 3;
                        var16 = 1;
                    }
                }
            }
        }
    }
    if ((count < (long)(tail))) {
        var35 = (unsigned long)((unsigned int)(*(int *)((&local_58[0] + (count * 4)))));
        count = (count + 1);
        vertex = var35;
        goto L_1170;
    }
    *(signed char *)(&local_68[0]) = var9;
    *(signed char *)((&local_68[0] + 1)) = var11;
    *(signed char *)((&local_68[0] + 2)) = var13;
    *(signed char *)((&local_68[0] + 3)) = var16;
    // x86-64 epilogue: restore callee registers
    return count;
}

gcc -O0

1/1
graph_bfs pass 56 lines 
// glaurung: graph_bfs @ 0x1119
int32_t graph_bfs(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int head;
    int tail;
    int count;
    int vertex;
    int next;
    unsigned char local_20[16];
    unsigned char local_60[64];
    long local_8;
    long ret;
    long var11;
    long var15;
    long var4;
    long var40;
    // x86-64 prologue: save rbp, frame 160 bytes
    local_8 = (long)(0x28);
    *(long *)(&local_20[0]) = 0;
    *(long *)((&local_20[0] + 8)) = 0;
    head = 0;
    tail = 0;
    count = 0;
    if (((((((arg0 == 0) || (arg3 == 0)) || (((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0))) || ((((unsigned long)((unsigned int)(arg1)) == 4) | ((long)(arg1) < 4)) == 0)) || ((long)(arg2) < 0)) || (arg1 <= arg2))) {
        ret = 0;
    } else {
        var4 = (unsigned long)((unsigned int)(tail));
        tail = ((unsigned int)(tail) + 1);
        *(int *)((&local_60[0] + ((long)((int)(var4)) * 4))) = arg2;
        *(signed char *)((&local_20[0] + (long)(arg2))) = 1;
        while ((head < tail)) {
            var11 = (unsigned long)((unsigned int)(head));
            head = ((unsigned int)(head) + 1);
            vertex = *(int *)((&local_60[0] + ((long)((int)(var11)) * 4)));
            var15 = (unsigned long)((unsigned int)(count));
            count = ((unsigned int)(count) + 1);
            arg3[(long)((int)(var15))] = vertex;
            for (next = 0; (next < arg1); next++) {
                if (((unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)(next)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(vertex)) * arg1))))))])) != 0)) {
                    if (((unsigned long)((unsigned char)(((unsigned int)((unsigned char)(*(char *)((&local_20[0] + (long)(next))))) & 255))) == 0)) {
                        *(signed char *)((&local_20[0] + (long)(next))) = 1;
                        var40 = (unsigned long)((unsigned int)(tail));
                        tail = ((unsigned int)(tail) + 1);
                        *(int *)((&local_60[0] + ((long)((int)(var40)) * 4))) = next;
                    }
                }
            }
        }
        ret = (unsigned long)((unsigned int)(count));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}

gcc -O2

1/1
graph_bfs pass 79 lines 
// glaurung: graph_bfs @ 0x1120
int32_t graph_bfs(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int count;
    int tail;
    int next;
    long local_10;
    unsigned char local_28[16];
    unsigned char local_68[64];
    long var10;
    long var13;
    long var14;
    long var20;
    long var26;
    long var28;
    long var8;
    long var9;
    local_10 = (long)(0x28);
    *(int *)(&local_28[0]) = 0;
    *(int *)((&local_28[0] + 4)) = 0;
    *(int *)((&local_28[0] + 8)) = 0;
    *(int *)((&local_28[0] + 12)) = 0;
    var8 = var9;
    if ((arg0 == 0)) {
        goto L_11d0;
    }
    var10 = (long)arg3;
    var8 = var9;
    if ((arg3 == 0)) {
        goto L_11d0;
    }
    var8 = 0;
    if (((unsigned long)(3) < (unsigned long)((unsigned long)((unsigned int)((arg1 - 1)))))) {
        goto L_11d3;
    }
    if (((long)(arg2) < 0)) {
        goto L_11d0;
    }
    if ((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2))) {
        goto L_11d0;
    }
    var13 = (long)(arg2);
    var14 = (long)arg0;
    *(signed char *)((&local_28[0] + (long)(arg2))) = 1;
    count = 1;
    tail = 1;
    var20 = (unsigned long)((unsigned int)(arg2));
    L_1188: ;
    *(int *)((var10 + count * 4 - 0x4)) = var20;
    var8 = (unsigned long)((unsigned int)(count));
    var26 = (var14 + ((long)((int)((var20 * arg1))) * 4));
    next = 0;
    var28 = (unsigned long)((unsigned int)(tail));
    do {
        tail = var28;
        if ((((unsigned long)((unsigned int)(*(int *)((var26 + next * 4)))) != 0) && ((unsigned long)((unsigned char)(*(char *)((&local_28[0] + next)))) == 0))) {
            *(signed char *)((&local_28[0] + next)) = 1;
            *(int *)((&local_68[0] + ((long)((int)(var28)) * 4))) = next;
            tail = (unsigned long)((unsigned int)((var28 + 1)));
        }
        var13 = ((unsigned long)((unsigned int)(next)) + 1);
        next = var13;
        var28 = (unsigned long)((unsigned int)(tail));
    } while (((((unsigned int)(arg1) == (unsigned int)(var13)) | ((long)(arg1) < (long)((int)(var13)))) == 0));
    if ((((unsigned int)(tail) == (unsigned int)(count)) | (tail < count))) {
        goto L_11d3;
    }
    var20 = (unsigned long)((unsigned int)(*(int *)((&local_68[0] + (count * 4)))));
    count = (count + 1);
    goto L_1188;
    L_11d0: ;
    var8 = 0;
    L_11d3: ;
    if ((local_10 == 0x28)) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var8);
    }
    __stack_chk_fail();
}

← 213 fixtures