* [PATCH GCC][08/13]Refactoring structure partition for distribution @ 2017-06-12 17:03 Bin Cheng 2017-06-14 13:47 ` Richard Biener 0 siblings, 1 reply; 6+ messages in thread From: Bin Cheng @ 2017-06-12 17:03 UTC (permalink / raw) To: gcc-patches; +Cc: nd [-- Attachment #1: Type: text/plain, Size: 710 bytes --] Hi, This patch refactors struct partition for later distribution. It records bitmap of data references in struct partition rather than vertices' data in partition dependence graph. It simplifies code as well as enables following rewriting. 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 partition): New fields recording its data references. (partition_alloc, partition_free): Init and release data refs. (partition_merge_into): Merge data refs. (build_rdg_partition_for_vertex): Collect data refs for partition. (distribute_loop): Remve data refs from vertice data of partition graph. [-- Attachment #2: 0008-struct-partition-refactoring-20170607.txt --] [-- Type: text/plain, Size: 9286 bytes --] From 1d3607e7aad7855e456b7a569f242703451911ab Mon Sep 17 00:00:00 2001 From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com> Date: Fri, 9 Jun 2017 12:29:24 +0100 Subject: [PATCH 08/14] struct-partition-refactoring-20170607.txt --- gcc/tree-loop-distribution.c | 180 ++++++++++++++++++++++++------------------- 1 file changed, 101 insertions(+), 79 deletions(-) diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index 0b16024..9a0e101 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -496,30 +496,43 @@ enum partition_kind { PKIND_NORMAL, PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE }; +/* Partition for loop distribution. */ struct partition { + /* Statements of the partition. */ bitmap stmts; + /* Loops of the partition. */ bitmap loops; + /* True if the partition defines variable which is used outside of loop. */ bool reduction_p; + /* For builtin partition, true if it executes one iteration more than + number of loop (latch) iterations. */ bool plus_one; enum partition_kind kind; /* data-references a kind != PKIND_NORMAL partition is about. */ data_reference_p main_dr; data_reference_p secondary_dr; + /* Number of loop (latch) iterations. */ tree niter; + /* Read data references in the partition. */ + bitmap reads; + /* Write data references in the partition. */ + bitmap writes; }; /* Allocate and initialize a partition from BITMAP. */ static partition * -partition_alloc (bitmap stmts, bitmap loops) +partition_alloc (void) { partition *partition = XCNEW (struct partition); - partition->stmts = stmts ? stmts : BITMAP_ALLOC (NULL); - partition->loops = loops ? loops : BITMAP_ALLOC (NULL); + partition->stmts = BITMAP_ALLOC (NULL); + partition->loops = BITMAP_ALLOC (NULL); partition->reduction_p = false; partition->kind = PKIND_NORMAL; + partition->reads = BITMAP_ALLOC (NULL); + partition->writes = BITMAP_ALLOC (NULL); return partition; } @@ -530,6 +543,8 @@ partition_free (partition *partition) { BITMAP_FREE (partition->stmts); BITMAP_FREE (partition->loops); + BITMAP_FREE (partition->reads); + BITMAP_FREE (partition->writes); free (partition); } @@ -577,6 +592,9 @@ partition_merge_into (partition *dest, partition *partition, enum fuse_type ft) if (partition_reduction_p (partition)) dest->reduction_p = true; + bitmap_ior_into (dest->reads, partition->reads); + bitmap_ior_into (dest->writes, partition->writes); + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Fuse partitions because %s:\n", fuse_message[ft]); @@ -1050,10 +1068,11 @@ generate_code_for_partition (struct loop *loop, static partition * build_rdg_partition_for_vertex (struct graph *rdg, int v) { - partition *partition = partition_alloc (NULL, NULL); + partition *partition = partition_alloc (); auto_vec<int, 3> nodes; - unsigned i; + unsigned i, j; int x; + data_reference_p dr; graphds_dfs (rdg, &v, 1, &nodes, false, NULL); @@ -1062,6 +1081,18 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) bitmap_set_bit (partition->stmts, x); bitmap_set_bit (partition->loops, loop_containing_stmt (RDG_STMT (rdg, x))->num); + + for (j = 0; RDG_DATAREFS (rdg, x).iterate (j, &dr); ++j) + { + int *slot = datarefs_map->get (dr); + + gcc_assert (slot != NULL); + + if (DR_IS_READ (dr)) + bitmap_set_bit (partition->reads, *slot); + else + bitmap_set_bit (partition->writes, *slot); + } } return partition; @@ -1426,63 +1457,69 @@ partition_contains_all_rw (struct graph *rdg, static int pg_add_dependence_edges (struct graph *rdg, int dir, - vec<data_reference_p> drs1, - vec<data_reference_p> drs2) + bitmap drs1, bitmap drs2) { - data_reference_p dr1, dr2; + unsigned i, j; + bitmap_iterator bi, bj; + data_reference_p dr1, dr2, saved_dr1; /* dependence direction - 0 is no dependence, -1 is back, 1 is forth, 2 is both (we can stop then, merging will occur). */ - for (int ii = 0; drs1.iterate (ii, &dr1); ++ii) - for (int jj = 0; drs2.iterate (jj, &dr2); ++jj) - { - data_reference_p saved_dr1 = dr1; - int this_dir = 1; - ddr_p ddr; - /* Re-shuffle data-refs to be in dominator order. */ - if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) - > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) - { - std::swap (dr1, dr2); - this_dir = -this_dir; - } - ddr = initialize_data_dependence_relation (dr1, dr2, *loop_nest); - compute_affine_dependence (ddr, (*loop_nest)[0]); - if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) - this_dir = 2; - else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) - { - if (DDR_REVERSED_P (ddr)) - { - std::swap (dr1, dr2); - this_dir = -this_dir; - } - /* Known dependences can still be unordered througout the - iteration space, see gcc.dg/tree-ssa/ldist-16.c. */ - if (DDR_NUM_DIST_VECTS (ddr) != 1) - this_dir = 2; - /* If the overlap is exact preserve stmt order. */ - else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) - ; - else - { - /* Else as the distance vector is lexicographic positive - swap the dependence direction. */ - this_dir = -this_dir; - } - } - else - this_dir = 0; - free_dependence_relation (ddr); - if (this_dir == 2) - return 2; - else if (dir == 0) - dir = this_dir; - else if (this_dir != 0 && dir != this_dir) - return 2; - /* Shuffle "back" dr1. */ - dr1 = saved_dr1; - } + EXECUTE_IF_SET_IN_BITMAP (drs1, 0, i, bi) + { + dr1 = (*datarefs_vec)[i]; + + EXECUTE_IF_SET_IN_BITMAP (drs2, 0, j, bj) + { + dr2 = (*datarefs_vec)[j]; + saved_dr1 = dr1; + int this_dir = 1; + ddr_p ddr; + /* Re-shuffle data-refs to be in dominator order. */ + if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) + > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) + { + std::swap (dr1, dr2); + this_dir = -this_dir; + } + ddr = initialize_data_dependence_relation (dr1, dr2, *loop_nest); + compute_affine_dependence (ddr, (*loop_nest)[0]); + if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) + this_dir = 2; + else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + { + if (DDR_REVERSED_P (ddr)) + { + std::swap (dr1, dr2); + this_dir = -this_dir; + } + /* Known dependences can still be unordered througout the + iteration space, see gcc.dg/tree-ssa/ldist-16.c. */ + if (DDR_NUM_DIST_VECTS (ddr) != 1) + this_dir = 2; + /* If the overlap is exact preserve stmt order. */ + else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) + ; + else + { + /* Else as the distance vector is lexicographic positive + swap the dependence direction. */ + this_dir = -this_dir; + } + } + else + this_dir = 0; + free_dependence_relation (ddr); + if (this_dir == 2) + return 2; + else if (dir == 0) + dir = this_dir; + else if (this_dir != 0 && dir != this_dir) + return 2; + /* Shuffle "back" dr1. */ + dr1 = saved_dr1; + } + } return dir; } @@ -1652,28 +1689,15 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, pg = new_graph (partitions.length ()); struct pgdata { struct partition *partition; - vec<data_reference_p> writes; - vec<data_reference_p> reads; }; #define PGDATA(i) ((pgdata *)(pg->vertices[i].data)) for (i = 0; partitions.iterate (i, &partition); ++i) { vertex *v = &pg->vertices[i]; pgdata *data = new pgdata; - data_reference_p dr; /* FIXME - leaks. */ v->data = data; - bitmap_iterator bi; - unsigned j; data->partition = partition; - data->reads = vNULL; - data->writes = vNULL; - EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, j, bi) - for (int k = 0; RDG_DATAREFS (rdg, j).iterate (k, &dr); ++k) - if (DR_IS_READ (dr)) - data->reads.safe_push (dr); - else - data->writes.safe_push (dr); } struct partition *partition1, *partition2; for (i = 0; partitions.iterate (i, &partition1); ++i) @@ -1683,16 +1707,16 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, 1 is forth, 2 is both (we can stop then, merging will occur). */ int dir = 0; dir = pg_add_dependence_edges (rdg, dir, - PGDATA(i)->writes, - PGDATA(j)->reads); + partition1->writes, + partition2->reads); if (dir != 2) dir = pg_add_dependence_edges (rdg, dir, - PGDATA(i)->reads, - PGDATA(j)->writes); + partition1->reads, + partition2->writes); if (dir != 2) dir = pg_add_dependence_edges (rdg, dir, - PGDATA(i)->writes, - PGDATA(j)->writes); + partition1->writes, + partition2->writes); if (dir == 1 || dir == 2) add_edge (pg, i, j); if (dir == -1 || dir == 2) @@ -1738,8 +1762,6 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, pgdata *data = PGDATA (i); if (data->partition) partitions.safe_push (data->partition); - data->reads.release (); - data->writes.release (); delete data; } gcc_assert (partitions.length () == (unsigned)num_sccs); -- 1.9.1 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][08/13]Refactoring structure partition for distribution 2017-06-12 17:03 [PATCH GCC][08/13]Refactoring structure partition for distribution Bin Cheng @ 2017-06-14 13:47 ` Richard Biener 2017-06-19 13:37 ` Bin.Cheng 0 siblings, 1 reply; 6+ messages in thread From: Richard Biener @ 2017-06-14 13:47 UTC (permalink / raw) To: Bin Cheng; +Cc: gcc-patches, nd On Mon, Jun 12, 2017 at 7:03 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: > Hi, > This patch refactors struct partition for later distribution. It records > bitmap of data references in struct partition rather than vertices' data in > partition dependence graph. It simplifies code as well as enables following > rewriting. > Bootstrap and test on x86_64 and AArch64. Is it OK? Ok. Richard. > Thanks, > bin > > 2017-06-07 Bin Cheng <bin.cheng@arm.com> > > * tree-loop-distribution.c (struct partition): New fields recording > its data references. > (partition_alloc, partition_free): Init and release data refs. > (partition_merge_into): Merge data refs. > (build_rdg_partition_for_vertex): Collect data refs for partition. > (distribute_loop): Remve data refs from vertice data of partition > graph. ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][08/13]Refactoring structure partition for distribution 2017-06-14 13:47 ` Richard Biener @ 2017-06-19 13:37 ` Bin.Cheng 2017-06-19 15:18 ` Richard Biener 0 siblings, 1 reply; 6+ messages in thread From: Bin.Cheng @ 2017-06-19 13:37 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 1117 bytes --] On Wed, Jun 14, 2017 at 2:47 PM, 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 refactors struct partition for later distribution. It records >> bitmap of data references in struct partition rather than vertices' data in >> partition dependence graph. It simplifies code as well as enables following >> rewriting. >> Bootstrap and test on x86_64 and AArch64. Is it OK? > > Ok. Hi, I updated patch by merging read/write data references together in struct partition. This helps remove code duplication. Is it OK? Thanks, bin 2017-06-07 Bin Cheng <bin.cheng@arm.com> * tree-loop-distribution.c (struct partition): New field recording its data reference. (partition_alloc, partition_free): Init and release data refs. (partition_merge_into): Merge data refs. (build_rdg_partition_for_vertex): Collect data refs for partition. (pg_add_dependence_edges): Change parameters from vector to bitmap. Update uses. (distribute_loop): Remve data refs from vertice data of partition graph. [-- Attachment #2: 0007-struct-partition-refactoring-20170608.txt.patch --] [-- Type: text/x-patch, Size: 9138 bytes --] From 9a3e3e96703fd792d71d964b31a12a3ce7dc5448 Mon Sep 17 00:00:00 2001 From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com> Date: Fri, 9 Jun 2017 12:29:24 +0100 Subject: [PATCH 07/13] struct-partition-refactoring-20170608.txt --- gcc/tree-loop-distribution.c | 179 +++++++++++++++++++++++-------------------- 1 file changed, 94 insertions(+), 85 deletions(-) diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index a013556..03bb735 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -500,30 +500,40 @@ enum partition_kind { PKIND_NORMAL, PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE }; +/* Partition for loop distribution. */ struct partition { + /* Statements of the partition. */ bitmap stmts; + /* Loops of the partition. */ bitmap loops; + /* True if the partition defines variable which is used outside of loop. */ bool reduction_p; + /* For builtin partition, true if it executes one iteration more than + number of loop (latch) iterations. */ bool plus_one; enum partition_kind kind; /* data-references a kind != PKIND_NORMAL partition is about. */ data_reference_p main_dr; data_reference_p secondary_dr; + /* Number of loop (latch) iterations. */ tree niter; + /* Data references in the partition. */ + bitmap datarefs; }; /* Allocate and initialize a partition from BITMAP. */ static partition * -partition_alloc (bitmap stmts, bitmap loops) +partition_alloc (void) { partition *partition = XCNEW (struct partition); - partition->stmts = stmts ? stmts : BITMAP_ALLOC (NULL); - partition->loops = loops ? loops : BITMAP_ALLOC (NULL); + partition->stmts = BITMAP_ALLOC (NULL); + partition->loops = BITMAP_ALLOC (NULL); partition->reduction_p = false; partition->kind = PKIND_NORMAL; + partition->datarefs = BITMAP_ALLOC (NULL); return partition; } @@ -534,6 +544,7 @@ partition_free (partition *partition) { BITMAP_FREE (partition->stmts); BITMAP_FREE (partition->loops); + BITMAP_FREE (partition->datarefs); free (partition); } @@ -581,6 +592,8 @@ partition_merge_into (partition *dest, partition *partition, enum fuse_type ft) if (partition_reduction_p (partition)) dest->reduction_p = true; + bitmap_ior_into (dest->datarefs, partition->datarefs); + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Fuse partitions because %s:\n", fuse_message[ft]); @@ -1051,10 +1064,11 @@ generate_code_for_partition (struct loop *loop, static partition * build_rdg_partition_for_vertex (struct graph *rdg, int v) { - partition *partition = partition_alloc (NULL, NULL); + partition *partition = partition_alloc (); auto_vec<int, 3> nodes; - unsigned i; + unsigned i, j; int x; + data_reference_p dr; graphds_dfs (rdg, &v, 1, &nodes, false, NULL); @@ -1063,6 +1077,14 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) bitmap_set_bit (partition->stmts, x); bitmap_set_bit (partition->loops, loop_containing_stmt (RDG_STMT (rdg, x))->num); + + for (j = 0; RDG_DATAREFS (rdg, x).iterate (j, &dr); ++j) + { + unsigned idx = (unsigned) DR_INDEX (dr); + gcc_assert (idx < datarefs_vec.length ()); + + bitmap_set_bit (partition->datarefs, idx); + } } return partition; @@ -1427,63 +1449,74 @@ partition_contains_all_rw (struct graph *rdg, static int pg_add_dependence_edges (struct graph *rdg, int dir, - vec<data_reference_p> drs1, - vec<data_reference_p> drs2) + bitmap drs1, bitmap drs2) { - data_reference_p dr1, dr2; + unsigned i, j; + bitmap_iterator bi, bj; + data_reference_p dr1, dr2, saved_dr1; /* dependence direction - 0 is no dependence, -1 is back, 1 is forth, 2 is both (we can stop then, merging will occur). */ - for (int ii = 0; drs1.iterate (ii, &dr1); ++ii) - for (int jj = 0; drs2.iterate (jj, &dr2); ++jj) - { - data_reference_p saved_dr1 = dr1; - int this_dir = 1; - ddr_p ddr; - /* Re-shuffle data-refs to be in dominator order. */ - if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) - > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) - { - std::swap (dr1, dr2); - this_dir = -this_dir; - } - ddr = initialize_data_dependence_relation (dr1, dr2, loop_nest); - compute_affine_dependence (ddr, loop_nest[0]); - if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) - this_dir = 2; - else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) - { - if (DDR_REVERSED_P (ddr)) - { - std::swap (dr1, dr2); - this_dir = -this_dir; - } - /* Known dependences can still be unordered througout the - iteration space, see gcc.dg/tree-ssa/ldist-16.c. */ - if (DDR_NUM_DIST_VECTS (ddr) != 1) - this_dir = 2; - /* If the overlap is exact preserve stmt order. */ - else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) - ; - else - { - /* Else as the distance vector is lexicographic positive - swap the dependence direction. */ - this_dir = -this_dir; - } - } - else - this_dir = 0; - free_dependence_relation (ddr); - if (this_dir == 2) - return 2; - else if (dir == 0) - dir = this_dir; - else if (this_dir != 0 && dir != this_dir) - return 2; - /* Shuffle "back" dr1. */ - dr1 = saved_dr1; - } + EXECUTE_IF_SET_IN_BITMAP (drs1, 0, i, bi) + { + dr1 = datarefs_vec[i]; + + EXECUTE_IF_SET_IN_BITMAP (drs2, 0, j, bj) + { + dr2 = datarefs_vec[j]; + + /* Skip all <read, read> data dependence. */ + if (DR_IS_READ (dr1) && DR_IS_READ (dr2)) + continue; + + saved_dr1 = dr1; + int this_dir = 1; + ddr_p ddr; + /* Re-shuffle data-refs to be in dominator order. */ + if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) + > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) + { + std::swap (dr1, dr2); + this_dir = -this_dir; + } + ddr = initialize_data_dependence_relation (dr1, dr2, loop_nest); + compute_affine_dependence (ddr, loop_nest[0]); + if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) + this_dir = 2; + else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + { + if (DDR_REVERSED_P (ddr)) + { + std::swap (dr1, dr2); + this_dir = -this_dir; + } + /* Known dependences can still be unordered througout the + iteration space, see gcc.dg/tree-ssa/ldist-16.c. */ + if (DDR_NUM_DIST_VECTS (ddr) != 1) + this_dir = 2; + /* If the overlap is exact preserve stmt order. */ + else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) + ; + else + { + /* Else as the distance vector is lexicographic positive + swap the dependence direction. */ + this_dir = -this_dir; + } + } + else + this_dir = 0; + free_dependence_relation (ddr); + if (this_dir == 2) + return 2; + else if (dir == 0) + dir = this_dir; + else if (this_dir != 0 && dir != this_dir) + return 2; + /* Shuffle "back" dr1. */ + dr1 = saved_dr1; + } + } return dir; } @@ -1644,28 +1677,15 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, pg = new_graph (partitions.length ()); struct pgdata { struct partition *partition; - vec<data_reference_p> writes; - vec<data_reference_p> reads; }; #define PGDATA(i) ((pgdata *)(pg->vertices[i].data)) for (i = 0; partitions.iterate (i, &partition); ++i) { vertex *v = &pg->vertices[i]; pgdata *data = new pgdata; - data_reference_p dr; /* FIXME - leaks. */ v->data = data; - bitmap_iterator bi; - unsigned j; data->partition = partition; - data->reads = vNULL; - data->writes = vNULL; - EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, j, bi) - for (int k = 0; RDG_DATAREFS (rdg, j).iterate (k, &dr); ++k) - if (DR_IS_READ (dr)) - data->reads.safe_push (dr); - else - data->writes.safe_push (dr); } struct partition *partition1, *partition2; for (i = 0; partitions.iterate (i, &partition1); ++i) @@ -1673,18 +1693,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, { /* dependence direction - 0 is no dependence, -1 is back, 1 is forth, 2 is both (we can stop then, merging will occur). */ - int dir = 0; - dir = pg_add_dependence_edges (rdg, dir, - PGDATA(i)->writes, - PGDATA(j)->reads); - if (dir != 2) - dir = pg_add_dependence_edges (rdg, dir, - PGDATA(i)->reads, - PGDATA(j)->writes); - if (dir != 2) - dir = pg_add_dependence_edges (rdg, dir, - PGDATA(i)->writes, - PGDATA(j)->writes); + int dir = pg_add_dependence_edges (rdg, dir, + partition1->datarefs, + partition2->datarefs); if (dir == 1 || dir == 2) add_edge (pg, i, j); if (dir == -1 || dir == 2) @@ -1730,8 +1741,6 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, pgdata *data = PGDATA (i); if (data->partition) partitions.safe_push (data->partition); - data->reads.release (); - data->writes.release (); delete data; } gcc_assert (partitions.length () == (unsigned)num_sccs); -- 1.9.1 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][08/13]Refactoring structure partition for distribution 2017-06-19 13:37 ` Bin.Cheng @ 2017-06-19 15:18 ` Richard Biener 2017-06-23 10:29 ` Bin.Cheng 0 siblings, 1 reply; 6+ messages in thread From: Richard Biener @ 2017-06-19 15:18 UTC (permalink / raw) To: Bin.Cheng; +Cc: gcc-patches On Mon, Jun 19, 2017 at 3:37 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Wed, Jun 14, 2017 at 2:47 PM, 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 refactors struct partition for later distribution. It records >>> bitmap of data references in struct partition rather than vertices' data in >>> partition dependence graph. It simplifies code as well as enables following >>> rewriting. >>> Bootstrap and test on x86_64 and AArch64. Is it OK? >> >> Ok. > Hi, > I updated patch by merging read/write data references together in > struct partition. This helps remove code duplication. Is it OK? Ok. Richard. > Thanks, > bin > 2017-06-07 Bin Cheng <bin.cheng@arm.com> > > * tree-loop-distribution.c (struct partition): New field recording > its data reference. > (partition_alloc, partition_free): Init and release data refs. > (partition_merge_into): Merge data refs. > (build_rdg_partition_for_vertex): Collect data refs for partition. > (pg_add_dependence_edges): Change parameters from vector to bitmap. > Update uses. > (distribute_loop): Remve data refs from vertice data of partition > graph. ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][08/13]Refactoring structure partition for distribution 2017-06-19 15:18 ` Richard Biener @ 2017-06-23 10:29 ` Bin.Cheng 2017-06-23 10:49 ` Richard Biener 0 siblings, 1 reply; 6+ messages in thread From: Bin.Cheng @ 2017-06-23 10:29 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches [-- Attachment #1: Type: text/plain, Size: 1926 bytes --] On Mon, Jun 19, 2017 at 4:18 PM, Richard Biener <richard.guenther@gmail.com> wrote: > On Mon, Jun 19, 2017 at 3:37 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >> On Wed, Jun 14, 2017 at 2:47 PM, 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 refactors struct partition for later distribution. It records >>>> bitmap of data references in struct partition rather than vertices' data in >>>> partition dependence graph. It simplifies code as well as enables following >>>> rewriting. >>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>> >>> Ok. >> Hi, >> I updated patch by merging read/write data references together in >> struct partition. This helps remove code duplication. Is it OK? > > Ok. Sorry I made a mistake when separating patch. The previous patch uses un-initialized variable "dir". Though related code was removed by following patch, for this specific version, the code is wrong. Is it OK? Like: + int dir = pg_add_dependence_edges (rdg, dir, + partition1->datarefs, + partition2->datarefs); Now changed to + int dir = pg_add_dependence_edges (rdg, 0, + partition1->datarefs, + partition2->datarefs); Thanks, bin > > Richard. > >> Thanks, >> bin >> 2017-06-07 Bin Cheng <bin.cheng@arm.com> >> >> * tree-loop-distribution.c (struct partition): New field recording >> its data reference. >> (partition_alloc, partition_free): Init and release data refs. >> (partition_merge_into): Merge data refs. >> (build_rdg_partition_for_vertex): Collect data refs for partition. >> (pg_add_dependence_edges): Change parameters from vector to bitmap. >> Update uses. >> (distribute_loop): Remve data refs from vertice data of partition >> graph. [-- Attachment #2: 0007-struct-partition-refactoring-20170608.txt.patch --] [-- Type: text/x-patch, Size: 9136 bytes --] From 324f9c5505cdf928e4178ab610aafc2800ca8577 Mon Sep 17 00:00:00 2001 From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com> Date: Fri, 9 Jun 2017 12:29:24 +0100 Subject: [PATCH 07/13] struct-partition-refactoring-20170608.txt --- gcc/tree-loop-distribution.c | 179 +++++++++++++++++++++++-------------------- 1 file changed, 94 insertions(+), 85 deletions(-) diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index a013556..eafd119 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -500,30 +500,40 @@ enum partition_kind { PKIND_NORMAL, PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE }; +/* Partition for loop distribution. */ struct partition { + /* Statements of the partition. */ bitmap stmts; + /* Loops of the partition. */ bitmap loops; + /* True if the partition defines variable which is used outside of loop. */ bool reduction_p; + /* For builtin partition, true if it executes one iteration more than + number of loop (latch) iterations. */ bool plus_one; enum partition_kind kind; /* data-references a kind != PKIND_NORMAL partition is about. */ data_reference_p main_dr; data_reference_p secondary_dr; + /* Number of loop (latch) iterations. */ tree niter; + /* Data references in the partition. */ + bitmap datarefs; }; /* Allocate and initialize a partition from BITMAP. */ static partition * -partition_alloc (bitmap stmts, bitmap loops) +partition_alloc (void) { partition *partition = XCNEW (struct partition); - partition->stmts = stmts ? stmts : BITMAP_ALLOC (NULL); - partition->loops = loops ? loops : BITMAP_ALLOC (NULL); + partition->stmts = BITMAP_ALLOC (NULL); + partition->loops = BITMAP_ALLOC (NULL); partition->reduction_p = false; partition->kind = PKIND_NORMAL; + partition->datarefs = BITMAP_ALLOC (NULL); return partition; } @@ -534,6 +544,7 @@ partition_free (partition *partition) { BITMAP_FREE (partition->stmts); BITMAP_FREE (partition->loops); + BITMAP_FREE (partition->datarefs); free (partition); } @@ -581,6 +592,8 @@ partition_merge_into (partition *dest, partition *partition, enum fuse_type ft) if (partition_reduction_p (partition)) dest->reduction_p = true; + bitmap_ior_into (dest->datarefs, partition->datarefs); + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Fuse partitions because %s:\n", fuse_message[ft]); @@ -1051,10 +1064,11 @@ generate_code_for_partition (struct loop *loop, static partition * build_rdg_partition_for_vertex (struct graph *rdg, int v) { - partition *partition = partition_alloc (NULL, NULL); + partition *partition = partition_alloc (); auto_vec<int, 3> nodes; - unsigned i; + unsigned i, j; int x; + data_reference_p dr; graphds_dfs (rdg, &v, 1, &nodes, false, NULL); @@ -1063,6 +1077,14 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) bitmap_set_bit (partition->stmts, x); bitmap_set_bit (partition->loops, loop_containing_stmt (RDG_STMT (rdg, x))->num); + + for (j = 0; RDG_DATAREFS (rdg, x).iterate (j, &dr); ++j) + { + unsigned idx = (unsigned) DR_INDEX (dr); + gcc_assert (idx < datarefs_vec.length ()); + + bitmap_set_bit (partition->datarefs, idx); + } } return partition; @@ -1427,63 +1449,74 @@ partition_contains_all_rw (struct graph *rdg, static int pg_add_dependence_edges (struct graph *rdg, int dir, - vec<data_reference_p> drs1, - vec<data_reference_p> drs2) + bitmap drs1, bitmap drs2) { - data_reference_p dr1, dr2; + unsigned i, j; + bitmap_iterator bi, bj; + data_reference_p dr1, dr2, saved_dr1; /* dependence direction - 0 is no dependence, -1 is back, 1 is forth, 2 is both (we can stop then, merging will occur). */ - for (int ii = 0; drs1.iterate (ii, &dr1); ++ii) - for (int jj = 0; drs2.iterate (jj, &dr2); ++jj) - { - data_reference_p saved_dr1 = dr1; - int this_dir = 1; - ddr_p ddr; - /* Re-shuffle data-refs to be in dominator order. */ - if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) - > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) - { - std::swap (dr1, dr2); - this_dir = -this_dir; - } - ddr = initialize_data_dependence_relation (dr1, dr2, loop_nest); - compute_affine_dependence (ddr, loop_nest[0]); - if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) - this_dir = 2; - else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) - { - if (DDR_REVERSED_P (ddr)) - { - std::swap (dr1, dr2); - this_dir = -this_dir; - } - /* Known dependences can still be unordered througout the - iteration space, see gcc.dg/tree-ssa/ldist-16.c. */ - if (DDR_NUM_DIST_VECTS (ddr) != 1) - this_dir = 2; - /* If the overlap is exact preserve stmt order. */ - else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) - ; - else - { - /* Else as the distance vector is lexicographic positive - swap the dependence direction. */ - this_dir = -this_dir; - } - } - else - this_dir = 0; - free_dependence_relation (ddr); - if (this_dir == 2) - return 2; - else if (dir == 0) - dir = this_dir; - else if (this_dir != 0 && dir != this_dir) - return 2; - /* Shuffle "back" dr1. */ - dr1 = saved_dr1; - } + EXECUTE_IF_SET_IN_BITMAP (drs1, 0, i, bi) + { + dr1 = datarefs_vec[i]; + + EXECUTE_IF_SET_IN_BITMAP (drs2, 0, j, bj) + { + dr2 = datarefs_vec[j]; + + /* Skip all <read, read> data dependence. */ + if (DR_IS_READ (dr1) && DR_IS_READ (dr2)) + continue; + + saved_dr1 = dr1; + int this_dir = 1; + ddr_p ddr; + /* Re-shuffle data-refs to be in dominator order. */ + if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) + > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) + { + std::swap (dr1, dr2); + this_dir = -this_dir; + } + ddr = initialize_data_dependence_relation (dr1, dr2, loop_nest); + compute_affine_dependence (ddr, loop_nest[0]); + if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) + this_dir = 2; + else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + { + if (DDR_REVERSED_P (ddr)) + { + std::swap (dr1, dr2); + this_dir = -this_dir; + } + /* Known dependences can still be unordered througout the + iteration space, see gcc.dg/tree-ssa/ldist-16.c. */ + if (DDR_NUM_DIST_VECTS (ddr) != 1) + this_dir = 2; + /* If the overlap is exact preserve stmt order. */ + else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) + ; + else + { + /* Else as the distance vector is lexicographic positive + swap the dependence direction. */ + this_dir = -this_dir; + } + } + else + this_dir = 0; + free_dependence_relation (ddr); + if (this_dir == 2) + return 2; + else if (dir == 0) + dir = this_dir; + else if (this_dir != 0 && dir != this_dir) + return 2; + /* Shuffle "back" dr1. */ + dr1 = saved_dr1; + } + } return dir; } @@ -1644,28 +1677,15 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, pg = new_graph (partitions.length ()); struct pgdata { struct partition *partition; - vec<data_reference_p> writes; - vec<data_reference_p> reads; }; #define PGDATA(i) ((pgdata *)(pg->vertices[i].data)) for (i = 0; partitions.iterate (i, &partition); ++i) { vertex *v = &pg->vertices[i]; pgdata *data = new pgdata; - data_reference_p dr; /* FIXME - leaks. */ v->data = data; - bitmap_iterator bi; - unsigned j; data->partition = partition; - data->reads = vNULL; - data->writes = vNULL; - EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, j, bi) - for (int k = 0; RDG_DATAREFS (rdg, j).iterate (k, &dr); ++k) - if (DR_IS_READ (dr)) - data->reads.safe_push (dr); - else - data->writes.safe_push (dr); } struct partition *partition1, *partition2; for (i = 0; partitions.iterate (i, &partition1); ++i) @@ -1673,18 +1693,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, { /* dependence direction - 0 is no dependence, -1 is back, 1 is forth, 2 is both (we can stop then, merging will occur). */ - int dir = 0; - dir = pg_add_dependence_edges (rdg, dir, - PGDATA(i)->writes, - PGDATA(j)->reads); - if (dir != 2) - dir = pg_add_dependence_edges (rdg, dir, - PGDATA(i)->reads, - PGDATA(j)->writes); - if (dir != 2) - dir = pg_add_dependence_edges (rdg, dir, - PGDATA(i)->writes, - PGDATA(j)->writes); + int dir = pg_add_dependence_edges (rdg, 0, + partition1->datarefs, + partition2->datarefs); if (dir == 1 || dir == 2) add_edge (pg, i, j); if (dir == -1 || dir == 2) @@ -1730,8 +1741,6 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, pgdata *data = PGDATA (i); if (data->partition) partitions.safe_push (data->partition); - data->reads.release (); - data->writes.release (); delete data; } gcc_assert (partitions.length () == (unsigned)num_sccs); -- 1.9.1 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH GCC][08/13]Refactoring structure partition for distribution 2017-06-23 10:29 ` Bin.Cheng @ 2017-06-23 10:49 ` Richard Biener 0 siblings, 0 replies; 6+ messages in thread From: Richard Biener @ 2017-06-23 10:49 UTC (permalink / raw) To: Bin.Cheng; +Cc: gcc-patches On Fri, Jun 23, 2017 at 12:29 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: > On Mon, Jun 19, 2017 at 4:18 PM, Richard Biener > <richard.guenther@gmail.com> wrote: >> On Mon, Jun 19, 2017 at 3:37 PM, Bin.Cheng <amker.cheng@gmail.com> wrote: >>> On Wed, Jun 14, 2017 at 2:47 PM, 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 refactors struct partition for later distribution. It records >>>>> bitmap of data references in struct partition rather than vertices' data in >>>>> partition dependence graph. It simplifies code as well as enables following >>>>> rewriting. >>>>> Bootstrap and test on x86_64 and AArch64. Is it OK? >>>> >>>> Ok. >>> Hi, >>> I updated patch by merging read/write data references together in >>> struct partition. This helps remove code duplication. Is it OK? >> >> Ok. > Sorry I made a mistake when separating patch. The previous patch uses > un-initialized variable "dir". Though related code was removed by > following patch, for this specific version, the code is wrong. Is it > OK? > Like: > + int dir = pg_add_dependence_edges (rdg, dir, > + partition1->datarefs, > + partition2->datarefs); > Now changed to > + int dir = pg_add_dependence_edges (rdg, 0, > + partition1->datarefs, > + partition2->datarefs); Ok. > Thanks, > bin > >> >> Richard. >> >>> Thanks, >>> bin >>> 2017-06-07 Bin Cheng <bin.cheng@arm.com> >>> >>> * tree-loop-distribution.c (struct partition): New field recording >>> its data reference. >>> (partition_alloc, partition_free): Init and release data refs. >>> (partition_merge_into): Merge data refs. >>> (build_rdg_partition_for_vertex): Collect data refs for partition. >>> (pg_add_dependence_edges): Change parameters from vector to bitmap. >>> Update uses. >>> (distribute_loop): Remve data refs from vertice data of partition >>> graph. ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2017-06-23 10:49 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-06-12 17:03 [PATCH GCC][08/13]Refactoring structure partition for distribution Bin Cheng 2017-06-14 13:47 ` Richard Biener 2017-06-19 13:37 ` Bin.Cheng 2017-06-19 15:18 ` Richard Biener 2017-06-23 10:29 ` Bin.Cheng 2017-06-23 10:49 ` Richard Biener
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).