From 3232fe2b92ca302ce776c07aaf3e8ab0945d080a Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Wed, 13 May 2020 11:37:47 +0800 Subject: Add missing unit dependence vector in data dependence analysis Current data dependence analysis misses unit distant vector if DRs in DDR have the same invariant access functions. This adds the vector as the constant access function case. 2020-05-13 Bin Cheng PR tree-optimization/94969 gcc/ * tree-data-dependence.c (constant_access_functions): Rename to... (invariant_access_functions): ...this. Add parameter. Check for invariant access function, rather than constant. (build_classic_dist_vector): Call above function. * tree-loop-distribution.c (pg_add_dependence_edges): Add comment. gcc/testsuite/ * gcc.dg/tree-ssa/pr94969.c: New test. --- gcc/tree-loop-distribution.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'gcc/tree-loop-distribution.c') diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index 4442321..b122c39 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -2080,7 +2080,8 @@ loop_distribution::pg_add_dependence_edges (struct graph *rdg, int dir, this_dir = -this_dir; /* Known dependences can still be unordered througout the - iteration space, see gcc.dg/tree-ssa/ldist-16.c. */ + iteration space, see gcc.dg/tree-ssa/ldist-16.c and + gcc.dg/tree-ssa/pr94969.c. */ if (DDR_NUM_DIST_VECTS (ddr) != 1) this_dir = 2; /* If the overlap is exact preserve stmt order. */ -- cgit v1.1 From 585072c75ce2fbfe632e955e8bfb2f526d018a65 Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Sat, 20 Jun 2020 15:42:12 +0800 Subject: Record and restore postorder information in breaking alias sccs. gcc/ PR tree-optimization/95638 * tree-loop-distribution.c (pg_edge_callback_data): New field. (loop_distribution::break_alias_scc_partitions): Record and restore postorder information. Fix memory leak. gcc/testsuite/ PR tree-optimization/95638 * g++.dg/tree-ssa/pr95638.C: New test. --- gcc/tree-loop-distribution.c | 23 +++++++++++++++++------ 1 file changed, 17 insertions(+), 6 deletions(-) (limited to 'gcc/tree-loop-distribution.c') diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index b122c39..9bc94e5 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -2145,6 +2145,8 @@ struct pg_edge_callback_data bitmap sccs_to_merge; /* Array constains component information for all vertices. */ int *vertices_component; + /* Array constains postorder information for all vertices. */ + int *vertices_post; /* Vector to record all data dependence relations which are needed to break strong connected components by runtime alias checks. */ vec *alias_ddrs; @@ -2401,7 +2403,7 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, vec *partitions, vec *alias_ddrs) { - int i, j, k, num_sccs, num_sccs_no_alias; + int i, j, k, num_sccs, num_sccs_no_alias = 0; /* Build partition dependence graph. */ graph *pg = build_partition_graph (rdg, partitions, false); @@ -2452,6 +2454,7 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, cbdata.sccs_to_merge = sccs_to_merge; cbdata.alias_ddrs = alias_ddrs; cbdata.vertices_component = XNEWVEC (int, pg->n_vertices); + cbdata.vertices_post = XNEWVEC (int, pg->n_vertices); /* Record the component information which will be corrupted by next graph scc finding call. */ for (i = 0; i < pg->n_vertices; ++i) @@ -2460,6 +2463,11 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, /* Collect data dependences for runtime alias checks to break SCCs. */ if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs) { + /* Record the postorder information which will be corrupted by next + graph SCC finding call. */ + for (i = 0; i < pg->n_vertices; ++i) + cbdata.vertices_post[i] = pg->vertices[i].post; + /* Run SCC finding algorithm again, with alias dependence edges skipped. This is to topologically sort partitions according to compilation time known dependence. Note the topological order @@ -2490,11 +2498,6 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, if (cbdata.vertices_component[k] != i) continue; - /* Update to the minimal postordeer number of vertices in scc so - that merged partition is sorted correctly against others. */ - if (pg->vertices[j].post > pg->vertices[k].post) - pg->vertices[j].post = pg->vertices[k].post; - partition_merge_into (NULL, first, partition, FUSE_SAME_SCC); (*partitions)[k] = NULL; partition_free (partition); @@ -2505,6 +2508,14 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, first->type = PTYPE_SEQUENTIAL; } } + /* Restore the postorder information if it's corrupted in finding SCC + with alias dependence edges skipped. */ + if (num_sccs_no_alias > 0) + for (i = 0; i < pg->n_vertices; ++i) + pg->vertices[i].post = cbdata.vertices_post[i]; + + free (cbdata.vertices_component); + free (cbdata.vertices_post); } sort_partitions_by_post_order (pg, partitions); -- cgit v1.1 From 92f4add097cc396f7224b39e9a7ff1363fa8711a Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Thu, 9 Jul 2020 18:10:03 +0800 Subject: Schedule reduction partition in the last. If reduction partition's SCC is broken by runtime alias checks, force a negative post order to it so that it will be scheduled in the last. 2020-07-09 Bin Cheng gcc/ PR tree-optimization/95804 * tree-loop-distribution.c (break_alias_scc_partitions): Force negative post order to reduction partition. gcc/testsuite/ PR tree-optimization/95804 * gcc.dg/tree-ssa/pr95804.c: New test. --- gcc/tree-loop-distribution.c | 21 ++++++++++++++++++--- 1 file changed, 18 insertions(+), 3 deletions(-) (limited to 'gcc/tree-loop-distribution.c') diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index 9bc94e5..888af48 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -2509,10 +2509,25 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, } } /* Restore the postorder information if it's corrupted in finding SCC - with alias dependence edges skipped. */ + with alias dependence edges skipped. If reduction partition's SCC is + broken by runtime alias checks, we force a negative post order to it + making sure it will be scheduled in the last. */ if (num_sccs_no_alias > 0) - for (i = 0; i < pg->n_vertices; ++i) - pg->vertices[i].post = cbdata.vertices_post[i]; + { + j = -1; + for (i = 0; i < pg->n_vertices; ++i) + { + pg->vertices[i].post = cbdata.vertices_post[i]; + struct pg_vdata *data = (struct pg_vdata *)pg->vertices[i].data; + if (data->partition && partition_reduction_p (data->partition)) + { + gcc_assert (j == -1); + j = i; + } + } + if (j >= 0) + pg->vertices[j].post = -1; + } free (cbdata.vertices_component); free (cbdata.vertices_post); -- cgit v1.1