Bug 106884 - ifcombine may move shift so it shifts more than bitwidth
Summary: ifcombine may move shift so it shifts more than bitwidth
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 13.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: wrong-code
Depends on: 106811
Blocks:
  Show dependency treegraph
 
Reported: 2022-09-08 00:20 UTC by Krister Walfridsson
Modified: 2022-10-10 06:38 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2022-09-08 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Krister Walfridsson 2022-09-08 00:20:48 UTC
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.
Comment 1 Richard Biener 2022-09-08 09:52:09 UTC
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.
Comment 2 Krister Walfridsson 2022-09-08 10:53:16 UTC
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.
Comment 3 Krister Walfridsson 2022-09-30 11:34:47 UTC
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.