[Bug middle-end/104017] New: unexpeted -Warray-bounds popping a fixed number of std::deque elements

[Bug middle-end/104017] New: unexpeted -Warray-bounds popping a fixed number of std::deque elements

[msebor at gcc dot gnu.org]

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

            Bug ID: 104017
           Summary: unexpeted -Warray-bounds popping a fixed number of
                    std::deque elements
           Product: gcc
           Version: 9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: msebor at gcc dot gnu.org
  Target Milestone: ---

I got the following report in my private mail.  I file it here for reference
(and my analysis).  Although the warning isn't terribly informative I don't
consider it a false positive.

$ cat t.C && g++ -O2 -S -Wall t.C
#include <deque>

struct Node { Node const * parent = nullptr; };

void func(Node const * n)
{
    std::deque<Node const *> p;

    Node const * e = n;
    while (e != nullptr) {
        p.push_front(e);
        e = e->parent;
    }

    [[maybe_unused]] Node const * b;

    p.pop_front();
    e = p.front();
    p.pop_front();

    b = p.back();
    p.pop_back();
}
In file included from
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
                 from
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/allocator.h:46,
                 from
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/deque:61,
                 from t.C:1:
In member function ‘void std::__new_allocator<_Tp>::destroy(_Up*) [with _Up =
const Node*; _Tp = const Node*]’,
    inlined from ‘static void std::allocator_traits<std::allocator<_Tp1>
>::destroy(allocator_type&, _Up*) [with _Up = const Node*; _Tp = const Node*]’
at
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/alloc_traits.h:535:15,
    inlined from ‘void std::deque<_Tp, _Alloc>::pop_back() [with _Tp = const
Node*; _Alloc = std::allocator<const Node*>]’ at
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_deque.h:1604:28,
    inlined from ‘void func(const Node*)’ at t.C:22:15:
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/new_allocator.h:181:11:
warning: array subscript -1 is outside array bounds of ‘const Node* [64]’
[-Warray-bounds]
  181 |         { __p->~_Up(); }
      |           ^~~
In member function ‘_Tp* std::__new_allocator<_Tp>::allocate(size_type, const
void*) [with _Tp = const Node*]’,
    inlined from ‘static _Tp* std::allocator_traits<std::allocator<_Tp1>
>::allocate(allocator_type&, size_type) [with _Tp = const Node*]’ at
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/alloc_traits.h:464:28,
    inlined from ‘std::_Deque_base<_Tp, _Alloc>::_Ptr std::_Deque_base<_Tp,
_Alloc>::_M_allocate_node() [with _Tp = const Node*; _Alloc =
std::allocator<const Node*>]’ at
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_deque.h:583:26,
    inlined from ‘void std::_Deque_base<_Tp,
_Alloc>::_M_create_nodes(_Map_pointer, _Map_pointer) [with _Tp = const Node*;
_Alloc = std::allocator<const Node*>]’ at
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_deque.h:684:37,
    inlined from ‘void std::_Deque_base<_Tp,
_Alloc>::_M_initialize_map(std::size_t) [with _Tp = const Node*; _Alloc =
std::allocator<const Node*>]’ at
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_deque.h:658:19,
    inlined from ‘std::_Deque_base<_Tp, _Alloc>::_Deque_base() [with _Tp =
const Node*; _Alloc = std::allocator<const Node*>]’ at
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_deque.h:460:26,
    inlined from ‘std::deque<_Tp, _Alloc>::deque() [with _Tp = const Node*;
_Alloc = std::allocator<const Node*>]’ at
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/stl_deque.h:855:7,
    inlined from ‘void func(const Node*)’ at t.C:7:30:
/build/gcc-master/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/new_allocator.h:137:55:
note: at offset -8 into object of size 512 allocated by ‘operator new’
  137 |         return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n *
sizeof(_Tp)));
      |                                                       ^

[Bug tree-optimization/104017] unexpeted -Warray-bounds popping a fixed number of std::deque elements

[msebor at gcc dot gnu.org]

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

--- Comment #1 from Martin Sebor <msebor at gcc dot gnu.org> ---
The warning triggers for the clobber statement in bb 43 below.  _236 is assumed
to point to the beginning of the block of 512 bytes allocated by new, so
subtracting a positive integer from it or adding one in excess of 512 is
invalid, as is dereferencing the result:

  <bb 2> [local count: 118111600]:
  ...
  _229 = operator new (512);                               >>> _229
  ...
  <bb 42> [local count: 50546886]:
  _176 = p.D.20902._M_impl.D.20257._M_finish._M_first;
  if (_176 != _229)
    goto <bb 43>; [82.57%]
  else
    goto <bb 44>; [17.43%]

  <bb 43> [local count: 41736564]:
  _236 = ASSERT_EXPR <_229, _229 != _176>;                 <<< _229
  _177 = _236 + 18446744073709551608;
  p.D.20951._M_impl.D.20306._M_finish._M_cur = _177;
  MEM[(const struct Node * *)_236 + -8B] ={v} {CLOBBER};   <<< -Warray-bounds
  goto <bb 45>; [100.00%]

I view the warning as helpful here (and so not a false positive even) because
the test function assumes the loop inserts at least three elements into the
container.  If it doesn't, one of the pop() calls will crash.

A more compelling test case would guard each if the pop() calls to prevent the
crash, like below:

#include <deque>

struct Node { Node const * parent = nullptr; };

void func(Node const * n)
{
    std::deque<Node const *> p;

    Node const * e = n;

    while (e != nullptr) {
        p.push_front(e);
        e = e->parent;
    }

    if (p.size ())
      p.pop_front();
    if (p.size ())
      p.pop_front();
    if (p.size ())
      p.pop_back();
}


This test case also triggers a warning, for the same reason: GCC can't
determine the relationship between a deque's internal node pointers and the
result of std::deque::size() (which is a function of the node pointers).

[Bug tree-optimization/104017] unexpeted -Warray-bounds popping a fixed number of std::deque elements

[larsbj at gullik dot net]

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

Lars Gullik Bjønnes <larsbj at gullik dot net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |larsbj at gullik dot net

--- Comment #2 from Lars Gullik Bjønnes <larsbj at gullik dot net> ---
(In reply to Martin Sebor from comment #1)

...
> #include <deque>
> 
> struct Node { Node const * parent = nullptr; };
> 
> void func(Node const * n)
> {
>     std::deque<Node const *> p;
> 
>     Node const * e = n;
> 
>     while (e != nullptr) {
>         p.push_front(e);
>         e = e->parent;
>     }
> 
>     if (p.size ())
>       p.pop_front();
>     if (p.size ())
>       p.pop_front();
>     if (p.size ())
>       p.pop_back();
> }
> 
> 
> This test case also triggers a warning, for the same reason: GCC can't
> determine the relationship between a deque's internal node pointers and the
> result of std::deque::size() (which is a function of the node pointers).

This is also the case amended with a check that the std::deque::size is large
enough (for the same reason). In that case the crash can never happen, still
GCC12 warns/errors.

I agree that the first test case, and the warning from it, is helpful. However
this second one not so much.

[Bug tree-optimization/104017] unexpeted -Warray-bounds popping a fixed number of std::deque elements

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Martin Sebor from comment #1)
> I view the warning as helpful here (and so not a false positive even)
> because the test function assumes the loop inserts at least three elements
> into the container.  If it doesn't, one of the pop() calls will crash.

Code is allowed to assume things that is known a priori. The compiler should
not assume every possible erroneous path is taken. If it's going to assume that
they're taken, it really needs better diagnostic messages to say *why* it
thinks there is a problem. Just stating that an error happens unconditionally
is misleading and confusing to users.

[Bug tree-optimization/104017] unexpeted -Warray-bounds popping a fixed number of std::deque elements

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
If users can't tell why a warning happens without studying the compiler's IR
dumps, the warning is not actually useful.

[Bug tree-optimization/104017] unexpeted -Warray-bounds popping a fixed number of std::deque elements

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Martin Sebor from comment #1)

> This test case also triggers a warning, for the same reason: GCC can't
> determine the relationship between a deque's internal node pointers and the
> result of std::deque::size() (which is a function of the node pointers).

Is the warning in this case coming from this function?

      void
      pop_back() _GLIBCXX_NOEXCEPT
      {
        __glibcxx_requires_nonempty();
        if (this->_M_impl._M_finish._M_cur
            != this->_M_impl._M_finish._M_first)
          {
            --this->_M_impl._M_finish._M_cur;
            _Alloc_traits::destroy(_M_get_Tp_allocator(),
                                   this->_M_impl._M_finish._M_cur);
          }
        else
          _M_pop_back_aux();
      }

I don't see what size() has got to do with anything, we explicitly check that
_M_cur is not the start of the node.

With -D_GLIBCXX_ASSERTIONS the first line of the function expands to:

  __glibcxx_assert(!this->empty())

but it still warns.

What else are we supposed to do there to let the compiler know the object we're
destroying is valid? Do we need to add a third way to check the deque is not
empty?

[Bug tree-optimization/104017] unexpected -Warray-bounds popping a fixed number of std::deque elements

[larsbj at gullik dot net]

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

--- Comment #6 from Lars Gullik Bjønnes <larsbj at gullik dot net> ---
This is from a report I made in private to Martin, for GCC12.
That tidbit seems to have been lost in the bug creation.