public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/pheeck/heads/sccp)] added coments; will test with testsuite
@ 2022-09-07 18:25 Filip Kastl
0 siblings, 0 replies; 2+ messages in thread
From: Filip Kastl @ 2022-09-07 18:25 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:55d28b73b1b8568ac250c8b4702239f61c4da26f
commit 55d28b73b1b8568ac250c8b4702239f61c4da26f
Author: Filip Kastl <filip.kastl@gmail.com>
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 <filip.kastl@gmail.com>
@@ -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
<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. */
+
#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 <algorithm>
-// DEBUG includes
+// DEBUG
#include <iostream>
-#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<gphi *>
-get_all_phis (void)
-{
- auto_vec<gphi *> 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<vertex>
tarjan_phis_to_vertices (auto_vec<gphi *> &phis)
@@ -160,12 +135,18 @@ tarjan_phis_to_vertices (auto_vec<gphi *> &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<vec<gphi *>>
tarjan_compute_sccs (auto_vec<gphi *> &phis)
{
auto_vec<vec<gphi *>> sccs;
- auto_vec<unsigned> worklist;
- auto_vec<unsigned> stack;
+ 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);
@@ -278,7 +259,6 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
}
}
- // DEBUG
if (!stack.is_empty ())
{
gcc_unreachable();
@@ -294,35 +274,22 @@ tarjan_compute_sccs (auto_vec<gphi *> &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<gphi *> 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<gphi *> &phis)
{
@@ -424,7 +388,7 @@ remove_redundant_phis (auto_vec<gphi *> &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<gphi *> &phis)
}
else
{
- gcc_unreachable (); // DEBUG
+ gcc_unreachable ();
}
scc.release ();
@@ -456,7 +420,51 @@ remove_redundant_phis (auto_vec<gphi *> &phis)
remove_zero_uses_phis ();
}
-/* TODO Pass description. */
+/* Return vector of all PHI functions from all basic blocks. */
+
+static auto_vec<gphi *>
+get_all_phis (void)
+{
+ auto_vec<gphi *> 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<gphi *> phis = get_all_phis ();
remove_redundant_phis (phis);
finalize_sccp ();
- /*
- // DEBUG
- std::cerr << std::endl;
- debug_phis ();
- */
-
return 0;
}
^ permalink raw reply [flat|nested] 2+ messages in thread
* [gcc(refs/users/pheeck/heads/sccp)] added coments; will test with testsuite
@ 2023-02-15 10:15 Filip Kastl
0 siblings, 0 replies; 2+ messages in thread
From: Filip Kastl @ 2023-02-15 10:15 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:05964a2701e07670eb72a5a2c2cdcdc5e33d6532
commit 05964a2701e07670eb72a5a2c2cdcdc5e33d6532
Author: Filip Kastl <filip.kastl@gmail.com>
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 <filip.kastl@gmail.com>
@@ -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
<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. */
+
#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 <algorithm>
-// DEBUG includes
+// DEBUG
#include <iostream>
-#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<gphi *>
-get_all_phis (void)
-{
- auto_vec<gphi *> 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<vertex>
tarjan_phis_to_vertices (auto_vec<gphi *> &phis)
@@ -160,12 +135,18 @@ tarjan_phis_to_vertices (auto_vec<gphi *> &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<vec<gphi *>>
tarjan_compute_sccs (auto_vec<gphi *> &phis)
{
auto_vec<vec<gphi *>> sccs;
- auto_vec<unsigned> worklist;
- auto_vec<unsigned> stack;
+ 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);
@@ -278,7 +259,6 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
}
}
- // DEBUG
if (!stack.is_empty ())
{
gcc_unreachable();
@@ -294,35 +274,22 @@ tarjan_compute_sccs (auto_vec<gphi *> &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<gphi *> 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<gphi *> &phis)
{
@@ -424,7 +388,7 @@ remove_redundant_phis (auto_vec<gphi *> &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<gphi *> &phis)
}
else
{
- gcc_unreachable (); // DEBUG
+ gcc_unreachable ();
}
scc.release ();
@@ -456,7 +420,51 @@ remove_redundant_phis (auto_vec<gphi *> &phis)
remove_zero_uses_phis ();
}
-/* TODO Pass description. */
+/* Return vector of all PHI functions from all basic blocks. */
+
+static auto_vec<gphi *>
+get_all_phis (void)
+{
+ auto_vec<gphi *> 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<gphi *> phis = get_all_phis ();
remove_redundant_phis (phis);
finalize_sccp ();
- /*
- // DEBUG
- std::cerr << std::endl;
- debug_phis ();
- */
-
return 0;
}
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2023-02-15 10:15 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-09-07 18:25 [gcc(refs/users/pheeck/heads/sccp)] added coments; will test with testsuite Filip Kastl
2023-02-15 10:15 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).