public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH GCC][2/6]Factor out code pruning runtime alias checks
@ 2017-05-23 16:23 Bin Cheng
  2017-05-26 11:16 ` Richard Biener
  0 siblings, 1 reply; 3+ messages in thread
From: Bin Cheng @ 2017-05-23 16:23 UTC (permalink / raw)
  To: gcc-patches; +Cc: nd

[-- Attachment #1: Type: text/plain, Size: 962 bytes --]

Hi,
This is the second patch in the set, it factors out code pruning runtime alias
checks from file tree-vect-data-refs.c to tree-data-ref.c.  It also introduces
new interface prune_runtime_alias_test_list so that we can use it in pass like
loop distribution.
Bootstrap and test on x86_64 and AArch64, is it OK?

Thanks,
bin
2017-05-22  Bin Cheng  <bin.cheng@arm.com>

	* tree-vect-data-refs.c (Operator==, comp_dr_with_seg_len_pair):
	Move from ...
	* tree-data-ref.c (Operator==, comp_dr_with_seg_len_pair): To here.
	* tree-vect-data-refs.c (vect_prune_runtime_alias_test_list): Factor
	out code pruning runtime alias checks.
	* tree-data-ref.c (prune_runtime_alias_test_list): New function
	factored out from above.
	* tree-vectorizer.h (struct dr_with_seg_len, dr_with_seg_len_pair_t):
	Move from ...
	* tree-data-ref.h (struct dr_with_seg_len, dr_with_seg_len_pair_t):
	... to here.
	(prune_runtime_alias_test_list): New decalaration.

[-- Attachment #2: 0002-prune-runtime-alias-check-20170516.txt --]
[-- Type: text/plain, Size: 21661 bytes --]

From 030967c7b1d6af95f2becd1159dad7823cdaecd9 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Tue, 23 May 2017 17:11:19 +0100
Subject: [PATCH 2/6] prune-runtime-alias-check-20170516

---
 gcc/tree-data-ref.c       | 233 ++++++++++++++++++++++++++++++++++++++++++++++
 gcc/tree-data-ref.h       |  28 ++++++
 gcc/tree-vect-data-refs.c | 228 +--------------------------------------------
 gcc/tree-vectorizer.h     |  28 ------
 4 files changed, 263 insertions(+), 254 deletions(-)

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 2480f4e..a5f8c1c 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1107,6 +1107,239 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt,
   return dr;
 }
 
+/* Operator == between two dr_with_seg_len objects.
+
+   This equality operator is used to make sure two data refs
+   are the same one so that we will consider to combine the
+   aliasing checks of those two pairs of data dependent data
+   refs.  */
+
+static bool
+operator == (const dr_with_seg_len& d1,
+	     const dr_with_seg_len& d2)
+{
+  return operand_equal_p (DR_BASE_ADDRESS (d1.dr),
+			  DR_BASE_ADDRESS (d2.dr), 0)
+	   && compare_tree (DR_OFFSET (d1.dr), DR_OFFSET (d2.dr)) == 0
+	   && compare_tree (DR_INIT (d1.dr), DR_INIT (d2.dr)) == 0
+	   && compare_tree (d1.seg_len, d2.seg_len) == 0;
+}
+
+/* Comparison function for sorting objects of dr_with_seg_len_pair_t
+   so that we can combine aliasing checks in one scan.  */
+
+static int
+comp_dr_with_seg_len_pair (const void *pa_, const void *pb_)
+{
+  const dr_with_seg_len_pair_t* pa = (const dr_with_seg_len_pair_t *) pa_;
+  const dr_with_seg_len_pair_t* pb = (const dr_with_seg_len_pair_t *) pb_;
+  const dr_with_seg_len &a1 = pa->first, &a2 = pa->second;
+  const dr_with_seg_len &b1 = pb->first, &b2 = pb->second;
+
+  /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks
+     if a and c have the same basic address snd step, and b and d have the same
+     address and step.  Therefore, if any a&c or b&d don't have the same address
+     and step, we don't care the order of those two pairs after sorting.  */
+  int comp_res;
+
+  if ((comp_res = compare_tree (DR_BASE_ADDRESS (a1.dr),
+				DR_BASE_ADDRESS (b1.dr))) != 0)
+    return comp_res;
+  if ((comp_res = compare_tree (DR_BASE_ADDRESS (a2.dr),
+				DR_BASE_ADDRESS (b2.dr))) != 0)
+    return comp_res;
+  if ((comp_res = compare_tree (DR_STEP (a1.dr), DR_STEP (b1.dr))) != 0)
+    return comp_res;
+  if ((comp_res = compare_tree (DR_STEP (a2.dr), DR_STEP (b2.dr))) != 0)
+    return comp_res;
+  if ((comp_res = compare_tree (DR_OFFSET (a1.dr), DR_OFFSET (b1.dr))) != 0)
+    return comp_res;
+  if ((comp_res = compare_tree (DR_INIT (a1.dr), DR_INIT (b1.dr))) != 0)
+    return comp_res;
+  if ((comp_res = compare_tree (DR_OFFSET (a2.dr), DR_OFFSET (b2.dr))) != 0)
+    return comp_res;
+  if ((comp_res = compare_tree (DR_INIT (a2.dr), DR_INIT (b2.dr))) != 0)
+    return comp_res;
+
+  return 0;
+}
+
+/* Merge alias checks recorded in ALIAS_PAIRS and remove redundant ones.
+   FACTOR is number of iterations that each data reference is accessed.
+
+   Basically, for each pair of dependent data refs store_ptr_0 & load_ptr_0,
+   we create an expression:
+
+   ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
+   || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
+
+   for aliasing checks.  However, in some cases we can decrease the number
+   of checks by combining two checks into one.  For example, suppose we have
+   another pair of data refs store_ptr_0 & load_ptr_1, and if the following
+   condition is satisfied:
+
+   load_ptr_0 < load_ptr_1  &&
+   load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0
+
+   (this condition means, in each iteration of vectorized loop, the accessed
+   memory of store_ptr_0 cannot be between the memory of load_ptr_0 and
+   load_ptr_1.)
+
+   we then can use only the following expression to finish the alising checks
+   between store_ptr_0 & load_ptr_0 and store_ptr_0 & load_ptr_1:
+
+   ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
+   || (load_ptr_1 + load_segment_length_1 <= store_ptr_0))
+
+   Note that we only consider that load_ptr_0 and load_ptr_1 have the same
+   basic address.  */
+
+void
+prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs,
+			       unsigned HOST_WIDE_INT factor)
+{
+  /* Sort the collected data ref pairs so that we can scan them once to
+     combine all possible aliasing checks.  */
+  alias_pairs->qsort (comp_dr_with_seg_len_pair);
+
+  /* Scan the sorted dr pairs and check if we can combine alias checks
+     of two neighboring dr pairs.  */
+  for (size_t i = 1; i < alias_pairs->length (); ++i)
+    {
+      /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2).  */
+      dr_with_seg_len *dr_a1 = &(*alias_pairs)[i-1].first,
+		      *dr_b1 = &(*alias_pairs)[i-1].second,
+		      *dr_a2 = &(*alias_pairs)[i].first,
+		      *dr_b2 = &(*alias_pairs)[i].second;
+
+      /* Remove duplicate data ref pairs.  */
+      if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2)
+	{
+	  if (dump_enabled_p ())
+	    {
+	      dump_printf (MSG_NOTE, "found equal ranges ");
+	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr));
+	      dump_printf (MSG_NOTE,  ", ");
+	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr));
+	      dump_printf (MSG_NOTE,  " and ");
+	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr));
+	      dump_printf (MSG_NOTE,  ", ");
+	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
+	      dump_printf (MSG_NOTE, "\n");
+	    }
+	  alias_pairs->ordered_remove (i--);
+	  continue;
+	}
+
+      if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2)
+	{
+	  /* We consider the case that DR_B1 and DR_B2 are same memrefs,
+	     and DR_A1 and DR_A2 are two consecutive memrefs.  */
+	  if (*dr_a1 == *dr_a2)
+	    {
+	      std::swap (dr_a1, dr_b1);
+	      std::swap (dr_a2, dr_b2);
+	    }
+
+	  if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
+				DR_BASE_ADDRESS (dr_a2->dr), 0)
+	      || !operand_equal_p (DR_OFFSET (dr_a1->dr),
+				   DR_OFFSET (dr_a2->dr), 0)
+	      || !tree_fits_shwi_p (DR_INIT (dr_a1->dr))
+	      || !tree_fits_shwi_p (DR_INIT (dr_a2->dr)))
+	    continue;
+
+	  /* Only merge const step data references.  */
+	  if (TREE_CODE (DR_STEP (dr_a1->dr)) != INTEGER_CST
+	      || TREE_CODE (DR_STEP (dr_a2->dr)) != INTEGER_CST)
+	    continue;
+
+	  /* DR_A1 and DR_A2 must goes in the same direction.  */
+	  if (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node)
+	      != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node))
+	    continue;
+
+	  /* Make sure dr_a1 starts left of dr_a2.  */
+	  if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
+	    std::swap (*dr_a1, *dr_a2);
+
+	  bool do_remove = false;
+	  unsigned HOST_WIDE_INT diff
+	    = (tree_to_shwi (DR_INIT (dr_a2->dr))
+               - tree_to_shwi (DR_INIT (dr_a1->dr)));
+
+	  /* If the left segment does not extend beyond the start of the
+	     right segment the new segment length is that of the right
+	     plus the segment distance.  */
+	  if (tree_fits_uhwi_p (dr_a1->seg_len)
+	      && compare_tree_int (dr_a1->seg_len, diff) <= 0)
+	    {
+	      dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
+					   size_int (diff));
+	      do_remove = true;
+	    }
+	  /* Generally the new segment length is the maximum of the
+	     left segment size and the right segment size plus the distance.
+	     ???  We can also build tree MAX_EXPR here but it's not clear this
+	     is profitable.  */
+	  else if (tree_fits_uhwi_p (dr_a1->seg_len)
+		   && tree_fits_uhwi_p (dr_a2->seg_len))
+	    {
+	      unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len);
+	      unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len);
+	      dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2));
+	      do_remove = true;
+	    }
+	  /* Now we check if the following condition is satisfied:
+
+	     DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
+
+	     where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
+	     SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
+	     have to make a best estimation.  We can get the minimum value
+	     of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
+	     then either of the following two conditions can guarantee the
+	     one above:
+
+	     1: DIFF <= MIN_SEG_LEN_B
+	     2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B  */
+	  else
+	    {
+	      unsigned HOST_WIDE_INT min_seg_len_b
+		= (tree_fits_uhwi_p (dr_b1->seg_len)
+		   ? tree_to_uhwi (dr_b1->seg_len)
+		   : factor);
+
+	      if (diff <= min_seg_len_b
+		  || (tree_fits_uhwi_p (dr_a1->seg_len)
+		      && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b))
+		{
+		  dr_a1->seg_len = size_binop (PLUS_EXPR,
+					       dr_a2->seg_len, size_int (diff));
+		  do_remove = true;
+		}
+	    }
+
+	  if (do_remove)
+	    {
+	      if (dump_enabled_p ())
+		{
+		  dump_printf (MSG_NOTE, "merging ranges for ");
+		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr));
+		  dump_printf (MSG_NOTE,  ", ");
+		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr));
+		  dump_printf (MSG_NOTE,  " and ");
+		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr));
+		  dump_printf (MSG_NOTE,  ", ");
+		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
+		  dump_printf (MSG_NOTE, "\n");
+		}
+	      alias_pairs->ordered_remove (i--);
+	    }
+	}
+    }
+}
+
 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
    expressions.  */
 static bool
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index 3a54120..75c32b3 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -148,6 +148,32 @@ struct data_reference
 
 typedef struct data_reference *data_reference_p;
 
+/* This struct is used to store the information of a data reference,
+   including the data ref itself and the segment length for aliasing
+   checks.  This is used to merge alias checks.  */
+
+struct dr_with_seg_len
+{
+  dr_with_seg_len (data_reference_p d, tree len)
+    : dr (d), seg_len (len) {}
+
+  data_reference_p dr;
+  tree seg_len;
+};
+
+/* This struct contains two dr_with_seg_len objects with aliasing data
+   refs.  Two comparisons are generated from them.  */
+
+struct dr_with_seg_len_pair_t
+{
+  dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
+			       const dr_with_seg_len& d2)
+    : first (d1), second (d2) {}
+
+  dr_with_seg_len first;
+  dr_with_seg_len second;
+};
+
 enum data_dependence_direction {
   dir_positive,
   dir_negative,
@@ -342,6 +368,8 @@ extern bool dr_may_alias_p (const struct data_reference *,
 extern bool dr_equal_offsets_p (struct data_reference *,
                                 struct data_reference *);
 
+extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
+					   unsigned HOST_WIDE_INT);
 /* Return true when the base objects of data references A and B are
    the same memory object.  */
 
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index 7b835ae..06580f0 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -2813,66 +2813,6 @@ vect_analyze_data_ref_accesses (vec_info *vinfo)
   return true;
 }
 
-
-/* Operator == between two dr_with_seg_len objects.
-
-   This equality operator is used to make sure two data refs
-   are the same one so that we will consider to combine the
-   aliasing checks of those two pairs of data dependent data
-   refs.  */
-
-static bool
-operator == (const dr_with_seg_len& d1,
-	     const dr_with_seg_len& d2)
-{
-  return operand_equal_p (DR_BASE_ADDRESS (d1.dr),
-			  DR_BASE_ADDRESS (d2.dr), 0)
-	   && compare_tree (DR_OFFSET (d1.dr), DR_OFFSET (d2.dr)) == 0
-	   && compare_tree (DR_INIT (d1.dr), DR_INIT (d2.dr)) == 0
-	   && compare_tree (d1.seg_len, d2.seg_len) == 0;
-}
-
-/* Function comp_dr_with_seg_len_pair.
-
-   Comparison function for sorting objects of dr_with_seg_len_pair_t
-   so that we can combine aliasing checks in one scan.  */
-
-static int
-comp_dr_with_seg_len_pair (const void *pa_, const void *pb_)
-{
-  const dr_with_seg_len_pair_t* pa = (const dr_with_seg_len_pair_t *) pa_;
-  const dr_with_seg_len_pair_t* pb = (const dr_with_seg_len_pair_t *) pb_;
-  const dr_with_seg_len &a1 = pa->first, &a2 = pa->second;
-  const dr_with_seg_len &b1 = pb->first, &b2 = pb->second;
-
-  /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks
-     if a and c have the same basic address snd step, and b and d have the same
-     address and step.  Therefore, if any a&c or b&d don't have the same address
-     and step, we don't care the order of those two pairs after sorting.  */
-  int comp_res;
-
-  if ((comp_res = compare_tree (DR_BASE_ADDRESS (a1.dr),
-				DR_BASE_ADDRESS (b1.dr))) != 0)
-    return comp_res;
-  if ((comp_res = compare_tree (DR_BASE_ADDRESS (a2.dr),
-				DR_BASE_ADDRESS (b2.dr))) != 0)
-    return comp_res;
-  if ((comp_res = compare_tree (DR_STEP (a1.dr), DR_STEP (b1.dr))) != 0)
-    return comp_res;
-  if ((comp_res = compare_tree (DR_STEP (a2.dr), DR_STEP (b2.dr))) != 0)
-    return comp_res;
-  if ((comp_res = compare_tree (DR_OFFSET (a1.dr), DR_OFFSET (b1.dr))) != 0)
-    return comp_res;
-  if ((comp_res = compare_tree (DR_INIT (a1.dr), DR_INIT (b1.dr))) != 0)
-    return comp_res;
-  if ((comp_res = compare_tree (DR_OFFSET (a2.dr), DR_OFFSET (b2.dr))) != 0)
-    return comp_res;
-  if ((comp_res = compare_tree (DR_INIT (a2.dr), DR_INIT (b2.dr))) != 0)
-    return comp_res;
-
-  return 0;
-}
-
 /* Function vect_vfa_segment_size.
 
    Create an expression that computes the size of segment
@@ -2987,34 +2927,6 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo)
   if (may_alias_ddrs.is_empty ())
     return true;
 
-  /* Basically, for each pair of dependent data refs store_ptr_0
-     and load_ptr_0, we create an expression:
-
-     ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
-     || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
-
-     for aliasing checks.  However, in some cases we can decrease
-     the number of checks by combining two checks into one.  For
-     example, suppose we have another pair of data refs store_ptr_0
-     and load_ptr_1, and if the following condition is satisfied:
-
-     load_ptr_0 < load_ptr_1  &&
-     load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0
-
-     (this condition means, in each iteration of vectorized loop,
-     the accessed memory of store_ptr_0 cannot be between the memory
-     of load_ptr_0 and load_ptr_1.)
-
-     we then can use only the following expression to finish the
-     alising checks between store_ptr_0 & load_ptr_0 and
-     store_ptr_0 & load_ptr_1:
-
-     ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
-     || (load_ptr_1 + load_segment_length_1 <= store_ptr_0))
-
-     Note that we only consider that load_ptr_0 and load_ptr_1 have the
-     same basic address.  */
-
   comp_alias_ddrs.create (may_alias_ddrs.length ());
 
   /* First, we collect all data ref pairs for aliasing checks.  */
@@ -3083,144 +2995,8 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo)
       comp_alias_ddrs.safe_push (dr_with_seg_len_pair);
     }
 
-  /* Second, we sort the collected data ref pairs so that we can scan
-     them once to combine all possible aliasing checks.  */
-  comp_alias_ddrs.qsort (comp_dr_with_seg_len_pair);
-
-  /* Third, we scan the sorted dr pairs and check if we can combine
-     alias checks of two neighboring dr pairs.  */
-  for (size_t i = 1; i < comp_alias_ddrs.length (); ++i)
-    {
-      /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2).  */
-      dr_with_seg_len *dr_a1 = &comp_alias_ddrs[i-1].first,
-		      *dr_b1 = &comp_alias_ddrs[i-1].second,
-		      *dr_a2 = &comp_alias_ddrs[i].first,
-		      *dr_b2 = &comp_alias_ddrs[i].second;
-
-      /* Remove duplicate data ref pairs.  */
-      if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2)
-	{
-	  if (dump_enabled_p ())
-	    {
-	      dump_printf_loc (MSG_NOTE, vect_location,
-			       "found equal ranges ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM,
-				 DR_REF (dr_a1->dr));
-	      dump_printf (MSG_NOTE,  ", ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM,
-				 DR_REF (dr_b1->dr));
-	      dump_printf (MSG_NOTE,  " and ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM,
-				 DR_REF (dr_a2->dr));
-	      dump_printf (MSG_NOTE,  ", ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM,
-				 DR_REF (dr_b2->dr));
-	      dump_printf (MSG_NOTE, "\n");
-	    }
-
-	  comp_alias_ddrs.ordered_remove (i--);
-	  continue;
-	}
-
-      if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2)
-	{
-	  /* We consider the case that DR_B1 and DR_B2 are same memrefs,
-	     and DR_A1 and DR_A2 are two consecutive memrefs.  */
-	  if (*dr_a1 == *dr_a2)
-	    {
-	      std::swap (dr_a1, dr_b1);
-	      std::swap (dr_a2, dr_b2);
-	    }
-
-	  if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
-				DR_BASE_ADDRESS (dr_a2->dr), 0)
-	      || !operand_equal_p (DR_OFFSET (dr_a1->dr),
-				   DR_OFFSET (dr_a2->dr), 0)
-	      || !tree_fits_shwi_p (DR_INIT (dr_a1->dr))
-	      || !tree_fits_shwi_p (DR_INIT (dr_a2->dr)))
-	    continue;
-
-	  /* Make sure dr_a1 starts left of dr_a2.  */
-	  if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
-	    std::swap (*dr_a1, *dr_a2);
-
-	  bool do_remove = false;
-	  unsigned HOST_WIDE_INT diff
-	    = (tree_to_shwi (DR_INIT (dr_a2->dr))
-               - tree_to_shwi (DR_INIT (dr_a1->dr)));
-
-	  /* If the left segment does not extend beyond the start of the
-	     right segment the new segment length is that of the right
-	     plus the segment distance.  */
-	  if (tree_fits_uhwi_p (dr_a1->seg_len)
-	      && compare_tree_int (dr_a1->seg_len, diff) <= 0)
-	    {
-	      dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
-					   size_int (diff));
-	      do_remove = true;
-	    }
-	  /* Generally the new segment length is the maximum of the
-	     left segment size and the right segment size plus the distance.
-	     ???  We can also build tree MAX_EXPR here but it's not clear this
-	     is profitable.  */
-	  else if (tree_fits_uhwi_p (dr_a1->seg_len)
-		   && tree_fits_uhwi_p (dr_a2->seg_len))
-	    {
-	      unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len);
-	      unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len);
-	      dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2));
-	      do_remove = true;
-	    }
-	  /* Now we check if the following condition is satisfied:
-
-	     DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
-
-	     where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
-	     SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
-	     have to make a best estimation.  We can get the minimum value
-	     of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
-	     then either of the following two conditions can guarantee the
-	     one above:
-
-	     1: DIFF <= MIN_SEG_LEN_B
-	     2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B  */
-	  else
-	    {
-	      unsigned HOST_WIDE_INT min_seg_len_b
-		= (tree_fits_uhwi_p (dr_b1->seg_len)
-		   ? tree_to_uhwi (dr_b1->seg_len)
-		   : vect_factor);
-
-	      if (diff <= min_seg_len_b
-		  || (tree_fits_uhwi_p (dr_a1->seg_len)
-		      && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b))
-		{
-		  dr_a1->seg_len = size_binop (PLUS_EXPR,
-					       dr_a2->seg_len, size_int (diff));
-		  do_remove = true;
-		}
-	    }
-
-	  if (do_remove)
-	    {
-	      if (dump_enabled_p ())
-		{
-		  dump_printf_loc (MSG_NOTE, vect_location,
-				   "merging ranges for ");
-		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr));
-		  dump_printf (MSG_NOTE,  ", ");
-		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr));
-		  dump_printf (MSG_NOTE,  " and ");
-		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr));
-		  dump_printf (MSG_NOTE,  ", ");
-		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
-		  dump_printf (MSG_NOTE, "\n");
-		}
-	      comp_alias_ddrs.ordered_remove (i--);
-	    }
-	}
-    }
-
+  prune_runtime_alias_test_list (&comp_alias_ddrs,
+				 (unsigned HOST_WIDE_INT) vect_factor);
   dump_printf_loc (MSG_NOTE, vect_location,
 		   "improved number of alias checks from %d to %d\n",
 		   may_alias_ddrs.length (), comp_alias_ddrs.length ());
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 12bb904..7978bbd 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -146,34 +146,6 @@ typedef struct _slp_instance {
 
 
 
-/* This struct is used to store the information of a data reference,
-   including the data ref itself and the segment length for aliasing
-   checks.  This is used to merge alias checks.  */
-
-struct dr_with_seg_len
-{
-  dr_with_seg_len (data_reference_p d, tree len)
-    : dr (d), seg_len (len) {}
-
-  data_reference_p dr;
-  tree seg_len;
-};
-
-/* This struct contains two dr_with_seg_len objects with aliasing data
-   refs.  Two comparisons are generated from them.  */
-
-struct dr_with_seg_len_pair_t
-{
-  dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
-			       const dr_with_seg_len& d2)
-    : first (d1), second (d2) {}
-
-  dr_with_seg_len first;
-  dr_with_seg_len second;
-};
-
-
-
 /* Vectorizer state common between loop and basic-block vectorization.  */
 struct vec_info {
   enum { bb, loop } kind;
-- 
1.9.1


^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH GCC][2/6]Factor out code pruning runtime alias checks
  2017-05-23 16:23 [PATCH GCC][2/6]Factor out code pruning runtime alias checks Bin Cheng
@ 2017-05-26 11:16 ` Richard Biener
  2017-05-26 14:19   ` Bin.Cheng
  0 siblings, 1 reply; 3+ messages in thread
From: Richard Biener @ 2017-05-26 11:16 UTC (permalink / raw)
  To: Bin Cheng; +Cc: gcc-patches, nd

On Tue, May 23, 2017 at 6:22 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> This is the second patch in the set, it factors out code pruning runtime alias
> checks from file tree-vect-data-refs.c to tree-data-ref.c.  It also introduces
> new interface prune_runtime_alias_test_list so that we can use it in pass like
> loop distribution.
> Bootstrap and test on x86_64 and AArch64, is it OK?

Ok.
Richard.

> Thanks,
> bin
> 2017-05-22  Bin Cheng  <bin.cheng@arm.com>
>
>         * tree-vect-data-refs.c (Operator==, comp_dr_with_seg_len_pair):
>         Move from ...
>         * tree-data-ref.c (Operator==, comp_dr_with_seg_len_pair): To here.
>         * tree-vect-data-refs.c (vect_prune_runtime_alias_test_list): Factor
>         out code pruning runtime alias checks.
>         * tree-data-ref.c (prune_runtime_alias_test_list): New function
>         factored out from above.
>         * tree-vectorizer.h (struct dr_with_seg_len, dr_with_seg_len_pair_t):
>         Move from ...
>         * tree-data-ref.h (struct dr_with_seg_len, dr_with_seg_len_pair_t):
>         ... to here.
>         (prune_runtime_alias_test_list): New decalaration.

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH GCC][2/6]Factor out code pruning runtime alias checks
  2017-05-26 11:16 ` Richard Biener
@ 2017-05-26 14:19   ` Bin.Cheng
  0 siblings, 0 replies; 3+ messages in thread
From: Bin.Cheng @ 2017-05-26 14:19 UTC (permalink / raw)
  To: Richard Biener; +Cc: Bin Cheng, gcc-patches, nd

[-- Attachment #1: Type: text/plain, Size: 1348 bytes --]

On Fri, May 26, 2017 at 12:15 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, May 23, 2017 at 6:22 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>> Hi,
>> This is the second patch in the set, it factors out code pruning runtime alias
>> checks from file tree-vect-data-refs.c to tree-data-ref.c.  It also introduces
>> new interface prune_runtime_alias_test_list so that we can use it in pass like
>> loop distribution.
>> Bootstrap and test on x86_64 and AArch64, is it OK?
>
> Ok.
Updated and committed attached patch wrto change in previous patch.

Thanks,
bin
> Richard.
>
>> Thanks,
>> bin
>> 2017-05-22  Bin Cheng  <bin.cheng@arm.com>
>>
>>         * tree-vect-data-refs.c (Operator==, comp_dr_with_seg_len_pair):
>>         Move from ...
>>         * tree-data-ref.c (Operator==, comp_dr_with_seg_len_pair): To here.
>>         * tree-vect-data-refs.c (vect_prune_runtime_alias_test_list): Factor
>>         out code pruning runtime alias checks.
>>         * tree-data-ref.c (prune_runtime_alias_test_list): New function
>>         factored out from above.
>>         * tree-vectorizer.h (struct dr_with_seg_len, dr_with_seg_len_pair_t):
>>         Move from ...
>>         * tree-data-ref.h (struct dr_with_seg_len, dr_with_seg_len_pair_t):
>>         ... to here.
>>         (prune_runtime_alias_test_list): New decalaration.

[-- Attachment #2: 0002-prune-runtime-alias-check-20170517.txt --]
[-- Type: text/plain, Size: 21909 bytes --]

From 24c5a33279731fafb1f6500acbd39a4d079fc2c5 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Tue, 23 May 2017 17:11:19 +0100
Subject: [PATCH 2/6] prune-runtime-alias-check-20170517.txt

---
 gcc/tree-data-ref.c       | 239 ++++++++++++++++++++++++++++++++++++++++++++++
 gcc/tree-data-ref.h       |  28 ++++++
 gcc/tree-vect-data-refs.c | 234 +--------------------------------------------
 gcc/tree-vectorizer.h     |  28 ------
 4 files changed, 269 insertions(+), 260 deletions(-)

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 6a32a65..671da4e 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1182,6 +1182,245 @@ data_ref_compare_tree (tree t1, tree t2)
   return 0;
 }
 
+/* Operator == between two dr_with_seg_len objects.
+
+   This equality operator is used to make sure two data refs
+   are the same one so that we will consider to combine the
+   aliasing checks of those two pairs of data dependent data
+   refs.  */
+
+static bool
+operator == (const dr_with_seg_len& d1,
+	     const dr_with_seg_len& d2)
+{
+  return operand_equal_p (DR_BASE_ADDRESS (d1.dr),
+			  DR_BASE_ADDRESS (d2.dr), 0)
+	   && data_ref_compare_tree (DR_OFFSET (d1.dr), DR_OFFSET (d2.dr)) == 0
+	   && data_ref_compare_tree (DR_INIT (d1.dr), DR_INIT (d2.dr)) == 0
+	   && data_ref_compare_tree (d1.seg_len, d2.seg_len) == 0;
+}
+
+/* Comparison function for sorting objects of dr_with_seg_len_pair_t
+   so that we can combine aliasing checks in one scan.  */
+
+static int
+comp_dr_with_seg_len_pair (const void *pa_, const void *pb_)
+{
+  const dr_with_seg_len_pair_t* pa = (const dr_with_seg_len_pair_t *) pa_;
+  const dr_with_seg_len_pair_t* pb = (const dr_with_seg_len_pair_t *) pb_;
+  const dr_with_seg_len &a1 = pa->first, &a2 = pa->second;
+  const dr_with_seg_len &b1 = pb->first, &b2 = pb->second;
+
+  /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks
+     if a and c have the same basic address snd step, and b and d have the same
+     address and step.  Therefore, if any a&c or b&d don't have the same address
+     and step, we don't care the order of those two pairs after sorting.  */
+  int comp_res;
+
+  if ((comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (a1.dr),
+					 DR_BASE_ADDRESS (b1.dr))) != 0)
+    return comp_res;
+  if ((comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (a2.dr),
+					 DR_BASE_ADDRESS (b2.dr))) != 0)
+    return comp_res;
+  if ((comp_res = data_ref_compare_tree (DR_STEP (a1.dr),
+					 DR_STEP (b1.dr))) != 0)
+    return comp_res;
+  if ((comp_res = data_ref_compare_tree (DR_STEP (a2.dr),
+					 DR_STEP (b2.dr))) != 0)
+    return comp_res;
+  if ((comp_res = data_ref_compare_tree (DR_OFFSET (a1.dr),
+					 DR_OFFSET (b1.dr))) != 0)
+    return comp_res;
+  if ((comp_res = data_ref_compare_tree (DR_INIT (a1.dr),
+					 DR_INIT (b1.dr))) != 0)
+    return comp_res;
+  if ((comp_res = data_ref_compare_tree (DR_OFFSET (a2.dr),
+					 DR_OFFSET (b2.dr))) != 0)
+    return comp_res;
+  if ((comp_res = data_ref_compare_tree (DR_INIT (a2.dr),
+					 DR_INIT (b2.dr))) != 0)
+    return comp_res;
+
+  return 0;
+}
+
+/* Merge alias checks recorded in ALIAS_PAIRS and remove redundant ones.
+   FACTOR is number of iterations that each data reference is accessed.
+
+   Basically, for each pair of dependent data refs store_ptr_0 & load_ptr_0,
+   we create an expression:
+
+   ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
+   || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
+
+   for aliasing checks.  However, in some cases we can decrease the number
+   of checks by combining two checks into one.  For example, suppose we have
+   another pair of data refs store_ptr_0 & load_ptr_1, and if the following
+   condition is satisfied:
+
+   load_ptr_0 < load_ptr_1  &&
+   load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0
+
+   (this condition means, in each iteration of vectorized loop, the accessed
+   memory of store_ptr_0 cannot be between the memory of load_ptr_0 and
+   load_ptr_1.)
+
+   we then can use only the following expression to finish the alising checks
+   between store_ptr_0 & load_ptr_0 and store_ptr_0 & load_ptr_1:
+
+   ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
+   || (load_ptr_1 + load_segment_length_1 <= store_ptr_0))
+
+   Note that we only consider that load_ptr_0 and load_ptr_1 have the same
+   basic address.  */
+
+void
+prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *alias_pairs,
+			       unsigned HOST_WIDE_INT factor)
+{
+  /* Sort the collected data ref pairs so that we can scan them once to
+     combine all possible aliasing checks.  */
+  alias_pairs->qsort (comp_dr_with_seg_len_pair);
+
+  /* Scan the sorted dr pairs and check if we can combine alias checks
+     of two neighboring dr pairs.  */
+  for (size_t i = 1; i < alias_pairs->length (); ++i)
+    {
+      /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2).  */
+      dr_with_seg_len *dr_a1 = &(*alias_pairs)[i-1].first,
+		      *dr_b1 = &(*alias_pairs)[i-1].second,
+		      *dr_a2 = &(*alias_pairs)[i].first,
+		      *dr_b2 = &(*alias_pairs)[i].second;
+
+      /* Remove duplicate data ref pairs.  */
+      if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2)
+	{
+	  if (dump_enabled_p ())
+	    {
+	      dump_printf (MSG_NOTE, "found equal ranges ");
+	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr));
+	      dump_printf (MSG_NOTE,  ", ");
+	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr));
+	      dump_printf (MSG_NOTE,  " and ");
+	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr));
+	      dump_printf (MSG_NOTE,  ", ");
+	      dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
+	      dump_printf (MSG_NOTE, "\n");
+	    }
+	  alias_pairs->ordered_remove (i--);
+	  continue;
+	}
+
+      if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2)
+	{
+	  /* We consider the case that DR_B1 and DR_B2 are same memrefs,
+	     and DR_A1 and DR_A2 are two consecutive memrefs.  */
+	  if (*dr_a1 == *dr_a2)
+	    {
+	      std::swap (dr_a1, dr_b1);
+	      std::swap (dr_a2, dr_b2);
+	    }
+
+	  if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
+				DR_BASE_ADDRESS (dr_a2->dr), 0)
+	      || !operand_equal_p (DR_OFFSET (dr_a1->dr),
+				   DR_OFFSET (dr_a2->dr), 0)
+	      || !tree_fits_shwi_p (DR_INIT (dr_a1->dr))
+	      || !tree_fits_shwi_p (DR_INIT (dr_a2->dr)))
+	    continue;
+
+	  /* Only merge const step data references.  */
+	  if (TREE_CODE (DR_STEP (dr_a1->dr)) != INTEGER_CST
+	      || TREE_CODE (DR_STEP (dr_a2->dr)) != INTEGER_CST)
+	    continue;
+
+	  /* DR_A1 and DR_A2 must goes in the same direction.  */
+	  if (tree_int_cst_compare (DR_STEP (dr_a1->dr), size_zero_node)
+	      != tree_int_cst_compare (DR_STEP (dr_a2->dr), size_zero_node))
+	    continue;
+
+	  /* Make sure dr_a1 starts left of dr_a2.  */
+	  if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
+	    std::swap (*dr_a1, *dr_a2);
+
+	  bool do_remove = false;
+	  unsigned HOST_WIDE_INT diff
+	    = (tree_to_shwi (DR_INIT (dr_a2->dr))
+               - tree_to_shwi (DR_INIT (dr_a1->dr)));
+
+	  /* If the left segment does not extend beyond the start of the
+	     right segment the new segment length is that of the right
+	     plus the segment distance.  */
+	  if (tree_fits_uhwi_p (dr_a1->seg_len)
+	      && compare_tree_int (dr_a1->seg_len, diff) <= 0)
+	    {
+	      dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
+					   size_int (diff));
+	      do_remove = true;
+	    }
+	  /* Generally the new segment length is the maximum of the
+	     left segment size and the right segment size plus the distance.
+	     ???  We can also build tree MAX_EXPR here but it's not clear this
+	     is profitable.  */
+	  else if (tree_fits_uhwi_p (dr_a1->seg_len)
+		   && tree_fits_uhwi_p (dr_a2->seg_len))
+	    {
+	      unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len);
+	      unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len);
+	      dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2));
+	      do_remove = true;
+	    }
+	  /* Now we check if the following condition is satisfied:
+
+	     DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
+
+	     where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
+	     SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
+	     have to make a best estimation.  We can get the minimum value
+	     of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
+	     then either of the following two conditions can guarantee the
+	     one above:
+
+	     1: DIFF <= MIN_SEG_LEN_B
+	     2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B  */
+	  else
+	    {
+	      unsigned HOST_WIDE_INT min_seg_len_b
+		= (tree_fits_uhwi_p (dr_b1->seg_len)
+		   ? tree_to_uhwi (dr_b1->seg_len)
+		   : factor);
+
+	      if (diff <= min_seg_len_b
+		  || (tree_fits_uhwi_p (dr_a1->seg_len)
+		      && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b))
+		{
+		  dr_a1->seg_len = size_binop (PLUS_EXPR,
+					       dr_a2->seg_len, size_int (diff));
+		  do_remove = true;
+		}
+	    }
+
+	  if (do_remove)
+	    {
+	      if (dump_enabled_p ())
+		{
+		  dump_printf (MSG_NOTE, "merging ranges for ");
+		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr));
+		  dump_printf (MSG_NOTE,  ", ");
+		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr));
+		  dump_printf (MSG_NOTE,  " and ");
+		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr));
+		  dump_printf (MSG_NOTE,  ", ");
+		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
+		  dump_printf (MSG_NOTE, "\n");
+		}
+	      alias_pairs->ordered_remove (i--);
+	    }
+	}
+    }
+}
+
 /* Check if OFFSET1 and OFFSET2 (DR_OFFSETs of some data-refs) are identical
    expressions.  */
 static bool
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index 96bc764..dbe8372 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -148,6 +148,32 @@ struct data_reference
 
 typedef struct data_reference *data_reference_p;
 
+/* This struct is used to store the information of a data reference,
+   including the data ref itself and the segment length for aliasing
+   checks.  This is used to merge alias checks.  */
+
+struct dr_with_seg_len
+{
+  dr_with_seg_len (data_reference_p d, tree len)
+    : dr (d), seg_len (len) {}
+
+  data_reference_p dr;
+  tree seg_len;
+};
+
+/* This struct contains two dr_with_seg_len objects with aliasing data
+   refs.  Two comparisons are generated from them.  */
+
+struct dr_with_seg_len_pair_t
+{
+  dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
+			       const dr_with_seg_len& d2)
+    : first (d1), second (d2) {}
+
+  dr_with_seg_len first;
+  dr_with_seg_len second;
+};
+
 enum data_dependence_direction {
   dir_positive,
   dir_negative,
@@ -343,6 +369,8 @@ extern bool dr_equal_offsets_p (struct data_reference *,
                                 struct data_reference *);
 
 extern int data_ref_compare_tree (tree, tree);
+extern void prune_runtime_alias_test_list (vec<dr_with_seg_len_pair_t> *,
+					   unsigned HOST_WIDE_INT);
 /* Return true when the base objects of data references A and B are
    the same memory object.  */
 
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c
index de04e27..a1ef24e 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -2814,72 +2814,6 @@ vect_analyze_data_ref_accesses (vec_info *vinfo)
   return true;
 }
 
-
-/* Operator == between two dr_with_seg_len objects.
-
-   This equality operator is used to make sure two data refs
-   are the same one so that we will consider to combine the
-   aliasing checks of those two pairs of data dependent data
-   refs.  */
-
-static bool
-operator == (const dr_with_seg_len& d1,
-	     const dr_with_seg_len& d2)
-{
-  return operand_equal_p (DR_BASE_ADDRESS (d1.dr),
-			  DR_BASE_ADDRESS (d2.dr), 0)
-	   && data_ref_compare_tree (DR_OFFSET (d1.dr), DR_OFFSET (d2.dr)) == 0
-	   && data_ref_compare_tree (DR_INIT (d1.dr), DR_INIT (d2.dr)) == 0
-	   && data_ref_compare_tree (d1.seg_len, d2.seg_len) == 0;
-}
-
-/* Function comp_dr_with_seg_len_pair.
-
-   Comparison function for sorting objects of dr_with_seg_len_pair_t
-   so that we can combine aliasing checks in one scan.  */
-
-static int
-comp_dr_with_seg_len_pair (const void *pa_, const void *pb_)
-{
-  const dr_with_seg_len_pair_t* pa = (const dr_with_seg_len_pair_t *) pa_;
-  const dr_with_seg_len_pair_t* pb = (const dr_with_seg_len_pair_t *) pb_;
-  const dr_with_seg_len &a1 = pa->first, &a2 = pa->second;
-  const dr_with_seg_len &b1 = pb->first, &b2 = pb->second;
-
-  /* For DR pairs (a, b) and (c, d), we only consider to merge the alias checks
-     if a and c have the same basic address snd step, and b and d have the same
-     address and step.  Therefore, if any a&c or b&d don't have the same address
-     and step, we don't care the order of those two pairs after sorting.  */
-  int comp_res;
-
-  if ((comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (a1.dr),
-				DR_BASE_ADDRESS (b1.dr))) != 0)
-    return comp_res;
-  if ((comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (a2.dr),
-				DR_BASE_ADDRESS (b2.dr))) != 0)
-    return comp_res;
-  if ((comp_res = data_ref_compare_tree (DR_STEP (a1.dr),
-					 DR_STEP (b1.dr))) != 0)
-    return comp_res;
-  if ((comp_res = data_ref_compare_tree (DR_STEP (a2.dr),
-					 DR_STEP (b2.dr))) != 0)
-    return comp_res;
-  if ((comp_res = data_ref_compare_tree (DR_OFFSET (a1.dr),
-					 DR_OFFSET (b1.dr))) != 0)
-    return comp_res;
-  if ((comp_res = data_ref_compare_tree (DR_INIT (a1.dr),
-					 DR_INIT (b1.dr))) != 0)
-    return comp_res;
-  if ((comp_res = data_ref_compare_tree (DR_OFFSET (a2.dr),
-					 DR_OFFSET (b2.dr))) != 0)
-    return comp_res;
-  if ((comp_res = data_ref_compare_tree (DR_INIT (a2.dr),
-					 DR_INIT (b2.dr))) != 0)
-    return comp_res;
-
-  return 0;
-}
-
 /* Function vect_vfa_segment_size.
 
    Create an expression that computes the size of segment
@@ -2994,34 +2928,6 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo)
   if (may_alias_ddrs.is_empty ())
     return true;
 
-  /* Basically, for each pair of dependent data refs store_ptr_0
-     and load_ptr_0, we create an expression:
-
-     ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
-     || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
-
-     for aliasing checks.  However, in some cases we can decrease
-     the number of checks by combining two checks into one.  For
-     example, suppose we have another pair of data refs store_ptr_0
-     and load_ptr_1, and if the following condition is satisfied:
-
-     load_ptr_0 < load_ptr_1  &&
-     load_ptr_1 - load_ptr_0 - load_segment_length_0 < store_segment_length_0
-
-     (this condition means, in each iteration of vectorized loop,
-     the accessed memory of store_ptr_0 cannot be between the memory
-     of load_ptr_0 and load_ptr_1.)
-
-     we then can use only the following expression to finish the
-     alising checks between store_ptr_0 & load_ptr_0 and
-     store_ptr_0 & load_ptr_1:
-
-     ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
-     || (load_ptr_1 + load_segment_length_1 <= store_ptr_0))
-
-     Note that we only consider that load_ptr_0 and load_ptr_1 have the
-     same basic address.  */
-
   comp_alias_ddrs.create (may_alias_ddrs.length ());
 
   /* First, we collect all data ref pairs for aliasing checks.  */
@@ -3092,144 +2998,8 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo)
       comp_alias_ddrs.safe_push (dr_with_seg_len_pair);
     }
 
-  /* Second, we sort the collected data ref pairs so that we can scan
-     them once to combine all possible aliasing checks.  */
-  comp_alias_ddrs.qsort (comp_dr_with_seg_len_pair);
-
-  /* Third, we scan the sorted dr pairs and check if we can combine
-     alias checks of two neighboring dr pairs.  */
-  for (size_t i = 1; i < comp_alias_ddrs.length (); ++i)
-    {
-      /* Deal with two ddrs (dr_a1, dr_b1) and (dr_a2, dr_b2).  */
-      dr_with_seg_len *dr_a1 = &comp_alias_ddrs[i-1].first,
-		      *dr_b1 = &comp_alias_ddrs[i-1].second,
-		      *dr_a2 = &comp_alias_ddrs[i].first,
-		      *dr_b2 = &comp_alias_ddrs[i].second;
-
-      /* Remove duplicate data ref pairs.  */
-      if (*dr_a1 == *dr_a2 && *dr_b1 == *dr_b2)
-	{
-	  if (dump_enabled_p ())
-	    {
-	      dump_printf_loc (MSG_NOTE, vect_location,
-			       "found equal ranges ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM,
-				 DR_REF (dr_a1->dr));
-	      dump_printf (MSG_NOTE,  ", ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM,
-				 DR_REF (dr_b1->dr));
-	      dump_printf (MSG_NOTE,  " and ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM,
-				 DR_REF (dr_a2->dr));
-	      dump_printf (MSG_NOTE,  ", ");
-	      dump_generic_expr (MSG_NOTE, TDF_SLIM,
-				 DR_REF (dr_b2->dr));
-	      dump_printf (MSG_NOTE, "\n");
-	    }
-
-	  comp_alias_ddrs.ordered_remove (i--);
-	  continue;
-	}
-
-      if (*dr_a1 == *dr_a2 || *dr_b1 == *dr_b2)
-	{
-	  /* We consider the case that DR_B1 and DR_B2 are same memrefs,
-	     and DR_A1 and DR_A2 are two consecutive memrefs.  */
-	  if (*dr_a1 == *dr_a2)
-	    {
-	      std::swap (dr_a1, dr_b1);
-	      std::swap (dr_a2, dr_b2);
-	    }
-
-	  if (!operand_equal_p (DR_BASE_ADDRESS (dr_a1->dr),
-				DR_BASE_ADDRESS (dr_a2->dr), 0)
-	      || !operand_equal_p (DR_OFFSET (dr_a1->dr),
-				   DR_OFFSET (dr_a2->dr), 0)
-	      || !tree_fits_shwi_p (DR_INIT (dr_a1->dr))
-	      || !tree_fits_shwi_p (DR_INIT (dr_a2->dr)))
-	    continue;
-
-	  /* Make sure dr_a1 starts left of dr_a2.  */
-	  if (tree_int_cst_lt (DR_INIT (dr_a2->dr), DR_INIT (dr_a1->dr)))
-	    std::swap (*dr_a1, *dr_a2);
-
-	  bool do_remove = false;
-	  unsigned HOST_WIDE_INT diff
-	    = (tree_to_shwi (DR_INIT (dr_a2->dr))
-               - tree_to_shwi (DR_INIT (dr_a1->dr)));
-
-	  /* If the left segment does not extend beyond the start of the
-	     right segment the new segment length is that of the right
-	     plus the segment distance.  */
-	  if (tree_fits_uhwi_p (dr_a1->seg_len)
-	      && compare_tree_int (dr_a1->seg_len, diff) <= 0)
-	    {
-	      dr_a1->seg_len = size_binop (PLUS_EXPR, dr_a2->seg_len,
-					   size_int (diff));
-	      do_remove = true;
-	    }
-	  /* Generally the new segment length is the maximum of the
-	     left segment size and the right segment size plus the distance.
-	     ???  We can also build tree MAX_EXPR here but it's not clear this
-	     is profitable.  */
-	  else if (tree_fits_uhwi_p (dr_a1->seg_len)
-		   && tree_fits_uhwi_p (dr_a2->seg_len))
-	    {
-	      unsigned HOST_WIDE_INT seg_len_a1 = tree_to_uhwi (dr_a1->seg_len);
-	      unsigned HOST_WIDE_INT seg_len_a2 = tree_to_uhwi (dr_a2->seg_len);
-	      dr_a1->seg_len = size_int (MAX (seg_len_a1, diff + seg_len_a2));
-	      do_remove = true;
-	    }
-	  /* Now we check if the following condition is satisfied:
-
-	     DIFF - SEGMENT_LENGTH_A < SEGMENT_LENGTH_B
-
-	     where DIFF = DR_A2_INIT - DR_A1_INIT.  However,
-	     SEGMENT_LENGTH_A or SEGMENT_LENGTH_B may not be constant so we
-	     have to make a best estimation.  We can get the minimum value
-	     of SEGMENT_LENGTH_B as a constant, represented by MIN_SEG_LEN_B,
-	     then either of the following two conditions can guarantee the
-	     one above:
-
-	     1: DIFF <= MIN_SEG_LEN_B
-	     2: DIFF - SEGMENT_LENGTH_A < MIN_SEG_LEN_B  */
-	  else
-	    {
-	      unsigned HOST_WIDE_INT min_seg_len_b
-		= (tree_fits_uhwi_p (dr_b1->seg_len)
-		   ? tree_to_uhwi (dr_b1->seg_len)
-		   : vect_factor);
-
-	      if (diff <= min_seg_len_b
-		  || (tree_fits_uhwi_p (dr_a1->seg_len)
-		      && diff - tree_to_uhwi (dr_a1->seg_len) < min_seg_len_b))
-		{
-		  dr_a1->seg_len = size_binop (PLUS_EXPR,
-					       dr_a2->seg_len, size_int (diff));
-		  do_remove = true;
-		}
-	    }
-
-	  if (do_remove)
-	    {
-	      if (dump_enabled_p ())
-		{
-		  dump_printf_loc (MSG_NOTE, vect_location,
-				   "merging ranges for ");
-		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a1->dr));
-		  dump_printf (MSG_NOTE,  ", ");
-		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b1->dr));
-		  dump_printf (MSG_NOTE,  " and ");
-		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_a2->dr));
-		  dump_printf (MSG_NOTE,  ", ");
-		  dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (dr_b2->dr));
-		  dump_printf (MSG_NOTE, "\n");
-		}
-	      comp_alias_ddrs.ordered_remove (i--);
-	    }
-	}
-    }
-
+  prune_runtime_alias_test_list (&comp_alias_ddrs,
+				 (unsigned HOST_WIDE_INT) vect_factor);
   dump_printf_loc (MSG_NOTE, vect_location,
 		   "improved number of alias checks from %d to %d\n",
 		   may_alias_ddrs.length (), comp_alias_ddrs.length ());
diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h
index 12bb904..7978bbd 100644
--- a/gcc/tree-vectorizer.h
+++ b/gcc/tree-vectorizer.h
@@ -146,34 +146,6 @@ typedef struct _slp_instance {
 
 
 
-/* This struct is used to store the information of a data reference,
-   including the data ref itself and the segment length for aliasing
-   checks.  This is used to merge alias checks.  */
-
-struct dr_with_seg_len
-{
-  dr_with_seg_len (data_reference_p d, tree len)
-    : dr (d), seg_len (len) {}
-
-  data_reference_p dr;
-  tree seg_len;
-};
-
-/* This struct contains two dr_with_seg_len objects with aliasing data
-   refs.  Two comparisons are generated from them.  */
-
-struct dr_with_seg_len_pair_t
-{
-  dr_with_seg_len_pair_t (const dr_with_seg_len& d1,
-			       const dr_with_seg_len& d2)
-    : first (d1), second (d2) {}
-
-  dr_with_seg_len first;
-  dr_with_seg_len second;
-};
-
-
-
 /* Vectorizer state common between loop and basic-block vectorization.  */
 struct vec_info {
   enum { bb, loop } kind;
-- 
1.9.1


^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2017-05-26 14:13 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-05-23 16:23 [PATCH GCC][2/6]Factor out code pruning runtime alias checks Bin Cheng
2017-05-26 11:16 ` Richard Biener
2017-05-26 14:19   ` Bin.Cheng

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).