Bug 83239 - False positive from -Wstringop-overflow on simple std::vector code
Summary: False positive from -Wstringop-overflow on simple std::vector code
Status: ASSIGNED
Alias: None
Product: gcc
Classification: Unclassified
Component: middle-end (show other bugs)
Version: 8.0
: P3 normal
Target Milestone: ---
Assignee: Jeffrey A. Law
URL:
Keywords: diagnostic, missed-optimization, patch
Depends on:
Blocks:
 
Reported: 2017-12-01 11:01 UTC by Tony E Lewis
Modified: 2018-08-02 06:41 UTC (History)
6 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2017-12-01 00:00:00


Attachments
Pre-processed (-save-temps) on GCC 7.2.0 [Ubuntu 17.10] (39.03 KB, text/plain)
2017-12-01 11:01 UTC, Tony E Lewis
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Tony E Lewis 2017-12-01 11:01:35 UTC
Created attachment 42765 [details]
Pre-processed (-save-temps) on GCC 7.2.0 [Ubuntu 17.10]

Compiling this:


#include <vector>

void fn() {
  std::vector<int> a;
  
  int num = 2;
  while ( num > 0 ) {
    const auto a_size = a.size();
    if ( a_size < 3 ) {
      a.assign( 1, 0 );
    }
    else {
      a.resize( a_size - 2 ); // <-- I think problem is here
    }
    --num;
  }
}

...with `g++ -O3 -Wall -Werror a.cpp` results in:


In function ‘void fn()’:
cc1plus: error: ‘void* __builtin_memset(void*, int, long unsigned int)’: specified size 18446744073709551608 exceeds maximum object size 9223372036854775807 [-Werror=stringop-overflow=]
cc1plus: all warnings being treated as errors


I think this is a problem for three reasons:
 1. the warning doesn't tell me the location of the problem
 2. worse, the warning name "stringop-overflow" is actively misleading because the code containing the problem isn't using strings
 3. the warning is wrong: AFAIU, it's complaining about `a_size - 2` potentially being a huge unsigned integer due to wrapping below 0 but it's in an else clause that only executes if `a_size >= 3`.

I'm seeing this problem on both GCC 8.0.0 20171130 (Godbolt) and GCC 7.2.0 (my Ubuntu).


Though there are other open bugs relating to this warning:

 * bug 79929
 * bug 82076
 * bug 82103
 * bug 82646

...I'm not sure any cover this issue (eg the first one is about Fortran).

Thanks very much.
Comment 1 Marc Glisse 2017-12-01 11:34:42 UTC
It is strongly related to the other PRs. IMO, all warnings like maybe-uninitialized should move from Wall to Wextra, but that's going to be a hard sell.

In the mean time, we fail to find some VRP optimizations that might help with the warning.

  _1 = _186 + 18446744073709551614;
  if (_1 > _186)

_186: [3, +INF]

Possibly because we haven't turned it into ADD_OVERFLOW yet (or because we are missing a specific transform, or because we have one in match.pd but don't call it, or because !single_use, I didn't check), we don't fold that to false.
Comment 2 Martin Sebor 2017-12-01 20:53:43 UTC
Confirmed (with -O3, the warning doesn't trigger at -O2 for me on x86_64).  There was a similar report last year involving vector (pr79095) that Jeff fixed in r245434.  Either the fix is incomplete or this case is sufficiently different that the fix is not effective.  The invalid memset in this case first also appears in a dump of the ldist pass, same as in pr79095:

  <bb 13> [local count: 357916946]:
  _1 = _17 + 18446744073709551614;
  if (_1 > _17)
    goto <bb 14>; [33.00%]
  else
    goto <bb 30>; [67.00%]

  <bb 14> [local count: 59056296]:
  _83 = a$16_134 - a$8_73;
  _84 = _83 /[ex] 4;
  _85 = (long unsigned int) _84;
  if (_85 > 18446744073709551613)
    goto <bb 42>; [67.00%]
  else
    goto <bb 16>; [33.00%]

  <bb 42> [local count: 39567718]:
  __builtin_memset (a$8_73, 0, 18446744073709551608);

An alternate solution to trying to nail down all these cases in VRP is to recognize calls with these excessive sizes either before they are introduced and avoid introducing them, or afterwards and replace them with a trap.  The patch I had originally submitted for bug 79095 (https://gcc.gnu.org/ml/gcc-patches/2017-01/msg01152.html) does that and it eliminates this warning.

The missing location is due to the code that introduces the memset call neglecting to set the location.

As for the name of the option, its name comes from the String handling section in the C standard which defines both raw memory functions (e.g., memset) and string functions (e.g., strcpy), all of them declared in <string.h>.
Comment 3 Martin Sebor 2017-12-01 20:58:13 UTC
Jeff, do you have a preference for how to handle this?  Should we revisit the trap approach or or try to handle it in VRP (if that's where it breaks down)?
Comment 4 Marc Glisse 2017-12-01 22:26:44 UTC
(In reply to Marc Glisse from comment #1)
> In the mean time, we fail to find some VRP optimizations that might help
> with the warning.
> 
>   _1 = _186 + 18446744073709551614;
>   if (_1 > _186)
> 
> _186: [3, +INF]
> 
> Possibly because we haven't turned it into ADD_OVERFLOW yet (or because we
> are missing a specific transform, or because we have one in match.pd but
> don't call it, or because !single_use, I didn't check), we don't fold that
> to false.

Ah, at some point I wanted to have match.pd optimize _1 > _186 to _186 < 2 (which would then be optimized easily in VRP), but that was breaking Jakub's code to detect ADD_OVERFLOW. Improving that code would be nice. We could also generate ADD_OVERFLOW from match.pd when we see x+n>x, but then I don't think we have code to CSE that with a plain addition, so it wouldn't help.
Comment 5 Jeffrey A. Law 2017-12-05 00:24:53 UTC
This (and pr80641) all feel closely related.  Transforming into a trap early means we're not likely to get these reports which would be unfortunate because they often point to a failing of the optimizer.

I think we should start by figuring out why VRP didn't help us here. From looking at the stuff we've got so far, I'd focus on:

;;   basic block 13, loop depth 1, count 357916946 (estimated locally), maybe hot
;;    prev block 12, next block 14, flags: (NEW, REACHABLE, VISITED)
;;    pred:       3 [50.0% (guessed)]  count:357916948 (estimated locally) (FALSE_VALUE,EXECUTABLE)
  _117 = ASSERT_EXPR <_17, _17 > 2>;
  _1 = _117 + 18446744073709551614;
  if (_1 > _117)
    goto <bb 14>; [33.00%]
  else
    goto <bb 28>; [67.00%]


;;   basic block 14, loop depth 1, count 59056296 (estimated locally), maybe hot
;;   Invalid sum of incoming counts 118112592 (estimated locally), should be 59056296 (estimated locally)
;;    prev block 13, next block 15, flags: (NEW, REACHABLE, VISITED)
;;    pred:       13 [33.0% (guessed)]  count:118112592 (estimated locally) (TRUE_VALUE,EXECUTABLE)
  _185 = ASSERT_EXPR <_1, _1 > _117>;
  _184 = ASSERT_EXPR <_185, _185 > 18446744073709551613>;
  _152 = ASSERT_EXPR <_117, _117 < _184>;
  _40 = ASSERT_EXPR <_152, _152 <= 1>;
  _83 = a$16_134 - a$8_73;
  _84 = _83 /[ex] 4;
  _85 = (long unsigned int) _84;
  if (_85 > 18446744073709551613)
    goto <bb 15>; [67.00%]
  else
    goto <bb 16>; [33.00%]
;;    succ:       15 [67.0% (guessed)]  count:39567718 (estimated locally) (TRUE_VALUE,EXECUTABLE)
;;                16 [33.0% (guessed)]  count:19488578 (estimated locally) (FALSE_VALUE,EXECUTABLE)


The biggest problem I see is we don't know the relationship between a$16_134 and a$8_73 in BB14.  In fact we know nothing about a$16_134 at that point.  So I don't see any way to simplify the conditional at the end of BB14.

The conditional at the end of BB12 is an overflow check.  But we're dealing with unsigned types, so we can't rule out overflow.  But even knowing what direction it took doesn't help us.  So we can't simplify/eliminate it nor use its direction to help.

Note this differs from 79095 because in 79095 we had information about the relationship between the two key pointers -- namely we knew they were not the same.  That allowed us to determine their difference was nonzero and the result of the exact division had to be nonzero as well.  All that played into being able to eventually prove the path leading to the problem memset was not executable.

I don't see anything in this BZ that would allow us to make the same determination here.
Comment 6 Martin Sebor 2017-12-05 04:10:38 UTC
This libstdc++ patch helps avoid both the warning and the bogus memset.  if Jonathan isn't opposed to this kind of annotation I think there might be other places in vector where this approach could improve the emitted object code.

diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index eadce3c..8093f5e 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -582,8 +582,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     {
       if (__n != 0)
 	{
-	  if (size_type(this->_M_impl._M_end_of_storage
-			- this->_M_impl._M_finish) >= __n)
+	  size_type __navail = size_type(this->_M_impl._M_end_of_storage
+					   - this->_M_impl._M_finish);
+
+	  if (__navail > max_size () - size ())
+	    __builtin_unreachable ();
+
+	  if (__navail >= __n)
 	    {
 	      _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
 	      this->_M_impl._M_finish =
Comment 7 Martin Sebor 2017-12-05 04:13:44 UTC
An ever-so-slightly slightly simplified test case (no loop) is the following:

void bar (std::vector<int> &a, int num)
{
  if (num > 0)
    {
      const auto sz = a.size ();

      if (sz < 3)
	a.assign (1, 0);
      else
	a.resize (sz - 2);
  }
}
Comment 8 Jeffrey A. Law 2017-12-05 16:55:12 UTC
Jon's call on the annotation, obviously.

In theory that kind of annotation should be zero cost as there is no code on the __builtin_unreachable path which in turn allows the various optimizers to remove the __builtin_unreachable as well as the controlling condition.

I know from recent work a __builtin_unreachable like this can sneak through the gimple optimizers.  But it was a pretty oddball case involving computed jumps where the computed jump target was an empty __builtin_unreachable block.  Similarly I just fixed a bug where the ranges implied by the __builtin_unreachables were getting lost.

My point for Jon is that while these are supposed to be zero cost ways to describe situations that aren't supposed to happen, a little verification seems wise :-)
Comment 9 Jonathan Wakely 2017-12-05 17:24:32 UTC
(In reply to Martin Sebor from comment #6)
> This libstdc++ patch helps avoid both the warning and the bogus memset.  if
> Jonathan isn't opposed to this kind of annotation I think there might be
> other places in vector where this approach could improve the emitted object
> code.
> 
> diff --git a/libstdc++-v3/include/bits/vector.tcc
> b/libstdc++-v3/include/bits/vector.tcc
> index eadce3c..8093f5e 100644
> --- a/libstdc++-v3/include/bits/vector.tcc
> +++ b/libstdc++-v3/include/bits/vector.tcc
> @@ -582,8 +582,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>      {
>        if (__n != 0)
>  	{
> -	  if (size_type(this->_M_impl._M_end_of_storage
> -			- this->_M_impl._M_finish) >= __n)
> +	  size_type __navail = size_type(this->_M_impl._M_end_of_storage
> +					   - this->_M_impl._M_finish);
> +
> +	  if (__navail > max_size () - size ())
> +	    __builtin_unreachable ();

In principle I'm strongly in favour of adding annotations like this to help the compiler reason about our components like std::vector.

However, this touches on a topic I raised on the LWG reflector last week: what does max_size() mean? What happens if we exceed it?

Here's a program which creates a vector larger than its own max_size()

#include <vector>
#include <cassert>

template<typename T>
struct Alloc {
  using value_type = T;
  template<typename U> struct rebind { using other = Alloc<U>; };
  Alloc() = default;
  template<typename U> Alloc(const Alloc<U>&) { }

  T* allocate(std::size_t n) { return std::allocator<T>().allocate(n); }
  void deallocate(T* p, std::size_t n) { std::allocator<T>().deallocate(p, n); }

  std::size_t max_size() const noexcept { return 100; }
};

template<typename T, typename U>
bool operator==(const Alloc<T>&, const Alloc<U>&) { return true; }
template<typename T, typename U>
bool operator!=(const Alloc<T>&, const Alloc<U>&) { return false; }

int main()
{
  std::vector<int, Alloc<int>> v(Alloc<int>().max_size() + 1);
  assert(v.size() > v.max_size());
}

I think Martin's patch would make this undefined, but the standard doesn't actually say it's undefined to exceed max_size(). So the patch isn't OK.

I think failing to say what happens if you exceed max_size() is a defect in the standard, but maybe it's a bug in our implementation and we need to add extra code to ensure we don't try to grow larger than max_size(). With either of those changes, the patch seems OK to me.
Comment 10 Jonathan Wakely 2017-12-05 19:41:57 UTC
It was pointed out to me that the allocator in my example should not allocate more than its max_size, so the example isn't reasonable. So the invariant in Martin's patch is OK.
Comment 11 Martin Sebor 2017-12-06 03:46:37 UTC
I agree that the standard should say more about when max_size() is used.  I proposed that in LWG 580 but the LWG resolved it as NAD.  It wasn't the first time this came up.  LWG 197 pointed out the underspecification way back in 1999 but the LWG resolved that one as NAD as well.  The latest discussion only highlights that the issue hasn't been put to rest.

Jon, I posted an updated patch for you to consider:
https://gcc.gnu.org/ml/libstdc++/2017-12/msg00023.html
Comment 12 Jeffrey A. Law 2017-12-07 15:04:00 UTC
I was looking at this again tonight, and I clearly missed the interaction between known ranges and the overflow check.

If we look at the .vrp1 dump we see this overflow check in bb16:

23 = ASSERT_EXPR <_13, _13 > 2>;
_1 = _23 + 18446744073709551614;
if (_1 > _23)
  goto <bb 17>; [33.00%]
else
  goto <bb 41>; [67.00%]

This is a controlling condition for the clearing loop which ldist will turn into a memset.

The range for _23 is:

(gdb) p debug_value_range (get_value_range (gimple_cond_rhs (stmt)))
[3, +INF]  EQUIVALENCES: { _13 } (1 elements)

Exactly what we'd expect given the ASSERT_EXPR.  So far so good.

The condition can be rewritten as _23 - 2 > _23, which is only going to be true if _23 has the value 0 or 1.  So we can deduce that the condition is always false.

We're correctly identifying the test as an overflow check in VRP, but we're not optimizing it.  I think we just need to extend vr_values::vrp_evaluate_conditional_warnv_with_ops and the right things should just happen.
Comment 13 Richard Biener 2017-12-11 11:59:42 UTC
(In reply to Jeffrey A. Law from comment #12)
> I was looking at this again tonight, and I clearly missed the interaction
> between known ranges and the overflow check.
> 
> If we look at the .vrp1 dump we see this overflow check in bb16:
> 
> 23 = ASSERT_EXPR <_13, _13 > 2>;
> _1 = _23 + 18446744073709551614;
> if (_1 > _23)
>   goto <bb 17>; [33.00%]
> else
>   goto <bb 41>; [67.00%]
> 
> This is a controlling condition for the clearing loop which ldist will turn
> into a memset.
> 
> The range for _23 is:
> 
> (gdb) p debug_value_range (get_value_range (gimple_cond_rhs (stmt)))
> [3, +INF]  EQUIVALENCES: { _13 } (1 elements)
> 
> Exactly what we'd expect given the ASSERT_EXPR.  So far so good.
> 
> The condition can be rewritten as _23 - 2 > _23, which is only going to be
> true if _23 has the value 0 or 1.  So we can deduce that the condition is
> always false.
> 
> We're correctly identifying the test as an overflow check in VRP, but we're
> not optimizing it.  I think we just need to extend
> vr_values::vrp_evaluate_conditional_warnv_with_ops and the right things
> should just happen.

In fact if we'd do it like EVRP (set SSA_NAME_RANGE_INFO) then IMHO
stmt folding via gimple_fold_stmt_to_constant_1 should handle it
without adding "tricks" to vrp_evaluate_conditional_warnv_with_ops.
That said, this function should likely call match-and-simplify somehow
(note that match.pd lacks a pattern that would simplify the above with
range information).

That said, doing this somewhere more generic (match.pd) might be better,
though VRP not setting range-info during propagation might make things
harder here.
Comment 14 Jeffrey A. Law 2017-12-11 18:40:14 UTC
You *really* don't want to do this with a match.pd pattern.  Recovering the arith-with-overflow optimizations is virtually impossible in the general case.

All that really needs to be done here is generalize existing code that currently handles overflow tests with +-1 to handle them more generically.  In fact doing so actually removes code since we had separate cases for +1 and -1 generating an overflow.
Comment 15 Martin Sebor 2017-12-16 22:37:54 UTC
Author: msebor
Date: Sat Dec 16 22:37:22 2017
New Revision: 255753

URL: https://gcc.gnu.org/viewcvs?rev=255753&root=gcc&view=rev
Log:
PR tree-optimization/83239 - False positive from -Wstringop-overflow
on simple std::vector code

libstdc++/CHangeLog:
	* include/bits/vector.tcc (vector::_M_default_append): Assert
        invariant to generate better code.

gcc/testsuite/ChangeLog:
	* g++.dg/pr83239.C: New test case.

Added:
    trunk/gcc/testsuite/g++.dg/pr83239.C
Modified:
    trunk/gcc/testsuite/ChangeLog
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/vector.tcc
Comment 16 Martin Sebor 2017-12-16 22:41:43 UTC
With the libstdc++ patch committed in r255753 the warning is no longer issued.

Jeff, do you want to keep this open as a reminder to look into the ideas in comment #12 and later?
Comment 17 Christophe Lyon 2017-12-18 11:16:16 UTC
(In reply to Martin Sebor from comment #15)
> Author: msebor
> Date: Sat Dec 16 22:37:22 2017
> New Revision: 255753
> 

Hi,
After this patch, I've noticed a regression on aarch64 and arm:
FAIL:    g++.dg/pr79095-4.C  -std=gnu++11  (test for warnings, line )
FAIL:    g++.dg/pr79095-4.C  -std=gnu++14  (test for warnings, line )
Comment 18 Christophe Lyon 2017-12-18 12:55:48 UTC
(In reply to Christophe Lyon from comment #17)
> (In reply to Martin Sebor from comment #15)
> > Author: msebor
> > Date: Sat Dec 16 22:37:22 2017
> > New Revision: 255753
> > 
> 
> Hi,
> After this patch, I've noticed a regression on aarch64 and arm:
> FAIL:    g++.dg/pr79095-4.C  -std=gnu++11  (test for warnings, line )
> FAIL:    g++.dg/pr79095-4.C  -std=gnu++14  (test for warnings, line )

Which looks like what HJ Lu reported at https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83460
Comment 19 Martin Sebor 2017-12-18 15:53:33 UTC
Right.  Please see  my comment in pr83460.
Comment 20 Jeffrey A. Law 2017-12-18 16:31:46 UTC
Yes.  Very much want to keep this open -- I've got a patch for the missed optimization, but need to recover the tests I'd written and somehow lost before submitting.
Comment 21 Tony E Lewis 2017-12-28 09:14:12 UTC
Many thanks to all for the thought, time and work you're devoting to this issue.
Comment 22 Jonathan Wakely 2018-06-14 14:43:59 UTC
The new trunk/gcc/testsuite/g++.dg/pr83239.C test has started failing, due to a change I made to std::vector, see PR 86153