From: Robin Dapp <[email protected]>
This patch makes use of the preparational patches and actives
non-wrapping DR analysis. The resulting nowrap bounds are collected and
added to the existing niter assumptions by ANDing each term.
I needed to move DR analysis a bit earlier in order to re-use niter
checks and dumps. We now retrieve the DRs directly after
vect_analyze_loop_form, then build the assumptions and check them.
Afterwards, the DRs are finalized.
The vect tests are unchanged from my last patch attempt. Test 1-3
are based on 557.xz's hot loop.
PR tree-optimization/121908
gcc/ChangeLog:
* tree-vect-data-refs.cc (vect_find_stmt_data_reference):
Allow non-wrapping DR analysis.
(vect_reset_dr): New function.
* tree-vect-loop.cc (vect_analyze_loop_form): Defer assumption
checking.
(vect_get_loop_datarefs): New function.
(vect_build_assumptions): New function.
(vect_analyze_loop): Use new functions.
* tree-vectorizer.h (vect_reset_dr): Declare.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-prof/update-loopch.c:
* gcc.dg/tree-ssa/scev-12.c:
* gcc.dg/tree-ssa/scev-8.c:
* gcc.dg/vect/vect-unsigned-assump-1.c: New test.
* gcc.dg/vect/vect-unsigned-assump-2.c: New test.
* gcc.dg/vect/vect-unsigned-assump-3.c: New test.
* gcc.dg/vect/vect-unsigned-assump-4.c: New test.
* gcc.dg/vect/vect-unsigned-assump-5.c: New test.
* gcc.dg/vect/vect-unsigned-assump-6.c: New test.
* gcc.dg/vect/vect-unsigned-assump-7.c: New test.
* gcc.dg/vect/vect-unsigned-assump-8.c: New test.
vec
---
.../gcc.dg/tree-prof/update-loopch.c | 2 +
gcc/testsuite/gcc.dg/tree-ssa/scev-12.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/scev-8.c | 2 +-
.../gcc.dg/vect/vect-unsigned-assump-1.c | 22 +++
.../gcc.dg/vect/vect-unsigned-assump-2.c | 24 +++
.../gcc.dg/vect/vect-unsigned-assump-3.c | 20 +++
.../gcc.dg/vect/vect-unsigned-assump-4.c | 13 ++
.../gcc.dg/vect/vect-unsigned-assump-5.c | 14 ++
.../gcc.dg/vect/vect-unsigned-assump-6.c | 13 ++
.../gcc.dg/vect/vect-unsigned-assump-7.c | 17 ++
.../gcc.dg/vect/vect-unsigned-assump-8.c | 13 ++
gcc/tree-vect-data-refs.cc | 15 +-
gcc/tree-vect-loop.cc | 164 +++++++++++++++---
gcc/tree-vectorizer.h | 1 +
14 files changed, 292 insertions(+), 30 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-1.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-2.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-3.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-4.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-5.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-6.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-7.c
create mode 100644 gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-8.c
diff --git a/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
b/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
index a30b895bb67..efb92b2c4fc 100644
--- a/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
+++ b/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
@@ -5,6 +5,8 @@ int
main ()
{
int i;
+/* If we vectorize this, the block count changes which defies the test. */
+#pragma GCC novector
for (i = 0; i < max; i++)
{
a[i % 8]++;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-12.c
b/gcc/testsuite/gcc.dg/tree-ssa/scev-12.c
index e2ded46047e..b0feee911c1 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/scev-12.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-12.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+/* { dg-options "-O2 -fno-tree-vectorize -fdump-tree-ivopts-details" } */
int a[128];
extern int b[];
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-8.c
b/gcc/testsuite/gcc.dg/tree-ssa/scev-8.c
index a5b2ff71958..abdbf0250dd 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/scev-8.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-8.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+/* { dg-options "-O2 -fno-tree-vectorize -fdump-tree-ivopts-details" } */
int *a;
diff --git a/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-1.c
b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-1.c
new file mode 100644
index 00000000000..2c64eb890fd
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-1.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target vect_early_break } */
+
+#define uint8_t unsigned char
+#define uint32_t unsigned int
+
+int foo (const uint8_t *const cur, uint32_t len, uint32_t len_limit,
+ uint32_t pos, uint32_t cur_match)
+{
+ const uint32_t delta = pos - cur_match;
+ const uint8_t *pb = cur - delta;
+
+ while (++len != len_limit)
+ if (pb[len] != cur[len])
+ break;
+
+ return len;
+}
+
+/* { dg-final { scan-tree-dump "vectorized 1 loops in function" "vect" } } */
+/* { dg-final { scan-tree-dump "adding no-wrap assumption" "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-2.c
b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-2.c
new file mode 100644
index 00000000000..a071ec399f0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-2.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target vect_early_break } */
+/* { dg-require-effective-target vect_load_lanes } */
+
+#define uint8_t unsigned char
+#define uint32_t unsigned int
+
+int foo (const uint8_t *const cur, uint32_t len, uint32_t len_limit,
+ uint32_t pos, uint32_t cur_match)
+{
+ const uint32_t delta = pos - cur_match;
+ const uint8_t *pb = cur - delta;
+
+ /* We vectorize this with struct loads right now. */
+ while ((len += 2) != len_limit)
+ if (pb[len] != cur[len])
+ break;
+
+ return len;
+}
+
+/* { dg-final { scan-tree-dump "vectorized 1 loops in function" "vect" } } */
+/* { dg-final { scan-tree-dump "adding no-wrap assumption" "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-3.c
b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-3.c
new file mode 100644
index 00000000000..c9f6c2b0ca7
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-3.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target vect_early_break } */
+
+#define uint8_t unsigned char
+#define uint32_t unsigned int
+
+int foo (const uint8_t *const cur, uint32_t n)
+{
+ uint32_t i = 15;
+
+ while (i++ != n)
+ if (cur[i - 15] != cur[i])
+ break;
+
+ return i;
+}
+
+/* { dg-final { scan-tree-dump "vectorized 1 loops in function" "vect" } } */
+/* { dg-final { scan-tree-dump "adding no-wrap assumption" "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-4.c
b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-4.c
new file mode 100644
index 00000000000..8ba7ce435f9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-4.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-fno-builtin" } */
+/* { dg-require-effective-target vect_int } */
+
+/* We should vectorize this without additional assumptions.
+ The data-ref uses a pointer-based access which never wraps. */
+
+void f4 (int *p, unsigned start, unsigned end) {
+ for (unsigned i = start; i != end; i++)
+ *p++ = 0;
+}
+
+/* { dg-final { scan-tree-dump-not "adding no-wrap assumption" "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-5.c
b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-5.c
new file mode 100644
index 00000000000..2922fd1c114
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-5.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target vect_gather_load_ifn } */
+
+/* This should be vectorized without gather/scatter. */
+
+void f5 (int *__restrict a, int *__restrict b, unsigned start, unsigned end) {
+ for (unsigned i = start; i != end; i++)
+ a[i] = b[i];
+}
+
+/* { dg-final { scan-tree-dump-not "gather" "vect" } } */
+/* { dg-final { scan-tree-dump "vectorized 1 loops in function" "vect" } } */
+/* { dg-final { scan-tree-dump "adding no-wrap assumption" "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-6.c
b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-6.c
new file mode 100644
index 00000000000..e869e8095ea
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-6.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target vect_gather_load_ifn } */
+
+/* This should be vectorized without gather/scatter. */
+
+void f6 (int *__restrict a, int *__restrict b, unsigned start, unsigned end) {
+ for (unsigned i = start; i <= end; i++)
+ a[i] = b[i];
+}
+
+/* { dg-final { scan-tree-dump-not "gather" "vect" } } */
+/* { dg-final { scan-tree-dump "vectorized 1 loops in function" "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-7.c
b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-7.c
new file mode 100644
index 00000000000..6d7df016a13
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-7.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+/* This should be vectorized without gather/scatter. */
+
+void f7 (int *__restrict dst, unsigned n) {
+ unsigned i = 1;
+ while (i != n)
+ {
+ dst[i] = i;
+ i++;
+ }
+}
+
+/* { dg-final { scan-tree-dump-not "gather" "vect" } } */
+/* { dg-final { scan-tree-dump "vectorized 1 loops in function" "vect" } } */
+/* { dg-final { scan-tree-dump "adding no-wrap assumption" "vect" } } */
diff --git a/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-8.c
b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-8.c
new file mode 100644
index 00000000000..37d76304274
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-unsigned-assump-8.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-fno-builtin" } */
+/* { dg-require-effective-target vect_int } */
+
+/* We should vectorize this without additional assumptions.
+ The data-ref uses a pointer-based access which never wraps. */
+
+void f8 (int *__restrict a, unsigned start, unsigned n) {
+ for (unsigned i = start; i != n; i++)
+ a[i - start] = 0;
+}
+
+/* { dg-final { scan-tree-dump-not "adding no-wrap assumption" "vect" } } */
diff --git a/gcc/tree-vect-data-refs.cc b/gcc/tree-vect-data-refs.cc
index ab850de024b..4d90d285458 100644
--- a/gcc/tree-vect-data-refs.cc
+++ b/gcc/tree-vect-data-refs.cc
@@ -5180,7 +5180,7 @@ vect_find_stmt_data_reference (loop_p loop, gimple *stmt,
stmt);
auto_vec<data_reference_p, 2> refs;
- opt_result res = find_data_references_in_stmt (loop, stmt, &refs);
+ opt_result res = find_data_references_in_stmt (loop, stmt, &refs, true);
if (!res)
return res;
@@ -5237,7 +5237,8 @@ vect_find_stmt_data_reference (loop_p loop, gimple *stmt,
{
struct data_reference *newdr
= create_data_ref (NULL, loop_containing_stmt (stmt), DR_REF (dr), stmt,
- DR_IS_READ (dr), DR_IS_CONDITIONAL_IN_STMT (dr));
+ DR_IS_READ (dr), DR_IS_CONDITIONAL_IN_STMT (dr),
+ true);
if (DR_BASE_ADDRESS (newdr)
&& DR_OFFSET (newdr)
&& DR_INIT (newdr)
@@ -5318,6 +5319,16 @@ vect_find_stmt_data_reference (loop_p loop, gimple *stmt,
return opt_result::success ();
}
+/* Reset DR_INNERMOST, DR_NOWRAP_BOUND, and access functions of DR. */
+
+void
+vect_reset_dr (data_reference *dr)
+{
+ DR_INNERMOST (dr) = innermost_loop_behavior ();
+ DR_NOWRAP_BOUND (dr) = NULL_TREE;
+ dr->indices.access_fns.release ();
+}
+
/* Function vect_analyze_data_refs.
Find all the data references in the loop or basic block.
diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc
index 931b942d7cb..3908cad5714 100644
--- a/gcc/tree-vect-loop.cc
+++ b/gcc/tree-vect-loop.cc
@@ -1651,17 +1651,6 @@ vect_analyze_loop_form (class loop *loop, gimple
*loop_vectorized_call,
}
}
- if (!integer_onep (info->assumptions))
- {
- if (dump_enabled_p ())
- {
- dump_printf_loc (MSG_NOTE, vect_location,
- "Loop to be versioned with niter assumption ");
- dump_generic_expr (MSG_NOTE, TDF_SLIM, info->assumptions);
- dump_printf (MSG_NOTE, "\n");
- }
- }
-
return opt_result::success ();
}
@@ -2053,6 +2042,132 @@ vect_get_datarefs_in_loop (loop_p loop, basic_block
*bbs,
return opt_result::success ();
}
+/* Collect the data references of LOOP into SHARED. Return true if
+ all references could be analyzed and false otherwise. */
+
+static opt_result
+vect_get_loop_datarefs (class loop *loop, vec_info_shared *shared)
+{
+ basic_block *bbs = XCNEWVEC (basic_block, loop->num_nodes);
+ unsigned int nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p, bbs,
+ loop->num_nodes, loop);
+ gcc_assert (nbbs == loop->num_nodes);
+ opt_result res = vect_get_datarefs_in_loop (loop, bbs, &shared->datarefs);
+ free (bbs);
+ if (!res && dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
+ "not vectorized: loop contains function "
+ "calls or data references that cannot "
+ "be analyzed\n");
+ return res;
+}
+
+/* Gather no-wrap bounds from SHARED's datarefs and accumulate them in
+ one assumption. Validate this assumption, as well as INFO's niter
+ assumption and return an error on failure.
+ If the assumptions are valid, reset loop properties as well as
+ scev's hashtable and return success. */
+
+static opt_result
+vect_build_assumptions (class loop *loop, vec_info_shared *shared,
+ vect_loop_form_info *info)
+{
+ tree niter = info->number_of_iterations;
+ bool niter_known = niter && !chrec_contains_undetermined (niter);
+
+ /* Accumulate the surviving nowrap predicates separately so we can report
+ just them, rather than the union with the pre-existing niter
+ assumptions. */
+ tree nowrap_assum = NULL_TREE;
+
+ unsigned int i;
+ struct data_reference *dr;
+ FOR_EACH_VEC_ELT (shared->datarefs, i, dr)
+ {
+ tree bound = DR_NOWRAP_BOUND (dr);
+ if (!bound)
+ continue;
+
+ /* Build the assumption "NITER <= BOUND" */
+ tree assum = NULL_TREE;
+ if (niter_known)
+ {
+ unsigned prec = MAX (TYPE_PRECISION (TREE_TYPE (niter)),
+ TYPE_PRECISION (TREE_TYPE (bound)));
+ tree t = build_nonstandard_integer_type (prec, 1);
+ assum = fold_build2 (LE_EXPR, boolean_type_node,
+ fold_convert (t, niter),
+ fold_convert (t, bound));
+ }
+
+ if (assum && integer_onep (assum))
+ continue;
+
+ if (!assum || integer_zerop (assum))
+ {
+ vect_reset_dr (dr);
+
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "data reference address wraps, discarding "
+ "no-wrap assumption: %G", DR_STMT (dr));
+ continue;
+ }
+
+ /* Accumulate assumptions. */
+ if (nowrap_assum && nowrap_assum != assum)
+ nowrap_assum = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ nowrap_assum, assum);
+ else
+ nowrap_assum = assum;
+ }
+
+ /* Combine nowrap assumptions and niter assumption. */
+ if (nowrap_assum)
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "adding no-wrap assumption: %T\n", nowrap_assum);
+
+ if (info->assumptions && !integer_onep (info->assumptions))
+ nowrap_assum = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ info->assumptions, nowrap_assum);
+ info->assumptions = nowrap_assum;
+ }
+
+ if (integer_zerop (info->assumptions))
+ return opt_result::failure_at
+ (vect_location,
+ "not vectorized: number of iterations cannot be computed.\n");
+
+ if (!integer_onep (info->assumptions))
+ {
+ if (dump_enabled_p ())
+ {
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "Loop to be versioned with assumption ");
+ dump_generic_expr (MSG_NOTE, TDF_SLIM, info->assumptions);
+ dump_printf (MSG_NOTE, "\n");
+ }
+
+ /* 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);
+ /* 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);
+ }
+ else
+ /* Clear the existing niter information to make sure the nonwrapping flag
+ will be calculated and set propriately. */
+ free_numbers_of_iterations_estimates (loop);
+
+ return opt_result::success ();
+}
+
+
/* Determine if operating on full vectors for LOOP_VINFO might leave
some scalar iterations still to do. If so, decide how we should
handle those scalar iterations. The possibilities are:
@@ -2952,21 +3067,18 @@ vect_analyze_loop (class loop *loop, gimple
*loop_vectorized_call,
"bad loop form.\n");
return opt_loop_vec_info::propagate_failure (res);
}
- if (!integer_onep (loop_form_info.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);
- /* 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);
- }
- else
- /* Clear the existing niter information to make sure the nonwrapping flag
- will be calculated and set propriately. */
- free_numbers_of_iterations_estimates (loop);
+
+ res = vect_get_loop_datarefs (loop, shared);
+ if (!res)
+ return opt_loop_vec_info::propagate_failure (res);
+
+ res = vect_build_assumptions (loop, shared, &loop_form_info);
+ if (!res)
+ return opt_loop_vec_info::propagate_failure (res);
+
+ /* vect_build_assumptions can still invalidate a dataref
+ but from here on they are fixed. */
+ shared->save_datarefs ();
auto_vector_modes vector_modes;
/* Autodetect first vector size we try. */
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 2e4756926f2..d23c618d22c 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -2650,6 +2650,7 @@ extern void vect_describe_gather_scatter_call
(stmt_vec_info,
extern opt_result vect_find_stmt_data_reference (loop_p, gimple *,
vec<data_reference_p> *,
vec<int> *, int);
+extern void vect_reset_dr (data_reference *);
extern opt_result vect_analyze_data_refs (vec_info *, bool *);
extern void vect_record_base_alignments (vec_info *);
extern tree vect_create_data_ref_ptr (vec_info *,
--
2.54.0
