From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <pheeck@sourceware.org>
Received: by sourceware.org (Postfix, from userid 7879)
	id C91213858409; Wed, 15 Feb 2023 10:13:09 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C91213858409
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1676455989;
	bh=IsyYWHJNnutaD/a8y48ZXah5zLSkXcIxpWqB0hORb/4=;
	h=From:To:Subject:Date:From;
	b=xb+rLWM+jqbl8HQsSeLHbfrn92DODaSZklTksMh4i+M6ToKcY5gTODJ28Bkfo/1SW
	 Fa8Al6jFcBKspew68YHlTUM9hXuHBNYIfqjFKlBkEIqy5cIk9aNx3dI2yNjP+rwH6V
	 yPIy55F6A5WnwbQh1/O0d6GdxLShZGDRtZCCtHsw=
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)] wip first version of tarjan's scc
 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: 883bdf26a9f6d430b548372b5740f9b3834b8b99
X-Git-Newrev: 4fb1427f2ed0ee6dcf6bf4c15e8c718572e1caaa
Message-Id: <20230215101309.C91213858409@sourceware.org>
Date: Wed, 15 Feb 2023 10:13:09 +0000 (GMT)
List-Id: <gcc-cvs.sourceware.org>

https://gcc.gnu.org/g:4fb1427f2ed0ee6dcf6bf4c15e8c718572e1caaa

commit 4fb1427f2ed0ee6dcf6bf4c15e8c718572e1caaa
Author: Filip Kastl <filip.kastl@gmail.com>
Date:   Fri Jul 1 17:51:42 2022 +0200

    wip first version of tarjan's scc algorithm

Diff:
---
 gcc/sccp.cc | 111 ++++++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 94 insertions(+), 17 deletions(-)

diff --git a/gcc/sccp.cc b/gcc/sccp.cc
index 42763a565e1..45cb8bfbfed 100644
--- a/gcc/sccp.cc
+++ b/gcc/sccp.cc
@@ -32,9 +32,11 @@ along with GCC; see the file COPYING3.  If not see
 
 #include <iostream>
 #include "gimple-pretty-print.h"
-#include "bitmap.h"
-#include "sbitmap.h"
+#include "vec.h"
+#include "libiberty.h"
+#include <algorithm>
 
+// Tohle jsem naimportoval kvuli num_ssa_names
 #include "backend.h"
 #include "cfghooks.h"
 #include "ssa.h"
@@ -54,20 +56,101 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-propagate.h"
 #include "gimple-fold.h"
 
-/* TODO Smaz.  */
-static sbitmap visited;
+struct vertex // Variables from Tarjan's SCC algorithm
+{
+  bool visited;
+  bool is_on_stack;
+  unsigned index;
+  unsigned lowlink;
+}
+
+static *vertices; // Each SSA name ~ vertex. Indexed by SSA version number.
+static vec<vec<unsigned>> tarjan_sccs; // Each SCC is a vector of version nums.
+static vec<unsigned> tarjan_stack;
+static unsigned tarjan_index = 0;
 
 /* Initialize structures used for sccp.  */
 
 static void
 init_sccp (void)
 {
-  visited = sbitmap_alloc (num_ssa_names);
+  vertices = XCNEWVEC (vertex, num_ssa_names);
+}
+
+/* TODO */
+
+static void
+tarjan_assign_index (unsigned vnum)
+{
+  vertices[vnum].index = tarjan_index;
+  vertices[vnum].lowlink = tarjan_index;
+  tarjan_index++;
+}
+
+/* TODO */
+
+static void
+tarjan_update_lowlink (unsigned vnum, unsigned new_lowlink)
+{
+  unsigned old_lowlink = vertices[vnum].lowlink.
+  vertices[vnum].lowlink = min (old_lowlink, new_lowlink);
 }
 
+/* Tarjan SCC algorithm subprocedure.  */
+
+static void
+tarjan_strongconnect (unsigned vnum)
+{
+  tarjan_assign_index (vnum);
+  vec_safe_push (tarjan_stack, vnum);
+  vertices[vnum].is_on_stack = true;
+
+  for (neigh_vnum) // TODO Iterate over neighbours (arguments of PHI)
+    {
+      if (!vertices[neigh_vnum].visited)
+	{
+	  tarjan_strongconnect (neigh_vnum);
+	  tarjan_update_lowlink (vnum, vertices[neigh_vnum].lowlink);
+	}
+      else if (vertices[neigh_vnum].is_on_stack)
+	{
+	  tarjan_update_lowlink (vnum, vertices[neigh_vnum].index);
+	}
+    }
+
+  if (vertices[vnum].lowlink == vertices[vnum].index)
+    {
+      // TODO
+    }
+}
+
+/* Runs Tarjan's SCC algorithm on PHIs. Fills out tarjan_sccs.  */
+
+static void
+tarjan_compute_sccs (void)
+{
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      gphi_iterator pi;
+
+      for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
+	{
+	  gphi *phi = pi.phi ();
+	  // TODO Filtrovat stmts jako v copyprop
+	  int ver = SSA_NAME_VERSION (phi);
+	  if (!vertices[ver].visited)
+	    {
+	      tarjan_strongconnect (ver);
+	    }
+	}
+    }
+}
+
+
 /* TODO Smaz.  */
 
-static void debug_reachable_phi(gimple* phi)
+static void
+debug_reachable_phi(gimple* phi)
 {
   debug_gimple_stmt (phi);
 
@@ -120,22 +203,16 @@ unsigned
 pass_sccp::execute (function *)
 {
   basic_block bb;
-
   init_sccp ();
+  vec<vec<unsigned>> *sccs = tarjan_compute_sccs ();
 
-  FOR_EACH_BB_FN (bb, cfun)
+  for (vec<unsigned> scc : *sccs)
     {
-      gphi_iterator pi;
-
-      for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
+      for (unsigned phi : scc)
 	{
-	  gphi *phi = pi.phi ();
-	  // TODO Filtrovat stmts jako v copyprop
-	  // Ale to asi budu muset filtrovat stmts, ne phi
-	  bitmap_clear (visited);
-	  debug_reachable_phi (phi);
-	  std::cerr << std::endl; // Blank line
+	  std::cerr << phi << std::endl;
 	}
+      std::cerr << std::endl;
     }
 
   return 0; // TODO Co tu mam vracet?