Re: [PATCH] unswitch most profitable condition first
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 (!candidat
[PATCH] unswitch most profitable condition first
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?
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
