From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-1.mimecast.com (us-smtp-delivery-1.mimecast.com [205.139.110.120]) by sourceware.org (Postfix) with ESMTP id ADC563858D37 for ; Thu, 6 Aug 2020 12:50:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org ADC563858D37 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-394-AcCDVCMeMtatJ6j_QkBtYg-1; Thu, 06 Aug 2020 08:50:48 -0400 X-MC-Unique: AcCDVCMeMtatJ6j_QkBtYg-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id C345279EC4; Thu, 6 Aug 2020 12:50:47 +0000 (UTC) Received: from tucnak.zalov.cz (ovpn-113-174.ams2.redhat.com [10.36.113.174]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 565B069315; Thu, 6 Aug 2020 12:50:47 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.15.2/8.15.2) with ESMTP id 076Coiu4011988; Thu, 6 Aug 2020 14:50:44 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.15.2/8.15.2/Submit) id 076CohgK011987; Thu, 6 Aug 2020 14:50:43 +0200 Date: Thu, 6 Aug 2020 14:50:43 +0200 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] reassoc: Improve maybe_optimize_range_tests [PR96480] Message-ID: <20200806125043.GV2363@tucnak> Reply-To: Jakub Jelinek MIME-Version: 1.0 User-Agent: Mutt/1.11.3 (2019-02-01) X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Status: No, score=-7.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, 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 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 12:50:52 -0000 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? 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