[gcc(refs/users/pheeck/heads/sccp)] trying to find testcases for algorithm

[gcc(refs/users/pheeck/heads/sccp)] trying to find testcases for algorithm

[Filip Kastl]

https://gcc.gnu.org/g:8938f59405770ecdde927e761053d9236aa78a25

commit 8938f59405770ecdde927e761053d9236aa78a25
Author: Filip Kastl <filip.kastl@gmail.com>
Date:   Wed Aug 3 22:15:54 2022 +0200

    trying to find testcases for algorithm

Diff:
---
 gcc/sccp.cc                       | 31 +++++++++++++++++++++++++++----
 rocnikovy-projekt-specifikace.txt | 22 ++++++++++++++++++++++
 2 files changed, 49 insertions(+), 4 deletions(-)

diff --git a/gcc/sccp.cc b/gcc/sccp.cc
index c0bb98f9f79..529307dbe27 100644
--- a/gcc/sccp.cc
+++ b/gcc/sccp.cc
@@ -369,13 +369,17 @@ process_scc (vec<gphi *> scc)
   if (outer_ops.length () == 1)
     replace_scc_by_value (scc, outer_ops.pop());
   else if (outer_ops.length () > 1)
-    remove_redundant_phis (inner);
+    {
+      std::cerr << inner.length () << std::endl;
+      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);
@@ -407,7 +411,7 @@ public:
   {}
 
   /* opt_pass methods: */
-  virtual bool gate (function *) { return true; } // TODO
+  virtual bool gate (function *) { return true; }
   virtual unsigned int execute (function *);
 }; // class pass_sccp
 
@@ -415,8 +419,26 @@ unsigned
 pass_sccp::execute (function *)
 {
   init_sccp ();
-  vec<vec<gphi *>> sccs = tarjan_compute_sccs (get_all_normal_phis ());
+  remove_redundant_phis (get_all_normal_phis ());
+
+  /*
+  // DEBUG
+  basic_block bb;
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      debug_bb (bb);
+      gphi_iterator pi;
+      std::cerr << "PHI LIST" << std::endl;
+      for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
+	{
+	  gphi *phi = pi.phi ();
+	  debug_gimple_stmt (phi);
+	}
+      std::cerr << std::endl << std::endl;
+    }
+  */
 
+  /*
   std::cerr << "function:" << std::endl;
   for (vec<gphi *> scc : sccs)
     {
@@ -430,10 +452,11 @@ pass_sccp::execute (function *)
       std::cerr << std::endl;
     }
   std::cerr << std::endl;
+  */
 
   finalize_sccp ();
 
-  return 0; // TODO What should I return?
+  return 0;
 }
 
 } // anon namespace
diff --git a/rocnikovy-projekt-specifikace.txt b/rocnikovy-projekt-specifikace.txt
new file mode 100644
index 00000000000..1e488a3736e
--- /dev/null
+++ b/rocnikovy-projekt-specifikace.txt
@@ -0,0 +1,22 @@
+Název: Optimalizace silných komponent phi funkcí pro překladač GCC
+
+Účelem je vytvořit patch pro komunitou vyvíjený překladač GCC. Patch bude
+obsahovat implementaci algoritmu z sekce 3.2 článku Simple and Efficient
+Construction of Static Single Assignment Form[1]. Cílem algoritmu je vyhledávat
+a redukovat phi funkce odkazující se na sebe navzájem, tedy tvořící silné
+komponenty. Algoritmus se bude nacházet v novém optimalizačním průchodu.
+
+Ani GCC ani konkurenční LLVM v tuto chvíli neobsahuje v produkční verzi
+implementaci algoritmu. Je možné, že průchod FRE (Forward Elimination) v GCC
+také umí redukovat silné komponenty, ale nový průchod bude rychlejší a tedy
+použitelný ve více fázích optimalizace. Nový průchod by také mohl nahradit
+starý Copy Propagation průchod.
+
+OS: Primárně Linux
+Jazyk: C++
+
+[1] Braun, M., Buchwald, S., Hack, S., Leißa, R., Mallon, C., Zwinkau, A.
+(2013). Simple and Efficient Construction of Static Single Assignment Form. In:
+Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC 2013. Lecture Notes
+in Computer Science, vol 7791. Springer, Berlin, Heidelberg.
+https://doi.org/10.1007/978-3-642-37051-9_6

[gcc(refs/users/pheeck/heads/sccp)] trying to find testcases for algorithm

[Filip Kastl]

https://gcc.gnu.org/g:77e3b24be2006fe2008c71e9c78a2444c3a59a0f

commit 77e3b24be2006fe2008c71e9c78a2444c3a59a0f
Author: Filip Kastl <filip.kastl@gmail.com>
Date:   Wed Aug 3 22:15:54 2022 +0200

    trying to find testcases for algorithm

Diff:
---
 gcc/sccp.cc                       | 31 +++++++++++++++++++++++++++----
 rocnikovy-projekt-specifikace.txt | 22 ++++++++++++++++++++++
 2 files changed, 49 insertions(+), 4 deletions(-)

diff --git a/gcc/sccp.cc b/gcc/sccp.cc
index c0bb98f9f79..529307dbe27 100644
--- a/gcc/sccp.cc
+++ b/gcc/sccp.cc
@@ -369,13 +369,17 @@ process_scc (vec<gphi *> scc)
   if (outer_ops.length () == 1)
     replace_scc_by_value (scc, outer_ops.pop());
   else if (outer_ops.length () > 1)
-    remove_redundant_phis (inner);
+    {
+      std::cerr << inner.length () << std::endl;
+      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);
@@ -407,7 +411,7 @@ public:
   {}
 
   /* opt_pass methods: */
-  virtual bool gate (function *) { return true; } // TODO
+  virtual bool gate (function *) { return true; }
   virtual unsigned int execute (function *);
 }; // class pass_sccp
 
@@ -415,8 +419,26 @@ unsigned
 pass_sccp::execute (function *)
 {
   init_sccp ();
-  vec<vec<gphi *>> sccs = tarjan_compute_sccs (get_all_normal_phis ());
+  remove_redundant_phis (get_all_normal_phis ());
+
+  /*
+  // DEBUG
+  basic_block bb;
+  FOR_EACH_BB_FN (bb, cfun)
+    {
+      debug_bb (bb);
+      gphi_iterator pi;
+      std::cerr << "PHI LIST" << std::endl;
+      for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
+	{
+	  gphi *phi = pi.phi ();
+	  debug_gimple_stmt (phi);
+	}
+      std::cerr << std::endl << std::endl;
+    }
+  */
 
+  /*
   std::cerr << "function:" << std::endl;
   for (vec<gphi *> scc : sccs)
     {
@@ -430,10 +452,11 @@ pass_sccp::execute (function *)
       std::cerr << std::endl;
     }
   std::cerr << std::endl;
+  */
 
   finalize_sccp ();
 
-  return 0; // TODO What should I return?
+  return 0;
 }
 
 } // anon namespace
diff --git a/rocnikovy-projekt-specifikace.txt b/rocnikovy-projekt-specifikace.txt
new file mode 100644
index 00000000000..1e488a3736e
--- /dev/null
+++ b/rocnikovy-projekt-specifikace.txt
@@ -0,0 +1,22 @@
+Název: Optimalizace silných komponent phi funkcí pro překladač GCC
+
+Účelem je vytvořit patch pro komunitou vyvíjený překladač GCC. Patch bude
+obsahovat implementaci algoritmu z sekce 3.2 článku Simple and Efficient
+Construction of Static Single Assignment Form[1]. Cílem algoritmu je vyhledávat
+a redukovat phi funkce odkazující se na sebe navzájem, tedy tvořící silné
+komponenty. Algoritmus se bude nacházet v novém optimalizačním průchodu.
+
+Ani GCC ani konkurenční LLVM v tuto chvíli neobsahuje v produkční verzi
+implementaci algoritmu. Je možné, že průchod FRE (Forward Elimination) v GCC
+také umí redukovat silné komponenty, ale nový průchod bude rychlejší a tedy
+použitelný ve více fázích optimalizace. Nový průchod by také mohl nahradit
+starý Copy Propagation průchod.
+
+OS: Primárně Linux
+Jazyk: C++
+
+[1] Braun, M., Buchwald, S., Hack, S., Leißa, R., Mallon, C., Zwinkau, A.
+(2013). Simple and Efficient Construction of Static Single Assignment Form. In:
+Jhala, R., De Bosschere, K. (eds) Compiler Construction. CC 2013. Lecture Notes
+in Computer Science, vol 7791. Springer, Berlin, Heidelberg.
+https://doi.org/10.1007/978-3-642-37051-9_6