From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 84676 invoked by alias); 22 Jun 2017 08:31:38 -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 84515 invoked by uid 89); 22 Jun 2017 08:31:37 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00,SPF_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=fear X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 22 Jun 2017 08:31:35 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 6A419AB5D; Thu, 22 Jun 2017 08:31:33 +0000 (UTC) Date: Thu, 22 Jun 2017 08:31:00 -0000 From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jakub Jelinek , =?ISO-8859-15?Q?Martin_Li=A8ka?= Subject: Re: [RFC PATCH] Fix pointer diff (was: -fsanitize=pointer-overflow support (PR sanitizer/80998)) In-Reply-To: Message-ID: References: <20170619182515.GA2123@tucnak> <20170620081348.GE2123@tucnak> <20170621144001.GR2123@tucnak> User-Agent: Alpine 2.20 (LSU 67 2015-01-07) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-SW-Source: 2017-06/txt/msg01625.txt.bz2 On Wed, 21 Jun 2017, Marc Glisse wrote: > 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? I guess try to fix the negation and see if that magically fixes things... > > 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. Yep :/ This is the issue with all the non-pointer integer folding fixes as well -- as soon as we introduce unsigned ops for the fear of introducing undefined overflow we lose on followup optimization opportunities. > 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... I repeatedly thought of POINTER_DIFF_EXPR but adding such a basic tree code is quite a big job. So we'd have POINTER_DIFF_EXPR take two pointer typed args and produce ptrdiff_t. What's the advantage of having this? And yes, I agree that POINTER_PLUS_EXPR should take ptrdiff_t rather than sizetype offset -- changing one without the other will lead to awkwardness in required patterns involving both like (p - q) + q. As said, it's a big job with likely all sorts of (testsuite) fallout. > > 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. Not sure where the unsigned multiply comes from -- I guess we fold it inside the cast ... > 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 :-( It's always the question whether the above testsuite regressions have any real-world impact of course. I don't like the idea of not doing foldings condidional on sanitization too much. Richard.