From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id 738133858413 for ; Mon, 7 Nov 2022 08:59:16 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 738133858413 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 709A11F898; Mon, 7 Nov 2022 08:59:15 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1667811555; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=c90IHkzZjoRDs7j3ilXHJ7HIwa+0w+410VLZw1/k+zY=; b=qKqQvPMIbR/So5LF52Bsj0CtPpth2hMavJbA09qCRrRXHOwoqVxBUP2WMbZ0vGtTbzWFlB JBCdvan9WcMVpp2tyOkLWah5oY9A7djbf3kJcAkZn2v2wtEfQAOiiYvNQm0lRr05+UYUiu CrYRQln7nyXkwAScBzSsTsui0hZ1yBg= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1667811555; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=c90IHkzZjoRDs7j3ilXHJ7HIwa+0w+410VLZw1/k+zY=; b=7CU966kmGrJPJz1FZHDzWgPW8RHTwz7qcLRh+agK82Poh64k39czBTeSkiv2T3LqLZswgN 1r75KGk62qk4D9Dg== 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 64E682C141; Mon, 7 Nov 2022 08:59:15 +0000 (UTC) Date: Mon, 7 Nov 2022 08:59:15 +0000 (UTC) From: Richard Biener To: gcc-patches@gcc.gnu.org cc: Jan Hubicka Subject: Re: [PATCH] unswitch most profitable condition first Message-ID: 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=-11.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,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 List-Id: On Tue, 25 Oct 2022, Richard Biener wrote: > When doing the loop unswitching re-org we promised to followup > with improvements on the cost modeling. The following makes sure we > try to unswitch on the most profitable condition first. As most profitable > we pick the condition leading to the edge with the highest profile count. > > Note the profile is only applied when picking the first unswitching > opportunity since the profile counts are not updated with earlier > unswitchings in mind. Further opportunities are picked in DFS order. > > Bootstrapped and tested on x86_64-unknown-linux-gnu. > > Any comments? I have now pushed this. Richard. > Thanks, > Richard. > > * tree-ssa-loop-unswitch.cc (unswitch_predicate::count): New. > (unswitch_predicate::unswitch_predicate): Initialize count. > (init_loop_unswitch_info): First collect candidates and > determine the outermost loop to unswitch. > (tree_ssa_unswitch_loops): First perform all guard hoisting, > then perform unswitching on innermost loop predicates. > (find_unswitching_predicates_for_bb): Keep track of the > most profitable predicate to unswitch on. > (tree_unswitch_single_loop): Unswitch given predicate if > not NULL. > --- > gcc/tree-ssa-loop-unswitch.cc | 66 ++++++++++++++++++++++++++++------- > 1 file changed, 54 insertions(+), 12 deletions(-) > > diff --git a/gcc/tree-ssa-loop-unswitch.cc b/gcc/tree-ssa-loop-unswitch.cc > index 7d6781d1505..dfe75f52f12 100644 > --- a/gcc/tree-ssa-loop-unswitch.cc > +++ b/gcc/tree-ssa-loop-unswitch.cc > @@ -118,6 +118,7 @@ struct unswitch_predicate > if (!false_range.varying_p () > && !false_range.undefined_p ()) > false_range.invert (); > + count = e->count (); > num = predicates->length (); > predicates->safe_push (this); > } > @@ -126,7 +127,8 @@ struct unswitch_predicate > unswitch_predicate (gcond *stmt) > : switch_p (false) > { > - if (EDGE_SUCC (gimple_bb (stmt), 0)->flags & EDGE_TRUE_VALUE) > + basic_block bb = gimple_bb (stmt); > + if (EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE) > edge_index = 0; > else > edge_index = 1; > @@ -134,6 +136,7 @@ struct unswitch_predicate > tree rhs = gimple_cond_rhs (stmt); > enum tree_code code = gimple_cond_code (stmt); > condition = build2 (code, boolean_type_node, lhs, rhs); > + count = EDGE_SUCC (bb, 0)->count ().max (EDGE_SUCC (bb, 1)->count ()); > if (irange::supports_p (TREE_TYPE (lhs))) > { > auto range_op = range_op_handler (code, TREE_TYPE (lhs)); > @@ -180,6 +183,9 @@ struct unswitch_predicate > /* Index of the edge the predicate belongs to in the successor vector. */ > int edge_index; > > + /* The profile count of this predicate. */ > + profile_count count; > + > /* Whether the predicate was created from a switch statement. */ > bool switch_p; > > @@ -206,10 +212,14 @@ static class loop *tree_unswitch_loop (class loop *, edge, tree); > static bool tree_unswitch_single_loop (class loop *, dump_user_location_t, > predicate_vector &predicate_path, > unsigned loop_size, unsigned &budget, > - int ignored_edge_flag, bitmap); > + int ignored_edge_flag, bitmap, > + unswitch_predicate * = NULL, > + basic_block = NULL); > static void > find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, > - vec &candidates); > + vec &candidates, > + unswitch_predicate *&hottest, > + basic_block &hottest_bb); > static bool tree_unswitch_outer_loop (class loop *); > static edge find_loop_guard (class loop *, vec&); > static bool empty_bb_without_guard_p (class loop *, basic_block, > @@ -242,7 +252,8 @@ set_predicates_for_bb (basic_block bb, vec predicates) > Return total number of instructions in the loop. */ > > static unsigned > -init_loop_unswitch_info (class loop *loop) > +init_loop_unswitch_info (class loop *loop, unswitch_predicate *&hottest, > + basic_block &hottest_bb) > { > unsigned total_insns = 0; > > @@ -259,13 +270,16 @@ init_loop_unswitch_info (class loop *loop) > total_insns += insns; > } > > + hottest = NULL; > + hottest_bb = NULL; > /* Find all unswitching candidates. */ > for (unsigned i = 0; i != loop->num_nodes; i++) > { > /* Find a bb to unswitch on. */ > vec candidates; > candidates.create (1); > - find_unswitching_predicates_for_bb (bbs[i], loop, candidates); > + find_unswitching_predicates_for_bb (bbs[i], loop, candidates, > + hottest, hottest_bb); > if (!candidates.is_empty ()) > set_predicates_for_bb (bbs[i], candidates); > else > @@ -329,7 +343,10 @@ tree_ssa_unswitch_loops (function *fun) > unswitch_predicate::predicates = new vec (); > > /* Unswitch innermost loop. */ > - unsigned int loop_size = init_loop_unswitch_info (loop); > + unswitch_predicate *hottest; > + basic_block hottest_bb; > + unsigned int loop_size = init_loop_unswitch_info (loop, hottest, > + hottest_bb); > unsigned int budget = loop_size + param_max_unswitch_insns; > > predicate_vector predicate_path; > @@ -338,7 +355,8 @@ tree_ssa_unswitch_loops (function *fun) > changed_unswitch > |= tree_unswitch_single_loop (loop, loc, predicate_path, > loop_size, budget, > - ignored_edge_flag, handled); > + ignored_edge_flag, handled, > + hottest, hottest_bb); > predicate_path.release (); > > for (auto predlist : bb_predicates) > @@ -449,7 +467,9 @@ is_maybe_undefined (const tree name, gimple *stmt, class loop *loop) > > static void > find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, > - vec &candidates) > + vec &candidates, > + unswitch_predicate *&hottest, > + basic_block &hottest_bb) > { > gimple *last, *def; > tree use; > @@ -489,6 +509,14 @@ find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, > > unswitch_predicate *predicate = new unswitch_predicate (stmt); > candidates.safe_push (predicate); > + /* If we unswitch on this predicate we isolate both paths, so > + pick the highest count for updating of the hottest predicate > + to unswitch on first. */ > + if (!hottest || predicate->count > hottest->count) > + { > + hottest = predicate; > + hottest_bb = bb; > + } > } > else if (gswitch *stmt = safe_dyn_cast (last)) > { > @@ -561,6 +589,11 @@ find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, > edge_index, e, > edge_range[edge_index]); > candidates.safe_push (predicate); > + if (!hottest || predicate->count > hottest->count) > + { > + hottest = predicate; > + hottest_bb = bb; > + } > } > } > } > @@ -888,13 +921,15 @@ evaluate_loop_insns_for_predicate (class loop *loop, > > /* Unswitch single LOOP. PREDICATE_PATH contains so far used predicates > for unswitching. BUDGET is number of instruction for which we can increase > - the loop and is updated when unswitching occurs. */ > + the loop and is updated when unswitching occurs. If HOTTEST is not > + NULL then pick this candidate as the one to unswitch on. */ > > static bool > tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc, > predicate_vector &predicate_path, > unsigned loop_size, unsigned &budget, > - int ignored_edge_flag, bitmap handled) > + int ignored_edge_flag, bitmap handled, > + unswitch_predicate *hottest, basic_block hottest_bb) > { > class loop *nloop; > bool changed = false; > @@ -939,8 +974,15 @@ tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc, > } > return false; > }; > - /* Check predicates of reachable blocks. */ > - evaluate_bbs (loop, NULL, ignored_edge_flag, check_predicates); > + > + if (hottest) > + { > + predicate = hottest; > + predicate_bb = hottest_bb; > + } > + else > + /* Check predicates of reachable blocks. */ > + evaluate_bbs (loop, NULL, ignored_edge_flag, check_predicates); > > if (predicate != NULL) > { > -- 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)