[RFC PATCH] Fix pointer diff (was: -fsanitize=pointer-overflow support (PR sanitizer/80998))

[Jakub Jelinek <jakub at redhat dot com>]

On Tue, Jun 20, 2017 at 10:18:20AM +0200, Richard Biener wrote:
> > > > 3) not really related to this patch, but something I also saw during the
> > > > bootstrap-ubsan on i686-linux:
> > > > ../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147426384 - 2147475412 cannot be represented in type 'int'
> > > > ../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147426384 - 2147478324 cannot be represented in type 'int'
> > > > ../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147450216 - 2147451580 cannot be represented in type 'int'
> > > > ../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147450216 - 2147465664 cannot be represented in type 'int'
> > > > ../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147469348 - 2147451544 cannot be represented in type 'int'
> > > > ../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147482364 - 2147475376 cannot be represented in type 'int'
> > > > ../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147483624 - 2147475376 cannot be represented in type 'int'
> > > > ../../gcc/bitmap.c:141:12: runtime error: signed integer overflow: -2147483628 - 2147451544 cannot be represented in type 'int'
> > > > ../../gcc/memory-block.cc:59:4: runtime error: signed integer overflow: -2147426384 - 2147475376 cannot be represented in type 'int'
> > > > ../../gcc/memory-block.cc:59:4: runtime error: signed integer overflow: -2147450216 - 2147451544 cannot be represented in type 'int'
> > > > The problem here is that we lower pointer subtraction, e.g.
> > > > long foo (char *p, char *q) { return q - p; }
> > > > as return (ptrdiff_t) ((ssizetype) q - (ssizetype) p);
> > > > and even for a valid testcase where we have an array across
> > > > the middle of the virtual address space, say the first one above
> > > > is (char *) 0x8000dfb0 - (char *) 0x7fffdfd4 subtraction, even if
> > > > there is 128KB array starting at 0x7fffd000, it will yield
> > > > UB (not in the source, but in whatever the compiler lowered it into).
> > > > So, shall we instead do the subtraction in sizetype and only then
> > > > cast?  For sizeof (*ptr) > 1 I think we have some outstanding PR,
> > > > and it is more difficult to find out in what types to compute it.
> > > > Or do we want to introduce POINTER_DIFF_EXPR?
> > > 
> > > Just use uintptr_t for the difference computation (well, an unsigned
> > > integer type of desired precision -- mind address-spaces), then cast
> > > the result to signed.
> > 
> > Ok (of course, will handle this separately from the rest).
> 
> Yes.  Note I didn't look at the actual patch (yet).

So, I wrote following patch to do the subtraction in unsigned
type.  It passes bootstrap, but on both x86_64-linux and i686-linux
regresses:
+FAIL: gcc.dg/torture/pr66178.c   -O*  (test for excess errors)
+FAIL: gcc.dg/tree-ssa/cmpexactdiv-2.c scan-tree-dump-not optimized "minus_expr"
+FAIL: g++.dg/tree-ssa/pr21082.C  -std=gnu++* (test for excess errors)

E.g. in the first testcase we have in the test:
static uintptr_t a =  ((char *)&&l2-(char *)&&l3)+((char *)&&l1-(char *)&&l2);
Without the patch, we ended up with:
static uintptr_t a = (uintptr_t) (((long int) &l2 - (long int) &l3) + ((long int) &l1 - (long int) &l2));
but with the patch with (the negation in signed type sounds like a folding
bug), which is too difficult for the initializer_constant_valid_p* handling:
(uintptr_t) (((long unsigned int) -(long int) &l3 - (long unsigned int) &l2) + ((long unsigned int) &l2 + (long unsigned int) &l1));
Shall we just xfail that test, or make sure we don't reassociate such
subtractions, something different?

The second failure is on:
int f (long *a, long *b, long *c) {
    __PTRDIFF_TYPE__ l1 = b - a;
    __PTRDIFF_TYPE__ l2 = c - a;
    return l1 < l2;
}
where without the patch during forwprop2 we optimize it
using match.pd:
/* X - Z < Y - Z is the same as X < Y when there is no overflow.  */
because we had:
  b.0_1 = (long int) b_8(D);
  a.1_2 = (long int) a_9(D);
  _3 = b.0_1 - a.1_2;
  c.2_4 = (long int) c_11(D);
  a.3_5 = (long int) a_9(D);
  _6 = c.2_4 - a.3_5;
  _7 = _3 < _6;
But with the patch we have:
  b.0_1 = (long unsigned int) b_9(D);
  a.1_2 = (long unsigned int) a_10(D);
  _3 = b.0_1 - a.1_2;
  _4 = (long int) _3;
  c.2_5 = (long unsigned int) c_11(D);
  _6 = c.2_5 - a.1_2;
  _7 = (long int) _6;
  _8 = _4 < _7;
instead.  But that is something we can't generally optimize.
So do we need to introduce POINTER_DIFF (where we could still
optimize this) or remove the test?  If we rely on largest possible
array to be half of the VA size - 1 (i.e. where for x > y both being
pointers into the same array x - y > 0), then it is a valid optimization
of the 2 pointer subtractions, but it is not a valid optimization on
comparison of unsigned subtractions cast to signed type.

The third one is
        if (&a[b] - &a[c] != b - c)
                link_error();
where fold already during generic folding used to be able to cope with it,
but now we have:
(long int) (((long unsigned int) b - (long unsigned int) c) * 4) /[ex] 4 != b - c
which we don't fold.

2017-06-21  Jakub Jelinek  <jakub@redhat.com>

	* c-typeck.c (pointer_diff): Perform subtraction in unsigned
	type and only cast the result to signed type for the division.

	* typeck.c (pointer_diff): Perform subtraction in unsigned
	type and only cast the result to signed type for the division.

--- gcc/c/c-typeck.c.jj	2017-06-21 12:46:10.130822026 +0200
+++ gcc/c/c-typeck.c	2017-06-21 13:22:45.868310030 +0200
@@ -3781,7 +3781,7 @@ static tree
 pointer_diff (location_t loc, tree op0, tree op1)
 {
   tree restype = ptrdiff_type_node;
-  tree result, inttype;
+  tree result, inttype, uinttype;
 
   addr_space_t as0 = TYPE_ADDR_SPACE (TREE_TYPE (TREE_TYPE (op0)));
   addr_space_t as1 = TYPE_ADDR_SPACE (TREE_TYPE (TREE_TYPE (op1)));
@@ -3809,11 +3809,21 @@ pointer_diff (location_t loc, tree op0,
 
   /* Determine integer type to perform computations in.  This will usually
      be the same as the result type (ptrdiff_t), but may need to be a wider
-     type if pointers for the address space are wider than ptrdiff_t.  */
+     type if pointers for the address space are wider than ptrdiff_t.
+     The subtraction should be performed in the unsigned type, because for
+     the case where one pointer is above the middle of the address space
+     and the other pointer is below the middle of the address space
+     we'd otherwise introduce undefined behavior during the subtraction.  */
   if (TYPE_PRECISION (restype) < TYPE_PRECISION (TREE_TYPE (op0)))
-    inttype = c_common_type_for_size (TYPE_PRECISION (TREE_TYPE (op0)), 0);
+    {
+      inttype = c_common_type_for_size (TYPE_PRECISION (TREE_TYPE (op0)), 0);
+      uinttype = c_common_type_for_size (TYPE_PRECISION (TREE_TYPE (op0)), 1);
+    }
   else
-    inttype = restype;
+    {
+      inttype = restype;
+      uinttype = c_common_type_for_size (TYPE_PRECISION (restype), 1);
+    }
 
   if (TREE_CODE (target_type) == VOID_TYPE)
     pedwarn (loc, OPT_Wpointer_arith,
@@ -3822,14 +3832,15 @@ pointer_diff (location_t loc, tree op0,
     pedwarn (loc, OPT_Wpointer_arith,
 	     "pointer to a function used in subtraction");
 
-  /* First do the subtraction as integers;
+  /* First do the subtraction as unsigned integers;
+     then convert to signed integer and
      then drop through to build the divide operator.
      Do not do default conversions on the minus operator
      in case restype is a short type.  */
 
-  op0 = build_binary_op (loc,
-			 MINUS_EXPR, convert (inttype, op0),
-			 convert (inttype, op1), 0);
+  op0 = build_binary_op (loc, MINUS_EXPR, convert (uinttype, op0),
+			 convert (uinttype, op1), 0);
+  op0 = convert (inttype, op0);
   /* This generates an error if op1 is pointer to incomplete type.  */
   if (!COMPLETE_OR_VOID_TYPE_P (TREE_TYPE (TREE_TYPE (orig_op1))))
     error_at (loc, "arithmetic on pointer to an incomplete type");
--- gcc/cp/typeck.c.jj	2017-06-19 08:28:07.000000000 +0200
+++ gcc/cp/typeck.c	2017-06-21 13:26:17.120829891 +0200
@@ -5398,14 +5398,18 @@ pointer_diff (location_t loc, tree op0,
 	return error_mark_node;
     }
 
-  /* First do the subtraction as integers;
+  tree uinttype = c_common_type_for_size (TYPE_PRECISION (restype), 1);
+
+  /* First do the subtraction as unsigned integers;
+     then cast to restype and
      then drop through to build the divide operator.  */
 
   op0 = cp_build_binary_op (loc,
 			    MINUS_EXPR,
-			    cp_convert (restype, op0, complain),
-			    cp_convert (restype, op1, complain),
+			    cp_convert (uinttype, op0, complain),
+			    cp_convert (uinttype, op1, complain),
 			    complain);
+  op0 = cp_convert (restype, op0, complain);
 
   /* This generates an error if op1 is a pointer to an incomplete type.  */
   if (!COMPLETE_TYPE_P (TREE_TYPE (TREE_TYPE (op1))))


	Jakub