[PATCH] correct handling of offset ranges that cross PTRDIFF_MAX (PR 83640)

[Martin Sebor <msebor at gmail dot com>]

PR tree-optimization/83640 - ice in generic_overlap at
gimple-ssa-warn-restrict.c:814 highlights out a class of cases
where the -Wrestrict checker assumes that the range of a pointer
offset that us represented by a VR_RANGE has a lower bound that
is less than its upper bound.  The pass asserts that this is so
and cases to the contrary trigger an ICE.

The submitted test case that triggers this ICE is due to a missed
optimization in tree-ssa-strlen (which could, and IMO should,
guarantee that the offsets it constructs are in such a range, and
I'll submit a separate patch with that change), but the assumption
isn't safe in general for offsets whose range happens to straddle
the PTRDIFF_MAX boundary, i.e., whose lower bound is greater than
its upper bound.

The attached patch makes adjustments to remove this assumption
and avoid the ICE.  Tested on x86_64-linux with no regressions.

Martin

PS The patch also removes the same troublesome assertion that's
also removed in the one below:

  https://gcc.gnu.org/ml/gcc-patches/2017-12/msg01399.html

PR tree-optimization/83640 - ice in generic_overlap at gimple-ssa-warn-restrict.c:814

gcc/ChangeLog:

	PR tree-optimization/83640
	* gimple-ssa-warn-restrict.c (builtin_access::builtin_access): Avoid
	subtracting negative offset from size.
	(builtin_access::overlap): Adjust offset bounds of the access to fall
	within the size of the object if possible.
	(maybe_diag_overlap): Remove troublesome assertion.

gcc/testsuite/ChangeLog:

	PR tree-optimization/83640
	* gcc.dg/Wrestrict-3.c: New test.
	* gcc.dg/pr83640.c: New test.

diff --git a/gcc/gimple-ssa-warn-restrict.c b/gcc/gimple-ssa-warn-restrict.c
index ac545e4..ebec381 100644
--- a/gcc/gimple-ssa-warn-restrict.c
+++ b/gcc/gimple-ssa-warn-restrict.c
@@ -698,9 +698,10 @@ builtin_access::builtin_access (gcall *call, builtin_memref &dst,
 
 	  /* For string functions, adjust the size range of the source
 	     reference by the inverse boundaries of the offset (because
-	     the higher  the offset into the string the shorter its
+	     the higher the offset into the string the shorter its
 	     length).  */
-	  if (srcref->offrange[1] < srcref->sizrange[0])
+	  if (srcref->offrange[1] >= 0
+	      && srcref->offrange[1] < srcref->sizrange[0])
 	    srcref->sizrange[0] -= srcref->offrange[1];
 	  else
 	    srcref->sizrange[0] = 0;
@@ -1134,30 +1135,53 @@ builtin_access::overlap ()
   if (!dstref->base || !srcref->base)
     return false;
 
-  /* If the base object is an array adjust the lower bound of the offset
-     to be non-negative.  */
+  /* Set the access offsets.  */
+  acs.dstoff[0] = dstref->offrange[0];
+  acs.dstoff[1] = dstref->offrange[1];
+
+  /* If the base object is an array adjust the bounds of the offset
+     to be non-negative and within the bounds of the array if possible.  */
   if (dstref->base
       && TREE_CODE (TREE_TYPE (dstref->base)) == ARRAY_TYPE)
-    acs.dstoff[0] = wi::smax (dstref->offrange[0], 0);
-  else
-    acs.dstoff[0] = dstref->offrange[0];
+    {
+      if (acs.dstoff[0] < 0 && acs.dstoff[1] >= 0)
+	acs.dstoff[0] = 0;
 
-  acs.dstoff[1] = dstref->offrange[1];
+      if (acs.dstoff[1] < acs.dstoff[0])
+	{
+	  if (tree size = TYPE_SIZE_UNIT (TREE_TYPE (dstref->base)))
+	    acs.dstoff[1] = wi::umin (acs.dstoff[1], wi::to_offset (size));
+	  else
+	    acs.dstoff[1] = wi::umin (acs.dstoff[1], maxobjsize);
+	}
+    }
+
+  acs.srcoff[0] = srcref->offrange[0];
+  acs.srcoff[1] = srcref->offrange[1];
 
   if (srcref->base
       && TREE_CODE (TREE_TYPE (srcref->base)) == ARRAY_TYPE)
-    acs.srcoff[0] = wi::smax (srcref->offrange[0], 0);
-  else
-    acs.srcoff[0] = srcref->offrange[0];
+    {
+      if (acs.srcoff[0] < 0 && acs.srcoff[1] >= 0)
+	acs.srcoff[0] = 0;
 
-  acs.srcoff[1] = srcref->offrange[1];
+      if (tree size = TYPE_SIZE_UNIT (TREE_TYPE (srcref->base)))
+	acs.srcoff[1] = wi::umin (acs.srcoff[1], wi::to_offset (size));
+      else if (acs.srcoff[1] < acs.srcoff[0])
+	acs.srcoff[1] = wi::umin (acs.srcoff[1], maxobjsize);
+    }
 
-  /* When the lower bound of the offset is less that the upper bound
-     disregard it and use the inverse of the maximum object size
-     instead.  The upper bound is the result of a negative offset
-     being represented as a large positive value.  */
+  /* When the upper bound of the offset is less than the lower bound
+     the former is the result of a negative offset being represented
+     as a large positive value or vice versa.  The resulting range is
+     a union of two subranges: [MIN, UB] and [LB, MAX].  Since such
+     a union is not representable using the current data structure
+     replace it with the full range of offsets.  */
   if (acs.dstoff[1] < acs.dstoff[0])
-    acs.dstoff[0] = -maxobjsize;
+    {
+      acs.dstoff[0] = -maxobjsize - 1;
+      acs.dstoff[1] = maxobjsize;
+    }
 
   /* Validate the offset and size of each reference on its own first.
      This is independent of whether or not the base objects are the
@@ -1173,7 +1197,10 @@ builtin_access::overlap ()
 
   /* Repeat the same as above but for the source offsets.  */
   if (acs.srcoff[1] < acs.srcoff[0])
-    acs.srcoff[0] = -maxobjsize;
+    {
+      acs.srcoff[0] = -maxobjsize - 1;
+      acs.srcoff[1] = maxobjsize;
+    }
 
   maxoff = acs.srcoff[0] + srcref->sizrange[0];
   if (maxobjsize < maxoff)
@@ -1365,11 +1392,6 @@ maybe_diag_overlap (location_t loc, gcall *call, builtin_access &acs)
       return true;
     }
 
-  /* Issue "may overlap" diagnostics below.  */
-  gcc_assert (ovlsiz[0] == 0
-	      && ovlsiz[1] > 0
-	      && ovlsiz[1] <= maxobjsize.to_shwi ());
-
   /* Use more concise wording when one of the offsets is unbounded
      to avoid confusing the user with large and mostly meaningless
      numbers.  */
diff --git a/gcc/testsuite/gcc.dg/Wrestrict-3.c b/gcc/testsuite/gcc.dg/Wrestrict-3.c
new file mode 100644
index 0000000..c1bb373
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/Wrestrict-3.c
@@ -0,0 +1,66 @@
+/* PR tree-optimization/83640 - ice in generic_overlap, at
+   gimple-ssa-warn-restrict.c:814
+   Test to verify that a pointer offset range whose upper bound is less
+   than its lower bound (when interpreted as a signed integer) is handled
+   correctly.
+   { dg-do compile }
+   { dg-options "-O2 -Wrestrict" }  */
+
+#include "range.h"
+
+extern char* strcpy (char*, const char*);
+extern char* stpcpy (char*, const char*);
+
+void sink (void*);
+
+void warn_2_smax_p2 (void)
+{
+  char a[7] = "01234";
+
+  char *d = a;
+
+  ptrdiff_t i = UR (2, DIFF_MAX + (size_t)2);
+
+  strcpy (d, d + i);          /* { dg-warning "accessing between 0 and 4 bytes at offsets 0 and \\\[2, -\[0-9\]+] may overlap up to 2 bytes at offset 2" } */
+
+  sink (d);
+}
+
+void nowarn_3_smax_p2 (void)
+{
+  char a[7] = "12345";
+
+  char *d = a;
+
+  ptrdiff_t i = UR (3, DIFF_MAX + (size_t)2);
+
+  strcpy (d, d + i);
+
+  sink (d);
+}
+
+void warn_2u_smax_p2 (void)
+{
+  char a[7] = "23456";
+
+  char *d = a;
+
+  size_t i = UR (2, DIFF_MAX + (size_t)2);
+
+  strcpy (d, d + i);          /* { dg-warning "accessing between 0 and 4 bytes at offsets 0 and \\\[2, -\[0-9\]+] may overlap up to 2 bytes at offset 2" } */
+
+  sink (d);
+}
+
+void nowarn_3u_smax_p2 (void)
+{
+  char a[7] = "34567";
+
+  char *d = a;
+
+  size_t i = UR (3, DIFF_MAX + (size_t)2);
+
+  strcpy (d, d + i);
+
+  sink (d);
+}
diff --git a/gcc/testsuite/gcc.dg/pr83640.c b/gcc/testsuite/gcc.dg/pr83640.c
new file mode 100644
index 0000000..3b4d1be
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr83640.c
@@ -0,0 +1,15 @@
+/* PR tree-optimization/83640 - ice in generic_overlap, at
+   gimple-ssa-warn-restrict.c:814
+   { dg-do compile }
+   { dg-options "-O2 -Wall" }  */
+
+char *foo (void);
+
+void
+bar (char *b, char *c)
+{
+  b = c;
+  c = foo ();
+  __builtin_strcat (c, "*/");
+  __builtin_strcat (c, b);
+}