glaurung

Fixture 15

binary search tree

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

typedef struct {
    int32_t key;
    int32_t left;
    int32_t right;
} BstNode;

__attribute__((noinline)) int32_t
bst_search(const BstNode *nodes, int32_t n, int32_t root, int32_t key) {
    int32_t current = root;
    int32_t steps;

    if (nodes == 0 || n <= 0 || n > 16) {
        return -1;
    }
    for (steps = 0; steps < n; ++steps) {
        if (current < 0 || current >= n) {
            return -1;
        }
        if (nodes[current].key == key) {
            return current;
        }
        current = key < nodes[current].key ? nodes[current].left
                                           : nodes[current].right;
    }
    return -1;
}

__attribute__((noinline)) uint32_t
bst_inorder_checksum(const BstNode *nodes, int32_t n, int32_t root) {
    int32_t stack[16];
    int32_t current = root;
    int32_t top = 0;
    int32_t visited = 0;
    uint32_t checksum = 0;

    if (nodes == 0 || n <= 0 || n > 16) {
        return 0;
    }
    while (visited < n && (top > 0 || (current >= 0 && current < n))) {
        while (current >= 0 && current < n && top < n) {
            stack[top++] = current;
            current = nodes[current].left;
        }
        if (top == 0) {
            break;
        }
        current = stack[--top];
        checksum = checksum * 33u + (uint32_t)nodes[current].key;
        ++visited;
        current = nodes[current].right;
    }
    return checksum;
}

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
bst_inorder_checksum pass 90 lines 
// glaurung: bst_inorder_checksum @ 0x1210
typedef struct anon_11c BstNode;
#ifndef GLAURUNG_STRUCT_anon_11c_DEFINED
#define GLAURUNG_STRUCT_anon_11c_DEFINED
typedef struct anon_11c anon_11c;
struct anon_11c {
    int32_t key;
    int32_t left;
    int32_t right;
};
#endif
__attribute__((no_stack_protector)) uint32_t bst_inorder_checksum(const BstNode * arg0, int32_t arg1, int32_t arg2) {
    int current;
    int top;
    int visited;
    unsigned int checksum;
    int local_4;
    unsigned char local_60[64];
    signed char local_71;
    signed char local_72;
    signed char local_73;
    signed char local_74;
    long var16;
    long var28;
    int var38;
    current = arg2;
    top = 0;
    visited = 0;
    checksum = 0;
    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_1264;
            }
        }
    }
    local_4 = 0;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1264: ;
    goto L_1269;
    L_1269: ;
    local_71 = 0;
    if ((visited < arg1)) {
        local_72 = 1;
        if (((((unsigned long)((unsigned int)(top)) == 0) | ((long)(top) < 0)) != 0)) {
            local_73 = 0;
            if ((0 <= (long)(current))) {
                local_73 = (current < arg1);
            }
            local_72 = local_73;
        }
        local_71 = local_72;
    }
    var16 = ((unsigned long)((unsigned char)(local_71)) & 255);
    if (((unsigned long)((unsigned char)((var16 & 1))) == 0)) {
        goto L_138b;
    }
    goto L_12c5;
    L_12c5: ;
    local_74 = 0;
    if ((0 <= (long)(current))) {
        local_74 = 0;
        if ((current < arg1)) {
            local_74 = (top < arg1);
        }
    }
    if (((unsigned long)((unsigned char)((local_74 & 1))) != 0)) {
        var28 = (unsigned long)((unsigned int)(top));
        top = ((unsigned int)(top) + 1);
        *(int *)((&local_60[0] + ((long)((int)(var28)) * 4))) = current;
        var16 = (unsigned long)((unsigned int)(arg0[(int)(current)].left));
        current = var16;
        goto L_12c5;
    }
    if (((unsigned long)((unsigned int)(top)) == 0)) {
        goto L_138b;
    }
    var38 = ((unsigned int)(top) - 1);
    top = var38;
    current = *(int *)((&local_60[0] + ((long)((int)(var38)) * 4)));
    checksum = ((checksum * 33) + arg0[(int)(current)].key);
    visited = ((unsigned int)(visited) + 1);
    current = arg0[(int)(current)].right;
    goto L_1269;
    L_138b: ;
    local_4 = checksum;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
bst_search pass 61 lines 
// glaurung: bst_search @ 0x1100
typedef struct anon_11c BstNode;
#ifndef GLAURUNG_STRUCT_anon_11c_DEFINED
#define GLAURUNG_STRUCT_anon_11c_DEFINED
typedef struct anon_11c anon_11c;
struct anon_11c {
    int32_t key;
    int32_t left;
    int32_t right;
};
#endif
int32_t bst_search(const BstNode * arg0, int32_t arg1, int32_t arg2, int32_t arg3) {
    int current;
    int steps;
    int local_28;
    int local_4;
    current = 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_1142;
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1142: ;
    steps = 0;
    L_1149: ;
    if ((arg1 <= steps)) {
        goto L_11f9;
    }
    if ((0 <= (long)(current))) {
        if ((current < arg1)) {
            goto L_1177;
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1177: ;
    if (((unsigned int)(arg0[(int)(current)].key) == (unsigned int)(arg3))) {
        local_4 = current;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((long)(arg3) < (long)((int)(arg0[(int)(current)].key)))) {
        local_28 = arg0[(int)(current)].left;
        goto L_11e5;
    }
    local_28 = arg0[(int)(current)].right;
    L_11e5: ;
    current = local_28;
    steps = ((unsigned int)(steps) + 1);
    goto L_1149;
    L_11f9: ;
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

2/2
bst_inorder_checksum pass 94 lines 
// glaurung: bst_inorder_checksum @ 0x1150
typedef struct anon_107 BstNode;
#ifndef GLAURUNG_STRUCT_anon_107_DEFINED
#define GLAURUNG_STRUCT_anon_107_DEFINED
typedef struct anon_107 anon_107;
struct anon_107 {
    int32_t key;
    int32_t left;
    int32_t right;
};
#endif
__attribute__((no_stack_protector)) uint32_t bst_inorder_checksum(const BstNode * arg0, int32_t arg1, int32_t arg2) {
    unsigned int checksum;
    int visited;
    int current;
    int top;
    unsigned char local_4c[76];
    long of_20;
    long ret;
    long sf_20;
    long var14;
    long var17;
    int var18;
    long var2;
    long var21;
    long var27;
    int var28;
    long var3;
    int var30;
    long var9;
    var2 = 0;
    ret = 0;
    if (((unsigned long)((unsigned long)((unsigned int)((arg1 - 1)))) <= (unsigned long)(15))) {
        ret = var2;
        if ((arg0 == 0)) {
            return ret;
        }
        var3 = (unsigned long)((unsigned int)(arg1));
        checksum = 0;
        var9 = 0;
        visited = 0;
        current = arg2;
        do {
            if (((((unsigned long)((unsigned int)(var9)) == 0) | ((long)((int)(var9)) < 0)) != 0)) {
                if (((long)(current) < 0)) {
                    return checksum;
                }
                if ((arg1 <= current)) {
                    return checksum;
                }
            }
            if ((0 <= (long)(current))) {
                if ((current < arg1)) {
                    if (((long)((int)(var9)) < (long)(arg1))) {
                        top = ((long)((int)(var9)) + 1);
                        var14 = var9;
                        do {
                            *(int *)((&local_4c[0] + (top * 4))) = current;
                            var17 = (unsigned long)((unsigned int)(arg0[(unsigned int)(current)].left));
                            var18 = (var14 + 1);
                            var14 = (unsigned long)((unsigned int)(var18));
                            var9 = (unsigned long)((unsigned int)(var18));
                            if (((long)((int)(var17)) < 0)) {
                                break;
                            }
                            var9 = var14;
                            if (((long)(arg1) <= (long)((int)(var17)))) {
                                break;
                            }
                            sf_20 = ((top - var3) < 0);
                            of_20 = ((top < var3) ^ ((top - var3) < 0));
                            top = (top + 1);
                            current = var17;
                            var9 = var14;
                        } while ((sf_20 ^ of_20));
                    }
                }
            }
            if (((unsigned long)((unsigned int)(var9)) == 0)) {
                return checksum;
            }
            var21 = (long)((int)(*(int *)((&local_4c[0] + ((long)((int)(var9)) * 4)))));
            var27 = (var21 + (var21 * 2));
            var28 = ((unsigned int)(((unsigned long)((unsigned int)((checksum << 5))) + checksum)) + arg0[var21].key);
            ret = (unsigned long)((unsigned int)(var28));
            var9 = (unsigned long)((unsigned int)((var9 - 1)));
            var30 = (visited + 1);
            visited = (unsigned long)((unsigned int)(var30));
            checksum = (unsigned long)((unsigned int)(var28));
            current = (unsigned long)((unsigned int)(arg0[var21].right));
        } while (((unsigned int)(var30) != (unsigned int)(arg1)));
    }
    return ret;
}
bst_search pass 46 lines 
// glaurung: bst_search @ 0x1100
typedef struct anon_107 BstNode;
#ifndef GLAURUNG_STRUCT_anon_107_DEFINED
#define GLAURUNG_STRUCT_anon_107_DEFINED
typedef struct anon_107 anon_107;
struct anon_107 {
    int32_t key;
    int32_t left;
    int32_t right;
};
#endif
int32_t bst_search(const BstNode * arg0, int32_t arg1, int32_t arg2, int32_t arg3) {
    int current;
    int steps;
    long ret;
    long t10;
    int var11;
    long var2;
    long var5;
    if (((unsigned long)(15) < (unsigned long)((unsigned long)((unsigned int)((arg1 - 1)))))) {
        return 0xffffffff;
    }
    if ((arg0 == 0)) {
        return 0xffffffff;
    }
    var2 = (unsigned long)((unsigned int)(arg1));
    current = (unsigned long)((unsigned int)(arg2));
    while ((0 <= (long)(current))) {
        if ((arg1 <= current)) {
            break;
        }
        var5 = ((unsigned long)((unsigned int)(current)) + ((unsigned long)((unsigned int)(current)) * 2));
        t10 = arg0[(unsigned int)(current)].key;
        ret = (unsigned long)((unsigned int)(current));
        if (((unsigned int)(t10) == (unsigned int)(arg3))) {
            return ret;
        }
        var11 = (var2 - 1);
        var2 = (unsigned long)((unsigned int)(var11));
        current = (unsigned long)((unsigned int)(*(int *)(((((long)arg0 + (var5 * 4)) + ((unsigned int)((unsigned char)(((((unsigned int)(t10) == (unsigned int)(arg3)) | ((long)((int)(t10)) < (long)(arg3))) & 255))) * 4)) + 4))));
        if (((unsigned long)((unsigned int)(var11)) == 0)) {
            break;
        }
    }
    return 0xffffffff;
}

gcc -O0

2/2
bst_inorder_checksum pass 82 lines 
// glaurung: bst_inorder_checksum @ 0x121e
typedef struct anon_9d BstNode;
#ifndef GLAURUNG_STRUCT_anon_9d_DEFINED
#define GLAURUNG_STRUCT_anon_9d_DEFINED
typedef struct anon_9d anon_9d;
struct anon_9d {
    int32_t key;
    int32_t left;
    int32_t right;
};
#endif
uint32_t bst_inorder_checksum(const BstNode * arg0, int32_t arg1, int32_t arg2) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int current;
    int top;
    int visited;
    unsigned int checksum;
    unsigned char local_50[64];
    long local_8;
    long ret;
    long var4;
    local_8 = (long)(0x28);
    current = arg2;
    top = 0;
    visited = 0;
    checksum = 0;
    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_133a;
            }
        }
    }
    ret = 0;
    goto L_1364;
    L_127f: ;
    var4 = (unsigned long)((unsigned int)(top));
    top = ((unsigned int)(top) + 1);
    *(int *)((&local_50[0] + ((long)((int)(var4)) * 4))) = current;
    current = *(int *)((((long)arg0 + ((((long)(current) + (long)(current)) + (long)(current)) << 2)) + 4));
    L_12b4: ;
    if ((0 <= (long)(current))) {
        if ((current < arg1)) {
            if ((top < arg1)) {
                goto L_127f;
            }
        }
    }
    if (((unsigned long)((unsigned int)(top)) == 0)) {
        goto L_1360;
    }
    top = (top - 1);
    current = *(int *)((&local_50[0] + ((long)(top) * 4)));
    checksum = ((unsigned int)(*(int *)(((long)arg0 + ((((long)(current) + (long)(current)) + (long)(current)) << 2)))) + (unsigned int)(((unsigned long)((unsigned int)((checksum << 5))) + checksum)));
    visited = (visited + 1);
    current = *(int *)((((long)arg0 + ((((long)(current) + (long)(current)) + (long)(current)) << 2)) + 8));
    L_133a: ;
    if ((arg1 <= visited)) {
        goto L_1361;
    }
    if (((((unsigned long)((unsigned int)(top)) == 0) | ((long)(top) < 0)) == 0)) {
        goto L_12b4;
    }
    if (((long)(current) < 0)) {
        goto L_1361;
    }
    if ((current < arg1)) {
        goto L_12b4;
    }
    goto L_1361;
    L_1360: ;
    L_1361: ;
    ret = (unsigned long)(checksum);
    L_1364: ;
    if ((local_8 == 0x28)) {
        // x86-64 epilogue: restore rbp
        return ret;
    }
    __stack_chk_fail();
    // x86-64 epilogue: restore rbp
    return ret;
}
bst_search pass 56 lines 
// glaurung: bst_search @ 0x1119
typedef struct anon_9d BstNode;
#ifndef GLAURUNG_STRUCT_anon_9d_DEFINED
#define GLAURUNG_STRUCT_anon_9d_DEFINED
typedef struct anon_9d anon_9d;
struct anon_9d {
    int32_t key;
    int32_t left;
    int32_t right;
};
#endif
int32_t bst_search(const BstNode * arg0, int32_t arg1, int32_t arg2, int32_t arg3) {
    int current;
    int steps;
    long var31;
    current = 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_1151;
            }
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_1151: ;
    steps = 0;
    goto L_120b;
    L_115d: ;
    if ((0 <= (long)(current))) {
        if ((current < arg1)) {
            goto L_1175;
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_1175: ;
    if (((unsigned int)(arg3) == (unsigned int)(*(int *)(((long)arg0 + ((((long)(current) + (long)(current)) + (long)(current)) << 2)))))) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(current);
    }
    if (((long)(arg3) < (long)((int)(*(int *)(((long)arg0 + ((((long)(current) + (long)(current)) + (long)(current)) << 2))))))) {
        var31 = (unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((((long)(current) + (long)(current)) + (long)(current)) << 2)) + 4))));
        goto L_1204;
    }
    var31 = (unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((((long)(current) + (long)(current)) + (long)(current)) << 2)) + 8))));
    L_1204: ;
    current = var31;
    steps = (steps + 1);
    L_120b: ;
    if ((steps < arg1)) {
        goto L_115d;
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
}

gcc -O2

2/2
bst_inorder_checksum pass 98 lines 
// glaurung: bst_inorder_checksum @ 0x1180
typedef struct anon_9d BstNode;
#ifndef GLAURUNG_STRUCT_anon_9d_DEFINED
#define GLAURUNG_STRUCT_anon_9d_DEFINED
typedef struct anon_9d anon_9d;
struct anon_9d {
    int32_t key;
    int32_t left;
    int32_t right;
};
#endif
uint32_t bst_inorder_checksum(const BstNode * arg0, int32_t arg1, int32_t arg2) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    unsigned int checksum;
    int top;
    int visited;
    int current;
    long local_10;
    unsigned char local_58[64];
    long var22;
    long var23;
    long var26;
    long var28;
    int var30;
    anon_9d * var4;
    long var42;
    long var44;
    long var5;
    local_10 = (long)(0x28);
    if (((unsigned long)(15) < (unsigned long)((unsigned long)((unsigned int)((arg1 - 1)))))) {
        goto L_1220;
    }
    var4 = (anon_9d *)arg0;
    if ((arg0 == 0)) {
        goto L_1220;
    }
    var5 = (unsigned long)((unsigned int)(arg1));
    checksum = 0;
    top = 0;
    visited = 0;
    current = arg2;
    L_11c0: ;
    var22 = (unsigned long)((unsigned int)((((((unsigned int)(var5) == (unsigned int)(current)) | ((long)((int)(var5)) < (long)(current))) == 0) & (unsigned long)((unsigned int)(((unsigned long)((unsigned int)((~(unsigned long)((unsigned int)(current))))) >> 31))))));
    if (((unsigned long)((unsigned int)(top)) == 0)) {
        goto L_1240;
    }
    if (((unsigned long)((unsigned char)((var22 & 255))) == 0)) {
        goto L_1246;
    }
    if ((((unsigned int)(var5) == (unsigned int)(top)) | ((long)((int)(var5)) < (long)(top)))) {
        goto L_1246;
    }
    L_11da: ;
    var23 = (long)(top);
    do {
        *(int *)((&local_58[0] + (var23 * 4))) = current;
        var26 = (unsigned long)((unsigned int)(var23));
        var28 = ((long)var4 + (((long)(current) + ((long)(current) * 2)) * 4));
        current = (unsigned long)((unsigned int)(var4[(int)(current)].left));
        if (((long)(current) < 0)) {
            goto L_1204;
        }
        if ((((unsigned int)(var5) == (unsigned int)(current)) | ((long)((int)(var5)) < (long)(current)))) {
            goto L_1204;
        }
        var23 = (var23 + 1);
    } while (((((unsigned int)(var5) == (unsigned int)(var23)) | ((long)((int)(var5)) < (long)((int)(var23)))) == 0));
    L_1204: ;
    var30 = (visited + 1);
    visited = (unsigned long)((unsigned int)(var30));
    current = (unsigned long)((unsigned int)(*(int *)((var28 + 0x8))));
    checksum = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)((checksum << 5))) + checksum))) + *(int *)((var28)))));
    top = var26;
    if (((((unsigned int)(var5) == (unsigned int)(var30)) | ((long)((int)(var5)) < (long)((int)(var30)))) == 0)) {
        goto L_11c0;
    }
    goto L_1223;
    L_1220: ;
    checksum = 0;
    L_1223: ;
    if ((local_10 != 0x28)) {
        goto L_125a;
    }
    return checksum;
    L_1240: ;
    if (((unsigned long)((unsigned char)((var22 & 255))) != 0)) {
        goto L_11da;
    }
    goto L_1223;
    L_1246: ;
    var42 = (unsigned long)((unsigned int)((top - 1)));
    var44 = (long)((int)(*(int *)((&local_58[0] + ((long)((int)(var42)) * 4)))));
    var28 = ((long)var4 + ((var44 + (var44 * 2)) * 4));
    var26 = var42;
    goto L_1204;
    L_125a: ;
    __stack_chk_fail();
}
bst_search pass 44 lines 
// glaurung: bst_search @ 0x1120
typedef struct anon_9d BstNode;
#ifndef GLAURUNG_STRUCT_anon_9d_DEFINED
#define GLAURUNG_STRUCT_anon_9d_DEFINED
typedef struct anon_9d anon_9d;
struct anon_9d {
    int32_t key;
    int32_t left;
    int32_t right;
};
#endif
int32_t bst_search(const BstNode * arg0, int32_t arg1, int32_t arg2, int32_t arg3) {
    int steps;
    int current;
    long t10;
    anon_9d * var1;
    int var11;
    long var8;
    var1 = (anon_9d *)arg0;
    if (((unsigned long)((unsigned long)((unsigned int)((arg1 - 1)))) <= (unsigned long)(15))) {
        if ((arg0 == 0)) {
            return 0xffffffff;
        }
        steps = 0;
        current = arg2;
        while ((0 <= (long)(current))) {
            if ((((unsigned int)(arg1) == (unsigned int)(current)) | (arg1 < current))) {
                break;
            }
            var8 = ((long)var1 + (((long)(current) + ((long)(current) * 2)) * 4));
            t10 = arg0[(int)(current)].key;
            if (((unsigned int)(t10) == (unsigned int)(arg3))) {
                return (unsigned int)(current);
            }
            var11 = (steps + 1);
            steps = (unsigned long)((unsigned int)(var11));
            current = (((((unsigned int)(t10) == (unsigned int)(arg3)) | ((long)((int)(t10)) < (long)(arg3))) == 0) ? arg0[(int)(current)].left : (unsigned long)((unsigned int)(arg0[(int)(current)].right)));
            if (((((unsigned int)(arg1) == (unsigned int)(var11)) | (arg1 < var11)) != 0)) {
                break;
            }
        }
    }
    return 0xffffffff;
}

← 213 fixtures