From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x534.google.com (mail-ed1-x534.google.com [IPv6:2a00:1450:4864:20::534]) by sourceware.org (Postfix) with ESMTPS id D2D753848434 for ; Wed, 9 Jun 2021 12:09:38 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D2D753848434 Received: by mail-ed1-x534.google.com with SMTP id w21so28302759edv.3 for ; Wed, 09 Jun 2021 05:09:38 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=JFgajcT5DCFD36tyOx/XvN2971vUWiAkos7vu8tFSQg=; b=MCRAE6xq/nY+X19qJW5BdryqiYtVIfEez4dalQ1xwHlwgQJXPcww5AXHaPWBwgG2I0 QEKGfaVZRhZ01+eFbC8+V0YBk5WXGYUKpwvY85ZgJ3CiHub7VB409w0WNsbZ/LPfoIP8 /BW2ItknEIhQp0q56H2OMUjRXwC+MiOTwj/PiXeFQxU3npR4oXOgAHS9hUzW5trVEYrj mjsKewhuTKyQdLJeI0myORcNyoFE9YhaDdgAxkWP/bPwuNP9KRxg1pMjSwoMYW8oiVSg WjBCT+d1sOKzTC40kvWx736vv2L60xtAmZYcRpCF9EICaIPdb9GsUJ1QgZPZTXee9bTW edkQ== X-Gm-Message-State: AOAM532DxZV1ISBJDMvZpmSbaRD6z1PZbqLlCeQlwZ6HWB+r4waWTEWt pG7c1ZtKxQKtQrLhV9nFQHpRx6yhC36Y9I7R8rg= X-Google-Smtp-Source: ABdhPJzngD9ZtgBB1nO6AJu99vkapPAsz/JoaSZi0w/aqAfV3Ww1snNkUz/jP/Z3wVMzG+dWrE2pf/zPQdJ9Vn0q5zI= X-Received: by 2002:aa7:cd42:: with SMTP id v2mr30814385edw.245.1623240577685; Wed, 09 Jun 2021 05:09:37 -0700 (PDT) MIME-Version: 1.0 References: <07775b9d-b8eb-48cb-57ef-9cc278d38967@redhat.com> In-Reply-To: <07775b9d-b8eb-48cb-57ef-9cc278d38967@redhat.com> From: Richard Biener Date: Wed, 9 Jun 2021 14:09:26 +0200 Message-ID: Subject: Re: replacing the backwards threader and more To: Aldy Hernandez Cc: Jeff Law , GCC Mailing List Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-3.0 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.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 09 Jun 2021 12:09:40 -0000 On Wed, Jun 9, 2021 at 1:50 PM Aldy Hernandez via Gcc wrote: > > Hi Jeff. Hi folks. > > What started as a foray into severing the old (forward) threader's > dependency on evrp, turned into a rewrite of the backwards threader > code. I'd like to discuss the possibility of replacing the current > backwards threader with a new one that gets far more threads and can > potentially subsume all threaders in the future. > > I won't include code here, as it will just detract from the high level > discussion. But if it helps, I could post what I have, which just needs > some cleanups and porting to the latest trunk changes Andrew has made. > > Currently the backwards threader works by traversing DEF chains through > PHIs leading to possible paths that start in a constant. When such a > path is found, it is checked to see if it is profitable, and if so, the > constant path is threaded. The current implementation is rather limited > since backwards paths must end in a constant. For example, the > backwards threader can't get any of the tests in > gcc.dg/tree-ssa/ssa-thread-14.c: > > if (a && b) > foo (); > if (!b && c) > bar (); > > etc. > > After my refactoring patches to the threading code, it is now possible > to drop in an alternate implementation that shares the profitability > code (is this path profitable?), the jump registry, and the actual jump > threading code. I have leveraged this to write a ranger-based threader > that gets every single thread the current code gets, plus 90-130% more. > > Here are the details from the branch, which should be very similar to > trunk. I'm presenting the branch numbers because they contain Andrew's > upcoming relational query which significantly juices up the results. > > New threader: > ethread:65043 (+3.06%) > dom:32450 (-13.3%) > backwards threader:72482 (+89.6%) > vrp:40532 (-30.7%) > Total threaded: 210507 (+6.70%) > > This means that the new code gets 89.6% more jump threading > opportunities than the code I want to replace. In doing so, it reduces > the amount of DOM threading opportunities by 13.3% and by 30.7% from the > VRP jump threader. The total improvement across the jump threading > opportunities in the compiler is 6.70%. > > However, these are pessimistic numbers... > > I have noticed that some of the threading opportunities that DOM and VRP > now get are not because they're smarter, but because they're picking up > opportunities that the new code exposes. I experimented with running an > iterative threader, and then seeing what VRP and DOM could actually get. > This is too expensive to do in real life, but it at least shows what > the effect of the new code is on DOM/VRP's abilities: > > Iterative threader: > ethread:65043 (+3.06%) > dom:31170 (-16.7%) > thread:86717 (+127%) > vrp:33851 (-42.2%) > Total threaded: 216781 (+9.90%) > > This means that the new code not only gets 127% more cases, but it > reduces the DOM and VRP opportunities considerably (16.7% and 42.2% > respectively). The end result is that we have the possibility of > getting almost 10% more jump threading opportunities in the entire > compilation run. Yeah, DOM once was iterating ... You probably have noticed that we have very man (way too many) 'thread' passes, often in close succession with each other or DOM or VRP. So in the above numbers I wonder if you can break down the numbers individually for the actual passes (in their order)? > (Note that the new code gets even more opportunities, but I'm only > reporting the profitable ones that made it all the way through to the > threader backend, and actually eliminated a branch.) > > The overall compilation hit from this work is currently 1.38% as > measured by callgrind. We should be able to reduce this a bit, plus we > could get some of that back if we can replace the DOM and VRP threaders > (future work). > > My proposed implementation should be able to get any threading > opportunity, and will get more as range-ops and ranger improve. > > I can go into the details if necessary, but the gist of it is that we > leverage the import facility in the ranger to only look up paths that > have a direct repercussion in the conditional being threaded, thus > reducing the search space. This enhanced path discovery, plus an engine > to resolve conditionals based on knowledge from a CFG path, is all that > is needed to register new paths. There is no limit to how far back we > look, though in practice, we stop looking once a path is too expensive > to continue the search in a given direction. > > The solver API is simple: > > // This class is a thread path solver. Given a set of BBs indicating > // a path through the CFG, range_in_path() will return the range > // of an SSA as if the BBs in the path would have been executed in > // order. > // > // Note that the blocks are in reverse order, thus the exit block is > path[0]. > > class thread_solver : gori_compute > { > > public: > thread_solver (gimple_ranger &ranger); > virtual ~thread_solver (); > void set_path (const vec *, const bitmap_head *imports); > void range_in_path (irange &, tree name); > void range_in_path (irange &, gimple *); > ... > }; > > Basically, as we're discovering paths, we ask the solver what the value > of the final conditional in a BB is in a given path. If it resolves, we > register the path. > > A follow-up project would be to analyze what DOM/VRP are actually > getting that we don't, because in theory with an enhanced ranger, we > should be able to get everything they do (minus some float stuff, and > some CSE things DOM does). However, IMO, this is good enough to at > least replace the current backwards threading code. > > My suggestion would be to keep both implementations, defaulting to the > ranger based, and running the old code immediately after-- trapping if > it can find any threading opportunities. But due to iteration uncovering new opportunities this will inevitably break, no? > After a few weeks, we could > kill the old code. Note that for analyzing threadings done apart from looking at overall numbers the statistics infrastructure can be useful, likewise could be the opt-info one where you can diff stats based on file or function (statistics) or even location of a participating jump (opt-info). If you are re-using tree-ssa-thread{edge,update}.{c,h} anyway you probably only have to amend one or two places. I'm personally breaking things down to file/function via statistics to spot gross differences more locally. IMHO removing threading from VRP (as a step to make "VRP" into another EVRP run) should be part of the initial transition, there's always a thread pass nearby. Performing threading from EVRP itself might be another option to evaluate. Trimming down the number of (now backwards-)threaders would be another goal. Richard. > Thoughts? > > Aldy > > p.s. BTW, ranger-based is technically a minomer. It's gori based. We > don't need the entire ranger caching ability here. I'm only using it to > get the imports for the interesting conditionals, since those are static. >