public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/pheeck/heads/sccp)] got rid of recursion in main algorithm
@ 2022-09-05 17:54 Filip Kastl
0 siblings, 0 replies; 2+ messages in thread
From: Filip Kastl @ 2022-09-05 17:54 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:768444c46e52c181076428902bd6a3f1ad0a6997
commit 768444c46e52c181076428902bd6a3f1ad0a6997
Author: Filip Kastl <filip.kastl@gmail.com>
Date: Mon Sep 5 19:54:16 2022 +0200
got rid of recursion in main algorithm
Diff:
---
gcc/sccp.cc | 108 ++++++++++++++++++++++++++++++------------------------------
1 file changed, 54 insertions(+), 54 deletions(-)
diff --git a/gcc/sccp.cc b/gcc/sccp.cc
index e29754fb37d..8574d424b66 100644
--- a/gcc/sccp.cc
+++ b/gcc/sccp.cc
@@ -380,82 +380,82 @@ remove_zero_uses_phis ()
}
}
-static void remove_redundant_phis (vec<gphi *> phis); // TODO Where to put
- // declaration?
-
static void
-process_scc (vec<gphi *> scc)
+remove_redundant_phis (vec<gphi *> phis)
{
- vec<gphi *> inner = vNULL;
- hash_set<tree> outer_ops;
+ vec<vec<gphi *>> worklist = vNULL;
+ worklist = tarjan_compute_sccs (phis);
- for (gphi *phi : scc)
+ while (!worklist.is_empty ())
{
- bool is_inner = true;
-
- unsigned i;
- for (i = 0; i < gimple_phi_num_args (phi); i++)
+ vec<gphi *> scc = worklist.pop ();
+
+ vec<gphi *> inner = vNULL;
+ hash_set<tree> outer_ops;
+
+ for (gphi *phi : scc)
{
- // Check if operand is a phi from scc
- bool op_in_scc = false;
- tree op = gimple_phi_arg_def (phi, i);
+ bool is_inner = true;
- if (TREE_CODE (op) == SSA_NAME)
+ unsigned i;
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
{
- gimple *op_stmt = SSA_NAME_DEF_STMT (op);
+ // Check if operand is a phi from current scc
+ bool op_in_scc = false;
+ tree op = gimple_phi_arg_def (phi, i);
- // TODO Efficiency
- for (gphi *foo : scc)
+ if (TREE_CODE (op) == SSA_NAME)
{
- if (op_stmt == foo)
- op_in_scc = true;
+ gimple *op_stmt = SSA_NAME_DEF_STMT (op);
+
+ // TODO Efficiency
+ for (gphi *foo : scc)
+ {
+ if (op_stmt == foo)
+ op_in_scc = true;
+ }
+ }
+
+ if (!op_in_scc)
+ {
+ outer_ops.add (op);
+ is_inner = false;
}
}
- if (!op_in_scc)
+ if (is_inner)
{
- outer_ops.add (op);
- is_inner = false;
+ inner.safe_push (phi);
}
}
- if (is_inner)
+ // TODO if == 0 -> unreachable?
+ if (outer_ops.elements () == 1)
{
- inner.safe_push (phi);
- }
- }
+ /* Get the only operand in outer_ops. */
+ tree outer_op;
+ for (tree foo : outer_ops)
+ {
+ outer_op = foo;
+ break;
+ }
- // TODO if == 0 -> unreachable?
- if (outer_ops.elements () == 1)
- {
- /* Get the only operand in outer_ops. */
- tree outer_op;
- for (tree foo : outer_ops)
+ /* Don't replace by abnormal phis! */
+ if (!(TREE_CODE (outer_op) == SSA_NAME &&
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (outer_op)))
+ replace_scc_by_value (scc, outer_op);
+ }
+ else if (outer_ops.elements () > 1)
{
- outer_op = foo;
- break;
+ /* Add inner sccs to worklist. */
+ vec<vec<gphi *>> inner_sccs = tarjan_compute_sccs (inner);
+ for (vec<gphi *> inner_scc : inner_sccs)
+ {
+ worklist.safe_push (inner_scc);
+ }
}
-
- /* Only replace by non-abnormal phi. */
- if (!(TREE_CODE (outer_op) == SSA_NAME &&
- SSA_NAME_OCCURS_IN_ABNORMAL_PHI (outer_op)))
- replace_scc_by_value (scc, outer_op);
- }
- else if (outer_ops.elements () > 1)
- {
- remove_redundant_phis (inner);
}
-}
-static void
-remove_redundant_phis (vec<gphi *> phis)
-{
- vec<vec<gphi *>> sccs = tarjan_compute_sccs (phis);
- sccs.reverse (); /* Reverse topological order -> normal topo. order. */
- for (vec<gphi *> scc : sccs)
- {
- process_scc (scc);
- }
remove_zero_uses_phis ();
}
^ permalink raw reply [flat|nested] 2+ messages in thread
* [gcc(refs/users/pheeck/heads/sccp)] got rid of recursion in main algorithm
@ 2023-02-15 10:14 Filip Kastl
0 siblings, 0 replies; 2+ messages in thread
From: Filip Kastl @ 2023-02-15 10:14 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:24ad163a226c2d525e71cef9b1bf7f3f7a6d8401
commit 24ad163a226c2d525e71cef9b1bf7f3f7a6d8401
Author: Filip Kastl <filip.kastl@gmail.com>
Date: Mon Sep 5 19:54:16 2022 +0200
got rid of recursion in main algorithm
Diff:
---
gcc/sccp.cc | 108 ++++++++++++++++++++++++++++++------------------------------
1 file changed, 54 insertions(+), 54 deletions(-)
diff --git a/gcc/sccp.cc b/gcc/sccp.cc
index e29754fb37d..8574d424b66 100644
--- a/gcc/sccp.cc
+++ b/gcc/sccp.cc
@@ -380,82 +380,82 @@ remove_zero_uses_phis ()
}
}
-static void remove_redundant_phis (vec<gphi *> phis); // TODO Where to put
- // declaration?
-
static void
-process_scc (vec<gphi *> scc)
+remove_redundant_phis (vec<gphi *> phis)
{
- vec<gphi *> inner = vNULL;
- hash_set<tree> outer_ops;
+ vec<vec<gphi *>> worklist = vNULL;
+ worklist = tarjan_compute_sccs (phis);
- for (gphi *phi : scc)
+ while (!worklist.is_empty ())
{
- bool is_inner = true;
-
- unsigned i;
- for (i = 0; i < gimple_phi_num_args (phi); i++)
+ vec<gphi *> scc = worklist.pop ();
+
+ vec<gphi *> inner = vNULL;
+ hash_set<tree> outer_ops;
+
+ for (gphi *phi : scc)
{
- // Check if operand is a phi from scc
- bool op_in_scc = false;
- tree op = gimple_phi_arg_def (phi, i);
+ bool is_inner = true;
- if (TREE_CODE (op) == SSA_NAME)
+ unsigned i;
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
{
- gimple *op_stmt = SSA_NAME_DEF_STMT (op);
+ // Check if operand is a phi from current scc
+ bool op_in_scc = false;
+ tree op = gimple_phi_arg_def (phi, i);
- // TODO Efficiency
- for (gphi *foo : scc)
+ if (TREE_CODE (op) == SSA_NAME)
{
- if (op_stmt == foo)
- op_in_scc = true;
+ gimple *op_stmt = SSA_NAME_DEF_STMT (op);
+
+ // TODO Efficiency
+ for (gphi *foo : scc)
+ {
+ if (op_stmt == foo)
+ op_in_scc = true;
+ }
+ }
+
+ if (!op_in_scc)
+ {
+ outer_ops.add (op);
+ is_inner = false;
}
}
- if (!op_in_scc)
+ if (is_inner)
{
- outer_ops.add (op);
- is_inner = false;
+ inner.safe_push (phi);
}
}
- if (is_inner)
+ // TODO if == 0 -> unreachable?
+ if (outer_ops.elements () == 1)
{
- inner.safe_push (phi);
- }
- }
+ /* Get the only operand in outer_ops. */
+ tree outer_op;
+ for (tree foo : outer_ops)
+ {
+ outer_op = foo;
+ break;
+ }
- // TODO if == 0 -> unreachable?
- if (outer_ops.elements () == 1)
- {
- /* Get the only operand in outer_ops. */
- tree outer_op;
- for (tree foo : outer_ops)
+ /* Don't replace by abnormal phis! */
+ if (!(TREE_CODE (outer_op) == SSA_NAME &&
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (outer_op)))
+ replace_scc_by_value (scc, outer_op);
+ }
+ else if (outer_ops.elements () > 1)
{
- outer_op = foo;
- break;
+ /* Add inner sccs to worklist. */
+ vec<vec<gphi *>> inner_sccs = tarjan_compute_sccs (inner);
+ for (vec<gphi *> inner_scc : inner_sccs)
+ {
+ worklist.safe_push (inner_scc);
+ }
}
-
- /* Only replace by non-abnormal phi. */
- if (!(TREE_CODE (outer_op) == SSA_NAME &&
- SSA_NAME_OCCURS_IN_ABNORMAL_PHI (outer_op)))
- replace_scc_by_value (scc, outer_op);
- }
- else if (outer_ops.elements () > 1)
- {
- remove_redundant_phis (inner);
}
-}
-static void
-remove_redundant_phis (vec<gphi *> phis)
-{
- vec<vec<gphi *>> sccs = tarjan_compute_sccs (phis);
- sccs.reverse (); /* Reverse topological order -> normal topo. order. */
- for (vec<gphi *> scc : sccs)
- {
- process_scc (scc);
- }
remove_zero_uses_phis ();
}
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2023-02-15 10:14 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-09-05 17:54 [gcc(refs/users/pheeck/heads/sccp)] got rid of recursion in main algorithm Filip Kastl
2023-02-15 10:14 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).