public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/pheeck/heads/sccp)] rewrote tarjan_compute_sccs to remove duplicities
@ 2022-09-06 13:32 Filip Kastl
0 siblings, 0 replies; 2+ messages in thread
From: Filip Kastl @ 2022-09-06 13:32 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:472b5ddbf8c917c8d3c0f4a96311fd635264a1a3
commit 472b5ddbf8c917c8d3c0f4a96311fd635264a1a3
Author: Filip Kastl <filip.kastl@gmail.com>
Date: Tue Sep 6 15:32:08 2022 +0200
rewrote tarjan_compute_sccs to remove duplicities
Diff:
---
gcc/sccp.cc | 112 ++++++++++++++++++++++++++----------------------------------
1 file changed, 49 insertions(+), 63 deletions(-)
diff --git a/gcc/sccp.cc b/gcc/sccp.cc
index c7c9836e437..2df3547ed7b 100644
--- a/gcc/sccp.cc
+++ b/gcc/sccp.cc
@@ -191,8 +191,9 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
{
unsigned i = worklist.pop();
gphi *phi = vs[i].stmt;
+ vstate state = vs[i].state;
- if (vs[i].state == unvisited)
+ if (state == unvisited)
{
vs[i].state = vopen;
@@ -204,29 +205,37 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
/* 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;
+ }
- /* Put unvisited neighbors of vertex on worklist and update
- lowlink of this vertex according to indices of neighbors on
- stack. */
- unsigned j;
- for (j = 0; j < gimple_phi_num_args (phi); j++)
+ /* Iterate over neighbors of this vertex. */
+ unsigned j;
+ for (j = 0; j < gimple_phi_num_args (phi); j++)
+ {
+ tree op_var = gimple_phi_arg_def (phi, j);
+ 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. */
+ 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_phinum (op_phi);
+
+ if (state == unvisited)
{
- tree op_var = gimple_phi_arg_def (phi, j);
- 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. */
- 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_phinum (op_phi);
+ /* Put unvisited neighbors on worklist. Update lowlink of this
+ vertex according to indices of neighbors present on stack. */
switch (vs[op_i].state)
{
case unvisited:
@@ -241,55 +250,32 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
break;
}
}
- }
- else if (vs[i].state == vopen)
- {
- vs[i].state = closed;
-
- /* Update lowlink of this vertex according to lowlinks of children
- of this vertex (in terms of DFS tree). */
- unsigned j;
- for (j = 0; j < gimple_phi_num_args (phi); j++)
+ else if (state == vopen)
{
- tree op_var = gimple_phi_arg_def (phi, j); // TODO Same code
- // twice (iterator?)
- 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. */
- 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_phinum (op_phi);
+ /* Update lowlink of this vertex according to lowlinks of
+ children of this vertex (in terms of DFS tree). */
if (vs[op_i].state == closed)
{
vs[i].lowlink = std::min (vs[i].lowlink, vs[op_i].lowlink);
}
}
+ }
- /* If this is the root of an scc, pop it from stack. */
- if (vs[i].lowlink == vs[i].index)
- {
- vec<gphi *> scc = vNULL;
-
- unsigned j;
- do
- {
- j = stack.pop();
- scc.safe_push (vs[j].stmt);
- vs[j].state = in_scc;
- }
- while (j != i);
+ /* 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;
- sccs.safe_push (scc);
+ unsigned j;
+ do
+ {
+ j = stack.pop();
+ scc.safe_push (vs[j].stmt);
+ vs[j].state = in_scc;
}
+ while (j != i);
+
+ sccs.safe_push (scc);
}
}
@@ -310,7 +296,7 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
}
static void
-replace_scc_by_value (vec<gphi *> &scc, tree v)
+replace_scc_by_value (vec<gphi *> scc, tree v)
{
for (gphi *phi : scc)
{
^ permalink raw reply [flat|nested] 2+ messages in thread
* [gcc(refs/users/pheeck/heads/sccp)] rewrote tarjan_compute_sccs to remove duplicities
@ 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:2da5c4b15527c5bf7788ee53fae7d58187719f44
commit 2da5c4b15527c5bf7788ee53fae7d58187719f44
Author: Filip Kastl <filip.kastl@gmail.com>
Date: Tue Sep 6 15:32:08 2022 +0200
rewrote tarjan_compute_sccs to remove duplicities
Diff:
---
gcc/sccp.cc | 112 ++++++++++++++++++++++++++----------------------------------
1 file changed, 49 insertions(+), 63 deletions(-)
diff --git a/gcc/sccp.cc b/gcc/sccp.cc
index c7c9836e437..2df3547ed7b 100644
--- a/gcc/sccp.cc
+++ b/gcc/sccp.cc
@@ -191,8 +191,9 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
{
unsigned i = worklist.pop();
gphi *phi = vs[i].stmt;
+ vstate state = vs[i].state;
- if (vs[i].state == unvisited)
+ if (state == unvisited)
{
vs[i].state = vopen;
@@ -204,29 +205,37 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
/* 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;
+ }
- /* Put unvisited neighbors of vertex on worklist and update
- lowlink of this vertex according to indices of neighbors on
- stack. */
- unsigned j;
- for (j = 0; j < gimple_phi_num_args (phi); j++)
+ /* Iterate over neighbors of this vertex. */
+ unsigned j;
+ for (j = 0; j < gimple_phi_num_args (phi); j++)
+ {
+ tree op_var = gimple_phi_arg_def (phi, j);
+ 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. */
+ 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_phinum (op_phi);
+
+ if (state == unvisited)
{
- tree op_var = gimple_phi_arg_def (phi, j);
- 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. */
- 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_phinum (op_phi);
+ /* Put unvisited neighbors on worklist. Update lowlink of this
+ vertex according to indices of neighbors present on stack. */
switch (vs[op_i].state)
{
case unvisited:
@@ -241,55 +250,32 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
break;
}
}
- }
- else if (vs[i].state == vopen)
- {
- vs[i].state = closed;
-
- /* Update lowlink of this vertex according to lowlinks of children
- of this vertex (in terms of DFS tree). */
- unsigned j;
- for (j = 0; j < gimple_phi_num_args (phi); j++)
+ else if (state == vopen)
{
- tree op_var = gimple_phi_arg_def (phi, j); // TODO Same code
- // twice (iterator?)
- 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. */
- 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_phinum (op_phi);
+ /* Update lowlink of this vertex according to lowlinks of
+ children of this vertex (in terms of DFS tree). */
if (vs[op_i].state == closed)
{
vs[i].lowlink = std::min (vs[i].lowlink, vs[op_i].lowlink);
}
}
+ }
- /* If this is the root of an scc, pop it from stack. */
- if (vs[i].lowlink == vs[i].index)
- {
- vec<gphi *> scc = vNULL;
-
- unsigned j;
- do
- {
- j = stack.pop();
- scc.safe_push (vs[j].stmt);
- vs[j].state = in_scc;
- }
- while (j != i);
+ /* 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;
- sccs.safe_push (scc);
+ unsigned j;
+ do
+ {
+ j = stack.pop();
+ scc.safe_push (vs[j].stmt);
+ vs[j].state = in_scc;
}
+ while (j != i);
+
+ sccs.safe_push (scc);
}
}
@@ -310,7 +296,7 @@ tarjan_compute_sccs (auto_vec<gphi *> &phis)
}
static void
-replace_scc_by_value (vec<gphi *> &scc, tree v)
+replace_scc_by_value (vec<gphi *> scc, tree v)
{
for (gphi *phi : scc)
{
^ 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-06 13:32 [gcc(refs/users/pheeck/heads/sccp)] rewrote tarjan_compute_sccs to remove duplicities 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).