| Message ID | ZOdyHqxbRshejb4n@fkdesktop.suse.cz |
|---|---|
| State | New |
| Headers | show |
| Series | [RFC] gimple ssa: SCCP - A new PHI optimization pass | expand |
> Am 24.08.2023 um 17:07 schrieb Filip Kastl <fkastl@suse.cz>: > > Hi, > > As a part of my bachelor thesis under the supervision of Honza (Jan Hubicka), I > implemented a new PHI elimination algorithm into GCC. The algorithm is > described in the following article: > > Braun, M., Buchwald, S., Hack, S., Leißa, R., Mallon, C., Zwinkau, A. > (2013). Simple and Efficient Construction of Static Single Assignment > Form. In: Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC > 2013. Lecture Notes in Computer Science, vol 7791. Springer, Berlin, > Heidelberg. https://doi.org/10.1007/978-3-642-37051-9_6 > > In the article the PHI elimination algorithm is only considered a part of > another algorithm. However, with Honza we tried running the algorithm as a > standalone pass and found that there is a surprisingly big number of PHI > functions it is able to remove -- sometimes even ~13% of PHI functions or more. > This email contains a patch with the pass and with the placement in passes.def > we used to measure this. > > Do you think that the pass is worthy of inclusion into upstream GCC? What are > some things that I should change? Should I try to put the pass in different > places in passes.def? The most obvious places would be right after SSA construction and before RTL expansion. Can you provide measurements for those positions? Can the pass somehow be used as part of propagations like during value numbering? Richard > Things I already know I'd like to change: > - Split the patch into two (one for sccp, one for the utility functions) > - Change the name SCCP to something else since there already is a pass with > that name (any suggestions?) > - Add a comment into sccp.cc explaining the algorithm > > I successfully bootstrapped and tested GCC with the patch applied (with the > commit 3b691e0190c6e7291f8a52e1e14d8293a28ff4ce checked out). > > Here are my measurements. I measured the number of PHIs before the PHI > elimination algorithm was run and after it was run. I measured on the standard > 2017 benchmarks with -O3. Since the pass is present in passes.def twice, > results of the first run are marked (1) and results of the second are marked > (2). Honza also did measurements with profile feedback and got even bigger > percentages. > > 500.perlbench_r > Started with (1) 30287 > Ended with (1) 26188 > Removed PHI % (1) 13.53385941162875161000 > Started with (2) 38005 > Ended with (2) 37897 > Removed PHI % (2) .28417313511380081600 > > 502.gcc_r > Started with (1) 148187 > Ended with (1) 140292 > Removed PHI % (1) 5.32772780338356266100 > Started with (2) 211479 > Ended with (2) 210635 > Removed PHI % (2) .39909399987705635100 > > 505.mcf_r > Started with (1) 341 > Ended with (1) 303 > Removed PHI % (1) 11.14369501466275659900 > Started with (2) 430 > Ended with (2) 426 > Removed PHI % (2) .93023255813953488400 > > 523.xalancbmk_r > Started with (1) 62514 > Ended with (1) 57785 > Removed PHI % (1) 7.56470550596666346800 > Started with (2) 132561 > Ended with (2) 131726 > Removed PHI % (2) .62989868815111533600 > > 531.deepsjeng_r > Started with (1) 1388 > Ended with (1) 1250 > Removed PHI % (1) 9.94236311239193083600 > Started with (2) 1887 > Ended with (2) 1879 > Removed PHI % (2) .42395336512983571900 > > 541.leela_r > Started with (1) 3332 > Ended with (1) 2994 > Removed PHI % (1) 10.14405762304921968800 > Started with (2) 4372 > Ended with (2) 4352 > Removed PHI % (2) .45745654162854528900 > > Here is the patch: > > -- >8 -- > > This patch introduces two things: > - A new PHI elimination pass (major) > - New utility functions for passes that replace one ssa name with a > different one (minor) > > Strongly-connected copy propagation (SCCP) pass > > The PHI elimination pass is a lightweight optimization pass based on > strongly-connected components. Some set of PHIs may be redundant because > the PHIs only refer to each other or to a single value from outside the > set. This pass finds and eliminates these sets. As a bonus the pass also > does some basic copy propagation because it considers a copy statement > to be a PHI with a single argument. > > SCCP uses an algorithm from this article: > Braun, M., Buchwald, S., Hack, S., Leißa, R., Mallon, C., Zwinkau, A. > (2013). Simple and Efficient Construction of Static Single Assignment > Form. In: Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC > 2013. Lecture Notes in Computer Science, vol 7791. Springer, Berlin, > Heidelberg. https://doi.org/10.1007/978-3-642-37051-9_6 > > cleanup_after_replace and cleanup_after_all_replaces_done > > Whenever you replace all uses of an ssa name by a different ssa name, > some GCC internal structures have to be updated. To streamline this > process, the patch adds the cleanup_after_replace function that should > be called after an ssa name is replaced by a different one and the > cleanup_after_all_replaces_done that should be called before a pass that > replaced one or more ssa names exits. The SCCP pass uses these > functions. > > Signed-off-by: Filip Kastl <fkastl@suse.cz> > > gcc/ChangeLog: > > * Makefile.in: Added sccp pass. > * passes.def: Added sccp pass to early and late optimizations. > * tree-pass.h (make_pass_sccp): Added sccp pass. > * tree-ssa-propagate.cc (cleanup_after_replace): New function. > (cleanup_after_all_replaces_done): New function. > * tree-ssa-propagate.h (cleanup_after_replace): New function. > (cleanup_after_all_replaces_done): New function. > * sccp.cc: New file. > --- > gcc/Makefile.in | 1 + > gcc/passes.def | 2 + > gcc/sccp.cc | 722 ++++++++++++++++++++++++++++++++++++++ > gcc/tree-pass.h | 1 + > gcc/tree-ssa-propagate.cc | 62 ++++ > gcc/tree-ssa-propagate.h | 7 + > 6 files changed, 795 insertions(+) > create mode 100644 gcc/sccp.cc > > diff --git a/gcc/Makefile.in b/gcc/Makefile.in > index 78779546459..7c34eb6ceda 100644 > --- a/gcc/Makefile.in > +++ b/gcc/Makefile.in > @@ -1706,6 +1706,7 @@ OBJS = \ > tree-ssa-forwprop.o \ > tree-ssa-ifcombine.o \ > tree-ssa-live.o \ > + sccp.o \ > tree-ssa-loop-ch.o \ > tree-ssa-loop-im.o \ > tree-ssa-loop-ivcanon.o \ > diff --git a/gcc/passes.def b/gcc/passes.def > index ef5a21afe49..4c94f9cec8b 100644 > --- a/gcc/passes.def > +++ b/gcc/passes.def > @@ -96,6 +96,7 @@ along with GCC; see the file COPYING3. If not see > NEXT_PASS (pass_dse); > NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); > NEXT_PASS (pass_phiopt, true /* early_p */); > + NEXT_PASS (pass_sccp); > NEXT_PASS (pass_tail_recursion); > NEXT_PASS (pass_if_to_switch); > NEXT_PASS (pass_convert_switch); > @@ -271,6 +272,7 @@ along with GCC; see the file COPYING3. If not see > NEXT_PASS (pass_tsan); > NEXT_PASS (pass_dse, true /* use DR analysis */); > NEXT_PASS (pass_dce); > + NEXT_PASS (pass_sccp); > /* Pass group that runs when 1) enabled, 2) there are loops > in the function. Make sure to run pass_fix_loops before > to discover/remove loops before running the gate function > diff --git a/gcc/sccp.cc b/gcc/sccp.cc > new file mode 100644 > index 00000000000..86a79303902 > --- /dev/null > +++ b/gcc/sccp.cc > @@ -0,0 +1,722 @@ > +/* Strongly connected copy propagation pass for the GNU compiler. > + Copyright (C) 2022 Free Software Foundation, Inc. > + Contributed by Filip Kastl <filip.kastl@gmail.com> > + > +This file is part of GCC. > + > +GCC is free software; you can redistribute it and/or modify it under > +the terms of the GNU General Public License as published by the Free > +Software Foundation; either version 3, or (at your option) any later > +version. > + > +GCC is distributed in the hope that it will be useful, but WITHOUT ANY > +WARRANTY; without even the implied warranty of MERCHANTABILITY or > +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License > +for more details. > + > +along with GCC; see the file COPYING3. If not see > +<http://www.gnu.org/licenses/>. */ > + > +#include "config.h" > +#include "system.h" > +#include "coretypes.h" > +#include "backend.h" > +#include "tree.h" > +#include "gimple.h" > +#include "tree-pass.h" > +#include "ssa.h" > +#include "gimple-iterator.h" > +#include "vec.h" > +#include "hash-set.h" > +#include <algorithm> > +#include "ssa-iterators.h" > +#include "gimple-fold.h" > +#include "gimplify.h" > +#include "tree-cfg.h" > +#include "tree-ssa-propagate.h" > + > +/* State of vertex during tarjan computation. > + > + unvisited Vertex hasn't yet been popped from worklist. > + vopen DFS has visited vertex for the first time. Vertex has been put on > + Tarjan stack. > + closed DFS has backtracked through vertex. At this point, vertex doesn't > + have any unvisited neighbors. > + in_scc Vertex has been popped from tarjan stack. */ > + > +enum vstate > +{ > + unvisited, > + vopen, > + closed, > + in_scc > +}; > + > +/* Information about a vertex used by tarjan. */ > + > +struct vertex > +{ > + vstate state; > + unsigned index; > + unsigned lowlink; > + gimple* stmt; > +}; > + > +static bool > +stmt_may_generate_copy (gimple *stmt) > +{ > + if (gimple_code (stmt) == GIMPLE_PHI) > + { > + gphi *phi = as_a <gphi *> (stmt); > + > + /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs. */ > + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi))) > + { > + return false; > + } > + > + unsigned i; > + for (i = 0; i < gimple_phi_num_args (phi); i++) > + { > + tree op = gimple_phi_arg_def (phi, i); > + if (TREE_CODE (op) == SSA_NAME && > + SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) > + { > + return false; > + } > + } > + > + return true; > + } > + > + if (gimple_code (stmt) != GIMPLE_ASSIGN) > + { > + return false; > + } > + > + /* If the statement has volatile operands, it won't generate a > + useful copy. */ > + if (gimple_has_volatile_ops (stmt)) > + { > + return false; > + } > + > + /* Statements with loads and/or stores will never generate a useful copy. */ > + if (gimple_store_p (stmt) || gimple_assign_load_p (stmt)) > + { > + return false; > + } > + > + if (!gimple_assign_single_p (stmt)) > + { > + return false; > + } > + > + tree lhs = gimple_assign_lhs (stmt); > + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) > + { > + return false; > + } > + > + /* If the assignment is from a constant it generates a useful copy. */ > + if (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) > + { > + return true; > + } > + > + /* Otherwise, the only statements that generate useful copies are > + assignments whose single SSA use doesn't flow through abnormal > + edges. */ > + tree rhs = single_ssa_tree_operand (stmt, SSA_OP_USE); > + > + if (!is_gimple_val (gimple_assign_rhs1 (stmt))) > + { > + return false; > + } > + > + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) > + { > + return false; > + } > + > + if (!rhs) > + { > + return false; > + } > + > + return true; > +} > + > +/* Set 'using' flag of gimple statement to true. > + If the flag isn't set, tarjan will ignore the statement. */ > + > +static void > +tarjan_set_using (gimple* stmt) > +{ > + gimple_set_plf (stmt, GF_PLF_1, true); > +} > + > +/* Clear 'using' flag of gimple statement to false. */ > + > +static void > +tarjan_clear_using (gimple* stmt) > +{ > + gimple_set_plf (stmt, GF_PLF_1, false); > +} > + > +/* Return value of 'using' flag of gimple statement. */ > + > +static bool > +tarjan_is_using (gimple* stmt) > +{ > + return gimple_plf (stmt, GF_PLF_1); > +} > + > +/* Set 'vxnum' (vertex number) of statement. Before computing SCCs, tarjan > + assigns unique vxnums to statements that it will use. */ > + > +static void > +tarjan_set_vxnum (gimple* stmt, unsigned num) > +{ > + gimple_set_uid (stmt, num); > +} > + > +/* Return 'vxnum' (vertex number) of statement. */ > + > +static unsigned > +tarjan_vxnum (gimple* stmt) > +{ > + return gimple_uid (stmt); > +} > + > +/* Create and initialize vertex struct for each given statement. */ > + > +static auto_vec<vertex> > +tarjan_stmts_to_vertices (auto_vec<gimple *> &stmts) > +{ > + auto_vec<vertex> result; > + for (gimple *stmt : stmts) > + { > + vertex v; > + v.state = unvisited; > + v.index = 0; > + v.lowlink = 0; > + v.stmt = stmt; > + > + result.safe_push (v); > + } > + return result; > +} > + > +static void > +tarjan_visit_neighbor (tree neigh_tree, unsigned parent_vxnum, > + auto_vec<vertex> &vs, auto_vec<unsigned> &worklist) > +{ > + if (TREE_CODE (neigh_tree) != SSA_NAME) > + return; /* Skip any neighbor that isn't an SSA name. */ > + > + gimple *neigh_stmt = SSA_NAME_DEF_STMT (neigh_tree); > + > + /* Skip neighbors outside the induced subgraph that Tarjan currently works > + with. */ > + if (!tarjan_is_using (neigh_stmt)) > + return; > + unsigned neigh_vxnum = tarjan_vxnum (neigh_stmt); > + > + gcc_checking_assert (stmt_may_generate_copy (neigh_stmt)); > + > + vstate neigh_state = vs[neigh_vxnum].state; > + vstate parent_state = vs[parent_vxnum].state; > + if (parent_state == vopen) /* We're currently opening parent. */ > + { > + /* Put unvisited neighbors on worklist. Update lowlink of parent > + vertex according to indices of neighbors present on stack. */ > + switch (neigh_state) > + { > + case unvisited: > + worklist.safe_push (neigh_vxnum); > + break; > + case vopen: > + case closed: > + vs[parent_vxnum].lowlink = std::min (vs[parent_vxnum].lowlink, > + vs[neigh_vxnum].index); > + break; > + case in_scc: > + /* Ignore these edges. */ > + break; > + } > + } > + else if (parent_state == closed) /* We're currently closing parent. */ > + { > + /* Update lowlink of parent vertex according to lowlinks of > + children of parent (in terms of DFS tree). */ > + if (neigh_state == closed) > + { > + vs[parent_vxnum].lowlink = std::min (vs[parent_vxnum].lowlink, > + vs[neigh_vxnum].lowlink); > + } > + } > +} > + > +/* Nonrecursive implementation of Tarjan's algorithm for computing strongly > + connected components in a graph. Statements are vertices. Edges lead from a > + copy stmt p using another copy stmt q to the stmt being used (p -> q when q > + is operand of p). > + > + Considers only the subgraph induced by given statements. */ > + > +static auto_vec<vec<gimple *>> > +tarjan_compute_sccs (auto_vec<gimple *> ©_stmts) > +{ > + auto_vec<vec<gimple *>> sccs; > + auto_vec<unsigned> worklist; /* DFS stack. */ > + auto_vec<unsigned> stack; /* Tarjan stack. */ > + unsigned curr_index = 0; > + > + auto_vec<vertex> vs = tarjan_stmts_to_vertices (copy_stmts); > + > + /* Mark the subgraph induced by 'copy_stmts' and index it by vxnums. */ > + unsigned i; > + for (i = 0; i < vs.length (); i++) > + { > + gimple *stmt = vs[i].stmt; > + tarjan_set_using (stmt); > + tarjan_set_vxnum (stmt, i); > + } > + > + /* Put all vertices on worklist. */ > + for (i = 0; i < vs.length (); i++) > + { > + worklist.safe_push (i); > + } > + > + /* Worklist loop. */ > + while (!worklist.is_empty ()) > + { > + unsigned i = worklist.pop(); > + gimple *stmt = vs[i].stmt; > + vstate state = vs[i].state; > + > + if (state == unvisited) > + { > + vs[i].state = vopen; > + > + /* Assign index to this vertex. */ > + vs[i].index = curr_index; > + vs[i].lowlink = curr_index; > + curr_index++; > + > + /* Put vertex on stack and also on worklist to be closed later. */ > + stack.safe_push (i); > + worklist.safe_push (i); > + } > + else if (state == vopen) > + { > + vs[i].state = closed; > + } > + > + /* Visit neighbors of this vertex. */ > + tree op; > + gphi *phi; > + switch (gimple_code (stmt)) > + { > + case GIMPLE_PHI: > + phi = as_a <gphi *> (stmt); > + unsigned j; > + for (j = 0; j < gimple_phi_num_args (phi); j++) > + { > + op = gimple_phi_arg_def (phi, j); > + tarjan_visit_neighbor (op, i, vs, worklist); > + } > + break; > + case GIMPLE_ASSIGN: > + op = gimple_assign_rhs1 (stmt); > + tarjan_visit_neighbor (op, i, vs, worklist); > + break; > + default: > + gcc_unreachable (); > + } > + > + /* If we've just closed a root vertex of an scc, pop scc from stack. */ > + if (state == vopen && vs[i].lowlink == vs[i].index) > + { > + vec<gimple *> scc = vNULL; > + > + unsigned j; > + do > + { > + j = stack.pop(); > + scc.safe_push (vs[j].stmt); > + vs[j].state = in_scc; > + } > + while (j != i); > + > + sccs.safe_push (scc); > + } > + } > + > + if (!stack.is_empty ()) > + { > + gcc_unreachable(); > + } > + > + /* Clear copy stmts' 'using' flags. */ > + for (vertex v : vs) > + { > + gimple *s = v.stmt; > + tarjan_clear_using (s); > + } > + > + return sccs; > +} > + > +static void > +replace_use_by (tree get_replaced, tree replace_by, bitmap need_eh_cleanup, > + bitmap need_ab_cleanup, vec<gimple *> stmts_to_fixup) > +{ > + /* Replace each occurence of 'get_replaced' by 'replace_by'. */ > + use_operand_p use_p; > + imm_use_iterator iter; > + gimple *use_stmt; > + FOR_EACH_IMM_USE_STMT (use_stmt, iter, get_replaced) > + { > + bool was_noreturn = false; > + bool can_make_abnormal_goto = false; > + if (is_gimple_call (use_stmt)) > + { > + was_noreturn = gimple_call_noreturn_p (use_stmt); > + can_make_abnormal_goto = stmt_can_make_abnormal_goto (use_stmt); > + } > + > + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) > + SET_USE (use_p, unshare_expr (replace_by)); > + > + /* Recompute tree invariant. */ > + if (gimple_assign_single_p (use_stmt)) > + { > + tree rhs = gimple_assign_rhs1 (use_stmt); > + > + if (TREE_CODE (rhs) == ADDR_EXPR) > + recompute_tree_invariant_for_addr_expr (rhs); > + } > + > + /* Cleanup. */ > + gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); > + fold_stmt (&gsi); > + gimple_set_modified (gsi_stmt (gsi), true); > + cleanup_after_replace (use_stmt, gsi_stmt (gsi), need_eh_cleanup, > + need_ab_cleanup, stmts_to_fixup, > + can_make_abnormal_goto, was_noreturn); > + } > +} > + > +/* Modify all usages of PHIs in a given SCC to instead reference a given > + variable. */ > + > +static void > +replace_scc_by_value (vec<gimple *> scc, tree replace_by, bitmap > + need_eh_cleanup, bitmap need_ab_cleanup, vec<gimple *> > + stmts_to_fixup) > +{ > + // DEBUG > + if (dump_file) > + { > + fprintf (dump_file, "Replacing SCC of length %d\n", scc.length ()); > + } > + > + for (gimple *stmt : scc) > + { > + tree get_replaced = gimple_get_lhs (stmt); > + replace_use_by (get_replaced, replace_by, need_eh_cleanup, > + need_ab_cleanup, stmts_to_fixup); > + } > +} > + > +/* Remove all PHIs with zero uses. */ > + > +static void > +remove_zero_uses_phis () > +{ > + basic_block bb; > + FOR_EACH_BB_FN (bb, cfun) > + { > + gphi_iterator pi; > + for (pi = gsi_start_phis (bb); !gsi_end_p (pi);) > + { > + gphi *phi = pi.phi (); > + tree ssa_name = gimple_phi_result (phi); > + if (has_zero_uses (ssa_name)) > + { > + /* Note that remove_phi_node() also frees SSA name. */ > + remove_phi_node (&pi, true); > + } > + else > + gsi_next (&pi); > + } > + } > +} > + > +static void > +sccp_visit_op (tree op, hash_set<tree> &outer_ops, hash_set<gimple *> &scc_set, > + bool &is_inner, tree &last_outer_op) > +{ > + bool op_in_scc = false; > + > + if (TREE_CODE (op) == SSA_NAME) > + { > + gimple *op_stmt = SSA_NAME_DEF_STMT (op); > + if (scc_set.contains (op_stmt)) > + op_in_scc = true; > + } > + > + if (!op_in_scc) > + { > + outer_ops.add (op); > + last_outer_op = op; > + is_inner = false; > + } > +} > + > +/* Apply Braun et al.'s algorithm on a given set of statements. Treat copy > + statements as PHI functions with a single argument. > + Main function of this pass. */ > + > +static void > +sccp_propagate (auto_vec<gimple *> ©_stmts) > +{ > + auto_vec<vec<gimple *>> worklist; > + worklist = tarjan_compute_sccs (copy_stmts); > + > + /* Prepare data structs for cleanup after stmt modification. */ > + bitmap need_eh_cleanup = BITMAP_ALLOC (NULL); > + bitmap need_ab_cleanup = BITMAP_ALLOC (NULL); > + vec<gimple *> stmts_to_fixup = vNULL; > + > + while (!worklist.is_empty ()) > + { > + vec<gimple *> scc = worklist.pop (); > + > + auto_vec<gimple *> inner; > + hash_set<tree> outer_ops; > + tree last_outer_op = NULL_TREE; > + > + /* Prepare hash set of PHIs in scc to query later. */ > + hash_set<gimple *> scc_set; > + for (gimple *stmt : scc) > + { > + scc_set.add (stmt); > + } > + > + for (gimple *stmt : scc) > + { > + bool is_inner = true; > + > + gphi *phi; > + tree op; > + switch (gimple_code (stmt)) > + { > + case GIMPLE_PHI: > + phi = as_a <gphi *> (stmt); > + unsigned j; > + for (j = 0; j < gimple_phi_num_args (phi); j++) > + { > + op = gimple_phi_arg_def (phi, j); > + sccp_visit_op (op, outer_ops, scc_set, is_inner, > + last_outer_op); > + } > + break; > + case GIMPLE_ASSIGN: > + op = gimple_assign_rhs1 (stmt); > + sccp_visit_op (op, outer_ops, scc_set, is_inner, > + last_outer_op); > + break; > + default: > + gcc_unreachable (); > + } > + > + if (is_inner) > + { > + inner.safe_push (stmt); > + } > + } > + > + if (outer_ops.elements () == 1) > + { > + /* The only operand in outer_ops. */ > + tree outer_op = last_outer_op; > + > + replace_scc_by_value (scc, outer_op, need_eh_cleanup, > + need_ab_cleanup, stmts_to_fixup); > + } > + else if (outer_ops.elements () > 1) > + { > + /* Add inner sccs to worklist. */ > + auto_vec<vec<gimple *>> inner_sccs = tarjan_compute_sccs (inner); > + for (vec<gimple *> inner_scc : inner_sccs) > + { > + worklist.safe_push (inner_scc); > + } > + } > + else > + { > + gcc_unreachable (); > + } > + > + scc.release (); > + } > + > + cleanup_after_all_replaces_done (need_eh_cleanup, need_ab_cleanup, > + stmts_to_fixup); > + > + /* Remove data structs for cleanup after stmt modification. */ > + BITMAP_FREE (need_eh_cleanup); > + BITMAP_FREE (need_ab_cleanup); > + stmts_to_fixup.release (); > + > + /* We want to remove dead MEM PHIs because memory is in FUD SSA and the dead > + PHIs would break the FUD property. */ > + remove_zero_uses_phis (); > +} > + > +/* Return all statements in cfun that may be useful. */ > + > +static auto_vec<gimple *> > +get_all_stmt_may_generate_copy (void) > +{ > + auto_vec<gimple *> result; > + > + basic_block bb; > + FOR_EACH_BB_FN (bb, cfun) > + { > + gimple_stmt_iterator gsi; > + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gimple *s = gsi_stmt (gsi); > + if (stmt_may_generate_copy (s)) > + result.safe_push (s); > + } > + > + gphi_iterator pi; > + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) > + { > + gimple *s = pi.phi (); > + if (stmt_may_generate_copy (s)) > + result.safe_push (s); > + } > + } > + > + return result; > +} > + > +/* Called when pass execution starts. */ > + > +static void > +init_sccp (void) > +{ > + // Clear 'tarjan using' flag on all statements > + basic_block bb; > + FOR_EACH_BB_FN (bb, cfun) > + { > + gimple_stmt_iterator gsi; > + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gimple* stmt = gsi_stmt (gsi); > + tarjan_clear_using (stmt); > + } > + > + gphi_iterator pi; > + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) > + { > + gimple *stmt = pi.phi (); > + tarjan_clear_using (stmt); > + } > + } > +} > + > +/* Called before pass execution ends. */ > + > +static void > +finalize_sccp (void) > +{ > + basic_block bb; > + FOR_EACH_BB_FN (bb, cfun) > + { > + gimple_purge_dead_eh_edges (bb); > + } > +} > + > +namespace { > + > +const pass_data pass_data_sccp = > +{ > + GIMPLE_PASS, /* type */ > + "sccp", /* name */ > + OPTGROUP_NONE, /* optinfo_flags */ > + TV_NONE, /* tv_id */ > + ( PROP_cfg | PROP_ssa ), /* properties_required */ > + 0, /* properties_provided */ > + 0, /* properties_destroyed */ > + 0, /* todo_flags_start */ > + TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */ > +}; > + > +class pass_sccp : public gimple_opt_pass > +{ > +public: > + pass_sccp (gcc::context *ctxt) > + : gimple_opt_pass (pass_data_sccp, ctxt) > + {} > + > + /* opt_pass methods: */ > + virtual bool gate (function *) { return true; } > + virtual unsigned int execute (function *); > + opt_pass * clone () final override { return new pass_sccp (m_ctxt); } > +}; // class pass_sccp > + > +unsigned > +pass_sccp::execute (function *) > +{ > + // DEBUG > + if (dump_file) > + { > + int phis = 0; > + basic_block bb; > + FOR_EACH_BB_FN (bb, cfun) > + { > + gphi_iterator pi; > + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) > + phis++; > + } > + fprintf (dump_file, "Started with %d PHIs\n", phis); > + } > + > + init_sccp (); > + auto_vec<gimple *> stmts = get_all_stmt_may_generate_copy (); > + sccp_propagate (stmts); > + finalize_sccp (); > + > + // DEBUG > + if (dump_file) > + { > + int phis = 0; > + basic_block bb; > + FOR_EACH_BB_FN (bb, cfun) > + { > + gphi_iterator pi; > + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) > + phis++; > + } > + fprintf (dump_file, "Ended with %d PHIs\n", phis); > + } > + > + return 0; > +} > + > +} // anon namespace > + > +gimple_opt_pass * > +make_pass_sccp (gcc::context *ctxt) > +{ > + return new pass_sccp (ctxt); > +} > diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h > index 57865cdfc42..ac1d8848c25 100644 > --- a/gcc/tree-pass.h > +++ b/gcc/tree-pass.h > @@ -398,6 +398,7 @@ extern gimple_opt_pass *make_pass_iv_optimize (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_tree_loop_done (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_ch (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_ch_vect (gcc::context *ctxt); > +extern gimple_opt_pass *make_pass_sccp (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_ccp (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_split_paths (gcc::context *ctxt); > extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctxt); > diff --git a/gcc/tree-ssa-propagate.cc b/gcc/tree-ssa-propagate.cc > index cb68b419b8c..f70240dcd2f 100644 > --- a/gcc/tree-ssa-propagate.cc > +++ b/gcc/tree-ssa-propagate.cc > @@ -1297,3 +1297,65 @@ clean_up_loop_closed_phi (function *fun) > > return 0; > } > + > +void > +cleanup_after_replace (gimple *old_stmt, gimple *stmt, bitmap need_eh_cleanup, > + bitmap need_ab_cleanup, vec<gimple *> stmts_to_fixup, > + bool can_make_abnormal_goto, bool was_noreturn) > +{ > + basic_block bb = stmt->bb; > + > + /* If we cleaned up EH information from the statement, > + remove EH edges. */ > + if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) > + bitmap_set_bit (need_eh_cleanup, bb->index); > + > + /* If we turned a call with possible abnormal control transfer > + into one that doesn't, remove abnormal edges. */ > + if (can_make_abnormal_goto > + && !stmt_can_make_abnormal_goto (stmt)) > + bitmap_set_bit (need_ab_cleanup, bb->index); > + > + /* If we turned a not noreturn call into a noreturn one > + schedule it for fixup. */ > + if (!was_noreturn > + && is_gimple_call (stmt) > + && gimple_call_noreturn_p (stmt)) > + stmts_to_fixup.safe_push (stmt); > + > + if (gimple_assign_single_p (stmt)) > + { > + tree rhs = gimple_assign_rhs1 (stmt); > + > + if (TREE_CODE (rhs) == ADDR_EXPR) > + recompute_tree_invariant_for_addr_expr (rhs); > + } > + > + update_stmt_if_modified (stmt); > +} > + > +void > +cleanup_after_all_replaces_done (bitmap need_eh_cleanup, bitmap > + need_ab_cleanup, vec<gimple *> stmts_to_fixup) > +{ > + if (!bitmap_empty_p (need_eh_cleanup)) > + gimple_purge_all_dead_eh_edges (need_eh_cleanup); > + if (!bitmap_empty_p (need_ab_cleanup)) > + gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup); > + > + /* Fixup stmts that became noreturn calls. This may require splitting > + blocks and thus isn't possible during the dominator walk. Do this > + in reverse order so we don't inadvertedly remove a stmt we want to > + fixup by visiting a dominating now noreturn call first. */ > + while (!stmts_to_fixup.is_empty ()) > + { > + gimple *stmt = stmts_to_fixup.pop (); > + if (dump_file && dump_flags & TDF_DETAILS) > + { > + fprintf (dump_file, "Fixing up noreturn call "); > + print_gimple_stmt (dump_file, stmt, 0); > + fprintf (dump_file, "\n"); > + } > + fixup_noreturn_call (stmt); > + } > +} > diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h > index 29bde37add9..a645baeacf4 100644 > --- a/gcc/tree-ssa-propagate.h > +++ b/gcc/tree-ssa-propagate.h > @@ -72,6 +72,13 @@ extern void propagate_value (use_operand_p, tree); > extern void replace_exp (use_operand_p, tree); > extern void propagate_tree_value (tree *, tree); > extern void propagate_tree_value_into_stmt (gimple_stmt_iterator *, tree); > +extern void cleanup_after_replace (gimple *old_stmt, gimple *stmt, bitmap > + need_eh_cleanup, bitmap need_ab_cleanup, > + vec<gimple *> stmts_to_fixup, bool > + can_make_abnormal_goto, bool was_noreturn); > +extern void cleanup_after_all_replaces_done (bitmap need_eh_cleanup, bitmap > + need_ab_cleanup, vec<gimple *> > + stms_to_fixup); > > /* Public interface into the SSA propagation engine. Clients should inherit > from this class and provide their own visitors. */ > -- > 2.41.0 >
On Thu, Aug 24, 2023 at 05:47:09PM +0200, Richard Biener via Gcc-patches wrote: > > Do you think that the pass is worthy of inclusion into upstream GCC? What are > > some things that I should change? Should I try to put the pass in different > > places in passes.def? > > The most obvious places would be right after SSA construction and before RTL expansion. > Can you provide measurements for those positions? > Can the pass somehow be used as part of propagations like during value numbering? Could the new file be called gimple-ssa-sccp.cc or something similar? Removing some PHIs is nice, but it would be also interesting to know what are the effects on generated code size and/or performance. And also if it has any effects on debug information coverage. Jakub
> The most obvious places would be right after SSA construction and before RTL expansion. > Can you provide measurements for those positions? The algorithm should only remove PHIs that break SSA form minimality. Since GCC's SSA construction already produces minimal SSA form, the algorithm isn't expected to remove any PHIs if run right after the construction. I even measured it and indeed -- no PHIs got removed (except for 502.gcc_r, where the algorithm managed to remove exactly 1 PHI, which is weird). I tried putting the pass before pass_expand. There isn't a lot of PHIs to remove at that point, but there still are some. 500.perlbench_r Started with 43111 Ended with 42942 Removed PHI % .39201131961680313700 502.gcc_r Started with 141392 Ended with 140455 Removed PHI % .66269661649881181400 505.mcf_r Started with 482 Ended with 478 Removed PHI % .82987551867219917100 523.xalancbmk_r Started with 136040 Ended with 135629 Removed PHI % .30211702440458688700 531.deepsjeng_r Started with 2150 Ended with 2148 Removed PHI % .09302325581395348900 541.leela_r Started with 4664 Ended with 4650 Removed PHI % .30017152658662092700 557.xz_r Started with 43 Ended with 43 Removed PHI % 0 > Can the pass somehow be used as part of propagations like during value numbering? I don't think that the pass could be used as a part of different optimizations since it works on the whole CFG (except for copy propagation as I noted in the RFC). I'm adding Honza into Cc. He'll have more insight into this. > Could the new file be called gimple-ssa-sccp.cc or something similar? Certainly. Though I'm not sure, but wouldn't tree-ssa-sccp.cc be more appropriate? I'm thinking about naming the pass 'scc-copy' and the file 'tree-ssa-scc-copy.cc'. > Removing some PHIs is nice, but it would be also interesting to know what > are the effects on generated code size and/or performance. > And also if it has any effects on debug information coverage. Regarding performance: I ran some benchmarks on a Zen3 machine with -O3 with and without the new pass. *I got ~2% speedup for 505.mcf_r and 541.leela_r. Here are the full results. What do you think? Should I run more benchmarks? Or benchmark multiple times? Or run the benchmarks on different machines?* 500.perlbench_r Without SCCP: 244.151807s With SCCP: 242.448438s -0.7025695913124297% 502.gcc_r Without SCCP: 211.029606s With SCCP: 211.614523s +0.27640683243653763% 505.mcf_r Without SCCP: 298.782621s With SCCP: 291.671468s -2.438069465197046% 523.xalancbmk_r Without SCCP: 189.940639s With SCCP: 189.876261s -0.03390523894928332% 531.deepsjeng_r Without SCCP: 250.63648s With SCCP: 250.988624s +0.1403027732444051% 541.leela_r Without SCCP: 346.066278s With SCCP: 339.692987s -1.8761915152519792% Regarding size: The pass doesn't seem to significantly reduce or increase the size of the result binary. The differences were at most ~0.1%. Regarding debug info coverage: I didn't notice any additional guality testcases failing after I applied the patch. *Is there any other way how I should check debug info coverage?* Filip K
On Thu, Aug 31, 2023 at 01:26:37PM +0200, Filip Kastl wrote: > Regarding debug info coverage: I didn't notice any additional guality testcases > failing after I applied the patch. *Is there any other way how I should check > debug info coverage?* I'm usually using https://github.com/pmachata/dwlocstat for that, usually on cc1plus from the last stage of gcc bootstrap. Though of course, if one tree is unpatched and one patched, that results in different code not just because the optimization did something, but because it is different source. So, for such purposes, I usually after one of the 2 bootstraps apply resp. revert the patch, make a copy of the cc1plus binary and do make -jN cc1plus in the last stage directory (only there, not attempt to rebootstrap). Jakub
On Thu, 31 Aug 2023, Filip Kastl wrote: > > The most obvious places would be right after SSA construction and before RTL expansion. > > Can you provide measurements for those positions? > > The algorithm should only remove PHIs that break SSA form minimality. Since > GCC's SSA construction already produces minimal SSA form, the algorithm isn't > expected to remove any PHIs if run right after the construction. I even > measured it and indeed -- no PHIs got removed (except for 502.gcc_r, where the > algorithm managed to remove exactly 1 PHI, which is weird). > > I tried putting the pass before pass_expand. There isn't a lot of PHIs to > remove at that point, but there still are some. That's interesting. Your placement at NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); NEXT_PASS (pass_phiopt, true /* early_p */); + NEXT_PASS (pass_sccp); and NEXT_PASS (pass_tsan); NEXT_PASS (pass_dse, true /* use DR analysis */); NEXT_PASS (pass_dce); + NEXT_PASS (pass_sccp); isn't immediately after the "best" existing pass we have to remove dead PHIs which is pass_cd_dce. phiopt might leave dead PHIs around and the second instance runs long after the last CD-DCE. So I wonder if your pass just detects unnecessary PHIs we'd have removed by other means and what survives until RTL expansion is what we should count? Can you adjust your original early placement to right after the cd-dce pass and for the late placement turn the dce pass before it into cd-dce and re-do your measurements? > 500.perlbench_r > Started with 43111 > Ended with 42942 > Removed PHI % .39201131961680313700 > > 502.gcc_r > Started with 141392 > Ended with 140455 > Removed PHI % .66269661649881181400 > > 505.mcf_r > Started with 482 > Ended with 478 > Removed PHI % .82987551867219917100 > > 523.xalancbmk_r > Started with 136040 > Ended with 135629 > Removed PHI % .30211702440458688700 > > 531.deepsjeng_r > Started with 2150 > Ended with 2148 > Removed PHI % .09302325581395348900 > > 541.leela_r > Started with 4664 > Ended with 4650 > Removed PHI % .30017152658662092700 > > 557.xz_r > Started with 43 > Ended with 43 > Removed PHI % 0 > > > Can the pass somehow be used as part of propagations like during value numbering? > > I don't think that the pass could be used as a part of different optimizations > since it works on the whole CFG (except for copy propagation as I noted in the > RFC). I'm adding Honza into Cc. He'll have more insight into this. > > > Could the new file be called gimple-ssa-sccp.cc or something similar? > > Certainly. Though I'm not sure, but wouldn't tree-ssa-sccp.cc be more > appropriate? > > I'm thinking about naming the pass 'scc-copy' and the file > 'tree-ssa-scc-copy.cc'. > > > Removing some PHIs is nice, but it would be also interesting to know what > > are the effects on generated code size and/or performance. > > And also if it has any effects on debug information coverage. > > Regarding performance: I ran some benchmarks on a Zen3 machine with -O3 with > and without the new pass. *I got ~2% speedup for 505.mcf_r and 541.leela_r. > Here are the full results. What do you think? Should I run more benchmarks? Or > benchmark multiple times? Or run the benchmarks on different machines?* > > 500.perlbench_r > Without SCCP: 244.151807s > With SCCP: 242.448438s > -0.7025695913124297% > > 502.gcc_r > Without SCCP: 211.029606s > With SCCP: 211.614523s > +0.27640683243653763% > > 505.mcf_r > Without SCCP: 298.782621s > With SCCP: 291.671468s > -2.438069465197046% > > 523.xalancbmk_r > Without SCCP: 189.940639s > With SCCP: 189.876261s > -0.03390523894928332% > > 531.deepsjeng_r > Without SCCP: 250.63648s > With SCCP: 250.988624s > +0.1403027732444051% > > 541.leela_r > Without SCCP: 346.066278s > With SCCP: 339.692987s > -1.8761915152519792% > > Regarding size: The pass doesn't seem to significantly reduce or increase the > size of the result binary. The differences were at most ~0.1%. > > Regarding debug info coverage: I didn't notice any additional guality testcases > failing after I applied the patch. *Is there any other way how I should check > debug info coverage?* > > > Filip K >
On Thu, Aug 31, 2023 at 5:15 AM Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > On Thu, 31 Aug 2023, Filip Kastl wrote: > > > > The most obvious places would be right after SSA construction and before RTL expansion. > > > Can you provide measurements for those positions? > > > > The algorithm should only remove PHIs that break SSA form minimality. Since > > GCC's SSA construction already produces minimal SSA form, the algorithm isn't > > expected to remove any PHIs if run right after the construction. I even > > measured it and indeed -- no PHIs got removed (except for 502.gcc_r, where the > > algorithm managed to remove exactly 1 PHI, which is weird). > > > > I tried putting the pass before pass_expand. There isn't a lot of PHIs to > > remove at that point, but there still are some. > > That's interesting. Your placement at > > NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); > NEXT_PASS (pass_phiopt, true /* early_p */); > + NEXT_PASS (pass_sccp); > > and > > NEXT_PASS (pass_tsan); > NEXT_PASS (pass_dse, true /* use DR analysis */); > NEXT_PASS (pass_dce); > + NEXT_PASS (pass_sccp); > > isn't immediately after the "best" existing pass we have to > remove dead PHIs which is pass_cd_dce. phiopt might leave > dead PHIs around and the second instance runs long after the > last CD-DCE. Actually the last phiopt is run before last pass_cd_dce: NEXT_PASS (pass_dce, true /* update_address_taken_p */); /* After late DCE we rewrite no longer addressed locals into SSA form if possible. */ NEXT_PASS (pass_forwprop); NEXT_PASS (pass_sink_code, true /* unsplit edges */); NEXT_PASS (pass_phiopt, false /* early_p */); NEXT_PASS (pass_fold_builtins); NEXT_PASS (pass_optimize_widening_mul); NEXT_PASS (pass_store_merging); /* If DCE is not run before checking for uninitialized uses, we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c). However, this also causes us to misdiagnose cases that should be real warnings (e.g., testsuite/gcc.dg/pr18501.c). */ NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); Thanks, Andrew Pinski > > So I wonder if your pass just detects unnecessary PHIs we'd have > removed by other means and what survives until RTL expansion is > what we should count? > > Can you adjust your original early placement to right after > the cd-dce pass and for the late placement turn the dce pass > before it into cd-dce and re-do your measurements? > > > 500.perlbench_r > > Started with 43111 > > Ended with 42942 > > Removed PHI % .39201131961680313700 > > > > 502.gcc_r > > Started with 141392 > > Ended with 140455 > > Removed PHI % .66269661649881181400 > > > > 505.mcf_r > > Started with 482 > > Ended with 478 > > Removed PHI % .82987551867219917100 > > > > 523.xalancbmk_r > > Started with 136040 > > Ended with 135629 > > Removed PHI % .30211702440458688700 > > > > 531.deepsjeng_r > > Started with 2150 > > Ended with 2148 > > Removed PHI % .09302325581395348900 > > > > 541.leela_r > > Started with 4664 > > Ended with 4650 > > Removed PHI % .30017152658662092700 > > > > 557.xz_r > > Started with 43 > > Ended with 43 > > Removed PHI % 0 > > > > > Can the pass somehow be used as part of propagations like during value numbering? > > > > I don't think that the pass could be used as a part of different optimizations > > since it works on the whole CFG (except for copy propagation as I noted in the > > RFC). I'm adding Honza into Cc. He'll have more insight into this. > > > > > Could the new file be called gimple-ssa-sccp.cc or something similar? > > > > Certainly. Though I'm not sure, but wouldn't tree-ssa-sccp.cc be more > > appropriate? > > > > I'm thinking about naming the pass 'scc-copy' and the file > > 'tree-ssa-scc-copy.cc'. > > > > > Removing some PHIs is nice, but it would be also interesting to know what > > > are the effects on generated code size and/or performance. > > > And also if it has any effects on debug information coverage. > > > > Regarding performance: I ran some benchmarks on a Zen3 machine with -O3 with > > and without the new pass. *I got ~2% speedup for 505.mcf_r and 541.leela_r. > > Here are the full results. What do you think? Should I run more benchmarks? Or > > benchmark multiple times? Or run the benchmarks on different machines?* > > > > 500.perlbench_r > > Without SCCP: 244.151807s > > With SCCP: 242.448438s > > -0.7025695913124297% > > > > 502.gcc_r > > Without SCCP: 211.029606s > > With SCCP: 211.614523s > > +0.27640683243653763% > > > > 505.mcf_r > > Without SCCP: 298.782621s > > With SCCP: 291.671468s > > -2.438069465197046% > > > > 523.xalancbmk_r > > Without SCCP: 189.940639s > > With SCCP: 189.876261s > > -0.03390523894928332% > > > > 531.deepsjeng_r > > Without SCCP: 250.63648s > > With SCCP: 250.988624s > > +0.1403027732444051% > > > > 541.leela_r > > Without SCCP: 346.066278s > > With SCCP: 339.692987s > > -1.8761915152519792% > > > > Regarding size: The pass doesn't seem to significantly reduce or increase the > > size of the result binary. The differences were at most ~0.1%. > > > > Regarding debug info coverage: I didn't notice any additional guality testcases > > failing after I applied the patch. *Is there any other way how I should check > > debug info coverage?* > > > > > > Filip K > > > > -- > Richard Biener <rguenther@suse.de> > SUSE Software Solutions Germany GmbH, > Frankenstrasse 146, 90461 Nuernberg, Germany; > GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
On Thu, 31 Aug 2023, Andrew Pinski wrote: > On Thu, Aug 31, 2023 at 5:15?AM Richard Biener via Gcc-patches > <gcc-patches@gcc.gnu.org> wrote: > > > > On Thu, 31 Aug 2023, Filip Kastl wrote: > > > > > > The most obvious places would be right after SSA construction and before RTL expansion. > > > > Can you provide measurements for those positions? > > > > > > The algorithm should only remove PHIs that break SSA form minimality. Since > > > GCC's SSA construction already produces minimal SSA form, the algorithm isn't > > > expected to remove any PHIs if run right after the construction. I even > > > measured it and indeed -- no PHIs got removed (except for 502.gcc_r, where the > > > algorithm managed to remove exactly 1 PHI, which is weird). > > > > > > I tried putting the pass before pass_expand. There isn't a lot of PHIs to > > > remove at that point, but there still are some. > > > > That's interesting. Your placement at > > > > NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); > > NEXT_PASS (pass_phiopt, true /* early_p */); > > + NEXT_PASS (pass_sccp); > > > > and > > > > NEXT_PASS (pass_tsan); > > NEXT_PASS (pass_dse, true /* use DR analysis */); > > NEXT_PASS (pass_dce); > > + NEXT_PASS (pass_sccp); > > > > isn't immediately after the "best" existing pass we have to > > remove dead PHIs which is pass_cd_dce. phiopt might leave > > dead PHIs around and the second instance runs long after the > > last CD-DCE. > > Actually the last phiopt is run before last pass_cd_dce: I meant the second instance of pass_sccp, not phiopt. Richard.
> That's interesting. Your placement at > > NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); > NEXT_PASS (pass_phiopt, true /* early_p */); > + NEXT_PASS (pass_sccp); > > and > > NEXT_PASS (pass_tsan); > NEXT_PASS (pass_dse, true /* use DR analysis */); > NEXT_PASS (pass_dce); > + NEXT_PASS (pass_sccp); > > isn't immediately after the "best" existing pass we have to > remove dead PHIs which is pass_cd_dce. phiopt might leave > dead PHIs around and the second instance runs long after the > last CD-DCE. > > So I wonder if your pass just detects unnecessary PHIs we'd have > removed by other means and what survives until RTL expansion is > what we should count? > > Can you adjust your original early placement to right after > the cd-dce pass and for the late placement turn the dce pass > before it into cd-dce and re-do your measurements? So I did this NEXT_PASS (pass_dse); NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); NEXT_PASS (pass_sccp); NEXT_PASS (pass_phiopt, true /* early_p */); NEXT_PASS (pass_tail_recursion); and this NEXT_PASS (pass_dse, true /* use DR analysis */); NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); NEXT_PASS (pass_sccp); /* Pass group that runs when 1) enabled, 2) there are loops and got these results: 500.perlbench_r Started with (1) 30318 Ended with (1) 26219 Removed PHI % (1) 13.52002110957187149600 Started with (2) 39043 Ended with (2) 38941 Removed PHI % (2) .26125041620777092000 502.gcc_r Started with (1) 148361 Ended with (1) 140464 Removed PHI % (1) 5.32282742769326170700 Started with (2) 216209 Ended with (2) 215367 Removed PHI % (2) .38943799749316633500 505.mcf_r Started with (1) 342 Ended with (1) 304 Removed PHI % (1) 11.11111111111111111200 Started with (2) 437 Ended with (2) 433 Removed PHI % (2) .91533180778032036700 523.xalancbmk_r Started with (1) 62995 Ended with (1) 58289 Removed PHI % (1) 7.47043416144138423700 Started with (2) 134026 Ended with (2) 133193 Removed PHI % (2) .62152119737961291100 531.deepsjeng_r Started with (1) 1402 Ended with (1) 1264 Removed PHI % (1) 9.84308131241084165500 Started with (2) 1928 Ended with (2) 1920 Removed PHI % (2) .41493775933609958600 541.leela_r Started with (1) 3398 Ended with (1) 3060 Removed PHI % (1) 9.94702766333137139500 Started with (2) 4473 Ended with (2) 4453 Removed PHI % (2) .44712720769058797300 557.xz_r Started with (1) 47 Ended with (1) 44 Removed PHI % (1) 6.38297872340425532000 Started with (2) 43 Ended with (2) 43 Removed PHI % (2) 0 These measurements don't differ very much from the previous. It seems to me that phiopt does output some redundant PHIs but the vast majority of the eliminated PHIs are generated in earlier passes and cd_dce isn't able to get rid of them. A noteworthy information might be that most of the eliminated PHIs are actually trivial PHIs. I consider a PHI to be trivial if it only references itself or one other SSA name. Here is a comparison of the newest measurements (sccp after cd_dce) with the previous ones (sccp after phiopt and dce): 500.perlbench_r Started with (1-PREV) 30287 Started with (1-NEW) 30318 Ended with (1-PREV) 26188 Ended with (1-NEW) 26219 Removed PHI % (1-PREV) 13.53385941162875161000 Removed PHI % (1-NEW) 13.52002110957187149600 Started with (2-PREV) 38005 Started with (2-NEW) 39043 Ended with (2-PREV) 37897 Ended with (2-NEW) 38941 Removed PHI % (2-PREV) .28417313511380081600 Removed PHI % (2-NEW) .26125041620777092000 502.gcc_r Started with (1-PREV) 148187 Started with (1-NEW) 148361 Ended with (1-PREV) 140292 Ended with (1-NEW) 140464 Removed PHI % (1-PREV) 5.32772780338356266100 Removed PHI % (1-NEW) 5.32282742769326170700 Started with (2-PREV) 211479 Started with (2-NEW) 216209 Ended with (2-PREV) 210635 Ended with (2-NEW) 215367 Removed PHI % (2-PREV) .39909399987705635100 Removed PHI % (2-NEW) .38943799749316633500 Filip K P.S. I made a small mistake and didn't compute the benchmark speedup percentages right in the previous email. Here are the corrected results. The correct percentages are a little bit smaller but very similar. There is still a ~2% speedup with 505.mcf_r and 541.leela_r. 500.perlbench_r Without SCCP: 244.151807s With SCCP: 242.448438s -0.6976679881791663% 502.gcc_r Without SCCP: 211.029606s With SCCP: 211.614523s +0.27717295742853737% 505.mcf_r Without SCCP: 298.782621s With SCCP: 291.671468s -2.380042378703145% 523.xalancbmk_r Without SCCP: 189.940639s With SCCP: 189.876261s -0.03389374719330334% 531.deepsjeng_r Without SCCP: 250.63648s With SCCP: 250.988624s +0.14049989849840747% 541.leela_r Without SCCP: 346.066278s With SCCP: 339.692987s -1.8416388435281157%
On Fri, 1 Sep 2023, Filip Kastl wrote: > > That's interesting. Your placement at > > > > NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); > > NEXT_PASS (pass_phiopt, true /* early_p */); > > + NEXT_PASS (pass_sccp); > > > > and > > > > NEXT_PASS (pass_tsan); > > NEXT_PASS (pass_dse, true /* use DR analysis */); > > NEXT_PASS (pass_dce); > > + NEXT_PASS (pass_sccp); > > > > isn't immediately after the "best" existing pass we have to > > remove dead PHIs which is pass_cd_dce. phiopt might leave > > dead PHIs around and the second instance runs long after the > > last CD-DCE. > > > > So I wonder if your pass just detects unnecessary PHIs we'd have > > removed by other means and what survives until RTL expansion is > > what we should count? > > > > Can you adjust your original early placement to right after > > the cd-dce pass and for the late placement turn the dce pass > > before it into cd-dce and re-do your measurements? > > So I did this > > NEXT_PASS (pass_dse); > NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); > NEXT_PASS (pass_sccp); > NEXT_PASS (pass_phiopt, true /* early_p */); > NEXT_PASS (pass_tail_recursion); > > and this > > NEXT_PASS (pass_dse, true /* use DR analysis */); > NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); > NEXT_PASS (pass_sccp); > /* Pass group that runs when 1) enabled, 2) there are loops > > and got these results: > > 500.perlbench_r > Started with (1) 30318 > Ended with (1) 26219 > Removed PHI % (1) 13.52002110957187149600 > Started with (2) 39043 > Ended with (2) 38941 > Removed PHI % (2) .26125041620777092000 > > 502.gcc_r > Started with (1) 148361 > Ended with (1) 140464 > Removed PHI % (1) 5.32282742769326170700 > Started with (2) 216209 > Ended with (2) 215367 > Removed PHI % (2) .38943799749316633500 > > 505.mcf_r > Started with (1) 342 > Ended with (1) 304 > Removed PHI % (1) 11.11111111111111111200 > Started with (2) 437 > Ended with (2) 433 > Removed PHI % (2) .91533180778032036700 > > 523.xalancbmk_r > Started with (1) 62995 > Ended with (1) 58289 > Removed PHI % (1) 7.47043416144138423700 > Started with (2) 134026 > Ended with (2) 133193 > Removed PHI % (2) .62152119737961291100 > > 531.deepsjeng_r > Started with (1) 1402 > Ended with (1) 1264 > Removed PHI % (1) 9.84308131241084165500 > Started with (2) 1928 > Ended with (2) 1920 > Removed PHI % (2) .41493775933609958600 > > 541.leela_r > Started with (1) 3398 > Ended with (1) 3060 > Removed PHI % (1) 9.94702766333137139500 > Started with (2) 4473 > Ended with (2) 4453 > Removed PHI % (2) .44712720769058797300 > > 557.xz_r > Started with (1) 47 > Ended with (1) 44 > Removed PHI % (1) 6.38297872340425532000 > Started with (2) 43 > Ended with (2) 43 > Removed PHI % (2) 0 > > These measurements don't differ very much from the previous. It seems to me > that phiopt does output some redundant PHIs but the vast majority of the > eliminated PHIs are generated in earlier passes and cd_dce isn't able to get > rid of them. > > A noteworthy information might be that most of the eliminated PHIs are actually > trivial PHIs. I consider a PHI to be trivial if it only references itself or > one other SSA name. Ah. The early pass numbers are certainly intresting - can you elaborate on the last bit? We have for example loop-closed PHI nodes like _1 = PHI <_2> and there are non-trivial degenerate PHIs like _1 = PHI <_2, _2> those are generally removed by value-numbering (FRE, DOM and PRE) and SSA propagation (CCP and copyprop), they are not "dead" so CD-DCE doesn't remove them. But we do have passes removing these kind of PHIs. The issue with the early pass is likely that we have NEXT_PASS (pass_fre, true /* may_iterate */); ^^ would elimimate these kind of PHIs NEXT_PASS (pass_early_vrp); ^^ rewrites into loop-closed SSA, adding many such PHIs NEXT_PASS (pass_merge_phi); NEXT_PASS (pass_dse); NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); and until here there's no pass eliding the LC SSA PHIs. You could add a pass_copy_prop after early_vrp, the later sccp pass shouldn't run into this issue I think so it must be other passes adding such kind of PHIs. Maybe you can count single-argument PHIs, degenerate multi-arg PHIs and "other" PHIs separately as you remove them? > Here is a comparison of the newest measurements (sccp after cd_dce) with the > previous ones (sccp after phiopt and dce): > > 500.perlbench_r > > Started with (1-PREV) 30287 > Started with (1-NEW) 30318 > > Ended with (1-PREV) 26188 > Ended with (1-NEW) 26219 > > Removed PHI % (1-PREV) 13.53385941162875161000 > Removed PHI % (1-NEW) 13.52002110957187149600 > > Started with (2-PREV) 38005 > Started with (2-NEW) 39043 > > Ended with (2-PREV) 37897 > Ended with (2-NEW) 38941 > > Removed PHI % (2-PREV) .28417313511380081600 > Removed PHI % (2-NEW) .26125041620777092000 > > 502.gcc_r > > Started with (1-PREV) 148187 > Started with (1-NEW) 148361 > > Ended with (1-PREV) 140292 > Ended with (1-NEW) 140464 > > Removed PHI % (1-PREV) 5.32772780338356266100 > Removed PHI % (1-NEW) 5.32282742769326170700 > > Started with (2-PREV) 211479 > Started with (2-NEW) 216209 > > Ended with (2-PREV) 210635 > Ended with (2-NEW) 215367 > > Removed PHI % (2-PREV) .39909399987705635100 > Removed PHI % (2-NEW) .38943799749316633500 > > > Filip K > > > P.S. I made a small mistake and didn't compute the benchmark speedup > percentages right in the previous email. Here are the corrected results. The > correct percentages are a little bit smaller but very similar. There is still a > ~2% speedup with 505.mcf_r and 541.leela_r. > > 500.perlbench_r > Without SCCP: 244.151807s > With SCCP: 242.448438s > -0.6976679881791663% > > 502.gcc_r > Without SCCP: 211.029606s > With SCCP: 211.614523s > +0.27717295742853737% > > 505.mcf_r > Without SCCP: 298.782621s > With SCCP: 291.671468s > -2.380042378703145% > > 523.xalancbmk_r > Without SCCP: 189.940639s > With SCCP: 189.876261s > -0.03389374719330334% > > 531.deepsjeng_r > Without SCCP: 250.63648s > With SCCP: 250.988624s > +0.14049989849840747% > > 541.leela_r > Without SCCP: 346.066278s > With SCCP: 339.692987s > -1.8416388435281157% > >
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 78779546459..7c34eb6ceda 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1706,6 +1706,7 @@ OBJS = \ tree-ssa-forwprop.o \ tree-ssa-ifcombine.o \ tree-ssa-live.o \ + sccp.o \ tree-ssa-loop-ch.o \ tree-ssa-loop-im.o \ tree-ssa-loop-ivcanon.o \ diff --git a/gcc/passes.def b/gcc/passes.def index ef5a21afe49..4c94f9cec8b 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -96,6 +96,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_dse); NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */); NEXT_PASS (pass_phiopt, true /* early_p */); + NEXT_PASS (pass_sccp); NEXT_PASS (pass_tail_recursion); NEXT_PASS (pass_if_to_switch); NEXT_PASS (pass_convert_switch); @@ -271,6 +272,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_tsan); NEXT_PASS (pass_dse, true /* use DR analysis */); NEXT_PASS (pass_dce); + NEXT_PASS (pass_sccp); /* Pass group that runs when 1) enabled, 2) there are loops in the function. Make sure to run pass_fix_loops before to discover/remove loops before running the gate function diff --git a/gcc/sccp.cc b/gcc/sccp.cc new file mode 100644 index 00000000000..86a79303902 --- /dev/null +++ b/gcc/sccp.cc @@ -0,0 +1,722 @@ +/* Strongly connected copy propagation pass for the GNU compiler. + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Filip Kastl <filip.kastl@gmail.com> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-iterator.h" +#include "vec.h" +#include "hash-set.h" +#include <algorithm> +#include "ssa-iterators.h" +#include "gimple-fold.h" +#include "gimplify.h" +#include "tree-cfg.h" +#include "tree-ssa-propagate.h" + +/* State of vertex during tarjan computation. + + unvisited Vertex hasn't yet been popped from worklist. + vopen DFS has visited vertex for the first time. Vertex has been put on + Tarjan stack. + closed DFS has backtracked through vertex. At this point, vertex doesn't + have any unvisited neighbors. + in_scc Vertex has been popped from tarjan stack. */ + +enum vstate +{ + unvisited, + vopen, + closed, + in_scc +}; + +/* Information about a vertex used by tarjan. */ + +struct vertex +{ + vstate state; + unsigned index; + unsigned lowlink; + gimple* stmt; +}; + +static bool +stmt_may_generate_copy (gimple *stmt) +{ + if (gimple_code (stmt) == GIMPLE_PHI) + { + gphi *phi = as_a <gphi *> (stmt); + + /* No OCCURS_IN_ABNORMAL_PHI SSA names in lhs nor rhs. */ + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi))) + { + return false; + } + + unsigned i; + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + tree op = gimple_phi_arg_def (phi, i); + if (TREE_CODE (op) == SSA_NAME && + SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) + { + return false; + } + } + + return true; + } + + if (gimple_code (stmt) != GIMPLE_ASSIGN) + { + return false; + } + + /* If the statement has volatile operands, it won't generate a + useful copy. */ + if (gimple_has_volatile_ops (stmt)) + { + return false; + } + + /* Statements with loads and/or stores will never generate a useful copy. */ + if (gimple_store_p (stmt) || gimple_assign_load_p (stmt)) + { + return false; + } + + if (!gimple_assign_single_p (stmt)) + { + return false; + } + + tree lhs = gimple_assign_lhs (stmt); + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) + { + return false; + } + + /* If the assignment is from a constant it generates a useful copy. */ + if (is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) + { + return true; + } + + /* Otherwise, the only statements that generate useful copies are + assignments whose single SSA use doesn't flow through abnormal + edges. */ + tree rhs = single_ssa_tree_operand (stmt, SSA_OP_USE); + + if (!is_gimple_val (gimple_assign_rhs1 (stmt))) + { + return false; + } + + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) + { + return false; + } + + if (!rhs) + { + return false; + } + + return true; +} + +/* Set 'using' flag of gimple statement to true. + If the flag isn't set, tarjan will ignore the statement. */ + +static void +tarjan_set_using (gimple* stmt) +{ + gimple_set_plf (stmt, GF_PLF_1, true); +} + +/* Clear 'using' flag of gimple statement to false. */ + +static void +tarjan_clear_using (gimple* stmt) +{ + gimple_set_plf (stmt, GF_PLF_1, false); +} + +/* Return value of 'using' flag of gimple statement. */ + +static bool +tarjan_is_using (gimple* stmt) +{ + return gimple_plf (stmt, GF_PLF_1); +} + +/* Set 'vxnum' (vertex number) of statement. Before computing SCCs, tarjan + assigns unique vxnums to statements that it will use. */ + +static void +tarjan_set_vxnum (gimple* stmt, unsigned num) +{ + gimple_set_uid (stmt, num); +} + +/* Return 'vxnum' (vertex number) of statement. */ + +static unsigned +tarjan_vxnum (gimple* stmt) +{ + return gimple_uid (stmt); +} + +/* Create and initialize vertex struct for each given statement. */ + +static auto_vec<vertex> +tarjan_stmts_to_vertices (auto_vec<gimple *> &stmts) +{ + auto_vec<vertex> result; + for (gimple *stmt : stmts) + { + vertex v; + v.state = unvisited; + v.index = 0; + v.lowlink = 0; + v.stmt = stmt; + + result.safe_push (v); + } + return result; +} + +static void +tarjan_visit_neighbor (tree neigh_tree, unsigned parent_vxnum, + auto_vec<vertex> &vs, auto_vec<unsigned> &worklist) +{ + if (TREE_CODE (neigh_tree) != SSA_NAME) + return; /* Skip any neighbor that isn't an SSA name. */ + + gimple *neigh_stmt = SSA_NAME_DEF_STMT (neigh_tree); + + /* Skip neighbors outside the induced subgraph that Tarjan currently works + with. */ + if (!tarjan_is_using (neigh_stmt)) + return; + unsigned neigh_vxnum = tarjan_vxnum (neigh_stmt); + + gcc_checking_assert (stmt_may_generate_copy (neigh_stmt)); + + vstate neigh_state = vs[neigh_vxnum].state; + vstate parent_state = vs[parent_vxnum].state; + if (parent_state == vopen) /* We're currently opening parent. */ + { + /* Put unvisited neighbors on worklist. Update lowlink of parent + vertex according to indices of neighbors present on stack. */ + switch (neigh_state) + { + case unvisited: + worklist.safe_push (neigh_vxnum); + break; + case vopen: + case closed: + vs[parent_vxnum].lowlink = std::min (vs[parent_vxnum].lowlink, + vs[neigh_vxnum].index); + break; + case in_scc: + /* Ignore these edges. */ + break; + } + } + else if (parent_state == closed) /* We're currently closing parent. */ + { + /* Update lowlink of parent vertex according to lowlinks of + children of parent (in terms of DFS tree). */ + if (neigh_state == closed) + { + vs[parent_vxnum].lowlink = std::min (vs[parent_vxnum].lowlink, + vs[neigh_vxnum].lowlink); + } + } +} + +/* Nonrecursive implementation of Tarjan's algorithm for computing strongly + connected components in a graph. Statements are vertices. Edges lead from a + copy stmt p using another copy stmt q to the stmt being used (p -> q when q + is operand of p). + + Considers only the subgraph induced by given statements. */ + +static auto_vec<vec<gimple *>> +tarjan_compute_sccs (auto_vec<gimple *> ©_stmts) +{ + auto_vec<vec<gimple *>> sccs; + auto_vec<unsigned> worklist; /* DFS stack. */ + auto_vec<unsigned> stack; /* Tarjan stack. */ + unsigned curr_index = 0; + + auto_vec<vertex> vs = tarjan_stmts_to_vertices (copy_stmts); + + /* Mark the subgraph induced by 'copy_stmts' and index it by vxnums. */ + unsigned i; + for (i = 0; i < vs.length (); i++) + { + gimple *stmt = vs[i].stmt; + tarjan_set_using (stmt); + tarjan_set_vxnum (stmt, i); + } + + /* Put all vertices on worklist. */ + for (i = 0; i < vs.length (); i++) + { + worklist.safe_push (i); + } + + /* Worklist loop. */ + while (!worklist.is_empty ()) + { + unsigned i = worklist.pop(); + gimple *stmt = vs[i].stmt; + vstate state = vs[i].state; + + if (state == unvisited) + { + vs[i].state = vopen; + + /* Assign index to this vertex. */ + vs[i].index = curr_index; + vs[i].lowlink = curr_index; + curr_index++; + + /* Put vertex on stack and also on worklist to be closed later. */ + stack.safe_push (i); + worklist.safe_push (i); + } + else if (state == vopen) + { + vs[i].state = closed; + } + + /* Visit neighbors of this vertex. */ + tree op; + gphi *phi; + switch (gimple_code (stmt)) + { + case GIMPLE_PHI: + phi = as_a <gphi *> (stmt); + unsigned j; + for (j = 0; j < gimple_phi_num_args (phi); j++) + { + op = gimple_phi_arg_def (phi, j); + tarjan_visit_neighbor (op, i, vs, worklist); + } + break; + case GIMPLE_ASSIGN: + op = gimple_assign_rhs1 (stmt); + tarjan_visit_neighbor (op, i, vs, worklist); + break; + default: + gcc_unreachable (); + } + + /* If we've just closed a root vertex of an scc, pop scc from stack. */ + if (state == vopen && vs[i].lowlink == vs[i].index) + { + vec<gimple *> scc = vNULL; + + unsigned j; + do + { + j = stack.pop(); + scc.safe_push (vs[j].stmt); + vs[j].state = in_scc; + } + while (j != i); + + sccs.safe_push (scc); + } + } + + if (!stack.is_empty ()) + { + gcc_unreachable(); + } + + /* Clear copy stmts' 'using' flags. */ + for (vertex v : vs) + { + gimple *s = v.stmt; + tarjan_clear_using (s); + } + + return sccs; +} + +static void +replace_use_by (tree get_replaced, tree replace_by, bitmap need_eh_cleanup, + bitmap need_ab_cleanup, vec<gimple *> stmts_to_fixup) +{ + /* Replace each occurence of 'get_replaced' by 'replace_by'. */ + use_operand_p use_p; + imm_use_iterator iter; + gimple *use_stmt; + FOR_EACH_IMM_USE_STMT (use_stmt, iter, get_replaced) + { + bool was_noreturn = false; + bool can_make_abnormal_goto = false; + if (is_gimple_call (use_stmt)) + { + was_noreturn = gimple_call_noreturn_p (use_stmt); + can_make_abnormal_goto = stmt_can_make_abnormal_goto (use_stmt); + } + + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + SET_USE (use_p, unshare_expr (replace_by)); + + /* Recompute tree invariant. */ + if (gimple_assign_single_p (use_stmt)) + { + tree rhs = gimple_assign_rhs1 (use_stmt); + + if (TREE_CODE (rhs) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (rhs); + } + + /* Cleanup. */ + gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); + fold_stmt (&gsi); + gimple_set_modified (gsi_stmt (gsi), true); + cleanup_after_replace (use_stmt, gsi_stmt (gsi), need_eh_cleanup, + need_ab_cleanup, stmts_to_fixup, + can_make_abnormal_goto, was_noreturn); + } +} + +/* Modify all usages of PHIs in a given SCC to instead reference a given + variable. */ + +static void +replace_scc_by_value (vec<gimple *> scc, tree replace_by, bitmap + need_eh_cleanup, bitmap need_ab_cleanup, vec<gimple *> + stmts_to_fixup) +{ + // DEBUG + if (dump_file) + { + fprintf (dump_file, "Replacing SCC of length %d\n", scc.length ()); + } + + for (gimple *stmt : scc) + { + tree get_replaced = gimple_get_lhs (stmt); + replace_use_by (get_replaced, replace_by, need_eh_cleanup, + need_ab_cleanup, stmts_to_fixup); + } +} + +/* Remove all PHIs with zero uses. */ + +static void +remove_zero_uses_phis () +{ + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi);) + { + gphi *phi = pi.phi (); + tree ssa_name = gimple_phi_result (phi); + if (has_zero_uses (ssa_name)) + { + /* Note that remove_phi_node() also frees SSA name. */ + remove_phi_node (&pi, true); + } + else + gsi_next (&pi); + } + } +} + +static void +sccp_visit_op (tree op, hash_set<tree> &outer_ops, hash_set<gimple *> &scc_set, + bool &is_inner, tree &last_outer_op) +{ + bool op_in_scc = false; + + if (TREE_CODE (op) == SSA_NAME) + { + gimple *op_stmt = SSA_NAME_DEF_STMT (op); + if (scc_set.contains (op_stmt)) + op_in_scc = true; + } + + if (!op_in_scc) + { + outer_ops.add (op); + last_outer_op = op; + is_inner = false; + } +} + +/* Apply Braun et al.'s algorithm on a given set of statements. Treat copy + statements as PHI functions with a single argument. + Main function of this pass. */ + +static void +sccp_propagate (auto_vec<gimple *> ©_stmts) +{ + auto_vec<vec<gimple *>> worklist; + worklist = tarjan_compute_sccs (copy_stmts); + + /* Prepare data structs for cleanup after stmt modification. */ + bitmap need_eh_cleanup = BITMAP_ALLOC (NULL); + bitmap need_ab_cleanup = BITMAP_ALLOC (NULL); + vec<gimple *> stmts_to_fixup = vNULL; + + while (!worklist.is_empty ()) + { + vec<gimple *> scc = worklist.pop (); + + auto_vec<gimple *> inner; + hash_set<tree> outer_ops; + tree last_outer_op = NULL_TREE; + + /* Prepare hash set of PHIs in scc to query later. */ + hash_set<gimple *> scc_set; + for (gimple *stmt : scc) + { + scc_set.add (stmt); + } + + for (gimple *stmt : scc) + { + bool is_inner = true; + + gphi *phi; + tree op; + switch (gimple_code (stmt)) + { + case GIMPLE_PHI: + phi = as_a <gphi *> (stmt); + unsigned j; + for (j = 0; j < gimple_phi_num_args (phi); j++) + { + op = gimple_phi_arg_def (phi, j); + sccp_visit_op (op, outer_ops, scc_set, is_inner, + last_outer_op); + } + break; + case GIMPLE_ASSIGN: + op = gimple_assign_rhs1 (stmt); + sccp_visit_op (op, outer_ops, scc_set, is_inner, + last_outer_op); + break; + default: + gcc_unreachable (); + } + + if (is_inner) + { + inner.safe_push (stmt); + } + } + + if (outer_ops.elements () == 1) + { + /* The only operand in outer_ops. */ + tree outer_op = last_outer_op; + + replace_scc_by_value (scc, outer_op, need_eh_cleanup, + need_ab_cleanup, stmts_to_fixup); + } + else if (outer_ops.elements () > 1) + { + /* Add inner sccs to worklist. */ + auto_vec<vec<gimple *>> inner_sccs = tarjan_compute_sccs (inner); + for (vec<gimple *> inner_scc : inner_sccs) + { + worklist.safe_push (inner_scc); + } + } + else + { + gcc_unreachable (); + } + + scc.release (); + } + + cleanup_after_all_replaces_done (need_eh_cleanup, need_ab_cleanup, + stmts_to_fixup); + + /* Remove data structs for cleanup after stmt modification. */ + BITMAP_FREE (need_eh_cleanup); + BITMAP_FREE (need_ab_cleanup); + stmts_to_fixup.release (); + + /* We want to remove dead MEM PHIs because memory is in FUD SSA and the dead + PHIs would break the FUD property. */ + remove_zero_uses_phis (); +} + +/* Return all statements in cfun that may be useful. */ + +static auto_vec<gimple *> +get_all_stmt_may_generate_copy (void) +{ + auto_vec<gimple *> result; + + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gimple_stmt_iterator gsi; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *s = gsi_stmt (gsi); + if (stmt_may_generate_copy (s)) + result.safe_push (s); + } + + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + { + gimple *s = pi.phi (); + if (stmt_may_generate_copy (s)) + result.safe_push (s); + } + } + + return result; +} + +/* Called when pass execution starts. */ + +static void +init_sccp (void) +{ + // Clear 'tarjan using' flag on all statements + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gimple_stmt_iterator gsi; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple* stmt = gsi_stmt (gsi); + tarjan_clear_using (stmt); + } + + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + { + gimple *stmt = pi.phi (); + tarjan_clear_using (stmt); + } + } +} + +/* Called before pass execution ends. */ + +static void +finalize_sccp (void) +{ + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gimple_purge_dead_eh_edges (bb); + } +} + +namespace { + +const pass_data pass_data_sccp = +{ + GIMPLE_PASS, /* type */ + "sccp", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_NONE, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */ +}; + +class pass_sccp : public gimple_opt_pass +{ +public: + pass_sccp (gcc::context *ctxt) + : gimple_opt_pass (pass_data_sccp, ctxt) + {} + + /* opt_pass methods: */ + virtual bool gate (function *) { return true; } + virtual unsigned int execute (function *); + opt_pass * clone () final override { return new pass_sccp (m_ctxt); } +}; // class pass_sccp + +unsigned +pass_sccp::execute (function *) +{ + // DEBUG + if (dump_file) + { + int phis = 0; + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + phis++; + } + fprintf (dump_file, "Started with %d PHIs\n", phis); + } + + init_sccp (); + auto_vec<gimple *> stmts = get_all_stmt_may_generate_copy (); + sccp_propagate (stmts); + finalize_sccp (); + + // DEBUG + if (dump_file) + { + int phis = 0; + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + gphi_iterator pi; + for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) + phis++; + } + fprintf (dump_file, "Ended with %d PHIs\n", phis); + } + + return 0; +} + +} // anon namespace + +gimple_opt_pass * +make_pass_sccp (gcc::context *ctxt) +{ + return new pass_sccp (ctxt); +} diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 57865cdfc42..ac1d8848c25 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -398,6 +398,7 @@ extern gimple_opt_pass *make_pass_iv_optimize (gcc::context *ctxt); extern gimple_opt_pass *make_pass_tree_loop_done (gcc::context *ctxt); extern gimple_opt_pass *make_pass_ch (gcc::context *ctxt); extern gimple_opt_pass *make_pass_ch_vect (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_sccp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_ccp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_split_paths (gcc::context *ctxt); extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctxt); diff --git a/gcc/tree-ssa-propagate.cc b/gcc/tree-ssa-propagate.cc index cb68b419b8c..f70240dcd2f 100644 --- a/gcc/tree-ssa-propagate.cc +++ b/gcc/tree-ssa-propagate.cc @@ -1297,3 +1297,65 @@ clean_up_loop_closed_phi (function *fun) return 0; } + +void +cleanup_after_replace (gimple *old_stmt, gimple *stmt, bitmap need_eh_cleanup, + bitmap need_ab_cleanup, vec<gimple *> stmts_to_fixup, + bool can_make_abnormal_goto, bool was_noreturn) +{ + basic_block bb = stmt->bb; + + /* If we cleaned up EH information from the statement, + remove EH edges. */ + if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) + bitmap_set_bit (need_eh_cleanup, bb->index); + + /* If we turned a call with possible abnormal control transfer + into one that doesn't, remove abnormal edges. */ + if (can_make_abnormal_goto + && !stmt_can_make_abnormal_goto (stmt)) + bitmap_set_bit (need_ab_cleanup, bb->index); + + /* If we turned a not noreturn call into a noreturn one + schedule it for fixup. */ + if (!was_noreturn + && is_gimple_call (stmt) + && gimple_call_noreturn_p (stmt)) + stmts_to_fixup.safe_push (stmt); + + if (gimple_assign_single_p (stmt)) + { + tree rhs = gimple_assign_rhs1 (stmt); + + if (TREE_CODE (rhs) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (rhs); + } + + update_stmt_if_modified (stmt); +} + +void +cleanup_after_all_replaces_done (bitmap need_eh_cleanup, bitmap + need_ab_cleanup, vec<gimple *> stmts_to_fixup) +{ + if (!bitmap_empty_p (need_eh_cleanup)) + gimple_purge_all_dead_eh_edges (need_eh_cleanup); + if (!bitmap_empty_p (need_ab_cleanup)) + gimple_purge_all_dead_abnormal_call_edges (need_ab_cleanup); + + /* Fixup stmts that became noreturn calls. This may require splitting + blocks and thus isn't possible during the dominator walk. Do this + in reverse order so we don't inadvertedly remove a stmt we want to + fixup by visiting a dominating now noreturn call first. */ + while (!stmts_to_fixup.is_empty ()) + { + gimple *stmt = stmts_to_fixup.pop (); + if (dump_file && dump_flags & TDF_DETAILS) + { + fprintf (dump_file, "Fixing up noreturn call "); + print_gimple_stmt (dump_file, stmt, 0); + fprintf (dump_file, "\n"); + } + fixup_noreturn_call (stmt); + } +} diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h index 29bde37add9..a645baeacf4 100644 --- a/gcc/tree-ssa-propagate.h +++ b/gcc/tree-ssa-propagate.h @@ -72,6 +72,13 @@ extern void propagate_value (use_operand_p, tree); extern void replace_exp (use_operand_p, tree); extern void propagate_tree_value (tree *, tree); extern void propagate_tree_value_into_stmt (gimple_stmt_iterator *, tree); +extern void cleanup_after_replace (gimple *old_stmt, gimple *stmt, bitmap + need_eh_cleanup, bitmap need_ab_cleanup, + vec<gimple *> stmts_to_fixup, bool + can_make_abnormal_goto, bool was_noreturn); +extern void cleanup_after_all_replaces_done (bitmap need_eh_cleanup, bitmap + need_ab_cleanup, vec<gimple *> + stms_to_fixup); /* Public interface into the SSA propagation engine. Clients should inherit from this class and provide their own visitors. */
Hi, As a part of my bachelor thesis under the supervision of Honza (Jan Hubicka), I implemented a new PHI elimination algorithm into GCC. The algorithm is described in the following article: Braun, M., Buchwald, S., Hack, S., Leißa, R., Mallon, C., Zwinkau, A. (2013). Simple and Efficient Construction of Static Single Assignment Form. In: Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC 2013. Lecture Notes in Computer Science, vol 7791. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37051-9_6 In the article the PHI elimination algorithm is only considered a part of another algorithm. However, with Honza we tried running the algorithm as a standalone pass and found that there is a surprisingly big number of PHI functions it is able to remove -- sometimes even ~13% of PHI functions or more. This email contains a patch with the pass and with the placement in passes.def we used to measure this. Do you think that the pass is worthy of inclusion into upstream GCC? What are some things that I should change? Should I try to put the pass in different places in passes.def? Things I already know I'd like to change: - Split the patch into two (one for sccp, one for the utility functions) - Change the name SCCP to something else since there already is a pass with that name (any suggestions?) - Add a comment into sccp.cc explaining the algorithm I successfully bootstrapped and tested GCC with the patch applied (with the commit 3b691e0190c6e7291f8a52e1e14d8293a28ff4ce checked out). Here are my measurements. I measured the number of PHIs before the PHI elimination algorithm was run and after it was run. I measured on the standard 2017 benchmarks with -O3. Since the pass is present in passes.def twice, results of the first run are marked (1) and results of the second are marked (2). Honza also did measurements with profile feedback and got even bigger percentages. 500.perlbench_r Started with (1) 30287 Ended with (1) 26188 Removed PHI % (1) 13.53385941162875161000 Started with (2) 38005 Ended with (2) 37897 Removed PHI % (2) .28417313511380081600 502.gcc_r Started with (1) 148187 Ended with (1) 140292 Removed PHI % (1) 5.32772780338356266100 Started with (2) 211479 Ended with (2) 210635 Removed PHI % (2) .39909399987705635100 505.mcf_r Started with (1) 341 Ended with (1) 303 Removed PHI % (1) 11.14369501466275659900 Started with (2) 430 Ended with (2) 426 Removed PHI % (2) .93023255813953488400 523.xalancbmk_r Started with (1) 62514 Ended with (1) 57785 Removed PHI % (1) 7.56470550596666346800 Started with (2) 132561 Ended with (2) 131726 Removed PHI % (2) .62989868815111533600 531.deepsjeng_r Started with (1) 1388 Ended with (1) 1250 Removed PHI % (1) 9.94236311239193083600 Started with (2) 1887 Ended with (2) 1879 Removed PHI % (2) .42395336512983571900 541.leela_r Started with (1) 3332 Ended with (1) 2994 Removed PHI % (1) 10.14405762304921968800 Started with (2) 4372 Ended with (2) 4352 Removed PHI % (2) .45745654162854528900 Here is the patch: -- >8 -- This patch introduces two things: - A new PHI elimination pass (major) - New utility functions for passes that replace one ssa name with a different one (minor) Strongly-connected copy propagation (SCCP) pass The PHI elimination pass is a lightweight optimization pass based on strongly-connected components. Some set of PHIs may be redundant because the PHIs only refer to each other or to a single value from outside the set. This pass finds and eliminates these sets. As a bonus the pass also does some basic copy propagation because it considers a copy statement to be a PHI with a single argument. SCCP uses an algorithm from this article: Braun, M., Buchwald, S., Hack, S., Leißa, R., Mallon, C., Zwinkau, A. (2013). Simple and Efficient Construction of Static Single Assignment Form. In: Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC 2013. Lecture Notes in Computer Science, vol 7791. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37051-9_6 cleanup_after_replace and cleanup_after_all_replaces_done Whenever you replace all uses of an ssa name by a different ssa name, some GCC internal structures have to be updated. To streamline this process, the patch adds the cleanup_after_replace function that should be called after an ssa name is replaced by a different one and the cleanup_after_all_replaces_done that should be called before a pass that replaced one or more ssa names exits. The SCCP pass uses these functions. Signed-off-by: Filip Kastl <fkastl@suse.cz> gcc/ChangeLog: * Makefile.in: Added sccp pass. * passes.def: Added sccp pass to early and late optimizations. * tree-pass.h (make_pass_sccp): Added sccp pass. * tree-ssa-propagate.cc (cleanup_after_replace): New function. (cleanup_after_all_replaces_done): New function. * tree-ssa-propagate.h (cleanup_after_replace): New function. (cleanup_after_all_replaces_done): New function. * sccp.cc: New file. --- gcc/Makefile.in | 1 + gcc/passes.def | 2 + gcc/sccp.cc | 722 ++++++++++++++++++++++++++++++++++++++ gcc/tree-pass.h | 1 + gcc/tree-ssa-propagate.cc | 62 ++++ gcc/tree-ssa-propagate.h | 7 + 6 files changed, 795 insertions(+) create mode 100644 gcc/sccp.cc