From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 7879) id 940283851425; Wed, 7 Sep 2022 18:25:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 940283851425 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1662575158; bh=oSCq7HXt/9bWQGef+Lb3CT2lQPyldxi1lKrNtFoV7ms=; h=From:To:Subject:Date:From; b=phYi2JAGj2xKPTaXDOjUcGBZYjovHgm69iAtA0q1PCOuekygZ886lwOrYgdnVkTmy vWI9+TDUPSEd8n6cfwloZiaMqK25tPLkHn+fDcA58sQMPLjHH+OomvJ48S5YvetCmB c2GqJnov/FRmKVIDwNSAa/KtLj3mozd70egQeFeM= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Filip Kastl To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/pheeck/heads/sccp)] added coments; will test with testsuite X-Act-Checkin: gcc X-Git-Author: Filip Kastl X-Git-Refname: refs/users/pheeck/heads/sccp X-Git-Oldrev: 92342e606688988a0ed117c0ed32c64e455f2e10 X-Git-Newrev: 55d28b73b1b8568ac250c8b4702239f61c4da26f Message-Id: <20220907182558.940283851425@sourceware.org> Date: Wed, 7 Sep 2022 18:25:58 +0000 (GMT) List-Id: https://gcc.gnu.org/g:55d28b73b1b8568ac250c8b4702239f61c4da26f commit 55d28b73b1b8568ac250c8b4702239f61c4da26f Author: Filip Kastl Date: Wed Sep 7 20:25:13 2022 +0200 added coments; will test with testsuite Diff: --- gcc/sccp.cc | 206 ++++++++++++++++++++++++++++++------------------------------ 1 file changed, 103 insertions(+), 103 deletions(-) diff --git a/gcc/sccp.cc b/gcc/sccp.cc index fe2d20cb8fa..0fe4aee41c6 100644 --- a/gcc/sccp.cc +++ b/gcc/sccp.cc @@ -1,5 +1,4 @@ -/* TODO Pass description - Strongly connected copy propagation pass +/* Strongly connected copy propagation pass for the GNU compiler. Copyright (C) 2022 Free Software Foundation, Inc. Contributed by Filip Kastl @@ -19,6 +18,25 @@ You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ +/* Strongly connected copy propagation (SCCP) + + References: + + Simple and Efficient Construction of Static Single Assignment Form, + Matthias Braun, et al., 2013, Section 3.2. + + SCCP uses algorithm presented by Braun et al. to seek out redundant sets of + PHI functions and remove them. Redundant set of PHIs is defined as a set + where for some value v each PHI in the set references either another PHI + from the set or v. + + Braun et al. prove that each redundant set contains a strongly connected + component (SCC) that is also redundant. The algorithm is based around + computing SCCs and then replacing all uses of variables from an SCC by + the appropriate value v. + + For computing SCCs, local implementation of Tarjan's algorithm is used. */ + #include "config.h" #include "system.h" #include "coretypes.h" @@ -28,24 +46,32 @@ along with GCC; see the file COPYING3. If not see #include "tree-pass.h" #include "ssa.h" #include "gimple-iterator.h" - #include "vec.h" #include "hash-set.h" +#include -// DEBUG includes +// DEBUG #include -#include "gimple-pretty-print.h" -#include "print-tree.h" -#include "dumpfile.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, /* Open and closed vertices are on stack. */ + vopen, closed, in_scc }; +/* Information about a vertex used by tarjan. */ + struct vertex { vstate state; @@ -54,6 +80,9 @@ struct vertex gphi* stmt; }; +/* 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) { @@ -72,6 +101,9 @@ tarjan_is_using (gimple* stmt) return gimple_plf (stmt, GF_PLF_1); } +/* Set 'phinum' of gimple PHI. Before computing SCCs, tarjan assigns PHIs + unique ids - phinums. */ + static void tarjan_set_phinum (gphi* phi, unsigned num) { @@ -84,64 +116,7 @@ tarjan_phinum (gphi* phi) return gimple_uid (phi); } -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); - } - } -} - -static void -finalize_sccp (void) -{ -} - -static void -debug_phis (void) // DEBUG -{ - std::cerr << "List of PHIs" << std::endl; - 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)) - { - gphi *phi = pi.phi (); - debug_gimple_stmt (phi); - } - } - std::cerr << std::endl; -} - -/* Return vector of all PHI functions from all basic blocks. */ - -static auto_vec -get_all_phis (void) -{ - auto_vec result; - - 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)) - { - gphi *phi = pi.phi (); - result.safe_push (phi); - } - } - - return result; -} +/* Create and initialize vertex struct for each given PHI. */ static auto_vec tarjan_phis_to_vertices (auto_vec &phis) @@ -160,12 +135,18 @@ tarjan_phis_to_vertices (auto_vec &phis) return result; } +/* Nonrecursive implementation of Tarjan's algorithm for computing strongly + connected components in a graph. PHIs are vertices. Edges lead from a PHI p + using another PHI q to the PHI being used (p -> q when q is operand of p). + + Considers only the given PHIs. Ignores other PHIs. */ + static auto_vec> tarjan_compute_sccs (auto_vec &phis) { auto_vec> sccs; - auto_vec worklist; - auto_vec stack; + auto_vec worklist; /* DFS stack. */ + auto_vec stack; /* Tarjan stack. */ unsigned curr_index = 0; auto_vec vs = tarjan_phis_to_vertices (phis); @@ -278,7 +259,6 @@ tarjan_compute_sccs (auto_vec &phis) } } - // DEBUG if (!stack.is_empty ()) { gcc_unreachable(); @@ -294,35 +274,22 @@ tarjan_compute_sccs (auto_vec &phis) return sccs; } +/* Modify all usages of PHIs in a given SCC to instead reference a given + variable. */ + static void replace_scc_by_value (vec scc, tree replace_by) { // DEBUG if (scc.length () >= 5) { - std::cerr << "Replacing scc of size " << scc.length () << std::endl; + std::cerr << "Replacing SCC of length " << scc.length () << std::endl; } for (gphi *phi : scc) { tree get_replaced = gimple_get_lhs (phi); - // DEBUG - /* - unsigned vnum_get_replaced = SSA_NAME_VERSION (get_replaced); - if (TREE_CODE (replace_by) == SSA_NAME) - { - unsigned vnum_replaced_by = SSA_NAME_VERSION (replace_by); - std::cerr << "Replacing " << vnum_get_replaced << " by " << - vnum_replaced_by << std::endl; - } - else - { - std::cerr << "Replacing " << vnum_get_replaced << " by something" - << " that isn't an SSA name" << std::endl; - } - */ - if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (get_replaced) && TREE_CODE (replace_by) == SSA_NAME) SSA_NAME_OCCURS_IN_ABNORMAL_PHI (replace_by) = 1; @@ -357,12 +324,6 @@ remove_zero_uses_phis () { /* Note that remove_phi_node() also frees SSA name. */ remove_phi_node (&pi, true); - - // DEBUG - /* - unsigned version = SSA_NAME_VERSION (ssa_name); - std::cerr << "Removed " << version << std::endl; - */ } else gsi_next (&pi); @@ -370,6 +331,9 @@ remove_zero_uses_phis () } } +/* Apply Braun et al.'s algorithm on a given set of PHIs. + Main function of this pass. */ + static void remove_redundant_phis (auto_vec &phis) { @@ -424,7 +388,7 @@ remove_redundant_phis (auto_vec &phis) if (outer_ops.elements () == 1) { /* Get the only operand in outer_ops. */ - tree outer_op; + tree outer_op = NULL_TREE; for (tree foo : outer_ops) { outer_op = foo; @@ -447,7 +411,7 @@ remove_redundant_phis (auto_vec &phis) } else { - gcc_unreachable (); // DEBUG + gcc_unreachable (); } scc.release (); @@ -456,7 +420,51 @@ remove_redundant_phis (auto_vec &phis) remove_zero_uses_phis (); } -/* TODO Pass description. */ +/* Return vector of all PHI functions from all basic blocks. */ + +static auto_vec +get_all_phis (void) +{ + auto_vec result; + + 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)) + { + gphi *phi = pi.phi (); + result.safe_push (phi); + } + } + + 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); + } + } +} + +/* Called before pass execution ends. */ + +static void +finalize_sccp (void) +{ +} namespace { @@ -488,19 +496,11 @@ public: unsigned pass_sccp::execute (function *) { - //debug_phis (); // DEBUG - init_sccp (); auto_vec phis = get_all_phis (); remove_redundant_phis (phis); finalize_sccp (); - /* - // DEBUG - std::cerr << std::endl; - debug_phis (); - */ - return 0; }