From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 55881 invoked by alias); 21 Jun 2017 16:27:18 -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 55856 invoked by uid 89); 21 Jun 2017 16:27:17 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.0 required=5.0 tests=AWL,BAYES_00,KAM_LAZY_DOMAIN_SECURITY,T_RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=cb X-HELO: mail3-relais-sop.national.inria.fr Received: from mail3-relais-sop.national.inria.fr (HELO mail3-relais-sop.national.inria.fr) (192.134.164.104) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 21 Jun 2017 16:27:15 +0000 Received: from stedding-dock.saclay.inria.fr ([193.55.177.248]) by mail3-relais-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 21 Jun 2017 18:26:49 +0200 Date: Wed, 21 Jun 2017 16:27:00 -0000 From: Marc Glisse Reply-To: gcc-patches@gcc.gnu.org To: Jakub Jelinek cc: Richard Biener , =?ISO-8859-15?Q?Martin_Li=A8ka?= , gcc-patches@gcc.gnu.org Subject: Re: [RFC PATCH] Fix pointer diff (was: -fsanitize=pointer-overflow support (PR sanitizer/80998)) In-Reply-To: <20170621144001.GR2123@tucnak> Message-ID: References: <20170619182515.GA2123@tucnak> <20170620081348.GE2123@tucnak> <20170621144001.GR2123@tucnak> User-Agent: Alpine 2.20 (DEB 67 2015-01-07) MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset=US-ASCII X-SW-Source: 2017-06/txt/msg01593.txt.bz2 On Wed, 21 Jun 2017, Jakub Jelinek wrote: > 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? Adding to match.pd a few more simple reassoc transformations (like (c-b)+(b-a) for instance) that work for both signed and unsigned is on my TODO-list, though that may not be enough. Maybe together with fixing whatever produced the negation would suffice? > 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. (this testcase was meant as a simpler version of vector.size() < vector.capacity() ) It does indeed seem impossible to do this optimization with the unsigned pointer subtraction. If we consider pointers as unsigned, with a subtraction that has a signed result with the constraint that overflow is undefined, we cannot model that optimally with just the usual signed/unsigned operations, so I am in favor of POINTER_DIFF, at least in the long run (together with having a signed second argument for POINTER_PLUS, etc). For 64-bit platforms it might have been easier to declare that the upper half (3/4 ?) of the address space doesn't exist... > 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. Once we have this last expression, we have lost, we need to know that the multiplication cannot overflow for this. When the size multiplications are done in a signed type in the future (?), it might help. On the other hand, is this an important optimization? I am surprised we are only doing this transformation in generic (so some hack in the front-end could still work), it shouldn't be hard to implement some subset of fold_addr_of_array_ref_difference in match.pd (it is recursive so a complete move may be harder). But that would make your patch break even more stuff :-( -- Marc Glisse