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.
Kel26,
Yours is the most comprehensive, detailed, and coherent bug report that I've ever read.
It's also an excellent template for anyone wishing to share future bug reports.
Thanks for sharing ...