From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx2.suse.de (mx2.suse.de [195.135.220.15]) by sourceware.org (Postfix) with ESMTPS id D9DE13857C6C for ; Thu, 6 Aug 2020 13:25:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org D9DE13857C6C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=rguenther@suse.de X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 30D8EABE4; Thu, 6 Aug 2020 13:25:18 +0000 (UTC) Date: Thu, 6 Aug 2020 15:25:00 +0200 (CEST) From: Richard Biener To: Jakub Jelinek cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] reassoc: Improve maybe_optimize_range_tests [PR96480] In-Reply-To: <20200806125043.GV2363@tucnak> Message-ID: References: <20200806125043.GV2363@tucnak> User-Agent: Alpine 2.21 (LSU 202 2017-01-01) MIME-Version: 1.0 X-Spam-Status: No, score=-5.1 required=5.0 tests=BAYES_00, KAM_DMARC_STATUS, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, 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 Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 8BIT X-Content-Filtered-By: Mailman/MimeDel 2.1.29 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: Thu, 06 Aug 2020 13:25:03 -0000 On Thu, 6 Aug 2020, Jakub Jelinek wrote: > Hi! > > On the following testcase, if the IL before reassoc would be: > ... > [local count: 354334800]: > if (x_3(D) == 2) > goto ; [34.00%] > else > goto ; [66.00%] > > [local count: 233860967]: > if (x_3(D) == 3) > goto ; [34.00%] > else > goto ; [66.00%] > > [local count: 79512730]: > > [local count: 1073741824]: > # prephitmp_7 = PHI <1(3), 1(4), 1(5), 1(2), 0(6)> > then we'd optimize it properly, but as bb 5-7 is instead: > [local count: 233860967]: > if (x_3(D) == 3) > goto ; [34.00%] > else > goto ; [66.00%] > > [local count: 79512730]: > > [local count: 1073741824]: > # prephitmp_7 = PHI <1(3), 1(4), 0(5), 1(2), 1(6)> > (i.e. the true/false edges on the last bb with condition swapped > and ditto for the phi args), we don't recognize it. If bb 6 > is empty, there should be no functional difference between the two IL > representations. > > This patch handles those special cases. > > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? OK. Thanks, Richard. > 2020-08-06 Jakub Jelinek > > PR tree-optimization/96480 > * tree-ssa-reassoc.c (suitable_cond_bb): Add TEST_SWAPPED_P argument. > If TEST_BB ends in cond and has one edge to *OTHER_BB and another > through an empty bb to that block too, if PHI args don't match, retry > them through the other path from TEST_BB. > (maybe_optimize_range_tests): Adjust callers. Handle such LAST_BB > through inversion of the condition. > > * gcc.dg/tree-ssa/pr96480.c: New test. > > --- gcc/tree-ssa-reassoc.c.jj 2020-07-30 15:04:38.000000000 +0200 > +++ gcc/tree-ssa-reassoc.c 2020-08-06 11:19:30.942825436 +0200 > @@ -4127,11 +4127,14 @@ final_range_test_p (gimple *stmt) > of TEST_BB, and *OTHER_BB is either NULL and filled by the routine, > or compared with to find a common basic block to which all conditions > branch to if true resp. false. If BACKWARD is false, TEST_BB should > - be the only predecessor of BB. */ > + be the only predecessor of BB. *TEST_SWAPPED_P is set to true if > + TEST_BB is a bb ending in condition where the edge to non-*OTHER_BB > + block points to an empty block that falls through into *OTHER_BB and > + the phi args match that path. */ > > static bool > suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb, > - bool backward) > + bool *test_swapped_p, bool backward) > { > edge_iterator ei, ei2; > edge e, e2; > @@ -4196,6 +4199,7 @@ suitable_cond_bb (basic_block bb, basic_ > /* Now check all PHIs of *OTHER_BB. */ > e = find_edge (bb, *other_bb); > e2 = find_edge (test_bb, *other_bb); > + retry:; > for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) > { > gphi *phi = gsi.phi (); > @@ -4221,11 +4225,52 @@ suitable_cond_bb (basic_block bb, basic_ > else > { > gimple *test_last = last_stmt (test_bb); > - if (gimple_code (test_last) != GIMPLE_COND > - && gimple_phi_arg_def (phi, e2->dest_idx) > - == gimple_assign_lhs (test_last) > - && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx)) > - || integer_onep (gimple_phi_arg_def (phi, e->dest_idx)))) > + if (gimple_code (test_last) == GIMPLE_COND) > + { > + if (backward ? e2->src != test_bb : e->src != bb) > + return false; > + > + /* For last_bb, handle also: > + if (x_3(D) == 3) > + goto ; [34.00%] > + else > + goto ; [66.00%] > + > + [local count: 79512730]: > + > + [local count: 1073741824]: > + # prephitmp_7 = PHI <1(3), 1(4), 0(5), 1(2), 1(6)> > + where bb 7 is *OTHER_BB, but the PHI values from the > + earlier bbs match the path through the empty bb > + in between. */ > + edge e3; > + if (backward) > + e3 = EDGE_SUCC (test_bb, > + e2 == EDGE_SUCC (test_bb, 0) ? 1 : 0); > + else > + e3 = EDGE_SUCC (bb, > + e == EDGE_SUCC (bb, 0) ? 1 : 0); > + if (empty_block_p (e3->dest) > + && single_succ_p (e3->dest) > + && single_succ (e3->dest) == *other_bb > + && single_pred_p (e3->dest) > + && single_succ_edge (e3->dest)->flags == EDGE_FALLTHRU) > + { > + if (backward) > + e2 = single_succ_edge (e3->dest); > + else > + e = single_succ_edge (e3->dest); > + if (test_swapped_p) > + *test_swapped_p = true; > + goto retry; > + } > + } > + else if (gimple_phi_arg_def (phi, e2->dest_idx) > + == gimple_assign_lhs (test_last) > + && (integer_zerop (gimple_phi_arg_def (phi, > + e->dest_idx)) > + || integer_onep (gimple_phi_arg_def (phi, > + e->dest_idx)))) > continue; > } > > @@ -4414,7 +4459,7 @@ maybe_optimize_range_tests (gimple *stmt > while (single_pred_p (first_bb)) > { > basic_block pred_bb = single_pred (first_bb); > - if (!suitable_cond_bb (pred_bb, first_bb, &other_bb, true)) > + if (!suitable_cond_bb (pred_bb, first_bb, &other_bb, NULL, true)) > break; > if (!no_side_effect_bb (first_bb)) > break; > @@ -4444,7 +4489,8 @@ maybe_optimize_range_tests (gimple *stmt > && gimple_code (stmt) == GIMPLE_COND > && EDGE_COUNT (e->dest->succs) == 2) > { > - if (suitable_cond_bb (first_bb, e->dest, &other_bb, true)) > + if (suitable_cond_bb (first_bb, e->dest, &other_bb, > + NULL, true)) > break; > else > other_bb = NULL; > @@ -4472,7 +4518,7 @@ maybe_optimize_range_tests (gimple *stmt > break; > if (!single_pred_p (e->dest)) > break; > - if (!suitable_cond_bb (e->dest, last_bb, &other_bb, false)) > + if (!suitable_cond_bb (e->dest, last_bb, &other_bb, NULL, false)) > break; > if (!no_side_effect_bb (e->dest)) > break; > @@ -4583,6 +4629,28 @@ maybe_optimize_range_tests (gimple *stmt > bbinfo.safe_push (bb_ent); > continue; > } > + else if (bb == last_bb) > + { > + /* For last_bb, handle also: > + if (x_3(D) == 3) > + goto ; [34.00%] > + else > + goto ; [66.00%] > + > + [local count: 79512730]: > + > + [local count: 1073741824]: > + # prephitmp_7 = PHI <1(3), 1(4), 0(5), 1(2), 1(6)> > + where bb 7 is OTHER_BB, but the PHI values from the > + earlier bbs match the path through the empty bb > + in between. */ > + bool test_swapped_p = false; > + bool ok = suitable_cond_bb (single_pred (last_bb), last_bb, > + &other_bb, &test_swapped_p, true); > + gcc_assert (ok); > + if (test_swapped_p) > + e = EDGE_SUCC (bb, e == EDGE_SUCC (bb, 0) ? 1 : 0); > + } > /* Otherwise stmt is GIMPLE_COND. */ > code = gimple_cond_code (stmt); > lhs = gimple_cond_lhs (stmt); > --- gcc/testsuite/gcc.dg/tree-ssa/pr96480.c.jj 2020-08-05 16:08:30.625614787 +0200 > +++ gcc/testsuite/gcc.dg/tree-ssa/pr96480.c 2020-08-05 16:02:32.498832099 +0200 > @@ -0,0 +1,23 @@ > +/* PR tree-optimization/96480 */ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* { dg-final { scan-tree-dump " = _\[0-9]* <= 3;" "optimized" } } */ > + > +int v[4]; > + > +int > +foo (int x) > +{ > + int *p; > + if (x == 0) > + p = &v[0]; > + else if (x == 1) > + p = &v[1]; > + else if (x == 2) > + p = &v[2]; > + else if (x == 3) > + p = &v[3]; > + else > + p = &v[4]; > + return p != &v[4]; > +} > > Jakub > > -- Richard Biener SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)