Re: [PATCH GCC][10/13]Compute and cache data dependence relation
On Fri, Jun 23, 2017 at 12:22 PM, Bin.Chengwrote: > On Tue, Jun 20, 2017 at 12:32 PM, Richard Biener > wrote: >> On Tue, Jun 20, 2017 at 11:15 AM, Bin.Cheng wrote: >>> On Fri, Jun 16, 2017 at 11:03 AM, Richard Biener >>> wrote: On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng 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 *ddrs_vec; + +/* Hash table for data dependence relation in the loop to be distributed. */ +static hash_table *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 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 >>> >>> * 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
On Tue, Jun 20, 2017 at 12:32 PM, Richard Bienerwrote: > On Tue, Jun 20, 2017 at 11:15 AM, Bin.Cheng wrote: >> On Fri, Jun 16, 2017 at 11:03 AM, Richard Biener >> wrote: >>> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng 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 *ddrs_vec; >>> + >>> +/* Hash table for data dependence relation in the loop to be distributed. >>> */ >>> +static hash_table *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 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 >> >> * 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 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 +{ + 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_nest; @@ -79,6 +108,10 @@ static vec 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 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
Re: [PATCH GCC][10/13]Compute and cache data dependence relation
On Tue, Jun 20, 2017 at 11:15 AM, Bin.Chengwrote: > On Fri, Jun 16, 2017 at 11:03 AM, Richard Biener > wrote: >> On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng 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 *ddrs_vec; >> + >> +/* Hash table for data dependence relation in the loop to be distributed. >> */ >> +static hash_table *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 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 > > * 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
On Fri, Jun 16, 2017 at 11:03 AM, Richard Bienerwrote: > On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng 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 *ddrs_vec; > + > +/* Hash table for data dependence relation in the loop to be distributed. */ > +static hash_table *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 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 * 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 6a3d78078355df492877955b5f00784a795a94d8 Mon Sep 17 00:00:00 2001 From: Bin Cheng 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 +{ + 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_nest; @@ -79,6 +106,10 @@ static vec 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 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 (, 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
Re: [PATCH GCC][10/13]Compute and cache data dependence relation
On Mon, Jun 12, 2017 at 7:03 PM, Bin Chengwrote: > 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 *ddrs_vec; + +/* Hash table for data dependence relation in the loop to be distributed. */ +static hash_table *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 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 > > * 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.
[PATCH GCC][10/13]Compute and cache data dependence relation
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* 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.From 6075d1db94b7f130a91bba53125bed5754a46f59 Mon Sep 17 00:00:00 2001 From: Bin Cheng 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 +{ + 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_nest; @@ -75,6 +112,13 @@ static vec *datarefs_vec; /* Map of data reference in the loop to a unique id. */ static hash_map *datarefs_map; +/* Vector of data dependence relations. */ +static vec *ddrs_vec; + +/* Hash table for data dependence relation in the loop to be distributed. */ +static hash_table *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 (, 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 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