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 <ja...@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