From 1d3607e7aad7855e456b7a569f242703451911ab Mon Sep 17 00:00:00 2001 From: Bin Cheng 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 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 drs1, - vec 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 stmts, pg = new_graph (partitions.length ()); struct pgdata { struct partition *partition; - vec writes; - vec 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 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 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