On Tue, Jun 20, 2017 at 12:32 PM, Richard Biener
<richard.guent...@gmail.com> wrote:
> On Tue, Jun 20, 2017 at 11:15 AM, Bin.Cheng <amker.ch...@gmail.com> wrote:
>> On Fri, Jun 16, 2017 at 11:03 AM, Richard Biener
>> <richard.guent...@gmail.com> wrote:
>>> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng <bin.ch...@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.ch...@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.
From f1bc5437a186af22398c6ab7071ba1ef8d0dd897 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binch...@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
