Fixture 77
lru cache
C · 1 functions · 4 lanes · 3 of 4 function-lanes behave identically
One lane has a function that returns a different result after decompilation: clang-O2 (0/1).
A fixed-capacity LRU cache built from parallel arrays with an explicit recency stamp. Lookup promotes; insertion evicts the minimum stamp. Two scans over the same arrays with different reduction operators.
#include <stdint.h>
/* A fixed-capacity LRU cache built from parallel arrays with an explicit
* recency stamp. Lookup promotes; insertion evicts the minimum stamp. Two
* scans over the same arrays with different reduction operators. */
#define LRU_CAPACITY 8
__attribute__((noinline)) int32_t
lru_access(int32_t *keys, int32_t *stamps, int32_t capacity, int32_t key,
int32_t clock, int32_t *evicted_key) {
int32_t index;
int32_t victim = 0;
if (keys == 0 || stamps == 0 || evicted_key == 0 || capacity < 1 ||
capacity > LRU_CAPACITY || clock < 0) {
return -1;
}
*evicted_key = -1;
for (index = 0; index < capacity; ++index) {
if (keys[index] == key) {
stamps[index] = clock;
return 1;
}
}
for (index = 0; index < capacity; ++index) {
if (keys[index] == 0) {
keys[index] = key;
stamps[index] = clock;
return 0;
}
if (stamps[index] < stamps[victim]) {
victim = index;
}
}
*evicted_key = keys[victim];
keys[victim] = key;
stamps[victim] = clock;
return 2;
}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 -O2
0/1lru_access fail 113 lines
// glaurung: lru_access @ 0x1100
int32_t lru_access(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4, int32_t * arg5) {
int victim;
int index;
long local_10;
long ret;
long var1;
long var12;
long var2;
long var3;
long var8;
ret = 0xffffffff;
if (((long)(arg4) < 0)) {
return ret;
}
if (((unsigned long)((unsigned long)((unsigned int)((arg2 - 9)))) < (unsigned long)(0xfffffff8))) {
return ret;
}
if ((arg0 == 0)) {
return ret;
}
if ((arg1 == 0)) {
return ret;
}
if ((arg5 == 0)) {
return ret;
}
local_10 = var1;
*(int *)(((long)arg5)) = -1;
ret = 1;
if (((unsigned int)(*(int *)(((long)arg0))) != (unsigned int)(arg3))) {
if (((unsigned long)((unsigned int)(arg2)) != 1)) {
var2 = 1;
if (((unsigned int)(*(int *)(((long)arg0 + 0x4))) != (unsigned int)(arg3))) {
if (((unsigned long)((unsigned int)(arg2)) == 2)) {
L_1156: ;
var3 = (unsigned long)((unsigned int)(arg2));
var8 = 0;
victim = 0;
L_1170: ;
while (((unsigned long)((unsigned int)(*(int *)(((long)arg0 + var8 * 4)))) != 0)) {
var12 = (unsigned long)((unsigned int)(var8));
if (((long)((int)(arg1[(long)(victim)])) <= (long)((int)(*(int *)(((long)arg1 + var8 * 4)))))) {
var12 = (unsigned long)((unsigned int)(victim));
}
index = (var8 + 1);
var8 = (unsigned long)((unsigned int)(index));
victim = (unsigned long)((unsigned int)(var12));
if ((var3 == index)) {
var2 = (long)((int)(var12));
*(int *)(((long)arg5)) = arg0[(long)((int)(var12))];
arg0[(long)((int)(var12))] = arg3;
ret = 2;
} else {
goto L_1170;
}
*(int *)(((long)arg1 + var2 * 4)) = arg4;
// x86-64 epilogue: tear down frame
return ret;
}
var2 = (unsigned long)((unsigned int)(var8));
arg0[(unsigned long)((unsigned int)(var8))] = arg3;
ret = 0;
} else {
var2 = 2;
if (((unsigned int)(*(int *)(((long)arg0 + 0x8))) != (unsigned int)(arg3))) {
if (((unsigned long)((unsigned int)(arg2)) == 3)) {
goto L_1156;
} else {
var2 = 3;
if (((unsigned int)(*(int *)(((long)arg0 + 0xc))) != (unsigned int)(arg3))) {
if (((unsigned long)((unsigned int)(arg2)) == 4)) {
goto L_1156;
} else {
var2 = 4;
if (((unsigned int)(*(int *)(((long)arg0 + 0x10))) != (unsigned int)(arg3))) {
if (((unsigned long)((unsigned int)(arg2)) == 5)) {
goto L_1156;
} else {
var2 = 5;
if (((unsigned int)(*(int *)(((long)arg0 + 0x14))) != (unsigned int)(arg3))) {
if (((unsigned long)((unsigned int)(arg2)) == 6)) {
goto L_1156;
} else {
var2 = 6;
if (((unsigned int)(*(int *)(((long)arg0 + 0x18))) != (unsigned int)(arg3))) {
if (((unsigned long)((unsigned int)(arg2)) == 7)) {
goto L_1156;
} else {
var2 = 7;
if (((unsigned int)(*(int *)(((long)arg0 + 0x1c))) != (unsigned int)(arg3))) {
goto L_1156;
} else {
}
}
}
}
}
}
}
}
}
}
}
}
}
} else {
goto L_1156;
}
} else {
var2 = 0;
}
}clang -O0
1/1lru_access pass 64 lines
// glaurung: lru_access @ 0x1100
int32_t lru_access(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4, int32_t * arg5) {
int victim;
int index;
int local_4;
victim = 0;
if ((arg0 != 0)) {
if ((arg1 != 0)) {
if ((arg5 != 0)) {
if ((1 <= (long)(arg2))) {
if (((((unsigned long)((unsigned int)(arg2)) == 8) | ((long)(arg2) < 8)) != 0)) {
if ((0 <= (long)(arg4))) {
goto L_116c;
}
}
}
}
}
}
local_4 = -1;
// x86-64 epilogue: restore rbp
return (unsigned int)(local_4);
L_116c: ;
*(int *)((long)arg5) = -1;
index = 0;
L_117d: ;
if ((arg2 <= index)) {
goto L_11ca;
}
if (((unsigned int)(arg0[(long)(index)]) == (unsigned int)(arg3))) {
arg1[(long)(index)] = arg4;
// x86-64 epilogue: restore rbp
return 1;
}
goto L_11bc;
L_11bc: ;
index = ((unsigned int)(index) + 1);
goto L_117d;
L_11ca: ;
index = 0;
L_11d1: ;
if ((arg2 <= index)) {
goto L_124c;
}
if (((unsigned long)((unsigned int)(arg0[(long)(index)])) == 0)) {
arg0[(long)(index)] = arg3;
arg1[(long)(index)] = arg4;
// x86-64 epilogue: restore rbp
return 0;
}
if (((long)((int)(arg1[(long)(index)])) < (long)((int)(arg1[(long)(victim)])))) {
victim = index;
}
goto L_123e;
L_123e: ;
index = ((unsigned int)(index) + 1);
goto L_11d1;
L_124c: ;
*(int *)((long)arg5) = arg0[(long)(victim)];
arg0[(long)(victim)] = arg3;
arg1[(long)(victim)] = arg4;
// x86-64 epilogue: restore rbp
return 2;
}gcc -O0
1/1lru_access pass 58 lines
// glaurung: lru_access @ 0x10f9
int32_t lru_access(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4, int32_t * arg5) {
int victim;
int index;
victim = 0;
if ((arg0 != 0)) {
if ((arg1 != 0)) {
if ((arg5 != 0)) {
if (((((unsigned long)((unsigned int)(arg2)) == 0) | ((long)(arg2) < 0)) == 0)) {
if (((((unsigned long)((unsigned int)(arg2)) == 8) | ((long)(arg2) < 8)) != 0)) {
if ((0 <= (long)(arg4))) {
goto L_114f;
}
}
}
}
}
}
// x86-64 epilogue: restore rbp
return 0xffffffff;
L_114f: ;
*(int *)((long)arg5) = -1;
index = 0;
goto L_11a4;
L_1162: ;
if (((unsigned int)(arg3) == (unsigned int)(arg0[(long)(index)]))) {
arg1[(long)(index)] = arg4;
// x86-64 epilogue: restore rbp
return 1;
}
index = (index + 1);
L_11a4: ;
if ((index < arg2)) {
goto L_1162;
}
index = 0;
goto L_1248;
L_11b8: ;
if (((unsigned long)((unsigned int)(arg0[(long)(index)])) == 0)) {
arg0[(long)(index)] = arg3;
arg1[(long)(index)] = arg4;
// x86-64 epilogue: restore rbp
return 0;
}
if (((long)((int)(arg1[(long)(index)])) < (long)((int)(arg1[(long)(victim)])))) {
victim = index;
}
index = (index + 1);
L_1248: ;
if ((index < arg2)) {
goto L_11b8;
}
*(int *)((long)arg5) = arg0[(long)(victim)];
arg0[(long)(victim)] = arg3;
arg1[(long)(victim)] = arg4;
// x86-64 epilogue: restore rbp
return 2;
}gcc -O2
1/1lru_access pass 88 lines
// glaurung: lru_access @ 0x1100
int32_t lru_access(int32_t * arg0, int32_t * arg1, int32_t arg2, int32_t arg3, int32_t arg4, int32_t * arg5) {
int index;
int victim;
long local_10;
long local_8;
long var0;
long var1;
long var10;
long var15;
long var16;
long var17;
long var2;
int var20;
int var21;
int var24;
long var25;
long var4;
long var6;
long var7;
long var8;
long var9;
local_8 = var0;
local_10 = var1;
if ((arg0 == 0)) {
goto L_11dd;
}
var2 = (long)arg1;
if ((arg1 == 0)) {
goto L_11dd;
}
if (((unsigned long)(7) < (unsigned long)((unsigned long)((unsigned int)((arg2 - 1)))))) {
goto L_11dd;
}
if ((arg5 == 0)) {
goto L_11dd;
}
if (((long)(arg4) < 0)) {
goto L_11dd;
}
*(int *)(((long)arg5)) = -1;
var4 = (unsigned long)((unsigned int)(arg3));
var6 = 0;
do {
var7 = (var6 * 4);
if (((unsigned int)(*(int *)(((long)arg0 + var6 * 4))) == (unsigned int)(var4))) {
goto L_11b8;
}
var8 = (var6 + 1);
var6 = var8;
} while (((((unsigned int)(arg2) == (unsigned int)(var8)) | ((long)(arg2) < (long)((int)(var8)))) == 0));
var9 = (long)arg0;
var10 = var2;
var15 = 0;
var16 = 0;
do {
var17 = (unsigned long)((unsigned int)(*(int *)((var9))));
if (((unsigned long)((unsigned int)(var17)) == 0)) {
goto L_11d0;
}
var20 = (((long)((int)(*(int *)((var10)))) < (long)((int)(*(int *)((var2 + ((long)((int)(var16)) * 4)))))) ? var15 : var16);
var21 = (var15 + 1);
var9 = (var9 + 4);
var10 = (var10 + 4);
var15 = (unsigned long)((unsigned int)(var21));
var16 = (unsigned long)((unsigned int)(var20));
} while (((((unsigned int)(arg2) == (unsigned int)(var21)) | (arg2 < var21)) == 0));
var24 = 2;
var25 = (long)(((long)arg0 + ((long)((int)(var20)) * 4)));
*(int *)(((long)arg5)) = *(int *)((var25));
*(int *)((var25)) = var4;
*(int *)((var2 + ((long)((int)(var20)) * 4))) = arg4;
L_11ad: ;
// x86-64 epilogue: tear down frame
return (unsigned int)(var24);
L_11b8: ;
*(int *)((var2 + var7)) = arg4;
// x86-64 epilogue: tear down frame
return 1;
L_11d0: ;
*(int *)((var9)) = var4;
*(int *)((var10)) = arg4;
// x86-64 epilogue: tear down frame
return (unsigned int)(var17);
L_11dd: ;
var24 = 0xffffffff;
goto L_11ad;
}