From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk1-x736.google.com (mail-qk1-x736.google.com [IPv6:2607:f8b0:4864:20::736]) by sourceware.org (Postfix) with ESMTPS id 2B37A3858439 for ; Mon, 27 Sep 2021 15:01:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 2B37A3858439 Received: by mail-qk1-x736.google.com with SMTP id q81so33396154qke.5 for ; Mon, 27 Sep 2021 08:01:22 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=73GWLAjglAigTavivfLOp0nW6MLkLZ40LmO5evvPwMU=; b=VlryHR6xP7fNayDYB9gpgPFTDM177A1fSuEhiu3ZcFB++w9LayEzCgu3ZOYEbrZLkX /t9L0KnRhJtcPf+z02NNDnpqDkRNJMhcKWGbsOasb5S/HJMPd5mCnjUIQT75tzhNJnXt 7nYIkOgTf6hV+9A6+ufrYB0NwTUU318yr+WgZcYqoeroBvce7OPz9b0gh7H/uvBt8y5M O6R23Dwws5gI51yFF5DEnAyITiZ4j7sOCMjHBdqAEIGjuVn4trpP2caOKGcBkwq4a9GZ hzBhKEi2/U+QA8l6T8fS+1C3rWrvrIYwFlZPPZ7c0PoM28JlIFIbR6PpWQVBWlVx/0DJ k1mA== X-Gm-Message-State: AOAM53356KVCs8OqdNofTJeub/aKAkAxHcitMQGcghie3PvR5+N4VyDh Ve2PTTuLn9iXXcR44948DgBg4LkViIA= X-Google-Smtp-Source: ABdhPJwa3WCLB9zXrRphJsSJ3nFEAbgkF7p6gXe+G5xqy2UOf20OPs1vJRrK1UCoPQGOSEpcJNHoSw== X-Received: by 2002:a37:464a:: with SMTP id t71mr363627qka.361.1632754881419; Mon, 27 Sep 2021 08:01:21 -0700 (PDT) Received: from [172.31.0.175] (c-98-202-48-222.hsd1.ut.comcast.net. [98.202.48.222]) by smtp.gmail.com with ESMTPSA id 18sm3492381qtz.49.2021.09.27.08.01.19 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 27 Sep 2021 08:01:20 -0700 (PDT) Subject: Re: [PATCH] Replace VRP threader with a hybrid forward threader. To: Aldy Hernandez Cc: Andrew MacLeod , GCC patches References: <20210924154653.1108992-1-aldyh@redhat.com> From: Jeff Law Message-ID: <5cd175c7-5dbb-e160-9dd2-85dcfe438059@gmail.com> Date: Mon, 27 Sep 2021 09:01:17 -0600 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 MIME-Version: 1.0 In-Reply-To: <20210924154653.1108992-1-aldyh@redhat.com> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-US X-Spam-Status: No, score=-4.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, NICE_REPLY_A, 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, 27 Sep 2021 15:01:23 -0000 On 9/24/2021 9:46 AM, Aldy Hernandez wrote: > This patch implements the new hybrid forward threader and replaces the > embedded VRP threader with it. But most importantly, it pulls it out of the VRP pass as we no longer need the VRP data or ASSERT_EXPRs. > > With all the pieces that have gone in, the implementation of the hybrid > threader is straightforward: convert the current state into > SSA imports that the solver will understand, and let the path solver > precompute ranges and relations for the path. After this setup is done, > we can use the range_query API to solve gimple statements in the threader. > The forward threader is now engine agnostic so there are no changes to > the threader per se. So the big question is do we think it's going to be this clean when we try to divorce the threading from DOM? > > I have put the hybrid bits in tree-ssa-threadedge.*, instead of VRP, > because they will also be used in the evrp removal of the DOM/threader, > which is my next task. Sweet. > > Most of the patch, is actually test changes. I have gone through every > single one and verified that we're correct. Most were trivial dump > file name changes, but others required going through the IL an > certifying that the different IL was expected. > > For example, in pr59597.c, we have one less thread because the > ASSERT_EXPR was getting in the way, and making it seem like things were > not crossing loops. The hybrid threader sees the correct representation > of the IL, and avoids threading this one case. > > The final numbers are a 12.16% improvement in jump threads immediately > after VRP, and a 0.82% improvement in overall jump threads. The > performance drop is 0.6% (plus the 1.43% hit from moving the embedded > threader into its own pass). As I've said, I'd prefer to keep the > threader in its own pass, but if this is an issue, we can address this > with a shared ranger when VRP is replaced with an evrp instance > (upcoming). Presumably we're also seeing a cannibalization of threads from later passes.   And just to be clear, this is good. And the big question, is the pass running after VRP2 doing anything particularly useful?  Do we want to try and kill it now, or later? > As I mentioned in my introductory note, paths ending in MEM_REF > conditional are missing. In reality, this didn't make a difference, as > it was so rare. However, as a follow-up, I will distill a test and add > a suitable PR to keep us honest. Yea, I don't think these are going to be a notable issue for the threaders that were previously run out of VRP.  I'm less sure about DOM though. > > There is a one-line change to libgomp/team.c silencing a new used > uninitialized warning. As my previous work with the threaders has > shown, warnings flare up after each improvement to jump threading. I > expect this to be no different. I've promised Jakub to investigate > fully, so I will analyze and add the appropriate PR for the warning > experts. ACK. > > Oh yeah, the new pass dump is called vrp-threader[12] to match each > VRP[12] pass. However, there's no reason for it to either be named > vrp-threader, or for it to live in tree-vrp.c. > > Tested on x86-64 Linux. > > OK? > > p.s. "Did I say 5 weeks? My bad, I meant 5 months." > > gcc/ChangeLog: > > * passes.def (pass_vrp_threader): New. > * tree-pass.h (make_pass_vrp_threader): Add make_pass_vrp_threader. > * tree-ssa-threadedge.c (hybrid_jt_state::register_equivs_stmt): New. > (hybrid_jt_simplifier::hybrid_jt_simplifier): New. > (hybrid_jt_simplifier::simplify): New. > (hybrid_jt_simplifier::compute_ranges_from_state): New. > * tree-ssa-threadedge.h (class hybrid_jt_state): New. > (class hybrid_jt_simplifier): New. > * tree-vrp.c (execute_vrp): Remove ASSERT_EXPR based jump > threader. > (class hybrid_threader): New. > (hybrid_threader::hybrid_threader): New. > (hybrid_threader::~hybrid_threader): New. > (hybrid_threader::before_dom_children): New. > (hybrid_threader::after_dom_children): New. > (execute_vrp_threader): New. > (class pass_vrp_threader): New. > (make_pass_vrp_threader): New. > > libgomp/ChangeLog: > > * team.c: Initialize start_data. > * testsuite/libgomp.graphite/force-parallel-4.c: Adjust. > * testsuite/libgomp.graphite/force-parallel-8.c: Adjust. > > gcc/testsuite/ChangeLog: > > * gcc.dg/torture/pr55107.c: Adjust. > * gcc.dg/tree-ssa/phi_on_compare-1.c: Adjust. > * gcc.dg/tree-ssa/phi_on_compare-2.c: Adjust. > * gcc.dg/tree-ssa/phi_on_compare-3.c: Adjust. > * gcc.dg/tree-ssa/phi_on_compare-4.c: Adjust. > * gcc.dg/tree-ssa/pr21559.c: Adjust. > * gcc.dg/tree-ssa/pr59597.c: Adjust. > * gcc.dg/tree-ssa/pr61839_1.c: Adjust. > * gcc.dg/tree-ssa/pr61839_3.c: Adjust. > * gcc.dg/tree-ssa/pr71437.c: Adjust. > * gcc.dg/tree-ssa/ssa-dom-thread-11.c: Adjust. > * gcc.dg/tree-ssa/ssa-dom-thread-16.c: Adjust. > * gcc.dg/tree-ssa/ssa-dom-thread-18.c: Adjust. > * gcc.dg/tree-ssa/ssa-dom-thread-2a.c: Adjust. > * gcc.dg/tree-ssa/ssa-dom-thread-4.c: Adjust. > * gcc.dg/tree-ssa/ssa-thread-14.c: Adjust. > * gcc.dg/tree-ssa/ssa-vrp-thread-1.c: Adjust. > * gcc.dg/tree-ssa/vrp106.c: Adjust. > * gcc.dg/tree-ssa/vrp55.c: Adjust. OK jeff