From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52a.google.com (mail-ed1-x52a.google.com [IPv6:2a00:1450:4864:20::52a]) by sourceware.org (Postfix) with ESMTPS id 8528F3858D28 for ; Mon, 6 Dec 2021 07:28:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8528F3858D28 Received: by mail-ed1-x52a.google.com with SMTP id l25so38925947eda.11 for ; Sun, 05 Dec 2021 23:28:01 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=ejT7L4xSe4hIGhcbtxHqxPOMnDJ/6AYzRMbub//KiOU=; b=U6Xgo1wY7ANrB6/PQEE1JX+aeeqtsalcao2251qDmZAjpN3gixcGXPH9GoCDmGboXZ +uA5Pv5YR16uMiGlw8ozJoeGNNrm52aaNVieJwJMAWP6Jm0a2QZyXZU887+bzhk4EfpY Tvkiaiy/0GYya/gXKm6A2SjpC+V4eMUpT1KBMS0c3MhMVR+ITvoeVRYpyqeeUAbrDrR6 FIkfSGqPCtaNWC0ATW7ScAgwIOYR+5LP4s3SUnULMTud1CR3iXGS6xHJ4RDmVamvbBev LeL9HMSOaBYwkxDVn9SfZcsPmpARbNSzM8XnLKJx3V3Qz9goTHLYVXDKS/vKNEbWkHUf frdA== X-Gm-Message-State: AOAM533uUTB4PVG44avRoxi2NHqWUzZwzfxCjBoyAmkpchKuEmPDdM2c S2bXX38UB1je9Ft83RTylZxKH7tVonb+uPj1naY= X-Google-Smtp-Source: ABdhPJypC0GnO6PQJlvBz5dA9XWrSO5wIAGqyl6YHMAa60WZNK9AoEYzkTHzbsnXt7+l47xpL9PuMH7y8POKzdn+RMM= X-Received: by 2002:a17:906:a10c:: with SMTP id t12mr43863872ejy.429.1638775680389; Sun, 05 Dec 2021 23:28:00 -0800 (PST) MIME-Version: 1.0 References: <69507e99-2f0a-1187-2701-ccfb240c77b3@redhat.com> In-Reply-To: <69507e99-2f0a-1187-2701-ccfb240c77b3@redhat.com> From: Richard Biener Date: Mon, 6 Dec 2021 08:27:49 +0100 Message-ID: Subject: Re: [PATCH 2/2] Use dominators to reduce ranger cache-flling. To: Andrew MacLeod Cc: gcc-patches Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 06 Dec 2021 07:28:03 -0000 On Fri, Dec 3, 2021 at 9:42 PM Andrew MacLeod via Gcc-patches wrote: > > When a request is made for the range of an ssa_name at some location, > the first thing we do is invoke range_of_stmt() to ensure we have looked > at the definition and have an evaluation for the name at a global > level. I recently added a patch which dramatically reduces the call > stack requirements for that call. > > Once we have confirmed the definition range has been set, a call is made > for the range-on-entry to the block of the use. This is performed by > the cache, which proceeds to walk the CFG predecessors looking for when > ranges are created (exported), existing range-on-entry cache hits, or > the definition block. Once this list of predecessors has been created, > a forward walk is done, pushing the range's through successor edges of > all the blocks were visited in the initial walk. > > If the use is far from the definition, we end up filling a lot of the > same value on these paths. Also uses which are far from a > range-modifying statement push the same value into a lot of blocks. > > This patch tries to address at least some inefficiencies. It recognizes > that > > First, if there is no range modifying stmt between this use and the last > range we saw in a dominating block, we can just use the value from the > dominating block and not fill in all the cache entries between here and > there. This is the biggest win. > > Second. if there is a range modifying statement at the end of some > block, we will have to do the appropriate cache walk to this point, but > its possible the range-on-entry to THAT block might be able to use a > dominating range, and we can prevent the walk from going any further > than this block > > Combined, this should prevent a lot of unnecessary ranges from being > plugging into the cache. > > ie, to visualize: > > bb4: > a = foo() > <..> > bb60: > if (a < 30) > <...> > bb110: > g = a + 10 > > if the first place we ask for a is in bb110, we walk the CFG from 110 > all the way back to bb4, on all paths leading back. then fill all those > cache entries. > With this patch, > a) if bb60 does not dominate bb110, the request will scan the > dominators, arrive at the definition block, have seen no range modifier, > and simply set the on-entry for 110 to the range of a. done. > b) if bb60 does dominate 110, we have no idea which edge out of 60 > dominates it, so we will revert to he existing cache algorithm. Before > doing so, it checks and determines that there are no modifiers between > bb60 and the def in bb4, and so sets the on-entry cache for bb60 to be > the range of a. Now when we do the cache fill walk, it only has to go > back as far as bb60 instead of all the way to bb4. > > Otherwise we just revert to what we do now (or if dominators are not > available). I have yet to see a case where we miss something we use to > get, but that does not mean there isn't one :-). > > The cumulative performance impact of this compiling a set of 390 GCC > source files at -O2 (measured via callgrind) is pretty decent: Negative > numbers are a compile time decrease. Thus -10% is 10% faster > compilation time. > > EVRP : %change from trunk is -26.31% (!) > VRP2 : %change from trunk is -9.53% > thread_jumps_full : %change from trunk is -15.8% > Total compilation time : %change from trunk is -1.06% > > So its not insignificant. > > Risk would be very low, unless dominators are screwed up mid-pass.. but > then the relation code would be screwed up too. > > Bootstrapped on x86_64-pc-linux-gnu with no regressions. OK? OK. Wow - I didn't realize we have this backwards CFG walk w/o dominators ... I wonder if you can add a counter to visualize places we end up using this path. I suggest to add statistics_counter_event (cfun, "slow range query", 1); or so and see with -fdump-statistics-stats which passes eventually trigger that (I suspect none?). Thanks, Richard. > Andrew > > > >