Fixture 16
red black tree
C · 1 functions · 4 lanes · 4 of 4 function-lanes behave identically
All 4 lanes recompile and return the same results as the original.
#include <stdint.h>
typedef struct {
int32_t key;
int32_t left;
int32_t right;
uint32_t color;
} RbNode;
__attribute__((noinline)) int32_t
rb_validate(const RbNode *nodes, int32_t n, int32_t root) {
int32_t parents[16] = {0};
int32_t node_stack[32];
int32_t black_stack[32];
int32_t expected_black = -1;
int32_t top = 0;
int32_t i;
if (nodes == 0 || n <= 0 || n > 16 || root < 0 || root >= n) {
return 0;
}
if (nodes[root].color != 0u) {
return 0;
}
for (i = 0; i < n; ++i) {
int32_t children[2] = {nodes[i].left, nodes[i].right};
int32_t side;
if (nodes[i].color > 1u) {
return 0;
}
for (side = 0; side < 2; ++side) {
int32_t child = children[side];
if (child == -1) {
continue;
}
if (child < 0 || child >= n || ++parents[child] != 1) {
return 0;
}
if ((side == 0 && nodes[child].key >= nodes[i].key) ||
(side == 1 && nodes[child].key <= nodes[i].key)) {
return 0;
}
if (nodes[i].color == 1u && nodes[child].color == 1u) {
return 0;
}
}
}
if (parents[root] != 0) {
return 0;
}
for (i = 0; i < n; ++i) {
if (i != root && parents[i] != 1) {
return 0;
}
}
node_stack[top] = root;
black_stack[top++] = 0;
while (top > 0) {
int32_t node;
int32_t black_count;
int32_t children[2];
int32_t side;
--top;
node = node_stack[top];
black_count = black_stack[top] + (nodes[node].color == 0u ? 1 : 0);
children[0] = nodes[node].left;
children[1] = nodes[node].right;
for (side = 0; side < 2; ++side) {
if (children[side] == -1) {
if (expected_black < 0) {
expected_black = black_count;
} else if (black_count != expected_black) {
return 0;
}
} else {
if (top >= 32) {
return 0;
}
node_stack[top] = children[side];
black_stack[top++] = black_count;
}
}
}
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
1/1rb_validate pass 191 lines
// glaurung: rb_validate @ 0x1110
typedef struct anon_12b RbNode;
#ifndef GLAURUNG_STRUCT_anon_12b_DEFINED
#define GLAURUNG_STRUCT_anon_12b_DEFINED
typedef struct anon_12b anon_12b;
struct anon_12b {
int32_t key;
int32_t left;
int32_t right;
uint32_t color;
};
#endif
__attribute__((no_stack_protector)) int32_t rb_validate(const RbNode * arg0, int32_t arg1, int32_t arg2) {
extern void * memset(void *, int, __SIZE_TYPE__);
int expected_black;
int top;
int i;
int local_178;
int child;
int node;
int black_count;
int side;
unsigned char local_160[128];
unsigned char local_174[8];
unsigned char local_18c[8];
unsigned char local_60[64];
unsigned char local_e0[128];
long t211;
void * var1;
long var111;
int var28;
long var43;
long var71;
var1 = memset((void *)(&local_60[0]), 0, (__SIZE_TYPE__)(64));
expected_black = -1;
top = 0;
if ((arg0 != 0)) {
if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) != 0)) {
if ((0 <= (long)(arg2))) {
if ((arg2 < arg1)) {
goto L_118a;
}
}
}
}
}
// x86-64 epilogue: restore rbp
return 0;
L_118a: ;
if (((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(arg2) << 4)) + 12)))) != 0)) {
// x86-64 epilogue: restore rbp
return 0;
}
i = 0;
L_11b9: ;
if ((arg1 <= i)) {
goto L_139e;
}
*(int *)(&local_174[0]) = *(int *)((((long)arg0 + ((long)(i) << 4)) + 4));
*(int *)((&local_174[0] + 4)) = *(int *)((((long)arg0 + ((long)(i) << 4)) + 8));
if (((unsigned long)(1) < (unsigned long)((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(i) << 4)) + 12))))))) {
// x86-64 epilogue: restore rbp
return 0;
}
local_178 = 0;
L_1230: ;
if ((2 <= (long)(local_178))) {
goto L_1385;
}
child = *(int *)((&local_174[0] + ((long)(local_178) * 4)));
if (((unsigned long)((unsigned int)(child)) == 0xffffffff)) {
goto L_1371;
}
if ((0 <= (long)(child))) {
if ((child < arg1)) {
var28 = ((unsigned int)(*(int *)((&local_60[0] + ((long)(child) * 4)))) + 1);
*(int *)((&local_60[0] + ((long)(child) * 4))) = var28;
if (((unsigned long)((unsigned int)(var28)) == 1)) {
goto L_12a6;
}
}
}
// x86-64 epilogue: restore rbp
return 0;
L_12a6: ;
if (((unsigned long)((unsigned int)(local_178)) == 0)) {
if (((long)((int)(*(int *)(((long)arg0 + ((long)(i) << 4))))) <= (long)((int)(*(int *)(((long)arg0 + ((long)(child) << 4))))))) {
goto L_131c;
}
}
if (((unsigned long)((unsigned int)(local_178)) != 1)) {
goto L_1328;
}
var43 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + ((long)(child) << 4)))));
t211 = *(int *)(((long)arg0 + ((long)(i) << 4)));
if (((((unsigned int)(var43) == (unsigned int)(t211)) | ((long)((int)(var43)) < (long)((int)(t211)))) == 0)) {
goto L_1328;
}
L_131c: ;
// x86-64 epilogue: restore rbp
return 0;
L_1328: ;
if (((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(i) << 4)) + 12)))) == 1)) {
if (((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(child) << 4)) + 12)))) == 1)) {
// x86-64 epilogue: restore rbp
return 0;
}
}
goto L_1371;
L_1371: ;
local_178 = ((unsigned int)(local_178) + 1);
goto L_1230;
L_1385: ;
goto L_138a;
L_138a: ;
i = ((unsigned int)(i) + 1);
goto L_11b9;
L_139e: ;
if (((unsigned long)((unsigned int)(*(int *)((&local_60[0] + ((long)(arg2) * 4))))) != 0)) {
// x86-64 epilogue: restore rbp
return 0;
}
i = 0;
L_13c3: ;
if ((arg1 <= i)) {
goto L_1418;
}
if (((unsigned int)(i) != (unsigned int)(arg2))) {
if (((unsigned long)((unsigned int)(*(int *)((&local_60[0] + ((long)(i) * 4))))) != 1)) {
// x86-64 epilogue: restore rbp
return 0;
}
}
goto L_1404;
L_1404: ;
i = ((unsigned int)(i) + 1);
goto L_13c3;
L_1418: ;
*(int *)((&local_e0[0] + ((long)(top) * 4))) = arg2;
var71 = (unsigned long)((unsigned int)(top));
top = ((unsigned int)(top) + 1);
*(int *)((&local_160[0] + ((long)((int)(var71)) * 4))) = 0;
L_1447: ;
if ((((unsigned long)((unsigned int)(top)) == 0) | ((long)(top) < 0))) {
goto L_15ca;
}
top = ((unsigned int)(top) - 1);
node = *(int *)((&local_e0[0] + ((long)(top) * 4)));
black_count = ((unsigned int)(*(int *)((&local_160[0] + ((long)(top) * 4)))) + (((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(node) << 4)) + 12)))) == 0) ? 1 : 0));
*(int *)(&local_18c[0]) = *(int *)((((long)arg0 + ((long)(node) << 4)) + 4));
*(int *)((&local_18c[0] + 4)) = *(int *)((((long)arg0 + ((long)(node) << 4)) + 8));
side = 0;
L_14ef: ;
if ((2 <= (long)(side))) {
goto L_15c5;
}
if (((unsigned long)((unsigned int)(*(int *)((&local_18c[0] + ((long)(side) * 4))))) != 0xffffffff)) {
goto L_1557;
}
if (((long)(expected_black) < 0)) {
expected_black = black_count;
goto L_1552;
}
if (((unsigned int)(black_count) != (unsigned int)(expected_black))) {
// x86-64 epilogue: restore rbp
return 0;
}
goto L_1552;
L_1552: ;
goto L_15ac;
L_1557: ;
if ((32 <= (long)(top))) {
// x86-64 epilogue: restore rbp
return 0;
}
*(int *)((&local_e0[0] + ((long)(top) * 4))) = *(int *)((&local_18c[0] + ((long)(side) * 4)));
var111 = (unsigned long)((unsigned int)(top));
top = ((unsigned int)(top) + 1);
*(int *)((&local_160[0] + ((long)((int)(var111)) * 4))) = black_count;
L_15ac: ;
goto L_15b1;
L_15b1: ;
side = ((unsigned int)(side) + 1);
goto L_14ef;
L_15c5: ;
goto L_1447;
L_15ca: ;
// x86-64 epilogue: restore rbp
return 1;
}clang -O2
1/1rb_validate pass 233 lines
// glaurung: rb_validate @ 0x1100
typedef struct anon_124 RbNode;
#ifndef GLAURUNG_STRUCT_anon_124_DEFINED
#define GLAURUNG_STRUCT_anon_124_DEFINED
typedef struct anon_124 anon_124;
struct anon_124 {
int32_t key;
int32_t left;
int32_t right;
uint32_t color;
};
#endif
__attribute__((no_stack_protector)) int32_t rb_validate(const RbNode * arg0, int32_t arg1, int32_t arg2) {
int i;
int expected_black;
int top;
int black_count;
int side;
unsigned char local_128[128];
unsigned char local_168[64];
unsigned char local_a8[168];
long ret;
long t209;
long var11;
long var14;
long var15;
long var16;
long var17;
long var18;
long var20;
long var22;
long var24;
long var25;
long var28;
long var32;
long var35;
long var37;
long var41;
long var46;
long var47;
long var50;
long var6;
long var9;
// x86-64 prologue: save callee registers, frame 32 bytes
*(int *)((&local_168[0] + 48)) = 0;
*(int *)((&local_168[0] + 52)) = 0;
*(int *)((&local_168[0] + 56)) = 0;
*(int *)((&local_168[0] + 60)) = 0;
*(int *)((&local_168[0] + 32)) = 0;
*(int *)((&local_168[0] + 36)) = 0;
*(int *)((&local_168[0] + 40)) = 0;
*(int *)((&local_168[0] + 44)) = 0;
*(int *)((&local_168[0] + 16)) = 0;
*(int *)((&local_168[0] + 20)) = 0;
*(int *)((&local_168[0] + 24)) = 0;
*(int *)((&local_168[0] + 28)) = 0;
*(int *)(&local_168[0]) = 0;
*(int *)((&local_168[0] + 4)) = 0;
*(int *)((&local_168[0] + 8)) = 0;
*(int *)((&local_168[0] + 12)) = 0;
ret = 0;
if ((arg1 <= arg2)) {
goto L_114c;
}
if (((long)(arg2) < 0)) {
goto L_114c;
}
if ((arg0 == 0)) {
goto L_114c;
}
if (((unsigned long)((unsigned long)((unsigned int)((arg1 - 17)))) < (unsigned long)(0xfffffff0))) {
goto L_114c;
}
var6 = (unsigned long)((unsigned int)(arg2));
if (((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((unsigned long)((unsigned int)(arg2)) << 4)) + 12)))) == 0)) {
goto L_115a;
}
L_114c: ;
// x86-64 epilogue: restore callee registers
return ret;
L_115a: ;
var9 = (unsigned long)((unsigned int)(arg1));
var11 = ((unsigned long)((unsigned int)(arg1)) << 4);
ret = 0;
var14 = 0;
goto L_117d;
L_1170: ;
var14 = (var14 + 16);
if ((var11 == var14)) {
goto L_1222;
}
L_117d: ;
var15 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var14 + 0xc))));
if (((unsigned long)(1) < (unsigned long)((unsigned long)((unsigned int)(var15))))) {
goto L_114c;
}
var16 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var14 + 0x4))));
var17 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var14 + 0x8))));
if (((unsigned long)((unsigned int)(var16)) != 0xffffffff)) {
if (((long)((int)(var16)) < 0)) {
goto L_114c;
}
if (((long)(arg1) <= (long)((int)(var16)))) {
goto L_114c;
}
var18 = (unsigned long)((unsigned int)(*(int *)((&local_168[0] + (var16 * 4)))));
*(int *)((&local_168[0] + (var16 * 4))) = (var18 + 1);
if (((unsigned long)((unsigned int)(var18)) != 0)) {
goto L_114c;
}
var20 = (var16 << 4);
if (((long)((int)(*(int *)(((long)arg0 + var14)))) <= (long)((int)(*(int *)(((long)arg0 + var20)))))) {
goto L_114c;
}
if (((unsigned long)((unsigned int)(var15)) == 1)) {
if (((unsigned long)((unsigned int)(*(int *)(((long)arg0 + var20 + 0xc)))) == 1)) {
goto L_114c;
}
}
}
if (((unsigned long)((unsigned int)(var17)) == 0xffffffff)) {
goto L_1170;
}
if (((long)((int)(var17)) < 0)) {
goto L_114c;
}
if (((long)(arg1) <= (long)((int)(var17)))) {
goto L_114c;
}
var22 = (unsigned long)((unsigned int)(*(int *)((&local_168[0] + (var17 * 4)))));
*(int *)((&local_168[0] + (var17 * 4))) = (var22 + 1);
if (((unsigned long)((unsigned int)(var22)) != 0)) {
goto L_114c;
}
var24 = (var17 << 4);
var25 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var24))));
t209 = *(int *)(((long)arg0 + var14));
if ((((unsigned int)(var25) == (unsigned int)(t209)) | ((long)((int)(var25)) < (long)((int)(t209))))) {
goto L_114c;
}
if (((unsigned long)((unsigned int)(var15)) != 1)) {
goto L_1170;
}
if (((unsigned long)((unsigned int)(*(int *)(((long)arg0 + var24 + 0xc)))) != 1)) {
goto L_1170;
}
goto L_114c;
L_1222: ;
if (((unsigned long)((unsigned int)(*(int *)((&local_168[0] + (var6 * 4))))) != 0)) {
goto L_114c;
}
var28 = 0;
goto L_1249;
L_1240: ;
i = (var28 + 1);
var28 = (unsigned long)((unsigned int)(i));
if ((var9 == i)) {
goto L_125a;
}
L_1249: ;
if ((var6 == var28)) {
goto L_1240;
}
if (((unsigned long)((unsigned int)(*(int *)((&local_168[0] + (var28 * 4))))) == 1)) {
goto L_1240;
}
goto L_12ef;
L_125a: ;
*(int *)(&local_a8[0]) = arg2;
*(int *)(&local_128[0]) = 0;
var32 = 1;
expected_black = 0xffffffff;
goto L_1283;
L_1272: ;
ret = 1;
var32 = (unsigned long)((unsigned int)(var37));
expected_black = (unsigned long)((unsigned int)(var35));
if ((((unsigned long)((unsigned int)(var37)) == 0) | ((long)((int)(var37)) < 0))) {
goto L_114c;
}
L_1283: ;
top = (unsigned long)((unsigned int)((var32 - 1)));
var41 = ((long)((int)(*(int *)((&local_a8[0] + (top * 4))))) << 4);
black_count = (unsigned int)(((unsigned int)(*(int *)((&local_128[0] + (top * 4)))) + ((unsigned long)((unsigned long)((unsigned int)(*(int *)(((long)arg0 + var41 + 0xc))))) < (unsigned long)(1))));
var46 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var41 + 0x4))));
var47 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var41 + 0x8))));
if (((unsigned long)((unsigned int)(var46)) != 0xffffffff)) {
var28 = var46;
if (((((unsigned long)((unsigned int)(var32)) == 32) | ((long)((int)(var32)) < 32)) == 0)) {
goto L_12ef;
}
*(int *)((&local_a8[0] + ((long)(top) * 4))) = var46;
*(int *)((&local_128[0] + ((long)(top) * 4))) = black_count;
top = (unsigned long)((unsigned int)(var32));
var50 = (unsigned long)((unsigned int)(expected_black));
goto L_12c9;
}
if ((0 <= (long)(expected_black))) {
var50 = (unsigned long)((unsigned int)(expected_black));
if (((unsigned int)(black_count) == (unsigned int)(expected_black))) {
goto L_12c9;
}
var28 = var46;
goto L_12ef;
}
var50 = (unsigned long)((unsigned int)(black_count));
L_12c9: ;
if (((unsigned long)((unsigned int)(var47)) != 0xffffffff)) {
var28 = var46;
if (((((unsigned long)((unsigned int)(top)) == 31) | ((long)(top) < 31)) == 0)) {
goto L_12ef;
}
*(int *)((&local_a8[0] + ((long)(top) * 4))) = var47;
var37 = (unsigned long)((unsigned int)((top + 1)));
*(int *)((&local_128[0] + ((long)(top) * 4))) = black_count;
var35 = (unsigned long)((unsigned int)(var50));
goto L_1272;
}
var37 = (unsigned long)((unsigned int)(top));
var35 = (unsigned long)((unsigned int)(black_count));
if (((long)((int)(var50)) < 0)) {
goto L_1272;
}
var37 = (unsigned long)((unsigned int)(top));
var35 = (unsigned long)((unsigned int)(black_count));
var28 = var46;
if (((unsigned int)(black_count) == (unsigned int)(var50))) {
goto L_1272;
}
L_12ef: ;
ret = 0;
goto L_114c;
}gcc -O0
1/1rb_validate pass 196 lines
// glaurung: rb_validate @ 0x1119
typedef struct anon_9d RbNode;
#ifndef GLAURUNG_STRUCT_anon_9d_DEFINED
#define GLAURUNG_STRUCT_anon_9d_DEFINED
typedef struct anon_9d anon_9d;
struct anon_9d {
int32_t key;
int32_t left;
int32_t right;
uint32_t color;
};
#endif
int32_t rb_validate(const RbNode * arg0, int32_t arg1, int32_t arg2) {
extern __attribute__((noreturn)) void __stack_chk_fail(void);
int expected_black;
int top;
int i;
int side;
int child;
int node;
int black_count;
int local_168;
unsigned char local_110[128];
unsigned char local_150[64];
unsigned char local_158[8];
long local_8;
unsigned char local_90[128];
long ret;
long var144;
long var65;
long var72;
long var99;
local_8 = (long)(0x28);
*(long *)(&local_150[0]) = 0;
*(long *)((&local_150[0] + 8)) = 0;
*(long *)((&local_150[0] + 16)) = 0;
*(long *)((&local_150[0] + 24)) = 0;
*(long *)((&local_150[0] + 32)) = 0;
*(long *)((&local_150[0] + 40)) = 0;
*(long *)((&local_150[0] + 48)) = 0;
*(long *)((&local_150[0] + 56)) = 0;
expected_black = -1;
top = 0;
if ((arg0 != 0)) {
if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) != 0)) {
if ((0 <= (long)(arg2))) {
if ((arg2 < arg1)) {
goto L_11f3;
}
}
}
}
}
ret = 0;
goto L_1628;
L_11f3: ;
if (((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(arg2) << 4)) + 12)))) != 0)) {
ret = 0;
goto L_1628;
}
i = 0;
goto L_141a;
L_122c: ;
*(int *)(&local_90[0]) = *(int *)((((long)arg0 + ((long)(i) << 4)) + 4));
*(int *)((&local_90[0] + 4)) = *(int *)((((long)arg0 + ((long)(i) << 4)) + 8));
if (((unsigned long)(1) < (unsigned long)((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(i) << 4)) + 12))))))) {
ret = 0;
goto L_1628;
}
side = 0;
goto L_1406;
L_12aa: ;
child = *(int *)((&local_90[0] + ((long)(side) * 4)));
if (((unsigned long)((unsigned int)(child)) == 0xffffffff)) {
goto L_13fe;
}
if ((0 <= (long)(child))) {
if ((child < arg1)) {
*(int *)((&local_150[0] + ((long)(child) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_150[0] + ((long)(child) * 4))))) + 1);
if (((unsigned long)((unsigned int)(*(int *)((&local_150[0] + ((long)(child) * 4))))) == 1)) {
goto L_1322;
}
}
}
ret = 0;
goto L_1628;
L_1322: ;
if (((unsigned long)((unsigned int)(side)) == 0)) {
if (((long)((int)(*(int *)(((long)arg0 + ((long)(i) << 4))))) <= (long)((int)(*(int *)(((long)arg0 + ((long)(child) << 4))))))) {
goto L_13a8;
}
}
if (((unsigned long)((unsigned int)(side)) != 1)) {
goto L_13b2;
}
var65 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + ((long)(child) << 4)))));
var72 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + ((long)(i) << 4)))));
if (((((unsigned int)(var65) == (unsigned int)(var72)) | ((long)((int)(var65)) < (long)((int)(var72)))) == 0)) {
goto L_13b2;
}
L_13a8: ;
ret = 0;
goto L_1628;
L_13b2: ;
if (((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(i) << 4)) + 12)))) != 1)) {
goto L_13ff;
}
if (((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(child) << 4)) + 12)))) != 1)) {
goto L_13ff;
}
ret = 0;
goto L_1628;
L_13fe: ;
L_13ff: ;
side = (side + 1);
L_1406: ;
if ((((unsigned long)((unsigned int)(side)) == 1) | ((long)(side) < 1))) {
goto L_12aa;
}
i = (i + 1);
L_141a: ;
if ((i < arg1)) {
goto L_122c;
}
if (((unsigned long)((unsigned int)(*(int *)((&local_150[0] + ((long)(arg2) * 4))))) != 0)) {
ret = 0;
goto L_1628;
}
i = 0;
goto L_1488;
L_1455: ;
if (((unsigned int)(i) != (unsigned int)(arg2))) {
if (((unsigned long)((unsigned int)(*(int *)((&local_150[0] + ((long)(i) * 4))))) != 1)) {
ret = 0;
goto L_1628;
}
}
i = (i + 1);
L_1488: ;
if ((i < arg1)) {
goto L_1455;
}
*(int *)((&local_110[0] + ((long)(top) * 4))) = arg2;
var99 = (unsigned long)((unsigned int)(top));
top = ((unsigned int)(top) + 1);
*(int *)((&local_90[0] + ((long)((int)(var99)) * 4))) = 0;
goto L_1616;
L_14cc: ;
top = (top - 1);
node = *(int *)((&local_110[0] + ((long)(top) * 4)));
black_count = (((unsigned long)((unsigned int)(*(int *)((((long)arg0 + ((long)(node) << 4)) + 12)))) == 0) + (unsigned int)(*(int *)((&local_90[0] + ((long)(top) * 4)))));
*(int *)(&local_158[0]) = *(int *)((((long)arg0 + ((long)(node) << 4)) + 4));
*(int *)((&local_158[0] + 4)) = *(int *)((((long)arg0 + ((long)(node) << 4)) + 8));
local_168 = 0;
goto L_1609;
L_1576: ;
if (((unsigned long)((unsigned int)(*(int *)((&local_158[0] + ((long)(local_168) * 4))))) == 0xffffffff)) {
if (((long)(expected_black) < 0)) {
expected_black = black_count;
goto L_1602;
}
if (((unsigned int)(black_count) == (unsigned int)(expected_black))) {
goto L_1602;
}
ret = 0;
goto L_1628;
}
if (((((unsigned long)((unsigned int)(top)) == 31) | ((long)(top) < 31)) == 0)) {
ret = 0;
goto L_1628;
}
*(int *)((&local_110[0] + ((long)(top) * 4))) = *(int *)((&local_158[0] + ((long)(local_168) * 4)));
var144 = (unsigned long)((unsigned int)(top));
top = ((unsigned int)(top) + 1);
*(int *)((&local_90[0] + ((long)((int)(var144)) * 4))) = black_count;
L_1602: ;
local_168 = (local_168 + 1);
L_1609: ;
if ((((unsigned long)((unsigned int)(local_168)) == 1) | ((long)(local_168) < 1))) {
goto L_1576;
}
L_1616: ;
if (((((unsigned long)((unsigned int)(top)) == 0) | ((long)(top) < 0)) == 0)) {
goto L_14cc;
}
ret = 1;
L_1628: ;
if ((local_8 == 0x28)) {
// x86-64 epilogue: restore rbp
return ret;
}
__stack_chk_fail();
// x86-64 epilogue: restore rbp
return ret;
}gcc -O2
1/1rb_validate pass 264 lines
// glaurung: rb_validate @ 0x1120
typedef struct anon_9d RbNode;
#ifndef GLAURUNG_STRUCT_anon_9d_DEFINED
#define GLAURUNG_STRUCT_anon_9d_DEFINED
typedef struct anon_9d anon_9d;
struct anon_9d {
int32_t key;
int32_t left;
int32_t right;
uint32_t color;
};
#endif
int32_t rb_validate(const RbNode * arg0, int32_t arg1, int32_t arg2) {
extern __attribute__((noreturn)) void __stack_chk_fail(void);
int expected_black;
int top;
int black_count;
int i;
int side;
unsigned char local_138[128];
unsigned char local_178[64];
long local_30;
unsigned char local_b8[128];
long ret;
long t200;
long var10;
long var12;
long var13;
long var16;
long var17;
long var18;
long var19;
long var20;
int var21;
long var23;
long var29;
long var30;
long var31;
int var33;
long var40;
long var42;
long var44;
long var50;
long var53;
long var55;
long var56;
long var59;
long var60;
long var66;
long var8;
long var9;
local_30 = (long)(0x28);
ret = (unsigned long)((unsigned int)((arg1 - 1)));
*(int *)(&local_178[0]) = 0;
*(int *)((&local_178[0] + 4)) = 0;
*(int *)((&local_178[0] + 8)) = 0;
*(int *)((&local_178[0] + 12)) = 0;
*(int *)((&local_178[0] + 16)) = 0;
*(int *)((&local_178[0] + 20)) = 0;
*(int *)((&local_178[0] + 24)) = 0;
*(int *)((&local_178[0] + 28)) = 0;
*(int *)((&local_178[0] + 32)) = 0;
*(int *)((&local_178[0] + 36)) = 0;
*(int *)((&local_178[0] + 40)) = 0;
*(int *)((&local_178[0] + 44)) = 0;
*(int *)((&local_178[0] + 48)) = 0;
*(int *)((&local_178[0] + 52)) = 0;
*(int *)((&local_178[0] + 56)) = 0;
*(int *)((&local_178[0] + 60)) = 0;
if (((unsigned long)(15) < (unsigned long)((unsigned long)((unsigned int)(ret))))) {
goto L_1250;
}
if ((arg0 == 0)) {
goto L_1250;
}
var8 = (unsigned long)((unsigned int)(arg2));
if (((long)(arg2) < 0)) {
goto L_1250;
}
var9 = (unsigned long)((unsigned int)(arg1));
if ((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2))) {
goto L_1250;
}
var10 = (long)(arg2);
ret = ((long)(arg2) << 4);
var12 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + ret + 0xc))));
if (((unsigned long)((unsigned int)(var12)) != 0)) {
goto L_1250;
}
var13 = (long)arg0;
var16 = 0;
var17 = var18;
goto L_11cc;
L_11a8: ;
t200 = *(int *)((ret));
if ((((unsigned int)(t200) == (unsigned int)(var19)) | ((long)((int)(t200)) < (long)((int)(var19))))) {
goto L_1250;
}
if (((unsigned long)((unsigned int)(var20)) == 1)) {
goto L_1248;
}
L_11bb: ;
var21 = (var16 + 1);
var13 = (var13 + 16);
var16 = (unsigned long)((unsigned int)(var21));
var17 = var23;
if ((((unsigned int)(var9) == (unsigned int)(var21)) | ((long)((int)(var9)) < (long)((int)(var21))))) {
goto L_1277;
}
L_11cc: ;
var20 = (unsigned long)((unsigned int)(*(int *)((var13 + 0xc))));
ret = (long)((int)(*(int *)((var13 + 0x4))));
var23 = ((unsigned long)((unsigned int)(var17)) | ((unsigned long)((unsigned int)(*(int *)((var13 + 0x8)))) << 32));
if (((unsigned long)(1) < (unsigned long)((unsigned long)((unsigned int)(var20))))) {
goto L_1250;
}
var29 = 0;
var30 = ((unsigned long)(var23) >> 32);
var31 = 0;
if (((unsigned long)((unsigned int)(ret)) == 0xffffffff)) {
goto L_1236;
}
L_11f5: ;
if (((long)((int)(ret)) < 0)) {
goto L_1250;
}
if ((((unsigned int)(var9) == (unsigned int)(ret)) | ((long)((int)(var9)) < (long)((int)(ret))))) {
goto L_1250;
}
var33 = ((unsigned int)(*(int *)((&local_178[0] + (ret * 4)))) + 1);
*(int *)((&local_178[0] + (ret * 4))) = var33;
if (((unsigned long)((unsigned int)(var33)) != 1)) {
goto L_1250;
}
var19 = (unsigned long)((unsigned int)(*(int *)((var13))));
ret = (long)(((ret << 4) + (long)arg0));
if ((var29 != 0)) {
goto L_11a8;
}
if (((long)((int)(var19)) <= (long)((int)(*(int *)((ret)))))) {
goto L_1250;
}
if (((unsigned long)((unsigned int)(var20)) == 1)) {
goto L_1248;
}
L_1229: ;
ret = (long)((int)(var30));
var29 = 1;
var31 = 1;
if (((unsigned long)((unsigned int)(var30)) != 0xffffffff)) {
goto L_11f5;
}
L_1236: ;
if ((var31 != 1)) {
goto L_1229;
}
goto L_11bb;
L_1248: ;
var31 = var29;
if (((unsigned long)((unsigned int)(*(int *)((ret + 0xc)))) != 1)) {
goto L_1236;
}
L_1250: ;
ret = 0;
L_1252: ;
if ((local_30 != 0x28)) {
goto L_1374;
}
// x86-64 epilogue: tear down frame
return ret;
L_1277: ;
ret = (unsigned long)((unsigned int)(*(int *)((&local_178[0] + (var10 * 4)))));
if (((unsigned long)((unsigned int)(ret)) != 0)) {
goto L_1250;
}
var40 = 0;
do {
if (((unsigned int)(var8) != (unsigned int)(var40))) {
if (((unsigned long)((unsigned int)(*(int *)((&local_178[0] + (var40 * 4))))) != 1)) {
goto L_1250;
}
}
var42 = (var40 + 1);
var40 = var42;
} while (((((unsigned int)(var9) == (unsigned int)(var42)) | ((long)((int)(var9)) < (long)((int)(var42)))) == 0));
*(int *)(&local_138[0]) = var8;
var44 = 0;
*(int *)(&local_b8[0]) = 0;
expected_black = 0xffffffff;
var50 = 0;
top = 1;
goto L_1314;
L_12c0: ;
if (((((unsigned long)((unsigned int)(var50)) == 31) | ((long)((int)(var50)) < 31)) == 0)) {
goto L_1252;
}
*(int *)((&local_138[0] + ((long)((int)(var50)) * 4))) = var53;
*(int *)((&local_b8[0] + ((long)((int)(var50)) * 4))) = black_count;
L_12d4: ;
var56 = (unsigned long)((unsigned int)(expected_black));
if (((unsigned long)((unsigned int)(var55)) == 0xffffffff)) {
goto L_134f;
}
L_12da: ;
if (((((unsigned long)((unsigned int)(top)) == 31) | ((long)(top) < 31)) == 0)) {
goto L_1252;
}
var59 = (unsigned long)((unsigned int)((top + 1)));
*(int *)((&local_138[0] + ((long)(top) * 4))) = var55;
*(int *)((&local_b8[0] + ((long)(top) * 4))) = black_count;
expected_black = var56;
L_12f5: ;
var60 = (unsigned long)((unsigned int)((var59 - 1)));
var10 = (long)((int)(*(int *)((&local_138[0] + ((long)((int)(var60)) * 4)))));
var12 = (unsigned long)((unsigned int)(*(int *)((((long)arg0 + (var10 << 4)) + 12))));
var44 = (unsigned long)((unsigned int)(*(int *)((&local_b8[0] + ((long)((int)(var60)) * 4)))));
var50 = var60;
top = var59;
L_1314: ;
var66 = (long)(((var10 << 4) + (long)arg0));
var53 = (unsigned long)((unsigned int)(*(int *)((var66 + 0x4))));
var55 = (unsigned long)((unsigned int)(*(int *)((var66 + 0x8))));
black_count = (unsigned int)(((unsigned int)(var44) + ((unsigned long)((unsigned long)((unsigned int)(var12))) < (unsigned long)(1))));
if (((unsigned long)((unsigned int)(var53)) != 0xffffffff)) {
goto L_12c0;
}
if (((long)(expected_black) < 0)) {
goto L_1360;
}
if (((unsigned int)(black_count) != (unsigned int)(expected_black))) {
goto L_1252;
}
var56 = (unsigned long)((unsigned int)(expected_black));
top = (unsigned long)((unsigned int)(var50));
var59 = (unsigned long)((unsigned int)(var50));
if (((unsigned long)((unsigned int)(var55)) != 0xffffffff)) {
goto L_12da;
}
L_1346: ;
if (((unsigned long)((unsigned int)(var59)) == 0)) {
goto L_136a;
}
expected_black = (unsigned long)((unsigned int)(black_count));
goto L_12f5;
L_134f: ;
var59 = (unsigned long)((unsigned int)(top));
if (((long)(expected_black) < 0)) {
goto L_1346;
}
var59 = (unsigned long)((unsigned int)(top));
if (((unsigned int)(expected_black) == (unsigned int)(black_count))) {
goto L_1346;
}
goto L_1252;
L_1360: ;
expected_black = (unsigned long)((unsigned int)(black_count));
top = (unsigned long)((unsigned int)(var50));
goto L_12d4;
L_136a: ;
ret = 1;
goto L_1252;
L_1374: ;
__stack_chk_fail();
}