public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/pheeck/heads/sccp)] rewritten sccp to consider copy stmts
@ 2023-02-15 10:15 Filip Kastl
0 siblings, 0 replies; only message in thread
From: Filip Kastl @ 2023-02-15 10:15 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:8ec8253c12226880e699aa4c350fc9cffe7b64d0
commit 8ec8253c12226880e699aa4c350fc9cffe7b64d0
Author: Filip Kastl <filip.kastl@gmail.com>
Date: Sat Nov 26 12:16:08 2022 +0100
rewritten sccp to consider copy stmts
Diff:
---
gcc/.gitignore | 1 +
gcc/sccp.cc | 267 +++++++++++++++++++++++++++++++--------------------------
2 files changed, 145 insertions(+), 123 deletions(-)
diff --git a/gcc/.gitignore b/gcc/.gitignore
new file mode 100644
index 00000000000..6e92f57d464
--- /dev/null
+++ b/gcc/.gitignore
@@ -0,0 +1 @@
+tags
diff --git a/gcc/sccp.cc b/gcc/sccp.cc
index 0fe4aee41c6..0f2f5cd61a3 100644
--- a/gcc/sccp.cc
+++ b/gcc/sccp.cc
@@ -18,24 +18,7 @@ You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
-/* 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. */
+// TODO: Description
#include "config.h"
#include "system.h"
@@ -49,9 +32,11 @@ along with GCC; see the file COPYING3. If not see
#include "vec.h"
#include "hash-set.h"
#include <algorithm>
+#include "ssa-iterators.h"
// DEBUG
#include <iostream>
+#include "gimple-pretty-print.h"
/* State of vertex during tarjan computation.
@@ -77,9 +62,40 @@ struct vertex
vstate state;
unsigned index;
unsigned lowlink;
- gphi* stmt;
+ gimple* stmt;
};
+static bool
+may_generate_useful_copy (gimple *stmt)
+{
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
+ // return true; // TODO
+
+ 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; // TODO Mozna tu nemusi byt
+
+ /* 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 the assignment is from a constant it generates a useful copy. */
+ if (gimple_assign_single_p (stmt)
+ && 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);
+ return (rhs && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs));
+}
+
/* Set 'using' flag of gimple statement to true.
If the flag isn't set, tarjan will ignore the statement. */
@@ -89,46 +105,52 @@ 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 'phinum' of gimple PHI. Before computing SCCs, tarjan assigns PHIs
- unique ids - phinums. */
+/* Set 'vxnum' (vertex number) of statement. Before computing SCCs, tarjan
+ assigns unique vxnums to statements that it will use. */
static void
-tarjan_set_phinum (gphi* phi, unsigned num)
+tarjan_set_vxnum (gimple* stmt, unsigned num)
{
- gimple_set_uid (phi, num);
+ gimple_set_uid (stmt, num);
}
+/* Return 'vxnum' (vertex number) of statement. */
+
static unsigned
-tarjan_phinum (gphi* phi)
+tarjan_vxnum (gimple* stmt)
{
- return gimple_uid (phi);
+ return gimple_uid (stmt);
}
-/* Create and initialize vertex struct for each given PHI. */
+/* Create and initialize vertex struct for each given statement. */
static auto_vec<vertex>
-tarjan_phis_to_vertices (auto_vec<gphi *> &phis)
+tarjan_stmts_to_vertices (auto_vec<gimple *> &stmts)
{
auto_vec<vertex> result;
- for (gphi *phi : phis)
+ for (gimple *stmt : stmts)
{
vertex v;
v.state = unvisited;
v.index = 0;
v.lowlink = 0;
- v.stmt = phi;
+ v.stmt = stmt;
result.safe_push (v);
}
@@ -136,28 +158,29 @@ tarjan_phis_to_vertices (auto_vec<gphi *> &phis)
}
/* 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).
+ 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 given PHIs. Ignores other PHIs. */
+ Considers only the subgraph induced by given statements. */
-static auto_vec<vec<gphi *>>
-tarjan_compute_sccs (auto_vec<gphi *> &phis)
+static auto_vec<vec<gimple *>>
+tarjan_compute_sccs (auto_vec<gimple *> ©_stmts)
{
- auto_vec<vec<gphi *>> sccs;
+ 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_phis_to_vertices (phis);
+ auto_vec<vertex> vs = tarjan_stmts_to_vertices (copy_stmts);
- /* Assign phinums and set PHI functions' 'using' flag. */
+ /* Mark the subgraph induced by 'copy_stmts' and index it by vxnums. */
unsigned i;
for (i = 0; i < vs.length (); i++)
{
- gphi *phi = vs[i].stmt;
- tarjan_set_using (phi);
- tarjan_set_phinum (phi, i);
+ gimple *stmt = vs[i].stmt;
+ tarjan_set_using (stmt);
+ tarjan_set_vxnum (stmt, i);
}
/* Put all vertices on worklist. */
@@ -170,7 +193,7 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
while (!worklist.is_empty ())
{
unsigned i = worklist.pop();
- gphi *phi = vs[i].stmt;
+ gimple *stmt = vs[i].stmt;
vstate state = vs[i].state;
if (state == unvisited)
@@ -192,25 +215,27 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
}
/* Iterate over neighbors of this vertex. */
- unsigned j;
- for (j = 0; j < gimple_phi_num_args (phi); j++)
+ ssa_op_iter iter;
+ use_operand_p use_p;
+ std::cerr << gimple_code (stmt) << std::endl; // DEBUG
+ std::cerr << "Hi" << std::endl;
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
{
- tree op_var = gimple_phi_arg_def (phi, j);
+ tree op_var = USE_FROM_PTR (use_p);
+
if (TREE_CODE (op_var) != SSA_NAME)
continue; /* Skip any operand that isn't an SSA name. */
gimple *op_stmt = SSA_NAME_DEF_STMT (op_var);
- /* Skip any operand that isn't a vertex we're using. */
+ /* Skip operands not from the induced subgraph. */
if (!tarjan_is_using (op_stmt))
continue;
-
- gphi *op_phi = dyn_cast<gphi *> (op_stmt);
- if (op_phi == NULL)
- /* Only PHI functions have the 'using' flags set. */
- gcc_unreachable ();
+ unsigned op_i = tarjan_vxnum (op_stmt);
- unsigned op_i = tarjan_phinum (op_phi);
+ /* This should hold if only copy stmts were given to this
+ function. */
+ gcc_checking_assert (may_generate_useful_copy (op_stmt));
if (state == unvisited)
{
@@ -244,7 +269,7 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
/* If we just closed a root vertex of an scc, pop scc from stack. */
if (state == vopen && vs[i].lowlink == vs[i].index)
{
- vec<gphi *> scc = vNULL;
+ vec<gimple *> scc = vNULL;
unsigned j;
do
@@ -264,11 +289,11 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
gcc_unreachable();
}
- /* Clear PHI functions' 'using' flags. */
+ /* Clear copy stmts' 'using' flags. */
for (vertex v : vs)
{
- gphi *phi = v.stmt;
- tarjan_clear_using (phi);
+ gimple *s = v.stmt;
+ tarjan_clear_using (s);
}
return sccs;
@@ -278,23 +303,23 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
variable. */
static void
-replace_scc_by_value (vec<gphi *> scc, tree replace_by)
+replace_scc_by_value (vec<gimple *> scc, tree replace_by)
{
// DEBUG
- if (scc.length () >= 5)
+ if (scc.length () >= 1)
{
std::cerr << "Replacing SCC of length " << scc.length () << std::endl;
}
- for (gphi *phi : scc)
+ for (gimple *stmt : scc)
{
- tree get_replaced = gimple_get_lhs (phi);
+ tree get_replaced = gimple_get_lhs (stmt);
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (get_replaced)
&& TREE_CODE (replace_by) == SSA_NAME)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (replace_by) = 1;
- /* Replace each occurence of PHI by value replace_by. */
+ /* Replace each occurence of copy stmts LHS by value 'replace_by'. */
use_operand_p use_p;
imm_use_iterator iter;
gimple *use_stmt;
@@ -307,95 +332,68 @@ replace_scc_by_value (vec<gphi *> scc, tree replace_by)
}
}
-/* 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);
- }
- }
-}
-
-/* Apply Braun et al.'s algorithm on a given set of PHIs.
+/* 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
-remove_redundant_phis (auto_vec<gphi *> &phis)
+sccp_propagate (auto_vec<gimple *> ©_stmts)
{
- auto_vec<vec<gphi *>> worklist;
- worklist = tarjan_compute_sccs (phis);
+ auto_vec<vec<gimple *>> worklist;
+ worklist = tarjan_compute_sccs (copy_stmts);
while (!worklist.is_empty ())
{
- vec<gphi *> scc = worklist.pop ();
+ vec<gimple *> scc = worklist.pop ();
- auto_vec<gphi *> inner;
+ 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<gphi *> scc_set;
- for (gphi *phi : scc)
+ hash_set<gimple *> scc_set;
+ for (gimple *stmt : scc)
{
- scc_set.add (phi);
+ scc_set.add (stmt);
}
- for (gphi *phi : scc)
+ for (gimple *stmt : scc)
{
bool is_inner = true;
- unsigned i;
- for (i = 0; i < gimple_phi_num_args (phi); i++)
+ ssa_op_iter iter;
+ use_operand_p use_p;
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
{
+ tree op_var = USE_FROM_PTR (use_p);
bool op_in_scc = false;
- tree op = gimple_phi_arg_def (phi, i);
- if (TREE_CODE (op) == SSA_NAME)
+ if (TREE_CODE (op_var) == SSA_NAME)
{
- gimple *op_stmt = SSA_NAME_DEF_STMT (op);
- if (gimple_code (op_stmt) == GIMPLE_PHI &&
- scc_set.contains (as_a<gphi *> (op_stmt)))
+ gimple *op_stmt = SSA_NAME_DEF_STMT (op_var);
+ if (scc_set.contains (op_stmt))
op_in_scc = true;
}
if (!op_in_scc)
{
- outer_ops.add (op);
+ outer_ops.add (op_var);
is_inner = false;
}
}
if (is_inner)
{
- inner.safe_push (phi);
+ inner.safe_push (stmt);
}
}
if (outer_ops.elements () == 1)
{
- /* Get the only operand in outer_ops. */
- tree outer_op = NULL_TREE;
- for (tree foo : outer_ops)
- {
- outer_op = foo;
- break;
- }
+ /* The only operand in outer_ops. */
+ tree outer_op = last_outer_op;
- /* Don't replace by abnormal phis! */
+ /* Now replace (Unless replacing by abnormal PHI!) */
if (!(TREE_CODE (outer_op) == SSA_NAME &&
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (outer_op)))
replace_scc_by_value (scc, outer_op);
@@ -403,8 +401,8 @@ remove_redundant_phis (auto_vec<gphi *> &phis)
else if (outer_ops.elements () > 1)
{
/* Add inner sccs to worklist. */
- auto_vec<vec<gphi *>> inner_sccs = tarjan_compute_sccs (inner);
- for (vec<gphi *> inner_scc : inner_sccs)
+ auto_vec<vec<gimple *>> inner_sccs = tarjan_compute_sccs (inner);
+ for (vec<gimple *> inner_scc : inner_sccs)
{
worklist.safe_push (inner_scc);
}
@@ -416,25 +414,48 @@ remove_redundant_phis (auto_vec<gphi *> &phis)
scc.release ();
}
-
- remove_zero_uses_phis ();
}
-/* Return vector of all PHI functions from all basic blocks. */
+/* Return all statements in cfun that may be useful. */
-static auto_vec<gphi *>
-get_all_phis (void)
+static auto_vec<gimple *>
+get_all_may_generate_useful_copy (void)
{
- auto_vec<gphi *> result;
+ 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);
+
+ /*
+ std::cerr << GIMPLE_PHI << std::endl; // DEBUG
+ std::cerr << GIMPLE_ASSIGN << std::endl;
+ debug_gimple_stmt (s);
+ std::cerr << gimple_code (s) << std::endl << std::endl;
+ */
+
+ if (may_generate_useful_copy (s))
+ result.safe_push (s);
+ }
+
gphi_iterator pi;
for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
{
- gphi *phi = pi.phi ();
- result.safe_push (phi);
+ gimple *s = pi.phi ();
+
+ /*
+ std::cerr << GIMPLE_PHI << std::endl; // DEBUG
+ std::cerr << GIMPLE_ASSIGN << std::endl;
+ debug_gimple_stmt (s);
+ std::cerr << gimple_code (s) << std::endl << std::endl;
+ */
+
+ if (may_generate_useful_copy (s))
+ result.safe_push (s);
}
}
@@ -497,8 +518,8 @@ unsigned
pass_sccp::execute (function *)
{
init_sccp ();
- auto_vec<gphi *> phis = get_all_phis ();
- remove_redundant_phis (phis);
+ auto_vec<gimple *> stmts = get_all_may_generate_useful_copy ();
+ sccp_propagate (stmts);
finalize_sccp ();
return 0;
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2023-02-15 10:15 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-02-15 10:15 [gcc(refs/users/pheeck/heads/sccp)] rewritten sccp to consider copy stmts Filip Kastl
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).