Wrong code at every /O level: two masked zero-tests joined by && lose their mask

[KEL26]

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

Code Select Expand

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:

Code Select Expand

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:

Code Select Expand

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:

Code Select Expand

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:

Code Select Expand

_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:

Code Select Expand

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:

Code Select Expand

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.

Code Select Expand

  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:

Code Select Expand

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

Code Select Expand

if (!isFillOrder(tif, td->td_fillorder) &&
    (tif->tif_flags & TIFF_NOBITREV) == 0)
    TIFFReverseBits((uint8_t *)data, cc);

with

Code Select Expand

#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:

Code Select Expand

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

Code Select Expand

  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.

[MrBcx]

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 ...