public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Filip Kastl <pheeck@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/pheeck/heads/sccp)] got rid of recursion in main algorithm Date: Mon, 5 Sep 2022 17:54:25 +0000 (GMT) [thread overview] Message-ID: <20220905175425.66A593857016@sourceware.org> (raw) 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 (); }
next reply other threads:[~2022-09-05 17:54 UTC|newest] Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top 2022-09-05 17:54 Filip Kastl [this message] 2023-02-15 10:14 Filip Kastl
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20220905175425.66A593857016@sourceware.org \ --to=pheeck@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
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).