From: "Martin Liška" <mliska@suse.cz>
To: Richard Biener <richard.guenther@gmail.com>
Cc: GCC Patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH] Loop unswitching: support gswitch statements.
Date: Mon, 29 Nov 2021 13:45:52 +0100 [thread overview]
Message-ID: <20265d97-6350-c234-695d-bc18e2e617b4@suse.cz> (raw)
In-Reply-To: <CAFiYyc3vdrwggxgN4GoekF4wATdmdUEuwt+JMx+2hQyX4dXQvQ@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 2152 bytes --]
On 11/26/21 09:12, Richard Biener wrote:
> On Wed, Nov 24, 2021 at 3:32 PM Martin Liška <mliska@suse.cz> wrote:
>>
>> On 11/24/21 15:14, Martin Liška wrote:
>>> It likely miscompiles gcc.dg/loop-unswitch-5.c, working on that..
>>
>> Fixed that in the updated version.
>
> Function level comments need updating it seems.
I've done that.
>
> +static unsigned
> +evaluate_insns (class loop *loop, basic_block *bbs,
> + predicate_vector &predicate_path,
> + auto_bb_flag &reachable_flag)
> +{
> + auto_vec<basic_block> worklist (loop->num_nodes);
> + worklist.quick_push (bbs[0]);
> ...
>
> so when adding gswitch support the easiest way to make
>
> + FOR_EACH_EDGE (e, ei, bb->succs)
> + {
> ...
> + {
> + worklist.safe_push (dest);
> + dest->flags |= reachable_flag;
>
> work is when the gcond/gswitch simplification would mark
> outgoing edges as (non-)executable. For gswitch this
> could be achieved by iterating over the case labels and
> intersecting that with the range while for gcond it's a
> matter of setting an edge flag instead of returning true/false.
Exactly, it can be quite naturally added to the current patch.
> I'd call the common function evaluate_control_stmt_using_entry_checks
> or so and invoke it on the last stmt of a block with >= 2 outgoing
> edges.
Yes, I'll do it for the gswitch support patch.
>
> We still seem to do the simplification work twice, once for costing
> and once for transform, but that's OK for now I guess.
>
> I think you want to clear_aux_for_blocks at the end of the pass.
Called that.
>
> Otherwise I like it - it seems you have some TODO around cost
> modeling. Did you try to do gswitch support ontop as I suggested
> to see if the general structure keeps working?
I vanished and tested the patch. No, I don't have the gswitch support patch
as the current patch was reworked a few times.
Can we please progress and have installed the suggested patch?
Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
Ready to be installed?
Thanks,
Martin
>
> Thanks,
> Richard.
>
>>
>> Martin
[-- Attachment #2: 0001-Loop-unswitching-refactoring-costing-improvement.patch --]
[-- Type: text/x-patch, Size: 25149 bytes --]
From cda58fc6552d4f55ae079e137bcb805fd8ebbc74 Mon Sep 17 00:00:00 2001
From: Martin Liska <mliska@suse.cz>
Date: Mon, 22 Nov 2021 13:54:20 +0100
Subject: [PATCH] Loop unswitching: refactoring & costing improvement
gcc/ChangeLog:
* dbgcnt.def (DEBUG_COUNTER): Add loop_unswitch debug counter.
* tree-ssa-loop-unswitch.c (struct unswitch_predicate): New.
(tree_unswitch_single_loop): Rework it by iterating all
candidates.
(tree_may_unswitch_on): Support Ranger.
(find_unswitching_predicates_for_bb): New.
(get_predicates_for_bb): Likewise.
(set_predicates_for_bb): Likewise.
(init_loop_unswitch_info): Likewise.
(tree_ssa_unswitch_loops): Initialize info before calling
init_loop_unswitch_info.
(combine_range): New.
(simplify_using_entry_checks): Rename to ...
(evaluate_control_stmt_using_entry_checks): ... this.
(simplify_loop_version): Support predicate_path as argument.
(evaluate_insns): New.
(evaluate_loop_insns_for_predicate): Likewise.
gcc/testsuite/ChangeLog:
* gcc.dg/loop-unswitch-8.c: New test.
* gcc.dg/loop-unswitch-9.c: New test.
---
gcc/dbgcnt.def | 1 +
gcc/testsuite/gcc.dg/loop-unswitch-8.c | 31 ++
gcc/testsuite/gcc.dg/loop-unswitch-9.c | 27 ++
gcc/tree-ssa-loop-unswitch.c | 592 +++++++++++++++++--------
4 files changed, 463 insertions(+), 188 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/loop-unswitch-8.c
create mode 100644 gcc/testsuite/gcc.dg/loop-unswitch-9.c
diff --git a/gcc/dbgcnt.def b/gcc/dbgcnt.def
index f8a15f3d1d1..278fb1112b3 100644
--- a/gcc/dbgcnt.def
+++ b/gcc/dbgcnt.def
@@ -187,6 +187,7 @@ DEBUG_COUNTER (ira_move)
DEBUG_COUNTER (ivopts_loop)
DEBUG_COUNTER (lim)
DEBUG_COUNTER (local_alloc_for_sched)
+DEBUG_COUNTER (loop_unswitch)
DEBUG_COUNTER (match)
DEBUG_COUNTER (merged_ipa_icf)
DEBUG_COUNTER (phiopt_edge_range)
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-8.c b/gcc/testsuite/gcc.dg/loop-unswitch-8.c
new file mode 100644
index 00000000000..ae5f8f300e9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-8.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details" } */
+
+int
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ if (order < 3)
+ tmp = -8 * a[i];
+ else
+ tmp = -4 * b[i];
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ if (5 > order)
+ x += 2;
+
+ if (order == 12345)
+ x *= 5;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop on condition: order" 3 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-9.c b/gcc/testsuite/gcc.dg/loop-unswitch-9.c
new file mode 100644
index 00000000000..9dd6023d49d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-9.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details" } */
+
+int
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ if (order == 1)
+ tmp = -8 * a[i];
+ else
+ {
+ if (order == 2)
+ tmp = -4 * b[i];
+ else
+ tmp = a[i];
+ }
+
+ r[i] = 3.4f * tmp + d[i];
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop on condition: order" 2 "unswitch" } } */
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index fe4dacc0833..12fa6b86088 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -37,6 +37,11 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "cfghooks.h"
#include "tree-ssa-loop-manip.h"
+#include "tree-pretty-print.h"
+#include "gimple-range.h"
+#include "dbgcnt.h"
+
+#include <utility>
/* This file implements the loop unswitching, i.e. transformation of loops like
@@ -74,9 +79,38 @@ along with GCC; see the file COPYING3. If not see
tree-ssa-loop-im.c ensures that all the suitable conditions are in this
shape. */
+/* A tuple that holds GIMPLE condition and value range for an unswitching
+ predicate. */
+
+struct unswitch_predicate
+{
+ /* Default constructor. */
+ unswitch_predicate (tree cond, tree lhs_)
+ : condition (cond), lhs (lhs_), true_range (), false_range ()
+ {}
+
+ tree condition;
+ tree lhs;
+ int_range_max true_range;
+ int_range_max false_range;
+};
+
+/* Cache storage for unswitch_predicate belonging to a basic block. */
+static vec<vec<unswitch_predicate *>> *bb_predicates = NULL;
+
+/* Ranger instance used in the pass. */
+static gimple_ranger *ranger = NULL;
+
+/* The type represents a predicate path leading to a basic block. */
+typedef auto_vec<std::pair<unswitch_predicate *, bool>> predicate_vector;
+
static class loop *tree_unswitch_loop (class loop *, basic_block, tree);
-static bool tree_unswitch_single_loop (class loop *, int);
-static tree tree_may_unswitch_on (basic_block, class loop *);
+static bool tree_unswitch_single_loop (class loop *, int,
+ predicate_vector &predicate_path,
+ unsigned budget);
+static void
+find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
+ vec<unswitch_predicate *> &candidates);
static bool tree_unswitch_outer_loop (class loop *);
static edge find_loop_guard (class loop *);
static bool empty_bb_without_guard_p (class loop *, basic_block);
@@ -85,6 +119,67 @@ static void hoist_guard (class loop *, edge);
static bool check_exit_phi (class loop *);
static tree get_vop_from_header (class loop *);
+/* Return vector of predicates that belong to a basic block. */
+
+static vec<unswitch_predicate *> &
+get_predicates_for_bb (basic_block bb)
+{
+ gimple *last = last_stmt (bb);
+ return (*bb_predicates)[last == NULL ? 0 : gimple_uid (last)];
+}
+
+/* Save predicates that belong to a basic block. */
+
+static void
+set_predicates_for_bb (basic_block bb, vec<unswitch_predicate *> predicates)
+{
+ gimple_set_uid (last_stmt (bb), bb_predicates->length ());
+ bb_predicates->safe_push (predicates);
+}
+
+/* Initialize LOOP information reused during the unswitching pass.
+ Return total number of instructions in the loop. */
+
+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++)
+ {
+ unsigned insns = 0;
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ insns += estimate_num_insns (gsi_stmt (gsi), &eni_size_weights);
+
+ bbs[i]->aux = (void *)(size_t)insns;
+ total_insns += insns;
+ }
+
+ /* Find all unswitching candidates. */
+ for (unsigned i = 0; i != loop->num_nodes; i++)
+ {
+ /* Find a bb to unswitch on. */
+ vec<unswitch_predicate *> candidates;
+ candidates.create (1);
+ find_unswitching_predicates_for_bb (bbs[i], loop, candidates);
+ if (!candidates.is_empty ())
+ set_predicates_for_bb (bbs[i], candidates);
+ else
+ {
+ gimple *last = last_stmt (bbs[i]);
+ if (last != NULL)
+ gimple_set_uid (last, 0);
+ }
+ }
+
+ free (bbs);
+
+ return total_insns;
+}
+
/* Main entry point. Perform loop unswitching on all suitable loops. */
unsigned int
@@ -92,16 +187,35 @@ tree_ssa_unswitch_loops (void)
{
bool changed = false;
+ ranger = enable_ranger (cfun);
+
/* Go through all loops starting from innermost. */
for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
{
if (!loop->inner)
- /* Unswitch innermost loop. */
- changed |= tree_unswitch_single_loop (loop, 0);
+ {
+ bb_predicates = new vec<vec<unswitch_predicate *>> ();
+ bb_predicates->safe_push (vec<unswitch_predicate *> ());
+
+ /* Unswitch innermost 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,
+ budget);
+
+ delete bb_predicates;
+ bb_predicates = NULL;
+ }
else
changed |= tree_unswitch_outer_loop (loop);
}
+
+ disable_ranger (cfun);
+ clear_aux_for_blocks ();
+
if (changed)
return TODO_cleanup_cfg;
return 0;
@@ -182,10 +296,12 @@ is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
}
/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
- basic blocks (for what it means see comments below). */
+ basic blocks (for what it means see comments below).
+ All candidates all filled to the provided vector CANDIDATES. */
-static tree
-tree_may_unswitch_on (basic_block bb, class loop *loop)
+static void
+find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
+ vec<unswitch_predicate *> &candidates)
{
gimple *last, *def;
gcond *stmt;
@@ -196,14 +312,14 @@ tree_may_unswitch_on (basic_block bb, class loop *loop)
/* BB must end in a simple conditional jump. */
last = last_stmt (bb);
if (!last || gimple_code (last) != GIMPLE_COND)
- return NULL_TREE;
+ return;
stmt = as_a <gcond *> (last);
/* To keep the things simple, we do not directly remove the conditions,
but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite
loop where we would unswitch again on such a condition. */
if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
- return NULL_TREE;
+ return;
/* Condition must be invariant. */
FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
@@ -212,64 +328,245 @@ tree_may_unswitch_on (basic_block bb, class loop *loop)
def_bb = gimple_bb (def);
if (def_bb
&& flow_bb_inside_loop_p (loop, def_bb))
- return NULL_TREE;
+ return;
/* Unswitching on undefined values would introduce undefined
behavior that the original program might never exercise. */
if (is_maybe_undefined (use, stmt, loop))
- return NULL_TREE;
+ return;
}
- cond = build2 (gimple_cond_code (stmt), boolean_type_node,
- gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+ tree lhs = gimple_cond_lhs (stmt);
+ tree rhs = gimple_cond_rhs (stmt);
+
+ cond = build2 (gimple_cond_code (stmt), boolean_type_node, lhs, rhs);
+ edge edge_true, edge_false;
+ extract_true_false_edges_from_block (bb, &edge_true, &edge_false);
+
+ unswitch_predicate *predicate = new unswitch_predicate (cond, lhs);
+ if (irange::supports_type_p (TREE_TYPE (lhs)) && CONSTANT_CLASS_P (rhs))
+ {
+ ranger->range_on_edge (predicate->true_range, edge_true, lhs);
+ predicate->false_range = predicate->true_range;
- return cond;
+ if (!predicate->false_range.varying_p ()
+ && !predicate->false_range.undefined_p ())
+ predicate->false_range.invert ();
+ }
+
+ candidates.safe_push (predicate);
}
-/* Simplifies COND using checks in front of the entry of the LOOP. Just very
- simplish (sufficient to prevent us from duplicating loop in unswitching
- unnecessarily). */
+static void
+combine_range (predicate_vector &predicate_path, tree index, irange &path_range)
+{
+ bool first = true;
+
+ for (auto p: predicate_path)
+ {
+ unswitch_predicate *predicate = p.first;
+ bool true_edge = p.second;
+
+ if (operand_equal_p (predicate->lhs, index, 0))
+ {
+ irange &other
+ = true_edge ? predicate->true_range : predicate->false_range;
+ if (first)
+ {
+ first = false;
+ path_range = other;
+ }
+ else
+ path_range.intersect (other);
+ }
+ }
+}
+
+/* Simplifies COND using checks in front of the entry of the LOOP.
+ Utilize both symbolic expressions and value ranges calculated by Ranger. */
static tree
-simplify_using_entry_checks (class loop *loop, tree cond)
+evaluate_control_stmt_using_entry_checks (gimple *stmt,
+ predicate_vector &predicate_path)
{
- edge e = loop_preheader_edge (loop);
- gimple *stmt;
+ if (predicate_path.is_empty ())
+ return NULL_TREE;
- while (1)
+ tree lhs = gimple_cond_lhs (stmt);
+ unswitch_predicate *last_predicate = predicate_path.last ().first;
+ bool true_edge = predicate_path.last ().second;
+
+ if (gimple_code (stmt) == GIMPLE_COND
+ && operand_equal_p (lhs, last_predicate->lhs, 0))
{
- stmt = last_stmt (e->src);
- if (stmt
- && gimple_code (stmt) == GIMPLE_COND
- && gimple_cond_code (stmt) == TREE_CODE (cond)
- && operand_equal_p (gimple_cond_lhs (stmt),
- TREE_OPERAND (cond, 0), 0)
+ if (gimple_cond_code (stmt) == TREE_CODE (last_predicate->condition)
&& operand_equal_p (gimple_cond_rhs (stmt),
- TREE_OPERAND (cond, 1), 0))
- return (e->flags & EDGE_TRUE_VALUE
- ? boolean_true_node
- : boolean_false_node);
+ TREE_OPERAND (last_predicate->condition, 1), 0))
+ return true_edge ? boolean_true_node : boolean_false_node;
+ else if (irange::supports_type_p (TREE_TYPE (lhs)))
+ {
+ int_range_max r;
+ int_range_max path_range;
+ combine_range (predicate_path, lhs, path_range);
+ if (!path_range.undefined_p ()
+ && fold_range (r, stmt, path_range)
+ && r.singleton_p ())
+ return r.zero_p () ? boolean_false_node : boolean_true_node;
+ }
+ }
+
+ return NULL_TREE;
+}
+
+/* Simplify LOOP based on PREDICATE_PATH where dead edges are properly
+ marked. */
- if (!single_pred_p (e->src))
- return cond;
+static bool
+simplify_loop_version (class loop *loop, predicate_vector &predicate_path)
+{
+ bool changed = false;
+ basic_block *bbs = get_loop_body (loop);
+
+ for (unsigned i = 0; i != loop->num_nodes; i++)
+ {
+ // FIXME: works only for gconds
+ if (!get_predicates_for_bb (bbs[i]).is_empty ())
+ {
+ gimple *stmt = last_stmt (bbs[i]);
- e = single_pred_edge (e->src);
- if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
- return cond;
+ tree folded = evaluate_control_stmt_using_entry_checks (stmt,
+ predicate_path);
+ if (folded != NULL_TREE)
+ {
+ /* Remove path. */
+ gcond *cond = dyn_cast<gcond *> (stmt);
+ if (integer_nonzerop (folded))
+ gimple_cond_set_condition_from_tree (cond, boolean_true_node);
+ else
+ gimple_cond_set_condition_from_tree (cond, boolean_false_node);
+
+ gimple_set_uid (cond, 0);
+ update_stmt (cond);
+ changed = true;
+ }
+ }
}
+
+ free (bbs);
+ return changed;
+}
+
+/* Evaluate how many instructions will be executed if we unswitch
+ LOOP (with BBS) based on PREDICATE_PATH.
+ REACHABLE_FLAG is used for marking of the basic blocks. */
+
+static unsigned
+evaluate_insns (class loop *loop, basic_block *bbs,
+ predicate_vector &predicate_path,
+ auto_bb_flag &reachable_flag)
+{
+ auto_vec<basic_block> worklist (loop->num_nodes);
+ worklist.quick_push (bbs[0]);
+
+ while (!worklist.is_empty ())
+ {
+ edge e;
+ edge_iterator ei;
+ int flags = 0;
+ basic_block bb = worklist.pop ();
+
+ if (EDGE_COUNT (bb->succs) == 2)
+ {
+ gcond *cond = dyn_cast<gcond *> (last_stmt (bb));
+ if (cond != NULL)
+ {
+ if (gimple_cond_true_p (cond))
+ flags = EDGE_FALSE_VALUE;
+ else if (gimple_cond_false_p (cond))
+ flags = EDGE_TRUE_VALUE;
+ else
+ {
+ // FIXME: works only for gconds
+ unswitch_predicate *predicate = NULL;
+ if (!get_predicates_for_bb (bb).is_empty ())
+ predicate = get_predicates_for_bb (bb)[0];
+
+ if (predicate != NULL)
+ {
+ tree folded
+ = evaluate_control_stmt_using_entry_checks (cond,
+ predicate_path);
+ if (folded == boolean_true_node)
+ flags = EDGE_FALSE_VALUE;
+ else if (folded == boolean_false_node)
+ flags = EDGE_TRUE_VALUE;
+ }
+ }
+ }
+ }
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ basic_block dest = e->dest;
+
+ if (dest->loop_father == loop
+ && !(dest->flags & reachable_flag)
+ && !(e->flags & flags))
+ {
+ worklist.safe_push (dest);
+ dest->flags |= reachable_flag;
+ }
+ }
+ }
+
+ /* Evaluate insns. */
+ unsigned size = 0;
+
+ for (unsigned i = 0; i < loop->num_nodes; i++)
+ if (bbs[i]->flags & reachable_flag)
+ size += (size_t)bbs[i]->aux;
+
+ /* Clear the flag from basic blocks. */
+ for (unsigned i = 0; i < loop->num_nodes; i++)
+ bbs[i]->flags &= ~reachable_flag;
+
+ return size;
+}
+
+/* Evaluate how many instruction will we have if we unswitch LOOP (with BBS)
+ based on PREDICATE predicate (using PREDICATE_PATH). */
+
+static unsigned
+evaluate_loop_insns_for_predicate (class loop *loop, basic_block *bbs,
+ predicate_vector &predicate_path,
+ unswitch_predicate *predicate)
+{
+ auto_bb_flag reachable_flag (cfun);
+
+ predicate_path.safe_push (std::make_pair (predicate, true));
+ unsigned true_loop_cost = evaluate_insns (loop, bbs, predicate_path,
+ reachable_flag);
+ predicate_path.pop ();
+
+ predicate_path.safe_push (std::make_pair (predicate, false));
+ unsigned false_loop_cost = evaluate_insns (loop, bbs, predicate_path,
+ reachable_flag);
+ predicate_path.pop ();
+
+ return true_loop_cost + false_loop_cost;
}
/* 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. */
+ grow exponentially. PREDICATE_PATH contains so far used predicates
+ 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)
+tree_unswitch_single_loop (class loop *loop, int num,
+ predicate_vector &predicate_path, unsigned budget)
{
- basic_block *bbs;
+ basic_block *bbs = NULL;
class loop *nloop;
- unsigned i, found;
- tree cond = NULL_TREE;
- gimple *stmt;
bool changed = false;
HOST_WIDE_INT iterations;
@@ -284,15 +581,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
return false;
}
- /* The loop should not be too large, to limit code growth. */
- if (tree_num_loop_insns (loop, &eni_size_weights)
- > (unsigned) param_max_unswitch_insns)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ";; Not unswitching, loop too big\n");
- return false;
- }
-
/* If the loop is not expected to iterate, there is no need
for unswitching. */
iterations = estimated_loop_iterations_int (loop);
@@ -307,166 +595,94 @@ tree_unswitch_single_loop (class loop *loop, int num)
}
}
- i = 0;
+ unswitch_predicate *predicate = NULL;
+ basic_block bb = NULL;
+ if (num > param_max_unswitch_level)
+ {
+ if (dump_file
+ && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
+ goto exit;
+ }
+
bbs = get_loop_body (loop);
- found = loop->num_nodes;
- while (1)
+ for (unsigned i = 0; i < loop->num_nodes; i++)
{
- /* Find a bb to unswitch on. */
- for (; i < loop->num_nodes; i++)
- if ((cond = tree_may_unswitch_on (bbs[i], loop)))
- break;
-
- if (i == loop->num_nodes)
+ vec<unswitch_predicate *> &preds = get_predicates_for_bb (bbs[i]);
+ for (auto pred: preds)
{
- if (dump_file
- && num > param_max_unswitch_level
- && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
+ unsigned cost
+ = evaluate_loop_insns_for_predicate (loop, bbs, predicate_path,
+ pred);
- if (found == loop->num_nodes)
+ /* FIXME: right now we select first candidate, but we can choose
+ a cheapest (best) one. */
+ if (cost <= budget)
{
- free (bbs);
- return changed;
+ predicate = pred;
+ bb = bbs[i];
+ budget -= cost;
+ break;
+ }
+ else if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, ";; Not unswitching condition, cost too big "
+ "(%d insns): ", cost);
+ print_generic_expr (dump_file, pred->condition);
+ fprintf (dump_file, "\n");
}
- break;
- }
-
- cond = simplify_using_entry_checks (loop, cond);
- stmt = last_stmt (bbs[i]);
- if (integer_nonzerop (cond))
- {
- /* Remove false path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_true_node);
- changed = true;
- }
- else if (integer_zerop (cond))
- {
- /* Remove true path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_false_node);
- changed = true;
- }
- /* Do not unswitch too much. */
- else if (num > param_max_unswitch_level)
- {
- i++;
- continue;
- }
- /* In nested tree_unswitch_single_loop first optimize all conditions
- using entry checks, then discover still reachable blocks in the
- loop and find the condition only among those still reachable bbs. */
- else if (num != 0)
- {
- if (found == loop->num_nodes)
- found = i;
- i++;
- continue;
- }
- else
- {
- found = i;
- break;
}
-
- update_stmt (stmt);
- i++;
}
- if (num != 0)
+ if (predicate != NULL)
{
- basic_block *tos, *worklist;
-
- /* When called recursively, first do a quick discovery
- of reachable bbs after the above changes and only
- consider conditions in still reachable bbs. */
- tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
+ if (!dbg_cnt (loop_unswitch))
+ goto exit;
- for (i = 0; i < loop->num_nodes; i++)
- bbs[i]->flags &= ~BB_REACHABLE;
-
- /* Start with marking header. */
- *tos++ = bbs[0];
- bbs[0]->flags |= BB_REACHABLE;
-
- /* Iterate: find everything reachable from what we've already seen
- within the same innermost loop. Don't look through false edges
- if condition is always true or true edges if condition is
- always false. */
- while (tos != worklist)
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- basic_block b = *--tos;
- edge e;
- edge_iterator ei;
- int flags = 0;
-
- if (EDGE_COUNT (b->succs) == 2)
- {
- gimple *stmt = last_stmt (b);
- if (stmt
- && gimple_code (stmt) == GIMPLE_COND)
- {
- gcond *cond_stmt = as_a <gcond *> (stmt);
- if (gimple_cond_true_p (cond_stmt))
- flags = EDGE_FALSE_VALUE;
- else if (gimple_cond_false_p (cond_stmt))
- flags = EDGE_TRUE_VALUE;
- }
- }
-
- FOR_EACH_EDGE (e, ei, b->succs)
- {
- basic_block dest = e->dest;
-
- if (dest->loop_father == loop
- && !(dest->flags & BB_REACHABLE)
- && !(e->flags & flags))
- {
- *tos++ = dest;
- dest->flags |= BB_REACHABLE;
- }
- }
+ fprintf (dump_file, ";; Unswitching loop on condition: ");
+ print_generic_expr (dump_file, predicate->condition);
+ fprintf (dump_file, "\n");
}
- free (worklist);
-
- /* Find a bb to unswitch on. */
- for (; found < loop->num_nodes; found++)
- if ((bbs[found]->flags & BB_REACHABLE)
- && (cond = tree_may_unswitch_on (bbs[found], loop)))
- break;
-
- if (found == loop->num_nodes)
+ initialize_original_copy_tables ();
+ /* Unswitch the loop on this condition. */
+ nloop = tree_unswitch_loop (loop, bb, predicate->condition);
+ if (!nloop)
{
- free (bbs);
- return changed;
+ free_original_copy_tables ();
+ goto exit;
}
- }
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ";; Unswitching loop\n");
+ /* Copy BB costs. */
+ basic_block *bbs2 = get_loop_body (nloop);
+ for (unsigned i = 0; i < nloop->num_nodes; i++)
+ bbs2[i]->aux = get_bb_original (bbs2[i])->aux;
- initialize_original_copy_tables ();
- /* Unswitch the loop on this condition. */
- nloop = tree_unswitch_loop (loop, bbs[found], cond);
- if (!nloop)
- {
+ free (bbs2);
+
+ /* Update the SSA form after unswitching. */
+ update_ssa (TODO_update_ssa);
free_original_copy_tables ();
- free (bbs);
- return changed;
- }
- /* Update the SSA form after unswitching. */
- update_ssa (TODO_update_ssa);
- free_original_copy_tables ();
+ /* 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, budget);
+ predicate_path.pop ();
- /* Invoke itself on modified loops. */
- tree_unswitch_single_loop (nloop, num + 1);
- tree_unswitch_single_loop (loop, num + 1);
+ 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, budget);
+ predicate_path.pop ();
+ changed = true;
+ }
+
+exit:
free (bbs);
- return true;
+ return changed;
}
/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
--
2.34.0
next prev parent reply other threads:[~2021-11-29 12:45 UTC|newest]
Thread overview: 67+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-09-15 8:46 Martin Liška
2021-09-19 16:50 ` Jeff Law
2021-09-28 11:50 ` Richard Biener
2021-09-28 20:39 ` Andrew MacLeod
2021-09-29 8:43 ` Richard Biener
2021-09-29 15:20 ` Andrew MacLeod
2021-09-29 15:28 ` Jeff Law
2021-09-29 15:59 ` Andrew MacLeod
2021-09-30 7:33 ` Richard Biener
2021-11-08 15:05 ` Martin Liška
2021-11-08 18:34 ` Andrew MacLeod
2021-11-08 19:45 ` Andrew MacLeod
2021-11-09 13:37 ` Richard Biener
2021-11-09 16:41 ` Andrew MacLeod
2021-11-10 7:52 ` Aldy Hernandez
2021-11-10 8:50 ` Richard Biener
2021-11-09 16:44 ` Martin Liška
2021-11-10 8:59 ` Richard Biener
2021-11-10 13:29 ` Martin Liška
2021-11-11 7:15 ` Richard Biener
2021-11-16 13:53 ` Martin Liška
2021-11-19 9:49 ` Richard Biener
2021-11-16 14:40 ` Martin Liška
2021-11-19 10:00 ` Richard Biener
2021-11-22 15:06 ` Martin Liška
2021-11-23 13:58 ` Richard Biener
2021-11-23 15:20 ` Martin Liška
2021-11-23 16:36 ` Martin Liška
2021-11-24 8:00 ` Richard Biener
2021-11-24 10:48 ` Martin Liška
2021-11-24 12:48 ` Richard Biener
2021-11-24 14:14 ` Martin Liška
2021-11-24 14:32 ` Martin Liška
2021-11-26 8:12 ` Richard Biener
2021-11-29 12:45 ` Martin Liška [this message]
2021-11-30 11:17 ` Richard Biener
2021-12-01 14:10 ` Martin Liška
2021-12-01 14:19 ` Richard Biener
2021-12-01 14:25 ` Martin Liška
2021-12-01 14:34 ` Richard Biener
2021-12-01 14:48 ` Martin Liška
2021-12-01 18:21 ` Andrew MacLeod
2021-12-02 11:45 ` Martin Liška
2021-12-02 12:01 ` Richard Biener
2021-12-02 13:10 ` Martin Liška
2021-12-02 13:46 ` Richard Biener
2021-12-08 21:06 ` Andrew MacLeod
2021-12-02 14:27 ` Andrew MacLeod
2021-12-02 16:02 ` Martin Liška
2021-12-03 14:09 ` Andrew MacLeod
2021-12-09 12:59 ` Martin Liška
2021-12-09 14:44 ` Andrew MacLeod
2021-12-09 13:02 ` Martin Liška
2022-01-05 12:34 ` Richard Biener
2022-01-06 15:11 ` Andrew MacLeod
2022-01-06 16:02 ` Martin Liška
2022-01-06 16:20 ` Andrew MacLeod
2022-01-06 16:35 ` Martin Liška
2022-01-06 16:42 ` Andrew MacLeod
2022-01-06 16:32 ` Andrew MacLeod
2022-01-06 16:30 ` Martin Liška
2022-01-13 16:01 ` Martin Liška
2022-01-14 7:23 ` Richard Biener
2021-11-25 10:38 ` Aldy Hernandez
2021-11-26 7:45 ` Richard Biener
2021-11-24 7:46 ` Richard Biener
2021-10-05 17:08 ` Andrew MacLeod
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20265d97-6350-c234-695d-bc18e2e617b4@suse.cz \
--to=mliska@suse.cz \
--cc=gcc-patches@gcc.gnu.org \
--cc=richard.guenther@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).