[PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Martin Sebor]

[-- Attachment #1: Type: text/plain, Size: 424 bytes --]

The test case submitted in bug 79095 - [7 regression] spurious
stringop-overflow warning shows that GCC optimizes some loops
into calls to memset with size arguments in excess of the object
size limit.  Since such calls will unavoidably lead to a buffer
overflow and memory corruption the attached patch detects them
and replaces them with a trap.  That both prevents the buffer
overflow and eliminates the warning.

Martin

[-- Attachment #2: gcc-79095.diff --]
[-- Type: text/x-patch, Size: 4135 bytes --]

PR c++/79095 - [7 regression] spurious stringop-overflow warning

gcc/ChangeLog:

	PR c++/79095
	* tree-loop-distribution.c (maybe_emit_trap): New function.
	(generate_memset_builtin): Call it.
	(generate_memcpy_builtin): Same.

gcc/testsuite/ChangeLog:

	PR c++/79095
	* g++.dg/pr79095.C: New test.

Index: gcc/testsuite/g++.dg/pr79095.C
===================================================================
--- gcc/testsuite/g++.dg/pr79095.C	(revision 0)
+++ gcc/testsuite/g++.dg/pr79095.C	(working copy)
@@ -0,0 +1,41 @@
+/* PR c++/79095 - spurious stringop-overflow warning
+   { dg-do compile }
+   { dg-options "-O3 -Wall -fdump-tree-optimized" } */
+
+typedef long unsigned int size_t;
+
+inline void
+fill (int *p, size_t n, int)
+{
+  while (n--)
+    *p++ = 0;
+}
+
+struct B
+{
+  int* p0, *p1, *p2;
+
+  size_t size () const {
+    return size_t (p1 - p0);
+  }
+
+  void resize (size_t n) {
+    if (n > size())
+      append (n - size());
+  }
+
+  void append (size_t n)
+  {
+    if (size_t (p2 - p1) >= n) {
+      fill (p1, n, 0);
+    }
+  }
+};
+
+void foo (B &b)
+{
+  b.resize (b.size () - 1);
+}
+
+
+/* { dg-final { scan-tree-dump-not "memset" "optimized" } } */
Index: gcc/tree-loop-distribution.c
===================================================================
--- gcc/tree-loop-distribution.c	(revision 244508)
+++ gcc/tree-loop-distribution.c	(working copy)
@@ -796,6 +796,49 @@ const_with_all_bytes_same (tree val)
   return buf[0];
 }
 
+/* If NBYTES is greater than SSIZE_MAX emit a trap and return true.
+   Otherwise return false.  FNCODE identifies the built-in function
+   being generated.  */
+
+static bool
+maybe_emit_trap (gimple_stmt_iterator gsi, tree nbytes,
+		 built_in_function fncode)
+{
+  if (TREE_CODE (nbytes) != INTEGER_CST
+      || tree_int_cst_le (nbytes, TYPE_MAX_VALUE (ssizetype)))
+    return false;
+
+  tree fn = builtin_decl_implicit (BUILT_IN_TRAP);
+  gimple *fn_call = gimple_build_call (fn, 0);
+  gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
+  split_block (gimple_bb (fn_call), fn_call);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      const char *fname = 0;
+
+      switch (fncode)
+	{
+	case BUILT_IN_MEMCPY:
+	  fname = "memcpy";
+	  break;
+	case BUILT_IN_MEMMOVE:
+	  fname = "memove";
+	  break;
+	case BUILT_IN_MEMSET:
+	  fname = "memset";
+	  break;
+	default:
+	  gcc_unreachable ();
+	}
+
+      fprintf (dump_file, "generated trap for an out-of-bounds %s "
+	       "with %wu size", fname, tree_to_uhwi (nbytes));
+    }
+
+  return true;
+}
+
 /* Generate a call to memset for PARTITION in LOOP.  */
 
 static void
@@ -817,6 +860,13 @@ generate_memset_builtin (struct loop *loop, partit
 				 partition->plus_one);
   nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
 				       false, GSI_CONTINUE_LINKING);
+
+  /* If the number of bytes is in excess of SSIZE_MAX avoid generating
+     the memset call that would certainly overflow and emit a trap
+     instead.  */
+  if (maybe_emit_trap (gsi, nb_bytes, BUILT_IN_MEMSET))
+    return;
+
   mem = build_addr_arg_loc (loc, partition->main_dr, nb_bytes);
   mem = force_gimple_operand_gsi (&gsi, mem, true, NULL_TREE,
 				  false, GSI_CONTINUE_LINKING);
@@ -873,6 +923,7 @@ generate_memcpy_builtin (struct loop *loop, partit
 				 partition->plus_one);
   nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
 				       false, GSI_CONTINUE_LINKING);
+
   dest = build_addr_arg_loc (loc, partition->main_dr, nb_bytes);
   src = build_addr_arg_loc (loc, partition->secondary_dr, nb_bytes);
   if (partition->kind == PKIND_MEMCPY
@@ -881,6 +932,12 @@ generate_memcpy_builtin (struct loop *loop, partit
   else
     kind = BUILT_IN_MEMMOVE;
 
+  /* If the number of bytes is in excess of SSIZE_MAX avoid generating
+     the mem(cpy|move) call that would certainly overflow and instead
+     emit a trap.  */
+  if (maybe_emit_trap (gsi, nb_bytes, kind))
+    return;
+
   dest = force_gimple_operand_gsi (&gsi, dest, true, NULL_TREE,
 				   false, GSI_CONTINUE_LINKING);
   src = force_gimple_operand_gsi (&gsi, src, true, NULL_TREE,

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Jakub Jelinek]

On Mon, Jan 16, 2017 at 05:06:40PM -0700, Martin Sebor wrote:
> The test case submitted in bug 79095 - [7 regression] spurious
> stringop-overflow warning shows that GCC optimizes some loops
> into calls to memset with size arguments in excess of the object
> size limit.  Since such calls will unavoidably lead to a buffer
> overflow and memory corruption the attached patch detects them
> and replaces them with a trap.  That both prevents the buffer
> overflow and eliminates the warning.

I fear this is going to break various 32-bit database programs and similar
that mmap say 3GB of RAM and then work on that memory chunk as contiguous.
Some things don't work too well in that case (pointer differences), but it
is unlikely they would be using those, while your patch actively breaks it
even for loops that can be transformed into memset (memcpy of course isn't a
problem, because you need some virtual address space to copy it from).

And as written in the PR, IMNSHO the warning should not be enabled by
default at its current verboseness and false positive rate.

	Jakub

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Martin Sebor]

On 01/17/2017 12:38 AM, Jakub Jelinek wrote:
> On Mon, Jan 16, 2017 at 05:06:40PM -0700, Martin Sebor wrote:
>> The test case submitted in bug 79095 - [7 regression] spurious
>> stringop-overflow warning shows that GCC optimizes some loops
>> into calls to memset with size arguments in excess of the object
>> size limit.  Since such calls will unavoidably lead to a buffer
>> overflow and memory corruption the attached patch detects them
>> and replaces them with a trap.  That both prevents the buffer
>> overflow and eliminates the warning.
>
> I fear this is going to break various 32-bit database programs and similar
> that mmap say 3GB of RAM and then work on that memory chunk as contiguous.
> Some things don't work too well in that case (pointer differences), but it
> is unlikely they would be using those, while your patch actively breaks it
> even for loops that can be transformed into memset (memcpy of course isn't a
> problem, because you need some virtual address space to copy it from).

I agree that breaking those applications would be bad.  It could
be dealt with by adding an option to let them disable the insertion
of the trap.  With the warning, programmers would get a heads up
that their (already dubious) code won't work otherwise.  I don't
think it's a necessary or wise to have the default mode be the most
permissive (and most dangerous) and expect users to tweak options
to make it safe.  Rather, I would argue that it should be the other
way around.  Make the default safe and strict and let the advanced
users who know how deal with the risks tweak those options.

Martin

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Jeff Law]

On 01/17/2017 08:16 PM, Martin Sebor wrote:
> On 01/17/2017 12:38 AM, Jakub Jelinek wrote:
>> On Mon, Jan 16, 2017 at 05:06:40PM -0700, Martin Sebor wrote:
>>> The test case submitted in bug 79095 - [7 regression] spurious
>>> stringop-overflow warning shows that GCC optimizes some loops
>>> into calls to memset with size arguments in excess of the object
>>> size limit.  Since such calls will unavoidably lead to a buffer
>>> overflow and memory corruption the attached patch detects them
>>> and replaces them with a trap.  That both prevents the buffer
>>> overflow and eliminates the warning.
>>
>> I fear this is going to break various 32-bit database programs and
>> similar
>> that mmap say 3GB of RAM and then work on that memory chunk as
>> contiguous.
>> Some things don't work too well in that case (pointer differences),
>> but it
>> is unlikely they would be using those, while your patch actively
>> breaks it
>> even for loops that can be transformed into memset (memcpy of course
>> isn't a
>> problem, because you need some virtual address space to copy it from).
>
> I agree that breaking those applications would be bad.  It could
> be dealt with by adding an option to let them disable the insertion
> of the trap.  With the warning, programmers would get a heads up
> that their (already dubious) code won't work otherwise.  I don't
> think it's a necessary or wise to have the default mode be the most
> permissive (and most dangerous) and expect users to tweak options
> to make it safe.  Rather, I would argue that it should be the other
> way around.  Make the default safe and strict and let the advanced
> users who know how deal with the risks tweak those options.
I still come back to the assertion that changing this loop to a mem* is 
fundamentally the wrong thing to do as it changes something that has 
well defined semantics to something that is invalid.

Thus the transformation into a mem* call is invalid.
jeff

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Jakub Jelinek]

On Tue, Jan 17, 2017 at 10:59:43PM -0700, Jeff Law wrote:
> > I agree that breaking those applications would be bad.  It could
> > be dealt with by adding an option to let them disable the insertion
> > of the trap.  With the warning, programmers would get a heads up
> > that their (already dubious) code won't work otherwise.  I don't
> > think it's a necessary or wise to have the default mode be the most
> > permissive (and most dangerous) and expect users to tweak options
> > to make it safe.  Rather, I would argue that it should be the other
> > way around.  Make the default safe and strict and let the advanced
> > users who know how deal with the risks tweak those options.
> I still come back to the assertion that changing this loop to a mem* is
> fundamentally the wrong thing to do as it changes something that has well
> defined semantics to something that is invalid.
> 
> Thus the transformation into a mem* call is invalid.

The mem* call is as valid as the loop, it will work exactly the same.
If you have say on 32-bit target
#include <stdlib.h>

int
main ()
{
  char *p = malloc (3U * 1024 * 1024 * 1024);
  if (p == NULL)
    return 0;
  size_t i;
  for (i = 0; i < 3U * 1024 * 1024 * 1024; i++)
    p[i] = 6;
  use (p);
  return 0;
}

then the loop does the same thing as will memset (p, 6, 3U * 1024 * 1024 * 1024);
do.  On such large objects some operations may not work properly, e.g.
&p[i] - &p[0] might be negative etc., but that is not something the above
loop does or memset will do internally.  If the loop doesn't use just 3/4 of
the address space, but much more, e.g. more than whole address space minus
one page, which is what happens in the testcase, it is indeed quite sure it
will crash if invoked, but the problem with the warning is the same with
many other late warnings or warnings excessively using VRP etc.
If we are given
void
foo (char *p, size_t len)
{
  memset (p, '\0', len);
}
then it also can invoke UB if somebody calls it with a huge len
(~(size_t)0), but we rightly don't want to warn because we can't prove it
will be called with that.  If some unrelated or related test somewhere else
makes the value range smaller on some path or turns it constant on some
path, the warning does warn, even when there is a sometimes low, sometimes
very high possibility the warning is on dead code.
Which is why IMHO it is a very bad idea to enable this warning by default
even without any -W* option, it just has too many false positives.
Turning extra large memcpy (as memcpy can't have overlap in between the
objects, already starting from half of address space is fine; for memset
I'd think only for something like -4096 or something similar that is just
unlikely in hosted environment to be a single object) into a trap or
unreachable might be a nice optimization and allow optimizing away code that
would follow the spot that would always crash.  But with warning above it
the problem is that it is hard to figure out if it is reachable or not.

	Jakub

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Martin Sebor]

On 01/18/2017 01:10 AM, Jakub Jelinek wrote:
> On Tue, Jan 17, 2017 at 10:59:43PM -0700, Jeff Law wrote:
>>> I agree that breaking those applications would be bad.  It could
>>> be dealt with by adding an option to let them disable the insertion
>>> of the trap.  With the warning, programmers would get a heads up
>>> that their (already dubious) code won't work otherwise.  I don't
>>> think it's a necessary or wise to have the default mode be the most
>>> permissive (and most dangerous) and expect users to tweak options
>>> to make it safe.  Rather, I would argue that it should be the other
>>> way around.  Make the default safe and strict and let the advanced
>>> users who know how deal with the risks tweak those options.
>> I still come back to the assertion that changing this loop to a mem* is
>> fundamentally the wrong thing to do as it changes something that has well
>> defined semantics to something that is invalid.
>>
>> Thus the transformation into a mem* call is invalid.
>
> The mem* call is as valid as the loop, it will work exactly the same.

The problem here isn't the loop itself or the memset call but the
bounds computed from the inputs.

In the test case submitted with the bug the inputs supplied by
the program are well within a valid range, yet the bounds of
the loop that are computed by GCC from those inputs are excessive
because they are based on impossible ranges (or an incomplete view
of the program).

There is no unbounded loop in

   void f(std::vector<int> &v)
   {
     size_t n = v.size ();

     if (n > 1 && n < 5)
       v.resize (n - 1);
   }

yet GCC synthesizes one:

   void f(std::vector<int>&) (struct vector & v)
   {
     ...
     <bb 2> [100.00%]:
     _7 = MEM[(int * *)v_5(D)];             // v._M_impl._M_start
     _8 = MEM[(int * *)v_5(D) + 8B];        // v._M_impl._M_finish
     _9 = (long int) _8;
     _10 = (long int) _7;
     _11 = _9 - _10;
     _12 = _11 /[ex] 4;
     _13 = (long unsigned int) _12;         // v.size()
     _1 = _13 + 18446744073709551614;       // v.size() - 4
     if (_1 <= 2)                           // if (v.size() <= 6)
       goto <bb 3>; [36.64%]
     else
       goto <bb 9>; [63.36%]

     <bb 3> [36.64%]:
     _2 = _13 + 18446744073709551615;       // v.size() - 1
     if (_2 > _13)                          // if (v.size() == 0)
       goto <bb 4>; [29.56%]                //   this can't happen
     else
       goto <bb 7>; [70.44%]

     <bb 4> [5.85%]:
     _24 = v_5(D)->D.15828._M_impl._M_end_of_storage;
     _25 = (long int) _24;
     _28 = _25 - _9;                        // bytes left
     if (_28 == -4)                         // this can't happen
       goto <bb 5>; [67.00%]
     else
       goto <bb 6>; [33.00%]

     <bb 5> [3.92%]:
     __builtin_memset (_8, 0, 18446744073709551612);   // (size_t)-4
     ...

     <bb 6> [1.93%]:
     std::__throw_length_error ("vector::_M_default_append");

> If you have say on 32-bit target
> #include <stdlib.h>
>
> int
> main ()
> {
>   char *p = malloc (3U * 1024 * 1024 * 1024);
>   if (p == NULL)
>     return 0;
>   size_t i;
>   for (i = 0; i < 3U * 1024 * 1024 * 1024; i++)
>     p[i] = 6;
>   use (p);
>   return 0;
> }

Unlike in the test case submitted with the bug, here the loop is in
the source and warning on it would be justified for most programs.

Here's a test case that's closer to the one from the bug.  It also
ends up with the out of bounds memset even at -O1, during PRE.

typedef __SIZE_TYPE__ size_t;

struct S
   int *p0, *p1, *p2;

   size_t size () const { return p1 - p0; }

   void f (size_t n) {
     if (n > size ())       // can't happen because
       foo (n - size ());   //   n is in [1, MIN(size() - 1, 3)]
     else if (n < size ())
       bar (p0 + n);
   }

   void foo (size_t n)
   {
     size_t left = (size_t)(p2 - p1);
     if (left >= n)
       __builtin_memset (p2, 0, n * sizeof *p2);
   }

   void bar (int*);
};

void f (S &s)
{
   size_t n = s.size ();
   if (n > 1 && n < 5)
     s.f (n - 1);
}

Martin

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Jeff Law]

On 01/18/2017 10:45 AM, Martin Sebor wrote:
> On 01/18/2017 01:10 AM, Jakub Jelinek wrote:
>> On Tue, Jan 17, 2017 at 10:59:43PM -0700, Jeff Law wrote:
>>>> I agree that breaking those applications would be bad.  It could
>>>> be dealt with by adding an option to let them disable the insertion
>>>> of the trap.  With the warning, programmers would get a heads up
>>>> that their (already dubious) code won't work otherwise.  I don't
>>>> think it's a necessary or wise to have the default mode be the most
>>>> permissive (and most dangerous) and expect users to tweak options
>>>> to make it safe.  Rather, I would argue that it should be the other
>>>> way around.  Make the default safe and strict and let the advanced
>>>> users who know how deal with the risks tweak those options.
>>> I still come back to the assertion that changing this loop to a mem* is
>>> fundamentally the wrong thing to do as it changes something that has
>>> well
>>> defined semantics to something that is invalid.
>>>
>>> Thus the transformation into a mem* call is invalid.
>>
>> The mem* call is as valid as the loop, it will work exactly the same.
>
> The problem here isn't the loop itself or the memset call but the
> bounds computed from the inputs.
Sorry.  My bad.  Only memcpy has the SIZE_MAX / 2 restriction.

[ ... ]
Going to work from the self-contained test...


>
> Here's a test case that's closer to the one from the bug.  It also
> ends up with the out of bounds memset even at -O1, during PRE.
>
> typedef __SIZE_TYPE__ size_t;
>
> struct S
>   int *p0, *p1, *p2;
>
>   size_t size () const { return p1 - p0; }
>
>   void f (size_t n) {
>     if (n > size ())       // can't happen because
>       foo (n - size ());   //   n is in [1, MIN(size() - 1, 3)]
>     else if (n < size ())
>       bar (p0 + n);
>   }
>
>   void foo (size_t n)
>   {
>     size_t left = (size_t)(p2 - p1);
>     if (left >= n)
>       __builtin_memset (p2, 0, n * sizeof *p2);
>   }
>
>   void bar (int*);
> };
>
> void f (S &s)
> {
>   size_t n = s.size ();
>   if (n > 1 && n < 5)
>     s.f (n - 1);
> }


Looking at the .vrp1 dump for this test we find:

;;   basic block 3, loop depth 0, count 0, freq 3664, maybe hot
;;    prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
;;    pred:       2 [36.6%]  (TRUE_VALUE,EXECUTABLE)
   _18 = ASSERT_EXPR <_13, _13 + 18446744073709551614 <= 2>;
   _2 = _18 + 18446744073709551615;
   if (_2 > _18)
     goto <bb 4>; [50.00%]
   else
     goto <bb 6>; [50.00%]

_2 > _18 is the same as

(_18 - 1) > _18

Which is only true if _18 is zero.  And since _18 has a computed range 
of [2..4], that can never happen.

VRP doesn't currently handle this case, though we do have some code to 
turn relational comparisons into equality comparisons.  If I manually 
turn the relational into _18 == 0 at that point, then the next VRP pass 
is able to optimize the conditional away which in turn eliminates the 
problematical memset call & warning.

So one possible approach would be to treat simplify_cond_using_ranges to 
simplify that kind of condition.  I don't know if that would fix the 
reported testcase as I haven't looked at it directly under the debugger yet.



Jeff

A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Jeff Law]

On 01/20/2017 04:30 PM, Jeff Law wrote:
> Going to work from the self-contained test...
>
>
>>
>> Here's a test case that's closer to the one from the bug.  It also
>> ends up with the out of bounds memset even at -O1, during PRE.
>>
>> typedef __SIZE_TYPE__ size_t;
>>
>> struct S
>>   int *p0, *p1, *p2;
>>
>>   size_t size () const { return p1 - p0; }
>>
>>   void f (size_t n) {
>>     if (n > size ())       // can't happen because
>>       foo (n - size ());   //   n is in [1, MIN(size() - 1, 3)]
>>     else if (n < size ())
>>       bar (p0 + n);
>>   }
>>
>>   void foo (size_t n)
>>   {
>>     size_t left = (size_t)(p2 - p1);
>>     if (left >= n)
>>       __builtin_memset (p2, 0, n * sizeof *p2);
>>   }
>>
>>   void bar (int*);
>> };
>>
>> void f (S &s)
>> {
>>   size_t n = s.size ();
>>   if (n > 1 && n < 5)
>>     s.f (n - 1);
>> }
>
>
> Looking at the .vrp1 dump for this test we find:
>
> ;;   basic block 3, loop depth 0, count 0, freq 3664, maybe hot
> ;;    prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
> ;;    pred:       2 [36.6%]  (TRUE_VALUE,EXECUTABLE)
>   _18 = ASSERT_EXPR <_13, _13 + 18446744073709551614 <= 2>;
>   _2 = _18 + 18446744073709551615;
>   if (_2 > _18)
>     goto <bb 4>; [50.00%]
>   else
>     goto <bb 6>; [50.00%]
>
> _2 > _18 is the same as
>
> (_18 - 1) > _18
>
> Which is only true if _18 is zero.  And since _18 has a computed range
> of [2..4], that can never happen.
>
> VRP doesn't currently handle this case, though we do have some code to
> turn relational comparisons into equality comparisons.  If I manually
> turn the relational into _18 == 0 at that point, then the next VRP pass
> is able to optimize the conditional away which in turn eliminates the
> problematical memset call & warning.
>
> So one possible approach would be to treat simplify_cond_using_ranges to
> simplify that kind of condition.  I don't know if that would fix the
> reported testcase as I haven't looked at it directly under the debugger
> yet.
In fact, match.pd already has a pattern to handle a relational like
(X + -1) > X

The pattern doesn't fire because of a single_use guard.   This was 
discussed back in 2015 with Jakub advocating for a single_use guard, but 
Marc leaning the other direction, but not enough to argue too much about it.

In early 2016 Marc actually submitted the match.pd patch with the single 
use guard per Jakub's preference.

The single use guard checks the SSA_NAME holding the (X + CST) 
expression for single use.   It's not entirely clear why we check for 
single use.  If it's because of object lifetimes, then that's a total 
red herring here.

Given something like:
x = a + c
if (a > x)

The transformation into

x = a + c;
if (a < c')

Where x has multiple uses, the transformation will not inherently change 
the lifetime of "x" worse (if the conditional was the last use, then the 
lifetime of x may shorten somewhat).  If there were uses after the 
condition, the lifetime of "x" remains unchanged.

"a" was already live from the assignment to at least the conditional. 
But again, we haven't inherently changed its lifetime.

However, what can happen is after transformation, the assignment might 
sink to a later use point in the CFG, which might lengthen the lifetime 
of "a", but it's also shortening the lifetime of "x" by the same amount.

So, ultimately I don't buy the argument that we should inhibit this 
based on register lifetime issues.

Jakub, perhaps you remember why you wanted this restricted to cases 
where "x" has a single use?

Certainly the easiest thing to do is remove the single use restriction. 
If we ultimately don't want to do that, we can probably detect when the 
transformation will allow the conditional to be eliminated in VRP and I 
would claim that elimination of the conditional at compile time trumps 
the other potential concerns here.  That's going to be uglier and 
essentially duplicate parts of what match.pd does, but certainly doable 
-- I've even prototyped it.

Thoughts?

jeff

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Marc Glisse]

On Fri, 20 Jan 2017, Jeff Law wrote:

> On 01/20/2017 04:30 PM, Jeff Law wrote:
>> Going to work from the self-contained test...
>> 
>> 
>>> 
>>> Here's a test case that's closer to the one from the bug.  It also
>>> ends up with the out of bounds memset even at -O1, during PRE.
>>> 
>>> typedef __SIZE_TYPE__ size_t;
>>> 
>>> struct S
>>>   int *p0, *p1, *p2;
>>>
>>>   size_t size () const { return p1 - p0; }
>>>
>>>   void f (size_t n) {
>>>     if (n > size ())       // can't happen because
>>>       foo (n - size ());   //   n is in [1, MIN(size() - 1, 3)]
>>>     else if (n < size ())
>>>       bar (p0 + n);
>>>   }
>>>
>>>   void foo (size_t n)
>>>   {
>>>     size_t left = (size_t)(p2 - p1);
>>>     if (left >= n)
>>>       __builtin_memset (p2, 0, n * sizeof *p2);
>>>   }
>>>
>>>   void bar (int*);
>>> };
>>> 
>>> void f (S &s)
>>> {
>>>   size_t n = s.size ();
>>>   if (n > 1 && n < 5)
>>>     s.f (n - 1);
>>> }
>> 
>> 
>> Looking at the .vrp1 dump for this test we find:
>> 
>> ;;   basic block 3, loop depth 0, count 0, freq 3664, maybe hot
>> ;;    prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
>> ;;    pred:       2 [36.6%]  (TRUE_VALUE,EXECUTABLE)
>>   _18 = ASSERT_EXPR <_13, _13 + 18446744073709551614 <= 2>;
>>   _2 = _18 + 18446744073709551615;
>>   if (_2 > _18)
>>     goto <bb 4>; [50.00%]
>>   else
>>     goto <bb 6>; [50.00%]
>> 
>> _2 > _18 is the same as
>> 
>> (_18 - 1) > _18
>> 
>> Which is only true if _18 is zero.  And since _18 has a computed range
>> of [2..4], that can never happen.
>> 
>> VRP doesn't currently handle this case, though we do have some code to
>> turn relational comparisons into equality comparisons.  If I manually
>> turn the relational into _18 == 0 at that point, then the next VRP pass
>> is able to optimize the conditional away which in turn eliminates the
>> problematical memset call & warning.
>> 
>> So one possible approach would be to treat simplify_cond_using_ranges to
>> simplify that kind of condition.  I don't know if that would fix the
>> reported testcase as I haven't looked at it directly under the debugger
>> yet.
> In fact, match.pd already has a pattern to handle a relational like
> (X + -1) > X
>
> The pattern doesn't fire because of a single_use guard.   This was discussed 
> back in 2015 with Jakub advocating for a single_use guard, but Marc leaning 
> the other direction, but not enough to argue too much about it.
>
> In early 2016 Marc actually submitted the match.pd patch with the single use 
> guard per Jakub's preference.
>
> The single use guard checks the SSA_NAME holding the (X + CST) expression for 
> single use.   It's not entirely clear why we check for single use.  If it's 
> because of object lifetimes, then that's a total red herring here.
>
> Given something like:
> x = a + c
> if (a > x)
>
> The transformation into
>
> x = a + c;
> if (a < c')
>
> Where x has multiple uses, the transformation will not inherently change the 
> lifetime of "x" worse (if the conditional was the last use, then the lifetime 
> of x may shorten somewhat).  If there were uses after the condition, the 
> lifetime of "x" remains unchanged.

I don't remember the conversation and I don't have experience with 
register pressure. My assumption would be that the issue is with the new 
constant c'. In the first case, during the comparison, only a and x are 
alive, while in the second case, c' is as well, which may use an extra 
register. Does that make sense?

(I don't know if that's bad enough to inhibit the simplification)

Or are we talking about the transformation that has this comment in 
match.pd:

    Currently restricted to single use so as not to interfere too much with
    ADD_OVERFLOW detection in tree-ssa-math-opts.c.

That detection logic needs to be improved anyway (see also a discussion 
with Vincent Lefevre yesterday on gcc-help, users do write the simplified 
form directly), the single_use is supposedly only there until that is done 
(really depends on how well the improved logic works...).

> "a" was already live from the assignment to at least the conditional. But 
> again, we haven't inherently changed its lifetime.
>
> However, what can happen is after transformation, the assignment might sink 
> to a later use point in the CFG, which might lengthen the lifetime of "a", 
> but it's also shortening the lifetime of "x" by the same amount.
>
> So, ultimately I don't buy the argument that we should inhibit this based on 
> register lifetime issues.
>
> Jakub, perhaps you remember why you wanted this restricted to cases where "x" 
> has a single use?
>
> Certainly the easiest thing to do is remove the single use restriction. If we 
> ultimately don't want to do that, we can probably detect when the 
> transformation will allow the conditional to be eliminated in VRP and I would 
> claim that elimination of the conditional at compile time trumps the other 
> potential concerns here.  That's going to be uglier and essentially duplicate 
> parts of what match.pd does, but certainly doable -- I've even prototyped 
> it.
>
> Thoughts?

I believe we are supposed to call match.pd from VRP eventually (though 
that may not have happened yet), so the test could probably also be done 
there, if that looks more convenient and we decide not to remove 
single_use completely for this transformation.

-- 
Marc Glisse

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Jeff Law]

On 01/21/2017 01:00 AM, Marc Glisse wrote:
> On Fri, 20 Jan 2017, Jeff Law wrote:
>
>> On 01/20/2017 04:30 PM, Jeff Law wrote:
>>> Going to work from the self-contained test...
>>>
>>>
>>>>
>>>> Here's a test case that's closer to the one from the bug.  It also
>>>> ends up with the out of bounds memset even at -O1, during PRE.
>>>>
>>>> typedef __SIZE_TYPE__ size_t;
>>>>
>>>> struct S
>>>>   int *p0, *p1, *p2;
>>>>
>>>>   size_t size () const { return p1 - p0; }
>>>>
>>>>   void f (size_t n) {
>>>>     if (n > size ())       // can't happen because
>>>>       foo (n - size ());   //   n is in [1, MIN(size() - 1, 3)]
>>>>     else if (n < size ())
>>>>       bar (p0 + n);
>>>>   }
>>>>
>>>>   void foo (size_t n)
>>>>   {
>>>>     size_t left = (size_t)(p2 - p1);
>>>>     if (left >= n)
>>>>       __builtin_memset (p2, 0, n * sizeof *p2);
>>>>   }
>>>>
>>>>   void bar (int*);
>>>> };
>>>>
>>>> void f (S &s)
>>>> {
>>>>   size_t n = s.size ();
>>>>   if (n > 1 && n < 5)
>>>>     s.f (n - 1);
>>>> }
>>>
>>>
>>> Looking at the .vrp1 dump for this test we find:
>>>
>>> ;;   basic block 3, loop depth 0, count 0, freq 3664, maybe hot
>>> ;;    prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
>>> ;;    pred:       2 [36.6%]  (TRUE_VALUE,EXECUTABLE)
>>>   _18 = ASSERT_EXPR <_13, _13 + 18446744073709551614 <= 2>;
>>>   _2 = _18 + 18446744073709551615;
>>>   if (_2 > _18)
>>>     goto <bb 4>; [50.00%]
>>>   else
>>>     goto <bb 6>; [50.00%]
>>>
>>> _2 > _18 is the same as
>>>
>>> (_18 - 1) > _18
>>>
>>> Which is only true if _18 is zero.  And since _18 has a computed range
>>> of [2..4], that can never happen.
>>>
>>> VRP doesn't currently handle this case, though we do have some code to
>>> turn relational comparisons into equality comparisons.  If I manually
>>> turn the relational into _18 == 0 at that point, then the next VRP pass
>>> is able to optimize the conditional away which in turn eliminates the
>>> problematical memset call & warning.
>>>
>>> So one possible approach would be to treat simplify_cond_using_ranges to
>>> simplify that kind of condition.  I don't know if that would fix the
>>> reported testcase as I haven't looked at it directly under the debugger
>>> yet.
>> In fact, match.pd already has a pattern to handle a relational like
>> (X + -1) > X
>>
>> The pattern doesn't fire because of a single_use guard.   This was
>> discussed back in 2015 with Jakub advocating for a single_use guard,
>> but Marc leaning the other direction, but not enough to argue too much
>> about it.
>>
>> In early 2016 Marc actually submitted the match.pd patch with the
>> single use guard per Jakub's preference.
>>
>> The single use guard checks the SSA_NAME holding the (X + CST)
>> expression for single use.   It's not entirely clear why we check for
>> single use.  If it's because of object lifetimes, then that's a total
>> red herring here.
>>
>> Given something like:
>> x = a + c
>> if (a > x)
>>
>> The transformation into
>>
>> x = a + c;
>> if (a < c')
>>
>> Where x has multiple uses, the transformation will not inherently
>> change the lifetime of "x" worse (if the conditional was the last use,
>> then the lifetime of x may shorten somewhat).  If there were uses
>> after the condition, the lifetime of "x" remains unchanged.
>
> I don't remember the conversation and I don't have experience with
> register pressure. My assumption would be that the issue is with the new
> constant c'. In the first case, during the comparison, only a and x are
> alive, while in the second case, c' is as well, which may use an extra
> register. Does that make sense?
>
> (I don't know if that's bad enough to inhibit the simplification)
>
> Or are we talking about the transformation that has this comment in
> match.pd:
>
>    Currently restricted to single use so as not to interfere too much with
>    ADD_OVERFLOW detection in tree-ssa-math-opts.c.
>
> That detection logic needs to be improved anyway (see also a discussion
> with Vincent Lefevre yesterday on gcc-help, users do write the
> simplified form directly), the single_use is supposedly only there until
> that is done (really depends on how well the improved logic works...).
>
>> "a" was already live from the assignment to at least the conditional.
>> But again, we haven't inherently changed its lifetime.
>>
>> However, what can happen is after transformation, the assignment might
>> sink to a later use point in the CFG, which might lengthen the
>> lifetime of "a", but it's also shortening the lifetime of "x" by the
>> same amount.
>>
>> So, ultimately I don't buy the argument that we should inhibit this
>> based on register lifetime issues.
>>
>> Jakub, perhaps you remember why you wanted this restricted to cases
>> where "x" has a single use?
So I went and looked at the match_uaddsub_overflow bits for a while. 
AFAICT it appears to be trying to allow us to do the arithmetic and 
overflow status computation once and CSE the result.  At the single 
instance we would generate a uaddv4 insn which does the arithmetic and jump.

ISTM the real value here is in the initial RTL generation.  DOM ought to 
be simplifying the arithmetic CSEs and dominated tests.  Threading 
should pick up the most common non-dominated tests.

Converting into an EQ/NE test against zero for the special case should 
still preserve those optimizations (and in fact makes the threading 
easier to discover).

So it's really a matter of do we do it directly in VRP, or in match.pd. 
The former is more effective, the latter is cleaner.
>
> I believe we are supposed to call match.pd from VRP eventually (though
> that may not have happened yet), so the test could probably also be done
> there, if that looks more convenient and we decide not to remove
> single_use completely for this transformation.
That was my thought as well, but AFAICT we only call into match.pd from 
VRP if we changed the insn.   There's no systematic calling into 
match.pd from most passes.  Thus, we don't do the transformation until 
fairly late in the pipeline when it's in match.pd.

Jeff

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Richard Biener]

On Tue, Jan 24, 2017 at 1:03 AM, Jeff Law <law@redhat.com> wrote:
> On 01/21/2017 01:00 AM, Marc Glisse wrote:
>>
>> On Fri, 20 Jan 2017, Jeff Law wrote:
>>
>>> On 01/20/2017 04:30 PM, Jeff Law wrote:
>>>>
>>>> Going to work from the self-contained test...
>>>>
>>>>
>>>>>
>>>>> Here's a test case that's closer to the one from the bug.  It also
>>>>> ends up with the out of bounds memset even at -O1, during PRE.
>>>>>
>>>>> typedef __SIZE_TYPE__ size_t;
>>>>>
>>>>> struct S
>>>>>   int *p0, *p1, *p2;
>>>>>
>>>>>   size_t size () const { return p1 - p0; }
>>>>>
>>>>>   void f (size_t n) {
>>>>>     if (n > size ())       // can't happen because
>>>>>       foo (n - size ());   //   n is in [1, MIN(size() - 1, 3)]
>>>>>     else if (n < size ())
>>>>>       bar (p0 + n);
>>>>>   }
>>>>>
>>>>>   void foo (size_t n)
>>>>>   {
>>>>>     size_t left = (size_t)(p2 - p1);
>>>>>     if (left >= n)
>>>>>       __builtin_memset (p2, 0, n * sizeof *p2);
>>>>>   }
>>>>>
>>>>>   void bar (int*);
>>>>> };
>>>>>
>>>>> void f (S &s)
>>>>> {
>>>>>   size_t n = s.size ();
>>>>>   if (n > 1 && n < 5)
>>>>>     s.f (n - 1);
>>>>> }
>>>>
>>>>
>>>>
>>>> Looking at the .vrp1 dump for this test we find:
>>>>
>>>> ;;   basic block 3, loop depth 0, count 0, freq 3664, maybe hot
>>>> ;;    prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
>>>> ;;    pred:       2 [36.6%]  (TRUE_VALUE,EXECUTABLE)
>>>>   _18 = ASSERT_EXPR <_13, _13 + 18446744073709551614 <= 2>;
>>>>   _2 = _18 + 18446744073709551615;
>>>>   if (_2 > _18)
>>>>     goto <bb 4>; [50.00%]
>>>>   else
>>>>     goto <bb 6>; [50.00%]
>>>>
>>>> _2 > _18 is the same as
>>>>
>>>> (_18 - 1) > _18
>>>>
>>>> Which is only true if _18 is zero.  And since _18 has a computed range
>>>> of [2..4], that can never happen.
>>>>
>>>> VRP doesn't currently handle this case, though we do have some code to
>>>> turn relational comparisons into equality comparisons.  If I manually
>>>> turn the relational into _18 == 0 at that point, then the next VRP pass
>>>> is able to optimize the conditional away which in turn eliminates the
>>>> problematical memset call & warning.
>>>>
>>>> So one possible approach would be to treat simplify_cond_using_ranges to
>>>> simplify that kind of condition.  I don't know if that would fix the
>>>> reported testcase as I haven't looked at it directly under the debugger
>>>> yet.
>>>
>>> In fact, match.pd already has a pattern to handle a relational like
>>> (X + -1) > X
>>>
>>> The pattern doesn't fire because of a single_use guard.   This was
>>> discussed back in 2015 with Jakub advocating for a single_use guard,
>>> but Marc leaning the other direction, but not enough to argue too much
>>> about it.
>>>
>>> In early 2016 Marc actually submitted the match.pd patch with the
>>> single use guard per Jakub's preference.
>>>
>>> The single use guard checks the SSA_NAME holding the (X + CST)
>>> expression for single use.   It's not entirely clear why we check for
>>> single use.  If it's because of object lifetimes, then that's a total
>>> red herring here.
>>>
>>> Given something like:
>>> x = a + c
>>> if (a > x)
>>>
>>> The transformation into
>>>
>>> x = a + c;
>>> if (a < c')
>>>
>>> Where x has multiple uses, the transformation will not inherently
>>> change the lifetime of "x" worse (if the conditional was the last use,
>>> then the lifetime of x may shorten somewhat).  If there were uses
>>> after the condition, the lifetime of "x" remains unchanged.
>>
>>
>> I don't remember the conversation and I don't have experience with
>> register pressure. My assumption would be that the issue is with the new
>> constant c'. In the first case, during the comparison, only a and x are
>> alive, while in the second case, c' is as well, which may use an extra
>> register. Does that make sense?
>>
>> (I don't know if that's bad enough to inhibit the simplification)
>>
>> Or are we talking about the transformation that has this comment in
>> match.pd:
>>
>>    Currently restricted to single use so as not to interfere too much with
>>    ADD_OVERFLOW detection in tree-ssa-math-opts.c.
>>
>> That detection logic needs to be improved anyway (see also a discussion
>> with Vincent Lefevre yesterday on gcc-help, users do write the
>> simplified form directly), the single_use is supposedly only there until
>> that is done (really depends on how well the improved logic works...).
>>
>>> "a" was already live from the assignment to at least the conditional.
>>> But again, we haven't inherently changed its lifetime.
>>>
>>> However, what can happen is after transformation, the assignment might
>>> sink to a later use point in the CFG, which might lengthen the
>>> lifetime of "a", but it's also shortening the lifetime of "x" by the
>>> same amount.
>>>
>>> So, ultimately I don't buy the argument that we should inhibit this
>>> based on register lifetime issues.
>>>
>>> Jakub, perhaps you remember why you wanted this restricted to cases
>>> where "x" has a single use?
>
> So I went and looked at the match_uaddsub_overflow bits for a while. AFAICT
> it appears to be trying to allow us to do the arithmetic and overflow status
> computation once and CSE the result.  At the single instance we would
> generate a uaddv4 insn which does the arithmetic and jump.
>
> ISTM the real value here is in the initial RTL generation.  DOM ought to be
> simplifying the arithmetic CSEs and dominated tests.  Threading should pick
> up the most common non-dominated tests.
>
> Converting into an EQ/NE test against zero for the special case should still
> preserve those optimizations (and in fact makes the threading easier to
> discover).
>
> So it's really a matter of do we do it directly in VRP, or in match.pd. The
> former is more effective, the latter is cleaner.
>>
>>
>> I believe we are supposed to call match.pd from VRP eventually (though
>> that may not have happened yet), so the test could probably also be done
>> there, if that looks more convenient and we decide not to remove
>> single_use completely for this transformation.
>
> That was my thought as well, but AFAICT we only call into match.pd from VRP
> if we changed the insn.

Yes - there was thoughts to change that (but it comes at an expense).  Basically
we'd like to re-fold stmts that indirectly use stmts we changed.  We certainly
don't want to re-fold everything all the time.

>   There's no systematic calling into match.pd from
> most passes.  Thus, we don't do the transformation until fairly late in the
> pipeline when it's in match.pd.

Passes should fold stmts they change but with match.pd we now have that
"indirect" issue indeed.  Currently only forwprop unconditionally folds all
stmts.

I'm not sure if there's any heuristic we can apply for folding stmts that
is cheaper than simply folding everything...  The simplest thing would
be to fold stmts in the same BB after we've changed a stmt in it.  A
"full" solution would be to populate a bitmap with all defs of stmts
using the changed stmts defs, folding their definitions (and clearing the
bits).  Exclude virtual operands and PHIs.

Something to experiment with I guess.  The above could apply to
the SSA propagator substitute-and-fold phase as well as FRE
elimination and DOM stmt optimization.

Richard.

>
> Jeff
>

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Marc Glisse]

On Tue, 24 Jan 2017, Richard Biener wrote:

>> That was my thought as well, but AFAICT we only call into match.pd
>> from VRP if we changed the insn.
>
> Yes - there was thoughts to change that (but it comes at an expense).
> Basically we'd like to re-fold stmts that indirectly use stmts we
> changed.  We certainly don't want to re-fold everything all the time.

VRP is kind of a special case, every variable for which it finds a
new/improved range could be considered changed, since it may trigger
some extra transformation in match.pd (same for CCP and the nonzero
mask).

-- 
Marc Glisse

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Jeff Law]

On 01/24/2017 07:29 AM, Marc Glisse wrote:
> On Tue, 24 Jan 2017, Richard Biener wrote:
>
>>> That was my thought as well, but AFAICT we only call into match.pd
>>> from VRP if we changed the insn.
>>
>> Yes - there was thoughts to change that (but it comes at an expense).
>> Basically we'd like to re-fold stmts that indirectly use stmts we
>> changed.  We certainly don't want to re-fold everything all the time.
>
> VRP is kind of a special case, every variable for which it finds a
> new/improved range could be considered changed, since it may trigger
> some extra transformation in match.pd (same for CCP and the nonzero
> mask).
But that would assume that match.pd is relying on range information and 
could thus use the improved range information.  *If* match.pd is using 
the range information generated by VRP, it's not terribly pervasive.

But waiting until forwprop3 means we're leaving a ton of useless blocks 
and statements in the IL for this testcase, and likely other code using 
std::vec.

Perhaps rather than open-coding a fix in VRP I could have VRP call into 
match.pd slightly more aggressively (say just for gimple_cond).  That 
may be enough to capture the effects much earlier in the pipeline 
without trying to fold *everything*.

Jeff

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Marc Glisse]

On Tue, 24 Jan 2017, Jeff Law wrote:

> But that would assume that match.pd is relying on range information and could 
> thus use the improved range information.  *If* match.pd is using the range 
> information generated by VRP, it's not terribly pervasive.

Oh, I thought we already had some explicit calls to get_range_info in 
there, but apparently not. We can use VRP info through get_nonzero_bits, 
expr_not_equal_to and maybe one or two more like tree_expr_nonzero_p or 
tree_expr_nonnegative_p. If we called into match.pd from VRP, I assume 
several of the simplify_*_using_ranges could be moved to match.pd. But I 
agree that most transformations do not look at ranges at all.

-- 
Marc Glisse

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Richard Biener]

On January 24, 2017 5:02:39 PM GMT+01:00, Marc Glisse <marc.glisse@inria.fr> wrote:
>On Tue, 24 Jan 2017, Jeff Law wrote:
>
>> But that would assume that match.pd is relying on range information
>and could 
>> thus use the improved range information.  *If* match.pd is using the
>range 
>> information generated by VRP, it's not terribly pervasive.
>
>Oh, I thought we already had some explicit calls to get_range_info in 
>there, but apparently not. We can use VRP info through
>get_nonzero_bits, 
>expr_not_equal_to and maybe one or two more like tree_expr_nonzero_p or

We have the latter already.

>tree_expr_nonnegative_p. If we called into match.pd from VRP, I assume 
>several of the simplify_*_using_ranges could be moved to match.pd. 

Yes, that will hopefully happen at some point but it also requires folding more stmts to not regress (I'd like to remove the stmt folding callback from the SSA propagator)

Richard.

But
>I 
>agree that most transformations do not look at ranges at all.

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Richard Biener]

On Tue, Jan 24, 2017 at 4:05 PM, Jeff Law <law@redhat.com> wrote:
> On 01/24/2017 07:29 AM, Marc Glisse wrote:
>>
>> On Tue, 24 Jan 2017, Richard Biener wrote:
>>
>>>> That was my thought as well, but AFAICT we only call into match.pd
>>>> from VRP if we changed the insn.
>>>
>>>
>>> Yes - there was thoughts to change that (but it comes at an expense).
>>> Basically we'd like to re-fold stmts that indirectly use stmts we
>>> changed.  We certainly don't want to re-fold everything all the time.
>>
>>
>> VRP is kind of a special case, every variable for which it finds a
>> new/improved range could be considered changed, since it may trigger
>> some extra transformation in match.pd (same for CCP and the nonzero
>> mask).
>
> But that would assume that match.pd is relying on range information and
> could thus use the improved range information.  *If* match.pd is using the
> range information generated by VRP, it's not terribly pervasive.
>
> But waiting until forwprop3 means we're leaving a ton of useless blocks and
> statements in the IL for this testcase, and likely other code using
> std::vec.
>
> Perhaps rather than open-coding a fix in VRP I could have VRP call into
> match.pd slightly more aggressively (say just for gimple_cond).  That may be
> enough to capture the effects much earlier in the pipeline without trying to
> fold *everything*.

Sure, the only disadvantage of doing it in VRP (in vrp_fold_stmt) is that you
may end up doing it twice.

Richard.

> Jeff
>
>

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Jeff Law]

On 01/25/2017 03:34 AM, Richard Biener wrote:
> On Tue, Jan 24, 2017 at 4:05 PM, Jeff Law <law@redhat.com> wrote:
>> On 01/24/2017 07:29 AM, Marc Glisse wrote:
>>>
>>> On Tue, 24 Jan 2017, Richard Biener wrote:
>>>
>>>>> That was my thought as well, but AFAICT we only call into match.pd
>>>>> from VRP if we changed the insn.
>>>>
>>>>
>>>> Yes - there was thoughts to change that (but it comes at an expense).
>>>> Basically we'd like to re-fold stmts that indirectly use stmts we
>>>> changed.  We certainly don't want to re-fold everything all the time.
>>>
>>>
>>> VRP is kind of a special case, every variable for which it finds a
>>> new/improved range could be considered changed, since it may trigger
>>> some extra transformation in match.pd (same for CCP and the nonzero
>>> mask).
>>
>> But that would assume that match.pd is relying on range information and
>> could thus use the improved range information.  *If* match.pd is using the
>> range information generated by VRP, it's not terribly pervasive.
>>
>> But waiting until forwprop3 means we're leaving a ton of useless blocks and
>> statements in the IL for this testcase, and likely other code using
>> std::vec.
>>
>> Perhaps rather than open-coding a fix in VRP I could have VRP call into
>> match.pd slightly more aggressively (say just for gimple_cond).  That may be
>> enough to capture the effects much earlier in the pipeline without trying to
>> fold *everything*.
>
> Sure, the only disadvantage of doing it in VRP (in vrp_fold_stmt) is that you
> may end up doing it twice.
Once per VRP pass doesn't seem excessive.

If we simplify in VRP with a valueizer that walks up the ASSERT_EXPRs, 
then VRP1 will simplify the two key conditionals.  The first DOM pass is 
then able to clean up the whole mess.  But that valueizer runs afoul of 
maybe_set_nonzero_bits's assumptions for an unrelated testcase (pr60482).

maybe_set_nonzero_bits has restrictions on the number of uses of an 
SSA_NAME.  folding with a valueizer that walks the ASSERT_EXPR chain has 
a side effect of copy propagating through ASSERT_EXPRs.  So for the 
pr60482 testcase we end up with 3 uses of "n_12" rather than the 
expected 2.  That in turn causes us to avoid aggressively clearing bits 
in the non-zero bitmask of n_12.  That in turn causes us to fail to 
eliminate a conditional, which in turn causes us to need a loop epilogue 
for vectorization.  Ugh.

If we fold in VRP1 without walking up the ASSERT_EXPRs, we transform 
just the first conditional in VRP1.  A goodly amount of simplification 
is still done in the first DOM pass, but not all of it.

forwprop3 then transforms the second conditional which PRE is then able 
to optimize away.  That's early enough to allow sinking of the arithmetic.

The first DOM pass still cleaned up most of the crud early so we're 
avoiding useless work.  The final result is the same as with the 
ASSERT_EXPR walking valueizer.  That seems like a reasonable compromise.

Spinning that version...

jeff

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Richard Biener]

On Sat, Jan 21, 2017 at 6:22 AM, Jeff Law <law@redhat.com> wrote:
> On 01/20/2017 04:30 PM, Jeff Law wrote:
>>
>> Going to work from the self-contained test...
>>
>>
>>>
>>> Here's a test case that's closer to the one from the bug.  It also
>>> ends up with the out of bounds memset even at -O1, during PRE.
>>>
>>> typedef __SIZE_TYPE__ size_t;
>>>
>>> struct S
>>>   int *p0, *p1, *p2;
>>>
>>>   size_t size () const { return p1 - p0; }
>>>
>>>   void f (size_t n) {
>>>     if (n > size ())       // can't happen because
>>>       foo (n - size ());   //   n is in [1, MIN(size() - 1, 3)]
>>>     else if (n < size ())
>>>       bar (p0 + n);
>>>   }
>>>
>>>   void foo (size_t n)
>>>   {
>>>     size_t left = (size_t)(p2 - p1);
>>>     if (left >= n)
>>>       __builtin_memset (p2, 0, n * sizeof *p2);
>>>   }
>>>
>>>   void bar (int*);
>>> };
>>>
>>> void f (S &s)
>>> {
>>>   size_t n = s.size ();
>>>   if (n > 1 && n < 5)
>>>     s.f (n - 1);
>>> }
>>
>>
>>
>> Looking at the .vrp1 dump for this test we find:
>>
>> ;;   basic block 3, loop depth 0, count 0, freq 3664, maybe hot
>> ;;    prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
>> ;;    pred:       2 [36.6%]  (TRUE_VALUE,EXECUTABLE)
>>   _18 = ASSERT_EXPR <_13, _13 + 18446744073709551614 <= 2>;
>>   _2 = _18 + 18446744073709551615;
>>   if (_2 > _18)
>>     goto <bb 4>; [50.00%]
>>   else
>>     goto <bb 6>; [50.00%]
>>
>> _2 > _18 is the same as
>>
>> (_18 - 1) > _18
>>
>> Which is only true if _18 is zero.  And since _18 has a computed range
>> of [2..4], that can never happen.
>>
>> VRP doesn't currently handle this case, though we do have some code to
>> turn relational comparisons into equality comparisons.  If I manually
>> turn the relational into _18 == 0 at that point, then the next VRP pass
>> is able to optimize the conditional away which in turn eliminates the
>> problematical memset call & warning.
>>
>> So one possible approach would be to treat simplify_cond_using_ranges to
>> simplify that kind of condition.  I don't know if that would fix the
>> reported testcase as I haven't looked at it directly under the debugger
>> yet.
>
> In fact, match.pd already has a pattern to handle a relational like
> (X + -1) > X
>
> The pattern doesn't fire because of a single_use guard.   This was discussed
> back in 2015 with Jakub advocating for a single_use guard, but Marc leaning
> the other direction, but not enough to argue too much about it.
>
> In early 2016 Marc actually submitted the match.pd patch with the single use
> guard per Jakub's preference.
>
> The single use guard checks the SSA_NAME holding the (X + CST) expression
> for single use.   It's not entirely clear why we check for single use.  If
> it's because of object lifetimes, then that's a total red herring here.
>
> Given something like:
> x = a + c
> if (a > x)
>
> The transformation into
>
> x = a + c;
> if (a < c')
>
> Where x has multiple uses, the transformation will not inherently change the
> lifetime of "x" worse (if the conditional was the last use, then the
> lifetime of x may shorten somewhat).  If there were uses after the
> condition, the lifetime of "x" remains unchanged.
>
> "a" was already live from the assignment to at least the conditional. But
> again, we haven't inherently changed its lifetime.
>
> However, what can happen is after transformation, the assignment might sink
> to a later use point in the CFG, which might lengthen the lifetime of "a",
> but it's also shortening the lifetime of "x" by the same amount.
>
> So, ultimately I don't buy the argument that we should inhibit this based on
> register lifetime issues.
>
> Jakub, perhaps you remember why you wanted this restricted to cases where
> "x" has a single use?

I think it was added for the reason stated in the comment:

/* When one argument is a constant, overflow detection can be simplified.
   Currently restricted to single use so as not to interfere too much with
   ADD_OVERFLOW detection in tree-ssa-math-opts.c.
   A + CST CMP A  ->  A CMP' CST' */
(for cmp (lt le ge gt)
     out (gt gt le le)
 (simplify
  (cmp:c (plus@2 @0 INTEGER_CST@1) @0)
  (if (TYPE_UNSIGNED (TREE_TYPE (@0))
       && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))
       && wi::ne_p (@1, 0)
       && single_use (@2))
   (out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value
               (TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); }))))

> Certainly the easiest thing to do is remove the single use restriction. If
> we ultimately don't want to do that, we can probably detect when the
> transformation will allow the conditional to be eliminated in VRP and I
> would claim that elimination of the conditional at compile time trumps the
> other potential concerns here.  That's going to be uglier and essentially
> duplicate parts of what match.pd does, but certainly doable -- I've even
> prototyped it.

Yeah, duplicating that sounds ugly.

But undoing it for the sake of detecting overflow builtins is as well (OTOH
nothing does the reverse transform so if the user wrote the "simplified"
variant we don't detect overflow either).

Richard.

> Thoughts?
>
> jeff
>
>

Re: A + B CMP A -> A CMP' CST' match.pd patterns [was [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)]

[Jeff Law]

On 01/23/2017 02:10 AM, Richard Biener wrote:
>
> I think it was added for the reason stated in the comment:
>
> /* When one argument is a constant, overflow detection can be simplified.
>    Currently restricted to single use so as not to interfere too much with
>    ADD_OVERFLOW detection in tree-ssa-math-opts.c.
>    A + CST CMP A  ->  A CMP' CST' */
> (for cmp (lt le ge gt)
>      out (gt gt le le)
>  (simplify
>   (cmp:c (plus@2 @0 INTEGER_CST@1) @0)
>   (if (TYPE_UNSIGNED (TREE_TYPE (@0))
>        && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))
>        && wi::ne_p (@1, 0)
>        && single_use (@2))
>    (out @0 { wide_int_to_tree (TREE_TYPE (@0), wi::max_value
>                (TYPE_PRECISION (TREE_TYPE (@0)), UNSIGNED) - @1); }))))
>
>> Certainly the easiest thing to do is remove the single use restriction. If
>> we ultimately don't want to do that, we can probably detect when the
>> transformation will allow the conditional to be eliminated in VRP and I
>> would claim that elimination of the conditional at compile time trumps the
>> other potential concerns here.  That's going to be uglier and essentially
>> duplicate parts of what match.pd does, but certainly doable -- I've even
>> prototyped it.
>
> Yeah, duplicating that sounds ugly.
So one possibility is to put an additional if case in the code above 
without the single_use condition which fires iff we're turning the two 
operand relational into a zero/not-zero test.

The only problem is that doesn't manage to clean things up until dom3. 
We could instead have them cleaned up by dom2 if the tweak is in VRP. 
This is because we don't call the gimple folders on the statement until 
after dom2 is already complete.

So there's 10 blocks of crud in the IL for the 40 passes between dom2 
and dom3.  And FWIW, this shows up a hundred times or so during a GCC 
bootstrap.  I haven't looked to see how many of those result in just a 
simplified test vs those with nice secondary optimizations like we see 
with the test in the BZ.


>
> But undoing it for the sake of detecting overflow builtins is as well (OTOH
> nothing does the reverse transform so if the user wrote the "simplified"
> variant we don't detect overflow either).
I'm not sure there'd be enough information left to undo the 
transformation, even if it were restricted to the zero/not-zero 
resulting test.

Jeff

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Jeff Law]

On 01/18/2017 01:10 AM, Jakub Jelinek wrote:
> On Tue, Jan 17, 2017 at 10:59:43PM -0700, Jeff Law wrote:
>>> I agree that breaking those applications would be bad.  It could
>>> be dealt with by adding an option to let them disable the insertion
>>> of the trap.  With the warning, programmers would get a heads up
>>> that their (already dubious) code won't work otherwise.  I don't
>>> think it's a necessary or wise to have the default mode be the most
>>> permissive (and most dangerous) and expect users to tweak options
>>> to make it safe.  Rather, I would argue that it should be the other
>>> way around.  Make the default safe and strict and let the advanced
>>> users who know how deal with the risks tweak those options.
>> I still come back to the assertion that changing this loop to a mem* is
>> fundamentally the wrong thing to do as it changes something that has well
>> defined semantics to something that is invalid.
>>
>> Thus the transformation into a mem* call is invalid.
>
> The mem* call is as valid as the loop, it will work exactly the same.
> If you have say on 32-bit target
> #include <stdlib.h>
>
> int
> main ()
> {
>   char *p = malloc (3U * 1024 * 1024 * 1024);
>   if (p == NULL)
>     return 0;
>   size_t i;
>   for (i = 0; i < 3U * 1024 * 1024 * 1024; i++)
>     p[i] = 6;
>   use (p);
>   return 0;
> }
>
> then the loop does the same thing as will memset (p, 6, 3U * 1024 * 1024 * 1024);
> do.  On such large objects some operations may not work properly, e.g.
> &p[i] - &p[0] might be negative etc., but that is not something the above
> loop does or memset will do internally.  If the loop doesn't use just 3/4 of
> the address space, but much more, e.g. more than whole address space minus
> one page, which is what happens in the testcase, it is indeed quite sure it
> will crash if invoked, but the problem with the warning is the same with
> many other late warnings or warnings excessively using VRP etc.
Not in my mind, it's different.  It's not triggered by path isolation. 
It's standard const propagation + simplification.

jeff

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Jakub Jelinek]

On Fri, Jan 20, 2017 at 04:32:19PM -0700, Jeff Law wrote:
> > then the loop does the same thing as will memset (p, 6, 3U * 1024 * 1024 * 1024);
> > do.  On such large objects some operations may not work properly, e.g.
> > &p[i] - &p[0] might be negative etc., but that is not something the above
> > loop does or memset will do internally.  If the loop doesn't use just 3/4 of
> > the address space, but much more, e.g. more than whole address space minus
> > one page, which is what happens in the testcase, it is indeed quite sure it
> > will crash if invoked, but the problem with the warning is the same with
> > many other late warnings or warnings excessively using VRP etc.
> Not in my mind, it's different.  It's not triggered by path isolation. It's
> standard const propagation + simplification.

So where does the constant -1 length appear there?  The test clearly just
attempts to clear some variable length - 1.  I admit I haven't looked at the
dumps in detail, I should...

	Jakub

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Jeff Law]

On 01/20/2017 04:34 PM, Jakub Jelinek wrote:
> On Fri, Jan 20, 2017 at 04:32:19PM -0700, Jeff Law wrote:
>>> then the loop does the same thing as will memset (p, 6, 3U * 1024 * 1024 * 1024);
>>> do.  On such large objects some operations may not work properly, e.g.
>>> &p[i] - &p[0] might be negative etc., but that is not something the above
>>> loop does or memset will do internally.  If the loop doesn't use just 3/4 of
>>> the address space, but much more, e.g. more than whole address space minus
>>> one page, which is what happens in the testcase, it is indeed quite sure it
>>> will crash if invoked, but the problem with the warning is the same with
>>> many other late warnings or warnings excessively using VRP etc.
>> Not in my mind, it's different.  It's not triggered by path isolation. It's
>> standard const propagation + simplification.
>
> So where does the constant -1 length appear there?  The test clearly just
> attempts to clear some variable length - 1.  I admit I haven't looked at the
> dumps in detail, I should...
At least in Martin's simplified test it's just a series of standard 
constant propagations and obvious simplifications.  No threading, no 
path isolation.

;;   basic block 2, loop depth 0, count 0, freq 10000, maybe hot
;;    prev block 0, next block 3, flags: (NEW, REACHABLE, VISITED)
;;    pred:       ENTRY [100.0%]  (FALLTHRU,EXECUTABLE)
   _7 = MEM[(int * *)s_5(D)];
   _8 = MEM[(int * *)s_5(D) + 8B];
   _9 = (long int) _8;
   _10 = (long int) _7;
   _11 = _9 - _10;
   _12 = _11 /[ex] 4;
   _13 = (long unsigned int) _12;
   _1 = _13 + 18446744073709551614;
   if (_1 <= 2)
     goto <bb 3>; [36.64%]
   else
     goto <bb 8>; [63.36%]
;;    succ:       3 [36.6%]  (TRUE_VALUE,EXECUTABLE)
;;                8 [63.4%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 3, loop depth 0, count 0, freq 3664, maybe hot
;;    prev block 2, next block 4, flags: (NEW, REACHABLE, VISITED)
;;    pred:       2 [36.6%]  (TRUE_VALUE,EXECUTABLE)
   _2 = _13 + 18446744073709551615;
   _14 = MEM[(int * *)s_5(D)];
   _15 = MEM[(int * *)s_5(D) + 8B];
   _16 = (long int) _15;
   _17 = (long int) _14;
   _18 = _16 - _17;
   _19 = _18 /[ex] 4;
   _20 = (long unsigned int) _19;
   if (_2 > _20)
     goto <bb 4>; [50.00%]
   else
     goto <bb 6>; [50.00%]
;;    succ:       4 [50.0%]  (TRUE_VALUE,EXECUTABLE)
;;                6 [50.0%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 4, loop depth 0, count 0, freq 1832, maybe hot
;;    prev block 3, next block 5, flags: (NEW, REACHABLE, VISITED)
;;    pred:       3 [50.0%]  (TRUE_VALUE,EXECUTABLE)
   _21 = _2 - _20;
   _22 = MEM[(int * *)s_5(D) + 16B];
   _23 = (long int) _22;
   _24 = _23 - _16;
   _25 = _24 /[ex] 4;
   left_26 = (size_t) _25;
   if (_21 <= left_26)
     goto <bb 5>; [33.00%]
   else
     goto <bb 8>; [67.00%]
;;    succ:       5 [33.0%]  (TRUE_VALUE,EXECUTABLE)
;;                8 [67.0%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 5, loop depth 0, count 0, freq 605, maybe hot
;;    prev block 4, next block 6, flags: (NEW, REACHABLE, VISITED)
;;    pred:       4 [33.0%]  (TRUE_VALUE,EXECUTABLE)
   _27 = _21 * 4;
   __builtin_memset (_22, 0, _27);
   goto <bb 8>; [100.00%]
;;    succ:       8 [100.0%]  (FALLTHRU,EXECUTABLE)


In particular look at _27, which is _21 * 4.

_21 is _2 - _20

If you follow things though the use-def chains and simplify you'll see 
that _2 - 20 is always -1.


Jeff

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Jeff Law]

On 01/16/2017 05:06 PM, Martin Sebor wrote:
> The test case submitted in bug 79095 - [7 regression] spurious
> stringop-overflow warning shows that GCC optimizes some loops
> into calls to memset with size arguments in excess of the object
> size limit.  Since such calls will unavoidably lead to a buffer
> overflow and memory corruption the attached patch detects them
> and replaces them with a trap.  That both prevents the buffer
> overflow and eliminates the warning.
But doesn't the creation of the bogus memset signal an invalid 
transformation in the loop optimizer?  ie, if we're going to convert a 
loop into a memset, then we'd damn well better be sure the loop bounds 
are reasonable.

Jeff

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Martin Sebor]

On 01/17/2017 08:26 AM, Jeff Law wrote:
> On 01/16/2017 05:06 PM, Martin Sebor wrote:
>> The test case submitted in bug 79095 - [7 regression] spurious
>> stringop-overflow warning shows that GCC optimizes some loops
>> into calls to memset with size arguments in excess of the object
>> size limit.  Since such calls will unavoidably lead to a buffer
>> overflow and memory corruption the attached patch detects them
>> and replaces them with a trap.  That both prevents the buffer
>> overflow and eliminates the warning.
> But doesn't the creation of the bogus memset signal an invalid
> transformation in the loop optimizer?  ie, if we're going to convert a
> loop into a memset, then we'd damn well better be sure the loop bounds
> are reasonable.

I'm not sure that emitting the memset call is necessarily a bug in
the loop optimizer (which in all likelihood wasn't written with
the goal of preventing or detecting possible buffer overflows).
The loop with the excessive bound is in the source code and can
be reached given the right inputs (calling v.resize(v.size() - 1)
on an empty vector.  It's a lurking bug in the program that, if
triggered, will overflow the vector and crash the program (or worse)
with or without the optimization.

What else could the loop optimizer could do in this instance?
I suppose it could just leave the loop alone and avoid emitting
the memset call.  That would avoid the warning but mask the
problem with the overflow.  In my mind, preventing the overflow
given that we have the opportunity is the right thing to do.
That is, after all, the goal of the warning.

As I mentioned privately yesterday, I'm actually pleasantly
surprised that it's helped identify this opportunity in GCC itself.
My hope was to eventually go and find the places where GCC emits
potentially out of bounds calls (based on user inputs) and fix them
to emit better code on the assumption that they can't be valid or
replace them with traps if they could happen in a running program.
It didn't occur to me that the warning itself would help find them.

Martin

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Jeff Law]

On 01/17/2017 09:12 AM, Martin Sebor wrote:
> On 01/17/2017 08:26 AM, Jeff Law wrote:
>> On 01/16/2017 05:06 PM, Martin Sebor wrote:
>>> The test case submitted in bug 79095 - [7 regression] spurious
>>> stringop-overflow warning shows that GCC optimizes some loops
>>> into calls to memset with size arguments in excess of the object
>>> size limit.  Since such calls will unavoidably lead to a buffer
>>> overflow and memory corruption the attached patch detects them
>>> and replaces them with a trap.  That both prevents the buffer
>>> overflow and eliminates the warning.
>> But doesn't the creation of the bogus memset signal an invalid
>> transformation in the loop optimizer?  ie, if we're going to convert a
>> loop into a memset, then we'd damn well better be sure the loop bounds
>> are reasonable.
>
> I'm not sure that emitting the memset call is necessarily a bug in
> the loop optimizer (which in all likelihood wasn't written with
> the goal of preventing or detecting possible buffer overflows).
> The loop with the excessive bound is in the source code and can
> be reached given the right inputs (calling v.resize(v.size() - 1)
> on an empty vector.  It's a lurking bug in the program that, if
> triggered, will overflow the vector and crash the program (or worse)
> with or without the optimization.
Right, but that doesn't mean that the loop optimizer can turn it into a 
memset.  If the bounds are such that we're going to invoke undefined 
behaviour from memset, then the loop optimizer must leave the loop alone.

>
> What else could the loop optimizer could do in this instance?
> I suppose it could just leave the loop alone and avoid emitting
> the memset call.  That would avoid the warning but mask the
> problem with the overflow.  In my mind, preventing the overflow
> given that we have the opportunity is the right thing to do.
> That is, after all, the goal of the warning.
The right warning in this case is WRT the loop iteration space 
independent of mem*.


>
> As I mentioned privately yesterday, I'm actually pleasantly
> surprised that it's helped identify this opportunity in GCC itself.
> My hope was to eventually go and find the places where GCC emits
> potentially out of bounds calls (based on user inputs) and fix them
> to emit better code on the assumption that they can't be valid or
> replace them with traps if they could happen in a running program.
> It didn't occur to me that the warning itself would help find them.
>
> Martin
>

Re: [PATCH] avoid calling memset et al. with excessively large sizes (PR 79095)

[Martin Sebor]

On 01/17/2017 10:57 AM, Jeff Law wrote:
> On 01/17/2017 09:12 AM, Martin Sebor wrote:
>> On 01/17/2017 08:26 AM, Jeff Law wrote:
>>> On 01/16/2017 05:06 PM, Martin Sebor wrote:
>>>> The test case submitted in bug 79095 - [7 regression] spurious
>>>> stringop-overflow warning shows that GCC optimizes some loops
>>>> into calls to memset with size arguments in excess of the object
>>>> size limit.  Since such calls will unavoidably lead to a buffer
>>>> overflow and memory corruption the attached patch detects them
>>>> and replaces them with a trap.  That both prevents the buffer
>>>> overflow and eliminates the warning.
>>> But doesn't the creation of the bogus memset signal an invalid
>>> transformation in the loop optimizer?  ie, if we're going to convert a
>>> loop into a memset, then we'd damn well better be sure the loop bounds
>>> are reasonable.
>>
>> I'm not sure that emitting the memset call is necessarily a bug in
>> the loop optimizer (which in all likelihood wasn't written with
>> the goal of preventing or detecting possible buffer overflows).
>> The loop with the excessive bound is in the source code and can
>> be reached given the right inputs (calling v.resize(v.size() - 1)
>> on an empty vector.  It's a lurking bug in the program that, if
>> triggered, will overflow the vector and crash the program (or worse)
>> with or without the optimization.
> Right, but that doesn't mean that the loop optimizer can turn it into a
> memset.  If the bounds are such that we're going to invoke undefined
> behaviour from memset, then the loop optimizer must leave the loop alone.
>
>>
>> What else could the loop optimizer could do in this instance?
>> I suppose it could just leave the loop alone and avoid emitting
>> the memset call.  That would avoid the warning but mask the
>> problem with the overflow.  In my mind, preventing the overflow
>> given that we have the opportunity is the right thing to do.
>> That is, after all, the goal of the warning.
> The right warning in this case is WRT the loop iteration space
> independent of mem*.

I agree that warning for the user code would be appropriate if
the loop with the excessive bound were unavoidable or at least
reachable.  But in the submitted test case it isn't because
the call to vector::resize() is guarded.  In fact, the out of-
bounds memset is also emitted with this modified test case:

   void f (std::vector<int> &v)
   {
     size_t n = v.size ();

     if (n > 1 && n < 5)
       v.resize (n - 1);
   }

I believe the root cause of the the out-of-bounds memset is the
lack of support for pointer ranges or at least some notion of
their relationships and constraints.  A std::vector is defined
by three pointers that satisfy the following relation:

   start <= finish <= end_of_storage

Queries about the capacity and size of a vector are done in terms
of expressions involving these three pointers:

   size_type capacity () {
     return end_of_storage - start;
   }

   size_type size () {
     return finish - start;
   }

Space remaining is hand-coded as

   end_of_storage - finish

The trouble is that GCC has no idea about the constraints on
the three pointers and so it treats them essentially as unrelated
integers with no ranges (except for their scale that depends on
the type the pointer points to).

Absent support for pointer ranges, GCC would be able to generate
much better code with just some help from annotations telling it
about at least some of the constraints.  In this case, for example,
adding the following optimistic invariant:

    size_type space_left = end_of_storage - finish;

    if (space_left > SIZE_MAX / 2 / sizeof (T))
      __builtin_unreachable ();

to vector::_M_default_append() lets GCC avoid the memset and emit
significantly more efficient code.  On x86_64 it reduces the number
instructions for the test case by 40%.

Martin