glaurung

Fixture 17

hash table

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

#define HASH_EMPTY INT32_MIN

static uint32_t hash_slot(int32_t key, int32_t capacity) {
    return ((uint32_t)key * 2654435761u) % (uint32_t)capacity;
}

__attribute__((noinline)) int32_t hash_lookup(const int32_t *keys,
                                               const int32_t *values,
                                               int32_t capacity, int32_t key) {
    uint32_t start;
    int32_t probe;
    if (keys == 0 || values == 0 || capacity <= 0 || capacity > 16 ||
        key == HASH_EMPTY) {
        return -1;
    }
    start = hash_slot(key, capacity);
    for (probe = 0; probe < capacity; ++probe) {
        uint32_t slot = (start + (uint32_t)probe) % (uint32_t)capacity;
        if (keys[slot] == HASH_EMPTY) {
            return -1;
        }
        if (keys[slot] == key) {
            return values[slot];
        }
    }
    return -1;
}

__attribute__((noinline)) int32_t hash_insert(int32_t *keys, int32_t *values,
                                               int32_t capacity, int32_t key,
                                               int32_t value) {
    uint32_t start;
    int32_t probe;
    if (keys == 0 || values == 0 || capacity <= 0 || capacity > 16 ||
        key == HASH_EMPTY) {
        return -1;
    }
    start = hash_slot(key, capacity);
    for (probe = 0; probe < capacity; ++probe) {
        uint32_t slot = (start + (uint32_t)probe) % (uint32_t)capacity;
        if (keys[slot] == HASH_EMPTY || keys[slot] == key) {
            keys[slot] = key;
            values[slot] = value;
            return (int32_t)slot;
        }
    }
    return -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

2/2
hash_insert pass 51 lines 
// glaurung: hash_insert @ 0x1210
int32_t hash_insert(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4) {
    extern unsigned int hash_slot(int, int);
    unsigned int start;
    int probe;
    unsigned int slot;
    int local_4;
    unsigned int var0;
    if ((arg0 != 0)) {
        if ((arg1 != 0)) {
            if (((((unsigned long)((unsigned int)(arg2)) == 0) | ((long)(arg2) < 0)) == 0)) {
                if (((((unsigned long)((unsigned int)(arg2)) == 16) | ((long)(arg2) < 16)) != 0)) {
                    if (((unsigned long)((unsigned int)(arg3)) != 0x80000000)) {
                        goto L_126d;
                    }
                }
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_126d: ;
    var0 = hash_slot((unsigned long)((unsigned int)(arg3)), (unsigned long)((unsigned int)(arg2)));
    start = var0;
    probe = 0;
    L_1282: ;
    if ((arg2 <= probe)) {
        goto L_12fb;
    }
    slot = ((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((unsigned long)((unsigned int)((start + probe))))) % (unsigned int)(arg2))));
    if (((unsigned long)((unsigned int)(arg0[slot])) != 0x80000000)) {
        if (((unsigned int)(arg0[slot]) != (unsigned int)(arg3))) {
            goto L_12e8;
        }
    }
    arg0[slot] = arg3;
    arg1[slot] = arg4;
    local_4 = slot;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_12e8: ;
    goto L_12ed;
    L_12ed: ;
    probe = ((unsigned int)(probe) + 1);
    goto L_1282;
    L_12fb: ;
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
hash_lookup pass 50 lines 
// glaurung: hash_lookup @ 0x1100
int32_t hash_lookup(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    extern unsigned int hash_slot(int, int);
    unsigned int start;
    int probe;
    unsigned int slot;
    int local_4;
    unsigned int var0;
    if ((arg0 != 0)) {
        if ((arg1 != 0)) {
            if (((((unsigned long)((unsigned int)(arg2)) == 0) | ((long)(arg2) < 0)) == 0)) {
                if (((((unsigned long)((unsigned int)(arg2)) == 16) | ((long)(arg2) < 16)) != 0)) {
                    if (((unsigned long)((unsigned int)(arg3)) != 0x80000000)) {
                        goto L_1159;
                    }
                }
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1159: ;
    var0 = hash_slot((unsigned long)((unsigned int)(arg3)), (unsigned long)((unsigned int)(arg2)));
    start = var0;
    probe = 0;
    L_116e: ;
    if ((arg2 <= probe)) {
        goto L_11e0;
    }
    slot = ((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((unsigned long)((unsigned int)((start + probe))))) % (unsigned int)(arg2))));
    if (((unsigned long)((unsigned int)(arg0[slot])) == 0x80000000)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((unsigned int)(arg0[slot]) == (unsigned int)(arg3))) {
        local_4 = arg1[slot];
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    goto L_11d2;
    L_11d2: ;
    probe = ((unsigned int)(probe) + 1);
    goto L_116e;
    L_11e0: ;
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

2/2
hash_insert pass 58 lines 
// glaurung: hash_insert @ 0x1170
int32_t hash_insert(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4) {
    unsigned int start;
    unsigned int slot;
    int probe;
    long local_10;
    long var0;
    long var1;
    long var14;
    long var15;
    long var21;
    int var23;
    long var4;
    local_10 = var0;
    var1 = 0xffffffff;
    if (((unsigned long)((unsigned int)(arg3)) == 0x80000000)) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var1);
    }
    if ((arg0 == 0)) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var1);
    }
    if ((arg1 == 0)) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var1);
    }
    var4 = (unsigned long)((unsigned int)(arg2));
    if (((unsigned long)((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg2)) - 17)))) < (unsigned long)(0xfffffff0))) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var1);
    }
    start = (unsigned long)((unsigned int)(((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((arg3 * -0x61c8864fLL))) % (unsigned int)(var4))))));
    var14 = (unsigned long)((unsigned int)(var4));
    var15 = 0;
    L_11b0: ;
    while (1) {
        slot = ((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((unsigned long)((unsigned int)((var15 + start))))) % (unsigned int)(var4))));
        var21 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + slot * 4))));
        if ((((unsigned long)((unsigned int)(var21)) == 0x80000000) || ((unsigned int)(var21) == (unsigned int)(arg3)))) {
            break;
        }
        var15 = (unsigned long)((unsigned int)((var15 + 1)));
        var23 = (var14 - 1);
        var14 = (unsigned long)((unsigned int)(var23));
        if (((unsigned long)((unsigned int)(var23)) != 0)) {
            goto L_11b0;
        } else {
        }
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var1);
    }
    arg0[slot] = arg3;
    arg1[slot] = arg4;
    var1 = (unsigned long)(slot);
    // x86-64 epilogue: tear down frame
    return slot;
}
hash_lookup pass 51 lines 
// glaurung: hash_lookup @ 0x1100
int32_t hash_lookup(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    unsigned int start;
    unsigned int slot;
    int probe;
    long var0;
    long var1;
    long var11;
    long var12;
    long var18;
    int var20;
    var0 = 0xffffffff;
    if (((unsigned long)((unsigned int)(arg3)) == 0x80000000)) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var0);
    }
    if ((arg0 == 0)) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var0);
    }
    if ((arg1 == 0)) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var0);
    }
    var1 = (unsigned long)((unsigned int)(arg2));
    if (((unsigned long)((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg2)) - 17)))) < (unsigned long)(0xfffffff0))) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var0);
    }
    start = (unsigned long)((unsigned int)(((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((arg3 * -0x61c8864fLL))) % (unsigned int)(var1))))));
    var11 = (unsigned long)((unsigned int)(var1));
    var12 = 0;
    do {
        slot = ((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((unsigned long)((unsigned int)((var12 + start))))) % (unsigned int)(var1))));
        var18 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + slot * 4))));
        if (((unsigned long)((unsigned int)(var18)) == 0x80000000)) {
            // x86-64 epilogue: tear down frame
            return (unsigned int)(var0);
        }
        if (((unsigned int)(var18) == (unsigned int)(arg3))) {
            var0 = (unsigned long)((unsigned int)(arg1[slot]));
            // x86-64 epilogue: tear down frame
            return (unsigned int)(var0);
        }
        var12 = (unsigned long)((unsigned int)((var12 + 1)));
        var20 = (var11 - 1);
        var11 = (unsigned long)((unsigned int)(var20));
    } while (((unsigned long)((unsigned int)(var20)) != 0));
    // x86-64 epilogue: tear down frame
    return (unsigned int)(var0);
}

gcc -O0

2/2
hash_insert pass 45 lines 
// glaurung: hash_insert @ 0x11f9
int32_t hash_insert(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4) {
    extern unsigned int hash_slot(int, int);
    unsigned int start;
    int probe;
    unsigned int slot;
    unsigned int var2;
    if ((arg0 != 0)) {
        if ((arg1 != 0)) {
            if (((((unsigned long)((unsigned int)(arg2)) == 0) | ((long)(arg2) < 0)) == 0)) {
                if (((((unsigned long)((unsigned int)(arg2)) == 16) | ((long)(arg2) < 16)) != 0)) {
                    if (((unsigned long)((unsigned int)(arg3)) != 0x80000000)) {
                        goto L_1244;
                    }
                }
            }
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_1244: ;
    var2 = hash_slot((unsigned long)((unsigned int)(arg3)), (unsigned long)((unsigned int)(arg2)));
    start = var2;
    probe = 0;
    goto L_12e2;
    L_1262: ;
    slot = ((unsigned int)(((((unsigned long long)(unsigned int)(0) << 32) | (unsigned int)((unsigned long)((unsigned int)((start + (unsigned long)((unsigned int)(probe))))))) % (unsigned int)((unsigned long)((unsigned int)(arg2))))));
    if (((unsigned long)((unsigned int)(arg0[slot])) != 0x80000000)) {
        if (((unsigned int)(arg3) != (unsigned int)(arg0[slot]))) {
            goto L_12de;
        }
    }
    arg0[slot] = arg3;
    arg1[slot] = arg4;
    // x86-64 epilogue: restore rbp
    return slot;
    L_12de: ;
    probe = (probe + 1);
    L_12e2: ;
    if ((probe < arg2)) {
        goto L_1262;
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
}
hash_lookup pass 43 lines 
// glaurung: hash_lookup @ 0x111e
int32_t hash_lookup(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    extern unsigned int hash_slot(int, int);
    unsigned int start;
    int probe;
    unsigned int slot;
    unsigned int var2;
    if ((arg0 != 0)) {
        if ((arg1 != 0)) {
            if (((((unsigned long)((unsigned int)(arg2)) == 0) | ((long)(arg2) < 0)) == 0)) {
                if (((((unsigned long)((unsigned int)(arg2)) == 16) | ((long)(arg2) < 16)) != 0)) {
                    if (((unsigned long)((unsigned int)(arg3)) != 0x80000000)) {
                        goto L_1165;
                    }
                }
            }
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_1165: ;
    var2 = hash_slot((unsigned long)((unsigned int)(arg3)), (unsigned long)((unsigned int)(arg2)));
    start = var2;
    probe = 0;
    goto L_11ea;
    L_1180: ;
    slot = ((unsigned int)(((((unsigned long long)(unsigned int)(0) << 32) | (unsigned int)((unsigned long)((unsigned int)((start + (unsigned long)((unsigned int)(probe))))))) % (unsigned int)((unsigned long)((unsigned int)(arg2))))));
    if (((unsigned long)((unsigned int)(arg0[slot])) == 0x80000000)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((unsigned int)(arg3) == (unsigned int)(arg0[slot]))) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(arg1[(unsigned long)(slot)]);
    }
    probe = (probe + 1);
    L_11ea: ;
    if ((probe < arg2)) {
        goto L_1180;
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
}

gcc -O2

2/2
hash_insert pass 57 lines 
// glaurung: hash_insert @ 0x1180
int32_t hash_insert(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4) {
    unsigned int start;
    int probe;
    unsigned int slot;
    long local_10;
    long var0;
    int var12;
    long var2;
    long var21;
    long var22;
    long var23;
    int var24;
    long var3;
    long var7;
    long var8;
    if ((arg0 == 0)) {
        return 0xffffffff;
    }
    var0 = (long)arg1;
    if ((arg1 == 0)) {
        return 0xffffffff;
    }
    var2 = (unsigned long)((unsigned int)(arg2));
    if (((unsigned long)(15) < (unsigned long)((unsigned long)((unsigned int)((arg2 - 1)))))) {
        return 0xffffffff;
    }
    var3 = (unsigned long)((unsigned int)(arg3));
    if (((unsigned long)((unsigned int)(arg3)) == 0x80000000)) {
        return 0xffffffff;
    }
    var7 = (long)arg0;
    local_10 = var8;
    var12 = ((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((arg3 * -0x61c8864fLL))) % (unsigned int)((unsigned long)((unsigned int)(arg2))))));
    start = (unsigned long)((unsigned int)(var12));
    probe = 0;
    slot = var12;
    while (1) {
        slot = ((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((unsigned long)((unsigned int)((probe + start))))) % (unsigned int)(var2))));
        var21 = ((unsigned long)(slot) << 2);
        var22 = (var7 + var21);
        var23 = (unsigned long)((unsigned int)(*(int *)((var22))));
        if ((((unsigned int)(var23) == (unsigned int)(var3)) || ((unsigned long)((unsigned int)(var23)) == 0x80000000))) {
            break;
        }
        var24 = (probe + 1);
        probe = (unsigned long)((unsigned int)(var24));
        if (((((unsigned int)(var2) == (unsigned int)(var24)) | ((long)((int)(var2)) < (long)((int)(var24)))) != 0)) {
            // x86-64 epilogue: tear down frame
            return 0xffffffff;
        }
    }
    *(int *)((var22)) = var3;
    *(int *)((var0 + var21)) = arg4;
    // x86-64 epilogue: tear down frame
    return slot;
}
hash_lookup pass 48 lines 
// glaurung: hash_lookup @ 0x1100
int32_t hash_lookup(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    unsigned int start;
    int probe;
    long var0;
    long var1;
    int var11;
    long var18;
    long var19;
    long var2;
    int var20;
    long var3;
    var0 = (long)arg0;
    var1 = (long)arg1;
    var2 = (unsigned long)((unsigned int)(arg3));
    var3 = (unsigned long)((unsigned int)(arg2));
    if ((arg0 != 0)) {
        if ((arg1 == 0)) {
            return 0xffffffff;
        }
        if (((unsigned long)(15) < (unsigned long)((unsigned long)((unsigned int)((arg2 - 1)))))) {
            return 0xffffffff;
        }
        if (((unsigned long)((unsigned int)(arg3)) == 0x80000000)) {
            return 0xffffffff;
        }
        var11 = ((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((arg3 * -0x61c8864fLL))) % (unsigned int)((unsigned long)((unsigned int)(arg2))))));
        start = (unsigned long)((unsigned int)(var11));
        probe = 0;
        while (1) {
            var11 = ((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)((unsigned long)((unsigned int)((probe + start))))) % (unsigned int)(var3))));
            var18 = (unsigned long)((unsigned int)(*(int *)((var0 + var11 * 4))));
            var19 = ((unsigned long)((unsigned int)(var11)) * 4);
            if (((unsigned long)((unsigned int)(var18)) == 0x80000000)) {
                break;
            }
            if (((unsigned int)(var18) == (unsigned int)(var2))) {
                return (unsigned int)(*(int *)((var1 + var19)));
            }
            var20 = (probe + 1);
            probe = (unsigned long)((unsigned int)(var20));
            if (((((unsigned int)(var3) == (unsigned int)(var20)) | ((long)((int)(var3)) < (long)((int)(var20)))) != 0)) {
                break;
            }
        }
    }
    return 0xffffffff;
}

← 213 fixtures