glaurung

Fixture 22

dijkstra

C · 1 functions · 4 lanes · 4 of 4 function-lanes behave identically

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

tests/decompiler_fixtures/src/22_dijkstra.c source 
#include <limits.h>
#include <stdint.h>

__attribute__((noinline)) int32_t dijkstra_dense(const int32_t *weights,
                                                  int32_t n, int32_t source,
                                                  int32_t *distance) {
    uint8_t used[16] = {0};
    int32_t iteration;
    int32_t i;
    if (weights == 0 || distance == 0 || n <= 0 || n > 4 || source < 0 ||
        source >= n) {
        return 0;
    }
    for (i = 0; i < n; ++i) {
        distance[i] = INT_MAX;
    }
    distance[source] = 0;
    for (iteration = 0; iteration < n; ++iteration) {
        int32_t best = -1;
        for (i = 0; i < n; ++i) {
            if (used[i] == 0 &&
                (best < 0 || distance[i] < distance[best])) {
                best = i;
            }
        }
        if (best < 0 || distance[best] == INT_MAX) {
            break;
        }
        used[best] = 1;
        for (i = 0; i < n; ++i) {
            int32_t weight = weights[best * n + i];
            if (weight > 0 && used[i] == 0 &&
                weight <= INT_MAX - distance[best] &&
                distance[best] + weight < distance[i]) {
                distance[i] = distance[best] + weight;
            }
        }
    }
    return distance[n - 1];
}

Recovered C

Generated by glaurung decompile --style decbench at b47f6b43. baseline.json records the result after recompiling the C and calling it beside the original with seeded inputs.

clang -O0

1/1
dijkstra_dense pass 101 lines 
// glaurung: dijkstra_dense @ 0x1110
__attribute__((no_stack_protector)) int32_t dijkstra_dense(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    extern void * memset(void *, int, __SIZE_TYPE__);
    int i;
    int iteration;
    int best;
    int weight;
    unsigned char local_30[16];
    int local_4;
    void * var1;
    long var44;
    var1 = memset((void *)(&local_30[0]), 0, (__SIZE_TYPE__)(16));
    if ((arg0 != 0)) {
        if ((arg3 != 0)) {
            if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
                if (((((unsigned long)((unsigned int)(arg1)) == 4) | ((long)(arg1) < 4)) != 0)) {
                    if ((0 <= (long)(arg2))) {
                        if ((arg2 < arg1)) {
                            goto L_1182;
                        }
                    }
                }
            }
        }
    }
    local_4 = 0;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1182: ;
    i = 0;
    L_1189: ;
    if ((i < arg1)) {
        arg3[(long)(i)] = 0x7fffffff;
        i = ((unsigned int)(i) + 1);
        goto L_1189;
    }
    arg3[(long)(arg2)] = 0;
    iteration = 0;
    L_11c8: ;
    if ((arg1 <= iteration)) {
        goto L_132b;
    }
    best = -1;
    i = 0;
    L_11e2: ;
    if ((arg1 <= i)) {
        goto L_123f;
    }
    if (((unsigned long)((unsigned int)((unsigned char)(*(char *)((&local_30[0] + (long)(i)))))) != 0)) {
        goto L_122c;
    }
    if ((0 <= (long)(best))) {
        if (((long)((int)(arg3[(long)(best)])) <= (long)((int)(arg3[(long)(i)])))) {
            goto L_122c;
        }
    }
    best = i;
    L_122c: ;
    goto L_1231;
    L_1231: ;
    i = ((unsigned int)(i) + 1);
    goto L_11e2;
    L_123f: ;
    if ((0 <= (long)(best))) {
        if (((unsigned long)((unsigned int)(arg3[(long)(best)])) != 0x7fffffff)) {
            goto L_1263;
        }
    }
    goto L_132b;
    L_1263: ;
    *(signed char *)((&local_30[0] + (long)(best))) = 1;
    i = 0;
    L_1273: ;
    if ((arg1 <= i)) {
        goto L_1318;
    }
    weight = arg0[(long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(best)) * arg1))) + i)))];
    if (((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) == 0)) {
        if (((unsigned long)((unsigned int)((unsigned char)(*(char *)((&local_30[0] + (long)(i)))))) == 0)) {
            var44 = (unsigned long)((unsigned int)((0x7fffffff - arg3[(long)(best)])));
            if (((((unsigned int)(weight) == (unsigned int)(var44)) | ((long)(weight) < (long)((int)(var44)))) != 0)) {
                if (((long)((int)(((unsigned long)((unsigned int)(arg3[(long)(best)])) + weight))) < (long)((int)(arg3[(long)(i)])))) {
                    arg3[(long)(i)] = ((unsigned long)((unsigned int)(arg3[(long)(best)])) + weight);
                }
            }
        }
    }
    goto L_130a;
    L_130a: ;
    i = ((unsigned int)(i) + 1);
    goto L_1273;
    L_1318: ;
    goto L_131d;
    L_131d: ;
    iteration = ((unsigned int)(iteration) + 1);
    goto L_11c8;
    L_132b: ;
    local_4 = arg3[(long)((int)(((unsigned long)((unsigned int)(arg1)) - 1)))];
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

1/1
dijkstra_dense pass 164 lines 
// glaurung: dijkstra_dense @ 0x1100
__attribute__((no_stack_protector)) int32_t dijkstra_dense(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    int best;
    int i;
    int weight;
    int iteration;
    unsigned char local_28[40];
    long ret;
    long var10;
    long var13;
    int var15;
    long var21;
    long var23;
    long var24;
    long var28;
    long var32;
    long var35;
    long var37;
    int var41;
    long var42;
    long var44;
    long var7;
    // x86-64 prologue: save callee registers, frame 24 bytes
    *(int *)(&local_28[0]) = 0;
    *(int *)((&local_28[0] + 4)) = 0;
    *(int *)((&local_28[0] + 8)) = 0;
    *(int *)((&local_28[0] + 12)) = 0;
    ret = 0;
    if ((arg1 <= arg2)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if (((long)(arg2) < 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if (((unsigned long)((unsigned long)((unsigned int)((arg1 - 5)))) < (unsigned long)(0xfffffffc))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg3 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    *(int *)(((long)arg3)) = 0x7fffffff;
    if (((unsigned long)((unsigned int)(arg1)) != 1)) {
        *(int *)(((long)arg3 + 0x4)) = 0x7fffffff;
        if (((unsigned long)((unsigned int)(arg1)) != 2)) {
            *(int *)(((long)arg3 + 0x8)) = 0x7fffffff;
            if (((unsigned long)((unsigned int)(arg1)) != 3)) {
                *(int *)(((long)arg3 + 0xc)) = 0x7fffffff;
            }
        }
    }
    arg3[(long)(arg2)] = 0;
    var7 = (unsigned long)((unsigned int)(arg1));
    var10 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) & -2)));
    var13 = 0;
    goto L_118d;
    L_1180: ;
    var15 = (var13 + 1);
    var13 = (unsigned long)((unsigned int)(var15));
    if (((unsigned int)(var15) == (unsigned int)(arg1))) {
        // x86-64 epilogue: restore callee registers
        return (unsigned int)(arg3[(unsigned long)((unsigned int)((arg1 - 1)))]);
    }
    L_118d: ;
    var21 = 0;
    best = 0xffffffff;
    var23 = 0;
    var24 = 0xffffffff;
    if (((unsigned long)((unsigned int)(arg1)) != 1)) {
        goto L_1240;
    }
    L_119d: ;
    if (((unsigned long)((unsigned char)((var7 & 1))) == 0)) {
        goto L_11c0;
    }
    if (((unsigned long)((unsigned char)(*(char *)((&local_28[0] + var21)))) != 0)) {
        goto L_11c0;
    }
    if ((0 <= (long)(best))) {
        if (((long)((int)(arg3[(unsigned long)((unsigned int)(best))])) <= (long)((int)(*(int *)(((long)arg3 + var21 * 4)))))) {
            goto L_11c0;
        }
    }
    best = (unsigned long)((unsigned int)(var21));
    L_11c0: ;
    if (((long)(best) < 0)) {
        // x86-64 epilogue: restore callee registers
        return (unsigned int)(arg3[(unsigned long)((unsigned int)((arg1 - 1)))]);
    }
    var28 = (unsigned long)((unsigned int)(best));
    if (((unsigned long)((unsigned int)(arg3[(unsigned long)((unsigned int)(best))])) == 0x7fffffff)) {
        // x86-64 epilogue: restore callee registers
        return (unsigned int)(arg3[(unsigned long)((unsigned int)((arg1 - 1)))]);
    }
    *(signed char *)((&local_28[0] + var28)) = 1;
    var32 = (long)(((long)arg0 + ((long)((int)((best * arg1))) * 4)));
    var35 = 0;
    goto L_11f9;
    L_11f0: ;
    i = (var35 + 1);
    var35 = (unsigned long)((unsigned int)(i));
    if ((var7 == i)) {
        goto L_1180;
    }
    L_11f9: ;
    weight = (unsigned long)((unsigned int)(*(int *)((var32 + var35 * 4))));
    if ((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0))) {
        goto L_11f0;
    }
    if (((unsigned long)((unsigned char)(*(char *)((&local_28[0] + var35)))) != 0)) {
        goto L_11f0;
    }
    var37 = (unsigned long)((unsigned int)(*(int *)(((long)arg3 + var28 * 4))));
    if (((unsigned long)((unsigned long)((unsigned int)((0x7fffffff - var37)))) < (unsigned long)((unsigned long)((unsigned int)(weight))))) {
        goto L_11f0;
    }
    var41 = (var37 + weight);
    var42 = (unsigned long)((unsigned int)(var41));
    if (((long)((int)(*(int *)(((long)arg3 + var35 * 4)))) <= (long)((int)(var41)))) {
        goto L_11f0;
    }
    *(int *)(((long)arg3 + var35 * 4)) = var42;
    goto L_11f0;
    L_1230: ;
    best = (unsigned long)((unsigned int)((var23 + 1)));
    L_1233: ;
    var44 = (var23 + 2);
    var21 = var44;
    var23 = var44;
    var24 = (unsigned long)((unsigned int)(best));
    if ((var10 == var44)) {
        goto L_119d;
    }
    L_1240: ;
    best = var24;
    if (((unsigned long)((unsigned char)(*(char *)((&local_28[0] + var23)))) != 0)) {
        goto L_1257;
    }
    if ((0 <= (long)((int)(var24)))) {
        best = var24;
        if (((long)((int)(arg3[(unsigned long)((unsigned int)(var24))])) <= (long)((int)(*(int *)(((long)arg3 + var23 * 4)))))) {
            goto L_1257;
        }
    }
    best = (unsigned long)((unsigned int)(var23));
    L_1257: ;
    if (((unsigned long)((unsigned char)(*(char *)((&local_28[0] + (var23 + 1))))) != 0)) {
        goto L_1233;
    }
    if (((long)(best) < 0)) {
        goto L_1230;
    }
    if (((long)((int)(*(int *)(((long)arg3 + var23 * 4 + 0x4)))) < (long)((int)(arg3[(unsigned long)((unsigned int)(best))])))) {
        goto L_1230;
    }
    goto L_1233;
}

gcc -O0

1/1
dijkstra_dense pass 57 lines 
// glaurung: dijkstra_dense @ 0x1119
int32_t dijkstra_dense(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int i;
    int iteration;
    int best;
    int weight;
    unsigned char local_20[16];
    long local_8;
    long ret;
    long var65;
    // x86-64 prologue: save rbp, frame 80 bytes
    local_8 = (long)(0x28);
    *(long *)(&local_20[0]) = 0;
    *(long *)((&local_20[0] + 8)) = 0;
    if (((((((arg0 == 0) || (arg3 == 0)) || (((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0))) || ((((unsigned long)((unsigned int)(arg1)) == 4) | ((long)(arg1) < 4)) == 0)) || ((long)(arg2) < 0)) || (arg1 <= arg2))) {
        ret = 0;
    } else {
        for (i = 0; (i < arg1); i++) {
            arg3[(long)(i)] = 0x7fffffff;
        }
        arg3[(long)(arg2)] = 0;
        iteration = 0;
        while ((iteration < arg1)) {
            best = -1;
            for (i = 0; (i < arg1); i++) {
                if ((((unsigned long)((unsigned char)(((unsigned int)((unsigned char)(*(char *)((&local_20[0] + (long)(i))))) & 255))) == 0) && (((long)(best) < 0) || ((long)((int)(arg3[(long)(i)])) < (long)((int)(arg3[(long)(best)])))))) {
                    best = i;
                }
            }
            if ((((long)(best) < 0) || ((unsigned long)((unsigned int)(arg3[(long)(best)])) == 0x7fffffff))) {
                break;
            }
            *(signed char *)((&local_20[0] + (long)(best))) = 1;
            for (i = 0; (i < arg1); i++) {
                weight = arg0[(long)((int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(best)) * arg1))))))];
                if (((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) == 0)) {
                    if (((unsigned long)((unsigned char)(((unsigned int)((unsigned char)(*(char *)((&local_20[0] + (long)(i))))) & 255))) == 0)) {
                        var65 = (unsigned long)((unsigned int)((0x7fffffff - (unsigned long)((unsigned int)(arg3[(long)(best)])))));
                        if (((((unsigned int)(weight) == (unsigned int)(var65)) | ((long)(weight) < (long)((int)(var65)))) != 0)) {
                            if (((long)((int)(((unsigned long)((unsigned int)(arg3[(long)(best)])) + (unsigned long)((unsigned int)(weight))))) < (long)((int)(arg3[(long)(i)])))) {
                                arg3[(long)(i)] = ((unsigned long)((unsigned int)(weight)) + (unsigned long)((unsigned int)(arg3[(long)(best)])));
                            }
                        }
                    }
                }
            }
            iteration = (iteration + 1);
        }
        ret = (unsigned long)((unsigned int)(*(int *)(((long)arg3 + (((long)(arg1) << 2) - 4)))));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}

gcc -O2

1/1
dijkstra_dense pass 159 lines 
// glaurung: dijkstra_dense @ 0x1120
int32_t dijkstra_dense(const int32_t * arg0, int32_t arg1, int32_t arg2, int32_t * arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int best;
    int i;
    int weight;
    int iteration;
    long local_20;
    unsigned char local_38[16];
    long ret;
    long var12;
    long var13;
    int var20;
    long var21;
    long var22;
    long var24;
    int var25;
    long var26;
    long var27;
    long var28;
    long var32;
    long var33;
    long var36;
    long var37;
    long var38;
    long var39;
    long var45;
    long var48;
    long var5;
    int var52;
    long var53;
    int var54;
    long var55;
    long var8;
    var5 = (long)arg0;
    local_20 = (long)(0x28);
    ret = 0;
    *(int *)(&local_38[0]) = 0;
    *(int *)((&local_38[0] + 4)) = 0;
    *(int *)((&local_38[0] + 8)) = 0;
    *(int *)((&local_38[0] + 12)) = 0;
    if ((arg0 == 0)) {
        goto L_1250;
    }
    var8 = (long)arg3;
    if ((arg3 == 0)) {
        goto L_1250;
    }
    if (((unsigned long)(3) < (unsigned long)((unsigned long)((unsigned int)((arg1 - 1)))))) {
        goto L_1252;
    }
    if (((long)(arg2) < 0)) {
        goto L_1250;
    }
    if ((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2))) {
        goto L_1250;
    }
    var12 = 0;
    do {
        *(int *)((var8 + var12 * 4)) = 0x7fffffff;
        var13 = (var12 + 1);
        var12 = var13;
    } while (((((unsigned int)(arg1) == (unsigned int)(var13)) | ((long)(arg1) < (long)((int)(var13)))) == 0));
    *(int *)((var8 + ((long)(arg2) * 4))) = 0;
    var20 = 0x7fffffff;
    var21 = 0;
    var22 = 0;
    L_11a0: ;
    var24 = 0;
    var25 = 0xffffffff;
    var26 = 0xffffffff;
    if (((unsigned long)((unsigned char)((var22 & 255))) != 0)) {
        goto L_11bc;
    }
    var27 = var24;
    var28 = (unsigned long)((unsigned int)(var25));
    if (((unsigned long)((unsigned int)(var25)) == 0xffffffff)) {
        goto L_11d2;
    }
    L_11b0: ;
    var24 = var27;
    var26 = (((long)((int)(*(int *)((var8 + var27 * 4)))) < (long)((int)(*(int *)((var8 + ((long)((int)(var28)) * 4)))))) ? var27 : var28);
    L_11bc: ;
    var32 = (var24 + 1);
    var24 = var32;
    var33 = var26;
    best = var26;
    if ((((unsigned int)(arg1) == (unsigned int)(var32)) | ((long)(arg1) < (long)((int)(var32))))) {
        goto L_11dc;
    }
    L_11c4: ;
    var26 = var33;
    if (((unsigned long)((unsigned char)(((unsigned int)((unsigned char)(*(char *)((&local_38[0] + var24)))) & 255))) != 0)) {
        goto L_11bc;
    }
    var27 = var24;
    var28 = var33;
    if (((unsigned long)((unsigned int)(var33)) != 0xffffffff)) {
        goto L_11b0;
    }
    L_11d2: ;
    var36 = (unsigned long)((unsigned int)(var24));
    var37 = (var24 + 1);
    var24 = var37;
    var33 = var36;
    best = var36;
    if (((((unsigned int)(arg1) == (unsigned int)(var37)) | ((long)(arg1) < (long)((int)(var37)))) == 0)) {
        goto L_11c4;
    }
    L_11dc: ;
    if (((unsigned long)((unsigned int)(best)) == 0xffffffff)) {
        goto L_1270;
    }
    var38 = (long)(best);
    var39 = (var8 + ((long)(best) * 4));
    if (((unsigned long)((unsigned int)(*(int *)((var39)))) == 0x7fffffff)) {
        goto L_1270;
    }
    *(signed char *)((&local_38[0] + var38)) = 1;
    var45 = (var5 + ((long)((int)((best * arg1))) * 4));
    i = 0;
    do {
        weight = (unsigned long)((unsigned int)(*(int *)((var45 + i * 4))));
        if (((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) == 0)) {
            if (((unsigned long)((unsigned char)(*(char *)((&local_38[0] + i)))) == 0)) {
                var48 = (unsigned long)((unsigned int)(*(int *)((var39))));
                if (((long)(weight) <= (long)((int)(((unsigned long)((unsigned int)(var20)) - var48))))) {
                    var52 = (var48 + weight);
                    var53 = (unsigned long)((unsigned int)(var52));
                    if (((long)((int)(var52)) < (long)((int)(*(int *)((var8 + i * 4)))))) {
                        *(int *)((var8 + i * 4)) = var53;
                    }
                }
            }
        }
        i = (i + 1);
    } while (((((unsigned int)(arg1) == (unsigned int)(i)) | (arg1 < i)) == 0));
    var54 = (var21 + 1);
    var55 = (unsigned long)((unsigned int)(var54));
    if (((unsigned int)(arg1) == (unsigned int)(var54))) {
        goto L_1270;
    }
    var21 = var55;
    var22 = (unsigned int)((unsigned char)(*(char *)(&local_38[0])));
    goto L_11a0;
    L_1250: ;
    ret = 0;
    L_1252: ;
    if ((local_20 != 0x28)) {
        goto L_1279;
    }
    // x86-64 epilogue: tear down frame
    return ret;
    L_1270: ;
    ret = (unsigned long)((unsigned int)(*(int *)(((var8 + ((long)(arg1) * 4)) - 4))));
    goto L_1252;
    L_1279: ;
    __stack_chk_fail();
}

← 213 fixtures