From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 7879) id 35A623858430; Wed, 15 Feb 2023 10:14:41 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 35A623858430 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1676456081; bh=nA/ex4oBdk6qb+eQeh69WMN2C7WkkxnQNyRrkK6vqzE=; h=From:To:Subject:Date:From; b=Ju4PybsRaRQ+Btqz7d0r3RrHxuoixCssohVeEZDGyW3SKenvvIIkiAEQQ97oBOM+u X7R3+BFK1f6jQJe4S/FEAl9u53xjEBG8PgF9LL7jwpMatbVddu51P/m/uCo2eekwUK J1rmiz6B1DXgWznfX81I/20aZOyQXqM7kVK2lnG4= 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)] rewrote tarjan_compute_sccs to remove duplicities X-Act-Checkin: gcc X-Git-Author: Filip Kastl X-Git-Refname: refs/users/pheeck/heads/sccp X-Git-Oldrev: d8ccc7ccf06c1777b01c22e3490b3b047eee135d X-Git-Newrev: 2da5c4b15527c5bf7788ee53fae7d58187719f44 Message-Id: <20230215101441.35A623858430@sourceware.org> Date: Wed, 15 Feb 2023 10:14:41 +0000 (GMT) List-Id: https://gcc.gnu.org/g:2da5c4b15527c5bf7788ee53fae7d58187719f44 commit 2da5c4b15527c5bf7788ee53fae7d58187719f44 Author: Filip Kastl 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 &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 &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 (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 (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 &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 (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 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 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 &phis) } static void -replace_scc_by_value (vec &scc, tree v) +replace_scc_by_value (vec scc, tree v) { for (gphi *phi : scc) {