[PATCH GCC][10/13]Compute and cache data dependence relation

[PATCH GCC][10/13]Compute and cache data dependence relation

[Bin Cheng]

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

Hi,
This patch computes and caches data dependence relation in a hash table
so that it can be queried multiple times later for partition dependence
check.
Bootstrap and test on x86_64 and AArch64.  Is it OK?

Thanks,
bin

2017-06-07  Bin Cheng  <bin.cheng@arm.com>

	* tree-loop-distribution.c (struct ddr_entry, ddr_entry_hasher): New.
	(ddr_entry_hasher::hash, ::equal, get_data_dependence): New function.
	(ddrs_vec, ddrs_table): New.
	(classify_partition): Call get_data_dependence.
	(pg_add_dependence_edges): Ditto.
	(distribute_loop): Initialize data dependence global variables.

[-- Attachment #2: 0010-cache-data-dependence-20170607.txt --]
[-- Type: text/plain, Size: 6381 bytes --]

From 6075d1db94b7f130a91bba53125bed5754a46f59 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Fri, 9 Jun 2017 13:02:09 +0100
Subject: [PATCH 10/14] cache-data-dependence-20170607.txt

---
 gcc/tree-loop-distribution.c | 118 +++++++++++++++++++++++++++++++++----------
 1 file changed, 92 insertions(+), 26 deletions(-)

diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index 90dc8ea..eacd9a1 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -66,6 +66,43 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-vectorizer.h"
 
 
+/* Hashtable entry for data reference relation.  */
+struct ddr_entry
+{
+  data_reference_p a;
+  data_reference_p b;
+  ddr_p ddr;
+  hashval_t hash;
+};
+
+/* Hashtable helpers.  */
+
+struct ddr_entry_hasher : delete_ptr_hash <ddr_entry>
+{
+  static inline hashval_t hash (const ddr_entry *);
+  static inline bool equal (const ddr_entry *, const ddr_entry *);
+};
+
+/* Hash function for data reference relation.  */
+
+inline hashval_t
+ddr_entry_hasher::hash (const ddr_entry *entry)
+{
+  return entry->hash;
+}
+
+/* Hash table equality function for data reference relation.  */
+
+inline bool
+ddr_entry_hasher::equal (const ddr_entry *entry1, const ddr_entry *entry2)
+{
+  return (entry1->hash == entry2->hash
+	  && DR_STMT (entry1->a) == DR_STMT (entry2->a)
+	  && DR_STMT (entry1->b) == DR_STMT (entry2->b)
+	  && operand_equal_p (DR_REF (entry1->a), DR_REF (entry2->a), 0)
+	  && operand_equal_p (DR_REF (entry1->b), DR_REF (entry2->b), 0));
+}
+
 /* The loop (nest) to be distributed.  */
 static vec<loop_p> *loop_nest;
 
@@ -75,6 +112,13 @@ static vec<data_reference_p> *datarefs_vec;
 /* Map of data reference in the loop to a unique id.  */
 static hash_map<data_reference_p, int> *datarefs_map;
 
+/* Vector of data dependence relations.  */
+static vec<ddr_p> *ddrs_vec;
+
+/* Hash table for data dependence relation in the loop to be distributed.  */
+static hash_table<ddr_entry_hasher> *ddrs_table;
+
+
 /* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
 struct rdg_vertex
 {
@@ -1061,6 +1105,41 @@ generate_code_for_partition (struct loop *loop,
   return false;
 }
 
+/* Return data dependence relation for data references A and B.  The two
+   data references must be in lexicographic order wrto reduced dependence
+   graph RDG.  We firstly try to find ddr from global ddr hash table.  If
+   it doesn't exist, compute the ddr and cache it.  */
+
+static data_dependence_relation *
+get_data_dependence (struct graph *rdg, data_reference_p a, data_reference_p b)
+{
+  struct ddr_entry ent, **slot;
+  struct data_dependence_relation *ddr;
+
+  gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b));
+  gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a))
+	      <= rdg_vertex_for_stmt (rdg, DR_STMT (b)));
+  ent.a = a;
+  ent.b = b;
+  ent.hash = iterative_hash_expr (DR_REF (a), 0);
+  ent.hash = iterative_hash_expr (DR_REF (b), ent.hash);
+  slot = ddrs_table->find_slot (&ent, INSERT);
+  if (*slot == NULL)
+    {
+      ddr = initialize_data_dependence_relation (a, b, *loop_nest);
+      compute_affine_dependence (ddr, (*loop_nest)[0]);
+
+      ddrs_vec->safe_push (ddr);
+
+      *slot = new ddr_entry ();
+      (*slot)->a = a;
+      (*slot)->b = b;
+      (*slot)->ddr = ddr;
+      (*slot)->hash = ent.hash;
+    }
+
+  return (*slot)->ddr;
+}
 
 /* Returns a partition with all the statements needed for computing
    the vertex V of the RDG, also including the loop exit conditions.  */
@@ -1231,44 +1310,27 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition)
 	return;
       /* Now check that if there is a dependence this dependence is
          of a suitable form for memmove.  */
-      vec<loop_p> loops = vNULL;
-      ddr_p ddr;
-      loops.safe_push (loop);
-      ddr = initialize_data_dependence_relation (single_load, single_store,
-						 loops);
-      compute_affine_dependence (ddr, loop);
+      ddr_p ddr = get_data_dependence (rdg, single_load, single_store);
       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
-	{
-	  free_dependence_relation (ddr);
-	  loops.release ();
-	  return;
-	}
+	return;
+
       if (DDR_ARE_DEPENDENT (ddr) != chrec_known)
 	{
 	  if (DDR_NUM_DIST_VECTS (ddr) == 0)
-	    {
-	      free_dependence_relation (ddr);
-	      loops.release ();
-	      return;
-	    }
+	    return;
+
 	  lambda_vector dist_v;
 	  FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
 	    {
 	      int dist = dist_v[index_in_loop_nest (loop->num,
 						    DDR_LOOP_NEST (ddr))];
 	      if (dist > 0 && !DDR_REVERSED_P (ddr))
-		{
-		  free_dependence_relation (ddr);
-		  loops.release ();
-		  return;
-		}
+		return;
 	    }
 	  partition->kind = PKIND_MEMMOVE;
 	}
       else
 	partition->kind = PKIND_MEMCPY;
-      free_dependence_relation (ddr);
-      loops.release ();
       partition->main_dr = single_store;
       partition->secondary_dr = single_load;
       partition->niter = nb_iter;
@@ -1532,8 +1594,7 @@ pg_add_dependence_edges (struct graph *rdg, int dir,
 	      std::swap (dr1, dr2);
 	      this_dir = -this_dir;
 	    }
-	  ddr = initialize_data_dependence_relation (dr1, dr2, *loop_nest);
-	  compute_affine_dependence (ddr, (*loop_nest)[0]);
+	  ddr = get_data_dependence (rdg, dr1, dr2);
 	  if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 	    this_dir = 2;
 	  else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
@@ -1559,7 +1620,6 @@ pg_add_dependence_edges (struct graph *rdg, int dir,
 	    }
 	  else
 	    this_dir = 0;
-	  free_dependence_relation (ddr);
 	  if (this_dir == 2)
 	    return 2;
 	  else if (dir == 0)
@@ -1652,6 +1712,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts,
   if (dump_file && (dump_flags & TDF_DETAILS))
     dump_rdg (dump_file, rdg);
 
+  ddrs_vec = new vec<ddr_p> ();
+  ddrs_table = new hash_table<ddr_entry_hasher> (389);
+
   auto_vec<struct partition *, 3> partitions;
   rdg_build_partitions (rdg, stmts, &partitions);
 
@@ -1840,6 +1903,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts,
  ldist_done:
   loop_nest->release ();
   delete loop_nest;
+  free_dependence_relations (*ddrs_vec);
+  delete ddrs_vec;
+  delete ddrs_table;
   free_data_refs (*datarefs_vec);
   delete datarefs_vec;
   delete datarefs_map;
-- 
1.9.1

Re: [PATCH GCC][10/13]Compute and cache data dependence relation

[Richard Biener]

On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> This patch computes and caches data dependence relation in a hash table
> so that it can be queried multiple times later for partition dependence
> check.
> Bootstrap and test on x86_64 and AArch64.  Is it OK?

+/* Vector of data dependence relations.  */
+static vec<ddr_p> *ddrs_vec;
+
+/* Hash table for data dependence relation in the loop to be distributed.  */
+static hash_table<ddr_entry_hasher> *ddrs_table;

avoid the extra indirection.

+/* Hashtable entry for data reference relation.  */
+struct ddr_entry
+{
+  data_reference_p a;
+  data_reference_p b;
+  ddr_p ddr;
+  hashval_t hash;
+};
...
+/* Hash table equality function for data reference relation.  */
+
+inline bool
+ddr_entry_hasher::equal (const ddr_entry *entry1, const ddr_entry *entry2)
+{
+  return (entry1->hash == entry2->hash
+         && DR_STMT (entry1->a) == DR_STMT (entry2->a)
+         && DR_STMT (entry1->b) == DR_STMT (entry2->b)
+         && operand_equal_p (DR_REF (entry1->a), DR_REF (entry2->a), 0)
+         && operand_equal_p (DR_REF (entry1->b), DR_REF (entry2->b), 0));
+}

what's the issue with using hash_table <ddr_p> with a custom hasher?
That is, simply key on the dataref pointers (hash them, compare those
for equality)?

Your scheme looks too complicated / expensive to me ...

You can drop ddrs_vec needed only for memory removal if you traverse
the hashtable.

Richard.

> Thanks,
> bin
>
> 2017-06-07  Bin Cheng  <bin.cheng@arm.com>
>
>         * tree-loop-distribution.c (struct ddr_entry, ddr_entry_hasher): New.
>         (ddr_entry_hasher::hash, ::equal, get_data_dependence): New function.
>         (ddrs_vec, ddrs_table): New.
>         (classify_partition): Call get_data_dependence.
>         (pg_add_dependence_edges): Ditto.
>         (distribute_loop): Initialize data dependence global variables.

Re: [PATCH GCC][10/13]Compute and cache data dependence relation

[Bin.Cheng]

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

On Fri, Jun 16, 2017 at 11:03 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>> Hi,
>> This patch computes and caches data dependence relation in a hash table
>> so that it can be queried multiple times later for partition dependence
>> check.
>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>
> +/* Vector of data dependence relations.  */
> +static vec<ddr_p> *ddrs_vec;
> +
> +/* Hash table for data dependence relation in the loop to be distributed.  */
> +static hash_table<ddr_entry_hasher> *ddrs_table;
>
> avoid the extra indirection.
>
> +/* Hashtable entry for data reference relation.  */
> +struct ddr_entry
> +{
> +  data_reference_p a;
> +  data_reference_p b;
> +  ddr_p ddr;
> +  hashval_t hash;
> +};
> ...
> +/* Hash table equality function for data reference relation.  */
> +
> +inline bool
> +ddr_entry_hasher::equal (const ddr_entry *entry1, const ddr_entry *entry2)
> +{
> +  return (entry1->hash == entry2->hash
> +         && DR_STMT (entry1->a) == DR_STMT (entry2->a)
> +         && DR_STMT (entry1->b) == DR_STMT (entry2->b)
> +         && operand_equal_p (DR_REF (entry1->a), DR_REF (entry2->a), 0)
> +         && operand_equal_p (DR_REF (entry1->b), DR_REF (entry2->b), 0));
> +}
>
> what's the issue with using hash_table <ddr_p> with a custom hasher?
> That is, simply key on the dataref pointers (hash them, compare those
> for equality)?
>
> Your scheme looks too complicated / expensive to me ...
>
> You can drop ddrs_vec needed only for memory removal if you traverse
> the hashtable.
Thanks for reviewing.  Patch simplified as suggested.  Is it OK?

Thanks,
bin
2017-06-17  Bin Cheng  <bin.cheng@arm.com>

    * tree-loop-distribution.c (struct ddr_hasher): New.
    (ddr_hasher::hash, ::equal, get_data_dependence): New function.
    (ddrs_table): New.
    (classify_partition): Call get_data_dependence.
    (pg_add_dependence_edges): Ditto.
    (distribute_loop): Release data dependence hash table.

[-- Attachment #2: 0009-cache-data-dependence-20170608.txt.patch --]
[-- Type: text/x-patch, Size: 5668 bytes --]

From 6a3d78078355df492877955b5f00784a795a94d8 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Fri, 9 Jun 2017 13:02:09 +0100
Subject: [PATCH 09/13] cache-data-dependence-20170608.txt

---
 gcc/tree-loop-distribution.c | 97 ++++++++++++++++++++++++++++++++------------
 1 file changed, 71 insertions(+), 26 deletions(-)

diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index 2e5a828..a2e543e 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -70,6 +70,33 @@ along with GCC; see the file COPYING3.  If not see
 #define MAX_DATAREFS_NUM \
 	((unsigned) PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
 
+/* Hashtable helpers.  */
+
+struct ddr_hasher : nofree_ptr_hash <struct data_dependence_relation>
+{
+  static inline hashval_t hash (const data_dependence_relation *);
+  static inline bool equal (const data_dependence_relation *,
+			    const data_dependence_relation *);
+};
+
+/* Hash function for data dependence.  */
+
+inline hashval_t
+ddr_hasher::hash (const data_dependence_relation *ddr)
+{
+  return iterative_hash_object (DDR_A (ddr),
+				iterative_hash_object (DDR_B (ddr), 0));
+}
+
+/* Hash table equality function for data dependence.  */
+
+inline bool
+ddr_hasher::equal (const data_dependence_relation *ddr1,
+		   const data_dependence_relation *ddr2)
+{
+  return (DDR_A (ddr1) == DDR_A (ddr2) && DDR_B (ddr1) == DDR_B (ddr2));
+}
+
 /* The loop (nest) to be distributed.  */
 static vec<loop_p> loop_nest;
 
@@ -79,6 +106,10 @@ static vec<data_reference_p> datarefs_vec;
 /* Store index of data reference in aux field.  */
 #define DR_INDEX(dr)      ((uintptr_t) (dr)->aux)
 
+/* Hash table for data dependence relation in the loop to be distributed.  */
+static hash_table<ddr_hasher> ddrs_table (389);
+
+
 /* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
 struct rdg_vertex
 {
@@ -1057,6 +1088,32 @@ generate_code_for_partition (struct loop *loop,
   return false;
 }
 
+/* Return data dependence relation for data references A and B.  The two
+   data references must be in lexicographic order wrto reduced dependence
+   graph RDG.  We firstly try to find ddr from global ddr hash table.  If
+   it doesn't exist, compute the ddr and cache it.  */
+
+static data_dependence_relation *
+get_data_dependence (struct graph *rdg, data_reference_p a, data_reference_p b)
+{
+  struct data_dependence_relation ent, **slot;
+  struct data_dependence_relation *ddr;
+
+  gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b));
+  gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a))
+	      <= rdg_vertex_for_stmt (rdg, DR_STMT (b)));
+  ent.a = a;
+  ent.b = b;
+  slot = ddrs_table.find_slot (&ent, INSERT);
+  if (*slot == NULL)
+    {
+      ddr = initialize_data_dependence_relation (a, b, loop_nest);
+      compute_affine_dependence (ddr, loop_nest[0]);
+      *slot = ddr;
+    }
+
+  return *slot;
+}
 
 /* Returns a partition with all the statements needed for computing
    the vertex V of the RDG, also including the loop exit conditions.  */
@@ -1223,44 +1280,27 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition)
 	return;
       /* Now check that if there is a dependence this dependence is
          of a suitable form for memmove.  */
-      vec<loop_p> loops = vNULL;
-      ddr_p ddr;
-      loops.safe_push (loop);
-      ddr = initialize_data_dependence_relation (single_load, single_store,
-						 loops);
-      compute_affine_dependence (ddr, loop);
+      ddr_p ddr = get_data_dependence (rdg, single_load, single_store);
       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
-	{
-	  free_dependence_relation (ddr);
-	  loops.release ();
-	  return;
-	}
+	return;
+
       if (DDR_ARE_DEPENDENT (ddr) != chrec_known)
 	{
 	  if (DDR_NUM_DIST_VECTS (ddr) == 0)
-	    {
-	      free_dependence_relation (ddr);
-	      loops.release ();
-	      return;
-	    }
+	    return;
+
 	  lambda_vector dist_v;
 	  FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
 	    {
 	      int dist = dist_v[index_in_loop_nest (loop->num,
 						    DDR_LOOP_NEST (ddr))];
 	      if (dist > 0 && !DDR_REVERSED_P (ddr))
-		{
-		  free_dependence_relation (ddr);
-		  loops.release ();
-		  return;
-		}
+		return;
 	    }
 	  partition->kind = PKIND_MEMMOVE;
 	}
       else
 	partition->kind = PKIND_MEMCPY;
-      free_dependence_relation (ddr);
-      loops.release ();
       partition->main_dr = single_store;
       partition->secondary_dr = single_load;
       partition->niter = nb_iter;
@@ -1474,8 +1514,7 @@ pg_add_dependence_edges (struct graph *rdg, int dir,
 	      std::swap (dr1, dr2);
 	      this_dir = -this_dir;
 	    }
-	  ddr = initialize_data_dependence_relation (dr1, dr2, loop_nest);
-	  compute_affine_dependence (ddr, loop_nest[0]);
+	  ddr = get_data_dependence (rdg, dr1, dr2);
 	  if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 	    this_dir = 2;
 	  else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
@@ -1501,7 +1540,6 @@ pg_add_dependence_edges (struct graph *rdg, int dir,
 	    }
 	  else
 	    this_dir = 0;
-	  free_dependence_relation (ddr);
 	  if (this_dir == 2)
 	    return 2;
 	  else if (dir == 0)
@@ -1764,6 +1802,13 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts,
  ldist_done:
   loop_nest.release ();
   free_data_refs (datarefs_vec);
+  for (hash_table<ddr_hasher>::iterator iter = ddrs_table.begin ();
+       iter != ddrs_table.end (); ++iter)
+    {
+      free_dependence_relation (*iter);
+      *iter = NULL;
+    }
+  ddrs_table.empty ();
 
   FOR_EACH_VEC_ELT (partitions, i, partition)
     partition_free (partition);
-- 
1.9.1

Re: [PATCH GCC][10/13]Compute and cache data dependence relation

[Richard Biener]

On Tue, Jun 20, 2017 at 11:15 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Fri, Jun 16, 2017 at 11:03 AM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>> Hi,
>>> This patch computes and caches data dependence relation in a hash table
>>> so that it can be queried multiple times later for partition dependence
>>> check.
>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>
>> +/* Vector of data dependence relations.  */
>> +static vec<ddr_p> *ddrs_vec;
>> +
>> +/* Hash table for data dependence relation in the loop to be distributed.  */
>> +static hash_table<ddr_entry_hasher> *ddrs_table;
>>
>> avoid the extra indirection.
>>
>> +/* Hashtable entry for data reference relation.  */
>> +struct ddr_entry
>> +{
>> +  data_reference_p a;
>> +  data_reference_p b;
>> +  ddr_p ddr;
>> +  hashval_t hash;
>> +};
>> ...
>> +/* Hash table equality function for data reference relation.  */
>> +
>> +inline bool
>> +ddr_entry_hasher::equal (const ddr_entry *entry1, const ddr_entry *entry2)
>> +{
>> +  return (entry1->hash == entry2->hash
>> +         && DR_STMT (entry1->a) == DR_STMT (entry2->a)
>> +         && DR_STMT (entry1->b) == DR_STMT (entry2->b)
>> +         && operand_equal_p (DR_REF (entry1->a), DR_REF (entry2->a), 0)
>> +         && operand_equal_p (DR_REF (entry1->b), DR_REF (entry2->b), 0));
>> +}
>>
>> what's the issue with using hash_table <ddr_p> with a custom hasher?
>> That is, simply key on the dataref pointers (hash them, compare those
>> for equality)?
>>
>> Your scheme looks too complicated / expensive to me ...
>>
>> You can drop ddrs_vec needed only for memory removal if you traverse
>> the hashtable.
> Thanks for reviewing.  Patch simplified as suggested.  Is it OK?

+inline hashval_t
+ddr_hasher::hash (const data_dependence_relation *ddr)
+{
+  return iterative_hash_object (DDR_A (ddr),
+                               iterative_hash_object (DDR_B (ddr), 0));
+}
+

please use

    inchash::hash h;
    h.add_ptr (DDR_A (ddr));
    h.add_ptr (DDR_B (ddr));
    return h.end ();

Ok with that change.

Richard.

> Thanks,
> bin
> 2017-06-17  Bin Cheng  <bin.cheng@arm.com>
>
>     * tree-loop-distribution.c (struct ddr_hasher): New.
>     (ddr_hasher::hash, ::equal, get_data_dependence): New function.
>     (ddrs_table): New.
>     (classify_partition): Call get_data_dependence.
>     (pg_add_dependence_edges): Ditto.
>     (distribute_loop): Release data dependence hash table.

Re: [PATCH GCC][10/13]Compute and cache data dependence relation

[Bin.Cheng]

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

On Tue, Jun 20, 2017 at 12:32 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Jun 20, 2017 at 11:15 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>> On Fri, Jun 16, 2017 at 11:03 AM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>> Hi,
>>>> This patch computes and caches data dependence relation in a hash table
>>>> so that it can be queried multiple times later for partition dependence
>>>> check.
>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>
>>> +/* Vector of data dependence relations.  */
>>> +static vec<ddr_p> *ddrs_vec;
>>> +
>>> +/* Hash table for data dependence relation in the loop to be distributed.  */
>>> +static hash_table<ddr_entry_hasher> *ddrs_table;
>>>
>>> avoid the extra indirection.
>>>
>>> +/* Hashtable entry for data reference relation.  */
>>> +struct ddr_entry
>>> +{
>>> +  data_reference_p a;
>>> +  data_reference_p b;
>>> +  ddr_p ddr;
>>> +  hashval_t hash;
>>> +};
>>> ...
>>> +/* Hash table equality function for data reference relation.  */
>>> +
>>> +inline bool
>>> +ddr_entry_hasher::equal (const ddr_entry *entry1, const ddr_entry *entry2)
>>> +{
>>> +  return (entry1->hash == entry2->hash
>>> +         && DR_STMT (entry1->a) == DR_STMT (entry2->a)
>>> +         && DR_STMT (entry1->b) == DR_STMT (entry2->b)
>>> +         && operand_equal_p (DR_REF (entry1->a), DR_REF (entry2->a), 0)
>>> +         && operand_equal_p (DR_REF (entry1->b), DR_REF (entry2->b), 0));
>>> +}
>>>
>>> what's the issue with using hash_table <ddr_p> with a custom hasher?
>>> That is, simply key on the dataref pointers (hash them, compare those
>>> for equality)?
>>>
>>> Your scheme looks too complicated / expensive to me ...
>>>
>>> You can drop ddrs_vec needed only for memory removal if you traverse
>>> the hashtable.
>> Thanks for reviewing.  Patch simplified as suggested.  Is it OK?
>
> +inline hashval_t
> +ddr_hasher::hash (const data_dependence_relation *ddr)
> +{
> +  return iterative_hash_object (DDR_A (ddr),
> +                               iterative_hash_object (DDR_B (ddr), 0));
> +}
> +
>
> please use
>
>     inchash::hash h;
>     h.add_ptr (DDR_A (ddr));
>     h.add_ptr (DDR_B (ddr));
>     return h.end ();
>
> Ok with that change.
Done, patch updated.

Thanks,
bin
>
> Richard.
>
>> Thanks,
>> bin
>> 2017-06-17  Bin Cheng  <bin.cheng@arm.com>
>>
>>     * tree-loop-distribution.c (struct ddr_hasher): New.
>>     (ddr_hasher::hash, ::equal, get_data_dependence): New function.
>>     (ddrs_table): New.
>>     (classify_partition): Call get_data_dependence.
>>     (pg_add_dependence_edges): Ditto.
>>     (distribute_loop): Release data dependence hash table.

[-- Attachment #2: 0009-cache-data-dependence-20170609.txt.patch --]
[-- Type: text/x-patch, Size: 5672 bytes --]

From f1bc5437a186af22398c6ab7071ba1ef8d0dd897 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Fri, 9 Jun 2017 13:02:09 +0100
Subject: [PATCH 09/13] cache-data-dependence-20170609.txt

---
 gcc/tree-loop-distribution.c | 99 ++++++++++++++++++++++++++++++++------------
 1 file changed, 73 insertions(+), 26 deletions(-)

diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index 119863f..516d5f7 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -70,6 +70,35 @@ along with GCC; see the file COPYING3.  If not see
 #define MAX_DATAREFS_NUM \
 	((unsigned) PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
 
+/* Hashtable helpers.  */
+
+struct ddr_hasher : nofree_ptr_hash <struct data_dependence_relation>
+{
+  static inline hashval_t hash (const data_dependence_relation *);
+  static inline bool equal (const data_dependence_relation *,
+			    const data_dependence_relation *);
+};
+
+/* Hash function for data dependence.  */
+
+inline hashval_t
+ddr_hasher::hash (const data_dependence_relation *ddr)
+{
+  inchash::hash h;
+  h.add_ptr (DDR_A (ddr));
+  h.add_ptr (DDR_B (ddr));
+  return h.end ();
+}
+
+/* Hash table equality function for data dependence.  */
+
+inline bool
+ddr_hasher::equal (const data_dependence_relation *ddr1,
+		   const data_dependence_relation *ddr2)
+{
+  return (DDR_A (ddr1) == DDR_A (ddr2) && DDR_B (ddr1) == DDR_B (ddr2));
+}
+
 /* The loop (nest) to be distributed.  */
 static vec<loop_p> loop_nest;
 
@@ -79,6 +108,10 @@ static vec<data_reference_p> datarefs_vec;
 /* Store index of data reference in aux field.  */
 #define DR_INDEX(dr)      ((uintptr_t) (dr)->aux)
 
+/* Hash table for data dependence relation in the loop to be distributed.  */
+static hash_table<ddr_hasher> ddrs_table (389);
+
+
 /* A Reduced Dependence Graph (RDG) vertex representing a statement.  */
 struct rdg_vertex
 {
@@ -1057,6 +1090,32 @@ generate_code_for_partition (struct loop *loop,
   return false;
 }
 
+/* Return data dependence relation for data references A and B.  The two
+   data references must be in lexicographic order wrto reduced dependence
+   graph RDG.  We firstly try to find ddr from global ddr hash table.  If
+   it doesn't exist, compute the ddr and cache it.  */
+
+static data_dependence_relation *
+get_data_dependence (struct graph *rdg, data_reference_p a, data_reference_p b)
+{
+  struct data_dependence_relation ent, **slot;
+  struct data_dependence_relation *ddr;
+
+  gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b));
+  gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a))
+	      <= rdg_vertex_for_stmt (rdg, DR_STMT (b)));
+  ent.a = a;
+  ent.b = b;
+  slot = ddrs_table.find_slot (&ent, INSERT);
+  if (*slot == NULL)
+    {
+      ddr = initialize_data_dependence_relation (a, b, loop_nest);
+      compute_affine_dependence (ddr, loop_nest[0]);
+      *slot = ddr;
+    }
+
+  return *slot;
+}
 
 /* Returns a partition with all the statements needed for computing
    the vertex V of the RDG, also including the loop exit conditions.  */
@@ -1223,44 +1282,27 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition)
 	return;
       /* Now check that if there is a dependence this dependence is
          of a suitable form for memmove.  */
-      vec<loop_p> loops = vNULL;
-      ddr_p ddr;
-      loops.safe_push (loop);
-      ddr = initialize_data_dependence_relation (single_load, single_store,
-						 loops);
-      compute_affine_dependence (ddr, loop);
+      ddr_p ddr = get_data_dependence (rdg, single_load, single_store);
       if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
-	{
-	  free_dependence_relation (ddr);
-	  loops.release ();
-	  return;
-	}
+	return;
+
       if (DDR_ARE_DEPENDENT (ddr) != chrec_known)
 	{
 	  if (DDR_NUM_DIST_VECTS (ddr) == 0)
-	    {
-	      free_dependence_relation (ddr);
-	      loops.release ();
-	      return;
-	    }
+	    return;
+
 	  lambda_vector dist_v;
 	  FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
 	    {
 	      int dist = dist_v[index_in_loop_nest (loop->num,
 						    DDR_LOOP_NEST (ddr))];
 	      if (dist > 0 && !DDR_REVERSED_P (ddr))
-		{
-		  free_dependence_relation (ddr);
-		  loops.release ();
-		  return;
-		}
+		return;
 	    }
 	  partition->kind = PKIND_MEMMOVE;
 	}
       else
 	partition->kind = PKIND_MEMCPY;
-      free_dependence_relation (ddr);
-      loops.release ();
       partition->main_dr = single_store;
       partition->secondary_dr = single_load;
       partition->niter = nb_iter;
@@ -1472,8 +1514,7 @@ pg_add_dependence_edges (struct graph *rdg, int dir,
 	      std::swap (dr1, dr2);
 	      this_dir = -this_dir;
 	    }
-	  ddr = initialize_data_dependence_relation (dr1, dr2, loop_nest);
-	  compute_affine_dependence (ddr, loop_nest[0]);
+	  ddr = get_data_dependence (rdg, dr1, dr2);
 	  if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 	    this_dir = 2;
 	  else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
@@ -1499,7 +1540,6 @@ pg_add_dependence_edges (struct graph *rdg, int dir,
 	    }
 	  else
 	    this_dir = 0;
-	  free_dependence_relation (ddr);
 	  if (this_dir == 2)
 	    return 2;
 	  else if (dir == 0)
@@ -1762,6 +1802,13 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts,
  ldist_done:
   loop_nest.release ();
   free_data_refs (datarefs_vec);
+  for (hash_table<ddr_hasher>::iterator iter = ddrs_table.begin ();
+       iter != ddrs_table.end (); ++iter)
+    {
+      free_dependence_relation (*iter);
+      *iter = NULL;
+    }
+  ddrs_table.empty ();
 
   FOR_EACH_VEC_ELT (partitions, i, partition)
     partition_free (partition);
-- 
1.9.1

Re: [PATCH GCC][10/13]Compute and cache data dependence relation

[Richard Biener]

On Fri, Jun 23, 2017 at 12:22 PM, Bin.Cheng <amker.cheng@gmail.com> wrote:
> On Tue, Jun 20, 2017 at 12:32 PM, Richard Biener
> <richard.guenther@gmail.com> wrote:
>> On Tue, Jun 20, 2017 at 11:15 AM, Bin.Cheng <amker.cheng@gmail.com> wrote:
>>> On Fri, Jun 16, 2017 at 11:03 AM, Richard Biener
>>> <richard.guenther@gmail.com> wrote:
>>>> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>>> Hi,
>>>>> This patch computes and caches data dependence relation in a hash table
>>>>> so that it can be queried multiple times later for partition dependence
>>>>> check.
>>>>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>>>>
>>>> +/* Vector of data dependence relations.  */
>>>> +static vec<ddr_p> *ddrs_vec;
>>>> +
>>>> +/* Hash table for data dependence relation in the loop to be distributed.  */
>>>> +static hash_table<ddr_entry_hasher> *ddrs_table;
>>>>
>>>> avoid the extra indirection.
>>>>
>>>> +/* Hashtable entry for data reference relation.  */
>>>> +struct ddr_entry
>>>> +{
>>>> +  data_reference_p a;
>>>> +  data_reference_p b;
>>>> +  ddr_p ddr;
>>>> +  hashval_t hash;
>>>> +};
>>>> ...
>>>> +/* Hash table equality function for data reference relation.  */
>>>> +
>>>> +inline bool
>>>> +ddr_entry_hasher::equal (const ddr_entry *entry1, const ddr_entry *entry2)
>>>> +{
>>>> +  return (entry1->hash == entry2->hash
>>>> +         && DR_STMT (entry1->a) == DR_STMT (entry2->a)
>>>> +         && DR_STMT (entry1->b) == DR_STMT (entry2->b)
>>>> +         && operand_equal_p (DR_REF (entry1->a), DR_REF (entry2->a), 0)
>>>> +         && operand_equal_p (DR_REF (entry1->b), DR_REF (entry2->b), 0));
>>>> +}
>>>>
>>>> what's the issue with using hash_table <ddr_p> with a custom hasher?
>>>> That is, simply key on the dataref pointers (hash them, compare those
>>>> for equality)?
>>>>
>>>> Your scheme looks too complicated / expensive to me ...
>>>>
>>>> You can drop ddrs_vec needed only for memory removal if you traverse
>>>> the hashtable.
>>> Thanks for reviewing.  Patch simplified as suggested.  Is it OK?
>>
>> +inline hashval_t
>> +ddr_hasher::hash (const data_dependence_relation *ddr)
>> +{
>> +  return iterative_hash_object (DDR_A (ddr),
>> +                               iterative_hash_object (DDR_B (ddr), 0));
>> +}
>> +
>>
>> please use
>>
>>     inchash::hash h;
>>     h.add_ptr (DDR_A (ddr));
>>     h.add_ptr (DDR_B (ddr));
>>     return h.end ();
>>
>> Ok with that change.
> Done, patch updated.

Ok.

> Thanks,
> bin
>>
>> Richard.
>>
>>> Thanks,
>>> bin
>>> 2017-06-17  Bin Cheng  <bin.cheng@arm.com>
>>>
>>>     * tree-loop-distribution.c (struct ddr_hasher): New.
>>>     (ddr_hasher::hash, ::equal, get_data_dependence): New function.
>>>     (ddrs_table): New.
>>>     (classify_partition): Call get_data_dependence.
>>>     (pg_add_dependence_edges): Ditto.
>>>     (distribute_loop): Release data dependence hash table.