[Bug tree-optimization/114326] New: Missed optimization for A || B when !B implies A.

[Bug tree-optimization/114326] New: Missed optimization for A || B when !B implies A.

[manolis.tsamis at vrull dot eu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114326

            Bug ID: 114326
           Summary: Missed optimization for A || B when !B implies A.
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: manolis.tsamis at vrull dot eu
  Target Milestone: ---

The function below doesn't fold to return 0;

int cmp1(uint64_t d1, uint64_t d2) {
  if (((d1 ^ d2) & 0xabcd) == 0 || d1 != d2)
    return 0;
  return foo();
}

while the following function does: 

int cmp2(uint64_t d1, uint64_t d2) {
  if (d1 != d2 || ((d1 ^ d2) & 0xabcd) == 0)
    return 0;
  return foo();
}

The functions are equivalent since the lhs and rhs of || don't have side
effects.

In general, there pattern here is a side-effect free expression a || b where !b
implies a should be optimized to true. As in the testcase above, a doesn't
necessarily imply !b. Something similar could be stated for && expressions.

Complementary godbolt link: https://godbolt.org/z/qK5bYf36T

[Bug tree-optimization/114326] Missed optimization for A || B when !B implies A.

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114326

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2024-03-13

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
  _1 = d1_5(D) ^ d2_6(D);
  _2 = _1 & 43981;
  _10 = d1_5(D) != d2_6(D);
  _11 = _2 == 0;
  _12 = _10 | _11;

(d1 != d2) | ((d1 ^ d2) & CST) == 0)

Confirmed.

Obvious if the first part is false then d1 ^ d2 will be 0.

This will work though maybe there is another place where this can be handled
...

(simplify
 (bit_ior
  (ne@n4 @0 @1)
  (cmp
   (bit_and
    (bit_xor @0 @1)
    @2)
   @3))
 (bit_ior @n4 
  (cmp { build_zero_cst (TREE_TYPE (@0)); } @3))
)

[Bug tree-optimization/114326] Missed optimization for A || B when !B implies A.

[ptomsich at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114326

--- Comment #2 from ptomsich at gcc dot gnu.org ---
To copy the last piece of info from our internal tracker...

LLVM learned this new trick only in the run-up to LLVM 18.
Up until then, GCC and LLVM performed identically on this snippet.

[Bug tree-optimization/114326] Missed optimization for A || B when !B implies A.

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114326

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to ptomsich from comment #2)
> To copy the last piece of info from our internal tracker...
> 
> LLVM learned this new trick only in the run-up to LLVM 18.
> Up until then, GCC and LLVM performed identically on this snippet.

Yes it looks like it is pattern matching what I suggested (well with and
without the and).

Note we do need another pattern, one without the bit_and:
(simplify
 (bit_ior
  (ne@n4 @0 @1)
  (cmp
   (bit_xor @0 @1)
   @2))
 (bit_ior @n4 
  (cmp { build_zero_cst (TREE_TYPE (@0)); } @2))
)

And we need one more for bit_ior:
(simplify
 (bit_ior
  (ne@n4 @0 @1)
  (cmp
   (bit_ior
    (bit_xor @0 @1)
    @2)
   @3))
 (bit_ior @n4 
  (cmp @2 @3))
)

Note it looks like clang does not handle non-contants that well, (they handle d
== 0 though).

E.g.:
```
int foo(void);
int cmp1(unsigned d1, unsigned d2, unsigned c, unsigned d) {
  int t = ((d1 ^ d2) & c ) == (d);
  int t1 = d1 != d2;
  int tt = t | t1;
  return tt;
}

```

Should be optimized to:
int foo(void);
int cmp1(unsigned d1, unsigned d2, unsigned c, unsigned d) {
  int t = 0 == d;
  int t1 = d1 != d2;
  int tt = t | t1;
  return tt;
}
```