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, 39 insertions, 6 deletions

diff --git a/gcc/tree-vect-loop-manip.c b/gcc/tree-vect-loop-manip.c
index 97080a6..f78e4b4 100644
--- a/gcc/tree-vect-loop-manip.c
+++ b/gcc/tree-vect-loop-manip.c
@@ -1944,6 +1944,19 @@ vect_create_cond_for_niters_checks (loop_vec_info loop_vinfo, tree *cond_expr)
     *cond_expr = part_cond_expr;
 }
 
+/* Set *COND_EXPR to a tree that is true when both the original *COND_EXPR
+   and PART_COND_EXPR are true.  Treat a null *COND_EXPR as "true".  */
+
+static void
+chain_cond_expr (tree *cond_expr, tree part_cond_expr)
+{
+  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.
 
    Create a conditional expression that represents the alignment checks for
@@ -2054,11 +2067,28 @@ vect_create_cond_for_align_checks (loop_vec_info loop_vinfo,
   ptrsize_zero = build_int_cst (int_ptrsize_type, 0);
   part_cond_expr = fold_build2 (EQ_EXPR, boolean_type_node,
 				and_tmp_name, ptrsize_zero);
-  if (*cond_expr)
-    *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
-			      *cond_expr, part_cond_expr);
-  else
-    *cond_expr = part_cond_expr;
+  chain_cond_expr (cond_expr, part_cond_expr);
+}
+
+/* If LOOP_VINFO_CHECK_UNEQUAL_ADDRS contains <A1, B1>, ..., <An, Bn>,
+   create a tree representation of: (&A1 != &B1) && ... && (&An != &Bn).
+   Set *COND_EXPR to a tree that is true when both the original *COND_EXPR
+   and this new condition are true.  Treat a null *COND_EXPR as "true".  */
+
+static void
+vect_create_cond_for_unequal_addrs (loop_vec_info loop_vinfo, tree *cond_expr)
+{
+  vec<vec_object_pair> pairs = LOOP_VINFO_CHECK_UNEQUAL_ADDRS (loop_vinfo);
+  unsigned int i;
+  vec_object_pair *pair;
+  FOR_EACH_VEC_ELT (pairs, i, pair)
+    {
+      tree addr1 = build_fold_addr_expr (pair->first);
+      tree addr2 = build_fold_addr_expr (pair->second);
+      tree part_cond_expr = fold_build2 (NE_EXPR, boolean_type_node,
+					 addr1, addr2);
+      chain_cond_expr (cond_expr, part_cond_expr);
+    }
 }
 
 /* Function vect_create_cond_for_alias_checks.
@@ -2158,7 +2188,10 @@ vect_loop_versioning (loop_vec_info loop_vinfo,
 				       &cond_expr_stmt_list);
 
   if (version_alias)
-    vect_create_cond_for_alias_checks (loop_vinfo, &cond_expr);
+    {
+      vect_create_cond_for_unequal_addrs (loop_vinfo, &cond_expr);
+      vect_create_cond_for_alias_checks (loop_vinfo, &cond_expr);
+    }
 
   cond_expr = force_gimple_operand_1 (cond_expr, &gimplify_stmt_list,
 				      is_gimple_condexpr, NULL_TREE);