public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/marxin/heads/loop-unswitching-switch-v3)] Use ranger in loop unswitching.
@ 2021-09-13 15:30 Martin Liska
0 siblings, 0 replies; 2+ messages in thread
From: Martin Liska @ 2021-09-13 15:30 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:e91cc5544a450f1040f20cc17a13c5983762f01b
commit e91cc5544a450f1040f20cc17a13c5983762f01b
Author: Martin Liska <mliska@suse.cz>
Date: Mon Sep 13 14:16:00 2021 +0200
Use ranger in loop unswitching.
Diff:
---
gcc/tree-ssa-loop-unswitch.c | 115 +++++++++++++++++++++++--------------------
1 file changed, 62 insertions(+), 53 deletions(-)
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index 47d9bfaf467..347cbf443df 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -40,6 +40,7 @@ along with GCC; see the file COPYING3. If not see
#include "cfganal.h"
#include "tree-cfgcleanup.h"
#include "tree-pretty-print.h"
+#include "gimple-range.h"
/* This file implements the loop unswitching, i.e. transformation of loops like
@@ -79,7 +80,7 @@ along with GCC; see the file COPYING3. If not see
static class loop *tree_unswitch_loop (class loop *, basic_block, tree, edge);
static bool tree_unswitch_single_loop (class loop *, int);
-static tree tree_may_unswitch_on (basic_block, class loop *, edge *, tree *);
+static tree tree_may_unswitch_on (basic_block, class loop *, edge *);
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);
@@ -100,8 +101,10 @@ tree_ssa_unswitch_loops (void)
for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
{
if (!loop->inner)
- /* Unswitch innermost loop. */
- changed |= tree_unswitch_single_loop (loop, 0);
+ {
+ /* Unswitch innermost loop. */
+ changed |= tree_unswitch_single_loop (loop, 0);
+ }
else
changed |= tree_unswitch_outer_loop (loop);
}
@@ -193,8 +196,7 @@ is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
When a gswitch case is returned, fill up COND_EDGE for it. */
static tree
-tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge,
- tree *case_expr)
+tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge)
{
gimple *last, *def;
tree use;
@@ -266,9 +268,6 @@ tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge,
if (e == e2)
{
tree cmp;
- if (*case_expr == NULL)
- *case_expr = CASE_LOW (lab);
-
if (CASE_HIGH (lab) != NULL_TREE)
{
tree cmp1 = build2 (GE_EXPR, boolean_type_node, idx,
@@ -314,7 +313,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
class loop *nloop;
unsigned i, found;
tree cond = NULL_TREE;
- tree case_expr = NULL_TREE;
edge cond_edge = NULL;
gimple *stmt;
bool changed = false;
@@ -358,12 +356,12 @@ tree_unswitch_single_loop (class loop *loop, int num)
bbs = get_loop_body (loop);
found = loop->num_nodes;
+ gimple_ranger ranger;
while (1)
{
/* Find a bb to unswitch on. */
for (; i < loop->num_nodes; i++)
- if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge,
- &case_expr)))
+ if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge)))
break;
if (i == loop->num_nodes)
@@ -382,6 +380,58 @@ tree_unswitch_single_loop (class loop *loop, int num)
}
stmt = last_stmt (bbs[i]);
+ gcond *condition = dyn_cast<gcond *> (stmt);
+ gswitch *swtch = dyn_cast<gswitch *> (stmt);
+
+ if (condition != NULL)
+ {
+ int_range_max r;
+ edge edge_true, edge_false;
+ extract_true_false_edges_from_block (bbs[i], &edge_true, &edge_false);
+
+ if (ranger.range_on_edge (r, edge_true, gimple_cond_lhs (stmt))
+ && r.undefined_p ())
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_false_node);
+ changed = true;
+ }
+ else if(ranger.range_on_edge (r, edge_false, gimple_cond_lhs (stmt))
+ && r.undefined_p ())
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_true_node);
+ changed = true;
+ }
+ }
+ else if (swtch != NULL)
+ {
+ hash_set<edge> ignored_edges;
+ unsigned nlabels = gimple_switch_num_labels (swtch);
+ tree index_candidate = NULL_TREE;
+
+ for (unsigned i = 0; i < nlabels; ++i)
+ {
+ tree lab = gimple_switch_label (swtch, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e = find_edge (gimple_bb (stmt), dest);
+
+ int_range_max r;
+ if (ranger.range_on_edge (r, e, gimple_switch_index (swtch))
+ && r.undefined_p ())
+ {
+ e->flags |= EDGE_IGNORE;
+ ignored_edges.add (e);
+ }
+ else
+ index_candidate = CASE_LOW (lab);
+ }
+
+ if (index_candidate != NULL_TREE
+ && ignored_edges.elements () == EDGE_COUNT (bbs[i]->succs) - 1)
+ gimple_switch_set_index (swtch, index_candidate);
+ }
+
/* gswitch can return NULL_TREE for cases that are not supported. */
if (cond == NULL_TREE)
;
@@ -471,8 +521,7 @@ tree_unswitch_single_loop (class loop *loop, int num)
/* 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, &cond_edge,
- &case_expr)))
+ && (cond = tree_may_unswitch_on (bbs[found], loop, &cond_edge)))
break;
if (found == loop->num_nodes)
@@ -499,46 +548,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
return changed;
}
- /* Mark false edge of the newly created condition. */
- basic_block bb = bbs[found];
- stmt = last_stmt (bb);
- if (is_a <gcond *> (stmt))
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_true_node);
- else
- gimple_switch_set_index (as_a <gswitch *> (stmt), case_expr);
- update_stmt (stmt);
-
- /* Mark true edge of the newly created condition. */
- basic_block *nbbs = get_loop_body (nloop);
- for (unsigned i = 0; i < nloop->num_nodes; ++i)
- {
- basic_block nbb = nbbs[i];
- if (bb == get_bb_original (nbb))
- {
- stmt = last_stmt (nbb);
- if (is_a <gcond *> (stmt))
- {
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_false_node);
- update_stmt (stmt);
- }
- else
- {
- edge e2;
- edge_iterator ei;
- FOR_EACH_EDGE (e2, ei, nbb->succs)
- if (cond_edge->dest == get_bb_original (e2->dest))
- {
- e2->flags |= EDGE_IGNORE;
- break;
- }
- }
- break;
- }
- }
- free (nbbs);
-
/* Update the SSA form after unswitching. */
update_ssa (TODO_update_ssa);
free_original_copy_tables ();
^ permalink raw reply [flat|nested] 2+ messages in thread
* [gcc(refs/users/marxin/heads/loop-unswitching-switch-v3)] Use ranger in loop unswitching.
@ 2021-09-13 13:26 Martin Liska
0 siblings, 0 replies; 2+ messages in thread
From: Martin Liska @ 2021-09-13 13:26 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:bde7dc34c6d0cc1ffbcd21b34f8dcfa1d2dbb646
commit bde7dc34c6d0cc1ffbcd21b34f8dcfa1d2dbb646
Author: Martin Liska <mliska@suse.cz>
Date: Mon Sep 13 14:16:00 2021 +0200
Use ranger in loop unswitching.
Diff:
---
gcc/tree-ssa-loop-unswitch.c | 115 +++++++++++++++++++++++--------------------
1 file changed, 62 insertions(+), 53 deletions(-)
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index 47d9bfaf467..347cbf443df 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -40,6 +40,7 @@ along with GCC; see the file COPYING3. If not see
#include "cfganal.h"
#include "tree-cfgcleanup.h"
#include "tree-pretty-print.h"
+#include "gimple-range.h"
/* This file implements the loop unswitching, i.e. transformation of loops like
@@ -79,7 +80,7 @@ along with GCC; see the file COPYING3. If not see
static class loop *tree_unswitch_loop (class loop *, basic_block, tree, edge);
static bool tree_unswitch_single_loop (class loop *, int);
-static tree tree_may_unswitch_on (basic_block, class loop *, edge *, tree *);
+static tree tree_may_unswitch_on (basic_block, class loop *, edge *);
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);
@@ -100,8 +101,10 @@ tree_ssa_unswitch_loops (void)
for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
{
if (!loop->inner)
- /* Unswitch innermost loop. */
- changed |= tree_unswitch_single_loop (loop, 0);
+ {
+ /* Unswitch innermost loop. */
+ changed |= tree_unswitch_single_loop (loop, 0);
+ }
else
changed |= tree_unswitch_outer_loop (loop);
}
@@ -193,8 +196,7 @@ is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
When a gswitch case is returned, fill up COND_EDGE for it. */
static tree
-tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge,
- tree *case_expr)
+tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge)
{
gimple *last, *def;
tree use;
@@ -266,9 +268,6 @@ tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge,
if (e == e2)
{
tree cmp;
- if (*case_expr == NULL)
- *case_expr = CASE_LOW (lab);
-
if (CASE_HIGH (lab) != NULL_TREE)
{
tree cmp1 = build2 (GE_EXPR, boolean_type_node, idx,
@@ -314,7 +313,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
class loop *nloop;
unsigned i, found;
tree cond = NULL_TREE;
- tree case_expr = NULL_TREE;
edge cond_edge = NULL;
gimple *stmt;
bool changed = false;
@@ -358,12 +356,12 @@ tree_unswitch_single_loop (class loop *loop, int num)
bbs = get_loop_body (loop);
found = loop->num_nodes;
+ gimple_ranger ranger;
while (1)
{
/* Find a bb to unswitch on. */
for (; i < loop->num_nodes; i++)
- if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge,
- &case_expr)))
+ if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge)))
break;
if (i == loop->num_nodes)
@@ -382,6 +380,58 @@ tree_unswitch_single_loop (class loop *loop, int num)
}
stmt = last_stmt (bbs[i]);
+ gcond *condition = dyn_cast<gcond *> (stmt);
+ gswitch *swtch = dyn_cast<gswitch *> (stmt);
+
+ if (condition != NULL)
+ {
+ int_range_max r;
+ edge edge_true, edge_false;
+ extract_true_false_edges_from_block (bbs[i], &edge_true, &edge_false);
+
+ if (ranger.range_on_edge (r, edge_true, gimple_cond_lhs (stmt))
+ && r.undefined_p ())
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_false_node);
+ changed = true;
+ }
+ else if(ranger.range_on_edge (r, edge_false, gimple_cond_lhs (stmt))
+ && r.undefined_p ())
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_true_node);
+ changed = true;
+ }
+ }
+ else if (swtch != NULL)
+ {
+ hash_set<edge> ignored_edges;
+ unsigned nlabels = gimple_switch_num_labels (swtch);
+ tree index_candidate = NULL_TREE;
+
+ for (unsigned i = 0; i < nlabels; ++i)
+ {
+ tree lab = gimple_switch_label (swtch, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e = find_edge (gimple_bb (stmt), dest);
+
+ int_range_max r;
+ if (ranger.range_on_edge (r, e, gimple_switch_index (swtch))
+ && r.undefined_p ())
+ {
+ e->flags |= EDGE_IGNORE;
+ ignored_edges.add (e);
+ }
+ else
+ index_candidate = CASE_LOW (lab);
+ }
+
+ if (index_candidate != NULL_TREE
+ && ignored_edges.elements () == EDGE_COUNT (bbs[i]->succs) - 1)
+ gimple_switch_set_index (swtch, index_candidate);
+ }
+
/* gswitch can return NULL_TREE for cases that are not supported. */
if (cond == NULL_TREE)
;
@@ -471,8 +521,7 @@ tree_unswitch_single_loop (class loop *loop, int num)
/* 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, &cond_edge,
- &case_expr)))
+ && (cond = tree_may_unswitch_on (bbs[found], loop, &cond_edge)))
break;
if (found == loop->num_nodes)
@@ -499,46 +548,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
return changed;
}
- /* Mark false edge of the newly created condition. */
- basic_block bb = bbs[found];
- stmt = last_stmt (bb);
- if (is_a <gcond *> (stmt))
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_true_node);
- else
- gimple_switch_set_index (as_a <gswitch *> (stmt), case_expr);
- update_stmt (stmt);
-
- /* Mark true edge of the newly created condition. */
- basic_block *nbbs = get_loop_body (nloop);
- for (unsigned i = 0; i < nloop->num_nodes; ++i)
- {
- basic_block nbb = nbbs[i];
- if (bb == get_bb_original (nbb))
- {
- stmt = last_stmt (nbb);
- if (is_a <gcond *> (stmt))
- {
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_false_node);
- update_stmt (stmt);
- }
- else
- {
- edge e2;
- edge_iterator ei;
- FOR_EACH_EDGE (e2, ei, nbb->succs)
- if (cond_edge->dest == get_bb_original (e2->dest))
- {
- e2->flags |= EDGE_IGNORE;
- break;
- }
- }
- break;
- }
- }
- free (nbbs);
-
/* Update the SSA form after unswitching. */
update_ssa (TODO_update_ssa);
free_original_copy_tables ();
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2021-09-13 15:30 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-09-13 15:30 [gcc(refs/users/marxin/heads/loop-unswitching-switch-v3)] Use ranger in loop unswitching Martin Liska
-- strict thread matches above, loose matches on Subject: below --
2021-09-13 13:26 Martin Liska
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).