Wrong code at every /O level: two masked zero-tests joined by && lose their masks
SUMMARY
When two masked zero-tests on the SAME variable are joined by &&, and either
mask is a run-time value rather than a compile-time constant, the generated
code discards both masks and tests the variable against itself.
This function
unsigned int decide(unsigned int x, unsigned int m)
{
return !((x & m) != 0) && ((x & 0x100u) == 0);
}
is compiled as though it read return x == 0;
No diagnostic is issued, at any warning level.
AFFECTED
Compiler Pelles ISO C Compiler, Version 14.50.0
Targets -Tx64-coff and -Tx86-coff, both affected
Levels /Os, /Ot, /Ox, /O1, /O2 -- every one
Not affected compiling with no /O switch
Independent of /Ze, /Zx, /Go, and the /std: setting
(verified across nine switch combinations,
and with /std:C99, /std:C11, /std:C17)
WHAT THE STANDARD REQUIRES
ISO/IEC 9899:2018 6.5.10p4 (&), 6.5.3.3p5 (!) and 6.5.13p3 (&&) give, for
x = 0x00000279 and m = 2:
x & m = 0x279 & 0x002 = 0
(x & m) != 0 = 0
!((x & m) != 0) = 1
x & 0x100u = 0x279 & 0x100 = 0
(x & 0x100u) == 0 = 1
1 && 1 = 1
decide(0x279, 2) shall return 1. It returns 0.
There is no undefined behaviour in the function. Every operand is
unsigned int, so no signed overflow and no implementation-defined signed
conversion arises. There is no shift, no pointer arithmetic, no aliasing and
no uninitialised read, and neither operand of && has a side effect.
GENERATED CODE
Compiled -Tx64-coff -std:C17 with no /O switch -- correct:
decide:
mov dword ptr [rsp+8],ecx
mov dword ptr [rsp+10],edx
mov eax,dword ptr [rsp+10]
test dword ptr [rsp+8],eax ; x & m
jne L_false
test dword ptr [rsp+8],100 ; x & 0x100
jne L_false
mov eax,1
ret
L_false:
mov eax,0
ret
The same source, -Tx64-coff -Ot -std:C17 -- wrong:
decide:
xor eax,eax
test ecx,ecx ; x is tested against ITSELF
sete al
ret
edx, which holds the parameter m, is never read. The constant 0x100 has
disappeared as well.
The 32-bit target, -Tx86-coff /Ot, shows the same fault:
_decide:
xor eax,eax
cmp dword ptr [esp+4],0
sete al
ret
WHAT APPEARS TO BE HAPPENING
Fusing two masked zero-tests on one variable,
(x & m) == 0 && (x & n) == 0 ==> (x & (m | n)) == 0
is a valid and worthwhile transformation, and it is performed CORRECTLY when
both masks are compile-time constants. With m = 0x002 and n = 0x100 written
literally, the emitted code is exactly right:
both_const:
xor eax,eax
test ecx,102 ; 0x002 | 0x100 = 0x102 CORRECT
sete al
ret
The fault appears when either mask is not a constant. Rather than computing
m | n at run time, or declining the transformation, the emitted test takes the
value register as its second operand.
A run-time mask can be built perfectly well when the fusion is written out by
hand, so the capability is clearly there:
unsigned int fused_by_hand(unsigned int x, unsigned int m)
{
return ((x & m) | (x & 0x100u)) == 0;
}
fused_by_hand:
xor eax,eax
or edx,100 ; m | 0x100
test ecx,edx
sete al
ret ; CORRECT
WHICH FORMS ARE AFFECTED
All compiled -Tx64-coff -Ot -std:C17.
form emitted test verdict
----------------------------------------------------------------------
both masks compile-time constants test ecx,102 correct
first mask a parameter, second constant test ecx,ecx WRONG
first mask constant, second a parameter test ecx,ecx WRONG
both masks parameters test ecx,ecx WRONG
three conjuncts, first mask a parameter test ecx,ecx WRONG
signed int operands, otherwise identical test ecx,ecx WRONG
shared value left in first &, right in second test ecx,ecx WRONG
shared value is the right operand of both two tests correct
shared operand is a variable mask, values differ two tests correct
shared operand is a constant mask, values differ two tests correct
both masks are enumeration constants test ecx,14000 correct
single masked test, variable mask, no && test ecx,edx correct
the two tests on different variables two tests correct
fusion written by hand with | or, then test correct
|| with != 0 (the De Morgan dual) two tests correct
----------------------------------------------------------------------
Stated exactly: the fault arises when the LEFT operand of the & in an earlier
conjunct reappears, in either position, in a later conjunct's masked
zero-test, and at least one of the remaining operands is not a compile-time
constant.
Two further points, both measured rather than assumed:
- An enumeration constant behaves exactly as a literal does. Masks
NO_UGLY = 0x10000 and CONSERVE_MEMORY = 0x4000, declared in an enum, fuse
correctly to test ecx,14000 -- byte for byte the code the literals give.
- If the shared operand is the MASK rather than the value, as in
(h & 3) == 0 && (w & 3) == 0 where two different values are tested against
one constant, no fusion is attempted and the code is correct.
Signedness does not matter. Hoisting the sub-expressions into ordinary
non-volatile locals does NOT avoid it.
CONTROL
The identical source compiled by MinGW-w64 GCC 13 at -O2 performs the same
fusion and gets it right:
decide:
xor %eax,%eax
or $0x1,%dh # sets bit 8 of edx: m | 0x100
test %ecx,%edx
sete %al
ret
WHERE THIS WAS FOUND IN REAL CODE
Building libtiff 4.7.2 at /Ot. The function TIFFWriteEncodedStrip, in the
source file tif_write.c, contains
if (!isFillOrder(tif, td->td_fillorder) &&
(tif->tif_flags & TIFF_NOBITREV) == 0)
TIFFReverseBits((uint8_t *)data, cc);
with
#define isFillOrder(tif, o) (((tif)->tif_flags & (o)) != 0)
#define TIFF_NOBITREV 0x00100U
At run time tif_flags = 0x00100279 and td_fillorder = 2, so the condition is
true and the bit reversal must happen. The optimised build evaluated it as
false, skipped the reversal, and wrote every CCITT Group 3 fax image
bit-reversed while still tagging it FillOrder = 2. The files opened
without complaint; the pixels were wrong.
Twelve sites in that library match this trigger. No diagnostic was issued
for any of them.
TO REPRODUCE IN THIRTY SECONDS
The attached pellesc_1450_optimiser_bug.c is self-checking. Compile it twice
and run both:
pocc -Tx64-coff -std:C17 -c pellesc_1450_optimiser_bug.c
polink -subsystem:console -machine:x64 pellesc_1450_optimiser_bug.obj ^
crt64.lib kernel32.lib -out:noopt.exe
noopt.exe -> "All 7 cases correct." exit status 0
pocc -Tx64-coff -Ot -std:C17 -c pellesc_1450_optimiser_bug.c
polink -subsystem:console -machine:x64 pellesc_1450_optimiser_bug.obj ^
crt64.lib kernel32.lib -out:opt.exe
opt.exe -> "4 of 7 cases WRONG." exit status 1
ATTACHED FILES
src/pellesc_1450_optimiser_bug.c self-checking reproducer, run it twice
src/bug.c the single function, for disassembly
src/variants.c ten of the forms in the table above
src/characterise.c the same test across operand values
src/hypothesis.c demonstrates the transformation performed
src/shared_mask.c shared mask versus shared value
src/position.c which operand position matters
src/enum_masks.c enumeration constants as masks
disassembly/bug_no_optimisation_x64.asm correct
disassembly/bug_Ot_x64.asm WRONG
disassembly/bug_Ot_x86.asm WRONG
disassembly/variants_Ot_x64.asm all variants
disassembly/shared_mask_Ot_x64.asm
disassembly/position_Ot_x64.asm
disassembly/enum_masks_Ot_x64.asm
disassembly/bug_gcc_O2_control.asm GCC 13 -O2, correct
All listings were produced with podump /DISASM on the object files built
from exactly the attached sources.