Fixture 80
trie
C · 2 functions · 4 lanes · 8 of 8 function-lanes behave identically
All 4 lanes recompile and return the same results as the original.
A four-way prefix tree over a flat node array (symbols 'a'..'d'). Children are indices, not pointers, so insertion allocates by bumping a cursor and lookup is a chain of dependent loads -- pointer-chasing without a heap.
#include <stdint.h>
/* A four-way prefix tree over a flat node array (symbols 'a'..'d'). Children
* are indices, not pointers, so insertion allocates by bumping a cursor and
* lookup is a chain of dependent loads -- pointer-chasing without a heap. */
#define TRIE_NODES 24
#define TRIE_FANOUT 4
__attribute__((noinline)) int32_t
trie_insert(int32_t *children, uint8_t *terminal, int32_t *cursor,
const uint8_t *word, int32_t length) {
int32_t node = 0;
int32_t index;
if (children == 0 || terminal == 0 || cursor == 0 || word == 0 ||
length < 0 || length > 8 || *cursor < 1 || *cursor > TRIE_NODES) {
return -1;
}
for (index = 0; index < length; ++index) {
int32_t symbol = (int32_t)word[index] - 'a';
int32_t slot;
if (symbol < 0 || symbol >= TRIE_FANOUT) {
return -2;
}
slot = node * TRIE_FANOUT + symbol;
if (children[slot] == 0) {
if (*cursor >= TRIE_NODES) {
return -3;
}
children[slot] = *cursor;
*cursor = *cursor + 1;
}
node = children[slot];
}
terminal[node] = 1;
return node;
}
__attribute__((noinline)) int32_t
trie_lookup(const int32_t *children, const uint8_t *terminal,
const uint8_t *word, int32_t length) {
int32_t node = 0;
int32_t index;
if (children == 0 || terminal == 0 || word == 0 || length < 0 ||
length > 8) {
return -1;
}
for (index = 0; index < length; ++index) {
int32_t symbol = (int32_t)word[index] - 'a';
int32_t slot;
if (symbol < 0 || symbol >= TRIE_FANOUT) {
return -2;
}
slot = node * TRIE_FANOUT + symbol;
if (children[slot] == 0) {
return 0;
}
node = children[slot];
}
return terminal[node] ? 1 : 0;
} 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/2trie_insert pass 65 lines
// glaurung: trie_insert @ 0x1100
int32_t trie_insert(int32_t * arg0, uint8_t * arg1, int32_t * arg2, const uint8_t * arg3, int32_t arg4) {
int node;
int index;
int symbol;
int slot;
int local_4;
long t155;
node = 0;
if ((arg0 != 0)) {
if ((arg1 != 0)) {
if ((arg2 != 0)) {
if ((arg3 != 0)) {
if ((0 <= (long)(arg4))) {
if (((((unsigned long)((unsigned int)(arg4)) == 8) | ((long)(arg4) < 8)) != 0)) {
if ((1 <= (long)((int)(*(int *)((long)arg2))))) {
t155 = *(int *)((long)arg2);
if ((((unsigned long)((unsigned int)(t155)) == 24) | ((long)((int)(t155)) < 24))) {
goto L_1185;
}
}
}
}
}
}
}
}
local_4 = -1;
// x86-64 epilogue: restore rbp
return (unsigned int)(local_4);
L_1185: ;
index = 0;
L_118c: ;
if ((arg4 <= index)) {
goto L_123d;
}
symbol = ((unsigned int)((unsigned char)(arg3[index])) - 97);
if ((0 <= (long)(symbol))) {
if (((long)(symbol) < 4)) {
goto L_11ca;
}
}
local_4 = -2;
// x86-64 epilogue: restore rbp
return (unsigned int)(local_4);
L_11ca: ;
slot = ((unsigned int)(((unsigned long)((unsigned int)(node)) << 2)) + symbol);
if (((unsigned long)((unsigned int)(arg0[(long)(slot)])) == 0)) {
if ((24 <= (long)((int)(*(int *)((long)arg2))))) {
local_4 = -3;
// x86-64 epilogue: restore rbp
return (unsigned int)(local_4);
}
arg0[(long)(slot)] = *(int *)((long)arg2);
*(int *)((long)arg2) = ((unsigned long)((unsigned int)(*(int *)((long)arg2))) + 1);
}
node = arg0[(long)(slot)];
index = ((unsigned int)(index) + 1);
goto L_118c;
L_123d: ;
arg1[node] = 1;
local_4 = node;
// x86-64 epilogue: restore rbp
return (unsigned int)(local_4);
} trie_lookup pass 51 lines
// glaurung: trie_lookup @ 0x1260
int32_t trie_lookup(const int32_t * arg0, const uint8_t * arg1, const uint8_t * arg2, int32_t arg3) {
int node;
int index;
int symbol;
int slot;
int local_4;
node = 0;
if ((arg0 != 0)) {
if ((arg1 != 0)) {
if ((arg2 != 0)) {
if ((0 <= (long)(arg3))) {
if ((((unsigned long)((unsigned int)(arg3)) == 8) | ((long)(arg3) < 8))) {
goto L_12bb;
}
}
}
}
}
local_4 = -1;
// x86-64 epilogue: restore rbp
return (unsigned int)(local_4);
L_12bb: ;
index = 0;
L_12c2: ;
if ((arg3 <= index)) {
goto L_1346;
}
symbol = ((unsigned int)((unsigned char)(arg2[index])) - 97);
if ((0 <= (long)(symbol))) {
if (((long)(symbol) < 4)) {
goto L_1300;
}
}
local_4 = -2;
// x86-64 epilogue: restore rbp
return (unsigned int)(local_4);
L_1300: ;
slot = ((unsigned int)(((unsigned long)((unsigned int)(node)) << 2)) + symbol);
if (((unsigned long)((unsigned int)(arg0[(long)(slot)])) == 0)) {
// x86-64 epilogue: restore rbp
return 0;
}
node = arg0[(long)(slot)];
index = ((unsigned int)(index) + 1);
goto L_12c2;
L_1346: ;
local_4 = (((unsigned long)((unsigned int)((unsigned char)(arg1[node]))) != 0) ? 1 : 0);
// x86-64 epilogue: restore rbp
return (unsigned int)(local_4);
} clang -O2
2/2trie_insert pass 88 lines
// glaurung: trie_insert @ 0x1100
int32_t trie_insert(int32_t * arg0, uint8_t * arg1, int32_t * arg2, const uint8_t * arg3, int32_t arg4) {
int node;
int index;
int slot;
long local_8;
long ret;
long var0;
long var1;
long var11;
int var12;
int var15;
long var17;
long var18;
int var20;
long var3;
long var8;
local_8 = var0;
ret = 0xffffffff;
if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg4))))) {
// x86-64 epilogue: tear down frame
return ret;
}
if ((arg0 == 0)) {
// x86-64 epilogue: tear down frame
return ret;
}
if ((arg1 == 0)) {
// x86-64 epilogue: tear down frame
return ret;
}
if ((arg2 == 0)) {
// x86-64 epilogue: tear down frame
return ret;
}
if ((arg3 == 0)) {
// x86-64 epilogue: tear down frame
return ret;
}
var1 = (unsigned long)((unsigned int)(*(int *)(((long)arg2))));
if (((unsigned long)((unsigned long)((unsigned int)((var1 - 25)))) < (unsigned long)(0xffffffe8))) {
// x86-64 epilogue: tear down frame
return ret;
}
if (((unsigned long)((unsigned int)(arg4)) == 0)) {
goto L_1183;
}
var3 = (unsigned long)((unsigned int)(arg4));
var8 = 0;
node = 0;
goto L_1149;
L_1140: ;
index = (var8 + 1);
var8 = (unsigned long)((unsigned int)(index));
var11 = (unsigned long)((unsigned int)(node));
if ((var3 == index)) {
goto L_1185;
}
L_1149: ;
var12 = (unsigned int)((unsigned char)(*(char *)(((long)arg3 + var8))));
if (((unsigned long)((unsigned long)((unsigned char)(((unsigned long)((unsigned int)((var12 - 101))) & 255)))) < (unsigned long)(252))) {
// x86-64 epilogue: tear down frame
return 0xfffffffe;
}
var15 = ((unsigned int)((var12 + (node * 4))) - 97);
var17 = (long)((int)(var15));
var18 = (unsigned long)((unsigned int)(arg0[(long)((int)(var15))]));
node = var18;
if (((unsigned long)((unsigned int)(var18)) != 0)) {
goto L_1140;
}
if (((((unsigned long)((unsigned int)(var1)) == 23) | ((long)((int)(var1)) < 23)) == 0)) {
// x86-64 epilogue: tear down frame
return 0xfffffffd;
}
*(int *)(((long)arg0 + var17 * 4)) = var1;
var20 = ((unsigned int)(*(int *)(((long)arg2))) + 1);
var1 = (unsigned long)((unsigned int)(var20));
*(int *)(((long)arg2)) = var20;
node = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var17 * 4))));
goto L_1140;
L_1183: ;
var11 = 0;
L_1185: ;
arg1[(long)((int)(var11))] = 1;
// x86-64 epilogue: tear down frame
return var11;
} trie_lookup pass 128 lines
// glaurung: trie_lookup @ 0x11a0
int32_t trie_lookup(const int32_t * arg0, const uint8_t * arg1, const uint8_t * arg2, int32_t arg3) {
int node;
int index;
int slot;
long ret;
int var0;
int var14;
int var20;
int var26;
long var3;
int var32;
int var38;
int var44;
int var8;
ret = 0xffffffff;
if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
return ret;
}
if ((arg0 == 0)) {
return ret;
}
if ((arg1 == 0)) {
return ret;
}
if ((arg2 == 0)) {
return ret;
}
if (((unsigned long)((unsigned int)(arg3)) == 0)) {
goto L_11ff;
}
var0 = (unsigned int)((unsigned char)(*(char *)(((long)arg2))));
ret = 0xfffffffe;
if (((unsigned long)((unsigned long)((unsigned char)(((unsigned long)((unsigned int)((var0 - 101))) & 255)))) < (unsigned long)(252))) {
return ret;
}
node = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var0 * 4 - 0x184))));
if (((unsigned long)((unsigned int)(node)) == 0)) {
return 0;
}
if (((unsigned long)((unsigned int)(arg3)) != 1)) {
goto L_120b;
}
L_11fa: ;
var3 = (long)(node);
goto L_1201;
L_11ff: ;
var3 = 0;
L_1201: ;
return ((unsigned long)((unsigned char)(*(char *)(((long)arg1 + var3)))) != 0);
L_120b: ;
var8 = (unsigned int)((unsigned char)(*(char *)(((long)arg2 + 0x1))));
if (((unsigned long)((unsigned long)((unsigned char)(((unsigned long)((unsigned int)((var8 - 101))) & 255)))) < (unsigned long)(252))) {
return ret;
}
node = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)((var8 + (node * 4)))) - 97)))]));
if (((unsigned long)((unsigned int)(node)) == 0)) {
return 0;
}
if (((unsigned long)((unsigned int)(arg3)) == 2)) {
goto L_11fa;
}
var14 = (unsigned int)((unsigned char)(*(char *)(((long)arg2 + 0x2))));
if (((unsigned long)((unsigned long)((unsigned char)(((unsigned long)((unsigned int)((var14 - 101))) & 255)))) < (unsigned long)(252))) {
return ret;
}
node = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)((var14 + (node * 4)))) - 97)))]));
if (((unsigned long)((unsigned int)(node)) == 0)) {
return 0;
}
if (((unsigned long)((unsigned int)(arg3)) == 3)) {
goto L_11fa;
}
var20 = (unsigned int)((unsigned char)(*(char *)(((long)arg2 + 0x3))));
if (((unsigned long)((unsigned long)((unsigned char)(((unsigned long)((unsigned int)((var20 - 101))) & 255)))) < (unsigned long)(252))) {
return ret;
}
node = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)((var20 + (node * 4)))) - 97)))]));
if (((unsigned long)((unsigned int)(node)) == 0)) {
return 0;
}
if (((unsigned long)((unsigned int)(arg3)) == 4)) {
goto L_11fa;
}
var26 = (unsigned int)((unsigned char)(*(char *)(((long)arg2 + 0x4))));
if (((unsigned long)((unsigned long)((unsigned char)(((unsigned long)((unsigned int)((var26 - 101))) & 255)))) < (unsigned long)(252))) {
return ret;
}
node = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)((var26 + (node * 4)))) - 97)))]));
if (((unsigned long)((unsigned int)(node)) == 0)) {
return 0;
}
if (((unsigned long)((unsigned int)(arg3)) == 5)) {
goto L_11fa;
}
var32 = (unsigned int)((unsigned char)(*(char *)(((long)arg2 + 0x5))));
if (((unsigned long)((unsigned long)((unsigned char)(((unsigned long)((unsigned int)((var32 - 101))) & 255)))) < (unsigned long)(252))) {
return ret;
}
node = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)((var32 + (node * 4)))) - 97)))]));
if (((unsigned long)((unsigned int)(node)) == 0)) {
return 0;
}
if (((unsigned long)((unsigned int)(arg3)) == 6)) {
goto L_11fa;
}
var38 = (unsigned int)((unsigned char)(*(char *)(((long)arg2 + 0x6))));
if (((unsigned long)((unsigned long)((unsigned char)(((unsigned long)((unsigned int)((var38 - 101))) & 255)))) < (unsigned long)(252))) {
return ret;
}
node = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)((var38 + (node * 4)))) - 97)))]));
if (((unsigned long)((unsigned int)(node)) == 0)) {
return 0;
}
if (((unsigned long)((unsigned int)(arg3)) == 7)) {
goto L_11fa;
}
var44 = (unsigned int)((unsigned char)(*(char *)(((long)arg2 + 0x7))));
if (((unsigned long)((unsigned long)((unsigned char)(((unsigned long)((unsigned int)((var44 - 101))) & 255)))) < (unsigned long)(252))) {
return ret;
}
node = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)((var44 + (node * 4)))) - 97)))]));
ret = 0;
if (((unsigned long)((unsigned int)(node)) != 0)) {
goto L_11fa;
}
return ret;
} gcc -O0
2/2trie_insert pass 64 lines
// glaurung: trie_insert @ 0x10f9
int32_t trie_insert(int32_t * arg0, uint8_t * arg1, int32_t * arg2, const uint8_t * arg3, int32_t arg4) {
int node;
int index;
int symbol;
int slot;
long t136;
long var24;
long var3;
node = 0;
if ((arg0 != 0)) {
if ((arg1 != 0)) {
if ((arg2 != 0)) {
if ((arg3 != 0)) {
if ((0 <= (long)(arg4))) {
if (((((unsigned long)((unsigned int)(arg4)) == 8) | ((long)(arg4) < 8)) != 0)) {
t136 = (unsigned long)((unsigned int)(*(int *)((long)arg2)));
if (((((unsigned long)((unsigned int)(t136)) == 0) | ((long)((int)(t136)) < 0)) == 0)) {
var3 = (unsigned long)((unsigned int)(*(int *)((long)arg2)));
if ((((unsigned long)((unsigned int)(var3)) == 24) | ((long)((int)(var3)) < 24))) {
goto L_1163;
}
}
}
}
}
}
}
}
// x86-64 epilogue: restore rbp
return 0xffffffff;
L_1163: ;
index = 0;
goto L_1224;
L_116f: ;
symbol = ((unsigned int)((unsigned char)(((unsigned int)((unsigned char)(arg3[index])) & 255))) - 97);
if ((0 <= (long)(symbol))) {
if ((((unsigned long)((unsigned int)(symbol)) == 3) | ((long)(symbol) < 3))) {
goto L_119e;
}
}
// x86-64 epilogue: restore rbp
return 0xfffffffe;
L_119e: ;
slot = ((unsigned int)(symbol) + (unsigned int)(((unsigned long)((unsigned int)(node)) * 4)));
if (((unsigned long)((unsigned int)(arg0[(long)(slot)])) == 0)) {
var24 = (unsigned long)((unsigned int)(*(int *)((long)arg2)));
if (((((unsigned long)((unsigned int)(var24)) == 23) | ((long)((int)(var24)) < 23)) == 0)) {
// x86-64 epilogue: restore rbp
return 0xfffffffd;
}
arg0[(long)(slot)] = *(int *)((long)arg2);
*(int *)((long)arg2) = ((unsigned long)((unsigned int)(*(int *)((long)arg2))) + 1);
}
node = arg0[(long)(slot)];
index = (index + 1);
L_1224: ;
if ((index < arg4)) {
goto L_116f;
}
arg1[node] = 1;
// x86-64 epilogue: restore rbp
return (unsigned int)(node);
} trie_lookup pass 47 lines
// glaurung: trie_lookup @ 0x1245
int32_t trie_lookup(const int32_t * arg0, const uint8_t * arg1, const uint8_t * arg2, int32_t arg3) {
int node;
int index;
int symbol;
int slot;
node = 0;
if ((arg0 != 0)) {
if ((arg1 != 0)) {
if ((arg2 != 0)) {
if ((0 <= (long)(arg3))) {
if ((((unsigned long)((unsigned int)(arg3)) == 8) | ((long)(arg3) < 8))) {
goto L_128e;
}
}
}
}
}
// x86-64 epilogue: restore rbp
return 0xffffffff;
L_128e: ;
index = 0;
goto L_1313;
L_1297: ;
symbol = ((unsigned int)((unsigned char)(((unsigned int)((unsigned char)(arg2[index])) & 255))) - 97);
if ((0 <= (long)(symbol))) {
if ((((unsigned long)((unsigned int)(symbol)) == 3) | ((long)(symbol) < 3))) {
goto L_12c3;
}
}
// x86-64 epilogue: restore rbp
return 0xfffffffe;
L_12c3: ;
slot = ((unsigned int)(symbol) + (unsigned int)(((unsigned long)((unsigned int)(node)) * 4)));
if (((unsigned long)((unsigned int)(arg0[(long)(slot)])) == 0)) {
// x86-64 epilogue: restore rbp
return 0;
}
node = arg0[(long)(slot)];
index = (index + 1);
L_1313: ;
if ((index < arg3)) {
goto L_1297;
}
// x86-64 epilogue: restore rbp
return ((unsigned long)((unsigned char)(((unsigned int)((unsigned char)(arg1[node])) & 255))) != 0);
} gcc -O2
2/2trie_insert pass 83 lines
// glaurung: trie_insert @ 0x1100
int32_t trie_insert(int32_t * arg0, uint8_t * arg1, int32_t * arg2, const uint8_t * arg3, int32_t arg4) {
int symbol;
int index;
int node;
int slot;
int * var0;
long var13;
long var14;
long var15;
long var16;
long var22;
long var24;
long var7;
long var8;
long var9;
var0 = (int *)arg2;
if ((arg0 == 0)) {
goto L_11ba;
}
if ((arg1 == 0)) {
goto L_11ba;
}
if ((arg2 == 0)) {
goto L_11ba;
}
if ((arg3 == 0)) {
goto L_11ba;
}
if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg4))))) {
goto L_11ba;
}
if (((unsigned long)(23) < (unsigned long)((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(*(int *)(((long)arg2)))) - 1)))))) {
goto L_11ba;
}
if (((unsigned long)((unsigned int)(arg4)) == 0)) {
goto L_11c2;
}
var7 = (long)((((long)arg3 + (unsigned long)((unsigned int)((arg4 - 1)))) + 1));
var8 = 0;
var9 = (long)arg3;
goto L_1186;
L_1158: ;
var13 = (long)(((long)arg0 + ((long)((int)((symbol + (var8 * 4)))) * 4)));
var14 = (unsigned long)((unsigned int)(*(int *)((var13))));
var15 = var14;
if (((unsigned long)((unsigned int)(var14)) == 0)) {
var16 = (unsigned long)((unsigned int)(*(int *)((var0))));
if (((((unsigned long)((unsigned int)(var16)) == 23) | ((long)((int)(var16)) < 23)) == 0)) {
goto L_11b0;
}
*(int *)((var13)) = var16;
*(int *)((var0)) = (var16 + 1);
var15 = (unsigned long)((unsigned int)(*(int *)((var13))));
}
var9 = (var9 + 1);
var8 = var15;
if ((var7 == var9)) {
goto L_11a0;
}
L_1186: ;
symbol = (unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)((var9)))) - 97)));
if (((unsigned long)((unsigned long)((unsigned int)(symbol))) <= (unsigned long)(3))) {
goto L_1158;
}
var22 = 0xfffffffe;
L_1197: ;
return (unsigned int)(var22);
L_11a0: ;
var24 = (long)(((long)arg1 + (long)((int)(var15))));
L_11a6: ;
*(signed char *)((var24)) = 1;
return (unsigned int)(var15);
L_11b0: ;
return 0xfffffffd;
L_11ba: ;
var22 = 0xffffffff;
goto L_1197;
L_11c2: ;
var15 = 0;
var24 = (long)arg1;
goto L_11a6;
} trie_lookup pass 56 lines
// glaurung: trie_lookup @ 0x11d0
int32_t trie_lookup(const int32_t * arg0, const uint8_t * arg1, const uint8_t * arg2, int32_t arg3) {
int node;
int symbol;
int index;
int slot;
long var1;
long var2;
long var6;
long var7;
if ((arg0 == 0)) {
goto L_1241;
}
if ((arg1 == 0)) {
goto L_1241;
}
if ((arg2 == 0)) {
goto L_1241;
}
if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
goto L_1241;
}
node = var1;
var2 = (long)arg1;
if (((unsigned long)((unsigned int)(arg3)) == 0)) {
goto L_1233;
}
var6 = (long)((((long)arg2 + (unsigned long)((unsigned int)((arg3 - 1)))) + 1));
node = 0;
var7 = (long)arg2;
goto L_1218;
L_1200: ;
node = (long)((int)(arg0[(long)((int)((symbol + (node * 4))))]));
if (((unsigned long)((unsigned int)(node)) == 0)) {
goto L_1229;
}
var7 = (var7 + 1);
if ((var6 == var7)) {
goto L_1230;
}
L_1218: ;
symbol = (unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)((var7)))) - 97)));
if (((unsigned long)((unsigned long)((unsigned int)(symbol))) <= (unsigned long)(3))) {
goto L_1200;
}
node = 0xfffffffe;
L_1229: ;
return (unsigned int)(node);
L_1230: ;
var2 = (long)(((long)arg1 + (unsigned long)((unsigned int)(node))));
L_1233: ;
return ((unsigned long)((unsigned char)(*(char *)((var2)))) != 0);
L_1241: ;
node = 0xffffffff;
goto L_1229;
}