public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth
@ 2022-09-08  0:20 kristerw at gcc dot gnu.org
  2022-09-08  9:52 ` [Bug tree-optimization/106884] " rguenth at gcc dot gnu.org
                   ` (6 more replies)
  0 siblings, 7 replies; 8+ messages in thread
From: kristerw at gcc dot gnu.org @ 2022-09-08  0:20 UTC (permalink / raw)
  To: gcc-bugs

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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth
  2022-09-08  0:20 [Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth kristerw at gcc dot gnu.org
@ 2022-09-08  9:52 ` rguenth at gcc dot gnu.org
  2022-09-08 10:53 ` kristerw at gcc dot gnu.org
                   ` (5 subsequent siblings)
  6 siblings, 0 replies; 8+ messages in thread
From: rguenth at gcc dot gnu.org @ 2022-09-08  9:52 UTC (permalink / raw)
  To: gcc-bugs

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

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth
  2022-09-08  0:20 [Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth kristerw at gcc dot gnu.org
  2022-09-08  9:52 ` [Bug tree-optimization/106884] " rguenth at gcc dot gnu.org
@ 2022-09-08 10:53 ` kristerw at gcc dot gnu.org
  2022-09-30 11:34 ` kristerw at gcc dot gnu.org
                   ` (4 subsequent siblings)
  6 siblings, 0 replies; 8+ messages in thread
From: kristerw at gcc dot gnu.org @ 2022-09-08 10:53 UTC (permalink / raw)
  To: gcc-bugs

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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth
  2022-09-08  0:20 [Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth kristerw at gcc dot gnu.org
  2022-09-08  9:52 ` [Bug tree-optimization/106884] " rguenth at gcc dot gnu.org
  2022-09-08 10:53 ` kristerw at gcc dot gnu.org
@ 2022-09-30 11:34 ` kristerw at gcc dot gnu.org
  2023-07-11  9:45 ` rguenth at gcc dot gnu.org
                   ` (3 subsequent siblings)
  6 siblings, 0 replies; 8+ messages in thread
From: kristerw at gcc dot gnu.org @ 2022-09-30 11:34 UTC (permalink / raw)
  To: gcc-bugs

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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth
  2022-09-08  0:20 [Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth kristerw at gcc dot gnu.org
                   ` (2 preceding siblings ...)
  2022-09-30 11:34 ` kristerw at gcc dot gnu.org
@ 2023-07-11  9:45 ` rguenth at gcc dot gnu.org
  2023-07-11 15:36 ` pinskia at gcc dot gnu.org
                   ` (2 subsequent siblings)
  6 siblings, 0 replies; 8+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-07-11  9:45 UTC (permalink / raw)
  To: gcc-bugs

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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth
  2022-09-08  0:20 [Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth kristerw at gcc dot gnu.org
                   ` (3 preceding siblings ...)
  2023-07-11  9:45 ` rguenth at gcc dot gnu.org
@ 2023-07-11 15:36 ` pinskia at gcc dot gnu.org
  2023-08-06  0:07 ` kristerw at gcc dot gnu.org
  2023-11-01 15:57 ` pinskia at gcc dot gnu.org
  6 siblings, 0 replies; 8+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-07-11 15:36 UTC (permalink / raw)
  To: gcc-bugs

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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth
  2022-09-08  0:20 [Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth kristerw at gcc dot gnu.org
                   ` (4 preceding siblings ...)
  2023-07-11 15:36 ` pinskia at gcc dot gnu.org
@ 2023-08-06  0:07 ` kristerw at gcc dot gnu.org
  2023-11-01 15:57 ` pinskia at gcc dot gnu.org
  6 siblings, 0 replies; 8+ messages in thread
From: kristerw at gcc dot gnu.org @ 2023-08-06  0:07 UTC (permalink / raw)
  To: gcc-bugs

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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* [Bug tree-optimization/106884] ifcombine may move shift so it shifts more than bitwidth
  2022-09-08  0:20 [Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth kristerw at gcc dot gnu.org
                   ` (5 preceding siblings ...)
  2023-08-06  0:07 ` kristerw at gcc dot gnu.org
@ 2023-11-01 15:57 ` pinskia at gcc dot gnu.org
  6 siblings, 0 replies; 8+ messages in thread
From: pinskia at gcc dot gnu.org @ 2023-11-01 15:57 UTC (permalink / raw)
  To: gcc-bugs

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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2023-11-01 15:57 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-09-08  0:20 [Bug tree-optimization/106884] New: ifcombine may move shift so it shifts more than bitwidth kristerw at gcc dot gnu.org
2022-09-08  9:52 ` [Bug tree-optimization/106884] " rguenth at gcc dot gnu.org
2022-09-08 10:53 ` kristerw at gcc dot gnu.org
2022-09-30 11:34 ` kristerw at gcc dot gnu.org
2023-07-11  9:45 ` rguenth at gcc dot gnu.org
2023-07-11 15:36 ` pinskia at gcc dot gnu.org
2023-08-06  0:07 ` kristerw at gcc dot gnu.org
2023-11-01 15:57 ` pinskia at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).