From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id A89E33856DF5 for ; Wed, 3 Aug 2022 08:25:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A89E33856DF5 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id AC6C11FE2E; Wed, 3 Aug 2022 08:25:54 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 972AC2C141; Wed, 3 Aug 2022 08:25:54 +0000 (UTC) Date: Wed, 3 Aug 2022 08:25:54 +0000 (UTC) From: Richard Biener To: Tamar Christina cc: Richard Biener , "jakub@redhat.com" , nd , "gcc-patches@gcc.gnu.org" Subject: RE: [PATCH 2/2]middle-end: Support recognition of three-way max/min. In-Reply-To: Message-ID: References: <29n37062-n3s3-71o9-8411-r851o15ss72@fhfr.qr> User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-5.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: Wed, 03 Aug 2022 08:25:57 -0000 On Wed, 3 Aug 2022, Tamar Christina wrote: > > > -----Original Message----- > > From: Richard Biener > > Sent: Tuesday, August 2, 2022 10:11 AM > > To: Tamar Christina > > Cc: Richard Biener ; jakub@redhat.com; nd > > ; gcc-patches@gcc.gnu.org > > Subject: Re: [PATCH 2/2]middle-end: Support recognition of three-way > > max/min. > > > > On Tue, Aug 2, 2022 at 10:33 AM Tamar Christina via Gcc-patches > patches@gcc.gnu.org> wrote: > > > > > > > > > > When this function replaces the edge it doesn't seem to update > > > > > > > the > > > > > > dominators. > > > > > > > Since It's replacing the middle BB we then end up with an > > > > > > > error > > > > > > > > > > > > > > gcc/testsuite/gcc.dg/tree-ssa/minmax-14.c:17:1: error: > > > > > > > dominator of 5 should be 4, not 2 > > > > > > > > > > > > > > during early verify. So instead, I replace the BB but defer > > > > > > > its deletion until cleanup which removes it and updates the > > dominators. > > > > > > > > > > > > Hmm, for a diamond shouldn't you replace > > > > > > > > > > > > if (EDGE_SUCC (cond_block, 0)->dest == bb) > > > > > > edge_to_remove = EDGE_SUCC (cond_block, 1); > > > > > > else > > > > > > edge_to_remove = EDGE_SUCC (cond_block, 0); > > > > > > > > > > > > with > > > > > > > > > > > > if (EDGE_SUCC (cond_block, 0)->dest == bb) > > > > > > edge_to_remove = EDGE_SUCC (cond_block, 1); > > > > > > else if (EDGE_SUCC (cond_block, 1)->dest == bb) > > > > > > edge_to_remove = EDGE_SUCC (cond_block, 0); > > > > > > > > > > > > thus, the code expects to be left with a fallthru to the PHI > > > > > > block which is expected to have the immediate dominator being > > > > > > cond_block but with a diamond there's a (possibly empty) block > > > > > > inbetween and dominators are wrong. > > > > > > > > > > Agreed, but the (EDGE_SUCC (cond_block, 1)->dest == bb) doesn't > > > > > seem like the Right one since for a diamond there will be a block > > > > > in between the two. Did you perhaps mean EDGE_SUCC (EDGE_SUCC > > > > > (cond_block, 1)->dest, 0)->dest == bb? i.e. that that destination > > > > > across the > > > > diamond be bb, and then you remove the middle block? > > > > > > > > Hmm, I think my condition was correct - the code tries to remove the > > > > edge to the middle-block and checks the remaining edge falls through > > > > to the merge block. With a true diamond there is no fallthru to the > > > > merge block to keep so we better don't remove any edge? > > > > > > > > > For the minmax diamond we want both edges removed, since all the > > > > > code in the middle BBs are now dead. But this is probably not > > > > > true in the general > > > > sense. > > > > > > Ah! Sorry I was firing a few cylinders short, I get what you mean now: > > > > > > @@ -425,8 +439,19 @@ replace_phi_edge_with_variable (basic_block > > cond_block, > > > edge edge_to_remove; > > > if (EDGE_SUCC (cond_block, 0)->dest == bb) > > > edge_to_remove = EDGE_SUCC (cond_block, 1); > > > - else > > > + else if (EDGE_SUCC (cond_block, 1)->dest == bb) > > > edge_to_remove = EDGE_SUCC (cond_block, 0); > > > + else > > > + { > > > + /* If neither edge from the conditional is the final bb > > > + then we must have a diamond block, in which case > > > + the true edge was changed by SET_USE above and we must > > > + mark the other edge as the false edge. */ > > > + gcond *cond = as_a (last_stmt (cond_block)); > > > + gimple_cond_make_false (cond); > > > + return; > > > + } > > > + > > > > Note there is already > > > > if (EDGE_COUNT (edge_to_remove->dest->preds) == 1) > > { > > ... > > } > > else > > { > > /* If there are other edges into the middle block make > > CFG cleanup deal with the edge removal to avoid > > updating dominators here in a non-trivial way. */ > > gcond *cond = as_a (last_stmt (cond_block)); > > if (edge_to_remove->flags & EDGE_TRUE_VALUE) > > gimple_cond_make_false (cond); > > else > > gimple_cond_make_true (cond); > > } > > > > I'm not sure how you can say 'e' is always the true edge? May I suggest to > > amend the first condition with edge_to_remove && (and initialize that to > > NULL) and use e->flags instead of edge_to_remove in the else, of course > > also inverting the logic since we're keeping 'e'? > > As discussed on IRC, here's the version using keep_edge: > > @@ -422,12 +436,17 @@ replace_phi_edge_with_variable (basic_block cond_block, > SET_USE (PHI_ARG_DEF_PTR (phi, e->dest_idx), new_tree); > > /* Remove the empty basic block. */ > - edge edge_to_remove; > + edge edge_to_remove = NULL, keep_edge = NULL; > if (EDGE_SUCC (cond_block, 0)->dest == bb) > edge_to_remove = EDGE_SUCC (cond_block, 1); > - else > + else if (EDGE_SUCC (cond_block, 1)->dest == bb) > edge_to_remove = EDGE_SUCC (cond_block, 0); > - if (EDGE_COUNT (edge_to_remove->dest->preds) == 1) > + else if ((keep_edge = find_edge (cond_block, e->src))) > + ; > + else > + gcc_unreachable (); > + > + if (edge_to_remove && EDGE_COUNT (edge_to_remove->dest->preds) == 1) > { > e->flags |= EDGE_FALLTHRU; > e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); > @@ -438,6 +457,18 @@ replace_phi_edge_with_variable (basic_block cond_block, > gsi = gsi_last_bb (cond_block); > gsi_remove (&gsi, true); > } > + else if (keep_edge) > + { > + /* If we're in a diamond then we have identified the edge > + that we want to keep. Since the dominators will require > + updating in a non-trivial way we leave it to CFG cleanup > + but mark the condition as appropriately true/false. */ > + gcond *cond = as_a (last_stmt (cond_block)); > + if (keep_edge->flags & EDGE_FALSE_VALUE) > + gimple_cond_make_false (cond); > + else if (keep_edge->flags & EDGE_TRUE_VALUE) > + gimple_cond_make_true (cond); > + } > else > { > /* If there are other edges into the middle block make I meant to merge the keep_edge and the existing else case by setting keep_edge the obvious way in the other two if cases. Sorry for not being clear ... OK with that change. > @@ -1733,15 +1764,52 @@ value_replacement (basic_block cond_bb, basic_block middle_bb, > return 0; > } > > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues. > > Ok with change? > > Thanks, > Tamar > > > > > > Bootstrapped Regtested on aarch64-none-linux-gnu and no issues. > > > > > > Ok with this Change? > > > > > > Thanks, > > > Tamar > -- Richard Biener SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman; HRB 36809 (AG Nuernberg)