On 2021-06-21 14:19, guojiufu via Gcc-patches wrote:
On 2021-06-09 19:18, guojiufu wrote:On 2021-06-09 17:42, guojiufu via Gcc-patches wrote:On 2021-06-08 18:13, Richard Biener wrote:On Fri, 4 Jun 2021, Jiufu Guo wrote:cut...cut...
Besides the method in the previous mails,
I’m thinking of another way to split loops:
foo (int *a, int *b, unsigned k, unsigned n)
{
while (++k != n)
a[k] = b[k] + 1;
}
We may split it into:
if (k<n)
{
while (++k < n) //loop1
a[k] = b[k] + 1;
}
else
{
while (++k != n) //loop2
a[k] = b[k] + 1;
}
In most cases, loop1 would be hit, the overhead of this method is only
checking “if (k<n)”
which would be smaller than the previous method. And this method would be more easy to extend to nest loops like: unsigned int l_n = 0; unsigned int l_m = 0; unsigned int l_k = 0; for (l_n = 0; l_n != n; l_n++) for (l_k = 0; l_k != k; l_k++) for (l_m = 0; l_m != m; l_m++) xxx; Do you think this method is more valuable to implement? Below is a quick patch. This patch does not support nest loops yet. diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c index 3a09bbc39e5..c9d161565e4 100644 --- a/gcc/tree-ssa-loop-split.c +++ b/gcc/tree-ssa-loop-split.c @@ -41,6 +41,7 @@ along with GCC; see the file COPYING3. If not see #include "cfghooks.h" #include "gimple-fold.h" #include "gimplify-me.h" +#include "tree-ssa-loop-ivopts.h" /* This file implements two kinds of loop splitting. @@ -1593,6 +1594,468 @@ split_loop_on_cond (struct loop *loop) return do_split; } +/* Filter out type conversions on IDX. + Store the shortest type during conversion to SMALL_TYPE. + Store the longest type during conversion to LARGE_TYPE. */ + +static gimple *+filter_conversions (class loop *loop, tree idx, tree *small_type = NULL,
+ tree *large_type = NULL)
+{
+ gcc_assert (TREE_CODE (idx) == SSA_NAME);
+ gimple *stmt = SSA_NAME_DEF_STMT (idx);
+ while (is_gimple_assign (stmt)
+ && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
+ {
+ if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt)))
+ {
+ idx = gimple_assign_rhs1 (stmt);
+ if (small_type)
+ {
+ tree type = TREE_TYPE (idx);
+ if (TYPE_PRECISION (*small_type) > TYPE_PRECISION (type)
+ || (TYPE_PRECISION (*small_type) == TYPE_PRECISION (type)
+ && TYPE_UNSIGNED (*small_type) && !TYPE_UNSIGNED (type)))
+ *small_type = type;
+ }
+ if (large_type)
+ {
+ tree type = TREE_TYPE (idx);
+ if (TYPE_PRECISION (*large_type) < TYPE_PRECISION (type)
+ || (TYPE_PRECISION (*large_type) == TYPE_PRECISION (type)
+ && !TYPE_UNSIGNED (*large_type) && TYPE_UNSIGNED (type)))
+ *large_type = type;
+ }
+ }
+ else
+ break;
+
+ if (TREE_CODE (idx) != SSA_NAME)
+ break;
+ stmt = SSA_NAME_DEF_STMT (idx);
+ }
+ return stmt;
+}
+
+/* Collection of loop index related elements. */
+struct idx_elements
+{
+ gcond *gc;
+ gphi *phi;
+ gimple *inc_stmt;
+ tree idx;
+ tree bnd;
+ tree step;
+ tree large_type;
+ tree small_type;
+ bool cmp_on_next;
+};
+
+/* Analyze and get the idx related elements: bnd,
+ phi, increase stmt from exit edge E, etc.
+
+ i = phi (b, n)
+ ...
+ n0 = ik + 1
+ n1 = (type)n0
+ ...
+ if (i != bnd) or if (n != bnd)
+ ...
+ n = ()nl
+
+ IDX is the i' or n'. */
+
+bool
+analyze_idx_elements (class loop *loop, edge e, idx_elements &data)
+{
+ /* Avoid complicated edge. */
+ if (e->flags & EDGE_FAKE)
+ return false;
+ if (e->src != loop->header && e->src != single_pred (loop->latch))
+ return false;
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->src))
+ return false;
+
+ /* Check gcond. */
+ gimple *last = last_stmt (e->src);
+ if (!last || gimple_code (last) != GIMPLE_COND)
+ return false;
+
+ /* Get idx and bnd from gcond. */
+ gcond *gc = as_a<gcond *> (last);
+ tree bnd = gimple_cond_rhs (gc);
+ tree idx = gimple_cond_lhs (gc);
+ if (expr_invariant_in_loop_p (loop, idx))
+ std::swap (idx, bnd);
+ else if (!expr_invariant_in_loop_p (loop, bnd))
+ return false;
+ if (TREE_CODE (idx) != SSA_NAME)
+ return false;
+
+ gimple *inc_stmt = NULL;
+ bool cmp_next = false;
+ tree small_type = TREE_TYPE (idx);
+ tree large_type = small_type;
+ gimple *stmt = filter_conversions (loop, idx, &small_type,
&large_type);
+ /* The idx on gcond is not PHI, it would be next. */
+ if (is_gimple_assign (stmt))
+ {
+ tree rhs = gimple_assign_rhs1 (stmt);
+ if (TREE_CODE (rhs) != SSA_NAME)
+ return false;
+
+ cmp_next = true;
+ inc_stmt = stmt;
+ stmt = filter_conversions (loop, rhs, &small_type, &large_type);
+ }
+
+ /* Get phi and next. */
+ if (gimple_code (stmt) != GIMPLE_PHI || gimple_bb (stmt) !=
loop->header)
+ return false;
+ gphi *phi = as_a<gphi *> (stmt);
+ tree next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
+ if (TREE_CODE (next) != SSA_NAME)
+ return false;
+
+ /* The define of next should be the increasement stmt. */
+ stmt = filter_conversions (loop, next, &small_type, &large_type);
+ if (inc_stmt != NULL && inc_stmt != stmt)
+ return false;
+ if (!is_gimple_assign (stmt)
+ || !flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
+ return false;
+ tree_code rhs_code = gimple_assign_rhs_code (stmt);
+ if (rhs_code != PLUS_EXPR)
+ return false;
+ tree step = gimple_assign_rhs2 (stmt);
+ if (!integer_minus_onep (step) && !integer_onep (step))
+ return false;
+ inc_stmt = stmt;
+ tree prev = gimple_assign_rhs1 (stmt);
+ if (TREE_CODE (prev) != SSA_NAME)
+ return false;
+ stmt = filter_conversions (loop, prev, &small_type, &large_type);
+ if (stmt != phi)
+ return false;
+
+ data.gc = gc;
+ data.phi = phi;
+ data.idx = idx;
+ data.bnd = bnd;
+ data.step = step;
+ data.large_type = large_type;
+ data.small_type = small_type;
+ data.inc_stmt = inc_stmt;
+ data.cmp_on_next = cmp_next;
+
+ return true;
+}
+
+/* Check if the loop is possible to wrap at index.
+ Return the assumption under which the wrap will not happen.
+ Return NULL_TREE, if wrap will not happen. */
+
+static tree
+get_wrap_assumption (class loop *loop, edge *exit, idx_elements &data)
+{
+ int i;
+ edge e;
+ if (!single_pred_p (loop->latch) || !empty_block_p (loop->latch))
+ return NULL_TREE;
+
+ auto_vec<edge> edges = get_loop_exit_edges (loop);
+ FOR_EACH_VEC_ELT (edges, i, e)
+ {
+ if (!analyze_idx_elements (loop, e, data))
+ continue;
+
+ /* Check if bound is MAX/MIN val of a integral type. */
+ tree bnd = data.bnd;
+ tree bnd_type = TREE_TYPE (bnd);
+ if (!INTEGRAL_TYPE_P (bnd_type) || !TYPE_UNSIGNED (bnd_type))
+ continue;
+ if (tree_int_cst_equal (bnd, TYPE_MAX_VALUE (bnd_type))
+ || tree_int_cst_equal (bnd, TYPE_MIN_VALUE (bnd_type)))
+ continue;
+
+ /* Check if it is "idx != bnd" or "idx < bnd". */
+ gcond *gc = data.gc;
+ enum tree_code code = gimple_cond_code (gc);
+ if (bnd == gimple_cond_lhs (gc))
+ code = swap_tree_comparison (code);
+ if ((e->flags & EDGE_TRUE_VALUE) && code == EQ_EXPR)
+ code = NE_EXPR;
+ if (code != NE_EXPR && code != LT_EXPR && code != GT_EXPR)
+ continue;
+
+ /* Check if idx is iv with base and step. */
+ affine_iv iv;
+ tree iv_niters = NULL_TREE;
+ tree idx = PHI_RESULT (data.phi);
+ if (!simple_iv_with_niters (loop, loop_containing_stmt (gc), idx,
&iv,
+ &iv_niters, false)) + continue;+ if (!iv.base || !iv.step || !tree_int_cst_equal (iv.step, data.step))
+ continue; + + bool is_negative = tree_int_cst_sign_bit (iv.step); + enum tree_code expect_code = is_negative ? GT_EXPR : LT_EXPR; + if (code != NE_EXPR && code != expect_code) + continue; ++ /* Update the type for base, bound and the max value of boundary. */
+ tree base = iv.base; + tree small_type = data.small_type; + tree large_type = data.large_type; + tree max_min_bnd = is_negative ? TYPE_MIN_VALUE (small_type) + : TYPE_MAX_VALUE (small_type); + if (large_type != TREE_TYPE (base)) + base = fold_convert (large_type, base); + if (large_type != TREE_TYPE (bnd)) + bnd = fold_convert (large_type, bnd); + if (large_type != small_type) + max_min_bnd = fold_convert (large_type, max_min_bnd); + + /* There is no wrap if bnd <= max value && base <= bnd. */ + enum tree_code expect_code1 = is_negative ? GE_EXPR : LE_EXPR; + tree no_wrap + = fold_build2 (expect_code1, boolean_type_node, bnd, max_min_bnd); + no_wrap + = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, no_wrap, + fold_build2 (expect_code1, boolean_type_node, base, bnd)); + + if (integer_zerop (no_wrap)) + continue; + + *exit = e; + return no_wrap; + } + + return NULL_TREE; +} ++/* Update the idx and bnd with a suitable type for no wrap/oveflow loop. + Suitable type would be the largest type of the type conversion which + occur on index, if the largest type is unsigned, using sizetype. */
+
+static bool
+update_idx_bnd_type (class loop *loop, idx_elements &data)
+{
+ gphi *phi = data.phi;
+ tree type = TREE_TYPE (PHI_RESULT (phi));
+ tree suitable_type = data.large_type;
+ if (TYPE_UNSIGNED (suitable_type))
+ {
+ if (TYPE_PRECISION (suitable_type) == TYPE_PRECISION (sizetype))
+ return false;
+ suitable_type = sizetype;
+ }
+
+ /* New base and new bound. */
+ tree bnd = data.bnd;
+ edge pre_e = loop_preheader_edge (loop);
+ tree base = PHI_ARG_DEF_FROM_EDGE (phi, pre_e);
+ tree new_base = fold_convert (suitable_type, base);
+ tree new_bnd = fold_convert (suitable_type, bnd);
+ gimple_seq seq = NULL;
+ new_base = force_gimple_operand (new_base, &seq, true, NULL_TREE);
+ if (seq)
+ gsi_insert_seq_on_edge_immediate (pre_e, seq);
+ seq = NULL;
+ new_bnd = force_gimple_operand (new_bnd, &seq, true, NULL_TREE);
+ if (seq)
+ gsi_insert_seq_on_edge_immediate (pre_e, seq);
+
+ /* new_i = phi (new_b, new_n)
+ new_n = new_i + 1 */
+ edge latch_e = loop_latch_edge (loop);
+ const char *name = "idx";
+ tree new_idx = make_temp_ssa_name (suitable_type, NULL, name);
+ tree new_next = make_temp_ssa_name (suitable_type, NULL, name);
+ gphi *newphi = create_phi_node (new_idx, loop->header);
+ add_phi_arg (newphi, new_base, pre_e, UNKNOWN_LOCATION);
+ add_phi_arg (newphi, new_next, latch_e, UNKNOWN_LOCATION);
+
+ /* New increase stmt. */
+ gimple *inc_stmt = data.inc_stmt;
+ tree step = gimple_assign_rhs2 (inc_stmt);
+ if (tree_int_cst_sign_bit(step))
+ {
+ wide_int v = wi::to_wide (step);
+ v = wide_int::from (v, TYPE_PRECISION (suitable_type),
+ SIGNED);
+
+ step = wide_int_to_tree (suitable_type, v);
+ }
+ else
+ step = fold_convert (suitable_type, step);
+ new_idx = PHI_RESULT (newphi);
+ tree_code inc_code = gimple_assign_rhs_code (inc_stmt);
+ gimple *new_inc = gimple_build_assign (new_next, inc_code, new_idx,
step);
+ gimple_stmt_iterator gsi = gsi_for_stmt (inc_stmt); + gsi_insert_before (&gsi, new_inc, GSI_SAME_STMT); + + /* Update gcond. */ + gcond *gc = data.gc; + bool inv = bnd == gimple_cond_lhs (gc); + tree cmp_idx = data.cmp_on_next ? new_next : new_idx; + gimple_cond_set_lhs (gc, inv ? new_bnd : cmp_idx); + gimple_cond_set_rhs (gc, inv ? cmp_idx : new_bnd); + update_stmt (gc); + + /* next = (next type)new_next + And remove next = prev + 1. */ + tree next = gimple_assign_lhs (inc_stmt); + type = TREE_TYPE (next);+ gimple *stmt = gimple_build_assign (next, fold_convert (type, new_next));
+ gsi = gsi_for_stmt (inc_stmt); + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + + gsi = gsi_for_stmt (inc_stmt); + gsi_remove (&gsi, true); + + /* prev = (prev type)new_prev + And remove prev = phi. */ + tree idx = PHI_RESULT (phi); + type = TREE_TYPE (idx); + stmt = gimple_build_assign (idx, fold_convert (type, new_idx)); + gsi = gsi_after_labels (loop->header); + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + + gsi = gsi_for_stmt (phi); + gsi_remove (&gsi, true); + + if (dump_file && (dump_flags & TDF_DETAILS))+ fprintf (dump_file, ";; Loop index type is updated to use faster type.\n");
+
+ return true;
+}
+
+/* Split out a new loop which would not wrap,
+ under the guard that NO_WRAP_COND will not be true. */
+
+static bool
+split_wrap_boundary (class loop *loop, edge e, tree no_wrap_cond,
+ bool is_negative_step)
+{
+ /* Convert the condition into a suitable gcond. */
+ gimple_seq stmts = NULL;
+ no_wrap_cond = force_gimple_operand_1 (no_wrap_cond, &stmts,
+ is_gimple_condexpr, NULL_TREE);
+
+ /* Version the loop. */
+ initialize_original_copy_tables ();
+ basic_block cond_bb;
+ loop_version (loop, no_wrap_cond, &cond_bb,
+ profile_probability::very_likely (),
+ profile_probability::very_unlikely (),
+ profile_probability::very_likely (),
+ profile_probability::very_unlikely (), true);
+ free_original_copy_tables ();
+
+ /* Insert the statements that feed COND. */
+ if (stmts)
+ {
+ gimple_stmt_iterator gsi = gsi_last_bb (cond_bb);
+ gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
+ }
+
+ /* Update gcond code. */
+ gcond *gc = as_a<gcond *> (last_stmt (e->src));
+ enum tree_code code = gimple_cond_code (gc);
+ enum tree_code new_code;
+ bool inv = expr_invariant_in_loop_p (loop, gimple_cond_lhs (gc));
+ if (is_negative_step)
+ new_code = inv ? LT_EXPR : GT_EXPR;
+ else
+ new_code = inv ? GT_EXPR : LT_EXPR;
+ if (code == NE_EXPR || code == EQ_EXPR)
+ gimple_cond_set_code (gc, new_code);
+
+ /* Swap edge. */
+ if (code == EQ_EXPR)
+ {
+ edge out = EDGE_SUCC (e->src, 0);
+ edge in = EDGE_SUCC (e->src, 1);
+ if (in->flags & EDGE_TRUE_VALUE)
+ std::swap (in, out);
+ in->flags |= EDGE_TRUE_VALUE;
+ in->flags &= ~EDGE_FALSE_VALUE;
+ out->flags |= EDGE_FALSE_VALUE;
+ out->flags &= ~EDGE_TRUE_VALUE;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ";; Loop split on wrap index.\n");
+
+ return true;
+}
+
+/* Split loop if there is possible wrap.
+ For example:
+ transform
+
+ void
+ foo (int *a, int *b, unsigned l, unsigned u_n)
+ {
+ while (++l != u_n)
+ a[l] = b[l] + 1;
+ }
+
+ to:
+ if (l < u_n)
+ {
+ int li = l;
+ int n = u_n;
+ while (++li < n)
+ a[li] = b[li] + 1;
+ l = li;
+ }
+ else
+ while (++l != n)
+ a[l] = b[l] + 1;
+ */
+static bool
+split_loop_on_wrap (class loop *loop)
+{
+ edge e;
+ idx_elements data;
+ tree no_wrap = get_wrap_assumption (loop, &e, data);
+
+ if (!no_wrap)
+ return false;
+
+ int num = 0;
+ basic_block *bbs = get_loop_body (loop);
+ for (unsigned i = 0; i < loop->num_nodes; i++)
+ num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights);
+
+ if (num > param_max_peeled_insns)
+ {
+ free (bbs);
+ return false;
+ }
+
+ if (!can_copy_bbs_p (bbs, loop->num_nodes))
+ {
+ free (bbs);
+ return false;
+ }
+
+ free (bbs);
+
+ if (integer_onep (no_wrap))
+ return update_idx_bnd_type (loop, data);
+
+ if (split_wrap_boundary (loop, e, no_wrap, tree_int_cst_sign_bit
(data.step)))
+ {
+ update_idx_bnd_type (loop, data);
+ return true;
+ }
+
+ return false;
+}
+
/* Main entry point. Perform loop splitting on all suitable loops. */
static unsigned int
@@ -1622,7 +2085,8 @@ tree_ssa_split_loops (void)
if (optimize_loop_for_size_p (loop))
continue;
- if (split_loop (loop) || split_loop_on_cond (loop))
+ if (split_loop (loop) || split_loop_on_cond (loop)
+ || split_loop_on_wrap (loop))
{
/* Mark our containing loop as having had some split inner loops.
*/
loop_outer (loop)->aux = loop;
Here is the updated patch, thanks for your time!Updates: . Enhance code to support negative step. . Check step +-1 to make sure it hits loop condition !=. Enhance runtime cases to check more boundary cases and run order cases. . Refine for compiling time: check loop num of insns and can_copy_bbs_p laterdiff --git a/gcc/testsuite/gcc.dg/loop-split1.c b/gcc/testsuite/gcc.dg/loop-split1.c new file mode 100644 index 00000000000..dd2d03a7b96 --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-split1.c @@ -0,0 +1,101 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fsplit-loops -fdump-tree-lsplit-details" } */ + +void +foo (int *a, int *b, unsigned l, unsigned n) +{ + while (++l != n) + a[l] = b[l] + 1; +} +void +foo_1 (int *a, int *b, unsigned n) +{ + unsigned l = 0; + while (++l != n) + a[l] = b[l] + 1; +} + +void +foo1 (int *a, int *b, unsigned l, unsigned n) +{ + while (l++ != n) + a[l] = b[l] + 1; +} + +/* No wrap. */ +void +foo1_1 (int *a, int *b, unsigned n) +{ + unsigned l = 0; + while (l++ != n) + a[l] = b[l] + 1; +} + +unsigned +foo2 (char *a, char *b, unsigned l, unsigned n) +{ + while (++l != n) + if (a[l] != b[l]) + break; + + return l; +} + +unsigned +foo2_1 (char *a, char *b, unsigned l, unsigned n) +{ + l = 0; + while (++l != n) + if (a[l] != b[l]) + break; + + return l; +} + +unsigned +foo3 (char *a, char *b, unsigned l, unsigned n) +{ + while (l++ != n) + if (a[l] != b[l]) + break; + + return l; +} + +/* No wrap. */ +unsigned +foo3_1 (char *a, char *b, unsigned l, unsigned n) +{ + l = 0; + while (l++ != n) + if (a[l] != b[l]) + break; + + return l; +} + +void +bar (); +void +foo4 (unsigned n, unsigned i) +{ + do + { + if (i == n) + return; + bar (); + ++i; + } + while (1); +} + +unsigned +find_skip_diff (char *p, char *q, unsigned n, unsigned i) +{ + while (p[i] == q[i] && ++i != n) + p++, q++; + + return i; +} + +/* { dg-final { scan-tree-dump-times "Loop split" 8 "lsplit" } } */ diff --git a/gcc/testsuite/gcc.dg/loop-split2.c b/gcc/testsuite/gcc.dg/loop-split2.c new file mode 100644 index 00000000000..56377e2f2f5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-split2.c @@ -0,0 +1,155 @@ +/* { dg-do run } */ +/* { dg-options "-O3" } */ + +extern void +abort (void); +extern void +exit (int); +void +push (int); + +#define NI __attribute__ ((noinline)) + +void NI +foo (int *a, int *b, unsigned char l, unsigned char n) +{ + while (++l != n) + a[l] = b[l] + 1; +} + +unsigned NI +bar (int *a, int *b, unsigned char l, unsigned char n) +{ + while (l++ != n) + { + push (l); + if (a[l] != b[l]) + break; + push (l + 1); + } + return l; +} + +void NI +foo_1 (int *a, int *b, unsigned char l, unsigned char n) +{ + while (--l != n) + a[l] = b[l] + 1; +} + +unsigned NI +bar_1 (int *a, int *b, unsigned char l, unsigned char n) +{ + while (l-- != n) + { + push (l); + if (a[l] != b[l]) + break; + push (l + 1); + } + + return l; +} + +int a[258]; +int b[258]; +int c[1024]; +static int top = 0; +void +push (int e) +{ + c[top++] = e; +} + +void +reset () +{ + top = 0; + __builtin_memset (c, 0, sizeof (c)); +} + +#define check(a, b) (a == b) + +int +check_c (int *c, int a0, int a1, int a2, int a3, int a4, int a5) +{ + return check (c[0], a0) && check (c[1], a1) && check (c[2], a2) + && check (c[3], a3) && check (c[4], a4) && check (c[5], a5); +} + +int +main () +{ + __builtin_memcpy (b, a, sizeof (a)); + reset (); + if (bar (a, b, 6, 8) != 9 || !check_c (c, 7, 8, 8, 9, 0, 0)) + abort (); + + reset (); + if (bar (a, b, 5, 3) != 4 || !check_c (c, 6, 7, 7, 8, 8, 9) + || !check_c (c + 496, 254, 255, 255, 256, 0, 1)) + abort (); + + reset (); + if (bar (a, b, 6, 6) != 7 || !check_c (c, 0, 0, 0, 0, 0, 0)) + abort (); + + reset ();+ if (bar (a, b, 253, 255) != 0 || !check_c (c, 254, 255, 255, 256, 0, 0))+ abort (); + + reset ();+ if (bar (a, b, 253, 0) != 1 || !check_c (c, 254, 255, 255, 256, 0, 1))+ abort (); + + reset (); + if (bar_1 (a, b, 6, 8) != 7 || !check_c (c, 5, 6, 4, 5, 3, 4)) + abort (); + + reset (); + if (bar_1 (a, b, 5, 3) != 2 || !check_c (c, 4, 5, 3, 4, 0, 0)) + abort (); + + reset (); + if (bar_1 (a, b, 6, 6) != 5) + abort (); + + reset ();+ if (bar_1 (a, b, 2, 255) != 254 || !check_c (c, 1, 2, 0, 1, 255, 256))+ abort (); + + reset (); + if (bar_1 (a, b, 2, 0) != 255 || !check_c (c, 1, 2, 0, 1, 0, 0)) + abort (); + + b[100] += 1; + reset (); + if (bar (a, b, 90, 110) != 100) + abort (); + + reset (); + if (bar (a, b, 110, 105) != 100) + abort (); + + reset (); + if (bar_1 (a, b, 90, 110) != 109) + abort (); + + reset (); + if (bar_1 (a, b, 2, 90) != 100) + abort (); + + foo (a, b, 99, 99); + a[99] = b[99] + 1; + for (int i = 0; i < 256; i++) + if (a[i] != b[i] + 1) + abort (); + + foo_1 (a, b, 99, 99); + a[99] = b[99] + 1; + for (int i = 0; i < 256; i++) + if (a[i] != b[i] + 1) + abort (); + + exit (0); +} diff --git a/gcc/testsuite/gcc.dg/loop-split3.c b/gcc/testsuite/gcc.dg/loop-split3.c new file mode 100644 index 00000000000..ec93ee8bd12 --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-split3.c @@ -0,0 +1,62 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fsplit-loops -fdump-tree-lsplit-details" } */ + +void +foo (int *a, int *b, unsigned l, unsigned n) +{ + while (--l != n) + a[l] = b[l] + 1; +} + +void +foo1 (int *a, int *b, unsigned l, unsigned n) +{ + while (l-- != n) + a[l] = b[l] + 1; +} + +unsigned +foo2 (char *a, char *b, unsigned l, unsigned n) +{ + while (--l != n) + if (a[l] != b[l]) + break; + + return l; +} + +unsigned +foo3 (char *a, char *b, unsigned l, unsigned n) +{ + while (l-- != n) + if (a[l] != b[l]) + break; + + return l; +} + +void +bar (); +void +foo4 (unsigned n, unsigned i) +{ + do + { + if (i == n) + return; + bar (); + --i; + } + while (1); +} + +unsigned +find_skip_diff (char *p, char *q, unsigned n, unsigned i) +{ + while (p[i] == q[i] && --i != n) + p--, q--; + + return i; +} + +/* { dg-final { scan-tree-dump-times "Loop split" 6 "lsplit" } } */ diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c index 3a09bbc39e5..e9f23b32186 100644 --- a/gcc/tree-ssa-loop-split.c +++ b/gcc/tree-ssa-loop-split.c @@ -41,6 +41,7 @@ along with GCC; see the file COPYING3. If not see #include "cfghooks.h" #include "gimple-fold.h" #include "gimplify-me.h" +#include "tree-ssa-loop-ivopts.h" /* This file implements two kinds of loop splitting. @@ -229,11 +230,14 @@ easy_exit_values (class loop *loop) conditional). I.e. the second loop can now be entered either via the original entry or via NEW_E, so the entry values of LOOP2 phi nodes are either the original ones or those at the exit - of LOOP1. Insert new phi nodes in LOOP2 pre-header reflecting - this. The loops need to fulfill easy_exit_values(). */ + of LOOP1. Selecting the previous value instead next value as the + exit value of LOOP1 if USE_PREV is true. Insert new phi nodes in + LOOP2 pre-header reflecting this. The loops need to fulfill + easy_exit_values(). */ static void -connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e) +connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e, + bool use_prev = false) { basic_block rest = loop_preheader_edge (loop2)->src; gcc_assert (new_e->dest == rest); @@ -279,7 +283,8 @@ connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e) gphi * newphi = create_phi_node (new_init, rest); add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION); - add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION);+ add_phi_arg (newphi, use_prev ? PHI_RESULT (phi_first) : next, new_e,+ UNKNOWN_LOCATION); SET_USE (op, new_init); } } @@ -1593,6 +1598,252 @@ split_loop_on_cond (struct loop *loop) return do_split; } +/* Check if the LOOP exit branch is like "if (idx != bound)",+ Return the branch edge which exit loop, if wrap may happen on "idx". */+ +static edge +get_ne_cond_branch (struct loop *loop, tree *step) +{ + int i; + edge e; + + auto_vec<edge> edges = get_loop_exit_edges (loop); + FOR_EACH_VEC_ELT (edges, i, e) + { + basic_block bb = e->src; + + /* Check if exit at gcond. */ + gimple *last = last_stmt (bb); + if (!last || gimple_code (last) != GIMPLE_COND) + continue; + gcond *cond = as_a<gcond *> (last); + enum tree_code code = gimple_cond_code (cond); + if (!((code == NE_EXPR && (e->flags & EDGE_FALSE_VALUE)) + || (code == EQ_EXPR && (e->flags & EDGE_TRUE_VALUE)))) + continue; + + /* Check if bound is invarant. */ + tree idx = gimple_cond_lhs (cond); + tree bnd = gimple_cond_rhs (cond); + if (expr_invariant_in_loop_p (loop, idx)) + std::swap (idx, bnd); + else if (!expr_invariant_in_loop_p (loop, bnd)) + continue; + + /* Only unsigned type conversion could cause wrap. */ + tree type = TREE_TYPE (idx); + if (!INTEGRAL_TYPE_P (type) || TREE_CODE (idx) != SSA_NAME + || !TYPE_UNSIGNED (type)) + continue; + + /* Avoid to split if bound is MAX/MIN val. */ + tree bound_type = TREE_TYPE (bnd); + if (tree_int_cst_equal (bnd, TYPE_MAX_VALUE (bound_type)) + || tree_int_cst_equal (bnd, TYPE_MIN_VALUE (bound_type))) + continue; + + /* Check if there is possible wrap. */ + class tree_niter_desc niter; + if (!number_of_iterations_exit (loop, e, &niter, false, false)) + continue; + if (niter.control.no_overflow) + return NULL; + if (niter.cmp != NE_EXPR) + continue; + if (!integer_onep (niter.control.step) + && !integer_minus_onep (niter.control.step)) + continue; + *step = niter.control.step; ++ /* If exit edge is just before the empty latch, it is easy to link+ the split loops: just jump from the exit edge of one loop to the + header of new loop. */ + if (single_pred_p (loop->latch) + && single_pred_edge (loop->latch)->src == bb + && empty_block_p (loop->latch)) + return e; ++ /* If exit edge is at end of header, and header contains i++ or ++i,+ only, it is simple to link the split loops: jump from the end of+ one loop header to the new loop header, and use unchanged PHI result+ of the first loop as the entry PHI value of the second loop. */ + if (bb == loop->header) + { + /* Only one phi. */ + gphi_iterator psi = gsi_start_phis (bb); + if (gsi_end_p (psi)) + continue; + gphi *phi = psi.phi (); + gsi_next (&psi); + if (!gsi_end_p (psi)) + continue; + + /* Check it is ++i or ++i */ + tree next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); + tree prev = PHI_RESULT (phi); + if (idx != prev && idx != next) + continue; ++ gimple_stmt_iterator gsi = gsi_start_nondebug_after_labels_bb (bb);+ if (gsi_end_p (gsi)) + continue; + gimple *s1 = gsi_stmt (gsi); + if (!is_gimple_assign (s1) || gimple_assign_lhs (s1) != next + || gimple_assign_rhs1 (s1) != prev) + continue; + + gsi_next_nondebug (&gsi); + if (!gsi_end_p (gsi) && gsi_stmt (gsi) == cond) + return e; + } + } + + return NULL; +} ++/* Split the LOOP with NE_EXPR into two loops with GT_EXPR and LT_EXPR. */+ +static bool +split_ne_loop (struct loop *loop, edge cond_e, tree step) +{ + initialize_original_copy_tables (); + + struct loop *loop2 = loop_version (loop, boolean_true_node, NULL, + profile_probability::always (), + profile_probability::never (), + profile_probability::always (), + profile_probability::always (), true); + + gcc_assert (loop2); + update_ssa (TODO_update_ssa); + + basic_block loop2_cond_exit_bb = get_bb_copy (cond_e->src); + free_original_copy_tables (); + + gcond *gc = as_a<gcond *> (last_stmt (cond_e->src)); + gcond *dup_gc = as_a<gcond *> (last_stmt (loop2_cond_exit_bb)); + + /* Invert edges for gcond. */ + if (gimple_cond_code (gc) == EQ_EXPR) + { + auto invert_edge = [](basic_block bb) { + edge out = EDGE_SUCC (bb, 0); + edge in = EDGE_SUCC (bb, 1); + if (in->flags & EDGE_TRUE_VALUE) + std::swap (in, out); + in->flags |= EDGE_TRUE_VALUE; + in->flags &= ~EDGE_FALSE_VALUE; + out->flags |= EDGE_FALSE_VALUE; + out->flags &= ~EDGE_TRUE_VALUE; + }; + + invert_edge (gimple_bb (gc)); + invert_edge (gimple_bb (dup_gc)); + } + + /* Change if (i != n) to LOOP1:if (i > n) and LOOP2:if (i < n) */ + bool inv = expr_invariant_in_loop_p (loop, gimple_cond_lhs (gc)); + if (tree_int_cst_sign_bit (step)) + inv = !inv; + enum tree_code first_loop_code = inv ? LT_EXPR : GT_EXPR; + enum tree_code second_loop_code = inv ? GT_EXPR : LT_EXPR; + + gimple_cond_set_code (gc, first_loop_code); + gimple_cond_set_code (dup_gc, second_loop_code); + + /* Link the exit cond edge to new loop. */ + gcond *break_cond = as_a<gcond *> (gimple_copy (gc)); + edge pred_e = single_pred_edge (loop->latch); + bool simple_loop+ = pred_e && pred_e->src == cond_e->src && empty_block_p (loop->latch);+ if (simple_loop) + gimple_cond_set_code (break_cond, second_loop_code); + else + gimple_cond_make_true (break_cond); + + basic_block break_bb = split_edge (cond_e); + gimple_stmt_iterator gsi = gsi_last_bb (break_bb); + gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT); + + edge to_exit = single_succ_edge (break_bb);+ edge to_new_loop = make_edge (break_bb, loop_preheader_edge (loop2)->src, 0);+ to_new_loop->flags |= EDGE_TRUE_VALUE; + to_exit->flags |= EDGE_FALSE_VALUE; + to_exit->flags &= ~EDGE_FALLTHRU; + to_exit->probability = cond_e->probability; + to_new_loop->probability = to_exit->probability.invert (); + + update_ssa (TODO_update_ssa); + + connect_loop_phis (loop, loop2, to_new_loop, !simple_loop); + + rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ";; Loop split on wrap index.\n"); + + return true; +} ++/* Checks if LOOP contains a suitable NE_EXPR conditional block to split.+L_H: + if (i!=N) + S; + else + goto EXIT; + i++; + goto L_H; + +The "i!=N" is like "i>N || i<N", then it could be transformed to: + +L_H: + if (i>N) + S; + else + goto EXIT; + i++; + goto L_H; +L1_H: + if (i<N) + S; + else + goto EXIT; + i++; + goto L1_H; + +The loop with "i<N" is in favor of both GIMPLE and RTL passes. */ + +static bool +split_loop_on_ne_cond (class loop *loop) +{ + tree step; + edge branch_edge = get_ne_cond_branch (loop, &step); + if (!branch_edge) + return false; + + int num = 0; + basic_block *bbs = get_loop_body (loop); + for (unsigned i = 0; i < loop->num_nodes; i++)+ num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights);+ + if (num > param_max_peeled_insns) + { + free (bbs); + return false; + } + + if (!can_copy_bbs_p (bbs, loop->num_nodes)) + { + free (bbs); + return false; + } + free (bbs); + + if (split_ne_loop (loop, branch_edge, step)) + return true; + + return false; +} +/* Main entry point. Perform loop splitting on all suitable loops. */static unsigned int @@ -1622,7 +1873,8 @@ tree_ssa_split_loops (void) if (optimize_loop_for_size_p (loop)) continue; - if (split_loop (loop) || split_loop_on_cond (loop)) + if (split_loop (loop) || split_loop_on_cond (loop) + || split_loop_on_ne_cond (loop)) {/* Mark our containing loop as having had some split inner loops. */loop_outer (loop)->aux = loop;
