From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1851) id 94B54386F437; Mon, 29 Nov 2021 11:13:54 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 94B54386F437 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Martin Liska To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/marxin/heads/loop-unswitch-improvement-v3)] Support budgeting in loop unswitching. X-Act-Checkin: gcc X-Git-Author: Martin Liska X-Git-Refname: refs/users/marxin/heads/loop-unswitch-improvement-v3 X-Git-Oldrev: 277832038c353f154ba7bc670f6e6d0751102b51 X-Git-Newrev: 121b02fbc47138cb52bc2dc25688bcc56df8d92a Message-Id: <20211129111354.94B54386F437@sourceware.org> Date: Mon, 29 Nov 2021 11:13:54 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 29 Nov 2021 11:13:54 -0000 https://gcc.gnu.org/g:121b02fbc47138cb52bc2dc25688bcc56df8d92a commit 121b02fbc47138cb52bc2dc25688bcc56df8d92a Author: Martin Liska Date: Mon Nov 29 12:12:00 2021 +0100 Support budgeting in loop unswitching. Diff: --- gcc/tree-ssa-loop-unswitch.c | 33 ++++++++++++++++++++++----------- 1 file changed, 22 insertions(+), 11 deletions(-) diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index aa9f25e1907..12fa6b86088 100644 --- a/gcc/tree-ssa-loop-unswitch.c +++ b/gcc/tree-ssa-loop-unswitch.c @@ -106,7 +106,8 @@ typedef auto_vec> predicate_vector; static class loop *tree_unswitch_loop (class loop *, basic_block, tree); static bool tree_unswitch_single_loop (class loop *, int, - predicate_vector &predicate_path); + predicate_vector &predicate_path, + unsigned budget); static void find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, vec &candidates); @@ -136,11 +137,14 @@ set_predicates_for_bb (basic_block bb, vec predicates) bb_predicates->safe_push (predicates); } -/* Initialize LOOP information reused during the unswitching pass. */ +/* Initialize LOOP information reused during the unswitching pass. + Return total number of instructions in the loop. */ -static void +static unsigned init_loop_unswitch_info (class loop *loop) { + unsigned total_insns = 0; + /* Calculate instruction count. */ basic_block *bbs = get_loop_body (loop); for (unsigned i = 0; i < loop->num_nodes; i++) @@ -151,6 +155,7 @@ init_loop_unswitch_info (class loop *loop) insns += estimate_num_insns (gsi_stmt (gsi), &eni_size_weights); bbs[i]->aux = (void *)(size_t)insns; + total_insns += insns; } /* Find all unswitching candidates. */ @@ -171,6 +176,8 @@ init_loop_unswitch_info (class loop *loop) } free (bbs); + + return total_insns; } /* Main entry point. Perform loop unswitching on all suitable loops. */ @@ -191,9 +198,12 @@ tree_ssa_unswitch_loops (void) bb_predicates->safe_push (vec ()); /* Unswitch innermost loop. */ - init_loop_unswitch_info (loop); + unsigned int budget + = init_loop_unswitch_info (loop) + param_max_unswitch_insns; + predicate_vector predicate_path; - changed |= tree_unswitch_single_loop (loop, 0, predicate_path); + changed |= tree_unswitch_single_loop (loop, 0, predicate_path, + budget); delete bb_predicates; bb_predicates = NULL; @@ -548,11 +558,12 @@ evaluate_loop_insns_for_predicate (class loop *loop, basic_block *bbs, /* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow it to grow too much, it is too easy to create example on that the code would grow exponentially. PREDICATE_PATH contains so far used predicates - for unswitching. */ + for unswitching. BUDGET is number of instruction for which we can increase + the loop. */ static bool tree_unswitch_single_loop (class loop *loop, int num, - predicate_vector &predicate_path) + predicate_vector &predicate_path, unsigned budget) { basic_block *bbs = NULL; class loop *nloop; @@ -601,17 +612,17 @@ tree_unswitch_single_loop (class loop *loop, int num, vec &preds = get_predicates_for_bb (bbs[i]); for (auto pred: preds) { - // FIXME: update badget costing unsigned cost = evaluate_loop_insns_for_predicate (loop, bbs, predicate_path, pred); /* FIXME: right now we select first candidate, but we can choose a cheapest (best) one. */ - if (cost <= (unsigned)param_max_unswitch_insns) + if (cost <= budget) { predicate = pred; bb = bbs[i]; + budget -= cost; break; } else if (dump_file && (dump_flags & TDF_DETAILS)) @@ -659,12 +670,12 @@ tree_unswitch_single_loop (class loop *loop, int num, /* Invoke itself on modified loops. */ predicate_path.safe_push (std::make_pair (predicate, false)); changed |= simplify_loop_version (nloop, predicate_path); - tree_unswitch_single_loop (nloop, num + 1, predicate_path); + tree_unswitch_single_loop (nloop, num + 1, predicate_path, budget); predicate_path.pop (); predicate_path.safe_push (std::make_pair (predicate, true)); changed |= simplify_loop_version (loop, predicate_path); - tree_unswitch_single_loop (loop, num + 1, predicate_path); + tree_unswitch_single_loop (loop, num + 1, predicate_path, budget); predicate_path.pop (); changed = true; }