From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x634.google.com (mail-ej1-x634.google.com [IPv6:2a00:1450:4864:20::634]) by sourceware.org (Postfix) with ESMTPS id 171AD3898517 for ; Mon, 28 Jun 2021 08:12:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 171AD3898517 Received: by mail-ej1-x634.google.com with SMTP id yy20so20708888ejb.6 for ; Mon, 28 Jun 2021 01:12:48 -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=+6t74SjDNPo4bjx0rgBx2jz26OTKeC2omeq7W2AGxno=; b=YuSQRIrQstOKR6yBrqz60UH5iLfoP4EJmPssJ1hWP0jGt9bQvnji2v1qeE0LJZhgo+ y4eaq1G24AmdzGcq/8Ry6eqGSS29GSp05MXyJogSBagnIiqPZXPwHD02i9YH6ltqySbv KAsyYtNMExBJuymy7WCqK9UBq6TEgb7Aj+WxAZCTfZHKQsPATncgsjNRK03fR98n5988 oqbmNalQHqIPXnMbzQboePVOOs/MXedNYi4P56Tzxg/fmAxxN69K1ehvICsjo9hEmhRe gnMBAiIqd1mpsg+Ke5coHnpsnXBgmpjUB52dTu+3uZBoVAFfWSaGk6NKasvpYzjQdnXY UNQw== X-Gm-Message-State: AOAM533H4vo26CSCUo0Iwpcc1s/qNW+DFJsohAsuTr/BQB/kFjlhOI7a hQdV9Hfm5Our3xmGP/Qlspk0aRagmBbdGDsJNcg= X-Google-Smtp-Source: ABdhPJxkq4fnUmhMsW9t97NJLtUqxvsgK2igcS4YgGv8/hvrwb5D91Ckg57fjtDd+myO5hw233k4JbXuAfJ3HB7a5fA= X-Received: by 2002:a17:907:3faa:: with SMTP id hr42mr23031792ejc.129.1624867967145; Mon, 28 Jun 2021 01:12:47 -0700 (PDT) MIME-Version: 1.0 References: <860299c5-8f2e-2d1f-c7bc-bab4eb25ec8a@redhat.com> <69174dc2-450b-2f57-1469-31892b937158@redhat.com> In-Reply-To: <69174dc2-450b-2f57-1469-31892b937158@redhat.com> From: Richard Biener Date: Mon, 28 Jun 2021 10:12:36 +0200 Message-ID: Subject: Re: [PATCH] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction To: Aldy Hernandez Cc: Andrew MacLeod , Di Zhao , "gcc-patches@gcc.gnu.org" , Jeff Law 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-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, 28 Jun 2021 08:12:50 -0000 On Sun, Jun 27, 2021 at 5:46 PM Aldy Hernandez wrote: > > > > On 6/25/21 9:38 AM, Richard Biener wrote: > > On Thu, Jun 24, 2021 at 5:01 PM Andrew MacLeod wrote: > >> > >> On 6/24/21 9:25 AM, Andrew MacLeod wrote: > >>> On 6/24/21 8:29 AM, Richard Biener wrote: > >>> > >>> > >>> THe original function in EVRP currently looks like: > >>> > >>> =========== BB 2 ============ > >>> : > >>> if (a_5(D) == b_6(D)) > >>> goto ; [INV] > >>> else > >>> goto ; [INV] > >>> > >>> =========== BB 8 ============ > >>> Equivalence set : [a_5(D), b_6(D)] edge 2->8 provides > >>> a_5 and b_6 as equivalences > >>> : > >>> goto ; [100.00%] > >>> > >>> =========== BB 6 ============ > >>> : > >>> # i_1 = PHI <0(8), i_10(5)> > >>> if (i_1 < a_5(D)) > >>> goto ; [INV] > >>> else > >>> goto ; [INV] > >>> > >>> =========== BB 3 ============ > >>> Relational : (i_1 < a_5(D)) edge 6->3 provides > >>> this relation > >>> : > >>> if (i_1 == b_6(D)) > >>> goto ; [INV] > >>> else > >>> goto ; [INV] > >>> > >>> > >>> So It knows that a_5 and b_6 are equivalence, and it knows that i_1 < > >>> a_5 in BB3 as well.. > >>> > >>> so we should be able to indicate that i_1 == b_6 as [0,0].. we > >>> currently aren't. I think I had turned on equivalence mapping during > >>> relational processing, so should be able to tag that without > >>> transitive relations... I'll have a look at why. > >>> > >>> And once we get a bit further along, you will be able to access this > >>> without ranger.. if one wants to simply register the relations directly. > >>> > >>> Anyway, I'll get back to you why its currently being missed. > >>> > >>> Andrew > >>> > >>> > >>> > >> As promised. There was a typo in the equivalency comparisons... so it > >> was getting missed. With the fix, the oracle identifies the relation > >> and evrp will now fold that expression away and the IL becomes: > >> > >> : > >> if (a_5(D) == b_6(D)) > >> goto ; [INV] > >> else > >> goto ; [INV] > >> > >> : > >> i_10 = i_1 + 1; > >> > >> : > >> # i_1 = PHI <0(2), i_10(3)> > >> if (i_1 < a_5(D)) > >> goto ; [INV] > >> else > >> goto ; [INV] > >> > >> : > >> return; > >> > >> for the other cases you quote, there are no predictions such that if a > >> != 0 then this equivalency exists... > >> > >> + if (a != 0) > >> + { > >> + c = b; > >> + } > >> > >> but the oracle would register that in the TRUE block, c and b are > >> equivalent... so some other pass that was interested in tracking > >> conditions that make a block relevant would be able to compare relations... > > > > I guess to fully leverage optimizations for cases like > > > > if (a != 0) > > c = b; > > ... > > if (a != 0) > > { > > if (c == b) > > ... > > } > > > > one would need to consider the "optimally jump threaded path" to the > > program point where the to be optimized stmt resides, making all > > originally conditional but on the jump threaded path unconditional > > relations and equivalences available. > > > > For VN that could be done by unwinding to the CFG merge after > > the first if (a != 0), treating only one of the predecessor edges > > as executable and registering the appropriate a != 0 result and > > continue VN up to the desired point, committing to the result > > until before the CFG merge after the second if (a != 0). And then > > unwinding again for the "else" path. Sounds like a possible > > explosion in complexity as well if second-order opportunities > > arise. > > > > That is, we'd do simplifications exposed by jump threading but > > without actually doing the jump threading (which will of course > > not allow all possible simplifications w/o inserting extra PHIs > > for computations we might want to re-use). > > FWIW, as I mention in the PR, if the upcoming threader work could be > taught to use the relation oracle, it could easily solve the conditional > flowing through the a!=0 path. However, we wouldn't be able to thread > it because in this particular case, the path crosses loop boundaries. > > I leave it to Jeff/others to pontificate on whether the jump-threader > path duplicator could be taught to through loops. ?? If the path doesn't end outside of the loop then it will usually create an alternate entry and thus turn the loop into an irreducible region - that's quite a bad thing to do unless we somehow get a high profitability hint and are late in the compilation. Richard. > > Aldy >