glaurung

Fixture 112

recursion shapes

C · 4 functions · 4 lanes · 13 of 16 function-lanes behave identically

3 of 4 lanes have a function that returns a different result after decompilation: clang-O0 (3/4), gcc-O0 (3/4), gcc-O2 (3/4).

Four recursion shapes that lower differently: mutual recursion (two frames that cannot be inlined into each other), self tail recursion (usually turned into a loop at -O2), non-tail recursion (a real frame), and an accumulator form that is tail-recursive by construction.

tests/decompiler_fixtures/src/112_recursion_shapes.c source 
#include <stdint.h>

/* Four recursion shapes that lower differently: mutual recursion (two frames
 * that cannot be inlined into each other), self tail recursion (usually turned
 * into a loop at -O2), non-tail recursion (a real frame), and an accumulator
 * form that is tail-recursive by construction. */

static int32_t is_odd_helper(int32_t value, int32_t fuel);

static int32_t is_even_helper(int32_t value, int32_t fuel) {
    if (fuel <= 0) {
        return -1;
    }
    if (value == 0) {
        return 1;
    }
    return is_odd_helper(value - 1, fuel - 1);
}

static int32_t is_odd_helper(int32_t value, int32_t fuel) {
    if (fuel <= 0) {
        return -1;
    }
    if (value == 0) {
        return 0;
    }
    return is_even_helper(value - 1, fuel - 1);
}

__attribute__((noinline)) int32_t mutual_parity(int32_t value) {
    if (value < 0 || value > 64) {
        return -1;
    }
    return is_even_helper(value, 128);
}

__attribute__((noinline)) int32_t tail_countdown(int32_t value, int32_t total) {
    if (value <= 0) {
        return total;
    }
    return tail_countdown(value - 1, total + value); /* self tail call */
}

__attribute__((noinline)) int32_t nontail_depth(int32_t value) {
    if (value <= 0) {
        return 0;
    }
    if (value > 32) {
        return -1;
    }
    /* The addition happens after the call returns: a real frame. */
    return 1 + nontail_depth(value - 1);
}

__attribute__((noinline)) int32_t
recursion_entry(int32_t selector, int32_t value) {
    if (value < 0 || value > 32) {
        return -1;
    }
    switch (selector & 3) {
    case 0:
        return mutual_parity(value);
    case 1:
        return tail_countdown(value, 0);
    default:
        return nontail_depth(value);
    }
}

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

3/4
mutual_parity pass 21 lines 
// glaurung: mutual_parity @ 0x1130
int32_t mutual_parity(int32_t arg0) {
    extern int is_even_helper(int, int);
    int local_4;
    int var0;
    // x86-64 prologue: save rbp, frame 16 bytes
    if (((long)(arg0) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg0)) == 64) | ((long)(arg0) < 64)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    var0 = is_even_helper((unsigned long)((unsigned int)(arg0)), 128);
    local_4 = var0;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
nontail_depth pass 15 lines 
// glaurung: nontail_depth @ 0x1220
int32_t nontail_depth(int32_t arg0) {
    int var2;
    // x86-64 prologue: save rbp, frame 16 bytes
    if (((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0)) == 0)) {
        if ((((unsigned long)((unsigned int)(arg0)) == 32) | ((long)(arg0) < 32))) {
            var2 = ((int (*)(int))nontail_depth)((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 1))));
            return (unsigned int)((var2 + 1));
        } else {
            return (unsigned int)(-1);
        }
    } else {
        return 0;
    }
}
recursion_entry pass 37 lines 
// glaurung: recursion_entry @ 0x1280
int32_t recursion_entry(int32_t arg0, int32_t arg1) {
    extern int mutual_parity(int);
    extern int nontail_depth(int);
    extern int tail_countdown(int, int);
    int local_10;
    int local_4;
    int var1;
    int var11;
    int var3;
    int var9;
    // x86-64 prologue: save rbp, frame 16 bytes
    if (((long)(arg1) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 32) | ((long)(arg1) < 32)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    var1 = ((unsigned int)(arg0) & 3);
    local_10 = var1;
    if (((unsigned long)((unsigned int)(var1)) == 0)) {
        var3 = mutual_parity((unsigned long)((unsigned int)(arg1)));
        return (unsigned int)(var3);
    } else {
        if (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(local_10)) - 1))) == 0)) {
            var9 = tail_countdown((unsigned long)((unsigned int)(arg1)), 0);
            return (unsigned int)(var9);
        } else {
            var11 = nontail_depth((unsigned long)((unsigned int)(arg1)));
            return (unsigned int)(var11);
        }
    }
}
tail_countdown fail 11 lines 
// glaurung: tail_countdown @ 0x11e0
int32_t tail_countdown(int32_t arg0, int32_t arg1) {
    int var4;
    // x86-64 prologue: save rbp, frame 16 bytes
    if (((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0)) == 0)) {
        var4 = ((int (*)(int, int))tail_countdown)((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 1))), (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) + arg0))));
        return (unsigned int)(var4);
    } else {
        return (unsigned int)(arg1);
    }
}

gcc -O0

3/4
mutual_parity pass 17 lines 
// glaurung: mutual_parity @ 0x11df
int32_t mutual_parity(int32_t arg0) {
    extern int is_even_helper(int, int);
    int ret;
    // x86-64 prologue: save rbp, frame 16 bytes
    if (((long)(arg0) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((((unsigned long)((unsigned int)(arg0)) == 64) | ((long)(arg0) < 64)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    ret = is_even_helper((unsigned long)((unsigned int)(arg0)), 128);
    // x86-64 epilogue: restore rbp
    return ret;
}
nontail_depth pass 15 lines 
// glaurung: nontail_depth @ 0x1248
int32_t nontail_depth(int32_t arg0) {
    int var3;
    // x86-64 prologue: save rbp, frame 16 bytes
    if (((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0)) == 0)) {
        if ((((unsigned long)((unsigned int)(arg0)) == 32) | ((long)(arg0) < 32))) {
            var3 = ((int (*)(int))nontail_depth)((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 1))));
            return (unsigned int)((var3 + 1));
        } else {
            return 0xffffffff;
        }
    } else {
        return 0;
    }
}
recursion_entry pass 32 lines 
// glaurung: recursion_entry @ 0x1283
int32_t recursion_entry(int32_t arg0, int32_t arg1) {
    extern int mutual_parity(int);
    extern int nontail_depth(int);
    extern int tail_countdown(int, int);
    long var2;
    int var4;
    int var6;
    int var8;
    // x86-64 prologue: save rbp, frame 16 bytes
    if (((long)(arg1) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 32) | ((long)(arg1) < 32)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    var2 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) & 3)));
    if (((unsigned long)((unsigned int)(var2)) == 0)) {
        var4 = mutual_parity((unsigned long)((unsigned int)(arg1)));
        return var4;
    } else {
        if (((unsigned long)((unsigned int)(var2)) == 1)) {
            var6 = tail_countdown((unsigned long)((unsigned int)(arg1)), 0);
            return var6;
        } else {
            var8 = nontail_depth((unsigned long)((unsigned int)(arg1)));
            return var8;
        }
    }
}
tail_countdown fail 11 lines 
// glaurung: tail_countdown @ 0x1212
int32_t tail_countdown(int32_t arg0, int32_t arg1) {
    int var7;
    // x86-64 prologue: save rbp, frame 16 bytes
    if (((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0)) == 0)) {
        var7 = ((int (*)(int, int))tail_countdown)((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg0)) - 1))), (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) + (unsigned long)((unsigned int)(arg0))))));
        return var7;
    } else {
        return (unsigned int)(arg1);
    }
}

gcc -O2

3/4
mutual_parity pass 33 lines 
// glaurung: mutual_parity @ 0x11c0
int32_t mutual_parity(int32_t arg0) {
    extern int is_even_helper(long, int);
    int ret;
    if (((unsigned long)(64) < (unsigned long)((unsigned long)((unsigned int)(arg0))))) {
        return 0xffffffff;
    }
    ret = 1;
    if (((unsigned long)((unsigned int)(arg0)) != 0)) {
        ret = 0;
        if (((unsigned long)((unsigned int)(arg0)) == 1)) {
            return ret;
        }
        ret = 1;
        if (((unsigned long)((unsigned int)(arg0)) == 2)) {
            return ret;
        }
        ret = 0;
        if (((unsigned long)((unsigned int)(arg0)) == 3)) {
            return ret;
        }
        ret = 1;
        if (((unsigned long)((unsigned int)(arg0)) == 4)) {
            return ret;
        }
        ret = 0;
        if (((unsigned long)((unsigned int)(arg0)) != 5)) {
            ret = is_even_helper((unsigned long)((unsigned int)((arg0 - 6))), 122);
            return ret;
        }
    }
    return ret;
}
nontail_depth pass 7 lines 
// glaurung: nontail_depth @ 0x1240
int32_t nontail_depth(int32_t arg0) {
    if ((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0))) {
        return 0;
    }
    return ((((unsigned long)((unsigned int)(arg0)) == 32) | ((long)(arg0) < 32)) ? arg0 : 0xffffffff);
}
recursion_entry fail 24 lines 
// glaurung: recursion_entry @ 0x1260
int32_t recursion_entry(int32_t arg0, int32_t arg1) {
    extern int mutual_parity(int);
    extern int nontail_depth(int);
    extern int tail_countdown(int, int);
    int ret;
    int var1;
    long var2;
    if (((unsigned long)(32) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return 0xffffffff;
    }
    var1 = ((unsigned int)(arg0) & 3);
    var2 = (unsigned long)((unsigned int)(var1));
    if (((unsigned long)((unsigned int)(var1)) == 0)) {
        ret = ((int (*)(void))mutual_parity)();
        return ret;
    }
    if (((unsigned long)((unsigned int)(var2)) == 1)) {
        ret = ((int (*)(void))tail_countdown)();
        return ret;
    }
    ret = nontail_depth((unsigned long)((unsigned int)(arg1)));
    return ret;
}
tail_countdown pass 21 lines 
// glaurung: tail_countdown @ 0x1220
int32_t tail_countdown(int32_t arg0, int32_t arg1) {
    long ret;
    long var0;
    long var1;
    int var2;
    int var3;
    var0 = (unsigned long)((unsigned int)(arg1));
    ret = (unsigned long)((unsigned int)(arg1));
    if ((((unsigned long)((unsigned int)(arg0)) != 0) && (0 <= (long)(arg0)))) {
        var1 = (unsigned long)((unsigned int)(arg0));
        do {
            var2 = (var0 + var1);
            var0 = (unsigned long)((unsigned int)(var2));
            var3 = (var1 - 1);
            var1 = (unsigned long)((unsigned int)(var3));
            ret = (unsigned long)((unsigned int)(var2));
        } while (((unsigned long)((unsigned int)(var3)) != 0));
    }
    return ret;
}

clang -O2

4/4
mutual_parity pass 33 lines 
// glaurung: mutual_parity @ 0x1130
int32_t mutual_parity(int32_t arg0) {
    long ret;
    long var1;
    long var2;
    int var3;
    ret = 0xffffffff;
    if (((unsigned long)(64) < (unsigned long)((unsigned long)((unsigned int)(arg0))))) {
        return ret;
    }
    var1 = 0;
    L_113c: ;
    while (1) {
        var2 = (unsigned long)((unsigned int)((arg0 + var1)));
        if (((unsigned long)((unsigned long)((unsigned int)(var2))) <= (unsigned long)(15))) {
            break;
        }
        var3 = (var1 - 16);
        var1 = (unsigned long)((unsigned int)(var3));
        if (((unsigned long)((unsigned int)(var3)) != 0xffffff80)) {
            goto L_113c;
        }
        goto L_114c;
    }
    ret = 1;
    if (((((unsigned long)(0x5555) >> (var2 & 31)) & 1) == 0)) {
        return 0;
    }
    L_115d: ;
    return ret;
    L_114c: ;
    goto L_115d;
}
nontail_depth pass 24 lines 
// glaurung: nontail_depth @ 0x1190
int32_t nontail_depth(int32_t arg0) {
    long ret;
    int var1;
    long var3;
    ret = 0;
    if ((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0))) {
        return ret;
    }
    L_11a0: ;
    while (((unsigned long)((unsigned long)((unsigned int)(arg0))) <= (unsigned long)(32))) {
        var1 = (ret + 1);
        ret = (unsigned long)((unsigned int)(var1));
        if (((unsigned int)(arg0) != (unsigned int)(var1))) {
            goto L_11a0;
        } else {
            var3 = 0;
            ret = (unsigned long)((unsigned int)(arg0));
        }
        return (unsigned int)((ret + var3));
    }
    var3 = 0xffffffff;
    return (unsigned int)((ret + 0xffffffff));
}
recursion_entry pass 22 lines 
// glaurung: recursion_entry @ 0x11c0
int32_t recursion_entry(int32_t arg0, int32_t arg1) {
    extern int mutual_parity(int);
    extern int nontail_depth(int);
    extern int tail_countdown(int, int);
    int ret;
    long var1;
    if (((unsigned long)(32) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return 0xffffffff;
    }
    var1 = (unsigned long)((unsigned int)((arg0 & 3)));
    if (((unsigned long)((unsigned int)(var1)) == 1)) {
        ret = tail_countdown((unsigned long)((unsigned int)(arg1)), 0);
        return ret;
    }
    if (((unsigned long)((unsigned int)(var1)) != 0)) {
        ret = nontail_depth((unsigned long)((unsigned int)(arg1)));
        return ret;
    }
    ret = mutual_parity((unsigned long)((unsigned int)(arg1)));
    return ret;
}
tail_countdown pass 11 lines 
// glaurung: tail_countdown @ 0x1170
int32_t tail_countdown(int32_t arg0, int32_t arg1) {
    long ret;
    long var0;
    ret = (unsigned long)((unsigned int)(arg1));
    if (((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0)) == 0)) {
        var0 = (unsigned long)((unsigned int)((arg0 - 1)));
        ret = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)((ret + arg0))) + (unsigned long)((unsigned int)((var0 * var0)))))) - ((unsigned long)(((unsigned long)((unsigned int)((arg0 - 2))) * var0)) >> 1))));
    }
    return ret;
}

← 213 fixtures