glaurung

Fixture 23

topological sort

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

__attribute__((noinline)) int32_t topological_sort(const int32_t *adjacency,
                                                    int32_t n,
                                                    int32_t *order) {
    int32_t indegree[16] = {0};
    int32_t queue[16];
    int32_t head = 0;
    int32_t tail = 0;
    int32_t count = 0;
    int32_t from;
    int32_t to;
    if (adjacency == 0 || order == 0 || n < 0 || n > 4) {
        return -1;
    }
    for (from = 0; from < n; ++from) {
        for (to = 0; to < n; ++to) {
            if (adjacency[from * n + to] != 0) {
                ++indegree[to];
            }
        }
    }
    for (to = 0; to < n; ++to) {
        if (indegree[to] == 0) {
            queue[tail++] = to;
        }
    }
    while (head < tail) {
        from = queue[head++];
        order[count++] = from;
        for (to = 0; to < n; ++to) {
            if (adjacency[from * n + to] != 0 && --indegree[to] == 0) {
                queue[tail++] = to;
            }
        }
    }
    return count == n ? count : -1;
}

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
topological_sort pass 83 lines 
// glaurung: topological_sort @ 0x1110
__attribute__((no_stack_protector)) int32_t topological_sort(const int32_t * arg0, int32_t arg1, int32_t * arg2) {
    extern void * memset(void *, int, __SIZE_TYPE__);
    int head;
    int tail;
    int count;
    int from;
    int to;
    int local_4;
    unsigned char local_60[64];
    unsigned char local_a0[64];
    int local_b8;
    void * var1;
    long var25;
    long var34;
    long var42;
    int var57;
    long var60;
    // x86-64 prologue: save rbp, frame 192 bytes
    var1 = memset((void *)(&local_60[0]), 0, (__SIZE_TYPE__)(64));
    head = 0;
    tail = 0;
    count = 0;
    if ((arg0 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if ((arg2 == 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 (((((unsigned long)((unsigned int)(arg1)) == 4) | ((long)(arg1) < 4)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    from = 0;
    while ((from < arg1)) {
        for (to = 0; (to < arg1); to++) {
            if (((unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(from)) * arg1))) + to)))])) != 0)) {
                *(int *)((&local_60[0] + ((long)(to) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_60[0] + ((long)(to) * 4))))) + 1);
            }
        }
        from = ((unsigned int)(from) + 1);
    }
    for (to = 0; (to < arg1); to++) {
        if (((unsigned long)((unsigned int)(*(int *)((&local_60[0] + ((long)(to) * 4))))) == 0)) {
            var25 = (unsigned long)((unsigned int)(tail));
            tail = ((unsigned int)(tail) + 1);
            *(int *)((&local_a0[0] + ((long)((int)(var25)) * 4))) = to;
        }
    }
    while ((head < tail)) {
        var34 = (unsigned long)((unsigned int)(head));
        head = ((unsigned int)(head) + 1);
        from = *(int *)((&local_a0[0] + ((long)((int)(var34)) * 4)));
        var42 = (unsigned long)((unsigned int)(count));
        count = ((unsigned int)(count) + 1);
        arg2[(long)((int)(var42))] = from;
        for (to = 0; (to < arg1); to++) {
            if (((unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(from)) * arg1))) + to)))])) != 0)) {
                var57 = ((unsigned int)(*(int *)((&local_60[0] + ((long)(to) * 4)))) - 1);
                *(int *)((&local_60[0] + ((long)(to) * 4))) = var57;
                if (((unsigned long)((unsigned int)(var57)) == 0)) {
                    var60 = (unsigned long)((unsigned int)(tail));
                    tail = ((unsigned int)(tail) + 1);
                    *(int *)((&local_a0[0] + ((long)((int)(var60)) * 4))) = to;
                }
            }
        }
    }
    local_b8 = (((unsigned int)(count) != (unsigned int)(arg1)) ? 0xffffffff : (unsigned long)((unsigned int)(count)));
    local_4 = local_b8;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

1/1
topological_sort pass 167 lines 
// glaurung: topological_sort @ 0x1100
__attribute__((no_stack_protector)) int32_t topological_sort(const int32_t * arg0, int32_t arg1, int32_t * arg2) {
    int count;
    int tail;
    int from;
    int to;
    unsigned char local_68[104];
    unsigned char local_a8[64];
    long ret;
    long t155;
    long var12;
    long var13;
    long var14;
    long var15;
    long var16;
    long var17;
    long var18;
    long var21;
    long var22;
    long var23;
    int var25;
    int var27;
    long var32;
    long var37;
    long var39;
    long var43;
    long var51;
    long var54;
    long var55;
    long var6;
    long var8;
    // x86-64 prologue: save callee registers, frame 40 bytes
    *(int *)((&local_a8[0] + 48)) = 0;
    *(int *)((&local_a8[0] + 52)) = 0;
    *(int *)((&local_a8[0] + 56)) = 0;
    *(int *)((&local_a8[0] + 60)) = 0;
    *(int *)((&local_a8[0] + 32)) = 0;
    *(int *)((&local_a8[0] + 36)) = 0;
    *(int *)((&local_a8[0] + 40)) = 0;
    *(int *)((&local_a8[0] + 44)) = 0;
    *(int *)((&local_a8[0] + 16)) = 0;
    *(int *)((&local_a8[0] + 20)) = 0;
    *(int *)((&local_a8[0] + 24)) = 0;
    *(int *)((&local_a8[0] + 28)) = 0;
    *(int *)(&local_a8[0]) = 0;
    *(int *)((&local_a8[0] + 4)) = 0;
    *(int *)((&local_a8[0] + 8)) = 0;
    *(int *)((&local_a8[0] + 12)) = 0;
    ret = 0xffffffff;
    if (((unsigned long)(4) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg2 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var6 = 0;
    count = 0;
    if (((unsigned long)((unsigned int)(arg1)) != 0)) {
        var8 = (unsigned long)((unsigned int)(arg1));
        var12 = (unsigned long)((unsigned int)(*(int *)((&local_a8[0] + 12))));
        var13 = (long)((arg0 + 3));
        var14 = ((unsigned long)((unsigned int)(arg1)) * 4);
        var15 = (unsigned long)((unsigned int)(arg1));
        var16 = (unsigned long)((unsigned int)(*(int *)((&local_a8[0] + 4))));
        var17 = (unsigned long)((unsigned int)(*(int *)((&local_a8[0] + 8))));
        var18 = (unsigned long)((unsigned int)(*(int *)(&local_a8[0])));
        do {
            var21 = (((unsigned long)((unsigned int)(*(int *)((var13 - 0xc)))) == 0) ? (unsigned long)((unsigned int)(var18)) : (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var18)) + 1))));
            var22 = var16;
            var23 = var17;
            if (((unsigned long)((unsigned int)(arg1)) != 1)) {
                var25 = (((unsigned long)((unsigned int)(*(int *)((var13 - 0x8)))) != 0) ? (unsigned long)((unsigned int)((var16 + 1))) : var16);
                var22 = (unsigned long)((unsigned int)(var25));
                var23 = var17;
                if (((unsigned long)((unsigned int)(arg1)) != 2)) {
                    var27 = (((unsigned long)((unsigned int)(*(int *)((var13 - 0x4)))) != 0) ? (unsigned long)((unsigned int)((var17 + 1))) : var17);
                    var22 = (unsigned long)((unsigned int)(var25));
                    var23 = (unsigned long)((unsigned int)(var27));
                    if (((unsigned long)((unsigned int)(arg1)) != 3)) {
                        var12 = (unsigned long)((unsigned int)((((unsigned long)((unsigned int)(*(int *)((var13)))) == 0) ? var12 : (unsigned long)((unsigned int)((var12 + 1))))));
                        var22 = (unsigned long)((unsigned int)(var25));
                        var23 = (unsigned long)((unsigned int)(var27));
                    }
                }
            }
            var13 = (var13 + var14);
            var15 = (var15 - 1);
            var16 = var22;
            var17 = var23;
            var18 = var21;
        } while ((var15 != 0));
        *(int *)(&local_a8[0]) = var21;
        *(int *)((&local_a8[0] + 4)) = var22;
        *(int *)((&local_a8[0] + 8)) = var23;
        *(int *)((&local_a8[0] + 12)) = var12;
        count = var6;
        if (((unsigned long)((unsigned int)(arg1)) != 0)) {
            var32 = 0;
            if (((unsigned long)((unsigned int)(*(int *)(&local_a8[0]))) == 0)) {
                *(int *)(&local_68[0]) = 0;
                var32 = 1;
            }
            tail = var32;
            if (((unsigned long)((unsigned int)(arg1)) != 1)) {
                tail = var32;
                if (((unsigned long)((unsigned int)(*(int *)((&local_a8[0] + 4)))) == 0)) {
                    tail = (unsigned long)((unsigned int)((var32 + 1)));
                    *(int *)((&local_68[0] + ((unsigned long)((unsigned int)(var32)) * 4))) = 1;
                }
                if (((unsigned long)((unsigned int)(arg1)) != 2)) {
                    if (((unsigned long)((unsigned int)(*(int *)((&local_a8[0] + 8)))) == 0)) {
                        var37 = (unsigned long)((unsigned int)(tail));
                        tail = (unsigned long)((unsigned int)((tail + 1)));
                        *(int *)((&local_68[0] + (var37 * 4))) = 2;
                    }
                    if (((unsigned long)((unsigned int)(arg1)) != 3)) {
                        if (((unsigned long)((unsigned int)(*(int *)((&local_a8[0] + 12)))) == 0)) {
                            var39 = (unsigned long)((unsigned int)(tail));
                            tail = (unsigned long)((unsigned int)((tail + 1)));
                            *(int *)((&local_68[0] + (var39 * 4))) = 3;
                        }
                    }
                }
            }
            count = 0;
            var43 = 0;
            if (((((unsigned long)((unsigned int)(tail)) == 0) | ((long)(tail) < 0)) != 0)) {
                // x86-64 epilogue: restore callee registers
                return (((unsigned int)(count) == (unsigned int)(arg1)) ? count : 0xffffffff);
            }
            do {
                from = (unsigned long)((unsigned int)(*(int *)((&local_68[0] + (var43 * 4)))));
                *(int *)(((long)arg2 + var43 * 4)) = from;
                count = (var43 + 1);
                if (((unsigned long)((unsigned int)(arg1)) != 0)) {
                    var51 = (long)(((long)arg0 + ((long)((int)((from * arg1))) * 4)));
                    var54 = 0;
                    var55 = (unsigned long)((unsigned int)(tail));
                    do {
                        tail = var55;
                        if (((unsigned long)((unsigned int)(*(int *)((var51 + var54 * 4)))) != 0)) {
                            t155 = (*(int *)((&local_a8[0] + (var54 * 4))) - 1);
                            *(int *)((&local_a8[0] + (var54 * 4))) = t155;
                            tail = var55;
                            if (((unsigned long)((unsigned int)(t155)) == 0)) {
                                tail = (unsigned long)((unsigned int)((var55 + 1)));
                                *(int *)((&local_68[0] + ((long)((int)(var55)) * 4))) = var54;
                            }
                        }
                        to = (var54 + 1);
                        var54 = (unsigned long)((unsigned int)(to));
                        var55 = (unsigned long)((unsigned int)(tail));
                    } while ((var8 != to));
                }
                var43 = (unsigned long)((unsigned int)(count));
            } while ((count < (long)(tail)));
        }
    }
    // x86-64 epilogue: restore callee registers
    return (((unsigned int)(count) == (unsigned int)(arg1)) ? count : 0xffffffff);
}

gcc -O0

1/1
topological_sort pass 74 lines 
// glaurung: topological_sort @ 0x1119
int32_t topological_sort(const int32_t * arg0, int32_t arg1, int32_t * arg2) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int head;
    int tail;
    int count;
    int from;
    int to;
    unsigned char local_50[64];
    long local_8;
    unsigned char local_90[64];
    long ret;
    long var27;
    long var32;
    long var36;
    long var65;
    // x86-64 prologue: save rbp, frame 208 bytes
    local_8 = (long)(0x28);
    *(long *)(&local_90[0]) = 0;
    *(long *)((&local_90[0] + 8)) = 0;
    *(long *)((&local_90[0] + 16)) = 0;
    *(long *)((&local_90[0] + 24)) = 0;
    *(long *)((&local_90[0] + 32)) = 0;
    *(long *)((&local_90[0] + 40)) = 0;
    *(long *)((&local_90[0] + 48)) = 0;
    *(long *)((&local_90[0] + 56)) = 0;
    head = 0;
    tail = 0;
    count = 0;
    if (((((arg0 == 0) || (arg2 == 0)) || ((long)(arg1) < 0)) || (((unsigned long)((unsigned int)(arg1)) != 4) && (4 <= (long)(arg1))))) {
        ret = 0xffffffff;
    } else {
        from = 0;
        while ((from < arg1)) {
            for (to = 0; (to < arg1); to++) {
                if (((unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)(to)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(from)) * arg1))))))])) != 0)) {
                    *(int *)((&local_90[0] + ((long)(to) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_90[0] + ((long)(to) * 4))))) + 1);
                }
            }
            from = (from + 1);
        }
        for (to = 0; (to < arg1); to++) {
            if (((unsigned long)((unsigned int)(*(int *)((&local_90[0] + ((long)(to) * 4))))) == 0)) {
                var27 = (unsigned long)((unsigned int)(tail));
                tail = ((unsigned int)(tail) + 1);
                *(int *)((&local_50[0] + ((long)((int)(var27)) * 4))) = to;
            }
        }
        while ((head < tail)) {
            var32 = (unsigned long)((unsigned int)(head));
            head = ((unsigned int)(head) + 1);
            from = *(int *)((&local_50[0] + ((long)((int)(var32)) * 4)));
            var36 = (unsigned long)((unsigned int)(count));
            count = ((unsigned int)(count) + 1);
            arg2[(long)((int)(var36))] = from;
            for (to = 0; (to < arg1); to++) {
                if (((unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)(to)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(from)) * arg1))))))])) != 0)) {
                    *(int *)((&local_90[0] + ((long)(to) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_90[0] + ((long)(to) * 4))))) - 1);
                    if (((unsigned long)((unsigned int)(*(int *)((&local_90[0] + ((long)(to) * 4))))) == 0)) {
                        var65 = (unsigned long)((unsigned int)(tail));
                        tail = ((unsigned int)(tail) + 1);
                        *(int *)((&local_50[0] + ((long)((int)(var65)) * 4))) = to;
                    }
                }
            }
        }
        ret = (((unsigned int)(count) != (unsigned int)(arg1)) ? 0xffffffff : (unsigned long)((unsigned int)(count)));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}

gcc -O2

1/1
topological_sort pass 133 lines 
// glaurung: topological_sort @ 0x1120
int32_t topological_sort(const int32_t * arg0, int32_t arg1, int32_t * arg2) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int from;
    int tail;
    int count;
    int to;
    long local_20;
    unsigned char local_68[64];
    unsigned char local_a8[64];
    long ret;
    long t155;
    long var10;
    long var11;
    long var14;
    long var19;
    int var21;
    long var26;
    long var27;
    long var33;
    long var35;
    long var37;
    long var42;
    long var45;
    long var5;
    long var51;
    long var52;
    long var8;
    var5 = (long)arg2;
    local_20 = (long)(0x28);
    var8 = 0;
    *(int *)(&local_a8[0]) = 0;
    *(int *)((&local_a8[0] + 4)) = 0;
    *(int *)((&local_a8[0] + 8)) = 0;
    *(int *)((&local_a8[0] + 12)) = 0;
    *(int *)((&local_a8[0] + 16)) = 0;
    *(int *)((&local_a8[0] + 20)) = 0;
    *(int *)((&local_a8[0] + 24)) = 0;
    *(int *)((&local_a8[0] + 28)) = 0;
    *(int *)((&local_a8[0] + 32)) = 0;
    *(int *)((&local_a8[0] + 36)) = 0;
    *(int *)((&local_a8[0] + 40)) = 0;
    *(int *)((&local_a8[0] + 44)) = 0;
    *(int *)((&local_a8[0] + 48)) = 0;
    *(int *)((&local_a8[0] + 52)) = 0;
    *(int *)((&local_a8[0] + 56)) = 0;
    *(int *)((&local_a8[0] + 60)) = 0;
    if ((arg0 == 0)) {
        goto L_124d;
    }
    if ((var5 == 0)) {
        goto L_124d;
    }
    ret = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(4) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        goto L_124d;
    }
    if (((unsigned long)((unsigned int)(arg1)) == 0)) {
        goto L_122e;
    }
    var10 = (long)arg0;
    var11 = (long)arg0;
    var14 = ((long)(arg1) << 2);
    from = 0;
    do {
        var19 = 0;
        do {
            if (((unsigned long)((unsigned int)(*(int *)((var11 + var19 * 4)))) != 0)) {
                *(int *)((&local_a8[0] + (var19 * 4))) = (*(int *)((&local_a8[0] + (var19 * 4))) + 1);
            }
            var8 = (var19 + 1);
            var19 = var8;
        } while (((((unsigned int)(ret) == (unsigned int)(var8)) | ((long)((int)(ret)) < (long)((int)(var8)))) == 0));
        var21 = (from + 1);
        from = (unsigned long)((unsigned int)(var21));
        var11 = (var11 + var14);
    } while (((unsigned int)(ret) != (unsigned int)(var21)));
    var26 = 0;
    var27 = 0;
    do {
        tail = var26;
        if (((unsigned long)((unsigned int)(*(int *)((&local_a8[0] + (var27 * 4))))) == 0)) {
            *(int *)((&local_68[0] + ((long)((int)(var26)) * 4))) = var27;
            tail = (unsigned long)((unsigned int)((var26 + 1)));
        }
        var33 = (var27 + 1);
        var26 = (unsigned long)((unsigned int)(tail));
        var27 = var33;
    } while (((((unsigned int)(from) == (unsigned int)(var33)) | ((long)(from) < (long)((int)(var33)))) == 0));
    if (((unsigned long)((unsigned int)(tail)) == 0)) {
        goto L_124d;
    }
    var35 = 0;
    do {
        var37 = (unsigned long)((unsigned int)(*(int *)((&local_68[0] + (var35 * 4)))));
        count = (unsigned long)((unsigned int)((var35 + 1)));
        *(int *)((var5 + var35 * 4)) = var37;
        var42 = (var10 + ((long)((int)((var37 * from))) * 4));
        var45 = (unsigned long)((unsigned int)(tail));
        to = 0;
        do {
            tail = var45;
            if (((unsigned long)((unsigned int)(*(int *)((var42 + to * 4)))) != 0)) {
                t155 = (*(int *)((&local_a8[0] + (to * 4))) - 1);
                *(int *)((&local_a8[0] + (to * 4))) = t155;
                tail = var45;
                if (((unsigned long)((unsigned int)(t155)) == 0)) {
                    *(int *)((&local_68[0] + ((long)((int)(var45)) * 4))) = to;
                    tail = (unsigned long)((unsigned int)((var45 + 1)));
                }
            }
            var51 = ((unsigned long)((unsigned int)(to)) + 1);
            var45 = (unsigned long)((unsigned int)(tail));
            to = var51;
        } while (((((unsigned int)(from) == (unsigned int)(var51)) | ((long)(from) < (long)((int)(var51)))) == 0));
        var52 = (var35 + 1);
        var35 = var52;
    } while (((((unsigned int)(tail) == (unsigned int)(var52)) | ((long)(tail) < (long)((int)(var52)))) == 0));
    if (((unsigned int)(count) != (unsigned int)(from))) {
        goto L_124d;
    }
    L_122e: ;
    if ((local_20 != 0x28)) {
        goto L_1254;
    }
    // x86-64 epilogue: tear down frame
    return ret;
    L_124d: ;
    ret = 0xffffffff;
    goto L_122e;
    L_1254: ;
    __stack_chk_fail();
}

← 213 fixtures