From patchwork Fri Jul 28 07:58:04 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1814116 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=bOx9dra1; dkim-atps=neutral Received: from server2.sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4RC0Pk0tmwz1ybX for ; Fri, 28 Jul 2023 17:58:28 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id F0F1038560AA for ; Fri, 28 Jul 2023 07:58:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org F0F1038560AA DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1690531106; bh=DOPG8rjfr8DsC0nKWo+N/tYWUh8IGd1T2b0oMkYNglo=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=bOx9dra14FDE4JZIIxCpK9JN5nFeiKOyfS/h8AmtIhsLLA3SedHBKkpZn8rsuMSG7 yI7hWQIlSr/yoezo89IdDEMuNcl6kaVOkKVRQ4OJWIy9qPSx6ZapJEhRBGMCWj2LO2 NInFajwZUU8p9vSzNsesxo37PUhETXazEZcHih70= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from nikam.ms.mff.cuni.cz (nikam.ms.mff.cuni.cz [195.113.20.16]) by sourceware.org (Postfix) with ESMTPS id 3D3B63858D33 for ; Fri, 28 Jul 2023 07:58:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3D3B63858D33 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id 14BD12828DC; Fri, 28 Jul 2023 09:58:04 +0200 (CEST) Date: Fri, 28 Jul 2023 09:58:04 +0200 To: gcc-patches@gcc.gnu.org, rguenther@suse.cz Subject: Loop-split improvements, part 2 Message-ID: MIME-Version: 1.0 Content-Disposition: inline X-Spam-Status: No, score=-10.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, GIT_PATCH_0, HEADER_FROM_DIFFERENT_DOMAINS, JMQ_SPF_NEUTRAL, KAM_NUMSUBJECT, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE 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-Patchwork-Original-From: Jan Hubicka via Gcc-patches From: Jan Hubicka Reply-To: Jan Hubicka Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi, this patch fixes profile update in the first case of loop splitting. The pass still gives up on very basic testcases: __attribute__ ((noinline,noipa)) void test1 (int n) { if (n <= 0 || n > 100000) return; for (int i = 0; i <= n; i++) { if (i < n) do_something (); if (a[i]) do_something2(); } } Here I needed to do the conditoinal that enforces sane value range of n. The reason is that it gives up on: !number_of_iterations_exit (loop1, exit1, &niter, false, true) and without the conditonal we get assumption that n>=0 and not INT_MAX. I think from overflow we shold derive that INT_MAX test is not needed and since the loop does nothing for n<0 it is also just an paranoia. I am not sure how to fix this though :(. In general the pass does not really need to compute iteration count. It only needs to know what direction the IVs go so it can detect tests that fires in first part of iteration space. Rich, any idea what the correct test should be? In testcase: for (int i = 0; i < 200; i++) if (i < 150) do_something (); else do_something2 (); the old code did wrong update of the exit condition probabilities. We know that first loop iterates 150 times and the second loop 50 times and we get it by simply scaling loop body by the probability of inner test. With the patch we now get: [count: 1000]: [count: 150000]: <- loop 1 correctly iterates 149 times # i_10 = PHI do_something (); i_7 = i_10 + 1; if (i_7 <= 149) goto ; [99.33%] else goto ; [0.67%] [count: 149000]: goto ; [100.00%] [count: 1000]: # i_15 = PHI [count: 49975]: <- loop 2 should iterate 50 times but we are slightly wrong # i_3 = PHI do_something2 (); i_14 = i_3 + 1; if (i_14 != 200) goto ; [98.00%] else goto ; [2.00%] [count: 48975]: goto ; [100.00%] [count: 1000]: <- this test is always true becuase it is reached form bb 3 # i_18 = PHI if (i_18 != 200) goto ; [99.95%] else goto ; [0.05%] [count: 1000]: return; The reason why we are slightly wrong is the condtion in bb17 that is always true but the pass does not konw it. Rich any idea how to do that? I think connect_loops should work out the cas where the loop exit conditon is never satisfied at the time the splitted condition fails for first time. Also we do not update loop iteration expectancies. If we were able to work out if one of the loop has constant iteration count, we could do it perfectly. Before patch on hmmer we get a lot of mismatches: Profile report here claims: dump id |static mismat|dynamic mismatch | |in count |in count |time | lsplit | 5 +5| 8151850567 +8151850567| 531506481006 +57.9%| ldist | 9 +4| 15345493501 +7193642934| 606848841056 +14.2%| ifcvt | 10 +1| 15487514871 +142021370| 689469797790 +13.6%| vect | 35 +25| 17558425961 +2070911090| 517375405715 -25.0%| cunroll | 42 +7| 16898736178 -659689783| 452445796198 -4.9%| loopdone| 33 -9| 2678017188 -14220718990| 330969127663 | tracer | 34 +1| 2678018710 +1522| 330613415364 +0.0%| fre | 33 -1| 2676980249 -1038461| 330465677073 -0.0%| expand | 28 -5| 2497468467 -179511782|--------------------------| With patch lsplit | 0 | 0 | 328723360744 -2.3%| ldist | 0 | 0 | 396193562452 +20.6%| ifcvt | 1 +1| 71010686 +71010686| 478743508522 +20.8%| vect | 14 +13| 697518955 +626508269| 299398068323 -37.5%| cunroll | 13 -1| 489349408 -208169547| 257777839725 -10.5%| loopdone| 11 -2| 402558559 -86790849| 201010712702 | tracer | 13 +2| 402977200 +418641| 200651036623 +0.0%| fre | 13 | 402622146 -355054| 200344398654 -0.2%| expand | 11 -2| 333608636 -69013510|--------------------------| So no mismatches for lsplit and ldist and also lsplit thinks it improves speed by 2.3% rather than regressig it by 57%. Update is still not perfect since we do not work out that the second loop never iterates. Also ldist is still wrong siince time should not go up. Ifcft wrecks profile by desing since it insert conditonals with both arms 100% that will be eliminated later after vect. It is not clear to me what happens in vect though. Bootstrapped/regtested x86_64-linux, comitted. gcc/ChangeLog: PR middle-end/106293 * tree-ssa-loop-split.cc (connect_loops): Change probability of the test preconditioning second loop to very_likely. (fix_loop_bb_probability): Handle correctly case where on of the arms of the conditional is empty. (split_loop): Fold the test guarding first condition to see if it is constant true; Set correct entry block probabilities of the split loops; determine correct loop eixt probabilities. gcc/testsuite/ChangeLog: PR middle-end/106293 * gcc.dg/tree-prof/loop-split-1.c: New test. * gcc.dg/tree-prof/loop-split-2.c: New test. * gcc.dg/tree-prof/loop-split-3.c: New test. diff --git a/gcc/testsuite/gcc.dg/tree-prof/loop-split-1.c b/gcc/testsuite/gcc.dg/tree-prof/loop-split-1.c new file mode 100644 index 00000000000..46f7ae66fa3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-prof/loop-split-1.c @@ -0,0 +1,33 @@ +/* { dg-options "-O3 -fdump-tree-lsplit-details-blocks -fdump-tree-optimized-details-blocks" } */ + + +void +__attribute__ ((noinline,noipa)) +do_something() +{ +} +void +__attribute__ ((noinline,noipa)) +do_something2() +{ +} + +__attribute__ ((noinline,noipa)) +void test1 (int n, int ga) +{ + for (int i = 0; i < 200; i++) + if (i < 150) + do_something (); + else + do_something2 (); +} +int +main(int, char **) +{ + for (int i = 0 ; i < 1000; i++) + test1(10, 10); + return 0; +} +/* { dg-final-use-not-autofdo { scan-tree-dump-times "Loop split" 1 "lsplit" } } */ +/* { dg-final-use-not-autofdo { scan-tree-dump-times "Invalid sum" 0 "lsplit" } } */ +/* { dg-final-use-not-autofdo { scan-tree-dump-times "Invalid sum" 0 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-prof/loop-split-2.c b/gcc/testsuite/gcc.dg/tree-prof/loop-split-2.c new file mode 100644 index 00000000000..de2c9f58301 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-prof/loop-split-2.c @@ -0,0 +1,36 @@ +/* { dg-options "-O3 -fdump-tree-lsplit-details-blocks -fdump-tree-optimized-details-blocks" } */ + +int M = 100; + +void +__attribute__ ((noinline,noipa)) +do_something() +{ +} +void +__attribute__ ((noinline,noipa)) +do_something2() +{ +} + +__attribute__ ((noinline,noipa)) +void test1 (int n) +{ + if (n <= 0 || n > 100000) + return; + for (int i = 0; i <= n; i++) + if (i < n) + do_something (); + else + do_something2 (); +} +int +main(int, char **) +{ + for (int i = 0 ; i < 1000; i++) + test1(M); + return 0; +} +/* { dg-final-use-not-autofdo { scan-tree-dump-times "Loop split" 1 "lsplit" } } */ +/* { dg-final-use-not-autofdo { scan-tree-dump-times "Invalid sum" 0 "lsplit" } } */ +/* { dg-final-use-not-autofdo { scan-tree-dump-times "Invalid sum" 0 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-prof/loop-split-3.c b/gcc/testsuite/gcc.dg/tree-prof/loop-split-3.c new file mode 100644 index 00000000000..a88bc1f8663 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-prof/loop-split-3.c @@ -0,0 +1,41 @@ +/* { dg-options "-O3 -fdump-tree-lsplit-details-blocks -fdump-tree-optimized-details-blocks" } */ + +int M = 100; +int a[1000]; + +void +__attribute__ ((noinline,noipa)) +do_something() +{ +} +void +__attribute__ ((noinline,noipa)) +do_something2() +{ +} + +__attribute__ ((noinline,noipa)) +void test1 (int n) +{ + if (n <= 0 || n > 100000) + return; + for (int i = 0; i <= n; i++) + { + if (i < n) + do_something (); + if (a[i]) + do_something2(); + } +} +int +main(int, char **) +{ + for (int i = 0 ; i < 1000; i+=3) + a[i]=1; + for (int i = 0 ; i < 1000; i++) + test1(M); + return 0; +} +/* { dg-final-use-not-autofdo { scan-tree-dump-times "Loop split" 1 "lsplit" } } */ +/* { dg-final-use-not-autofdo { scan-tree-dump-times "Invalid sum" 0 "lsplit" } } */ +/* { dg-final-use-not-autofdo { scan-tree-dump-times "Invalid sum" 0 "optimized" } } */ diff --git a/gcc/tree-ssa-loop-split.cc b/gcc/tree-ssa-loop-split.cc index f441f3fe1b5..70cd0aaefa7 100644 --- a/gcc/tree-ssa-loop-split.cc +++ b/gcc/tree-ssa-loop-split.cc @@ -355,7 +356,7 @@ connect_loops (class loop *loop1, class loop *loop2) new_e->flags |= EDGE_TRUE_VALUE; } - new_e->probability = profile_probability::likely (); + new_e->probability = profile_probability::very_likely (); skip_e->probability = new_e->probability.invert (); return new_e; @@ -496,6 +497,8 @@ fix_loop_bb_probability (class loop *loop1, class loop *loop2, edge true_edge, unsigned j; for (j = 0; j < loop1->num_nodes; j++) if (bbs1[j] == loop1->latch + /* Watch for case where the true conditional is empty. */ + || !single_pred_p (true_edge->dest) || !dominated_by_p (CDI_DOMINATORS, bbs1[j], true_edge->dest)) bbs1[j]->count = bbs1[j]->count.apply_probability (true_edge->probability); @@ -507,6 +510,8 @@ fix_loop_bb_probability (class loop *loop1, class loop *loop2, edge true_edge, bbs2 = get_loop_body (loop2); for (j = 0; j < loop2->num_nodes; j++) if (bbs2[j] == loop2->latch + /* Watch for case where the flase conditional is empty. */ + || !single_pred_p (bbi_copy) || !dominated_by_p (CDI_DOMINATORS, bbs2[j], bbi_copy)) bbs2[j]->count = bbs2[j]->count.apply_probability (true_edge->probability.invert ()); @@ -564,6 +569,7 @@ split_loop (class loop *loop1) for (i = 0; i < loop1->num_nodes; i++) if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv))) { + profile_count entry_count = loop_preheader_edge (loop1)->count (); /* Handling opposite steps is not implemented yet. Neither is handling different step sizes. */ if ((tree_int_cst_sign_bit (iv.step) @@ -610,7 +616,8 @@ split_loop (class loop *loop1) if (stmts2) gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1), stmts2); - tree cond = build2 (guard_code, boolean_type_node, guard_init, border); + tree cond = fold_build2 (guard_code, boolean_type_node, + guard_init, border); if (!initial_true) cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond); @@ -622,13 +629,71 @@ split_loop (class loop *loop1) initialize_original_copy_tables (); basic_block cond_bb; + profile_probability loop1_prob + = integer_onep (cond) ? profile_probability::always () + : true_edge->probability; + /* TODO: It is commonly a case that we know that both loops will be + entered. very_likely below is the probability that second loop will + be entered given by connect_loops. We should work out the common + case it is always true. */ class loop *loop2 = loop_version (loop1, cond, &cond_bb, - true_edge->probability, - true_edge->probability.invert (), + loop1_prob, + /* Pass always as we will later + redirect first loop to second + loop. */ profile_probability::always (), profile_probability::always (), + profile_probability::very_likely (), true); gcc_assert (loop2); + /* Correct probability of edge cond_bb->preheader_of_loop2. */ + single_pred_edge + (loop_preheader_edge (loop2)->src)->probability + = loop1_prob.invert (); + + fix_loop_bb_probability (loop1, loop2, true_edge, false_edge); + + /* Fix loop's exit probability after scaling. */ + + if (entry_count.initialized_p () && entry_count.nonzero_p ()) + { + edge exit_to_latch1; + if (EDGE_SUCC (exit1->src, 0) == exit1) + exit_to_latch1 = EDGE_SUCC (exit1->src, 1); + else + exit_to_latch1 = EDGE_SUCC (exit1->src, 0); + if (exit1->src->count.nonzero_p ()) + { + /* First loop is entered loop1_prob * entry_count times + and it needs to exit the same number of times. */ + exit1->probability + = entry_count.apply_probability + (loop1_prob).probability_in (exit1->src->count); + exit_to_latch1->probability = exit1->probability.invert (); + scale_dominated_blocks_in_loop (loop1, exit1->src, + exit_to_latch1->count (), + exit_to_latch1->dest->count); + } + + edge exit_to_latch2, exit2 = single_exit (loop2); + if (EDGE_SUCC (exit2->src, 0) == exit2) + exit_to_latch2 = EDGE_SUCC (exit2->src, 1); + else + exit_to_latch2 = EDGE_SUCC (exit2->src, 0); + if (exit2->src->count.nonzero_p ()) + { + /* Second loop is entered very_likely * entry_count times + and it needs to exit the same number of times. */ + exit2->probability + = entry_count.apply_probability + (profile_probability::very_likely ()) + .probability_in (exit2->src->count); + exit_to_latch2->probability = exit2->probability.invert (); + scale_dominated_blocks_in_loop (loop2, exit2->src, + exit_to_latch2->count (), + exit_to_latch2->dest->count); + } + } edge new_e = connect_loops (loop1, loop2); connect_loop_phis (loop1, loop2, new_e); @@ -647,16 +712,7 @@ split_loop (class loop *loop1) tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1)); patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true); - fix_loop_bb_probability (loop1, loop2, true_edge, false_edge); - - /* Fix first loop's exit probability after scaling. */ - edge exit_to_latch1; - if (EDGE_SUCC (exit1->src, 0) == exit1) - exit_to_latch1 = EDGE_SUCC (exit1->src, 1); - else - exit_to_latch1 = EDGE_SUCC (exit1->src, 0); - exit_to_latch1->probability *= true_edge->probability; - exit1->probability = exit_to_latch1->probability.invert (); + /* TODO: Update any_esitmate and upper bounds. */ /* Finally patch out the two copies of the condition to be always true/false (or opposite). */