Fixture 14
flag effects
C · 7 functions · 4 lanes · 28 of 28 function-lanes behave identically
All 4 lanes recompile and return the same results as the original.
Instructions whose FLAG side effects a later branch reads.
At -O0 this mostly hides: gcc emits an explicit cmp or test immediately before every conditional branch, and cmp is the one instruction whose flag effects we model completely. At -O2 arithmetic-then-branch is the dominant idiom — sub $1,%edi ; jne, dec %ecx ; jnz, and %eax,%eax ; jz — and the lifter defines NO flags for any arithmetic instruction at all. A branch then reads either a flag nothing defined, or worse, one left over from a cmp outside the loop, which never updates.
dec_loop below decompiled into an infinite loop for three compounding reasons, all visible in one function:
zf = (arg0 == 0); // test defines Z... if (sle) { return ret; } // ...but jle reads Sle, which NOTHING defines L_1180: ; var1 = (var1 - 2); // sub sets ZF; we define nothing if ((~zf)) { goto L_1180; } // stale zf from OUTSIDE the loop, and ~ of a // 0/1 flag is always true
The differential reported it as "did not terminate within 5.0s on an input the original returned on", which is the only reason it was noticed — no metric distinguishes an infinite loop from a slow one.
These are written to be simple at -O0 and to force the flag-setting idioms at -O2, so the -O2 lanes are the ones that matter here.
/* Instructions whose FLAG side effects a later branch reads.
*
* At -O0 this mostly hides: gcc emits an explicit `cmp` or `test` immediately
* before every conditional branch, and `cmp` is the one instruction whose flag
* effects we model completely. At -O2 arithmetic-then-branch is the dominant
* idiom — `sub $1,%edi ; jne`, `dec %ecx ; jnz`, `and %eax,%eax ; jz` — and the
* lifter defines NO flags for any arithmetic instruction at all. A branch then
* reads either a flag nothing defined, or worse, one left over from a `cmp`
* outside the loop, which never updates.
*
* `dec_loop` below decompiled into an infinite loop for three compounding
* reasons, all visible in one function:
*
* zf = (arg0 == 0); // `test` defines Z...
* if (sle) { return ret; } // ...but `jle` reads Sle, which NOTHING defines
* L_1180: ;
* var1 = (var1 - 2); // `sub` sets ZF; we define nothing
* if ((~zf)) { goto L_1180; } // stale zf from OUTSIDE the loop, and `~` of a
* // 0/1 flag is always true
*
* The differential reported it as "did not terminate within 5.0s on an input the
* original returned on", which is the only reason it was noticed — no metric
* distinguishes an infinite loop from a slow one.
*
* These are written to be simple at -O0 and to force the flag-setting idioms at
* -O2, so the -O2 lanes are the ones that matter here.
*/
/* Decrement-and-branch: the canonical `sub` sets ZF, `jne` reads it. */
int dec_loop(int n) {
int c = 0;
for (int i = n; i > 0; i--) c += i;
return c;
}
/* Post-decrement in the condition — `while (n--)` is a flag read of the
* decrement itself, with no separate compare anywhere. */
/* HOIST TRAP — measured, do not "simplify" this loop's lowering.
*
* This function is one of exactly four the loop-header hoist fallback protects. The
* verbose `while (1) { pre; if (!cond) break; }` form it decompiles to is NOT an
* accident to be tidied away: hoisting the header above the loop lets constant
* propagation substitute the initial value that dominates at the hoist position, which
* freezes the loop-carried value and the loop stops making progress.
*
* Measured on branch `recover-ged-cells` (see docs/design/ged-recovery-measured-trade.md):
* always-hoisting recovers 50.32 GED points, 46% of a regression — and breaks exactly
* these four functions across six lanes:
* 03_loop_shapes:gcc:O2:while_prefix
* 12_loop_rotation:gcc:O2:find_first_set
* 13_loop_early_exit:{clang,gcc}:O2:classify_run
* 14_flag_effects:{clang,gcc}:O0:countdown
* So the compact form is worth real score, and it is wrong. That is the trade.
*
* FOUR predicates have been tried and all four failed, each differently: a copy-chain
* rule, a loop-invariance rule, a use-count rule, and a post-fold check requiring only a
* nonempty read/write intersection (which passes `find_first_set`, whose body reassigns
* its flag lower down while the frozen value sits inside the hoisted expression). If a
* post-fold check is attempted again it must preserve EVERY original loop-carried
* dependency, not one overlapping register.
*
* The real fix is typed value identity plus dominance, where "may this expression move
* here" is a query rather than a guess — value-model-root-cause-and-plan.md Phase 2.
*/
int countdown(int n) {
int s = 0;
while (n--) s += n;
return s;
}
/* `sub` then a sign test on its result. -O2 turns this into sub/neg/cmovs, so it
* also covers the `neg`-defines-SF path that `cmovs` consumes. */
int sub_then_sign(int a, int b) {
int d = a - b;
if (d < 0) return -d;
return d;
}
/* `and` sets ZF; the compare against zero is redundant and -O2 removes it. */
int and_is_zero(unsigned x, unsigned m) {
if ((x & m) == 0) return 1;
return 0;
}
/* `add` sets SF, and a signed-overflow-free sign test reads it. */
int add_then_negative(int a, int b) {
if (a + b < 0) return -1;
return 1;
}
/* Shifts set ZF and SF. A shift-and-test loop is a common bit-scan idiom. */
int shift_until_zero(unsigned x) {
int n = 0;
while (x) { x >>= 1; n++; }
return n;
}
/* `inc`/`dec` are special: they set SF/ZF/OF but deliberately LEAVE CF ALONE.
* That is the reason they exist as distinct opcodes, and a model that derives
* flags uniformly from "it is an arithmetic result" will get this wrong. `jbe`
* after `dec` reads Ule = CF|ZF, whose CF half belongs to whatever set it last. */
int dec_preserves_carry(unsigned a, unsigned b) {
unsigned d = a - b; /* sets CF */
int i = 3;
i--; /* must NOT disturb CF */
if (a < b) return i; /* reads the CF from the subtraction */
return d + i;
}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
7/7add_then_negative pass 9 lines
// glaurung: add_then_negative @ 0x1200
int add_then_negative(int arg0, int arg1) {
// x86-64 prologue: save rbp
if ((0 <= (long)((int)(((unsigned long)((unsigned int)(arg0)) + arg1))))) {
return 1;
} else {
return (unsigned int)(-1);
}
}and_is_zero pass 9 lines
// glaurung: and_is_zero @ 0x11c0
int and_is_zero(unsigned int arg0, unsigned int arg1) {
// x86-64 prologue: save rbp
if (((unsigned long)((unsigned int)((arg0 & arg1))) != 0)) {
return 0;
} else {
return 1;
}
}countdown pass 17 lines
// glaurung: countdown @ 0x1140
int countdown(int arg0) {
int s;
long var0;
// x86-64 prologue: save rbp
s = 0;
while (1) {
var0 = (unsigned long)((unsigned int)(arg0));
arg0 = ((unsigned int)(arg0) - 1);
if (((unsigned long)((unsigned int)(var0)) == 0)) {
break;
}
s = ((unsigned int)(arg0) + s);
}
// x86-64 epilogue: restore rbp
return (unsigned int)(s);
}dec_loop pass 14 lines
// glaurung: dec_loop @ 0x1100
int dec_loop(int arg0) {
int c;
int i;
// x86-64 prologue: save rbp
c = 0;
i = arg0;
while (((((unsigned long)((unsigned int)(i)) == 0) | ((long)(i) < 0)) == 0)) {
c = ((unsigned int)(i) + c);
i = ((unsigned int)(i) - 1);
}
// x86-64 epilogue: restore rbp
return (unsigned int)(c);
}dec_preserves_carry pass 14 lines
// glaurung: dec_preserves_carry @ 0x1280
int dec_preserves_carry(unsigned int arg0, unsigned int arg1) {
unsigned int d;
int i;
// x86-64 prologue: save rbp
d = (arg0 - arg1);
i = 3;
i = ((unsigned int)(i) - 1);
if (((unsigned long)(arg1) <= (unsigned long)(arg0))) {
return (unsigned int)(((unsigned long)(d) + i));
} else {
return (unsigned int)(i);
}
}shift_until_zero pass 12 lines
// glaurung: shift_until_zero @ 0x1240
int shift_until_zero(unsigned int arg0) {
int n;
// x86-64 prologue: save rbp
n = 0;
while ((arg0 != 0)) {
arg0 = ((unsigned int)(arg0) >> 1);
n = ((unsigned int)(n) + 1);
}
// x86-64 epilogue: restore rbp
return (unsigned int)(n);
}sub_then_sign pass 11 lines
// glaurung: sub_then_sign @ 0x1180
int sub_then_sign(int arg0, int arg1) {
int d;
// x86-64 prologue: save rbp
d = ((unsigned int)(arg0) - arg1);
if ((0 <= (long)(d))) {
return (unsigned int)(d);
} else {
return (unsigned int)((0 - d));
}
}clang -O2
7/7add_then_negative pass 4 lines
// glaurung: add_then_negative @ 0x1160
int add_then_negative(int arg0, int arg1) {
return (unsigned int)(((unsigned long)((unsigned int)(((int)((arg0 + arg1)) >> 31))) | 1));
}and_is_zero pass 4 lines
// glaurung: and_is_zero @ 0x1150
int and_is_zero(unsigned int arg0, unsigned int arg1) {
return ((unsigned long)((unsigned int)((arg1 & arg0))) == 0);
}countdown pass 7 lines
// glaurung: countdown @ 0x1120
int countdown(int arg0) {
int s;
long var0;
var0 = (unsigned long)((unsigned int)((arg0 - 1)));
return (unsigned int)(((unsigned long)((unsigned int)((var0 * arg0))) - ((unsigned long)((var0 * (unsigned long)((unsigned int)(arg0)))) >> 1)));
}dec_loop pass 10 lines
// glaurung: dec_loop @ 0x1100
int dec_loop(int arg0) {
int c;
long var1;
if ((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0))) {
return 0;
}
var1 = (unsigned long)((unsigned int)((arg0 - 1)));
return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)((var1 * var1))) + arg0))) - ((unsigned long)(((unsigned long)((unsigned int)((arg0 - 2))) * var1)) >> 1)));
}dec_preserves_carry pass 4 lines
// glaurung: dec_preserves_carry @ 0x1190
int dec_preserves_carry(unsigned int arg0, unsigned int arg1) {
return (((unsigned long)(arg1) <= (unsigned long)(arg0)) ? (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)(arg0) - arg1))) + 2))) : 2);
}shift_until_zero pass 26 lines
// glaurung: shift_until_zero @ 0x1170
int shift_until_zero(unsigned int arg0) {
int n;
long cf_6;
long ret;
long var1;
long var2;
long var3;
long zf_6;
ret = 0;
if ((arg0 != 0)) {
var1 = (unsigned long)(arg0);
var2 = 0;
var3 = (unsigned long)(arg0);
do {
var1 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var1)) >> 1)));
n = (var2 + 1);
var2 = (unsigned long)((unsigned int)(n));
zf_6 = ((unsigned long)((unsigned int)(var3)) == 1);
cf_6 = ((unsigned long)((unsigned long)((unsigned int)(var3))) < (unsigned long)(1));
var3 = (unsigned long)((unsigned int)(var1));
ret = (unsigned long)((unsigned int)(n));
} while (((cf_6 | zf_6) == 0));
}
return ret;
}sub_then_sign pass 8 lines
// glaurung: sub_then_sign @ 0x1140
int sub_then_sign(int arg0, int arg1) {
int d;
long t0;
d = (unsigned long)((unsigned int)((arg0 - arg1)));
t0 = (-(unsigned long)((unsigned int)(d)));
return (((long)((int)(t0)) < 0) ? d : t0);
}gcc -O0
7/7add_then_negative pass 9 lines
// glaurung: add_then_negative @ 0x11a3
int add_then_negative(int arg0, int arg1) {
// x86-64 prologue: save rbp
if ((0 <= (long)((int)(((unsigned long)((unsigned int)(arg1)) + (unsigned long)((unsigned int)(arg0))))))) {
return 1;
} else {
return 0xffffffff;
}
}and_is_zero pass 9 lines
// glaurung: and_is_zero @ 0x117d
int and_is_zero(unsigned int arg0, unsigned int arg1) {
// x86-64 prologue: save rbp
if (((unsigned long)((unsigned int)((arg0 & arg1))) != 0)) {
return 0;
} else {
return 1;
}
}countdown pass 17 lines
// glaurung: countdown @ 0x1128
int countdown(int arg0) {
int s;
long var0;
// x86-64 prologue: save rbp
s = 0;
while (1) {
var0 = (unsigned long)((unsigned int)(arg0));
arg0 = ((unsigned int)(arg0) - 1);
if (((unsigned long)((unsigned int)(var0)) == 0)) {
break;
}
s = (s + (unsigned int)(arg0));
}
// x86-64 epilogue: restore rbp
return (unsigned int)(s);
}dec_loop pass 14 lines
// glaurung: dec_loop @ 0x10f9
int dec_loop(int arg0) {
int c;
int i;
// x86-64 prologue: save rbp
c = 0;
i = arg0;
while (((((unsigned long)((unsigned int)(i)) == 0) | ((long)(i) < 0)) == 0)) {
c = (c + (unsigned int)(i));
i = (i - 1);
}
// x86-64 epilogue: restore rbp
return (unsigned int)(c);
}dec_preserves_carry pass 14 lines
// glaurung: dec_preserves_carry @ 0x11f1
int dec_preserves_carry(unsigned int arg0, unsigned int arg1) {
unsigned int d;
int i;
// x86-64 prologue: save rbp
d = (arg0 - arg1);
i = 3;
i = (i - 1);
if (((unsigned long)(arg1) <= (unsigned long)(arg0))) {
return (unsigned int)(((unsigned long)(d) + (unsigned long)((unsigned int)(i))));
} else {
return (unsigned int)(i);
}
}shift_until_zero pass 12 lines
// glaurung: shift_until_zero @ 0x11cb
int shift_until_zero(unsigned int arg0) {
int n;
// x86-64 prologue: save rbp
n = 0;
while ((arg0 != 0)) {
arg0 = ((unsigned int)(arg0) >> 1);
n = (n + 1);
}
// x86-64 epilogue: restore rbp
return (unsigned int)(n);
}sub_then_sign pass 11 lines
// glaurung: sub_then_sign @ 0x1154
int sub_then_sign(int arg0, int arg1) {
int d;
// x86-64 prologue: save rbp
d = ((unsigned int)(arg0) - arg1);
if ((0 <= (long)(d))) {
return (unsigned int)(d);
} else {
return (-(unsigned long)((unsigned int)(d)));
}
}gcc -O2
7/7add_then_negative pass 4 lines
// glaurung: add_then_negative @ 0x1170
int add_then_negative(int arg0, int arg1) {
return (unsigned int)(((unsigned long)((unsigned int)(((int)((arg0 + arg1)) >> 31))) | 1));
}and_is_zero pass 4 lines
// glaurung: and_is_zero @ 0x1160
int and_is_zero(unsigned int arg0, unsigned int arg1) {
return ((unsigned long)((unsigned int)((arg0 & arg1))) == 0);
}countdown pass 21 lines
// glaurung: countdown @ 0x1130
int countdown(int arg0) {
int s;
long cf_5;
long var0;
long var2;
long var3;
var0 = (unsigned long)((unsigned int)((arg0 - 1)));
var2 = 0;
if (((unsigned long)((unsigned int)(arg0)) != 0)) {
var3 = 0;
do {
s = (var3 + var0);
var3 = (unsigned long)((unsigned int)(s));
cf_5 = ((unsigned long)((unsigned long)((unsigned int)(var0))) < (unsigned long)(1));
var0 = (unsigned long)((unsigned int)((var0 - 1)));
var2 = (unsigned long)((unsigned int)(s));
} while ((cf_5 == 0));
}
return (unsigned int)(var2);
}dec_loop pass 18 lines
// glaurung: dec_loop @ 0x1100
int dec_loop(int arg0) {
int c;
int i;
long ret;
long var1;
int var3;
ret = 0;
if ((((unsigned long)((unsigned int)(arg0)) != 0) && (0 <= (long)(arg0)))) {
var1 = (unsigned long)((unsigned int)(arg0));
do {
ret = (unsigned long)((unsigned int)((ret + var1)));
var3 = (var1 - 1);
var1 = (unsigned long)((unsigned int)(var3));
} while (((unsigned long)((unsigned int)(var3)) != 0));
}
return ret;
}dec_preserves_carry pass 6 lines
// glaurung: dec_preserves_carry @ 0x11b0
int dec_preserves_carry(unsigned int arg0, unsigned int arg1) {
unsigned int d;
int i;
return (((unsigned long)(arg0) < (unsigned long)(arg1)) ? 2 : (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)(arg0) - arg1))) + 2))));
}shift_until_zero pass 17 lines
// glaurung: shift_until_zero @ 0x1180
int shift_until_zero(unsigned int arg0) {
int n;
long ret;
long var1;
int var4;
ret = 0;
if ((arg0 != 0)) {
var1 = (unsigned long)(arg0);
do {
ret = (unsigned long)((unsigned int)((ret + 1)));
var4 = ((unsigned long)((unsigned int)(var1)) >> 1);
var1 = (unsigned long)((unsigned int)(var4));
} while (((unsigned long)((unsigned int)(var4)) != 0));
}
return ret;
}sub_then_sign pass 7 lines
// glaurung: sub_then_sign @ 0x1150
int sub_then_sign(int arg0, int arg1) {
int d;
int var4;
var4 = ((unsigned int)(arg0) - arg1);
return (((long)((int)(var4)) < 0) ? (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) - arg0))) : (unsigned long)((unsigned int)(var4)));
}