[Bug tree-optimization/108306] false-positive -Warray-bounds warning emitted with -fsanitize=shift

["rguenth at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW
                 CC|                            |amacleod at redhat dot com

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Kees Cook from comment #7)
> (In reply to Kees Cook from comment #6)
> > Sorry, I forgot to include those details fully! Here's how I'm seeing it:
> > 
> > $ gcc --version
> > gcc (GCC) 13.0.0 20230105 (experimental)
> > ...
> > $ gcc -O2 -fno-strict-overflow -fsanitize=shift -Warray-bounds -c -o
> > /dev/null poc.c
> 
> In function 'psi_group_change',
>     inlined from 'psi_task_switch' at poc.c:25:2:
> poc.c:15:30: warning: array subscript 32 is above array bounds of 'unsigned
> int[4]' [-Warray-bounds=]
>    15 |                         tasks[t]++;
>       |                         ~~~~~^~~
> poc.c: In function 'psi_task_switch':
> poc.c:6:14: note: while referencing 'tasks'
>     6 | unsigned int tasks[NR_PSI_TASK_COUNTS];
>       |              ^~~~~
> 
> (mispaste)

we diagnose

<bb 5> [local count: 8687547547]:
if (t_6 > 31)
  goto <bb 9>; [0.00%]

<bb 9> [count: 0]:
_7 = (unsigned long) t_6;
__builtin___ubsan_handle_shift_out_of_bounds (&*.Lubsan_data1, 1, _7);
_8 = 1 << t_6;
_9 = (unsigned int) _8;
_35 = _8 & 1;
_11 = (unsigned int) _35;
if (_35 != 0)
  goto <bb 10>; [50.00%]

<bb 10> [local count: 0]:
_12 = tasks[t_6];
_13 = _12 + 1;
tasks[t_6] = _13;

clearly t_6 is > 31 and thus the access is out-of-bounds [in the IL].
What we miss is the fact that we can rely on t_6 being in bounds for
the 1 << t_6 shift and thus this is unreachable code plus the fact
that for 1 << t_6 with t_6 > 31 bit zero is always zero.  That's something
for ranger to see - why doesn't it?  We have

=========== BB 5 ============
Imports: t_6
Exports: t_6
t_6     [irange] unsigned int VARYING
    <bb 5> [local count: 8687547547]:
    if (t_6 > 31)
      goto <bb 9>; [0.00%]
    else
      goto <bb 6>; [100.00%]

5->9  (T) t_6 :         [irange] unsigned int [32, +INF]
5->6  (F) t_6 :         [irange] unsigned int [0, 31] NONZERO 0x1f

=========== BB 9 ============
Imports: t_6  set_10
Exports: t_6  _8  _9  set_10  _11
         _7 : t_6(I)
         _8 : t_6(I)
         _9 : t_6(I)  _8
         _11 : t_6(I)  _8  _9  set_10(I)
         _35 : t_6(I)  _8
t_6     [irange] unsigned int [32, +INF]
set_10  [irange] unsigned int [1, 1] NONZERO 0x1
Partial equiv (_7 pe32 t_6)
Partial equiv (_9 pe32 _8)
    <bb 9> [count: 0]:
    _7 = (unsigned long) t_6;
    __builtin___ubsan_handle_shift_out_of_bounds (&*.Lubsan_data1, 1, _7);
    _8 = 1 << t_6;
    _9 = (unsigned int) _8;
    _35 = _8 & 1;
    _11 = (unsigned int) _35;
    if (_35 != 0)
      goto <bb 10>; [50.00%]
      goto <bb 10>; [50.00%]
    else
      goto <bb 11>; [50.00%]

_7 : [irange] unsigned long [32, 4294967295] NONZERO 0xffffffff
_11 : [irange] unsigned int [0, 1] NONZERO 0x1
9->10  (T) t_6 :        [irange] unsigned int [32, +INF]
9->10  (T) _7 :         [irange] unsigned long [32, 4294967295] NONZERO
0xffffffff
9->10  (T) _8 :         [irange] int [-INF, -1][1, +INF]
9->10  (T) set_10 :     [irange] unsigned int [1, 1] NONZERO 0x1
9->10  (T) _11 :        [irange] unsigned int [0, 1] NONZERO 0x1
9->10  (T) _35 :        [irange] int [0, 1] NONZERO 0x1
9->11  (F) t_6 :        [irange] unsigned int [32, +INF]
9->11  (F) _7 :         [irange] unsigned long [32, 4294967295] NONZERO
0xffffffff
9->11  (F) _8 :         [irange] int [-INF, -2][0, +INF] NONZERO 0xfffffffe
9->11  (F) set_10 :     [irange] unsigned int [1, 1] NONZERO 0x1
9->11  (F) _11 :        [irange] unsigned int [0, 1] NONZERO 0x1
9->11  (F) _35 :        [irange] int [0, 0] NONZERO 0x0

even without -fwrapv we don't seem to know that 1 << [32, +INF] resolves
to zero?!

6->7  (T) _31 :         [irange] int [-INF, -1][1, +INF]
6->8  (F) _31 :         [irange] int [-INF, -2][0, +INF] NONZERO 0xfffffffe

we seem to fall into

  else
    // Otherwise, invoke the generic fold routine.
    return range_operator::fold_range (r, type, op1, shift_range, rel);

and that oddly enough receives

(gdb) p debug (rh)
[irange] unsigned int [0, 31] NONZERO 0x1f

?!

#0  range_operator::fold_range (this=0x42f4ef0 <op_lshift>, r=..., 
    type=<integer_type 0x7ffff62855e8 int>, lh=..., rh=..., trio=...)
    at /home/rguenther/src/trunk/gcc/range-op.cc:244
#1  0x0000000002e26152 in operator_lshift::fold_range (
    this=0x42f4ef0 <op_lshift>, r=..., type=<integer_type 0x7ffff62855e8 int>, 
    op1=..., op2=..., rel=...)
    at /home/rguenther/src/trunk/gcc/range-op.cc:2192
#2  0x0000000002e3043d in range_op_handler::fold_range (this=0x7fffffff2c90, 
    r=..., type=<integer_type 0x7ffff62855e8 int>, lh=..., rh=..., rel=...)
    at /home/rguenther/src/trunk/gcc/range-op.cc:4506
#3  0x0000000002cb07e2 in fold_using_range::range_of_range_op (
    this=0x7fffffff2d3f, r=..., handler=..., src=...)
    at /home/rguenther/src/trunk/gcc/gimple-range-fold.cc:589
#4  0x0000000002caff11 in fold_using_range::fold_stmt (this=0x7fffffff2d3f, 
    r=..., s=<gimple_assign 0x7ffff607e630>, src=..., 
    name=<ssa_name 0x7ffff607cc18 8>)
    at /home/rguenther/src/trunk/gcc/gimple-range-fold.cc:489
#5  0x0000000002caf425 in fold_range (r=..., s=<gimple_assign 0x7ffff607e630>, 
    on_edge=<edge 0x7ffff60842d0 (11 -> 13)>, q=0x4352c88)
    at /home/rguenther/src/trunk/gcc/gimple-range-fold.cc:326
#6  0x0000000002cb89d0 in gori_compute::outgoing_edge_range_p (this=0x4352ca0, 
    r=..., e=<edge 0x7ffff60842d0 (11 -> 13)>, 
    name=<ssa_name 0x7ffff607cc18 8>, q=...)
    at /home/rguenther/src/trunk/gcc/gimple-range-gori.cc:1400
#7  0x0000000002ca8193 in ranger_cache::edge_range (this=0x4352c88, r=..., 
    e=<edge 0x7ffff60842d0 (11 -> 13)>, name=<ssa_name 0x7ffff607cc18 8>, 
    mode=ranger_cache::RFD_NONE)
    at /home/rguenther/src/trunk/gcc/gimple-range-cache.cc:964
#8  0x0000000002ca831c in ranger_cache::range_on_edge (this=0x4352c88, r=..., 
    e=<edge 0x7ffff60842d0 (11 -> 13)>, expr=<ssa_name 0x7ffff607cc18 8>)
    at /home/rguenther/src/trunk/gcc/gimple-range-cache.cc:1001
#9  0x0000000002ca256f in gimple_ranger::range_on_edge (this=0x4352c60, r=..., 
    e=<edge 0x7ffff60842d0 (11 -> 13)>, name=<ssa_name 0x7ffff607cc18 8>)
    at /home/rguenther/src/trunk/gcc/gimple-range.cc:241
#10 0x0000000002caedc8 in fur_edge::get_operand (this=0x7fffffff6030, r=..., 
    expr=<ssa_name 0x7ffff607cc18 8>)
    at /home/rguenther/src/trunk/gcc/gimple-range-fold.cc:131
#11 0x0000000002caeefc in fur_stmt::get_phi_operand (this=0x7fffffff9350, 
    r=..., expr=<ssa_name 0x7ffff607cc18 8>, 
    e=<edge 0x7ffff60842d0 (11 -> 13)>)
    at /home/rguenther/src/trunk/gcc/gimple-range-fold.cc:168
...

maybe I didn't capture the "correct" call (there are too many).  Still
something
goes wrong here.

A small testcase like

int foo (int n)
{
  if (n > 31)
    {
      int tem = 1 << n;
      if ((unsigned)tem & 1)
        bar ();
    }
}

is optimized just fine.