From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 38713 invoked by alias); 23 Aug 2019 15:39:32 -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 38703 invoked by uid 89); 23 Aug 2019 15:39:32 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS autolearn=ham version=3.3.1 spammy=year, p7n 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; Fri, 23 Aug 2019 15:39:30 +0000 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 53007356CE; Fri, 23 Aug 2019 15:39:29 +0000 (UTC) Received: from localhost.localdomain (ovpn-112-44.rdu2.redhat.com [10.10.112.44]) by smtp.corp.redhat.com (Postfix) with ESMTP id 527D4600F8; Fri, 23 Aug 2019 15:39:28 +0000 (UTC) Subject: Re: [RFA] [tree-optimization/80576] Handle non-constant sizes in DSE To: Martin Sebor , gcc-patches References: <8b836cef-7aa1-fd3d-5585-c2a6fe74bed6@redhat.com> <72ac1813-0ca3-6798-a77b-7f1ab914d91c@redhat.com> <845c672d-6d48-69a9-3210-eafb5e3b374b@gmail.com> <2a026de3-739a-2e6a-1468-b0109f585514@redhat.com> <4525a1d5-f27c-38f5-994a-09914e25fe21@gmail.com> From: Jeff Law Openpgp: preference=signencrypt Message-ID: <20901b67-7aa4-30a9-a821-39ffce2fbb18@redhat.com> Date: Fri, 23 Aug 2019 16:50:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.4.0 MIME-Version: 1.0 In-Reply-To: <4525a1d5-f27c-38f5-994a-09914e25fe21@gmail.com> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-IsSubscribed: yes X-SW-Source: 2019-08/txt/msg01663.txt.bz2 On 8/22/19 10:39 AM, Martin Sebor wrote: > On 8/21/19 4:34 PM, Jeff Law wrote: >> On 8/16/19 4:21 PM, Martin Sebor wrote: >>> On 8/16/19 12:15 PM, Jeff Law wrote: >>>> On 8/16/19 12:09 PM, Marc Glisse wrote: >>>>> On Fri, 16 Aug 2019, Jeff Law wrote: >>>>> >>>>>> This patch improves our ability to detect dead stores by handling >>>>>> cases >>>>>> where the size memcpy, memset, strncpy, etc call is not constant.  >>>>>> This >>>>>> addresses some, but not all, of the issues in 80576. >>>>>> >>>>>> The key here is when the size is not constant we can make >>>>>> conservative >>>>>> decisions that still give us a chance to analyze the code for dead >>>>>> stores. >>>>>> >>>>>> Remember that for dead store elimination, we're trying to prove that >>>>>> given two stores, the second store overwrites (partially or fully) >>>>>> the >>>>>> same memory locations as the first store.  That makes the first store >>>>>> either partially or fully dead. >>>>>> >>>>>> When we encounter the first store, we set up a bitmap of bytes >>>>>> written >>>>>> by that store (live_bytes).  We then look at subsequent stores and >>>>>> clear >>>>>> the appropriate entries in the bitmap. >>>>>> >>>>>> If the first store has a nonconstant length argument we can use the >>>>>> range of the length argument (max) and the size of the destination >>>>>> object to make a conservative estimation of how many bytes are >>>>>> written. >>>>>> >>>>>> For the second store the conservative thing to do for a non-constant >>>>>> length is to use the minimum of the range of the length argument. >>>>> >>>>> So I guess it won't handle things like >>>>> >>>>> void f(char*p,int n){ >>>>>     __builtin_memset(p,3,n); >>>>>     __builtin_memset(p,7,n); >>>>> } >>>>> >>>>> where we know nothing about the length, except that it is the same? Or >>>>> do you look at symbolic ranges? >>>> Nope.  I think ao_ref can represent that, so it'd just be a matter of >>>> recording "n" as the length, then verifying that the second call's >>>> length is "n" as well.  That makes the first call dead.  We'd have to >>>> bypass the byte tracking in that case, but I think that's trivial >>>> because we already have a means to do that when the sizes are too >>>> large. >>>> >>>>> >>>>>> This doesn't come up a lot in practice.  But it also happens to put >>>>>> some >>>>>> of the infrastructure in place to handle strcpy and strcpy_chk which >>>>>> are >>>>>> needed to fully resolve 80576. >>>>>> >>>>>> Bootstrapped and regression tested on x86, x86_64, ppc64le, ppc64, >>>>>> ppc32, aarch64, sparc, s390x and probably others.  Also verified that >>>>>> the tests work on the various *-elf targets in my tester. >>>>>> >>>>>> OK for the trunk? >>>>> >>>>> ENOPATCH >>>> Opps.    Attached. >>> >>> It's an improvement and I realize you said it doesn't handle >>> everything and that you don't think it comes up a lot, but... >>> I would actually expect the following example (from the bug) >>> not to be that uncommon: >>> >>>    void g (char *s) >>>    { >>>      char a[8]; >>>      __builtin_strcpy (a, s); >>>      __builtin_memset (a, 0, sizeof a); >>>      f (a); >>>    } >>> >>> or at least to be more common than the equivalent alternative >>> the improvement does optimize: >>> >>>    void g (char *s) >>>    { >>>      char a[8]; >>>      __builtin_memcpy (a, s,  __builtin_strlen (s)); >>>      __builtin_memset (a, 0, 8); >>>      f (a); >>>    } >>> >>> It seems that making the first one work should be just a matter >>> of handling strcpy analogously (the string length doesn't matter). >>> >>> As an aside, the new tests make me realize that -Wstringop-overflow >>> should be enhanced to detect this problem (i.e., a consider >>> the largest size in a PHI). >> Certainly not seeing much of these in the code I've looked at.  It may >> be a case that aliasing gets in the way often. >> >> Also note that we've got the same issues in this space that we did with >> the strlen optimization improvements for last year.  I totally spaced >> that and the net result may be we have to avoid using the type size for >> anything in DSE which may make it impossible to really do a good job. > > The issue with the strlen optimization was that it relied on > the type of subobjects of multidimensional arrays and structs > to determine the maximum valid size of the access to them. > This ran afoul of assumptions in code that doesn't respect > subobject boundaries. Right. And my proposed DSE changes have the same fundamental problem. > > This is not a concern for outermost objects like in the example > above.  strlen and other parts of GCC still make use of their > size for optimization.  The middle-end diagnostics I've been > adding still expect code to respect subobject boundaries.  I've > been doing that for this very reason: to let us do a better job > not just optimizing code, but also diagnosing bugs: find more > real problems with fewer false positives. True, but the proposed DSE code does not restrict itself to outermost objects. That's what I need to fix before resubmitting. Thankfully it's not terribly hard. jeff