glaurung

Fixture 19

disjoint set

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

static int32_t find_root(const int32_t *parent, int32_t n, int32_t x) {
    int32_t steps;
    if (x < 0 || x >= n) {
        return -1;
    }
    for (steps = 0; steps < n; ++steps) {
        int32_t next = parent[x];
        if (next == x) {
            return x;
        }
        if (next < 0 || next >= n) {
            return -1;
        }
        x = next;
    }
    return -1;
}

__attribute__((noinline)) int32_t dsu_find(int32_t *parent, int32_t n,
                                           int32_t x) {
    int32_t root;
    int32_t steps;
    if (parent == 0 || n <= 0 || n > 16) {
        return -1;
    }
    root = find_root(parent, n, x);
    if (root < 0) {
        return -1;
    }
    for (steps = 0; steps < n && x != root; ++steps) {
        int32_t next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

__attribute__((noinline)) int32_t dsu_union(int32_t *parent, int32_t *rank,
                                            int32_t n, int32_t a, int32_t b) {
    int32_t ra;
    int32_t rb;
    if (parent == 0 || rank == 0 || n <= 0 || n > 16) {
        return -1;
    }
    ra = find_root(parent, n, a);
    rb = find_root(parent, n, b);
    if (ra < 0 || rb < 0) {
        return -1;
    }
    if (ra == rb) {
        return ra;
    }
    if (rank[ra] < rank[rb]) {
        parent[ra] = rb;
        return rb;
    }
    parent[rb] = ra;
    if (rank[ra] == rank[rb] && rank[ra] < INT32_MAX) {
        ++rank[ra];
    }
    return ra;
}

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
dsu_find pass 46 lines 
// glaurung: dsu_find @ 0x1100
int32_t dsu_find(int32_t * arg0, int32_t arg1, int32_t arg2) {
    extern int find_root(int *, int, int);
    int root;
    int steps;
    int next;
    int local_18;
    signed char local_25;
    int local_4;
    int var0;
    local_18 = arg2;
    if ((arg0 != 0)) {
        if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
            if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                goto L_113d;
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_113d: ;
    var0 = find_root((int *)(arg0), (unsigned long)((unsigned int)(arg1)), (unsigned long)((unsigned int)(local_18)));
    root = var0;
    if (((long)(root) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    steps = 0;
    L_116c: ;
    local_25 = 0;
    if ((steps < arg1)) {
        local_25 = ((unsigned int)(local_18) != (unsigned int)(root));
    }
    if (((unsigned long)((unsigned char)((local_25 & 1))) != 0)) {
        next = arg0[(long)(local_18)];
        arg0[(long)(local_18)] = root;
        local_18 = next;
        steps = ((unsigned int)(steps) + 1);
        goto L_116c;
    }
    local_4 = root;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
dsu_union pass 60 lines 
// glaurung: dsu_union @ 0x1290
int32_t dsu_union(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4) {
    extern int find_root(int *, int, int);
    int ra;
    int rb;
    int local_4;
    int var0;
    int var2;
    // x86-64 prologue: save rbp, frame 48 bytes
    if ((arg0 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if ((arg1 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if ((((unsigned long)((unsigned int)(arg2)) == 0) | ((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);
    }
    var0 = find_root((int *)(arg0), (unsigned long)((unsigned int)(arg2)), (unsigned long)((unsigned int)(arg3)));
    ra = var0;
    var2 = find_root((int *)(arg0), (unsigned long)((unsigned int)(arg2)), (unsigned long)((unsigned int)(arg4)));
    rb = var2;
    if (((long)(ra) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((long)(rb) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((unsigned int)(ra) != (unsigned int)(rb))) {
        if (((long)((int)(arg1[(long)(rb)])) <= (long)((int)(arg1[(long)(ra)])))) {
            arg0[(long)(rb)] = ra;
            if (((unsigned int)(arg1[(long)(ra)]) == (unsigned int)(arg1[(long)(rb)]))) {
                if (((long)((int)(arg1[(long)(ra)])) < 0x7fffffff)) {
                    arg1[(long)(ra)] = ((unsigned long)((unsigned int)(arg1[(long)(ra)])) + 1);
                }
            }
            return (unsigned int)(ra);
        } else {
            arg0[(long)(ra)] = rb;
            return (unsigned int)(rb);
        }
    } else {
        return (unsigned int)(ra);
    }
}

clang -O2

2/2
dsu_find pass 66 lines 
// glaurung: dsu_find @ 0x1100
int32_t dsu_find(int32_t * arg0, int32_t arg1, int32_t arg2) {
    int next;
    int steps;
    long of_9;
    long ret;
    long t179;
    long var10;
    long var2;
    long var3;
    long var9;
    ret = 0xffffffff;
    if ((arg0 == 0)) {
        return ret;
    }
    if (((unsigned long)((unsigned long)((unsigned int)((arg1 - 17)))) < (unsigned long)(0xfffffff0))) {
        return ret;
    }
    if (((long)(arg2) < 0)) {
        return ret;
    }
    if ((arg1 <= arg2)) {
        return ret;
    }
    var2 = (unsigned long)((unsigned int)(arg2));
    var3 = 1;
    while (1) {
        next = (unsigned long)((unsigned int)(arg0[(unsigned long)((unsigned int)(var2))]));
        if (((unsigned int)(next) == (unsigned int)(var2))) {
            break;
        }
        if (((long)(next) < 0)) {
            return ret;
        }
        if ((arg1 <= next)) {
            return ret;
        }
        var2 = (unsigned long)((unsigned int)(next));
        t179 = (var3 - (unsigned long)((unsigned int)(arg1)));
        of_9 = (((long)((int)(var3)) < (long)(arg1)) ^ ((long)((int)(t179)) < 0));
        var3 = (unsigned long)((unsigned int)((var3 + 1)));
        if (((((long)((int)(t179)) < 0) ^ of_9) == 0)) {
            return ret;
        }
    }
    if ((((unsigned long)((unsigned int)(arg1)) != 0) && (0 <= (long)(arg1)))) {
        if (((unsigned int)(var2) == (unsigned int)(arg2))) {
            return (unsigned int)(var2);
        }
        steps = 1;
        var9 = (unsigned long)((unsigned int)(arg2));
        while (1) {
            var10 = (long)((int)(var9));
            var9 = (unsigned long)((unsigned int)(arg0[(long)((int)(var9))]));
            *(int *)(((long)arg0 + var10 * 4)) = var2;
            if ((arg1 <= steps)) {
                break;
            }
            steps = (unsigned long)((unsigned int)((steps + 1)));
            if (((unsigned int)(var9) == (unsigned int)(var2))) {
                break;
            }
        }
    }
    return (unsigned int)(var2);
}
dsu_union pass 106 lines 
// glaurung: dsu_union @ 0x1190
int32_t dsu_union(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4) {
    int ra;
    int steps;
    int next;
    int rb;
    long of_10;
    long of_19;
    long ret;
    long t207;
    long t211;
    long var12;
    long var14;
    long var15;
    long var18;
    long var20;
    long var7;
    ret = 0xffffffff;
    if ((arg0 == 0)) {
        goto L_1243;
    }
    if ((arg1 == 0)) {
        goto L_1243;
    }
    if (((unsigned long)((unsigned long)((unsigned int)((arg2 - 17)))) < (unsigned long)(0xfffffff0))) {
        goto L_1243;
    }
    ret = 0xffffffff;
    ra = 0xffffffff;
    if (((long)(arg3) < 0)) {
        goto L_1207;
    }
    ra = 0xffffffff;
    if ((arg2 <= arg3)) {
        goto L_1207;
    }
    steps = 1;
    next = arg3;
    L_11e0: ;
    var7 = (unsigned long)((unsigned int)(next));
    next = (unsigned long)((unsigned int)(arg0[(unsigned long)((unsigned int)(next))]));
    ra = var7;
    if (((unsigned int)(next) == (unsigned int)(var7))) {
        goto L_1207;
    }
    if ((0 <= (long)(next))) {
        if ((next < arg2)) {
            t207 = ((unsigned long)((unsigned int)(steps)) - (unsigned long)((unsigned int)(arg2)));
            of_10 = ((steps < arg2) ^ ((long)((int)(t207)) < 0));
            steps = (unsigned long)((unsigned int)((steps + 1)));
            if ((((long)((int)(t207)) < 0) ^ of_10)) {
                goto L_11e0;
            }
        }
    }
    ra = 0xffffffff;
    L_1207: ;
    if (((long)(arg4) < 0)) {
        goto L_1243;
    }
    if ((arg2 <= arg4)) {
        goto L_1243;
    }
    var12 = 1;
    rb = arg4;
    do {
        var14 = (unsigned long)((unsigned int)(rb));
        var15 = (unsigned long)((unsigned int)(arg0[(unsigned long)((unsigned int)(rb))]));
        if (((unsigned int)(var15) == (unsigned int)(rb))) {
            goto L_1244;
        }
        if (((long)((int)(var15)) < 0)) {
            goto L_1243;
        }
        if (((long)(arg2) <= (long)((int)(var15)))) {
            goto L_1243;
        }
        t211 = (var12 - (unsigned long)((unsigned int)(arg2)));
        of_19 = (((long)((int)(var12)) < (long)(arg2)) ^ ((long)((int)(t211)) < 0));
        var12 = (unsigned long)((unsigned int)((var12 + 1)));
        rb = (unsigned long)((unsigned int)(var15));
    } while ((((long)((int)(t211)) < 0) ^ of_19));
    L_1243: ;
    return ret;
    L_1244: ;
    if (((long)(ra) < 0)) {
        goto L_1243;
    }
    if (((unsigned int)(ra) != (unsigned int)(rb))) {
        var18 = (unsigned long)((unsigned int)(ra));
        if (((long)((int)(arg1[(unsigned long)((unsigned int)(ra))])) < (long)((int)(*(int *)(((long)arg1 + var14 * 4)))))) {
            *(int *)(((long)arg0 + var18 * 4)) = rb;
            return (unsigned int)(rb);
        }
        *(int *)(((long)arg0 + var14 * 4)) = ra;
        var20 = (unsigned long)((unsigned int)(*(int *)(((long)arg1 + var18 * 4))));
        if (((unsigned long)((unsigned int)(var20)) == 0x7fffffff)) {
            return (unsigned int)(ra);
        }
        if (((unsigned int)(var20) != (unsigned int)(*(int *)(((long)arg1 + var14 * 4))))) {
            return (unsigned int)(ra);
        }
        *(int *)(((long)arg1 + var18 * 4)) = (var20 + 1);
    }
    return (unsigned int)(ra);
}

gcc -O0

2/2
dsu_find pass 40 lines 
// glaurung: dsu_find @ 0x117d
int32_t dsu_find(int32_t * arg0, int32_t arg1, int32_t arg2) {
    extern int find_root(int *, int, int);
    int root;
    int steps;
    int next;
    int local_20;
    int var2;
    // x86-64 prologue: save rbp, frame 32 bytes
    local_20 = arg2;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if ((((unsigned long)((unsigned int)(arg1)) == 0) | ((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;
    }
    var2 = find_root((int *)(arg0), (unsigned long)((unsigned int)(arg1)), (unsigned long)((unsigned int)(local_20)));
    root = var2;
    if ((0 <= (long)(root))) {
        steps = 0;
        while ((steps < arg1)) {
            if (((unsigned int)(local_20) == (unsigned int)(root))) {
                break;
            }
            next = arg0[(long)(local_20)];
            arg0[(long)(local_20)] = root;
            local_20 = next;
            steps = (steps + 1);
        }
        return (unsigned int)(root);
    } else {
        return 0xffffffff;
    }
}
dsu_union pass 55 lines 
// glaurung: dsu_union @ 0x122b
int32_t dsu_union(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4) {
    extern int find_root(int *, int, int);
    int ra;
    int rb;
    int var2;
    long var49;
    int var6;
    // x86-64 prologue: save rbp, frame 48 bytes
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if ((arg1 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if ((((unsigned long)((unsigned int)(arg2)) == 0) | ((long)(arg2) < 0))) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((((unsigned long)((unsigned int)(arg2)) == 16) | ((long)(arg2) < 16)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    var2 = find_root((int *)(arg0), (unsigned long)((unsigned int)(arg2)), (unsigned long)((unsigned int)(arg3)));
    ra = var2;
    var6 = find_root((int *)(arg0), (unsigned long)((unsigned int)(arg2)), (unsigned long)((unsigned int)(arg4)));
    rb = var6;
    if (((long)(ra) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((long)(rb) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((unsigned int)(ra) != (unsigned int)(rb))) {
        if (((long)((int)(arg1[(long)(rb)])) <= (long)((int)(arg1[(long)(ra)])))) {
            arg0[(long)(rb)] = ra;
            if (((unsigned int)(arg1[(long)(ra)]) == (unsigned int)(arg1[(long)(rb)]))) {
                if (((unsigned long)((unsigned int)(arg1[(long)(ra)])) != 0x7fffffff)) {
                    var49 = (long)(((long)arg1 + ((long)(ra) * 4)));
                    *(int *)((var49)) = ((unsigned long)((unsigned int)(*(int *)((var49)))) + 1);
                }
            }
            return (unsigned int)(ra);
        } else {
            arg0[(long)(ra)] = rb;
            return (unsigned int)(rb);
        }
    } else {
        return (unsigned int)(ra);
    }
}

gcc -O2

2/2
dsu_find pass 61 lines 
// glaurung: dsu_find @ 0x1100
int32_t dsu_find(int32_t * arg0, int32_t arg1, int32_t arg2) {
    int steps;
    int next;
    long ret;
    int var14;
    long var15;
    long var4;
    long var5;
    int var7;
    if (((unsigned long)(15) < (unsigned long)((unsigned long)((unsigned int)((arg1 - 1)))))) {
        return 0xffffffff;
    }
    if ((arg0 == 0)) {
        return 0xffffffff;
    }
    if (((long)(arg2) < 0)) {
        return 0xffffffff;
    }
    if ((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2))) {
        return 0xffffffff;
    }
    var4 = 0;
    var5 = (unsigned long)((unsigned int)(arg2));
    while (1) {
        ret = (long)((int)(var5));
        var5 = (unsigned long)((unsigned int)(arg0[(long)((int)(var5))]));
        if (((unsigned int)(var5) == (unsigned int)(ret))) {
            break;
        }
        if (((long)((int)(var5)) < 0)) {
            return 0xffffffff;
        }
        if ((((unsigned int)(arg1) == (unsigned int)(var5)) | ((long)(arg1) < (long)((int)(var5))))) {
            return 0xffffffff;
        }
        var7 = (var4 + 1);
        var4 = (unsigned long)((unsigned int)(var7));
        if (((((unsigned int)(arg1) == (unsigned int)(var7)) | (arg1 < var7)) != 0)) {
            return 0xffffffff;
        }
    }
    if (((unsigned int)(arg2) != (unsigned int)(ret))) {
        steps = 0;
        next = arg2;
        while (1) {
            var14 = (steps + 1);
            steps = (unsigned long)((unsigned int)(var14));
            var15 = (long)(((long)arg0 + ((long)(next) * 4)));
            next = (unsigned long)((unsigned int)(*(int *)((var15))));
            *(int *)((var15)) = ret;
            if (((((unsigned int)(arg1) == (unsigned int)(var14)) | (arg1 < var14)) != 0)) {
                break;
            }
            if (((unsigned int)(next) == (unsigned int)(ret))) {
                return ret;
            }
        }
    }
    return ret;
}
dsu_union pass 112 lines 
// glaurung: dsu_union @ 0x1170
int32_t dsu_union(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4) {
    int next;
    int steps;
    int ra;
    int rb;
    long var0;
    long var1;
    int var11;
    long var15;
    long var16;
    long var19;
    long var20;
    int var22;
    long var24;
    long var25;
    long var26;
    long var28;
    long var3;
    long var9;
    var0 = (long)arg1;
    var1 = (unsigned long)((unsigned int)(arg2));
    if ((arg0 == 0)) {
        goto L_11f7;
    }
    if ((arg1 == 0)) {
        goto L_11f7;
    }
    if (((unsigned long)(15) < (unsigned long)((unsigned long)((unsigned int)((arg2 - 1)))))) {
        goto L_11f7;
    }
    var3 = (unsigned long)((unsigned int)(arg3));
    if (((0 <= (long)(arg3)) && ((((unsigned int)(var1) == (unsigned int)(arg3)) | ((long)((int)(var1)) < (long)(arg3))) == 0))) {
        next = arg3;
        steps = 0;
        do {
            var9 = (long)(next);
            next = (unsigned long)((unsigned int)(arg0[(long)(next)]));
            ra = var9;
            if (((unsigned int)(next) == (unsigned int)(var9))) {
                goto L_11bb;
            }
            var3 = (unsigned long)((unsigned int)(next));
            if (((long)(next) < 0)) {
                break;
            }
            var3 = (unsigned long)((unsigned int)(next));
            if ((((unsigned int)(var1) == (unsigned int)(next)) | ((long)((int)(var1)) < (long)(next)))) {
                break;
            }
            var11 = (steps + 1);
            steps = (unsigned long)((unsigned int)(var11));
            var3 = (unsigned long)((unsigned int)(next));
        } while (((unsigned int)(var1) != (unsigned int)(var11)));
    }
    ra = 0xffffffff;
    next = var3;
    L_11bb: ;
    if (((long)(arg4) < 0)) {
        goto L_11f7;
    }
    if ((((unsigned int)(var1) == (unsigned int)(arg4)) | ((long)((int)(var1)) < (long)(arg4)))) {
        goto L_11f7;
    }
    var15 = (unsigned long)((unsigned int)(arg4));
    var16 = 0;
    do {
        var19 = ((long)((int)(var15)) << 2);
        var20 = (long)(((long)arg0 + var19));
        rb = (unsigned long)((unsigned int)(*(int *)((var20))));
        if (((unsigned int)(rb) == (unsigned int)(var15))) {
            goto L_1208;
        }
        if (((long)(rb) < 0)) {
            goto L_11f7;
        }
        if ((((unsigned int)(var1) == (unsigned int)(rb)) | ((long)((int)(var1)) < (long)(rb)))) {
            goto L_11f7;
        }
        var22 = (var16 + 1);
        var16 = (unsigned long)((unsigned int)(var22));
        var15 = (unsigned long)((unsigned int)(rb));
    } while (((unsigned int)(var1) != (unsigned int)(var22)));
    L_11f7: ;
    ra = 0xffffffff;
    L_11fd: ;
    return (unsigned int)(ra);
    L_1208: ;
    if (((unsigned long)((unsigned int)(ra)) == 0xffffffff)) {
        goto L_11fd;
    }
    if (((unsigned int)(ra) == (unsigned int)(rb))) {
        goto L_11fd;
    }
    var24 = (long)(ra);
    var25 = (var0 + ((long)(ra) * 4));
    var26 = (var0 + var19);
    if (((long)((int)(*(int *)((var26)))) <= (long)((int)(*(int *)((var25)))))) {
        *(int *)((var20)) = ra;
        var28 = (unsigned long)((unsigned int)(*(int *)((var25))));
        if (((unsigned int)(*(int *)((var26))) != (unsigned int)(var28))) {
            goto L_11fd;
        }
        if (((unsigned long)((unsigned int)(var28)) == 0x7fffffff)) {
            goto L_11fd;
        }
        *(int *)((var25)) = (var28 + 1);
        return (unsigned int)(ra);
    }
    *(int *)(((long)arg0 + var24 * 4)) = rb;
    return (unsigned int)(rb);
}

← 213 fixtures