glaurung

Fixture 21

graph dfs

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/21_graph_dfs.c source 
#include <stdint.h>

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

clang -O2

1/1
graph_dfs pass 82 lines 
// glaurung: graph_dfs @ 0x1100
__attribute__((no_stack_protector)) int32_t graph_dfs(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    int count;
    int top;
    int vertex;
    unsigned char local_48[72];
    unsigned char local_59[17];
    long ret;
    long var10;
    long var11;
    int var12;
    long var13;
    long var15;
    long var16;
    long var22;
    long var23;
    long var24;
    long var25;
    long var6;
    long var7;
    // x86-64 prologue: save callee registers, frame 8 bytes
    *(int *)((&local_59[0] + 1)) = 0;
    *(int *)((&local_59[0] + 5)) = 0;
    *(int *)((&local_59[0] + 9)) = 0;
    *(int *)((&local_59[0] + 13)) = 0;
    ret = 0;
    if ((arg1 <= arg2)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if (((long)(arg2) < 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if (((unsigned long)((unsigned long)((unsigned int)((arg1 - 5)))) < (unsigned long)(0xfffffffc))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg3 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    *(int *)(&local_48[0]) = arg2;
    var6 = (unsigned long)((unsigned int)(arg1));
    var7 = (long)((arg0 - 1));
    ret = 0;
    var10 = 1;
    var11 = 0;
    do {
        var12 = (var10 - 1);
        var13 = (unsigned long)((unsigned int)(var12));
        var15 = (long)((int)(*(int *)((&local_48[0] + ((unsigned long)((unsigned int)(var12)) * 4)))));
        var16 = var11;
        if (((unsigned long)((unsigned char)(*(char *)((&local_59[0] + (var15 + 1))))) == 0)) {
            *(signed char *)((&local_59[0] + (var15 + 1))) = 1;
            ret = (unsigned long)((unsigned int)((var11 + 1)));
            arg3[(long)((int)(var11))] = var15;
            var22 = (var7 + ((long)((int)((var15 * arg1))) * 4));
            var23 = var6;
            var24 = var13;
            do {
                var25 = var23;
                var23 = (var23 - 1);
                var13 = var24;
                if ((((unsigned long)((unsigned int)(*(int *)((var22 + var25 * 4)))) != 0) && ((unsigned long)((unsigned char)(*(char *)((&local_59[0] + var25)))) == 0))) {
                    var13 = (unsigned long)((unsigned int)((var24 + 1)));
                    *(int *)((&local_48[0] + ((long)((int)(var24)) * 4))) = (var25 - 1);
                }
                var16 = ret;
                var24 = var13;
            } while ((1 < (var23 + 1)));
        }
        var10 = var13;
        var11 = var16;
    } while (((((unsigned long)((unsigned int)(var13)) == 0) | ((long)((int)(var13)) < 0)) == 0));
    // x86-64 epilogue: restore callee registers
    return ret;
}

gcc -O0

1/1
graph_dfs pass 56 lines 
// glaurung: graph_dfs @ 0x1119
int32_t graph_dfs(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int top;
    int count;
    int vertex;
    int next;
    unsigned char local_20[16];
    unsigned char local_60[64];
    long local_8;
    long ret;
    long var16;
    long var4;
    long var41;
    // x86-64 prologue: save rbp, frame 144 bytes
    local_8 = (long)(0x28);
    *(long *)(&local_20[0]) = 0;
    *(long *)((&local_20[0] + 8)) = 0;
    top = 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)(top));
        top = ((unsigned int)(top) + 1);
        *(int *)((&local_60[0] + ((long)((int)(var4)) * 4))) = arg2;
        while (((((unsigned long)((unsigned int)(top)) == 0) | ((long)(top) < 0)) == 0)) {
            top = (top - 1);
            vertex = *(int *)((&local_60[0] + ((long)(top) * 4)));
            if (((unsigned long)((unsigned char)(((unsigned int)((unsigned char)(*(char *)((&local_20[0] + (long)(vertex))))) & 255))) == 0)) {
                *(signed char *)((&local_20[0] + (long)(vertex))) = 1;
                var16 = (unsigned long)((unsigned int)(count));
                count = ((unsigned int)(count) + 1);
                arg3[(long)((int)(var16))] = vertex;
                next = ((unsigned int)(arg1) - 1);
                while ((0 <= (long)(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)) {
                            var41 = (unsigned long)((unsigned int)(top));
                            top = ((unsigned int)(top) + 1);
                            *(int *)((&local_60[0] + ((long)((int)(var41)) * 4))) = next;
                        }
                    }
                    next = (next - 1);
                }
            } else {
            }
        }
        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_dfs pass 100 lines 
// glaurung: graph_dfs @ 0x1120
int32_t graph_dfs(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int top;
    int vertex;
    int next;
    int count;
    long rbp;
    unsigned char stack_0[64];
    unsigned char stack_1[56];
    long var10;
    long var11;
    long var12;
    long var13;
    long var14;
    long var17;
    long var22;
    long var25;
    long var26;
    long var31;
    long var33;
    long var35;
    long var39;
    long var5;
    long var6;
    // x86-64 prologue: save callee registers, frame 8 bytes
    var5 = (long)arg0;
    *(long *)((&stack_1[0] + 40)) = rbp;
    *(long *)((&stack_1[0] + 32)) = var6;
    *(long *)((&stack_1[0] + 24)) = (long)((long)(0x28));
    *(int *)(&stack_1[0]) = 0;
    *(int *)((&stack_1[0] + 4)) = 0;
    *(int *)((&stack_1[0] + 8)) = 0;
    *(int *)((&stack_1[0] + 12)) = 0;
    var10 = var11;
    if ((arg0 == 0)) {
        goto L_11f0;
    }
    var12 = (long)arg3;
    var10 = var11;
    if ((arg3 == 0)) {
        goto L_11f0;
    }
    var13 = (unsigned long)((unsigned int)((arg1 - 1)));
    var14 = (unsigned long)((unsigned int)(arg1));
    var10 = 0;
    if (((unsigned long)(3) < (unsigned long)((unsigned long)((unsigned int)(var13))))) {
        goto L_11f3;
    }
    if (((long)(arg2) < 0)) {
        goto L_11f0;
    }
    if ((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2))) {
        goto L_11f0;
    }
    *(int *)(&stack_0[0]) = arg2;
    var17 = 0;
    rbp = (long)(&stack_0[0]);
    top = 1;
    L_118b: ;
    var10 = (unsigned long)((unsigned int)(var17));
    var22 = (rbp + ((long)(top) * 4));
    do {
        if (((unsigned long)((unsigned int)(top)) == 0)) {
            goto L_11f3;
        }
        vertex = (long)((int)(*(int *)((var22 - 0x4))));
        var25 = (unsigned long)((unsigned int)((top - 1)));
        var22 = (var22 - 4);
        var26 = (unsigned long)((unsigned int)(vertex));
        top = var25;
    } while (((unsigned long)((unsigned char)(*(char *)((&stack_1[0] + vertex)))) != 0));
    *(signed char *)((&stack_1[0] + vertex)) = 1;
    *(int *)((var12 + var17 * 4)) = vertex;
    var31 = (var5 + ((long)((int)((var26 * var14))) * 4));
    next = (long)((int)(var13));
    var33 = var25;
    do {
        var35 = var33;
        if ((((unsigned long)((unsigned int)(*(int *)((var31 + next * 4)))) != 0) && ((unsigned long)((unsigned char)(*(char *)((&stack_1[0] + next)))) == 0))) {
            *(int *)((&stack_0[0] + ((long)((int)(var33)) * 4))) = next;
            var35 = (unsigned long)((unsigned int)((var33 + 1)));
        }
        var39 = ((unsigned long)((unsigned int)(next)) - 1);
        next = var39;
        var33 = var35;
    } while (((unsigned long)((unsigned int)(var39)) != 0xffffffff));
    var17 = (var17 + 1);
    top = var35;
    goto L_118b;
    L_11f0: ;
    var10 = 0;
    L_11f3: ;
    if ((*(long *)((&stack_1[0] + 24)) == 0x28)) {
        rbp = *(long *)((&stack_1[0] + 40));
        // x86-64 epilogue: restore callee registers
        return (unsigned int)(var10);
    }
    __stack_chk_fail();
}

← 213 fixtures