public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/marxin/heads/loop-unswitching-switch-v5)] Loop unswitching: support gswitch statements.
@ 2021-11-08 15:36 Martin Liska
0 siblings, 0 replies; 5+ messages in thread
From: Martin Liska @ 2021-11-08 15:36 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:5c6911e08a69a34d1488733742b1ae2d0cc5fda5
commit 5c6911e08a69a34d1488733742b1ae2d0cc5fda5
Author: Martin Liska <mliska@suse.cz>
Date: Wed Sep 1 13:04:15 2021 +0200
Loop unswitching: support gswitch statements.
The patch extends the loop unswitching pass so that gswitch
statements are supported. The pass now uses ranger which marks
switch edges that are known to be unreachable in a versioned loop.
gcc/ChangeLog:
* tree-cfg.c (gimple_lv_add_condition_to_bb): Support non-gimple
expressions that needs to be gimplified.
* tree-ssa-loop-unswitch.c (tree_unswitch_loop): Add new
cond_edge parameter.
(tree_may_unswitch_on): Support gswitch statements.
(clean_up_switches): New function.
(tree_ssa_unswitch_loops): Call clean_up_switches.
(simplify_using_entry_checks): Removed and replaced with ranger.
(tree_unswitch_single_loop): Change assumptions.
gcc/testsuite/ChangeLog:
* gcc.dg/loop-unswitch-6.c: New test.
* gcc.dg/loop-unswitch-7.c: New test.
* gcc.dg/loop-unswitch-8.c: New test.
* gcc.dg/loop-unswitch-9.c: New test.
Co-Authored-By: Richard Biener <rguenther@suse.de>
Diff:
---
gcc/testsuite/gcc.dg/loop-unswitch-6.c | 56 +++++++
gcc/testsuite/gcc.dg/loop-unswitch-7.c | 45 ++++++
gcc/testsuite/gcc.dg/loop-unswitch-8.c | 28 ++++
gcc/testsuite/gcc.dg/loop-unswitch-9.c | 34 ++++
gcc/tree-cfg.c | 7 +-
gcc/tree-ssa-loop-unswitch.c | 284 ++++++++++++++++++++++++---------
6 files changed, 374 insertions(+), 80 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-6.c b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
new file mode 100644
index 00000000000..8a022e0f200
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
@@ -0,0 +1,56 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+int
+__attribute__((noipa))
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp, tmp2;
+
+ switch(order)
+ {
+ case 0:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 1:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 2:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 3:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+#define N 16 * 1024
+double aa[N], bb[N], cc[N], dd[N], rr[N];
+
+int main()
+{
+ for (int i = 0; i < 100 * 1000; i++)
+ foo (aa, bb, cc, dd, rr, N, i % 4);
+}
+
+
+/* Test that we actually unswitched something. */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 0" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 1" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 2" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 3" "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-7.c b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
new file mode 100644
index 00000000000..00f2fcff64b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
@@ -0,0 +1,45 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+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, tmp2;
+
+ switch(order)
+ {
+ case 5 ... 6:
+ case 9:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 11:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 22:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 33:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order_.* >= 5 & order_.* <= 6 | order_.* == 9" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 1" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 2" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 3" "unswitch" } } */
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..4cec1f53bcc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-8.c
@@ -0,0 +1,28 @@
+/* { 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
+ tmp = -4 * b[i];
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ if (order == 1)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "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..3058d4a5b38
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-9.c
@@ -0,0 +1,34 @@
+/* { 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, unsigned order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ switch (order)
+ {
+ case 0 ... 4:
+ tmp = -8 * a[i];
+ break;
+ default:
+ tmp = -4 * b[i];
+ break;
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ /* This should not be unswitched as it's mutually excluded with case 0 ... 4. */
+ if (order >= 5)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* <= 4" 1 "unswitch" } } */
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 8ed8c69b5b1..7db54f1cda2 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -9062,11 +9062,16 @@ gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
edge e0;
/* Build new conditional expr */
+ gsi = gsi_last_bb (cond_bb);
+
+ cond_expr = force_gimple_operand_gsi_1 (&gsi, cond_expr,
+ is_gimple_condexpr_for_cond,
+ NULL_TREE, false,
+ GSI_CONTINUE_LINKING);
new_cond_expr = gimple_build_cond_from_tree (cond_expr,
NULL_TREE, NULL_TREE);
/* Add new cond in cond_bb. */
- gsi = gsi_last_bb (cond_bb);
gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
/* Adjust edges appropriately to connect new head with first head
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index fe4dacc0833..a509938c7d0 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -37,6 +37,10 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "cfghooks.h"
#include "tree-ssa-loop-manip.h"
+#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
@@ -74,9 +78,9 @@ 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. */
-static class loop *tree_unswitch_loop (class loop *, basic_block, tree);
+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 *);
+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);
@@ -84,6 +88,7 @@ static bool used_outside_loop_p (class loop *, tree);
static void hoist_guard (class loop *, edge);
static bool check_exit_phi (class loop *);
static tree get_vop_from_header (class loop *);
+static void clean_up_switches (void);
/* Main entry point. Perform loop unswitching on all suitable loops. */
@@ -103,7 +108,10 @@ tree_ssa_unswitch_loops (void)
}
if (changed)
- return TODO_cleanup_cfg;
+ {
+ clean_up_switches ();
+ return TODO_cleanup_cfg;
+ }
return 0;
}
@@ -182,80 +190,114 @@ 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).
+ When a gswitch case is returned, fill up COND_EDGE for it. */
static tree
-tree_may_unswitch_on (basic_block bb, class loop *loop)
+tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge)
{
gimple *last, *def;
- gcond *stmt;
- tree cond, use;
+ tree use;
basic_block def_bb;
ssa_op_iter iter;
/* BB must end in a simple conditional jump. */
last = last_stmt (bb);
- if (!last || gimple_code (last) != GIMPLE_COND)
- return NULL_TREE;
- 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;
-
- /* Condition must be invariant. */
- FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ if (gcond *stmt = safe_dyn_cast <gcond *> (last))
{
- def = SSA_NAME_DEF_STMT (use);
+ /* 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;
+
+ /* Condition must be invariant. */
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ {
+ def = SSA_NAME_DEF_STMT (use);
+ def_bb = gimple_bb (def);
+ if (def_bb
+ && flow_bb_inside_loop_p (loop, def_bb))
+ return NULL_TREE;
+ /* 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;
+ }
+
+ edge e1 = EDGE_SUCC (bb, 0);
+ edge e2 = EDGE_SUCC (bb, 1);
+ *cond_edge = e1->flags & EDGE_TRUE_VALUE ? e1 : e2;
+ return build2 (gimple_cond_code (stmt), boolean_type_node,
+ gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+ }
+ else if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
+ {
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ tree idx = gimple_switch_index (stmt);
+ if (TREE_CODE (idx) != SSA_NAME
+ || nlabels < 1)
+ return NULL_TREE;
+ /* Index must be invariant. */
+ def = SSA_NAME_DEF_STMT (idx);
def_bb = gimple_bb (def);
if (def_bb
&& flow_bb_inside_loop_p (loop, def_bb))
return NULL_TREE;
/* Unswitching on undefined values would introduce undefined
behavior that the original program might never exercise. */
- if (is_maybe_undefined (use, stmt, loop))
+ if (is_maybe_undefined (idx, stmt, loop))
return NULL_TREE;
- }
-
- cond = build2 (gimple_cond_code (stmt), boolean_type_node,
- gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
- return cond;
-}
-
-/* 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 tree
-simplify_using_entry_checks (class loop *loop, tree cond)
-{
- edge e = loop_preheader_edge (loop);
- gimple *stmt;
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
+ {
+ if (!(e->flags & EDGE_IGNORE))
+ {
+ /* Build compound expression for all cases leading
+ to this edge. */
+ tree expr = NULL_TREE;
+ for (unsigned i = 1; i < gimple_switch_num_labels (stmt); ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e2 = find_edge (gimple_bb (stmt), dest);
+ if (e == e2)
+ {
+ tree cmp;
+ if (CASE_HIGH (lab) != NULL_TREE)
+ {
+ tree cmp1 = build2 (GE_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+ tree cmp2 = build2 (LE_EXPR, boolean_type_node, idx,
+ CASE_HIGH (lab));
+ cmp = build2 (BIT_AND_EXPR, boolean_type_node, cmp1,
+ cmp2);
+ }
+ else
+ cmp = build2 (EQ_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+
+ /* Combine the expression with the existing one. */
+ if (expr == NULL_TREE)
+ expr = cmp;
+ else
+ expr = build2 (BIT_IOR_EXPR, boolean_type_node, expr,
+ cmp);
+ }
+ }
- while (1)
- {
- 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)
- && operand_equal_p (gimple_cond_rhs (stmt),
- TREE_OPERAND (cond, 1), 0))
- return (e->flags & EDGE_TRUE_VALUE
- ? boolean_true_node
- : boolean_false_node);
-
- if (!single_pred_p (e->src))
- return cond;
-
- e = single_pred_edge (e->src);
- if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
- return cond;
+ if (expr != NULL_TREE)
+ {
+ *cond_edge = e;
+ return expr;
+ }
+ }
+ }
}
+
+ return NULL_TREE;
}
/* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
@@ -269,6 +311,7 @@ tree_unswitch_single_loop (class loop *loop, int num)
class loop *nloop;
unsigned i, found;
tree cond = NULL_TREE;
+ edge cond_edge = NULL;
gimple *stmt;
bool changed = false;
HOST_WIDE_INT iterations;
@@ -311,11 +354,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)))
+ if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge)))
break;
if (i == loop->num_nodes)
@@ -333,24 +377,70 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- cond = simplify_using_entry_checks (loop, cond);
stmt = last_stmt (bbs[i]);
- if (integer_nonzerop (cond))
+ gcond *condition = dyn_cast<gcond *> (stmt);
+ gswitch *swtch = dyn_cast<gswitch *> (stmt);
+
+ if (condition != NULL)
{
- /* Remove false path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_true_node);
- changed = true;
+ int_range_max r;
+ edge edge_true, edge_false;
+ extract_true_false_edges_from_block (bbs[i], &edge_true, &edge_false);
+ tree cond = gimple_cond_lhs (stmt);
+
+ if (r.supports_type_p (TREE_TYPE (cond)))
+ {
+ if (ranger.range_on_edge (r, edge_true, cond)
+ && r.undefined_p ())
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_false_node);
+ update_stmt (condition);
+ 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);
+ update_stmt (condition);
+ changed = true;
+ }
+ }
}
- else if (integer_zerop (cond))
+ else if (swtch != NULL)
{
- /* Remove true path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_false_node);
- changed = true;
+ 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);
+ update_stmt (swtch);
+ }
}
+
/* Do not unswitch too much. */
- else if (num > param_max_unswitch_level)
+ if (num > param_max_unswitch_level)
{
i++;
continue;
@@ -371,7 +461,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- update_stmt (stmt);
i++;
}
@@ -435,7 +524,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 = tree_may_unswitch_on (bbs[found], loop, &cond_edge)))
break;
if (found == loop->num_nodes)
@@ -446,11 +535,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
}
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ";; Unswitching loop\n");
+ {
+ fprintf (dump_file, ";; Unswitching loop with condition: ");
+ print_generic_expr (dump_file, cond);
+ fprintf (dump_file, "\n");
+ }
initialize_original_copy_tables ();
/* Unswitch the loop on this condition. */
- nloop = tree_unswitch_loop (loop, bbs[found], cond);
+ nloop = tree_unswitch_loop (loop, bbs[found], cond, cond_edge);
if (!nloop)
{
free_original_copy_tables ();
@@ -476,18 +569,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
static class loop *
tree_unswitch_loop (class loop *loop,
- basic_block unswitch_on, tree cond)
+ basic_block unswitch_on, tree cond, edge cond_edge)
{
profile_probability prob_true;
- edge edge_true, edge_false;
/* Some sanity checking. */
gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
- gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
gcc_assert (loop->inner == NULL);
- extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
- prob_true = edge_true->probability;
+ prob_true = cond_edge->probability;
return loop_version (loop, unshare_expr (cond),
NULL, prob_true,
prob_true.invert (),
@@ -965,6 +1055,42 @@ check_exit_phi (class loop *loop)
return true;
}
+/* Remove all dead cases from switches that are unswitched. */
+
+static void
+clean_up_switches (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ gimple *last = last_stmt (bb);
+ if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
+ {
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ unsigned index = 1;
+ for (unsigned i = 1; i < nlabels; ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e = find_edge (gimple_bb (stmt), dest);
+ if (e == NULL)
+ ; /* The edge is already removed. */
+ else if (e->flags & EDGE_IGNORE)
+ remove_edge (e);
+ else
+ {
+ gimple_switch_set_label (stmt, index, lab);
+ ++index;
+ }
+ }
+
+ if (index != nlabels)
+ gimple_switch_set_num_labels (stmt, index);
+ }
+ }
+}
+
/* Loop unswitching pass. */
namespace {
^ permalink raw reply [flat|nested] 5+ messages in thread
* [gcc(refs/users/marxin/heads/loop-unswitching-switch-v5)] Loop unswitching: support gswitch statements.
@ 2021-11-09 15:06 Martin Liska
0 siblings, 0 replies; 5+ messages in thread
From: Martin Liska @ 2021-11-09 15:06 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:cd14c58668623b3028764d9209fd6b5510939e29
commit cd14c58668623b3028764d9209fd6b5510939e29
Author: Martin Liska <mliska@suse.cz>
Date: Wed Sep 1 13:04:15 2021 +0200
Loop unswitching: support gswitch statements.
The patch extends the loop unswitching pass so that gswitch
statements are supported. The pass now uses ranger which marks
switch edges that are known to be unreachable in a versioned loop.
gcc/ChangeLog:
* tree-cfg.c (gimple_lv_add_condition_to_bb): Support non-gimple
expressions that needs to be gimplified.
* tree-ssa-loop-unswitch.c (tree_unswitch_loop): Add new
cond_edge argument.
(tree_may_unswitch_on): Support gswitch statements.
(clean_up_switches): New function.
(tree_ssa_unswitch_loops): Call clean_up_switches.
(tree_unswitch_single_loop): Change assumptions.
gcc/testsuite/ChangeLog:
* gcc.dg/loop-unswitch-6.c: New test.
* gcc.dg/loop-unswitch-7.c: New test.
* gcc.dg/loop-unswitch-8.c: New test.
* gcc.dg/loop-unswitch-9.c: New test.
* gcc.dg/loop-unswitch-10.c: New test.
* gcc.dg/loop-unswitch-11.c: New test.
Co-Authored-By: Richard Biener <rguenther@suse.de>
Diff:
---
gcc/testsuite/gcc.dg/loop-unswitch-10.c | 28 ++++
gcc/testsuite/gcc.dg/loop-unswitch-11.c | 60 +++++++
gcc/testsuite/gcc.dg/loop-unswitch-6.c | 56 +++++++
gcc/testsuite/gcc.dg/loop-unswitch-7.c | 45 ++++++
gcc/testsuite/gcc.dg/loop-unswitch-8.c | 28 ++++
gcc/testsuite/gcc.dg/loop-unswitch-9.c | 34 ++++
gcc/tree-cfg.c | 7 +-
gcc/tree-ssa-loop-unswitch.c | 272 ++++++++++++++++++++++++++------
8 files changed, 479 insertions(+), 51 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-10.c b/gcc/testsuite/gcc.dg/loop-unswitch-10.c
new file mode 100644
index 00000000000..747de272935
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-10.c
@@ -0,0 +1,28 @@
+/* { 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, float order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ if (order == 1.f)
+ tmp = -8 * a[i];
+ else
+ tmp = -4 * b[i];
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ if (order == 1.f)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1.0e" 1 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-11.c b/gcc/testsuite/gcc.dg/loop-unswitch-11.c
new file mode 100644
index 00000000000..30f4f347f7b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-11.c
@@ -0,0 +1,60 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+int
+__attribute__((noipa))
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp, tmp2;
+
+ if (order <= 0)
+ tmp = 123;
+
+ switch(order)
+ {
+ case 0:
+ tmp += -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 1:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 2:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 3:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+#define N 16 * 1024
+double aa[N], bb[N], cc[N], dd[N], rr[N];
+
+int main()
+{
+ for (int i = 0; i < 100 * 1000; i++)
+ foo (aa, bb, cc, dd, rr, N, i % 4);
+}
+
+
+/* Test that we actually unswitched something. */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* <= 0" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 0" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 2" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 3" 1 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-6.c b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
new file mode 100644
index 00000000000..315d6850877
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
@@ -0,0 +1,56 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+int
+__attribute__((noipa))
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp, tmp2;
+
+ switch(order)
+ {
+ case 0:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 1:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 2:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 3:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+#define N 16 * 1024
+double aa[N], bb[N], cc[N], dd[N], rr[N];
+
+int main()
+{
+ for (int i = 0; i < 100 * 1000; i++)
+ foo (aa, bb, cc, dd, rr, N, i % 4);
+}
+
+
+/* Test that we actually unswitched something. */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 0" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 2" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 3" 1 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-7.c b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
new file mode 100644
index 00000000000..efabd52886c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
@@ -0,0 +1,45 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+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, tmp2;
+
+ switch(order)
+ {
+ case 5 ... 6:
+ case 9:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 11:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 22:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 33:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order_.* >= 5 & order_.* <= 6 \\| order_.* == 9" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 2" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 3" 1 "unswitch" } } */
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..4cec1f53bcc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-8.c
@@ -0,0 +1,28 @@
+/* { 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
+ tmp = -4 * b[i];
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ if (order == 1)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "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..3058d4a5b38
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-9.c
@@ -0,0 +1,34 @@
+/* { 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, unsigned order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ switch (order)
+ {
+ case 0 ... 4:
+ tmp = -8 * a[i];
+ break;
+ default:
+ tmp = -4 * b[i];
+ break;
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ /* This should not be unswitched as it's mutually excluded with case 0 ... 4. */
+ if (order >= 5)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* <= 4" 1 "unswitch" } } */
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 8ed8c69b5b1..7db54f1cda2 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -9062,11 +9062,16 @@ gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
edge e0;
/* Build new conditional expr */
+ gsi = gsi_last_bb (cond_bb);
+
+ cond_expr = force_gimple_operand_gsi_1 (&gsi, cond_expr,
+ is_gimple_condexpr_for_cond,
+ NULL_TREE, false,
+ GSI_CONTINUE_LINKING);
new_cond_expr = gimple_build_cond_from_tree (cond_expr,
NULL_TREE, NULL_TREE);
/* Add new cond in cond_bb. */
- gsi = gsi_last_bb (cond_bb);
gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
/* Adjust edges appropriately to connect new head with first head
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index fe4dacc0833..bb4ff760166 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -37,6 +37,10 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "cfghooks.h"
#include "tree-ssa-loop-manip.h"
+#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
@@ -74,9 +78,10 @@ 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. */
-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 class loop *tree_unswitch_loop (class loop *, basic_block, tree, edge);
+static bool tree_unswitch_single_loop (class loop *, int, const auto_edge_flag &);
+static tree tree_may_unswitch_on (basic_block, class loop *, edge *,
+ const auto_edge_flag &);
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);
@@ -84,6 +89,7 @@ static bool used_outside_loop_p (class loop *, tree);
static void hoist_guard (class loop *, edge);
static bool check_exit_phi (class loop *);
static tree get_vop_from_header (class loop *);
+static void clean_up_switches (const auto_edge_flag &ignored_edge_flag);
/* Main entry point. Perform loop unswitching on all suitable loops. */
@@ -91,19 +97,23 @@ unsigned int
tree_ssa_unswitch_loops (void)
{
bool changed = false;
+ auto_edge_flag ignored_edge_flag (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);
+ changed |= tree_unswitch_single_loop (loop, 0, ignored_edge_flag);
else
changed |= tree_unswitch_outer_loop (loop);
}
if (changed)
- return TODO_cleanup_cfg;
+ {
+ clean_up_switches (ignored_edge_flag);
+ return TODO_cleanup_cfg;
+ }
return 0;
}
@@ -182,47 +192,115 @@ 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).
+ When a gswitch case is returned, fill up COND_EDGE for it. */
static tree
-tree_may_unswitch_on (basic_block bb, class loop *loop)
+tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge,
+ const auto_edge_flag &ignored_edge_flag)
{
gimple *last, *def;
- gcond *stmt;
- tree cond, use;
+ tree use;
basic_block def_bb;
ssa_op_iter iter;
/* BB must end in a simple conditional jump. */
last = last_stmt (bb);
- if (!last || gimple_code (last) != GIMPLE_COND)
- return NULL_TREE;
- stmt = as_a <gcond *> (last);
+ if (gcond *stmt = safe_dyn_cast <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;
- /* 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;
+ /* Condition must be invariant. */
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ {
+ def = SSA_NAME_DEF_STMT (use);
+ def_bb = gimple_bb (def);
+ if (def_bb
+ && flow_bb_inside_loop_p (loop, def_bb))
+ return NULL_TREE;
+ /* 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;
+ }
- /* Condition must be invariant. */
- FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ edge e1 = EDGE_SUCC (bb, 0);
+ edge e2 = EDGE_SUCC (bb, 1);
+ *cond_edge = e1->flags & EDGE_TRUE_VALUE ? e1 : e2;
+ return build2 (gimple_cond_code (stmt), boolean_type_node,
+ gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+ }
+ else if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
{
- def = SSA_NAME_DEF_STMT (use);
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ tree idx = gimple_switch_index (stmt);
+ if (TREE_CODE (idx) != SSA_NAME
+ || nlabels < 1)
+ return NULL_TREE;
+ /* Index must be invariant. */
+ def = SSA_NAME_DEF_STMT (idx);
def_bb = gimple_bb (def);
if (def_bb
&& flow_bb_inside_loop_p (loop, def_bb))
return NULL_TREE;
/* Unswitching on undefined values would introduce undefined
behavior that the original program might never exercise. */
- if (is_maybe_undefined (use, stmt, loop))
+ if (is_maybe_undefined (idx, stmt, loop))
return NULL_TREE;
- }
- cond = build2 (gimple_cond_code (stmt), boolean_type_node,
- gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
+ {
+ if (!(e->flags & ignored_edge_flag))
+ {
+ /* Build compound expression for all cases leading
+ to this edge. */
+ tree expr = NULL_TREE;
+ for (unsigned i = 1; i < gimple_switch_num_labels (stmt); ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e2 = find_edge (gimple_bb (stmt), dest);
+ if (e == e2)
+ {
+ tree cmp;
+ if (CASE_HIGH (lab) != NULL_TREE)
+ {
+ tree cmp1 = build2 (GE_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+ tree cmp2 = build2 (LE_EXPR, boolean_type_node, idx,
+ CASE_HIGH (lab));
+ cmp = build2 (BIT_AND_EXPR, boolean_type_node, cmp1,
+ cmp2);
+ }
+ else
+ cmp = build2 (EQ_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+
+ /* Combine the expression with the existing one. */
+ if (expr == NULL_TREE)
+ expr = cmp;
+ else
+ expr = build2 (BIT_IOR_EXPR, boolean_type_node, expr,
+ cmp);
+ }
+ }
- return cond;
+ if (expr != NULL_TREE)
+ {
+ *cond_edge = e;
+ return expr;
+ }
+ }
+ }
+ }
+
+ return NULL_TREE;
}
/* Simplifies COND using checks in front of the entry of the LOOP. Just very
@@ -263,12 +341,14 @@ simplify_using_entry_checks (class loop *loop, tree cond)
grow exponentially. */
static bool
-tree_unswitch_single_loop (class loop *loop, int num)
+tree_unswitch_single_loop (class loop *loop, int num,
+ const auto_edge_flag &ignored_edge_flag)
{
basic_block *bbs;
class loop *nloop;
unsigned i, found;
tree cond = NULL_TREE;
+ edge cond_edge = NULL;
gimple *stmt;
bool changed = false;
HOST_WIDE_INT iterations;
@@ -311,11 +391,13 @@ 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)))
+ if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge,
+ ignored_edge_flag)))
break;
if (i == loop->num_nodes)
@@ -333,24 +415,77 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- cond = simplify_using_entry_checks (loop, cond);
stmt = last_stmt (bbs[i]);
- if (integer_nonzerop (cond))
+ gcond *condition = dyn_cast<gcond *> (stmt);
+ gswitch *swtch = dyn_cast<gswitch *> (stmt);
+
+ if (condition != NULL)
{
- /* Remove false path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_true_node);
- changed = true;
+ tree result;
+ int_range_max r;
+
+ if (ranger.range_of_stmt (r, stmt) && r.singleton_p (&result))
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ result);
+ update_stmt (condition);
+ changed = true;
+ }
+ else
+ {
+ /* FIXME: Remove legacy code for floating point type that
+ is currently not supported by ranger. */
+ cond = simplify_using_entry_checks (loop, cond);
+ if (integer_nonzerop (cond))
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_true_node);
+ update_stmt (condition);
+ changed = true;
+ }
+ else if (integer_zerop (cond))
+ {
+ /* Remove true path. */
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_false_node);
+ update_stmt (condition);
+ changed = true;
+ }
+ }
}
- else if (integer_zerop (cond))
+ else if (swtch != NULL)
{
- /* Remove true path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_false_node);
- changed = true;
+ 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 |= ignored_edge_flag;
+ 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);
+ update_stmt (swtch);
+ }
}
+
/* Do not unswitch too much. */
- else if (num > param_max_unswitch_level)
+ if (num > param_max_unswitch_level)
{
i++;
continue;
@@ -371,7 +506,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- update_stmt (stmt);
i++;
}
@@ -435,7 +569,8 @@ 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 = tree_may_unswitch_on (bbs[found], loop, &cond_edge,
+ ignored_edge_flag)))
break;
if (found == loop->num_nodes)
@@ -446,11 +581,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
}
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ";; Unswitching loop\n");
+ {
+ fprintf (dump_file, ";; Unswitching loop with condition: ");
+ print_generic_expr (dump_file, cond);
+ fprintf (dump_file, "\n");
+ }
initialize_original_copy_tables ();
/* Unswitch the loop on this condition. */
- nloop = tree_unswitch_loop (loop, bbs[found], cond);
+ nloop = tree_unswitch_loop (loop, bbs[found], cond, cond_edge);
if (!nloop)
{
free_original_copy_tables ();
@@ -463,8 +602,8 @@ tree_unswitch_single_loop (class loop *loop, int num)
free_original_copy_tables ();
/* Invoke itself on modified loops. */
- tree_unswitch_single_loop (nloop, num + 1);
- tree_unswitch_single_loop (loop, num + 1);
+ tree_unswitch_single_loop (nloop, num + 1, ignored_edge_flag);
+ tree_unswitch_single_loop (loop, num + 1, ignored_edge_flag);
free (bbs);
return true;
}
@@ -476,18 +615,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
static class loop *
tree_unswitch_loop (class loop *loop,
- basic_block unswitch_on, tree cond)
+ basic_block unswitch_on, tree cond, edge cond_edge)
{
profile_probability prob_true;
- edge edge_true, edge_false;
/* Some sanity checking. */
gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
- gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
gcc_assert (loop->inner == NULL);
- extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
- prob_true = edge_true->probability;
+ prob_true = cond_edge->probability;
return loop_version (loop, unshare_expr (cond),
NULL, prob_true,
prob_true.invert (),
@@ -965,6 +1101,42 @@ check_exit_phi (class loop *loop)
return true;
}
+/* Remove all dead cases from switches that are unswitched. */
+
+static void
+clean_up_switches (const auto_edge_flag &ignored_edge_flag)
+{
+ basic_block bb;
+
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ gimple *last = last_stmt (bb);
+ if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
+ {
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ unsigned index = 1;
+ for (unsigned i = 1; i < nlabels; ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e = find_edge (gimple_bb (stmt), dest);
+ if (e == NULL)
+ ; /* The edge is already removed. */
+ else if (e->flags & ignored_edge_flag)
+ remove_edge (e);
+ else
+ {
+ gimple_switch_set_label (stmt, index, lab);
+ ++index;
+ }
+ }
+
+ if (index != nlabels)
+ gimple_switch_set_num_labels (stmt, index);
+ }
+ }
+}
+
/* Loop unswitching pass. */
namespace {
^ permalink raw reply [flat|nested] 5+ messages in thread
* [gcc(refs/users/marxin/heads/loop-unswitching-switch-v5)] Loop unswitching: support gswitch statements.
@ 2021-11-09 15:04 Martin Liska
0 siblings, 0 replies; 5+ messages in thread
From: Martin Liska @ 2021-11-09 15:04 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:94b11e43a9edf19f98f3abe90b8f227e3ee838a1
commit 94b11e43a9edf19f98f3abe90b8f227e3ee838a1
Author: Martin Liska <mliska@suse.cz>
Date: Wed Sep 1 13:04:15 2021 +0200
Loop unswitching: support gswitch statements.
The patch extends the loop unswitching pass so that gswitch
statements are supported. The pass now uses ranger which marks
switch edges that are known to be unreachable in a versioned loop.
gcc/ChangeLog:
* tree-cfg.c (gimple_lv_add_condition_to_bb): Support non-gimple
expressions that needs to be gimplified.
* tree-ssa-loop-unswitch.c (tree_unswitch_loop): Add new
cond_edge argument.
(tree_may_unswitch_on): Support gswitch statements.
(clean_up_switches): New function.
(tree_ssa_unswitch_loops): Call clean_up_switches.
(tree_unswitch_single_loop): Change assumptions.
gcc/testsuite/ChangeLog:
* gcc.dg/loop-unswitch-6.c: New test.
* gcc.dg/loop-unswitch-7.c: New test.
* gcc.dg/loop-unswitch-8.c: New test.
* gcc.dg/loop-unswitch-9.c: New test.
* gcc.dg/loop-unswitch-10.c: New test.
* gcc.dg/loop-unswitch-11.c: New test.
Co-Authored-By: Richard Biener <rguenther@suse.de>
Diff:
---
gcc/testsuite/gcc.dg/loop-unswitch-10.c | 28 ++++
gcc/testsuite/gcc.dg/loop-unswitch-11.c | 60 +++++++
gcc/testsuite/gcc.dg/loop-unswitch-6.c | 56 +++++++
gcc/testsuite/gcc.dg/loop-unswitch-7.c | 45 ++++++
gcc/testsuite/gcc.dg/loop-unswitch-8.c | 28 ++++
gcc/testsuite/gcc.dg/loop-unswitch-9.c | 34 ++++
gcc/tree-cfg.c | 7 +-
gcc/tree-ssa-loop-unswitch.c | 272 ++++++++++++++++++++++++++------
8 files changed, 479 insertions(+), 51 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-10.c b/gcc/testsuite/gcc.dg/loop-unswitch-10.c
new file mode 100644
index 00000000000..747de272935
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-10.c
@@ -0,0 +1,28 @@
+/* { 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, float order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ if (order == 1.f)
+ tmp = -8 * a[i];
+ else
+ tmp = -4 * b[i];
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ if (order == 1.f)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1.0e" 1 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-11.c b/gcc/testsuite/gcc.dg/loop-unswitch-11.c
new file mode 100644
index 00000000000..30f4f347f7b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-11.c
@@ -0,0 +1,60 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+int
+__attribute__((noipa))
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp, tmp2;
+
+ if (order <= 0)
+ tmp = 123;
+
+ switch(order)
+ {
+ case 0:
+ tmp += -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 1:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 2:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 3:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+#define N 16 * 1024
+double aa[N], bb[N], cc[N], dd[N], rr[N];
+
+int main()
+{
+ for (int i = 0; i < 100 * 1000; i++)
+ foo (aa, bb, cc, dd, rr, N, i % 4);
+}
+
+
+/* Test that we actually unswitched something. */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* <= 0" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 0" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 2" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 3" 1 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-6.c b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
new file mode 100644
index 00000000000..315d6850877
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
@@ -0,0 +1,56 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+int
+__attribute__((noipa))
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp, tmp2;
+
+ switch(order)
+ {
+ case 0:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 1:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 2:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 3:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+#define N 16 * 1024
+double aa[N], bb[N], cc[N], dd[N], rr[N];
+
+int main()
+{
+ for (int i = 0; i < 100 * 1000; i++)
+ foo (aa, bb, cc, dd, rr, N, i % 4);
+}
+
+
+/* Test that we actually unswitched something. */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 0" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 2" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 3" 1 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-7.c b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
new file mode 100644
index 00000000000..efabd52886c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
@@ -0,0 +1,45 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+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, tmp2;
+
+ switch(order)
+ {
+ case 5 ... 6:
+ case 9:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 11:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 22:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 33:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order_.* >= 5 & order_.* <= 6 \\| order_.* == 9" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 2" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 3" 1 "unswitch" } } */
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..4cec1f53bcc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-8.c
@@ -0,0 +1,28 @@
+/* { 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
+ tmp = -4 * b[i];
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ if (order == 1)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "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..3058d4a5b38
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-9.c
@@ -0,0 +1,34 @@
+/* { 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, unsigned order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ switch (order)
+ {
+ case 0 ... 4:
+ tmp = -8 * a[i];
+ break;
+ default:
+ tmp = -4 * b[i];
+ break;
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ /* This should not be unswitched as it's mutually excluded with case 0 ... 4. */
+ if (order >= 5)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* <= 4" 1 "unswitch" } } */
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 8ed8c69b5b1..7db54f1cda2 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -9062,11 +9062,16 @@ gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
edge e0;
/* Build new conditional expr */
+ gsi = gsi_last_bb (cond_bb);
+
+ cond_expr = force_gimple_operand_gsi_1 (&gsi, cond_expr,
+ is_gimple_condexpr_for_cond,
+ NULL_TREE, false,
+ GSI_CONTINUE_LINKING);
new_cond_expr = gimple_build_cond_from_tree (cond_expr,
NULL_TREE, NULL_TREE);
/* Add new cond in cond_bb. */
- gsi = gsi_last_bb (cond_bb);
gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
/* Adjust edges appropriately to connect new head with first head
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index fe4dacc0833..7d792e62a61 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -37,6 +37,10 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "cfghooks.h"
#include "tree-ssa-loop-manip.h"
+#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
@@ -74,9 +78,10 @@ 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. */
-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 class loop *tree_unswitch_loop (class loop *, basic_block, tree, edge);
+static bool tree_unswitch_single_loop (class loop *, int, auto_edge_flag);
+static tree tree_may_unswitch_on (basic_block, class loop *, edge *,
+ auto_edge_flag);
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);
@@ -84,6 +89,7 @@ static bool used_outside_loop_p (class loop *, tree);
static void hoist_guard (class loop *, edge);
static bool check_exit_phi (class loop *);
static tree get_vop_from_header (class loop *);
+static void clean_up_switches (auto_edge_flag ignored_edge_flag);
/* Main entry point. Perform loop unswitching on all suitable loops. */
@@ -91,19 +97,23 @@ unsigned int
tree_ssa_unswitch_loops (void)
{
bool changed = false;
+ auto_edge_flag ignored_edge_flag (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);
+ changed |= tree_unswitch_single_loop (loop, 0, ignored_edge_flag);
else
changed |= tree_unswitch_outer_loop (loop);
}
if (changed)
- return TODO_cleanup_cfg;
+ {
+ clean_up_switches (ignored_edge_flag);
+ return TODO_cleanup_cfg;
+ }
return 0;
}
@@ -182,47 +192,115 @@ 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).
+ When a gswitch case is returned, fill up COND_EDGE for it. */
static tree
-tree_may_unswitch_on (basic_block bb, class loop *loop)
+tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge,
+ auto_edge_flag ignored_edge_flag)
{
gimple *last, *def;
- gcond *stmt;
- tree cond, use;
+ tree use;
basic_block def_bb;
ssa_op_iter iter;
/* BB must end in a simple conditional jump. */
last = last_stmt (bb);
- if (!last || gimple_code (last) != GIMPLE_COND)
- return NULL_TREE;
- stmt = as_a <gcond *> (last);
+ if (gcond *stmt = safe_dyn_cast <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;
- /* 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;
+ /* Condition must be invariant. */
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ {
+ def = SSA_NAME_DEF_STMT (use);
+ def_bb = gimple_bb (def);
+ if (def_bb
+ && flow_bb_inside_loop_p (loop, def_bb))
+ return NULL_TREE;
+ /* 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;
+ }
- /* Condition must be invariant. */
- FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ edge e1 = EDGE_SUCC (bb, 0);
+ edge e2 = EDGE_SUCC (bb, 1);
+ *cond_edge = e1->flags & EDGE_TRUE_VALUE ? e1 : e2;
+ return build2 (gimple_cond_code (stmt), boolean_type_node,
+ gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+ }
+ else if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
{
- def = SSA_NAME_DEF_STMT (use);
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ tree idx = gimple_switch_index (stmt);
+ if (TREE_CODE (idx) != SSA_NAME
+ || nlabels < 1)
+ return NULL_TREE;
+ /* Index must be invariant. */
+ def = SSA_NAME_DEF_STMT (idx);
def_bb = gimple_bb (def);
if (def_bb
&& flow_bb_inside_loop_p (loop, def_bb))
return NULL_TREE;
/* Unswitching on undefined values would introduce undefined
behavior that the original program might never exercise. */
- if (is_maybe_undefined (use, stmt, loop))
+ if (is_maybe_undefined (idx, stmt, loop))
return NULL_TREE;
- }
- cond = build2 (gimple_cond_code (stmt), boolean_type_node,
- gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
+ {
+ if (!(e->flags & ignored_edge_flag))
+ {
+ /* Build compound expression for all cases leading
+ to this edge. */
+ tree expr = NULL_TREE;
+ for (unsigned i = 1; i < gimple_switch_num_labels (stmt); ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e2 = find_edge (gimple_bb (stmt), dest);
+ if (e == e2)
+ {
+ tree cmp;
+ if (CASE_HIGH (lab) != NULL_TREE)
+ {
+ tree cmp1 = build2 (GE_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+ tree cmp2 = build2 (LE_EXPR, boolean_type_node, idx,
+ CASE_HIGH (lab));
+ cmp = build2 (BIT_AND_EXPR, boolean_type_node, cmp1,
+ cmp2);
+ }
+ else
+ cmp = build2 (EQ_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+
+ /* Combine the expression with the existing one. */
+ if (expr == NULL_TREE)
+ expr = cmp;
+ else
+ expr = build2 (BIT_IOR_EXPR, boolean_type_node, expr,
+ cmp);
+ }
+ }
- return cond;
+ if (expr != NULL_TREE)
+ {
+ *cond_edge = e;
+ return expr;
+ }
+ }
+ }
+ }
+
+ return NULL_TREE;
}
/* Simplifies COND using checks in front of the entry of the LOOP. Just very
@@ -263,12 +341,14 @@ simplify_using_entry_checks (class loop *loop, tree cond)
grow exponentially. */
static bool
-tree_unswitch_single_loop (class loop *loop, int num)
+tree_unswitch_single_loop (class loop *loop, int num,
+ auto_edge_flag ignored_edge_flag)
{
basic_block *bbs;
class loop *nloop;
unsigned i, found;
tree cond = NULL_TREE;
+ edge cond_edge = NULL;
gimple *stmt;
bool changed = false;
HOST_WIDE_INT iterations;
@@ -311,11 +391,13 @@ 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)))
+ if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge,
+ ignored_edge_flag)))
break;
if (i == loop->num_nodes)
@@ -333,24 +415,77 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- cond = simplify_using_entry_checks (loop, cond);
stmt = last_stmt (bbs[i]);
- if (integer_nonzerop (cond))
+ gcond *condition = dyn_cast<gcond *> (stmt);
+ gswitch *swtch = dyn_cast<gswitch *> (stmt);
+
+ if (condition != NULL)
{
- /* Remove false path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_true_node);
- changed = true;
+ tree result;
+ int_range_max r;
+
+ if (ranger.range_of_stmt (r, stmt) && r.singleton_p (&result))
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ result);
+ update_stmt (condition);
+ changed = true;
+ }
+ else
+ {
+ /* FIXME: Remove legacy code for floating point type that
+ is currently not supported by ranger. */
+ cond = simplify_using_entry_checks (loop, cond);
+ if (integer_nonzerop (cond))
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_true_node);
+ update_stmt (condition);
+ changed = true;
+ }
+ else if (integer_zerop (cond))
+ {
+ /* Remove true path. */
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_false_node);
+ update_stmt (condition);
+ changed = true;
+ }
+ }
}
- else if (integer_zerop (cond))
+ else if (swtch != NULL)
{
- /* Remove true path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_false_node);
- changed = true;
+ 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 |= ignored_edge_flag;
+ 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);
+ update_stmt (swtch);
+ }
}
+
/* Do not unswitch too much. */
- else if (num > param_max_unswitch_level)
+ if (num > param_max_unswitch_level)
{
i++;
continue;
@@ -371,7 +506,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- update_stmt (stmt);
i++;
}
@@ -435,7 +569,8 @@ 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 = tree_may_unswitch_on (bbs[found], loop, &cond_edge,
+ ignored_edge_flag)))
break;
if (found == loop->num_nodes)
@@ -446,11 +581,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
}
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ";; Unswitching loop\n");
+ {
+ fprintf (dump_file, ";; Unswitching loop with condition: ");
+ print_generic_expr (dump_file, cond);
+ fprintf (dump_file, "\n");
+ }
initialize_original_copy_tables ();
/* Unswitch the loop on this condition. */
- nloop = tree_unswitch_loop (loop, bbs[found], cond);
+ nloop = tree_unswitch_loop (loop, bbs[found], cond, cond_edge);
if (!nloop)
{
free_original_copy_tables ();
@@ -463,8 +602,8 @@ tree_unswitch_single_loop (class loop *loop, int num)
free_original_copy_tables ();
/* Invoke itself on modified loops. */
- tree_unswitch_single_loop (nloop, num + 1);
- tree_unswitch_single_loop (loop, num + 1);
+ tree_unswitch_single_loop (nloop, num + 1, ignored_edge_flag);
+ tree_unswitch_single_loop (loop, num + 1, ignored_edge_flag);
free (bbs);
return true;
}
@@ -476,18 +615,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
static class loop *
tree_unswitch_loop (class loop *loop,
- basic_block unswitch_on, tree cond)
+ basic_block unswitch_on, tree cond, edge cond_edge)
{
profile_probability prob_true;
- edge edge_true, edge_false;
/* Some sanity checking. */
gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
- gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
gcc_assert (loop->inner == NULL);
- extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
- prob_true = edge_true->probability;
+ prob_true = cond_edge->probability;
return loop_version (loop, unshare_expr (cond),
NULL, prob_true,
prob_true.invert (),
@@ -965,6 +1101,42 @@ check_exit_phi (class loop *loop)
return true;
}
+/* Remove all dead cases from switches that are unswitched. */
+
+static void
+clean_up_switches (auto_edge_flag ignored_edge_flag)
+{
+ basic_block bb;
+
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ gimple *last = last_stmt (bb);
+ if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
+ {
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ unsigned index = 1;
+ for (unsigned i = 1; i < nlabels; ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e = find_edge (gimple_bb (stmt), dest);
+ if (e == NULL)
+ ; /* The edge is already removed. */
+ else if (e->flags & ignored_edge_flag)
+ remove_edge (e);
+ else
+ {
+ gimple_switch_set_label (stmt, index, lab);
+ ++index;
+ }
+ }
+
+ if (index != nlabels)
+ gimple_switch_set_num_labels (stmt, index);
+ }
+ }
+}
+
/* Loop unswitching pass. */
namespace {
^ permalink raw reply [flat|nested] 5+ messages in thread
* [gcc(refs/users/marxin/heads/loop-unswitching-switch-v5)] Loop unswitching: support gswitch statements.
@ 2021-11-09 10:06 Martin Liska
0 siblings, 0 replies; 5+ messages in thread
From: Martin Liska @ 2021-11-09 10:06 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:cf96b955f5a9a5e1ad7fcbeec892257ce3c8ebea
commit cf96b955f5a9a5e1ad7fcbeec892257ce3c8ebea
Author: Martin Liska <mliska@suse.cz>
Date: Wed Sep 1 13:04:15 2021 +0200
Loop unswitching: support gswitch statements.
The patch extends the loop unswitching pass so that gswitch
statements are supported. The pass now uses ranger which marks
switch edges that are known to be unreachable in a versioned loop.
gcc/ChangeLog:
* tree-cfg.c (gimple_lv_add_condition_to_bb): Support non-gimple
expressions that needs to be gimplified.
* tree-ssa-loop-unswitch.c (tree_unswitch_loop): Add new
cond_edge argument.
(tree_may_unswitch_on): Support gswitch statements.
(clean_up_switches): New function.
(tree_ssa_unswitch_loops): Call clean_up_switches.
(tree_unswitch_single_loop): Change assumptions.
gcc/testsuite/ChangeLog:
* gcc.dg/loop-unswitch-6.c: New test.
* gcc.dg/loop-unswitch-7.c: New test.
* gcc.dg/loop-unswitch-8.c: New test.
* gcc.dg/loop-unswitch-9.c: New test.
* gcc.dg/loop-unswitch-10.c: New test.
* gcc.dg/loop-unswitch-11.c: New test.
Co-Authored-By: Richard Biener <rguenther@suse.de>
Diff:
---
gcc/testsuite/gcc.dg/loop-unswitch-10.c | 28 ++++
gcc/testsuite/gcc.dg/loop-unswitch-11.c | 60 ++++++++
gcc/testsuite/gcc.dg/loop-unswitch-6.c | 56 +++++++
gcc/testsuite/gcc.dg/loop-unswitch-7.c | 45 ++++++
gcc/testsuite/gcc.dg/loop-unswitch-8.c | 28 ++++
gcc/testsuite/gcc.dg/loop-unswitch-9.c | 34 +++++
gcc/tree-cfg.c | 7 +-
gcc/tree-ssa-loop-unswitch.c | 256 ++++++++++++++++++++++++++------
8 files changed, 468 insertions(+), 46 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-10.c b/gcc/testsuite/gcc.dg/loop-unswitch-10.c
new file mode 100644
index 00000000000..747de272935
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-10.c
@@ -0,0 +1,28 @@
+/* { 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, float order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ if (order == 1.f)
+ tmp = -8 * a[i];
+ else
+ tmp = -4 * b[i];
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ if (order == 1.f)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1.0e" 1 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-11.c b/gcc/testsuite/gcc.dg/loop-unswitch-11.c
new file mode 100644
index 00000000000..30f4f347f7b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-11.c
@@ -0,0 +1,60 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+int
+__attribute__((noipa))
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp, tmp2;
+
+ if (order <= 0)
+ tmp = 123;
+
+ switch(order)
+ {
+ case 0:
+ tmp += -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 1:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 2:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 3:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+#define N 16 * 1024
+double aa[N], bb[N], cc[N], dd[N], rr[N];
+
+int main()
+{
+ for (int i = 0; i < 100 * 1000; i++)
+ foo (aa, bb, cc, dd, rr, N, i % 4);
+}
+
+
+/* Test that we actually unswitched something. */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* <= 0" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 0" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 2" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 3" 1 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-6.c b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
new file mode 100644
index 00000000000..315d6850877
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
@@ -0,0 +1,56 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+int
+__attribute__((noipa))
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp, tmp2;
+
+ switch(order)
+ {
+ case 0:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 1:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 2:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 3:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+#define N 16 * 1024
+double aa[N], bb[N], cc[N], dd[N], rr[N];
+
+int main()
+{
+ for (int i = 0; i < 100 * 1000; i++)
+ foo (aa, bb, cc, dd, rr, N, i % 4);
+}
+
+
+/* Test that we actually unswitched something. */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 0" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 2" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 3" 1 "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-7.c b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
new file mode 100644
index 00000000000..efabd52886c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
@@ -0,0 +1,45 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+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, tmp2;
+
+ switch(order)
+ {
+ case 5 ... 6:
+ case 9:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 11:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 22:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 33:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order_.* >= 5 & order_.* <= 6 \\| order_.* == 9" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 2" 1 "unswitch" } } */
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 3" 1 "unswitch" } } */
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..4cec1f53bcc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-8.c
@@ -0,0 +1,28 @@
+/* { 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
+ tmp = -4 * b[i];
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ if (order == 1)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "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..3058d4a5b38
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-9.c
@@ -0,0 +1,34 @@
+/* { 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, unsigned order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ switch (order)
+ {
+ case 0 ... 4:
+ tmp = -8 * a[i];
+ break;
+ default:
+ tmp = -4 * b[i];
+ break;
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ /* This should not be unswitched as it's mutually excluded with case 0 ... 4. */
+ if (order >= 5)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* <= 4" 1 "unswitch" } } */
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 8ed8c69b5b1..7db54f1cda2 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -9062,11 +9062,16 @@ gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
edge e0;
/* Build new conditional expr */
+ gsi = gsi_last_bb (cond_bb);
+
+ cond_expr = force_gimple_operand_gsi_1 (&gsi, cond_expr,
+ is_gimple_condexpr_for_cond,
+ NULL_TREE, false,
+ GSI_CONTINUE_LINKING);
new_cond_expr = gimple_build_cond_from_tree (cond_expr,
NULL_TREE, NULL_TREE);
/* Add new cond in cond_bb. */
- gsi = gsi_last_bb (cond_bb);
gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
/* Adjust edges appropriately to connect new head with first head
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index fe4dacc0833..45d53f5a6da 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -37,6 +37,10 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "cfghooks.h"
#include "tree-ssa-loop-manip.h"
+#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
@@ -74,9 +78,9 @@ 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. */
-static class loop *tree_unswitch_loop (class loop *, basic_block, tree);
+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 *);
+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);
@@ -84,6 +88,7 @@ static bool used_outside_loop_p (class loop *, tree);
static void hoist_guard (class loop *, edge);
static bool check_exit_phi (class loop *);
static tree get_vop_from_header (class loop *);
+static void clean_up_switches (void);
/* Main entry point. Perform loop unswitching on all suitable loops. */
@@ -103,7 +108,10 @@ tree_ssa_unswitch_loops (void)
}
if (changed)
- return TODO_cleanup_cfg;
+ {
+ clean_up_switches ();
+ return TODO_cleanup_cfg;
+ }
return 0;
}
@@ -182,47 +190,114 @@ 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).
+ When a gswitch case is returned, fill up COND_EDGE for it. */
static tree
-tree_may_unswitch_on (basic_block bb, class loop *loop)
+tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge)
{
gimple *last, *def;
- gcond *stmt;
- tree cond, use;
+ tree use;
basic_block def_bb;
ssa_op_iter iter;
/* BB must end in a simple conditional jump. */
last = last_stmt (bb);
- if (!last || gimple_code (last) != GIMPLE_COND)
- return NULL_TREE;
- stmt = as_a <gcond *> (last);
+ if (gcond *stmt = safe_dyn_cast <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;
- /* 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;
+ /* Condition must be invariant. */
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ {
+ def = SSA_NAME_DEF_STMT (use);
+ def_bb = gimple_bb (def);
+ if (def_bb
+ && flow_bb_inside_loop_p (loop, def_bb))
+ return NULL_TREE;
+ /* 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;
+ }
- /* Condition must be invariant. */
- FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ edge e1 = EDGE_SUCC (bb, 0);
+ edge e2 = EDGE_SUCC (bb, 1);
+ *cond_edge = e1->flags & EDGE_TRUE_VALUE ? e1 : e2;
+ return build2 (gimple_cond_code (stmt), boolean_type_node,
+ gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+ }
+ else if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
{
- def = SSA_NAME_DEF_STMT (use);
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ tree idx = gimple_switch_index (stmt);
+ if (TREE_CODE (idx) != SSA_NAME
+ || nlabels < 1)
+ return NULL_TREE;
+ /* Index must be invariant. */
+ def = SSA_NAME_DEF_STMT (idx);
def_bb = gimple_bb (def);
if (def_bb
&& flow_bb_inside_loop_p (loop, def_bb))
return NULL_TREE;
/* Unswitching on undefined values would introduce undefined
behavior that the original program might never exercise. */
- if (is_maybe_undefined (use, stmt, loop))
+ if (is_maybe_undefined (idx, stmt, loop))
return NULL_TREE;
- }
- cond = build2 (gimple_cond_code (stmt), boolean_type_node,
- gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
+ {
+ if (!(e->flags & EDGE_IGNORE))
+ {
+ /* Build compound expression for all cases leading
+ to this edge. */
+ tree expr = NULL_TREE;
+ for (unsigned i = 1; i < gimple_switch_num_labels (stmt); ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e2 = find_edge (gimple_bb (stmt), dest);
+ if (e == e2)
+ {
+ tree cmp;
+ if (CASE_HIGH (lab) != NULL_TREE)
+ {
+ tree cmp1 = build2 (GE_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+ tree cmp2 = build2 (LE_EXPR, boolean_type_node, idx,
+ CASE_HIGH (lab));
+ cmp = build2 (BIT_AND_EXPR, boolean_type_node, cmp1,
+ cmp2);
+ }
+ else
+ cmp = build2 (EQ_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+
+ /* Combine the expression with the existing one. */
+ if (expr == NULL_TREE)
+ expr = cmp;
+ else
+ expr = build2 (BIT_IOR_EXPR, boolean_type_node, expr,
+ cmp);
+ }
+ }
- return cond;
+ if (expr != NULL_TREE)
+ {
+ *cond_edge = e;
+ return expr;
+ }
+ }
+ }
+ }
+
+ return NULL_TREE;
}
/* Simplifies COND using checks in front of the entry of the LOOP. Just very
@@ -269,6 +344,7 @@ tree_unswitch_single_loop (class loop *loop, int num)
class loop *nloop;
unsigned i, found;
tree cond = NULL_TREE;
+ edge cond_edge = NULL;
gimple *stmt;
bool changed = false;
HOST_WIDE_INT iterations;
@@ -311,11 +387,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)))
+ if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge)))
break;
if (i == loop->num_nodes)
@@ -333,24 +410,77 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- cond = simplify_using_entry_checks (loop, cond);
stmt = last_stmt (bbs[i]);
- if (integer_nonzerop (cond))
+ gcond *condition = dyn_cast<gcond *> (stmt);
+ gswitch *swtch = dyn_cast<gswitch *> (stmt);
+
+ if (condition != NULL)
{
- /* Remove false path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_true_node);
- changed = true;
+ tree result;
+ int_range_max r;
+
+ if (ranger.range_of_stmt (r, stmt) && r.singleton_p (&result))
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ result);
+ update_stmt (condition);
+ changed = true;
+ }
+ else
+ {
+ /* FIXME: Remove legacy code for floating point type that
+ is currently not supported by ranger. */
+ cond = simplify_using_entry_checks (loop, cond);
+ if (integer_nonzerop (cond))
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_true_node);
+ update_stmt (condition);
+ changed = true;
+ }
+ else if (integer_zerop (cond))
+ {
+ /* Remove true path. */
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_false_node);
+ update_stmt (condition);
+ changed = true;
+ }
+ }
}
- else if (integer_zerop (cond))
+ else if (swtch != NULL)
{
- /* Remove true path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_false_node);
- changed = true;
+ 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);
+ update_stmt (swtch);
+ }
}
+
/* Do not unswitch too much. */
- else if (num > param_max_unswitch_level)
+ if (num > param_max_unswitch_level)
{
i++;
continue;
@@ -371,7 +501,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- update_stmt (stmt);
i++;
}
@@ -435,7 +564,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 = tree_may_unswitch_on (bbs[found], loop, &cond_edge)))
break;
if (found == loop->num_nodes)
@@ -446,11 +575,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
}
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ";; Unswitching loop\n");
+ {
+ fprintf (dump_file, ";; Unswitching loop with condition: ");
+ print_generic_expr (dump_file, cond);
+ fprintf (dump_file, "\n");
+ }
initialize_original_copy_tables ();
/* Unswitch the loop on this condition. */
- nloop = tree_unswitch_loop (loop, bbs[found], cond);
+ nloop = tree_unswitch_loop (loop, bbs[found], cond, cond_edge);
if (!nloop)
{
free_original_copy_tables ();
@@ -476,18 +609,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
static class loop *
tree_unswitch_loop (class loop *loop,
- basic_block unswitch_on, tree cond)
+ basic_block unswitch_on, tree cond, edge cond_edge)
{
profile_probability prob_true;
- edge edge_true, edge_false;
/* Some sanity checking. */
gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
- gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
gcc_assert (loop->inner == NULL);
- extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
- prob_true = edge_true->probability;
+ prob_true = cond_edge->probability;
return loop_version (loop, unshare_expr (cond),
NULL, prob_true,
prob_true.invert (),
@@ -965,6 +1095,42 @@ check_exit_phi (class loop *loop)
return true;
}
+/* Remove all dead cases from switches that are unswitched. */
+
+static void
+clean_up_switches (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ gimple *last = last_stmt (bb);
+ if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
+ {
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ unsigned index = 1;
+ for (unsigned i = 1; i < nlabels; ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e = find_edge (gimple_bb (stmt), dest);
+ if (e == NULL)
+ ; /* The edge is already removed. */
+ else if (e->flags & EDGE_IGNORE)
+ remove_edge (e);
+ else
+ {
+ gimple_switch_set_label (stmt, index, lab);
+ ++index;
+ }
+ }
+
+ if (index != nlabels)
+ gimple_switch_set_num_labels (stmt, index);
+ }
+ }
+}
+
/* Loop unswitching pass. */
namespace {
^ permalink raw reply [flat|nested] 5+ messages in thread
* [gcc(refs/users/marxin/heads/loop-unswitching-switch-v5)] Loop unswitching: support gswitch statements.
@ 2021-11-08 15:30 Martin Liska
0 siblings, 0 replies; 5+ messages in thread
From: Martin Liska @ 2021-11-08 15:30 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:0e261ebb4bc81f30a37195b69e8b39572aba8c35
commit 0e261ebb4bc81f30a37195b69e8b39572aba8c35
Author: Martin Liska <mliska@suse.cz>
Date: Wed Sep 1 13:04:15 2021 +0200
Loop unswitching: support gswitch statements.
The patch extends the loop unswitching pass so that gswitch
statements are supported. The pass now uses ranger which marks
switch edges that are known to be unreachable in a versioned loop.
gcc/ChangeLog:
* tree-cfg.c (gimple_lv_add_condition_to_bb): Support non-gimple
expressions that needs to be gimplified.
* tree-ssa-loop-unswitch.c (tree_unswitch_loop): Add new
cond_edge parameter.
(tree_may_unswitch_on): Support gswitch statements.
(clean_up_switches): New function.
(tree_ssa_unswitch_loops): Call clean_up_switches.
(simplify_using_entry_checks): Removed and replaced with ranger.
(tree_unswitch_single_loop): Change assumptions.
gcc/testsuite/ChangeLog:
* gcc.dg/loop-unswitch-6.c: New test.
* gcc.dg/loop-unswitch-7.c: New test.
* gcc.dg/loop-unswitch-8.c: New test.
* gcc.dg/loop-unswitch-9.c: New test.
Co-Authored-By: Richard Biener <rguenther@suse.de>
Diff:
---
gcc/testsuite/gcc.dg/loop-unswitch-6.c | 56 +++++++
gcc/testsuite/gcc.dg/loop-unswitch-7.c | 45 ++++++
gcc/testsuite/gcc.dg/loop-unswitch-8.c | 28 ++++
gcc/testsuite/gcc.dg/loop-unswitch-9.c | 34 ++++
gcc/tree-cfg.c | 7 +-
gcc/tree-ssa-loop-unswitch.c | 284 ++++++++++++++++++++++++---------
6 files changed, 374 insertions(+), 80 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-6.c b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
new file mode 100644
index 00000000000..8a022e0f200
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-6.c
@@ -0,0 +1,56 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+int
+__attribute__((noipa))
+foo(double *a, double *b, double *c, double *d, double *r, int size, int order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp, tmp2;
+
+ switch(order)
+ {
+ case 0:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 1:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 2:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 3:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+#define N 16 * 1024
+double aa[N], bb[N], cc[N], dd[N], rr[N];
+
+int main()
+{
+ for (int i = 0; i < 100 * 1000; i++)
+ foo (aa, bb, cc, dd, rr, N, i % 4);
+}
+
+
+/* Test that we actually unswitched something. */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 0" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 1" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 2" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 3" "unswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-7.c b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
new file mode 100644
index 00000000000..00f2fcff64b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-7.c
@@ -0,0 +1,45 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details --param=max-unswitch-insns=1000 --param=max-unswitch-level=10" } */
+
+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, tmp2;
+
+ switch(order)
+ {
+ case 5 ... 6:
+ case 9:
+ tmp = -8 * a[i];
+ tmp2 = 2 * b[i];
+ break;
+ case 11:
+ tmp = 3 * a[i] - 2 * b[i];
+ tmp2 = 5 * b[i] - 2 * c[i];
+ break;
+ case 22:
+ tmp = 9 * a[i] + 2 * b[i] + c[i];
+ tmp2 = 4 * b[i] + 2 * c[i] + 8 * d[i];
+ break;
+ case 33:
+ tmp = 3 * a[i] + 2 * b[i] - c[i];
+ tmp2 = b[i] - 2 * c[i] + 8 * d[i];
+ break;
+ defaut:
+ __builtin_unreachable ();
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+ double y = 3.4f * tmp + d[i] + tmp2;
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order_.* >= 5 & order_.* <= 6 | order_.* == 9" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 1" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 2" "unswitch" } } */
+/* { dg-final { scan-tree-dump ";; Unswitching loop with condition: order.* == 3" "unswitch" } } */
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..4cec1f53bcc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-8.c
@@ -0,0 +1,28 @@
+/* { 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
+ tmp = -4 * b[i];
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ if (order == 1)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* == 1" 1 "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..3058d4a5b38
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/loop-unswitch-9.c
@@ -0,0 +1,34 @@
+/* { 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, unsigned order)
+{
+ for (int i = 0; i < size; i++)
+ {
+ double tmp;
+
+ switch (order)
+ {
+ case 0 ... 4:
+ tmp = -8 * a[i];
+ break;
+ default:
+ tmp = -4 * b[i];
+ break;
+ }
+
+ double x = 3 * tmp + d[i] + tmp;
+
+ /* This should not be unswitched as it's mutually excluded with case 0 ... 4. */
+ if (order >= 5)
+ x += 2;
+
+ double y = 3.4f * tmp + d[i];
+ r[i] = x + y;
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times ";; Unswitching loop with condition: order.* <= 4" 1 "unswitch" } } */
diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c
index 8ed8c69b5b1..7db54f1cda2 100644
--- a/gcc/tree-cfg.c
+++ b/gcc/tree-cfg.c
@@ -9062,11 +9062,16 @@ gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
edge e0;
/* Build new conditional expr */
+ gsi = gsi_last_bb (cond_bb);
+
+ cond_expr = force_gimple_operand_gsi_1 (&gsi, cond_expr,
+ is_gimple_condexpr_for_cond,
+ NULL_TREE, false,
+ GSI_CONTINUE_LINKING);
new_cond_expr = gimple_build_cond_from_tree (cond_expr,
NULL_TREE, NULL_TREE);
/* Add new cond in cond_bb. */
- gsi = gsi_last_bb (cond_bb);
gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
/* Adjust edges appropriately to connect new head with first head
diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c
index fe4dacc0833..a509938c7d0 100644
--- a/gcc/tree-ssa-loop-unswitch.c
+++ b/gcc/tree-ssa-loop-unswitch.c
@@ -37,6 +37,10 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "cfghooks.h"
#include "tree-ssa-loop-manip.h"
+#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
@@ -74,9 +78,9 @@ 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. */
-static class loop *tree_unswitch_loop (class loop *, basic_block, tree);
+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 *);
+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);
@@ -84,6 +88,7 @@ static bool used_outside_loop_p (class loop *, tree);
static void hoist_guard (class loop *, edge);
static bool check_exit_phi (class loop *);
static tree get_vop_from_header (class loop *);
+static void clean_up_switches (void);
/* Main entry point. Perform loop unswitching on all suitable loops. */
@@ -103,7 +108,10 @@ tree_ssa_unswitch_loops (void)
}
if (changed)
- return TODO_cleanup_cfg;
+ {
+ clean_up_switches ();
+ return TODO_cleanup_cfg;
+ }
return 0;
}
@@ -182,80 +190,114 @@ 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).
+ When a gswitch case is returned, fill up COND_EDGE for it. */
static tree
-tree_may_unswitch_on (basic_block bb, class loop *loop)
+tree_may_unswitch_on (basic_block bb, class loop *loop, edge *cond_edge)
{
gimple *last, *def;
- gcond *stmt;
- tree cond, use;
+ tree use;
basic_block def_bb;
ssa_op_iter iter;
/* BB must end in a simple conditional jump. */
last = last_stmt (bb);
- if (!last || gimple_code (last) != GIMPLE_COND)
- return NULL_TREE;
- 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;
-
- /* Condition must be invariant. */
- FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ if (gcond *stmt = safe_dyn_cast <gcond *> (last))
{
- def = SSA_NAME_DEF_STMT (use);
+ /* 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;
+
+ /* Condition must be invariant. */
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ {
+ def = SSA_NAME_DEF_STMT (use);
+ def_bb = gimple_bb (def);
+ if (def_bb
+ && flow_bb_inside_loop_p (loop, def_bb))
+ return NULL_TREE;
+ /* 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;
+ }
+
+ edge e1 = EDGE_SUCC (bb, 0);
+ edge e2 = EDGE_SUCC (bb, 1);
+ *cond_edge = e1->flags & EDGE_TRUE_VALUE ? e1 : e2;
+ return build2 (gimple_cond_code (stmt), boolean_type_node,
+ gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+ }
+ else if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
+ {
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ tree idx = gimple_switch_index (stmt);
+ if (TREE_CODE (idx) != SSA_NAME
+ || nlabels < 1)
+ return NULL_TREE;
+ /* Index must be invariant. */
+ def = SSA_NAME_DEF_STMT (idx);
def_bb = gimple_bb (def);
if (def_bb
&& flow_bb_inside_loop_p (loop, def_bb))
return NULL_TREE;
/* Unswitching on undefined values would introduce undefined
behavior that the original program might never exercise. */
- if (is_maybe_undefined (use, stmt, loop))
+ if (is_maybe_undefined (idx, stmt, loop))
return NULL_TREE;
- }
-
- cond = build2 (gimple_cond_code (stmt), boolean_type_node,
- gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
- return cond;
-}
-
-/* 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 tree
-simplify_using_entry_checks (class loop *loop, tree cond)
-{
- edge e = loop_preheader_edge (loop);
- gimple *stmt;
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
+ {
+ if (!(e->flags & EDGE_IGNORE))
+ {
+ /* Build compound expression for all cases leading
+ to this edge. */
+ tree expr = NULL_TREE;
+ for (unsigned i = 1; i < gimple_switch_num_labels (stmt); ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e2 = find_edge (gimple_bb (stmt), dest);
+ if (e == e2)
+ {
+ tree cmp;
+ if (CASE_HIGH (lab) != NULL_TREE)
+ {
+ tree cmp1 = build2 (GE_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+ tree cmp2 = build2 (LE_EXPR, boolean_type_node, idx,
+ CASE_HIGH (lab));
+ cmp = build2 (BIT_AND_EXPR, boolean_type_node, cmp1,
+ cmp2);
+ }
+ else
+ cmp = build2 (EQ_EXPR, boolean_type_node, idx,
+ CASE_LOW (lab));
+
+ /* Combine the expression with the existing one. */
+ if (expr == NULL_TREE)
+ expr = cmp;
+ else
+ expr = build2 (BIT_IOR_EXPR, boolean_type_node, expr,
+ cmp);
+ }
+ }
- while (1)
- {
- 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)
- && operand_equal_p (gimple_cond_rhs (stmt),
- TREE_OPERAND (cond, 1), 0))
- return (e->flags & EDGE_TRUE_VALUE
- ? boolean_true_node
- : boolean_false_node);
-
- if (!single_pred_p (e->src))
- return cond;
-
- e = single_pred_edge (e->src);
- if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
- return cond;
+ if (expr != NULL_TREE)
+ {
+ *cond_edge = e;
+ return expr;
+ }
+ }
+ }
}
+
+ return NULL_TREE;
}
/* Unswitch single LOOP. NUM is number of unswitchings done; we do not allow
@@ -269,6 +311,7 @@ tree_unswitch_single_loop (class loop *loop, int num)
class loop *nloop;
unsigned i, found;
tree cond = NULL_TREE;
+ edge cond_edge = NULL;
gimple *stmt;
bool changed = false;
HOST_WIDE_INT iterations;
@@ -311,11 +354,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)))
+ if ((cond = tree_may_unswitch_on (bbs[i], loop, &cond_edge)))
break;
if (i == loop->num_nodes)
@@ -333,24 +377,70 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- cond = simplify_using_entry_checks (loop, cond);
stmt = last_stmt (bbs[i]);
- if (integer_nonzerop (cond))
+ gcond *condition = dyn_cast<gcond *> (stmt);
+ gswitch *swtch = dyn_cast<gswitch *> (stmt);
+
+ if (condition != NULL)
{
- /* Remove false path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_true_node);
- changed = true;
+ int_range_max r;
+ edge edge_true, edge_false;
+ extract_true_false_edges_from_block (bbs[i], &edge_true, &edge_false);
+ tree cond = gimple_cond_lhs (stmt);
+
+ if (r.supports_type_p (TREE_TYPE (cond)))
+ {
+ if (ranger.range_on_edge (r, edge_true, cond)
+ && r.undefined_p ())
+ {
+ gimple_cond_set_condition_from_tree (condition,
+ boolean_false_node);
+ update_stmt (condition);
+ 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);
+ update_stmt (condition);
+ changed = true;
+ }
+ }
}
- else if (integer_zerop (cond))
+ else if (swtch != NULL)
{
- /* Remove true path. */
- gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
- boolean_false_node);
- changed = true;
+ 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);
+ update_stmt (swtch);
+ }
}
+
/* Do not unswitch too much. */
- else if (num > param_max_unswitch_level)
+ if (num > param_max_unswitch_level)
{
i++;
continue;
@@ -371,7 +461,6 @@ tree_unswitch_single_loop (class loop *loop, int num)
break;
}
- update_stmt (stmt);
i++;
}
@@ -435,7 +524,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 = tree_may_unswitch_on (bbs[found], loop, &cond_edge)))
break;
if (found == loop->num_nodes)
@@ -446,11 +535,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
}
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, ";; Unswitching loop\n");
+ {
+ fprintf (dump_file, ";; Unswitching loop with condition: ");
+ print_generic_expr (dump_file, cond);
+ fprintf (dump_file, "\n");
+ }
initialize_original_copy_tables ();
/* Unswitch the loop on this condition. */
- nloop = tree_unswitch_loop (loop, bbs[found], cond);
+ nloop = tree_unswitch_loop (loop, bbs[found], cond, cond_edge);
if (!nloop)
{
free_original_copy_tables ();
@@ -476,18 +569,15 @@ tree_unswitch_single_loop (class loop *loop, int num)
static class loop *
tree_unswitch_loop (class loop *loop,
- basic_block unswitch_on, tree cond)
+ basic_block unswitch_on, tree cond, edge cond_edge)
{
profile_probability prob_true;
- edge edge_true, edge_false;
/* Some sanity checking. */
gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
- gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
gcc_assert (loop->inner == NULL);
- extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
- prob_true = edge_true->probability;
+ prob_true = cond_edge->probability;
return loop_version (loop, unshare_expr (cond),
NULL, prob_true,
prob_true.invert (),
@@ -965,6 +1055,42 @@ check_exit_phi (class loop *loop)
return true;
}
+/* Remove all dead cases from switches that are unswitched. */
+
+static void
+clean_up_switches (void)
+{
+ basic_block bb;
+
+ FOR_EACH_BB_FN (bb, cfun)
+ {
+ gimple *last = last_stmt (bb);
+ if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
+ {
+ unsigned nlabels = gimple_switch_num_labels (stmt);
+ unsigned index = 1;
+ for (unsigned i = 1; i < nlabels; ++i)
+ {
+ tree lab = gimple_switch_label (stmt, i);
+ basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
+ edge e = find_edge (gimple_bb (stmt), dest);
+ if (e == NULL)
+ ; /* The edge is already removed. */
+ else if (e->flags & EDGE_IGNORE)
+ remove_edge (e);
+ else
+ {
+ gimple_switch_set_label (stmt, index, lab);
+ ++index;
+ }
+ }
+
+ if (index != nlabels)
+ gimple_switch_set_num_labels (stmt, index);
+ }
+ }
+}
+
/* Loop unswitching pass. */
namespace {
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2021-11-09 15:06 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-11-08 15:36 [gcc(refs/users/marxin/heads/loop-unswitching-switch-v5)] Loop unswitching: support gswitch statements Martin Liska
-- strict thread matches above, loose matches on Subject: below --
2021-11-09 15:06 Martin Liska
2021-11-09 15:04 Martin Liska
2021-11-09 10:06 Martin Liska
2021-11-08 15:30 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).