@@ -2082,6 +2082,37 @@ vect_do_peeling_for_alignment (loop_vec_info loop_vinfo, tree ni_name,
free_original_copy_tables ();
}
+/* Function vect_create_cond_for_niters_checks.
+
+ Create a conditional expression that represents the run-time checks for
+ loop's niter. The loop is guaranteed to to terminate if the run-time
+ checks hold.
+
+ Input:
+ COND_EXPR - input conditional expression. New conditions will be chained
+ with logical AND operation. If it is NULL, then the function
+ is used to return the number of alias checks.
+ LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
+ to be checked.
+
+ Output:
+ COND_EXPR - conditional expression.
+
+ The returned COND_EXPR is the conditional expression to be used in the
+ if statement that controls which version of the loop gets executed at
+ runtime. */
+
+static void
+vect_create_cond_for_niters_checks (loop_vec_info loop_vinfo, tree *cond_expr)
+{
+ tree part_cond_expr = LOOP_VINFO_NITERS_ASSUMPTIONS (loop_vinfo);
+
+ if (*cond_expr)
+ *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ *cond_expr, part_cond_expr);
+ else
+ *cond_expr = part_cond_expr;
+}
/* Function vect_create_cond_for_align_checks.
@@ -2330,7 +2361,7 @@ void
vect_loop_versioning (loop_vec_info loop_vinfo,
unsigned int th, bool check_profitability)
{
- struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+ struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo), *nloop;
struct loop *scalar_loop = LOOP_VINFO_SCALAR_LOOP (loop_vinfo);
basic_block condition_bb;
gphi_iterator gsi;
@@ -2347,14 +2378,19 @@ vect_loop_versioning (loop_vec_info loop_vinfo,
tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
bool version_align = LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo);
bool version_alias = LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo);
+ bool version_niter = LOOP_REQUIRES_VERSIONING_FOR_NITERS (loop_vinfo);
if (check_profitability)
- {
- cond_expr = fold_build2 (GT_EXPR, boolean_type_node, scalar_loop_iters,
- build_int_cst (TREE_TYPE (scalar_loop_iters), th));
- cond_expr = force_gimple_operand_1 (cond_expr, &cond_expr_stmt_list,
- is_gimple_condexpr, NULL_TREE);
- }
+ cond_expr = fold_build2 (GT_EXPR, boolean_type_node, scalar_loop_iters,
+ build_int_cst (TREE_TYPE (scalar_loop_iters),
+ th));
+
+ if (version_niter)
+ vect_create_cond_for_niters_checks (loop_vinfo, &cond_expr);
+
+ if (cond_expr)
+ cond_expr = force_gimple_operand_1 (cond_expr, &cond_expr_stmt_list,
+ is_gimple_condexpr, NULL_TREE);
if (version_align)
vect_create_cond_for_align_checks (loop_vinfo, &cond_expr,
@@ -2375,8 +2411,8 @@ vect_loop_versioning (loop_vec_info loop_vinfo,
/* We don't want to scale SCALAR_LOOP's frequencies, we need to
scale LOOP's frequencies instead. */
- loop_version (scalar_loop, cond_expr, &condition_bb,
- prob, REG_BR_PROB_BASE, REG_BR_PROB_BASE - prob, true);
+ nloop = loop_version (scalar_loop, cond_expr, &condition_bb, prob,
+ REG_BR_PROB_BASE, REG_BR_PROB_BASE - prob, true);
scale_loop_frequencies (loop, prob, REG_BR_PROB_BASE);
/* CONDITION_BB was created above SCALAR_LOOP's preheader,
while we need to move it above LOOP's preheader. */
@@ -2403,8 +2439,18 @@ vect_loop_versioning (loop_vec_info loop_vinfo,
condition_bb);
}
else
- loop_version (loop, cond_expr, &condition_bb,
- prob, prob, REG_BR_PROB_BASE - prob, true);
+ nloop = loop_version (loop, cond_expr, &condition_bb,
+ prob, prob, REG_BR_PROB_BASE - prob, true);
+
+ if (version_niter)
+ {
+ /* The versioned loop could be infinite, we need to clear existing
+ niter information which is copied from the original loop. */
+ gcc_assert (loop_constraint_set_p (loop, LOOP_C_FINITE));
+ vect_free_loop_info_assumptions (nloop);
+ /* And set constraint LOOP_C_INFINITE for niter analyzer. */
+ loop_constraint_set (loop, LOOP_C_INFINITE);
+ }
if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION
&& dump_enabled_p ())
@@ -41,6 +41,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop.h"
#include "cfgloop.h"
#include "params.h"
#include "tree-scalar-evolution.h"
@@ -1002,37 +1003,89 @@ vect_fixup_scalar_cycles_with_patterns (loop_vec_info loop_vinfo)
Determine how many iterations the loop is executed and place it
in NUMBER_OF_ITERATIONS. Place the number of latch iterations
- in NUMBER_OF_ITERATIONSM1.
+ in NUMBER_OF_ITERATIONSM1. Place the condition under which the
+ niter information holds in ASSUMPTIONS.
Return the loop exit condition. */
static gcond *
-vect_get_loop_niters (struct loop *loop, tree *number_of_iterations,
- tree *number_of_iterationsm1)
+vect_get_loop_niters (struct loop *loop, tree *assumptions,
+ tree *number_of_iterations, tree *number_of_iterationsm1)
{
- tree niters;
-
+ edge exit = single_exit (loop);
+ struct tree_niter_desc niter_desc;
+ tree niter_assumptions, niter, may_be_zero;
+ gcond *cond = get_loop_exit_condition (loop);
+
+ *assumptions = boolean_true_node;
+ *number_of_iterationsm1 = chrec_dont_know;
+ *number_of_iterations = chrec_dont_know;
if (dump_enabled_p ())
dump_printf_loc (MSG_NOTE, vect_location,
"=== get_loop_niters ===\n");
- niters = number_of_latch_executions (loop);
- *number_of_iterationsm1 = niters;
+ if (!exit)
+ return cond;
+
+ niter = chrec_dont_know;
+ may_be_zero = NULL_TREE;
+ niter_assumptions = boolean_true_node;
+ if (!number_of_iterations_exit_assumptions (loop, exit, &niter_desc, NULL)
+ || chrec_contains_undetermined (niter_desc.niter))
+ return cond;
+
+ niter_assumptions = niter_desc.assumptions;
+ may_be_zero = niter_desc.may_be_zero;
+ niter = niter_desc.niter;
+
+ if (may_be_zero && integer_zerop (may_be_zero))
+ may_be_zero = NULL_TREE;
+
+ if (may_be_zero)
+ {
+ if (COMPARISON_CLASS_P (may_be_zero))
+ {
+ /* Try to combine may_be_zero with assumptions, this can simplify
+ computation of niter expression. */
+ if (niter_assumptions && !integer_nonzerop (niter_assumptions))
+ niter_assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ niter_assumptions,
+ fold_build1 (TRUTH_NOT_EXPR,
+ boolean_type_node,
+ may_be_zero));
+ else
+ niter = fold_build3 (COND_EXPR, TREE_TYPE (niter), may_be_zero,
+ build_int_cst (TREE_TYPE (niter), 0), niter);
+
+ may_be_zero = NULL_TREE;
+ }
+ else if (integer_nonzerop (may_be_zero))
+ {
+ niter = build_int_cst (TREE_TYPE (niter), 0);
+ *number_of_iterationsm1 = niter;
+ *number_of_iterations = niter;
+ return cond;
+ }
+ else
+ return cond;
+ }
+
+ *assumptions = niter_assumptions;
+ *number_of_iterationsm1 = niter;
/* We want the number of loop header executions which is the number
of latch executions plus one.
??? For UINT_MAX latch executions this number overflows to zero
for loops like do { n++; } while (n != 0); */
- if (niters && !chrec_contains_undetermined (niters))
- niters = fold_build2 (PLUS_EXPR, TREE_TYPE (niters), unshare_expr (niters),
- build_int_cst (TREE_TYPE (niters), 1));
- *number_of_iterations = niters;
+ if (niter && !chrec_contains_undetermined (niter))
+ niter = fold_build2 (PLUS_EXPR, TREE_TYPE (niter), unshare_expr (niter),
+ build_int_cst (TREE_TYPE (niter), 1));
+ *number_of_iterations = niter;
- return get_loop_exit_condition (loop);
+ return cond;
}
-
/* Function bb_in_loop_p
Used as predicate for dfs order traversal of the loop bbs. */
@@ -1101,6 +1154,7 @@ new_loop_vec_info (struct loop *loop)
LOOP_VINFO_NITERSM1 (res) = NULL;
LOOP_VINFO_NITERS (res) = NULL;
LOOP_VINFO_NITERS_UNCHANGED (res) = NULL;
+ LOOP_VINFO_NITERS_ASSUMPTIONS (res) = NULL;
LOOP_VINFO_COST_MODEL_THRESHOLD (res) = 0;
LOOP_VINFO_VECTORIZABLE_P (res) = 0;
LOOP_VINFO_PEELING_FOR_ALIGNMENT (res) = 0;
@@ -1280,12 +1334,13 @@ vect_compute_single_scalar_iteration_cost (loop_vec_info loop_vinfo)
Verify that certain CFG restrictions hold, including:
- the loop has a pre-header
- the loop has a single entry and exit
- - the loop exit condition is simple enough, and the number of iterations
- can be analyzed (a countable loop). */
+ - the loop exit condition is simple enough
+ - the number of iterations can be analyzed, i.e, a countable loop. The
+ niter could be analyzed under some assumptions. */
bool
vect_analyze_loop_form_1 (struct loop *loop, gcond **loop_cond,
- tree *number_of_iterationsm1,
+ tree *assumptions, tree *number_of_iterationsm1,
tree *number_of_iterations, gcond **inner_loop_cond)
{
if (dump_enabled_p ())
@@ -1376,9 +1431,13 @@ vect_analyze_loop_form_1 (struct loop *loop, gcond **loop_cond,
}
/* Analyze the inner-loop. */
- tree inner_niterm1, inner_niter;
+ tree inner_niterm1, inner_niter, inner_assumptions;
if (! vect_analyze_loop_form_1 (loop->inner, inner_loop_cond,
- &inner_niterm1, &inner_niter, NULL))
+ &inner_assumptions, &inner_niterm1,
+ &inner_niter, NULL)
+ /* Don't support analyzing niter under assumptions for inner
+ loop. */
+ || !integer_onep (inner_assumptions))
{
if (dump_enabled_p ())
dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
@@ -1447,7 +1506,7 @@ vect_analyze_loop_form_1 (struct loop *loop, gcond **loop_cond,
}
}
- *loop_cond = vect_get_loop_niters (loop, number_of_iterations,
+ *loop_cond = vect_get_loop_niters (loop, assumptions, number_of_iterations,
number_of_iterationsm1);
if (!*loop_cond)
{
@@ -1457,7 +1516,8 @@ vect_analyze_loop_form_1 (struct loop *loop, gcond **loop_cond,
return false;
}
- if (!*number_of_iterations
+ if (integer_zerop (*assumptions)
+ || !*number_of_iterations
|| chrec_contains_undetermined (*number_of_iterations))
{
if (dump_enabled_p ())
@@ -1483,10 +1543,11 @@ vect_analyze_loop_form_1 (struct loop *loop, gcond **loop_cond,
loop_vec_info
vect_analyze_loop_form (struct loop *loop)
{
- tree number_of_iterations, number_of_iterationsm1;
+ tree assumptions, number_of_iterations, number_of_iterationsm1;
gcond *loop_cond, *inner_loop_cond = NULL;
- if (! vect_analyze_loop_form_1 (loop, &loop_cond, &number_of_iterationsm1,
+ if (! vect_analyze_loop_form_1 (loop, &loop_cond,
+ &assumptions, &number_of_iterationsm1,
&number_of_iterations, &inner_loop_cond))
return NULL;
@@ -1494,6 +1555,19 @@ vect_analyze_loop_form (struct loop *loop)
LOOP_VINFO_NITERSM1 (loop_vinfo) = number_of_iterationsm1;
LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
LOOP_VINFO_NITERS_UNCHANGED (loop_vinfo) = number_of_iterations;
+ if (!integer_onep (assumptions))
+ {
+ /* We consider to vectorize this loop by versioning it under
+ some assumptions. In order to do this, we need to clear
+ existing information computed by scev and niter analyzer. */
+ scev_reset_htab ();
+ free_numbers_of_iterations_estimates_loop (loop);
+ /* Also set flag for this loop so that following scev and niter
+ analysis are done under the assumptions. */
+ loop_constraint_set (loop, LOOP_C_FINITE);
+ /* Also record the assumptions for versioning. */
+ LOOP_VINFO_NITERS_ASSUMPTIONS (loop_vinfo) = assumptions;
+ }
if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
{
@@ -2082,8 +2156,7 @@ start_over:
/* In case of versioning, check if the maximum number of
iterations is greater than th. If they are identical,
the epilogue is unnecessary. */
- && ((!LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo)
- && !LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
+ && (!LOOP_REQUIRES_VERSIONING (loop_vinfo)
|| (unsigned HOST_WIDE_INT) max_niter > th)))
LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo) = true;
@@ -3127,8 +3200,18 @@ vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo,
"versioning aliasing.\n");
}
- if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
- || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
+ /* Requires loop versioning with niter checks. */
+ if (LOOP_REQUIRES_VERSIONING_FOR_NITERS (loop_vinfo))
+ {
+ /* FIXME: Make cost depend on complexity of individual check. */
+ (void) add_stmt_cost (target_cost_data, 1, vector_stmt, NULL, 0,
+ vect_prologue);
+ dump_printf (MSG_NOTE,
+ "cost model: Adding cost of checks for loop "
+ "versioning niters.\n");
+ }
+
+ if (LOOP_REQUIRES_VERSIONING (loop_vinfo))
(void) add_stmt_cost (target_cost_data, 1, cond_branch_taken, NULL, 0,
vect_prologue);
@@ -3285,12 +3368,10 @@ vect_estimate_min_profitable_iters (loop_vec_info loop_vinfo,
decide whether to vectorize at compile time. Hence the scalar version
do not carry cost model guard costs. */
if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
- || LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
- || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
+ || LOOP_REQUIRES_VERSIONING (loop_vinfo))
{
/* Cost model check occurs at versioning. */
- if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
- || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
+ if (LOOP_REQUIRES_VERSIONING (loop_vinfo))
scalar_outside_cost += vect_get_stmt_cost (cond_branch_not_taken);
else
{
@@ -6629,8 +6710,7 @@ vect_transform_loop (loop_vec_info loop_vinfo)
/* Version the loop first, if required, so the profitability check
comes first. */
- if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
- || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
+ if (LOOP_REQUIRES_VERSIONING (loop_vinfo))
{
vect_loop_versioning (loop_vinfo, th, check_profitability);
check_profitability = false;
@@ -69,6 +69,7 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-iterator.h"
#include "gimple-walk.h"
#include "tree-ssa-loop-manip.h"
+#include "tree-ssa-loop-niter.h"
#include "tree-cfg.h"
#include "cfgloop.h"
#include "tree-vectorizer.h"
@@ -368,6 +369,20 @@ vect_destroy_datarefs (vec_info *vinfo)
free_data_refs (vinfo->datarefs);
}
+/* A helper function to free scev and LOOP niter information, as well as
+ clear loop constraint LOOP_C_FINITE. */
+
+void
+vect_free_loop_info_assumptions (struct loop *loop)
+{
+ scev_reset_htab ();
+ /* We need to explicitly reset upper bound information since they are
+ used even after free_numbers_of_iterations_estimates_loop. */
+ loop->any_upper_bound = false;
+ loop->any_likely_upper_bound = false;
+ free_numbers_of_iterations_estimates_loop (loop);
+ loop_constraint_clr (loop, LOOP_C_FINITE);
+}
/* Return whether STMT is inside the region we try to vectorize. */
@@ -537,7 +552,14 @@ vectorize_loops (void)
loop->aux = loop_vinfo;
if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
- continue;
+ {
+ /* Free existing information if loop is analyzed with some
+ assumptions. */
+ if (loop_constraint_set_p (loop, LOOP_C_FINITE))
+ vect_free_loop_info_assumptions (loop);
+
+ continue;
+ }
if (!dbg_cnt (vect_loop))
{
@@ -545,6 +567,11 @@ vectorize_loops (void)
debug counter. Set any_ifcvt_loops to visit
them at finalization. */
any_ifcvt_loops = true;
+ /* Free existing information if loop is analyzed with some
+ assumptions. */
+ if (loop_constraint_set_p (loop, LOOP_C_FINITE))
+ vect_free_loop_info_assumptions (loop);
+
break;
}
@@ -231,6 +231,8 @@ typedef struct _loop_vec_info : public vec_info {
tree num_iters;
/* Number of iterations of the original loop. */
tree num_iters_unchanged;
+ /* Condition under which this loop is analyzed and versioned. */
+ tree num_iters_assumptions;
/* Threshold of number of iterations below which vectorzation will not be
performed. It is calculated from MIN_PROFITABLE_ITERS and
@@ -343,6 +345,7 @@ typedef struct _loop_vec_info : public vec_info {
prologue peeling retain total unchanged scalar loop iterations for
cost model. */
#define LOOP_VINFO_NITERS_UNCHANGED(L) (L)->num_iters_unchanged
+#define LOOP_VINFO_NITERS_ASSUMPTIONS(L) (L)->num_iters_assumptions
#define LOOP_VINFO_COST_MODEL_THRESHOLD(L) (L)->th
#define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable
#define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor
@@ -371,10 +374,16 @@ typedef struct _loop_vec_info : public vec_info {
#define LOOP_VINFO_SCALAR_ITERATION_COST(L) (L)->scalar_cost_vec
#define LOOP_VINFO_SINGLE_SCALAR_ITERATION_COST(L) (L)->single_scalar_iteration_cost
-#define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \
+#define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \
((L)->may_misalign_stmts.length () > 0)
-#define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L) \
+#define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L) \
((L)->may_alias_ddrs.length () > 0)
+#define LOOP_REQUIRES_VERSIONING_FOR_NITERS(L) \
+ (LOOP_VINFO_NITERS_ASSUMPTIONS (L))
+#define LOOP_REQUIRES_VERSIONING(L) \
+ (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (L) \
+ || LOOP_REQUIRES_VERSIONING_FOR_ALIAS (L) \
+ || LOOP_REQUIRES_VERSIONING_FOR_NITERS (L))
#define LOOP_VINFO_NITERS_KNOWN_P(L) \
(tree_fits_shwi_p ((L)->num_iters) && tree_to_shwi ((L)->num_iters) > 0)
@@ -1177,5 +1186,6 @@ void vect_pattern_recog (vec_info *);
unsigned vectorize_loops (void);
void vect_destroy_datarefs (vec_info *);
bool vect_stmt_in_region_p (vec_info *, gimple *);
+void vect_free_loop_info_assumptions (struct loop *);
#endif /* GCC_TREE_VECTORIZER_H */
new file mode 100644
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+typedef unsigned long ul;
+void foo (ul* __restrict x, ul* __restrict y, ul n)
+{
+ ul i;
+ for (i=1; i<=n; i++, x++, y++)
+ *x += *y;
+}
+
+/* { dg-final { scan-tree-dump "vectorized 1 loops" "vect" } } */
new file mode 100644
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+void foo (int *a, int len)
+{
+ unsigned short i;
+
+ for (i = 1; i < (len - 1); i++)
+ a[i] = a[i+1];
+}
+
+/* { dg-final { scan-tree-dump "vectorized 1 loops" "vect" } } */