[Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth

[Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth

[kristerw at gcc dot gnu.org]

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

            Bug ID: 106884
           Summary: ifcombine may move shift so it shifts more than
                    bitwidth
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kristerw at gcc dot gnu.org
  Target Milestone: ---

The function foo from gcc.dg/tree-ssa/ssa-ifcombine-1.c can be called
as foo(1, 1, 33) without invoking undefined behavior

int foo (int x, int a, int b)
{
  int c = 1 << a;
  if (x & c)
    if (x & (1 << b))
      return 2;
  return 0;
}

But ifcombine transforms this to

int foo (int x, int a, int b)
{
   int c;
   int _4;
   int _10;
   int _11;
   int _12;
   int _13;

   <bb 2>:
   _10 = 1 << b_8(D);
   _11 = 1 << a_5(D);
   _12 = _10 | _11;
   _13 = x_7(D) & _12;
   if (_12 == _13)
     goto <bb 3>;
   else
     goto <bb 4>;

   <bb 3>:

   <bb 4>:
   # _4 = PHI <2(3), 0(2)>
   return _4;
}

and this will now calculate 1 << 33 unconditionally for _10.

[Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org
           Keywords|                            |wrong-code
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-09-08
         Depends on|                            |106811

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  r13-131-gc2a0d2e6f636c6 addressed some issues, but leaves others
such as shifts seen here.  It's not clear if (int)1 << 33 is undefined behavior
in
GIMPLE, see PR106811.  Note that ifcombine doesn't simply transform this to
(x & c) & (x & (1 << b)), thus removing the short-circuiting, instead it
computes tem = c | (1<<b) and checks (x & tem) == tem.  That's probably safe
for arbitrary results of the undefined operation though.

One possibility might be to rewrite 1 << b to (1 << (b&31)) to make it always
defined, but that comes at an extra cost compared to how we treat signed
overflow.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106811
[Bug 106811] GENERIC and GIMPLE IL undefined behavior needs documenting

[Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth

[kristerw at gcc dot gnu.org]

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

--- Comment #2 from Krister Walfridsson <kristerw at gcc dot gnu.org> ---
This optimization is invalid if (int)1 << 33 is _not_ undefined behavior in
GIMPLE!

Consider an architecture where (int)1 << 33 evaluates to 0. foo(2, 1, 33)
evaluates to 0 for the original GIMPLE, but it evaluates to 2 in the optimized
IR.

[Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth

[kristerw at gcc dot gnu.org]

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

--- Comment #3 from Krister Walfridsson <kristerw at gcc dot gnu.org> ---
A similar case is

int r1, r2;

int foo(int a, int s1, int s2)
{
  if (a & (1 << s1))
    return r1;
  if (a & (1 << s2))
    return r1;
  return r2;
}

where reassoc2 optimizes this to always shift by s2.

[Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
To clarify for the original testcase, ifcombine combines the two bit tests
(x & (1<<a)) && (x & (1<<b)) to x & ((1<<a) | (1<<b)) == ((1<<a) | (1<<b)).
We can rely on 1<<a being non-zero, otherwise the testcase invoked undefined
behavior.  That means whatever value 1<<b produced in the case it was
unspecified we still get false when bit 1<<a was not set and a defined value
when the value of 1<<b was well-defined.

But yes, since we now unconditionally compute 1<<b after the transform
GCC could assume b is in range.  We are lacking a way to compute 1<<b
optimally without that undefined behavior.

[Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> But yes, since we now unconditionally compute 1<<b after the transform
> GCC could assume b is in range.  We are lacking a way to compute 1<<b
> optimally without that undefined behavior.

phiopt will almost definitely run into a similar thing though right now, it has
not.

[Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth

[kristerw at gcc dot gnu.org]

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

--- Comment #6 from Krister Walfridsson <kristerw at gcc dot gnu.org> ---
One more similar case (that may be the same as comment #3):

int g;

void foo(int a, int b, int c, int d, int e)
{
  if ((10 + a) * b)
    {
      g = (c || (g >> d)) << 1;
    }
}

In this case, reassoc1 optimizes the IR for
  c || (g >> d)
to do 
  (c | (g >> d)) != 0
and we are now always doing the shift, even when c is true.

[Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
PR 111000 was similar one but for LIM.