From 84935c9822183ce403bb361c5f405711b9a808c6 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Wed, 15 Apr 2020 12:09:01 +0200 Subject: [PATCH] tree-optimization/33315 - common stores during sinking This implements commoning of stores to a common successor in a simple ad-hoc way. I've decided to put it into the code sinking pass since, well, it sinks stores. It's still separate since it does not really sink code into less executed places. It's ad-hoc since it does not perform any dataflow or alias analysis but simply only considers trailing stores in a block, iteratively though. If the stores are from different values a PHI node is inserted to merge them. gcc.dg/tree-ssa/split-path-7.c shows that path splitting will eventually undo this very transform, I've decided to not bother with it and simply disable sinking for the particular testcase. Doing this transform is good for code size when the stores are from constants, once we have to insert PHIs the situation becomes less clear but it's a transform we do elsewhere as well (cselim for one), and reversing the transform should be easy. 2020-05-15 Richard Biener PR tree-optimization/33315 * tree-ssa-sink.c: Include tree-eh.h. (sink_stats): Add commoned member. (sink_common_stores_to_bb): New function implementing store commoning by sinking to the successor. (sink_code_in_bb): Call it, pass down TODO_cleanup_cfg returned. (pass_sink_code::execute): Likewise. Record commoned stores in statistics. * gcc.dg/tree-ssa/ssa-sink-13.c: New testcase. * gcc.dg/tree-ssa/ssa-sink-14.c: Likewise. * gcc.dg/tree-ssa/split-path-7.c: Disable sinking. --- gcc/ChangeLog | 11 ++ gcc/testsuite/ChangeLog | 7 + gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c | 2 +- gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c | 25 +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-14.c | 17 ++ gcc/tree-ssa-sink.c | 185 ++++++++++++++++++- 6 files changed, 242 insertions(+), 5 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-14.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index c7b080f7c11..7daad3c214e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2020-05-15 Richard Biener + + PR tree-optimization/33315 + * tree-ssa-sink.c: Include tree-eh.h. + (sink_stats): Add commoned member. + (sink_common_stores_to_bb): New function implementing store + commoning by sinking to the successor. + (sink_code_in_bb): Call it, pass down TODO_cleanup_cfg returned. + (pass_sink_code::execute): Likewise. Record commoned stores + in statistics. + 2020-05-14 Xiong Hu Luo PR rtl-optimization/37451, part of PR target/61837 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index e2ee69f9b47..0bf5dcdbe06 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,10 @@ +2020-05-15 Richard Biener + + PR tree-optimization/33315 + * gcc.dg/tree-ssa/ssa-sink-13.c: New testcase. + * gcc.dg/tree-ssa/ssa-sink-14.c: Likewise. + * gcc.dg/tree-ssa/split-path-7.c: Disable sinking. + 2020-05-14 Xiong Hu Luo PR rtl-optimization/37451, part of PR target/61837 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c index 3d6186b34d9..a5df75c9b72 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-7.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim -fdump-tree-split-paths-details -w" } */ +/* { dg-options "-O2 -fsplit-paths -fno-tree-cselim -fno-tree-sink -fdump-tree-split-paths-details -w" } */ struct _reent diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c new file mode 100644 index 00000000000..a65ba35d4ba --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-13.c @@ -0,0 +1,25 @@ +/* PR33315 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-sink" } */ + +int num; +int a[20]; + +void test () +{ + int i; + int *ptr; + ptr = & a[0]; + i = num; + if ( i == 1) *(ptr+0) = 0; + if ( i != 1) *(ptr+0) = 0; + if ( i == 2) *(ptr+1) = 0; + if ( i != 2) *(ptr+1) = 0; + if ( i == 3) *(ptr+2) = 0; + if ( i != 3) *(ptr+2) = 0; +} + +/* We should sink/merge all stores and end up with a single BB. */ + +/* { dg-final { scan-tree-dump-times "MEM\[^\n\r\]* = 0;" 3 "sink" } } */ +/* { dg-final { scan-tree-dump-times "preds) > 1 + && (phi = get_virtual_phi (bb))) + { + /* Repeat until no more common stores are found. */ + while (1) + { + gimple *first_store = NULL; + auto_vec vdefs; + gimple_stmt_iterator gsi; + + /* Search for common stores defined by all virtual PHI args. + ??? Common stores not present in all predecessors could + be handled by inserting a forwarder to sink to. Generally + this involves deciding which stores to do this for if + multiple common stores are present for different sets of + predecessors. See PR11832 for an interesting case. */ + for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) + { + tree arg = gimple_phi_arg_def (phi, i); + gimple *def = SSA_NAME_DEF_STMT (arg); + if (! is_gimple_assign (def) + || stmt_can_throw_internal (cfun, def)) + { + /* ??? We could handle some cascading with the def being + another PHI. We'd have to insert multiple PHIs for + the rhs then though (if they are not all equal). */ + first_store = NULL; + break; + } + /* ??? Do not try to do anything fancy with aliasing, thus + do not sink across non-aliased loads (or even stores, + so different store order will make the sinking fail). */ + bool all_uses_on_phi = true; + imm_use_iterator iter; + use_operand_p use_p; + FOR_EACH_IMM_USE_FAST (use_p, iter, arg) + if (USE_STMT (use_p) != phi) + { + all_uses_on_phi = false; + break; + } + if (! all_uses_on_phi) + { + first_store = NULL; + break; + } + /* Check all stores are to the same LHS. */ + if (! first_store) + first_store = def; + /* ??? We could handle differing SSA uses in the LHS by inserting + PHIs for them. */ + else if (! operand_equal_p (gimple_assign_lhs (first_store), + gimple_assign_lhs (def), 0)) + { + first_store = NULL; + break; + } + vdefs.safe_push (arg); + } + if (! first_store) + break; + + /* Check if we need a PHI node to merge the stored values. */ + bool allsame = true; + for (unsigned i = 1; i < vdefs.length (); ++i) + { + gimple *def = SSA_NAME_DEF_STMT (vdefs[i]); + if (! operand_equal_p (gimple_assign_rhs1 (first_store), + gimple_assign_rhs1 (def), 0)) + { + allsame = false; + break; + } + } + + /* We cannot handle aggregate values if we need to merge them. */ + tree type = TREE_TYPE (gimple_assign_lhs (first_store)); + if (! allsame + && ! is_gimple_reg_type (type)) + break; + + if (dump_enabled_p ()) + { + dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, + first_store, + "sinking common stores %sto ", + allsame ? "with same value " : ""); + dump_generic_expr (MSG_OPTIMIZED_LOCATIONS, TDF_SLIM, + gimple_assign_lhs (first_store)); + dump_printf (MSG_OPTIMIZED_LOCATIONS, "\n"); + } + + /* Insert a PHI to merge differing stored values if necessary. + Note that in general inserting PHIs isn't a very good idea as + it makes the job of coalescing and register allocation harder. + Even common SSA uses on the rhs/lhs might extend their lifetime + across multiple edges by this code motion which makes + register allocation harder. */ + tree from; + if (! allsame) + { + from = make_ssa_name (type); + gphi *newphi = create_phi_node (from, bb); + for (unsigned i = 0; i < vdefs.length (); ++i) + { + gimple *def = SSA_NAME_DEF_STMT (vdefs[i]); + add_phi_arg (newphi, gimple_assign_rhs1 (def), + EDGE_PRED (bb, i), UNKNOWN_LOCATION); + } + } + else + from = gimple_assign_rhs1 (first_store); + + /* Remove all stores. */ + for (unsigned i = 0; i < vdefs.length (); ++i) + TREE_VISITED (vdefs[i]) = 1; + for (unsigned i = 0; i < vdefs.length (); ++i) + /* If we have more than one use of a VDEF on the PHI make sure + we remove the defining stmt only once. */ + if (TREE_VISITED (vdefs[i])) + { + TREE_VISITED (vdefs[i]) = 0; + gimple *def = SSA_NAME_DEF_STMT (vdefs[i]); + gsi = gsi_for_stmt (def); + unlink_stmt_vdef (def); + gsi_remove (&gsi, true); + release_defs (def); + } + + /* Insert the first store at the beginning of the merge BB. */ + gimple_set_vdef (first_store, gimple_phi_result (phi)); + SSA_NAME_DEF_STMT (gimple_vdef (first_store)) = first_store; + gimple_phi_set_result (phi, make_ssa_name (gimple_vop (cfun))); + gimple_set_vuse (first_store, gimple_phi_result (phi)); + gimple_assign_set_rhs1 (first_store, from); + /* ??? Should we reset first_stores location? */ + gsi = gsi_after_labels (bb); + gsi_insert_before (&gsi, first_store, GSI_SAME_STMT); + sink_stats.commoned++; + + todo |= TODO_cleanup_cfg; + } + + /* We could now have empty predecessors that we could remove, + forming a proper CFG for further sinking. Note that even + CFG cleanup doesn't do this fully at the moment and it + doesn't preserve post-dominators in the process either. + The mergephi pass might do it though. gcc.dg/tree-ssa/ssa-sink-13.c + shows this nicely if you disable tail merging or (same effect) + make the stored values unequal. */ + } + + return todo; +} + /* Perform code sinking on BB */ -static void +static unsigned sink_code_in_bb (basic_block bb) { basic_block son; @@ -477,6 +647,10 @@ sink_code_in_bb (basic_block bb) edge_iterator ei; edge e; bool last = true; + unsigned todo = 0; + + /* Sink common stores from the predecessor through our virtual PHI. */ + todo |= sink_common_stores_to_bb (bb); /* If this block doesn't dominate anything, there can't be any place to sink the statements to. */ @@ -563,8 +737,10 @@ sink_code_in_bb (basic_block bb) son; son = next_dom_son (CDI_POST_DOMINATORS, son)) { - sink_code_in_bb (son); + todo |= sink_code_in_bb (son); } + + return todo; } /* Perform code sinking. @@ -642,13 +818,14 @@ pass_sink_code::execute (function *fun) memset (&sink_stats, 0, sizeof (sink_stats)); calculate_dominance_info (CDI_DOMINATORS); calculate_dominance_info (CDI_POST_DOMINATORS); - sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun)); + unsigned todo = sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun)); statistics_counter_event (fun, "Sunk statements", sink_stats.sunk); + statistics_counter_event (fun, "Commoned stores", sink_stats.commoned); free_dominance_info (CDI_POST_DOMINATORS); remove_fake_exit_edges (); loop_optimizer_finalize (); - return 0; + return todo; } } // anon namespace -- 2.30.2