From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <pheeck@sourceware.org>
Received: by sourceware.org (Postfix, from userid 7879)
	id 66A593857016; Mon,  5 Sep 2022 17:54:25 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 66A593857016
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1662400465;
	bh=b8YqYI4BTk9ENQt+qarqrK37RtKtCIiZoTW4Kggu/1g=;
	h=From:To:Subject:Date:From;
	b=Oap/tY2umDo13m3PWJVIjjoraB2Sgk59/5YzBWhkasV+Zf32QbtLKYSySVdgRpTuK
	 9RpQLEg/144DF1AuZ95eL5OIzXpM7CD5bU4CzjEEkm9L9sJqhgNyCcQ0QQsn4kIL/p
	 RlznuicSigitOzMGo7k/QrBm9f8W2U7q6zFAT/Jg=
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
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
X-Act-Checkin: gcc
X-Git-Author: Filip Kastl <filip.kastl@gmail.com>
X-Git-Refname: refs/users/pheeck/heads/sccp
X-Git-Oldrev: a4bde9752ad292dd7cf54a8edb8fe0b324e98bbc
X-Git-Newrev: 768444c46e52c181076428902bd6a3f1ad0a6997
Message-Id: <20220905175425.66A593857016@sourceware.org>
Date: Mon,  5 Sep 2022 17:54:25 +0000 (GMT)
List-Id: <gcc-cvs.sourceware.org>

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 ();
 }