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, 70 insertions, 0 deletions

diff --git a/gcc/hash-traits.h b/gcc/hash-traits.h
index f1bfd9f..a5c4f10 100644
--- a/gcc/hash-traits.h
+++ b/gcc/hash-traits.h
@@ -301,6 +301,76 @@ struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
 
 struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
 
+/* Traits for pairs of values, using the first to record empty and
+   deleted slots.  */
+
+template <typename T1, typename T2>
+struct pair_hash
+{
+  typedef std::pair <typename T1::value_type,
+		     typename T2::value_type> value_type;
+  typedef std::pair <typename T1::compare_type,
+		     typename T2::compare_type> compare_type;
+
+  static inline hashval_t hash (const value_type &);
+  static inline bool equal (const value_type &, const compare_type &);
+  static inline void remove (value_type &);
+  static inline void mark_deleted (value_type &);
+  static inline void mark_empty (value_type &);
+  static inline bool is_deleted (const value_type &);
+  static inline bool is_empty (const value_type &);
+};
+
+template <typename T1, typename T2>
+inline hashval_t
+pair_hash <T1, T2>::hash (const value_type &x)
+{
+  return iterative_hash_hashval_t (T1::hash (x.first), T2::hash (x.second));
+}
+
+template <typename T1, typename T2>
+inline bool
+pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
+{
+  return T1::equal (x.first, y.first) && T2::equal (x.second, y.second);
+}
+
+template <typename T1, typename T2>
+inline void
+pair_hash <T1, T2>::remove (value_type &x)
+{
+  T1::remove (x.first);
+  T2::remove (x.second);
+}
+
+template <typename T1, typename T2>
+inline void
+pair_hash <T1, T2>::mark_deleted (value_type &x)
+{
+  T1::mark_deleted (x.first);
+}
+
+template <typename T1, typename T2>
+inline void
+pair_hash <T1, T2>::mark_empty (value_type &x)
+{
+  T1::mark_empty (x.first);
+}
+
+template <typename T1, typename T2>
+inline bool
+pair_hash <T1, T2>::is_deleted (const value_type &x)
+{
+  return T1::is_deleted (x.first);
+}
+
+template <typename T1, typename T2>
+inline bool
+pair_hash <T1, T2>::is_empty (const value_type &x)
+{
+  return T1::is_empty (x.first);
+}
+
 template <typename T> struct default_hash_traits : T {};
 
 template <typename T>