Re: [PATCH GCC][1/6]Move compare_tree to tree.c and expose the interface.

["Bin.Cheng" <amker.cheng@gmail.com>]

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

On Fri, May 26, 2017 at 12:50 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Fri, May 26, 2017 at 1:30 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Fri, May 26, 2017 at 12:14 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 patch set factors out runtime alias check code from tree-vect-data-refs.c
>>>> and tree-vect-loop-manip.c as general interfaces in tree-data-ref.c.  With this
>>>> change other optimizers like tree loop distribution could version loop wrto the
>>>> runtime alias checks.  During this work, I also found current code has issues
>>>> with negative DR_STEP.  This patch set fixes the issue as tracked in PR80815.
>>>>
>>>> This is the first patch simply moves compare_tree to tree.c and exposes it.
>>>> Bootstrap and test on x86_64 and AArch64, is it OK?
>>>
>>> I think the name is quite bad for an exported function given for INTEGER_CSTs
>>> it doesn't return anything resembling a comparison result.  Also (not
>>> your fault)
>>> it doesn't seem to handle hash collisions nor have a suitable fallback for
>>> trees it doesn't handle.
>>>
>>> I don't have a good suggestion for the name but tree.c exported fns should
>>> have higher standards regarding their implementation...
>> Hmm, I don't have idea to generalize it for the moment, so OK to
>> rename it to data_ref_compare_tree and move it to tree-data-ref.c?  It
>> needs to be external symbol though.
>
> Works for me.
Thanks, I updated and committed below patch.

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

    * tree-vect-data-refs.c (compare_tree): Rename and move ...
    * tree-data-ref.c (data_ref_compare_tree): ... to here.
    * tree-data-ref.h (data_ref_compare_tree): New decalaration.
    * tree-vect-data-refs.c (dr_group_sort_cmp): Update uses.
    (operator==, comp_dr_with_seg_len_pair): Ditto.
    (vect_prune_runtime_alias_test_list): Ditto.

>
> Richard.
>
>> Thanks,
>> bin
>>>
>>> Richard.
>>>
>>>
>>>
>>>> Thanks,
>>>> bin
>>>>
>>>> 2017-05-22  Bin Cheng  <bin.cheng@arm.com>
>>>>
>>>>         * tree-vect-data-refs.c (compare_tree): Move ...
>>>>         * tree.c (compare_tree): ... to here.
>>>>         * tree.h (compare_tree): New decalaration.

[-- Attachment #2: 0001-compare_tree-interface-20170516.txt --]
[-- Type: text/plain, Size: 9861 bytes --]

From ffbc71384ed53275847254e588353d9a176b70a1 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Fri, 19 May 2017 12:49:38 +0100
Subject: [PATCH 1/6] compare_tree-interface-20170516.txt

---
 gcc/tree-data-ref.c       |  75 ++++++++++++++++++++++++++++
 gcc/tree-data-ref.h       |   1 +
 gcc/tree-vect-data-refs.c | 122 ++++++++++------------------------------------
 3 files changed, 103 insertions(+), 95 deletions(-)

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 2480f4e..6a32a65 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1107,6 +1107,81 @@ create_data_ref (loop_p nest, loop_p loop, tree memref, gimple *stmt,
   return dr;
 }
 
+/*  A helper function computes order between two tree epxressions T1 and T2.
+    This is used in comparator functions sorting objects based on the order
+    of tree expressions.  The function returns -1, 0, or 1.  */
+
+int
+data_ref_compare_tree (tree t1, tree t2)
+{
+  int i, cmp;
+  enum tree_code code;
+  char tclass;
+
+  if (t1 == t2)
+    return 0;
+  if (t1 == NULL)
+    return -1;
+  if (t2 == NULL)
+    return 1;
+
+  STRIP_NOPS (t1);
+  STRIP_NOPS (t2);
+
+  if (TREE_CODE (t1) != TREE_CODE (t2))
+    return TREE_CODE (t1) < TREE_CODE (t2) ? -1 : 1;
+
+  code = TREE_CODE (t1);
+  switch (code)
+    {
+    /* For const values, we can just use hash values for comparisons.  */
+    case INTEGER_CST:
+    case REAL_CST:
+    case FIXED_CST:
+    case STRING_CST:
+    case COMPLEX_CST:
+    case VECTOR_CST:
+      {
+	hashval_t h1 = iterative_hash_expr (t1, 0);
+	hashval_t h2 = iterative_hash_expr (t2, 0);
+	if (h1 != h2)
+	  return h1 < h2 ? -1 : 1;
+	break;
+      }
+
+    case SSA_NAME:
+      cmp = data_ref_compare_tree (SSA_NAME_VAR (t1), SSA_NAME_VAR (t2));
+      if (cmp != 0)
+	return cmp;
+
+      if (SSA_NAME_VERSION (t1) != SSA_NAME_VERSION (t2))
+	return SSA_NAME_VERSION (t1) < SSA_NAME_VERSION (t2) ? -1 : 1;
+      break;
+
+    default:
+      tclass = TREE_CODE_CLASS (code);
+
+      /* For var-decl, we could compare their UIDs.  */
+      if (tclass == tcc_declaration)
+	{
+	  if (DECL_UID (t1) != DECL_UID (t2))
+	    return DECL_UID (t1) < DECL_UID (t2) ? -1 : 1;
+	  break;
+	}
+
+      /* For expressions with operands, compare their operands recursively.  */
+      for (i = TREE_OPERAND_LENGTH (t1) - 1; i >= 0; --i)
+	{
+	  cmp = data_ref_compare_tree (TREE_OPERAND (t1, i),
+				       TREE_OPERAND (t2, i));
+	  if (cmp != 0)
+	    return cmp;
+	}
+    }
+
+  return 0;
+}
+
 /* 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..96bc764 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -342,6 +342,7 @@ extern bool dr_may_alias_p (const struct data_reference *,
 extern bool dr_equal_offsets_p (struct data_reference *,
                                 struct data_reference *);
 
+extern int data_ref_compare_tree (tree, tree);
 /* 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 67cc969..de04e27 100644
--- a/gcc/tree-vect-data-refs.c
+++ b/gcc/tree-vect-data-refs.c
@@ -2574,83 +2574,6 @@ vect_analyze_data_ref_access (struct data_reference *dr)
   return vect_analyze_group_access (dr);
 }
 
-
-
-/*  A helper function used in the comparator function to sort data
-    references.  T1 and T2 are two data references to be compared.
-    The function returns -1, 0, or 1.  */
-
-static int
-compare_tree (tree t1, tree t2)
-{
-  int i, cmp;
-  enum tree_code code;
-  char tclass;
-
-  if (t1 == t2)
-    return 0;
-  if (t1 == NULL)
-    return -1;
-  if (t2 == NULL)
-    return 1;
-
-  STRIP_NOPS (t1);
-  STRIP_NOPS (t2);
-
-  if (TREE_CODE (t1) != TREE_CODE (t2))
-    return TREE_CODE (t1) < TREE_CODE (t2) ? -1 : 1;
-
-  code = TREE_CODE (t1);
-  switch (code)
-    {
-    /* For const values, we can just use hash values for comparisons.  */
-    case INTEGER_CST:
-    case REAL_CST:
-    case FIXED_CST:
-    case STRING_CST:
-    case COMPLEX_CST:
-    case VECTOR_CST:
-      {
-	hashval_t h1 = iterative_hash_expr (t1, 0);
-	hashval_t h2 = iterative_hash_expr (t2, 0);
-	if (h1 != h2)
-	  return h1 < h2 ? -1 : 1;
-	break;
-      }
-
-    case SSA_NAME:
-      cmp = compare_tree (SSA_NAME_VAR (t1), SSA_NAME_VAR (t2));
-      if (cmp != 0)
-	return cmp;
-
-      if (SSA_NAME_VERSION (t1) != SSA_NAME_VERSION (t2))
-	return SSA_NAME_VERSION (t1) < SSA_NAME_VERSION (t2) ? -1 : 1;
-      break;
-
-    default:
-      tclass = TREE_CODE_CLASS (code);
-
-      /* For var-decl, we could compare their UIDs.  */
-      if (tclass == tcc_declaration)
-	{
-	  if (DECL_UID (t1) != DECL_UID (t2))
-	    return DECL_UID (t1) < DECL_UID (t2) ? -1 : 1;
-	  break;
-	}
-
-      /* For expressions with operands, compare their operands recursively.  */
-      for (i = TREE_OPERAND_LENGTH (t1) - 1; i >= 0; --i)
-	{
-	  cmp = compare_tree (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
-	  if (cmp != 0)
-	    return cmp;
-	}
-    }
-
-  return 0;
-}
-
-
 /* Compare two data-references DRA and DRB to group them into chunks
    suitable for grouping.  */
 
@@ -2674,7 +2597,8 @@ dr_group_sort_cmp (const void *dra_, const void *drb_)
   /* Ordering of DRs according to base.  */
   if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0))
     {
-      cmp = compare_tree (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb));
+      cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra),
+				   DR_BASE_ADDRESS (drb));
       if (cmp != 0)
         return cmp;
     }
@@ -2682,7 +2606,7 @@ dr_group_sort_cmp (const void *dra_, const void *drb_)
   /* And according to DR_OFFSET.  */
   if (!dr_equal_offsets_p (dra, drb))
     {
-      cmp = compare_tree (DR_OFFSET (dra), DR_OFFSET (drb));
+      cmp = data_ref_compare_tree (DR_OFFSET (dra), DR_OFFSET (drb));
       if (cmp != 0)
         return cmp;
     }
@@ -2695,8 +2619,8 @@ dr_group_sort_cmp (const void *dra_, const void *drb_)
   if (!operand_equal_p (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
 			TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))), 0))
     {
-      cmp = compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
-                          TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
+      cmp = data_ref_compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))),
+				   TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
       if (cmp != 0)
         return cmp;
     }
@@ -2704,7 +2628,7 @@ dr_group_sort_cmp (const void *dra_, const void *drb_)
   /* And after step.  */
   if (!operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0))
     {
-      cmp = compare_tree (DR_STEP (dra), DR_STEP (drb));
+      cmp = data_ref_compare_tree (DR_STEP (dra), DR_STEP (drb));
       if (cmp != 0)
         return cmp;
     }
@@ -2904,9 +2828,9 @@ operator == (const dr_with_seg_len& d1,
 {
   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;
+	   && 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.
@@ -2928,23 +2852,29 @@ comp_dr_with_seg_len_pair (const void *pa_, const void *pb_)
      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),
+  if ((comp_res = data_ref_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),
+  if ((comp_res = data_ref_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)
+  if ((comp_res = data_ref_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)
+  if ((comp_res = data_ref_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)
+  if ((comp_res = data_ref_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)
+  if ((comp_res = data_ref_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)
+  if ((comp_res = data_ref_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)
+  if ((comp_res = data_ref_compare_tree (DR_INIT (a2.dr),
+					 DR_INIT (b2.dr))) != 0)
     return comp_res;
 
   return 0;
@@ -3128,9 +3058,11 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo)
       segment_length_a = vect_vfa_segment_size (dr_a, length_factor);
       segment_length_b = vect_vfa_segment_size (dr_b, length_factor);
 
-      comp_res = compare_tree (DR_BASE_ADDRESS (dr_a), DR_BASE_ADDRESS (dr_b));
+      comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (dr_a),
+					DR_BASE_ADDRESS (dr_b));
       if (comp_res == 0)
-	comp_res = compare_tree (DR_OFFSET (dr_a), DR_OFFSET (dr_b));
+	comp_res = data_ref_compare_tree (DR_OFFSET (dr_a),
+					  DR_OFFSET (dr_b));
 
       /* Alias is known at compilation time.  */
       if (comp_res == 0
-- 
1.9.1