From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id 986263858436; Tue, 24 Jan 2023 15:22:50 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 986263858436 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1674573770; bh=4bChWHmEKbBSpvy89/uz2IfhQnYIcVvtE6lcO5VLIZw=; h=From:To:Subject:Date:From; b=nayiUlGqquOqF8gmPZXQpLNu9NanaRUxxSwWs12JA0V06Yd0RdV2SsKEhZN/t7o3H 1gmvE/q3jBEoDox4pz8KyDKXqVwtSQ7kQlAJGgmLVR+SzyPLYCSOBO9t6Px4+BOCCL hd6wJzw9Rf6E3HVPP8H8wbkp+u+Sa2Ay+qH32EvM= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r11-10482] tree-optimization/107323 - loop distribution partition ordering issue X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/releases/gcc-11 X-Git-Oldrev: fb335c938bbd54e83af2d281f0ccf79df1c342b3 X-Git-Newrev: 28fe903730d2c6e424732184ab2d8b1e7d46db6c Message-Id: <20230124152250.986263858436@sourceware.org> Date: Tue, 24 Jan 2023 15:22:50 +0000 (GMT) List-Id: https://gcc.gnu.org/g:28fe903730d2c6e424732184ab2d8b1e7d46db6c commit r11-10482-g28fe903730d2c6e424732184ab2d8b1e7d46db6c Author: Richard Biener Date: Fri Oct 21 09:45:44 2022 +0200 tree-optimization/107323 - loop distribution partition ordering issue The following reverts part of the PR94125 fix which causes us to use a bogus partition ordering after applying versioning for alias to the testcase in PR107323. Instead PR94125 is fixed by appropriately considering to be merged SCCs when skipping edges we want to ignore because of the alias versioning. PR tree-optimization/107323 * tree-loop-distribution.c (pg_unmark_merged_alias_ddrs): New function. (loop_distribution::break_alias_scc_partitions): Revert postorder save/restore from the PR94125 fix. Instead make sure to not ignore edges from SCCs we are going to merge. * gcc.dg/tree-ssa/pr107323.c: New testcase. (cherry picked from commit 09f9814dc02c161ed78604c6df70b19b596f7524) Diff: --- gcc/testsuite/gcc.dg/tree-ssa/pr107323.c | 28 ++++++++++++++++++ gcc/tree-loop-distribution.c | 50 +++++++++++++++++++++++--------- 2 files changed, 64 insertions(+), 14 deletions(-) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr107323.c b/gcc/testsuite/gcc.dg/tree-ssa/pr107323.c new file mode 100644 index 00000000000..1204b6e36d5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr107323.c @@ -0,0 +1,28 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fno-tree-vectorize" } */ + +int A[4]; +int B[4]; + +static const char *__attribute__((noipa)) foo() +{ + return "1"; +} + +int main() +{ + const char *s = foo(); + + A[0] = 1000; + for(int i = 1; i < 4; ++i) { + B[i] = 0; + A[i] = 0; + if(s[0]) + B[i] = 1; + A[i] = A[i - 1]; + } + + if (A[3] != 1000) + __builtin_abort (); + return 0; +} diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index 7568384e286..947326ab1e7 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -2163,8 +2163,6 @@ 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; @@ -2414,6 +2412,33 @@ pg_collect_alias_ddrs (struct graph *g, struct graph_edge *e, void *data) cbdata->alias_ddrs->safe_splice (edata->alias_ddrs); } +/* Callback function for traversing edge E. DATA is private + callback data. */ + +static void +pg_unmark_merged_alias_ddrs (struct graph *, struct graph_edge *e, void *data) +{ + int i, j, component; + struct pg_edge_callback_data *cbdata; + struct pg_edata *edata = (struct pg_edata *) e->data; + + if (edata == NULL || edata->alias_ddrs.length () == 0) + return; + + cbdata = (struct pg_edge_callback_data *) data; + i = e->src; + j = e->dest; + component = cbdata->vertices_component[i]; + /* Make sure to not skip vertices inside SCCs we are going to merge. */ + if (component == cbdata->vertices_component[j] + && bitmap_bit_p (cbdata->sccs_to_merge, component)) + { + edata->alias_ddrs.release (); + delete edata; + e->data = NULL; + } +} + /* This is the main function breaking strong conected components in PARTITIONS giving reduced depdendence graph RDG. Store data dependence relations for runtime alias check in ALIAS_DDRS. */ @@ -2473,7 +2498,6 @@ 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) @@ -2482,17 +2506,18 @@ 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; + /* For SCCs we want to merge clear all alias_ddrs for edges + inside the component. */ + for_each_edge (pg, pg_unmark_merged_alias_ddrs, &cbdata); /* 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 is stored in the form of pg's post order number. */ num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge); - gcc_assert (partitions->length () == (unsigned) num_sccs_no_alias); + /* We cannot assert partitions->length () == num_sccs_no_alias + since we are not ignoring alias edges in cycles we are + going to merge. That's required to compute correct postorder. */ /* With topological order, we can construct two subgraphs L and R. L contains edge where x < y in terms of post order, while R contains edge where x > y. Edges for compilation time @@ -2527,16 +2552,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 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 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) { 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)) { @@ -2549,7 +2572,6 @@ loop_distribution::break_alias_scc_partitions (struct graph *rdg, } free (cbdata.vertices_component); - free (cbdata.vertices_post); } sort_partitions_by_post_order (pg, partitions);