From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 7879) id A42F73858C39; Sun, 24 Jul 2022 11:51:54 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A42F73858C39 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)] norecursive tarjan v2; seems to work X-Act-Checkin: gcc X-Git-Author: Filip Kastl X-Git-Refname: refs/users/pheeck/heads/sccp X-Git-Oldrev: 45740a202688b91096f439b2904f6022f5427c38 X-Git-Newrev: 47bb91efdb7673f9fba6efd7056cfe4c8eefc867 Message-Id: <20220724115154.A42F73858C39@sourceware.org> Date: Sun, 24 Jul 2022 11:51:54 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 24 Jul 2022 11:51:54 -0000 https://gcc.gnu.org/g:47bb91efdb7673f9fba6efd7056cfe4c8eefc867 commit 47bb91efdb7673f9fba6efd7056cfe4c8eefc867 Author: Filip Kastl Date: Sun Jul 24 13:50:46 2022 +0200 norecursive tarjan v2; seems to work Diff: --- gcc/sccp.cc | 113 ++++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 76 insertions(+), 37 deletions(-) diff --git a/gcc/sccp.cc b/gcc/sccp.cc index d33f0337e8c..c0bb98f9f79 100644 --- a/gcc/sccp.cc +++ b/gcc/sccp.cc @@ -58,24 +58,22 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-propagate.h" #include "gimple-fold.h" +enum vstate +{ + unvisited, + vopen, /* Open and closed vertices are on stack. */ + closed, + in_scc +}; + struct vertex { - bool visited; - bool is_on_stack; + vstate state; unsigned index; unsigned lowlink; gphi* stmt; }; -static unsigned -min (unsigned x, unsigned y) -{ - if (x < y) - return x; - else - return y; -} - static void tarjan_set_using (gimple* stmt) { @@ -159,8 +157,7 @@ tarjan_phis_to_vertices (vec phis) for (gphi *phi : phis) { vertex v; - v.visited = false; - v.is_on_stack = false; + v.state = unvisited; v.index = 0; v.lowlink = 0; v.stmt = phi; @@ -175,6 +172,7 @@ tarjan_compute_sccs (vec phis) { vec> sccs = vNULL; vec worklist = vNULL; + vec stack = vNULL; unsigned curr_index = 0; vec vs = tarjan_phis_to_vertices (phis); @@ -198,68 +196,109 @@ tarjan_compute_sccs (vec phis) while (!worklist.is_empty ()) { unsigned i = worklist.pop(); + gphi *phi = vs[i].stmt; - if (!vs[i].visited) + if (vs[i].state == unvisited) { - gphi *phi = vs[i].stmt; + vs[i].state = vopen; /* Assign index to this vertex. */ vs[i].index = curr_index; vs[i].lowlink = curr_index; curr_index++; - /* Put this vertex back on worklist. */ + /* Put vertex on stack and also on worklist to be closed later. */ + stack.safe_push (i); worklist.safe_push (i); - /* Put not yet visited children of vertex on worklist and update - lowlink of this vertex according to lowlinks of children on stack. */ + /* 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++) { - tree op_ssa = gimple_phi_arg_def (phi, i); + tree op_ssa = gimple_phi_arg_def (phi, j); gimple *op_stmt = SSA_NAME_DEF_STMT (op_ssa); /* Skip any operand that isn't a vertex we're using. */ if (!tarjan_is_using (op_stmt)) continue; - + gphi *op_phi = dyn_cast (op_stmt); if (op_phi == NULL) /* Only PHI functions have the 'using' flags set. */ gcc_unreachable (); unsigned op_i = tarjan_phinum (op_phi); - if (!vs[op_i].visited) + switch (vs[op_i].state) { + case unvisited: worklist.safe_push (op_i); - } - else if (vs[op_i].is_on_stack) - { - vs[i].lowlink = min (vs[i].lowlink, vs[op_i].index); + break; + case vopen: + case closed: + vs[i].lowlink = std::min (vs[i].lowlink, vs[op_i].index); + break; + case in_scc: + /* Ignore these edges. */ + break; } } } - else if (vs[i].is_on_stack) // TODO This check is redundant + else if (vs[i].state == vopen) { - vec scc = vNULL; - - /* Put vertex back on stack/worklist. */ - worklist.safe_push (i); + vs[i].state = closed; - /* Pop scc from stack/worklist. */ + /* Update lowlink of this vertex according to lowlinks of children + of this vertex (in terms of DFS tree). */ unsigned j; - do + for (j = 0; j < gimple_phi_num_args (phi); j++) { - j = worklist.pop(); - scc.safe_push (vs[j].stmt); - vs[j].is_on_stack = false; + tree op_ssa = gimple_phi_arg_def (phi, j); // TODO Same code + // twice (iterator?) + gimple *op_stmt = SSA_NAME_DEF_STMT (op_ssa); + + /* Skip any operand that isn't a vertex we're using. */ + if (!tarjan_is_using (op_stmt)) + continue; + + gphi *op_phi = dyn_cast (op_stmt); + if (op_phi == NULL) + /* Only PHI functions have the 'using' flags set. */ + gcc_unreachable (); + + unsigned op_i = tarjan_phinum (op_phi); + if (vs[op_i].state == closed) + { + vs[i].lowlink = std::min (vs[i].lowlink, vs[op_i].lowlink); + } } - while (vs[j].lowlink != vs[j].index); - sccs.safe_push (scc); + /* If this is the root of an scc, pop it from stack. */ + if (vs[i].lowlink == vs[i].index) + { + vec scc = vNULL; + + unsigned j; + do + { + j = stack.pop(); + scc.safe_push (vs[j].stmt); + vs[j].state = in_scc; + } + while (j != i); + + sccs.safe_push (scc); + } } } + // DEBUG + if (!stack.is_empty ()) + { + gcc_unreachable(); + } + /* Clear PHI functions' 'using' flags. */ for (vertex v : vs) {