From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52d.google.com (mail-ed1-x52d.google.com [IPv6:2a00:1450:4864:20::52d]) by sourceware.org (Postfix) with ESMTPS id A4B0939BC05E for ; Fri, 25 Jun 2021 07:54:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A4B0939BC05E Received: by mail-ed1-x52d.google.com with SMTP id r7so12131529edv.12 for ; Fri, 25 Jun 2021 00:54:31 -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=EPZ5KhvPq8f5W+NZC3hZYE0cwVQx6DVCyn9xjUNkjR4=; b=WbibZp/sxYedf55Da7Rou9xVXFKEuMjtoCYvh12SoYrMXac5+Km/vk3xILypB1V1Wx B+3JlNUOo6DIMplin1hrpFmiw03byJe1Qct2ZQsLQC/483wAbor8kc1YkB/WRSoSIpPk wt0Q9c4G5gfY76jmq0O9JbmGpxiCFIdHu1jAsDnc/S+DOaM58BFWH8V2g0CU2n4bbaxd oDk25hg9DZYP1j3twCcksdhnFUFgcF0GYBkBREaLQBxiIYP/KfkiDZgyRieWsF9RyTCr DizVtKRZRS6urRO9rON6i6IEj5i2kwwR+KKosKbHmAAc6NuxKUkiyHojPHdw3Bw3TkE9 yayQ== X-Gm-Message-State: AOAM530uE7iD+UgWm4q42q7kImDpbFlVSgEU2XUxLiEV/nKWLc8UMYLN RTIfKbSD7BXVmqksZQ1TlKTsSox6kmcbhiQpwZU= X-Google-Smtp-Source: ABdhPJzxm2wWX196GuKbLPGcSyRE3zC1BhFyCxqDML0dK+y3R533JiiNKTmEnGzrlAC7lbBRttrMctP2uK4rvJ9z+98= X-Received: by 2002:aa7:c3d6:: with SMTP id l22mr12854662edr.245.1624607670732; Fri, 25 Jun 2021 00:54:30 -0700 (PDT) MIME-Version: 1.0 References: <07775b9d-b8eb-48cb-57ef-9cc278d38967@redhat.com> <550e1ffd-957c-f348-49b6-b980c072c307@redhat.com> <3ac5e4e1-405f-fd5a-cb36-433a93f77df4@gmail.com> In-Reply-To: <3ac5e4e1-405f-fd5a-cb36-433a93f77df4@gmail.com> From: Richard Biener Date: Fri, 25 Jun 2021 09:54:19 +0200 Message-ID: Subject: Re: replacing the backwards threader and more To: Jeff Law Cc: Aldy Hernandez , GCC Mailing List , Andrew MacLeod Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.7 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: Fri, 25 Jun 2021 07:54:33 -0000 On Thu, Jun 24, 2021 at 6:14 PM Jeff Law wrote: > > > > On 6/21/2021 8:40 AM, Aldy Hernandez wrote: > > > > > > On 6/9/21 2:09 PM, Richard Biener wrote: > >> 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)? > > > > As promised. > > > > *** LEGACY: > > ethread42:61152 30.1369% (61152 threads for 30.1% of total) > > thread117:29646 14.6101% > > vrp118:62088 30.5982% > > thread132:2232 1.09997% > > dom133:31116 15.3346% > > thread197:1950 0.960998% > > dom198:10661 5.25395% > > thread200:587 0.289285% > > vrp201:3482 1.716% > > Total: 202914 > > > The above is from current trunk with my patches applied, defaulting to > > legacy mode. It follows the pass number nomenclature in the > > *.statistics files. > > > > New threader code (This is what I envision current trunk to look with > > my patchset): > > > > *** RANGER: > > ethread42:64389 30.2242% > > thread117:49449 23.2114% > > vrp118:46118 21.6478% > > thread132:8153 3.82702% > > dom133:27168 12.7527% > > thread197:5542 2.60141% > > dom198:8191 3.84485% > > thread200:1038 0.487237% > > vrp201:2990 1.40351% > > Total: 213038 > So this makes me think we should focus on dropping thread197, thread200, > & vrp201 and I'd probably focus on vrp201 first since we know we want to > get rid of it anyway and that may change the data for thread???. Then > I'd be looking at thread200 and thread197 in that order. I suspect that > at least some of the cases in thread200 and vrp201 are exposed by dom198. It might be interesting to see replacing vrp201 with evrp and run thread200 after that or alternatively move dom198 after vrp201 and then replace vrp201 with evrp and kill off thread200 completely. Supposedly we will for now keep the forward threading in DOM. Since we have FRE right before DOM it's likely only threading that DOM performs now. (but of course testcases will need adjustment) Richard. > > Jeff