[Bug tree-optimization/112104] New: loop of ^1 should just be reduced to ^(n&1)

[Bug tree-optimization/112104] New: loop of ^1 should just be reduced to ^(n&1)

[pinskia at gcc dot gnu.org]

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

            Bug ID: 112104
           Summary: loop of ^1 should just be reduced to ^(n&1)
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pinskia at gcc dot gnu.org
  Target Milestone: ---

Take:
```
int
foo(long n3) {
  int j = 0;
  for(int i=0; i<n3; i++)
    j=j^1;
  return j;
}

int
foo1(long n3) {
  int j = 0;
  if (n3>=0)
    j = j ^ (n3&1);
  return j;
}
```

We should figure out that j as the result is just alternating between 0 and 1
(VRP figures that that is the range) in SCCP pattern matching.

I Noticed this while looking into PR 111972

[Bug tree-optimization/112104] loop of ^1 should just be reduced to ^(n&1)

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This shows up in a really really bad benchmark:
https://github.com/kdlucas/byte-unixbench/blob/master/UnixBench/src/whets.c

[Bug tree-optimization/112104] loop of ^1 should just be reduced to ^(n&1)

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-10-27
             Status|UNCONFIRMED                 |NEW

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  I think it should apply even to

int
foo(long n3, int j, int x) {
  for(int i=0; i<n3; i++)
    j=j^x;
  return j;
}

which alternates between 'j' and 'j^x', thus the result
is n3&1 ? j^x : j?

I wonder if there's some online symbolic calculus service that we can
feed IL during compilation ;)

[Bug tree-optimization/112104] loop of ^1 should just be reduced to ^(n&1)

[crazylht at gmail dot com]

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

--- Comment #3 from Hongtao.liu <crazylht at gmail dot com> ---
We already have analyze_and_compute_bitop_with_inv_effect, but it only works
when inv is an SSA_NAME, it should be extended to constant.

[Bug tree-optimization/112104] loop of ^1 should just be reduced to ^(n&1)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED
   Target Milestone|---                         |14.0

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed via r14-5428-gfd1596f9962569afff6c9298a7c79686c6950bef .

[Bug tree-optimization/112104] loop of ^1 should just be reduced to ^(n&1)

[crazylht at gmail dot com]

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

--- Comment #5 from Hongtao.liu <crazylht at gmail dot com> ---
(In reply to Andrew Pinski from comment #4)
> Fixed via r14-5428-gfd1596f9962569afff6c9298a7c79686c6950bef .

Note, my patch only handles constant tripcount for XOR, but not do the
transformation when tripcount is variable.

[Bug tree-optimization/112104] loop of ^1 should just be reduced to ^(n&1)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |NEW
         Resolution|FIXED                       |---

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Hongtao.liu from comment #5)
> (In reply to Andrew Pinski from comment #4)
> > Fixed via r14-5428-gfd1596f9962569afff6c9298a7c79686c6950bef .
> 
> Note, my patch only handles constant tripcount for XOR, but not do the
> transformation when tripcount is variable.

Oh.

[Bug tree-optimization/112104] loop of ^1 should just be reduced to ^(n&1)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|14.0                        |---