glaurung

Fixture 34

coin change

C · 2 functions · 4 lanes · 8 of 8 function-lanes behave identically

All 4 lanes recompile and return the same results as the original.

Minimum-coin change and the count of distinct combinations. The sentinel "unreachable" value participates in arithmetic comparisons, which is where an over-eager value-range narrowing shows up.

tests/decompiler_fixtures/src/34_coin_change.c source 
#include <stdint.h>

/* Minimum-coin change and the count of distinct combinations.  The sentinel
 * "unreachable" value participates in arithmetic comparisons, which is where
 * an over-eager value-range narrowing shows up. */

#define COIN_KINDS 8
#define COIN_TARGET 32
#define COIN_UNREACHABLE 1000000

__attribute__((noinline)) int32_t
min_coins(const int32_t *denominations, int32_t kinds, int32_t target) {
    int32_t best[COIN_TARGET + 1];
    int32_t amount;
    int32_t kind;
    if (denominations == 0 || kinds < 0 || kinds > COIN_KINDS || target < 0 ||
        target > COIN_TARGET) {
        return -1;
    }
    best[0] = 0;
    for (amount = 1; amount <= target; ++amount) {
        best[amount] = COIN_UNREACHABLE;
    }
    for (amount = 1; amount <= target; ++amount) {
        for (kind = 0; kind < kinds; ++kind) {
            int32_t coin = denominations[kind];
            if (coin > 0 && coin <= amount) {
                int32_t candidate = best[amount - coin];
                if (candidate != COIN_UNREACHABLE && candidate + 1 < best[amount]) {
                    best[amount] = candidate + 1;
                }
            }
        }
    }
    if (best[target] == COIN_UNREACHABLE) {
        return -2;
    }
    return best[target];
}

__attribute__((noinline)) uint32_t
count_change(const int32_t *denominations, int32_t kinds, int32_t target) {
    uint32_t ways[COIN_TARGET + 1];
    int32_t amount;
    int32_t kind;
    if (denominations == 0 || kinds < 0 || kinds > COIN_KINDS || target < 0 ||
        target > COIN_TARGET) {
        return 0;
    }
    ways[0] = 1;
    for (amount = 1; amount <= target; ++amount) {
        ways[amount] = 0;
    }
    for (kind = 0; kind < kinds; ++kind) {
        int32_t coin = denominations[kind];
        if (coin <= 0 || coin > target) {
            continue;
        }
        for (amount = coin; amount <= target; ++amount) {
            ways[amount] += ways[amount - coin];
        }
    }
    return ways[target];
}

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
count_change pass 52 lines 
// glaurung: count_change @ 0x12d0
__attribute__((no_stack_protector)) uint32_t count_change(const int32_t * arg0, int32_t arg1, int32_t arg2) {
    int amount;
    int kind;
    int coin;
    int local_4;
    unsigned char local_a0[132];
    // x86-64 prologue: save rbp, frame 48 bytes
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((long)(arg1) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((long)(arg2) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((((unsigned long)((unsigned int)(arg2)) == 32) | ((long)(arg2) < 32)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    *(int *)(&local_a0[0]) = 1;
    for (amount = 1; ((((unsigned int)(amount) == (unsigned int)(arg2)) | (amount < arg2)) != 0); amount++) {
        *(int *)((&local_a0[0] + ((long)(amount) * 4))) = 0;
    }
    kind = 0;
    while ((kind < arg1)) {
        coin = arg0[(long)(kind)];
        if ((((unsigned long)((unsigned int)(coin)) == 0) | ((long)(coin) < 0))) {
            L_13b3: ;
        } else {
            if ((((unsigned int)(coin) == (unsigned int)(arg2)) | (coin < arg2))) {
                for (amount = coin; ((((unsigned int)(amount) == (unsigned int)(arg2)) | (amount < arg2)) != 0); amount++) {
                    *(int *)((&local_a0[0] + ((long)(amount) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_a0[0] + ((long)((int)(((unsigned long)((unsigned int)(amount)) - coin))) * 4))))) + *(int *)((&local_a0[0] + ((long)(amount) * 4))));
                }
            } else {
                goto L_13b3;
            }
        }
        kind = ((unsigned int)(kind) + 1);
    }
    local_4 = *(int *)((&local_a0[0] + ((long)(arg2) * 4)));
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
min_coins pass 61 lines 
// glaurung: min_coins @ 0x1100
__attribute__((no_stack_protector)) int32_t min_coins(const int32_t * arg0, int32_t arg1, int32_t arg2) {
    int amount;
    int kind;
    int coin;
    int candidate;
    int local_4;
    unsigned char local_a0[132];
    // 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 (((long)(arg1) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((long)(arg2) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg2)) == 32) | ((long)(arg2) < 32)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    *(int *)(&local_a0[0]) = 0;
    for (amount = 1; ((((unsigned int)(amount) == (unsigned int)(arg2)) | (amount < arg2)) != 0); amount++) {
        *(int *)((&local_a0[0] + ((long)(amount) * 4))) = 0xf4240;
    }
    amount = 1;
    while (((((unsigned int)(amount) == (unsigned int)(arg2)) | (amount < arg2)) != 0)) {
        for (kind = 0; (kind < arg1); kind++) {
            coin = arg0[(long)(kind)];
            if (((((unsigned long)((unsigned int)(coin)) == 0) | ((long)(coin) < 0)) == 0)) {
                if (((((unsigned int)(coin) == (unsigned int)(amount)) | (coin < amount)) != 0)) {
                    candidate = *(int *)((&local_a0[0] + ((long)((int)(((unsigned long)((unsigned int)(amount)) - coin))) * 4)));
                    if (((unsigned long)((unsigned int)(candidate)) != 0xf4240)) {
                        if (((long)((int)(((unsigned long)((unsigned int)(candidate)) + 1))) < (long)((int)(*(int *)((&local_a0[0] + ((long)(amount) * 4))))))) {
                            *(int *)((&local_a0[0] + ((long)(amount) * 4))) = ((unsigned long)((unsigned int)(candidate)) + 1);
                        }
                    }
                }
            }
        }
        amount = ((unsigned int)(amount) + 1);
    }
    if (((unsigned long)((unsigned int)(*(int *)((&local_a0[0] + ((long)(arg2) * 4))))) != 0xf4240)) {
        return (unsigned int)(*(int *)((&local_a0[0] + ((long)(arg2) * 4))));
    } else {
        return (unsigned int)(-2);
    }
}

clang -O2

2/2
count_change pass 232 lines 
// glaurung: count_change @ 0x12b0
__attribute__((no_stack_protector)) uint32_t count_change(const int32_t * arg0, int32_t arg1, int32_t arg2) {
    extern void * memset(void *, int, __SIZE_TYPE__);
    int coin;
    int amount;
    int kind;
    unsigned char local_b8[184];
    long ret;
    long var1;
    int var100;
    int var101;
    int var102;
    int var103;
    int var105;
    int var106;
    int var107;
    int var108;
    int var109;
    long var11;
    int var110;
    int var111;
    void * var14;
    long var15;
    long var19;
    long var2;
    long var29;
    long var3;
    long var30;
    long var33;
    long var34;
    long var36;
    int var39;
    long var43;
    long var48;
    long var49;
    long var51;
    long var52;
    long var55;
    long var57;
    long var58;
    int var67;
    int var68;
    int var69;
    void * var7;
    int var70;
    int var71;
    int var72;
    int var73;
    int var74;
    long var76;
    long var78;
    int var88;
    int var89;
    long var9;
    int var90;
    int var91;
    int var92;
    int var93;
    int var94;
    int var95;
    int var96;
    int var97;
    int var98;
    int var99;
    // x86-64 prologue: save callee registers, frame 40 bytes
    ret = 0;
    if (((unsigned long)(32) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var1 = (long)arg0;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var2 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var3 = (unsigned long)((unsigned int)(arg2));
    *(int *)(&local_b8[0]) = 1;
    if (((unsigned long)((unsigned int)(arg2)) != 0)) {
        var7 = memset((void *)((&local_b8[0] + 4)), 0, (__SIZE_TYPE__)(((unsigned long)((unsigned int)(var3)) << 2)));
    }
    if (((unsigned long)((unsigned int)(var2)) != 0)) {
        var9 = (unsigned long)((unsigned int)(var2));
        var11 = (unsigned long)((unsigned int)((var3 + 1)));
        var14 = &local_b8[0];
        var15 = 0;
        do {
            coin = (unsigned long)((unsigned int)(*(int *)((var1 + var15 * 4))));
            if (((((unsigned long)((unsigned int)(coin)) == 0) | ((long)(coin) < 0)) == 0)) {
                if (((((unsigned int)(coin) == (unsigned int)(var3)) | ((long)(coin) < (long)((int)(var3)))) != 0)) {
                    var19 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var3)) - coin)));
                    amount = coin;
                    if (((unsigned long)((unsigned long)((unsigned int)(var19))) < (unsigned long)(7))) {
                        L_1440: ;
                        if (((unsigned long)((unsigned char)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var11)) - amount))) & 1))) != 0)) {
                            *(int *)((&local_b8[0] + (amount * 4))) = (*(int *)((&local_b8[0] + (amount * 4))) + (unsigned long)((unsigned int)(*(int *)((&local_b8[0] + ((amount - coin) * 4))))));
                            var29 = ((unsigned long)((unsigned int)(amount)) + 1);
                            if (((unsigned int)(amount) == (unsigned int)(var3))) {
                                goto L_1320;
                            }
                            goto L_147c;
                        } else {
                            var30 = (unsigned long)((unsigned int)(amount));
                            if (((unsigned int)(amount) != (unsigned int)(var3))) {
                                var29 = var30;
                                L_147c: ;
                                var33 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var11)) - var29)));
                                var34 = (long)(((&local_b8[0] + 4) + (var29 * 4)));
                                var36 = (-((unsigned long)((unsigned int)(coin)) << 2));
                                do {
                                    *(int *)((var34 - 0x4)) = (*(int *)((var34 - 0x4)) + (unsigned long)((unsigned int)(*(int *)((var34 + var36 - 0x4)))));
                                    *(int *)((var34)) = (*(int *)((var34)) + (unsigned long)((unsigned int)(*(int *)((var34 + var36)))));
                                    var34 = (var34 + 8);
                                    var39 = (var33 - 2);
                                    var33 = (unsigned long)((unsigned int)(var39));
                                } while (((unsigned long)((unsigned int)(var39)) != 0));
                            }
                        }
                    } else {
                        var43 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var3)) - coin)));
                        var48 = ((unsigned long)(var14) < (unsigned long)(((&local_b8[0] + 4) + ((var43 + coin) * 4))));
                        if (((unsigned long)(((&local_b8[0] + 4) + (var43 * 4))) <= (unsigned long)((&local_b8[0] + (coin * 4))))) {
                            L_1376: ;
                            var49 = (var19 + 1);
                            var51 = (var49 & -8);
                            var52 = (var51 - 8);
                            var55 = (((unsigned long)(var52) >> 3) + 1);
                            if ((var52 == 0)) {
                                var57 = 0;
                                if (((unsigned long)((unsigned char)((var55 & 1))) != 0)) {
                                    L_1405: ;
                                    var58 = (var57 + (unsigned long)((unsigned int)(coin)));
                                    var67 = (*(int *)((&local_b8[0] + (var58 * 4))) + *(int *)((&local_b8[0] + (var57 * 4))));
                                    var68 = (*(int *)((&local_b8[0] + ((var58 * 4) + 4))) + *(int *)((&local_b8[0] + ((var57 * 4) + 4))));
                                    var69 = (*(int *)((&local_b8[0] + ((var58 * 4) + 8))) + *(int *)((&local_b8[0] + ((var57 * 4) + 8))));
                                    var70 = (*(int *)((&local_b8[0] + ((var58 * 4) + 12))) + *(int *)((&local_b8[0] + ((var57 * 4) + 12))));
                                    ret = ((unsigned long)((unsigned int)(var68)) | (unsigned long)((unsigned int)(var67)));
                                    var71 = (*(int *)((&local_b8[0] + ((var58 * 4) + 16))) + *(int *)((&local_b8[0] + ((var57 * 4) + 16))));
                                    var72 = (*(int *)((&local_b8[0] + ((var58 * 4) + 20))) + *(int *)((&local_b8[0] + ((var57 * 4) + 20))));
                                    var73 = (*(int *)((&local_b8[0] + ((var58 * 4) + 24))) + *(int *)((&local_b8[0] + ((var57 * 4) + 24))));
                                    var74 = (*(int *)((&local_b8[0] + ((var58 * 4) + 28))) + *(int *)((&local_b8[0] + ((var57 * 4) + 28))));
                                    *(int *)((&local_b8[0] + (var58 * 4))) = var67;
                                    *(int *)((&local_b8[0] + ((var58 * 4) + 4))) = var68;
                                    *(int *)((&local_b8[0] + ((var58 * 4) + 8))) = var69;
                                    *(int *)((&local_b8[0] + ((var58 * 4) + 12))) = var70;
                                    *(int *)((&local_b8[0] + ((var58 * 4) + 16))) = var71;
                                    *(int *)((&local_b8[0] + ((var58 * 4) + 20))) = var72;
                                    *(int *)((&local_b8[0] + ((var58 * 4) + 24))) = var73;
                                    *(int *)((&local_b8[0] + ((var58 * 4) + 28))) = var74;
                                } else {
                                }
                            } else {
                                var76 = (var55 & -2);
                                var78 = (long)((((&local_b8[0] + 4) + ((unsigned long)((unsigned int)(coin)) * 4)) + 44));
                                var57 = 0;
                                do {
                                    var88 = *(int *)((var78 + var57 * 4 - 0x10));
                                    var89 = *(int *)((var78 + var57 * 4 - 0xc));
                                    var90 = *(int *)((var78 + var57 * 4 - 0x8));
                                    var91 = *(int *)((var78 + var57 * 4 - 0x4));
                                    var92 = *(int *)((var78 + var57 * 4));
                                    var93 = *(int *)((var78 + var57 * 4 + 0x4));
                                    var94 = *(int *)((var78 + var57 * 4 + 0x8));
                                    var95 = *(int *)((var78 + var57 * 4 + 0xc));
                                    var96 = (*(int *)((var78 + var57 * 4 - 0x30)) + *(int *)((&local_b8[0] + (var57 * 4))));
                                    var97 = (*(int *)((var78 + var57 * 4 - 0x2c)) + *(int *)((&local_b8[0] + ((var57 * 4) + 4))));
                                    var98 = (*(int *)((var78 + var57 * 4 - 0x28)) + *(int *)((&local_b8[0] + ((var57 * 4) + 8))));
                                    var99 = (*(int *)((var78 + var57 * 4 - 0x24)) + *(int *)((&local_b8[0] + ((var57 * 4) + 12))));
                                    ret = ((unsigned long)((unsigned int)(var97)) | (unsigned long)((unsigned int)(var96)));
                                    var100 = (*(int *)((var78 + var57 * 4 - 0x20)) + *(int *)((&local_b8[0] + ((var57 * 4) + 16))));
                                    var101 = (*(int *)((var78 + var57 * 4 - 0x1c)) + *(int *)((&local_b8[0] + ((var57 * 4) + 20))));
                                    var102 = (*(int *)((var78 + var57 * 4 - 0x18)) + *(int *)((&local_b8[0] + ((var57 * 4) + 24))));
                                    var103 = (*(int *)((var78 + var57 * 4 - 0x14)) + *(int *)((&local_b8[0] + ((var57 * 4) + 28))));
                                    *(int *)((var78 + var57 * 4 - 0x30)) = var96;
                                    *(int *)((var78 + var57 * 4 - 0x2c)) = var97;
                                    *(int *)((var78 + var57 * 4 - 0x28)) = var98;
                                    *(int *)((var78 + var57 * 4 - 0x24)) = var99;
                                    *(int *)((var78 + var57 * 4 - 0x20)) = var100;
                                    *(int *)((var78 + var57 * 4 - 0x1c)) = var101;
                                    *(int *)((var78 + var57 * 4 - 0x18)) = var102;
                                    *(int *)((var78 + var57 * 4 - 0x14)) = var103;
                                    var105 = (var89 + *(int *)((&local_b8[0] + ((var57 * 4) + 36))));
                                    var106 = (var90 + *(int *)((&local_b8[0] + ((var57 * 4) + 40))));
                                    var107 = (var91 + *(int *)((&local_b8[0] + ((var57 * 4) + 44))));
                                    var108 = (var92 + *(int *)((&local_b8[0] + ((var57 * 4) + 48))));
                                    var109 = (var93 + *(int *)((&local_b8[0] + ((var57 * 4) + 52))));
                                    var110 = (var94 + *(int *)((&local_b8[0] + ((var57 * 4) + 56))));
                                    var111 = (var95 + *(int *)((&local_b8[0] + ((var57 * 4) + 60))));
                                    *(int *)((var78 + var57 * 4 - 0x10)) = (var88 + *(int *)((&local_b8[0] + ((var57 * 4) + 32))));
                                    *(int *)((var78 + var57 * 4 - 0xc)) = var105;
                                    *(int *)((var78 + var57 * 4 - 0x8)) = var106;
                                    *(int *)((var78 + var57 * 4 - 0x4)) = var107;
                                    *(int *)((var78 + var57 * 4)) = var108;
                                    *(int *)((var78 + var57 * 4 + 0x4)) = var109;
                                    *(int *)((var78 + var57 * 4 + 0x8)) = var110;
                                    *(int *)((var78 + var57 * 4 + 0xc)) = var111;
                                    var57 = (var57 + 16);
                                    var76 = (var76 - 2);
                                } while ((var76 != 0));
                                if (((unsigned long)((unsigned char)((var55 & 1))) == 0)) {
                                    goto L_142a;
                                }
                                goto L_1405;
                            }
                            L_142a: ;
                            if ((var49 != var51)) {
                                amount = (var51 + coin);
                                goto L_1440;
                            }
                        } else {
                            amount = coin;
                            if (((unsigned long)((unsigned char)((var48 & 255))) != 0)) {
                                goto L_1440;
                            } else {
                                goto L_1376;
                            }
                        }
                    }
                }
            }
            L_1320: ;
            kind = (var15 + 1);
            var15 = (unsigned long)((unsigned int)(kind));
        } while ((kind != var9));
    }
    // x86-64 epilogue: restore callee registers
    return (unsigned int)(*(int *)((&local_b8[0] + ((long)((int)(var3)) * 4))));
}
min_coins pass 168 lines 
// glaurung: min_coins @ 0x1110
__attribute__((no_stack_protector)) int32_t min_coins(const int32_t * arg0, int32_t arg1, int32_t arg2) {
    int amount;
    int coin;
    int candidate;
    int kind;
    unsigned char local_88[136];
    long ret;
    long var0;
    long var10;
    long var13;
    long var16;
    long var17;
    long var19;
    long var2;
    int var20;
    int var21;
    int var22;
    int var23;
    long var24;
    int var26;
    int var27;
    int var28;
    int var29;
    long var3;
    long var32;
    long var33;
    long var35;
    long var36;
    long var39;
    long var4;
    int var46;
    long var48;
    long var5;
    long var51;
    long var53;
    long var9;
    ret = 0xffffffff;
    if (((unsigned long)(32) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
        return ret;
    }
    if ((arg0 == 0)) {
        return ret;
    }
    if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return ret;
    }
    *(long *)((&local_88[0] + 128)) = 0xffffffff;
    *(int *)(&local_88[0]) = 0;
    if (((unsigned long)((unsigned int)(arg2)) != 0)) {
        var0 = (unsigned long)((unsigned int)(arg2));
        var2 = 1;
        var3 = var4;
        if (((unsigned long)((unsigned long)((unsigned int)(arg2))) < (unsigned long)(4))) {
            L_11f4: ;
            var5 = (var0 + 1);
            amount = var2;
            do {
                *(int *)((&local_88[0] + (amount * 4))) = 0xf4240;
                amount = (amount + 1);
            } while ((var5 != amount));
        } else {
            var9 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var0)) & -4)));
            var10 = (var9 - 4);
            var13 = (((unsigned long)(var10) >> 2) + 1);
            var16 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var13)) & 7)));
            if (((unsigned long)(28) <= (unsigned long)(var10))) {
                var17 = (var13 & -8);
                var19 = 0;
                var20 = 0xf4240;
                var21 = 0xf4240;
                var22 = 0xf4240;
                var23 = 0xf4240;
                do {
                    *(int *)((&local_88[0] + ((var19 * 4) + 4))) = var20;
                    *(int *)((&local_88[0] + ((var19 * 4) + 8))) = var21;
                    *(int *)((&local_88[0] + ((var19 * 4) + 12))) = var22;
                    *(int *)((&local_88[0] + ((var19 * 4) + 16))) = var23;
                    *(int *)((&local_88[0] + ((var19 * 4) + 20))) = var20;
                    *(int *)((&local_88[0] + ((var19 * 4) + 24))) = var21;
                    *(int *)((&local_88[0] + ((var19 * 4) + 28))) = var22;
                    *(int *)((&local_88[0] + ((var19 * 4) + 32))) = var23;
                    *(int *)((&local_88[0] + ((var19 * 4) + 36))) = var20;
                    *(int *)((&local_88[0] + ((var19 * 4) + 40))) = var21;
                    *(int *)((&local_88[0] + ((var19 * 4) + 44))) = var22;
                    *(int *)((&local_88[0] + ((var19 * 4) + 48))) = var23;
                    *(int *)((&local_88[0] + ((var19 * 4) + 52))) = var20;
                    *(int *)((&local_88[0] + ((var19 * 4) + 56))) = var21;
                    *(int *)((&local_88[0] + ((var19 * 4) + 60))) = var22;
                    *(int *)((&local_88[0] + ((var19 * 4) + 64))) = var23;
                    *(int *)((&local_88[0] + ((var19 * 4) + 68))) = var20;
                    *(int *)((&local_88[0] + ((var19 * 4) + 72))) = var21;
                    *(int *)((&local_88[0] + ((var19 * 4) + 76))) = var22;
                    *(int *)((&local_88[0] + ((var19 * 4) + 80))) = var23;
                    *(int *)((&local_88[0] + ((var19 * 4) + 84))) = var20;
                    *(int *)((&local_88[0] + ((var19 * 4) + 88))) = var21;
                    *(int *)((&local_88[0] + ((var19 * 4) + 92))) = var22;
                    *(int *)((&local_88[0] + ((var19 * 4) + 96))) = var23;
                    *(int *)((&local_88[0] + ((var19 * 4) + 100))) = var20;
                    *(int *)((&local_88[0] + ((var19 * 4) + 104))) = var21;
                    *(int *)((&local_88[0] + ((var19 * 4) + 108))) = var22;
                    *(int *)((&local_88[0] + ((var19 * 4) + 112))) = var23;
                    *(int *)((&local_88[0] + ((var19 * 4) + 116))) = var20;
                    *(int *)((&local_88[0] + ((var19 * 4) + 120))) = var21;
                    *(int *)((&local_88[0] + ((var19 * 4) + 124))) = var22;
                    *(int *)((&local_88[0] + ((var19 * 4) + 128))) = var23;
                    var19 = (var19 + 32);
                    var17 = (var17 - 8);
                    var24 = var19;
                } while ((var17 != 0));
            } else {
                var24 = 0;
            }
            var3 = var4;
            if ((var16 != 0)) {
                var26 = 0xf4240;
                var27 = 0xf4240;
                var28 = 0xf4240;
                var29 = 0xf4240;
                do {
                    var3 = ((var24 * 4) | 4);
                    *(int *)((&local_88[0] + var3)) = var26;
                    *(int *)((&local_88[0] + (var3 + 4))) = var27;
                    *(int *)((&local_88[0] + (var3 + 8))) = var28;
                    *(int *)((&local_88[0] + (var3 + 12))) = var29;
                    var24 = (var24 + 4);
                    var16 = (var16 - 1);
                } while ((var16 != 0));
            }
            if ((var0 != var9)) {
                var2 = (var9 | 1);
                goto L_11f4;
            }
        }
        if (((unsigned long)((unsigned int)(arg2)) != 0)) {
            var32 = (unsigned long)((unsigned int)((arg2 + 1)));
            var33 = (unsigned long)((unsigned int)(arg1));
            var35 = 1;
            do {
                var36 = var3;
                if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
                    var39 = 0;
                    do {
                        coin = (long)((int)(*(int *)(((long)arg0 + var39 * 4))));
                        if ((0 < coin)) {
                            if ((coin <= var35)) {
                                candidate = (unsigned long)((unsigned int)(*(int *)((&local_88[0] + ((long)((int)(((unsigned long)((unsigned int)(var35)) - coin))) * 4)))));
                                if (((unsigned long)((unsigned int)(candidate)) != 0xf4240)) {
                                    var46 = (candidate + 1);
                                    var48 = (unsigned long)((unsigned int)(*(int *)((&local_88[0] + (var35 * 4)))));
                                    *(int *)((&local_88[0] + (var35 * 4))) = (((long)((int)(var48)) <= (long)((int)(var46))) ? var48 : (unsigned long)((unsigned int)(var46)));
                                }
                            }
                        }
                        kind = (var39 + 1);
                        var36 = (unsigned long)((unsigned int)(kind));
                        var39 = (unsigned long)((unsigned int)(kind));
                    } while ((var33 != kind));
                }
                var51 = (var35 + 1);
                var35 = var51;
                var3 = var36;
            } while ((var51 != var32));
        }
    }
    var53 = (unsigned long)((unsigned int)(*(int *)((&local_88[0] + ((long)(arg2) * 4)))));
    return (((unsigned long)((unsigned int)(var53)) != 0xf4240) ? var53 : 0xfffffffe);
}

gcc -O0

2/2
count_change pass 37 lines 
// glaurung: count_change @ 0x12e6
uint32_t count_change(const int32_t * arg0, int32_t arg1, int32_t arg2) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int amount;
    int kind;
    int coin;
    long local_8;
    unsigned char local_90[132];
    long ret;
    // x86-64 prologue: save rbp, frame 176 bytes
    local_8 = (long)(0x28);
    if ((((((arg0 == 0) || ((long)(arg1) < 0)) || ((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) == 0)) || ((long)(arg2) < 0)) || (((unsigned long)((unsigned int)(arg2)) != 32) && (32 <= (long)(arg2))))) {
        ret = 0;
    } else {
        *(int *)(&local_90[0]) = 1;
        for (amount = 1; ((((unsigned int)(amount) == (unsigned int)(arg2)) | (amount < arg2)) != 0); amount++) {
            *(int *)((&local_90[0] + ((long)(amount) * 4))) = 0;
        }
        kind = 0;
        while ((kind < arg1)) {
            coin = arg0[(long)(kind)];
            if (((((unsigned long)((unsigned int)(coin)) == 0) | ((long)(coin) < 0)) || ((((unsigned int)(coin) == (unsigned int)(arg2)) | (coin < arg2)) == 0))) {
            } else {
                for (amount = coin; ((((unsigned int)(amount) == (unsigned int)(arg2)) | (amount < arg2)) != 0); amount++) {
                    *(int *)((&local_90[0] + ((long)(amount) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_90[0] + ((long)(amount) * 4))))) + (unsigned long)((unsigned int)(*(int *)((&local_90[0] + ((long)((int)(((unsigned long)((unsigned int)(amount)) - coin))) * 4))))));
                }
            }
            kind = (kind + 1);
        }
        ret = (unsigned long)((unsigned int)(*(int *)((&local_90[0] + ((long)(arg2) * 4)))));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}
min_coins pass 44 lines 
// glaurung: min_coins @ 0x1119
int32_t min_coins(const int32_t * arg0, int32_t arg1, int32_t arg2) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int amount;
    int kind;
    int coin;
    int candidate;
    long local_8;
    unsigned char local_90[132];
    long ret;
    // x86-64 prologue: save rbp, frame 176 bytes
    local_8 = (long)(0x28);
    if ((((((arg0 == 0) || ((long)(arg1) < 0)) || ((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) == 0)) || ((long)(arg2) < 0)) || (((unsigned long)((unsigned int)(arg2)) != 32) && (32 <= (long)(arg2))))) {
        ret = 0xffffffff;
    } else {
        *(int *)(&local_90[0]) = 0;
        for (amount = 1; ((((unsigned int)(amount) == (unsigned int)(arg2)) | (amount < arg2)) != 0); amount++) {
            *(int *)((&local_90[0] + ((long)(amount) * 4))) = 0xf4240;
        }
        amount = 1;
        while (((((unsigned int)(amount) == (unsigned int)(arg2)) | (amount < arg2)) != 0)) {
            for (kind = 0; (kind < arg1); kind++) {
                coin = arg0[(long)(kind)];
                if (((((unsigned long)((unsigned int)(coin)) == 0) | ((long)(coin) < 0)) == 0)) {
                    if (((((unsigned int)(coin) == (unsigned int)(amount)) | (coin < amount)) != 0)) {
                        candidate = *(int *)((&local_90[0] + ((long)((int)(((unsigned long)((unsigned int)(amount)) - coin))) * 4)));
                        if (((unsigned long)((unsigned int)(candidate)) != 0xf4240)) {
                            if (((long)((int)(((unsigned long)((unsigned int)(candidate)) + 1))) < (long)((int)(*(int *)((&local_90[0] + ((long)(amount) * 4))))))) {
                                *(int *)((&local_90[0] + ((long)(amount) * 4))) = ((unsigned long)((unsigned int)(candidate)) + 1);
                            }
                        }
                    }
                }
            }
            amount = (amount + 1);
        }
        ret = (((unsigned long)((unsigned int)(*(int *)((&local_90[0] + ((long)(arg2) * 4))))) != 0xf4240) ? (unsigned long)((unsigned int)(*(int *)((&local_90[0] + ((long)(arg2) * 4))))) : 0xfffffffe);
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}

gcc -O2

2/2
count_change pass 68 lines 
// glaurung: count_change @ 0x1260
uint32_t count_change(const int32_t * arg0, int32_t arg1, int32_t arg2) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    extern void * memset(void *, int, __SIZE_TYPE__);
    int amount;
    int kind;
    long local_20;
    unsigned char local_a8[132];
    long ret;
    long var11;
    long var13;
    long var14;
    long var2;
    long var20;
    long var22;
    long var23;
    long var24;
    long var4;
    long var5;
    void * var8;
    local_20 = (long)(0x28);
    ret = 0;
    if ((arg0 != 0)) {
        var2 = (unsigned long)((unsigned int)(arg2));
        if (((unsigned long)(32) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
            L_1350: ;
            ret = 0;
        } else {
            var4 = (unsigned long)((unsigned int)(arg1));
            if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
                goto L_1350;
            } else {
                *(int *)(&local_a8[0]) = 1;
                var5 = (long)arg0;
                if (((unsigned long)((unsigned int)(arg2)) != 0)) {
                    var8 = memset((void *)((&local_a8[0] + 4)), 0, (__SIZE_TYPE__)((((unsigned long)((unsigned int)((arg2 - 1))) * 4) + 4)));
                }
                if (((unsigned long)((unsigned int)(var4)) != 0)) {
                    var11 = var5;
                    var13 = (long)(&local_a8[0]);
                    var14 = ((var5 + ((unsigned long)((unsigned int)((var4 - 1))) * 4)) + 4);
                    do {
                        amount = (unsigned long)((unsigned int)(*(int *)((var11))));
                        if (((((unsigned long)((unsigned int)(amount)) == 0) | ((long)(amount) < 0)) == 0)) {
                            if (((long)(amount) <= (long)((int)(var2)))) {
                                var20 = ((long)(amount) * 4);
                                var22 = (var13 + var20);
                                var23 = (-var20);
                                var24 = (long)(((&local_a8[0] + 4) + (((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var2)) - amount))) + (long)(amount)) * 4)));
                                do {
                                    *(int *)((var22)) = (*(int *)((var22)) + (unsigned long)((unsigned int)(*(int *)((var22 + var23)))));
                                    var22 = (var22 + 4);
                                } while ((var22 != var24));
                            }
                        }
                        var11 = (var11 + 4);
                    } while ((var11 != var14));
                }
                ret = (unsigned long)((unsigned int)(*(int *)((&local_a8[0] + ((long)((int)(var2)) * 4)))));
            }
        }
    }
    if ((local_20 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: tear down frame
    return ret;
}
min_coins pass 86 lines 
// glaurung: min_coins @ 0x1140
int32_t min_coins(const int32_t * arg0, int32_t arg1, int32_t arg2) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int amount;
    int coin;
    int candidate;
    int kind;
    long local_10;
    unsigned char local_98[132];
    long ret;
    long var11;
    long var13;
    long var15;
    int var22;
    long var23;
    int var24;
    long var3;
    long var4;
    long var6;
    long var7;
    long var8;
    long var9;
    local_10 = (long)(0x28);
    if ((arg0 == 0)) {
        L_124b: ;
        ret = 0xffffffff;
    } else {
        var3 = (long)(arg2);
        if (((unsigned long)(32) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
            goto L_124b;
        } else {
            var4 = (unsigned long)((unsigned int)(arg1));
            if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
                goto L_124b;
            } else {
                *(int *)(&local_98[0]) = 0;
                if (((unsigned long)((unsigned int)(var3)) != 0)) {
                    var6 = (long)((&local_98[0] + 4));
                    var7 = (long)arg0;
                    var8 = (long)(((&local_98[0] + ((unsigned long)((unsigned int)((var3 - 1))) * 4)) + 8));
                    var9 = var6;
                    do {
                        *(int *)((var9)) = 0xf4240;
                        var9 = (var9 + 4);
                    } while ((var9 != var8));
                    var11 = (unsigned long)((unsigned int)((var3 + 1)));
                    var13 = ((var7 + ((unsigned long)((unsigned int)((var4 - 1))) * 4)) + 4);
                    amount = 1;
                    do {
                        var15 = var7;
                        if (((unsigned long)((unsigned int)(var4)) != 0)) {
                            do {
                                coin = (unsigned long)((unsigned int)(*(int *)((var15))));
                                if (((((unsigned long)((unsigned int)(coin)) == 0) | ((long)(coin) < 0)) == 0)) {
                                    if (((((unsigned int)(coin) == (unsigned int)(amount)) | (coin < amount)) != 0)) {
                                        candidate = (unsigned long)((unsigned int)(*(int *)((&local_98[0] + ((long)((int)(((unsigned long)((unsigned int)(amount)) - coin))) * 4)))));
                                        if (((unsigned long)((unsigned int)(candidate)) != 0xf4240)) {
                                            var22 = (candidate + 1);
                                            var23 = (unsigned long)((unsigned int)(var22));
                                            if (((long)((int)(var22)) < (long)((int)(*(int *)((var6)))))) {
                                                *(int *)((var6)) = var23;
                                            }
                                        }
                                    }
                                }
                                var15 = (var15 + 4);
                            } while ((var13 != var15));
                        }
                        var24 = (amount + 1);
                        amount = (unsigned long)((unsigned int)(var24));
                        var6 = (var6 + 4);
                    } while (((unsigned int)(var24) != (unsigned int)(var11)));
                }
                ret = (unsigned long)((unsigned int)(*(int *)((&local_98[0] + (var3 * 4)))));
                if (((unsigned long)((unsigned int)(ret)) == 0xf4240)) {
                    ret = 0xfffffffe;
                }
            }
        }
    }
    if ((local_10 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: tear down frame
    return ret;
}

← 213 fixtures