Use base inequality for some vector alias checks

This patch checks whether two data references x and y cannot
partially overlap and so are independent whenever &x != &y.
We can then use this in the vectoriser to optimise alias checks.

gcc/
2016-08-04  Richard Sandiford  <richard.sandiford@linaro.org>

	* hash-traits.h (pair_hash): New struct.
	* tree-data-ref.h (data_dependence_relation): Add object_a and
	object_b fields.
	(DDR_OBJECT_A, DDR_OBJECT_B): New macros.
	* tree-data-ref.c (initialize_data_dependence_relation): Initialize
	DDR_OBJECT_A and DDR_OBJECT_B.
	* tree-vectorizer.h (vec_object_pair): New type.
	(_loop_vec_info): Add a check_unequal_addrs field.
	(LOOP_VINFO_CHECK_UNEQUAL_ADDRS): New macro.
	(LOOP_REQUIRES_VERSIONING_FOR_ALIAS): Return true if there is an
	entry in check_unequal_addrs.  Check comp_alias_ddrs instead of
	may_alias_ddrs.
	* tree-vect-loop.c (destroy_loop_vec_info): Release
	LOOP_VINFO_CHECK_UNEQUAL_ADDRS.
	(vect_analyze_loop_2): Likewise, when restarting.
	(vect_estimate_min_profitable_iters): Estimate the cost of
	LOOP_VINFO_CHECK_UNEQUAL_ADDRS.
	* tree-vect-data-refs.c: Include tree-hash-traits.h.
	(vect_prune_runtime_alias_test_list): Try to handle conflicts
	using LOOP_VINFO_CHECK_UNEQUAL_ADDRS, if the data dependence allows.
	Count such tests in the final summary.
	* tree-vect-loop-manip.c (chain_cond_expr): New function.
	(vect_create_cond_for_align_checks): Use it.
	(vect_create_cond_for_unequal_addrs): New function.
	(vect_loop_versioning): Call it.

gcc/testsuite/
	* gcc.dg/vect/vect-alias-check-6.c: New test.

From-SVN: r250868

1 files changed, 10 insertions, 1 deletions

diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index cae0668..01c416c 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -149,6 +149,10 @@ typedef struct _slp_instance {
 
 
 
+/* Describes two objects whose addresses must be unequal for the vectorized
+   loop to be valid.  */
+typedef std::pair<tree, tree> vec_object_pair;
+
 /* Vectorizer state common between loop and basic-block vectorization.  */
 struct vec_info {
   enum { bb, loop } kind;
@@ -245,6 +249,9 @@ typedef struct _loop_vec_info : public vec_info {
      lengths from which the run-time aliasing check is built.  */
   vec<dr_with_seg_len_pair_t> comp_alias_ddrs;
 
+  /* Check that the addresses of each pair of objects is unequal.  */
+  vec<vec_object_pair> check_unequal_addrs;
+
   /* Statements in the loop that have data references that are candidates for a
      runtime (loop versioning) misalignment check.  */
   vec<gimple *> may_misalign_stmts;
@@ -339,6 +346,7 @@ typedef struct _loop_vec_info : public vec_info {
 #define LOOP_VINFO_MAY_MISALIGN_STMTS(L)   (L)->may_misalign_stmts
 #define LOOP_VINFO_MAY_ALIAS_DDRS(L)       (L)->may_alias_ddrs
 #define LOOP_VINFO_COMP_ALIAS_DDRS(L)      (L)->comp_alias_ddrs
+#define LOOP_VINFO_CHECK_UNEQUAL_ADDRS(L)  (L)->check_unequal_addrs
 #define LOOP_VINFO_GROUPED_STORES(L)       (L)->grouped_stores
 #define LOOP_VINFO_SLP_INSTANCES(L)        (L)->slp_instances
 #define LOOP_VINFO_SLP_UNROLLING_FACTOR(L) (L)->slp_unrolling_factor
@@ -358,7 +366,8 @@ typedef struct _loop_vec_info : public vec_info {
 #define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L)	\
   ((L)->may_misalign_stmts.length () > 0)
 #define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L)		\
-  ((L)->comp_alias_ddrs.length () > 0)
+  ((L)->comp_alias_ddrs.length () > 0 \
+   || (L)->check_unequal_addrs.length () > 0)
 #define LOOP_REQUIRES_VERSIONING_FOR_NITERS(L)		\
   (LOOP_VINFO_NITERS_ASSUMPTIONS (L))
 #define LOOP_REQUIRES_VERSIONING(L)			\