From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 82135 invoked by alias); 21 Jun 2017 14:40:20 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 82106 invoked by uid 89); 21 Jun 2017 14:40:19 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.9 required=5.0 tests=BAYES_00,GIT_PATCH_2,GIT_PATCH_3,SPF_HELO_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy= X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 21 Jun 2017 14:40:17 +0000 Received: from smtp.corp.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.13]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 2C798104C8; Wed, 21 Jun 2017 14:40:12 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 2C798104C8 Authentication-Results: ext-mx09.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com Authentication-Results: ext-mx09.extmail.prod.ext.phx2.redhat.com; spf=pass smtp.mailfrom=jakub@redhat.com DKIM-Filter: OpenDKIM Filter v2.11.0 mx1.redhat.com 2C798104C8 Received: from tucnak.zalov.cz (ovpn-116-143.ams2.redhat.com [10.36.116.143]) by smtp.corp.redhat.com (Postfix) with ESMTPS id C5E576073A; Wed, 21 Jun 2017 14:40:11 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.15.2/8.15.2) with ESMTP id v5LEe80C013864; Wed, 21 Jun 2017 16:40:08 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.15.2/8.15.2/Submit) id v5LEe1Tt013863; Wed, 21 Jun 2017 16:40:01 +0200 Date: Wed, 21 Jun 2017 14:40:00 -0000 From: Jakub Jelinek To: Richard Biener Cc: Martin =?utf-8?B?TGnFoWth?= , gcc-patches@gcc.gnu.org Subject: [RFC PATCH] Fix pointer diff (was: -fsanitize=pointer-overflow support (PR sanitizer/80998)) Message-ID: <20170621144001.GR2123@tucnak> Reply-To: Jakub Jelinek References: <20170619182515.GA2123@tucnak> <20170620081348.GE2123@tucnak> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.7.1 (2016-10-04) X-IsSubscribed: yes X-SW-Source: 2017-06/txt/msg01586.txt.bz2 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 * 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