[PATCH GCC]Rename and make remove_dead_inserted_code a simple dce interface

[PATCH GCC]Rename and make remove_dead_inserted_code a simple dce interface

[Bin Cheng]

[-- Attachment #1: Type: text/plain, Size: 760 bytes --]

Hi,
This patch renames remove_dead_inserted_code to simple_dce_from_worklist, moves it to tree-ssa-dce.c
and makes it a simple public DCE interface.  Bootstrap and test along with loop interchange.  It's required
for interchange pass.  Is it OK?
BTW, I will push this along with interchange to branch: gcc.gnu.org/svn/gcc/branches/gimple-linterchange.

Thanks,
bin
2017-11-27  Bin Cheng  <bin.cheng@arm.com>

	* tree-ssa-dce.c (simple_dce_from_worklist): Move and rename from
	tree-ssa-pre.c::remove_dead_inserted_code.
	* tree-ssa-dce.h: New file.
	* tree-ssa-pre.c (tree-ssa-dce.h): Include new header file.
	(remove_dead_inserted_code): Move and rename to function
	tree-ssa-dce.c::simple_dce_from_worklist.
	(pass_pre::execute): Update use.

[-- Attachment #2: simple-dce-interface-20171125.txt --]
[-- Type: text/plain, Size: 5563 bytes --]

diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index a5f0edf..227e55d 100644
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -1723,3 +1723,56 @@ make_pass_cd_dce (gcc::context *ctxt)
 {
   return new pass_cd_dce (ctxt);
 }
+
+
+/* A cheap DCE interface starting from a seed set of possibly dead stmts.  */
+
+void
+simple_dce_from_worklist (bitmap seeds)
+{
+  /* ???  Re-use seeds as worklist not only as initial set.  This may end up
+     removing more code as well.  If we keep seeds unchanged we could restrict
+     new worklist elements to members of seed.  */
+  bitmap worklist = seeds;
+  while (! bitmap_empty_p (worklist))
+    {
+      /* Pop item.  */
+      unsigned i = bitmap_first_set_bit (worklist);
+      bitmap_clear_bit (worklist, i);
+
+      tree def = ssa_name (i);
+      /* Removed by somebody else or still in use.  */
+      if (! def || ! has_zero_uses (def))
+	continue;
+
+      gimple *t = SSA_NAME_DEF_STMT (def);
+      if (gimple_has_side_effects (t))
+	continue;
+
+      /* Add uses to the worklist.  */
+      ssa_op_iter iter;
+      use_operand_p use_p;
+      FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
+	{
+	  tree use = USE_FROM_PTR (use_p);
+	  if (TREE_CODE (use) == SSA_NAME
+	      && ! SSA_NAME_IS_DEFAULT_DEF (use))
+	    bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
+	}
+
+      /* Remove stmt.  */
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Removing dead stmt:");
+	  print_gimple_stmt (dump_file, t, 0);
+	}
+      gimple_stmt_iterator gsi = gsi_for_stmt (t);
+      if (gimple_code (t) == GIMPLE_PHI)
+	remove_phi_node (&gsi, true);
+      else
+	{
+	  gsi_remove (&gsi, true);
+	  release_defs (t);
+	}
+    }
+}
diff --git a/gcc/tree-ssa-dce.h b/gcc/tree-ssa-dce.h
new file mode 100644
index 0000000..2adb086
--- /dev/null
+++ b/gcc/tree-ssa-dce.h
@@ -0,0 +1,22 @@
+/* Copyright (C) 2017 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef TREE_SSA_DCE_H
+#define TREE_SSA_DCE_H
+extern void simple_dce_from_worklist (bitmap);
+#endif
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 281f100..c19d486 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -49,6 +49,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "dbgcnt.h"
 #include "domwalk.h"
 #include "tree-ssa-propagate.h"
+#include "tree-ssa-dce.h"
 #include "tree-cfgcleanup.h"
 #include "alias.h"
 
@@ -4038,64 +4039,6 @@ compute_avail (void)
   free (worklist);
 }
 
-/* Cheap DCE of a known set of possibly dead stmts.
-
-   Because we don't follow exactly the standard PRE algorithm, and decide not
-   to insert PHI nodes sometimes, and because value numbering of casts isn't
-   perfect, we sometimes end up inserting dead code.   This simple DCE-like
-   pass removes any insertions we made that weren't actually used.  */
-
-static void
-remove_dead_inserted_code (void)
-{
-  /* ???  Re-use inserted_exprs as worklist not only as initial set.
-     This may end up removing non-inserted code as well.  If we
-     keep inserted_exprs unchanged we could restrict new worklist
-     elements to members of inserted_exprs.  */
-  bitmap worklist = inserted_exprs;
-  while (! bitmap_empty_p (worklist))
-    {
-      /* Pop item.  */
-      unsigned i = bitmap_first_set_bit (worklist);
-      bitmap_clear_bit (worklist, i);
-
-      tree def = ssa_name (i);
-      /* Removed by somebody else or still in use.  */
-      if (! def || ! has_zero_uses (def))
-	continue;
-
-      gimple *t = SSA_NAME_DEF_STMT (def);
-      if (gimple_has_side_effects (t))
-	continue;
-
-      /* Add uses to the worklist.  */
-      ssa_op_iter iter;
-      use_operand_p use_p;
-      FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
-	{
-	  tree use = USE_FROM_PTR (use_p);
-	  if (TREE_CODE (use) == SSA_NAME
-	      && ! SSA_NAME_IS_DEFAULT_DEF (use))
-	    bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
-	}
-
-      /* Remove stmt.  */
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file, "Removing unnecessary insertion:");
-	  print_gimple_stmt (dump_file, t, 0);
-	}
-      gimple_stmt_iterator gsi = gsi_for_stmt (t);
-      if (gimple_code (t) == GIMPLE_PHI)
-	remove_phi_node (&gsi, true);
-      else
-	{
-	  gsi_remove (&gsi, true);
-	  release_defs (t);
-	}
-    }
-}
-
 
 /* Initialize data structures used by PRE.  */
 
@@ -4234,7 +4177,13 @@ pass_pre::execute (function *fun)
   clear_expression_ids ();
 
   scev_finalize ();
-  remove_dead_inserted_code ();
+
+  /* Because we don't follow exactly the standard PRE algorithm, and decide not
+     to insert PHI nodes sometimes, and because value numbering of casts isn't
+     perfect, we sometimes end up inserting dead code.   This simple DCE-like
+     pass removes any insertions we made that weren't actually used.  */
+  simple_dce_from_worklist (inserted_exprs);
+
   fini_pre ();
   loop_optimizer_finalize ();
 

Re: [PATCH GCC]Rename and make remove_dead_inserted_code a simple dce interface

[Richard Biener]

On Tue, Nov 28, 2017 at 3:48 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> This patch renames remove_dead_inserted_code to simple_dce_from_worklist, moves it to tree-ssa-dce.c
> and makes it a simple public DCE interface.  Bootstrap and test along with loop interchange.  It's required
> for interchange pass.  Is it OK?

+  /* ???  Re-use seeds as worklist not only as initial set.  This may end up
+     removing more code as well.  If we keep seeds unchanged we could restrict
+     new worklist elements to members of seed.  */

Please remove this comment, while it applies to PRE when one takes
remove_dead_inserted_code
literally it doesn't apply to a seeded DCE.

Please also rename 'seeds' to 'worklist' directly and document that
worklist is consumed by the function.
The function has linear complexity in the number of dead stmts, the
constant factor is the number of
SSA use operands in those stmts (so 2 on average I'd say).

Ok with that change.

Thanks,
Richard.

> BTW, I will push this along with interchange to branch: gcc.gnu.org/svn/gcc/branches/gimple-linterchange.
>
> Thanks,
> bin
> 2017-11-27  Bin Cheng  <bin.cheng@arm.com>
>
>         * tree-ssa-dce.c (simple_dce_from_worklist): Move and rename from
>         tree-ssa-pre.c::remove_dead_inserted_code.
>         * tree-ssa-dce.h: New file.
>         * tree-ssa-pre.c (tree-ssa-dce.h): Include new header file.
>         (remove_dead_inserted_code): Move and rename to function
>         tree-ssa-dce.c::simple_dce_from_worklist.
>         (pass_pre::execute): Update use.

Re: [PATCH GCC]Rename and make remove_dead_inserted_code a simple dce interface

[Bin.Cheng]

[-- Attachment #1: Type: text/plain, Size: 1749 bytes --]

On Wed, Nov 29, 2017 at 10:02 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Nov 28, 2017 at 3:48 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>> Hi,
>> This patch renames remove_dead_inserted_code to simple_dce_from_worklist, moves it to tree-ssa-dce.c
>> and makes it a simple public DCE interface.  Bootstrap and test along with loop interchange.  It's required
>> for interchange pass.  Is it OK?
>
> +  /* ???  Re-use seeds as worklist not only as initial set.  This may end up
> +     removing more code as well.  If we keep seeds unchanged we could restrict
> +     new worklist elements to members of seed.  */
>
> Please remove this comment, while it applies to PRE when one takes
> remove_dead_inserted_code
> literally it doesn't apply to a seeded DCE.
>
> Please also rename 'seeds' to 'worklist' directly and document that
> worklist is consumed by the function.
> The function has linear complexity in the number of dead stmts, the
> constant factor is the number of
> SSA use operands in those stmts (so 2 on average I'd say).
>
> Ok with that change.
Updated, will commit new patch as attached.

Thanks,
bin

>
> Thanks,
> Richard.
>
>> BTW, I will push this along with interchange to branch: gcc.gnu.org/svn/gcc/branches/gimple-linterchange.
>>
>> Thanks,
>> bin
>> 2017-11-27  Bin Cheng  <bin.cheng@arm.com>
>>
>>         * tree-ssa-dce.c (simple_dce_from_worklist): Move and rename from
>>         tree-ssa-pre.c::remove_dead_inserted_code.
>>         * tree-ssa-dce.h: New file.
>>         * tree-ssa-pre.c (tree-ssa-dce.h): Include new header file.
>>         (remove_dead_inserted_code): Move and rename to function
>>         tree-ssa-dce.c::simple_dce_from_worklist.
>>         (pass_pre::execute): Update use.

[-- Attachment #2: 0001-simple-dce-interface.patch --]
[-- Type: text/x-patch, Size: 5991 bytes --]

From 219f42625b89eb81e2beb6605c9d594e83ed5048 Mon Sep 17 00:00:00 2001
From: amker <amker@amker-laptop.(none)>
Date: Sun, 26 Nov 2017 20:56:19 +0800
Subject: [PATCH 01/41] simple-dce-interface

---
 gcc/tree-ssa-dce.c | 52 ++++++++++++++++++++++++++++++++++++++++++
 gcc/tree-ssa-dce.h | 22 ++++++++++++++++++
 gcc/tree-ssa-pre.c | 67 +++++++-----------------------------------------------
 3 files changed, 82 insertions(+), 59 deletions(-)
 create mode 100644 gcc/tree-ssa-dce.h

diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index a5f0edf..8595dec 100644
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -1723,3 +1723,55 @@ make_pass_cd_dce (gcc::context *ctxt)
 {
   return new pass_cd_dce (ctxt);
 }
+
+
+/* A cheap DCE interface.  WORKLIST is a list of possibly dead stmts and
+   is consumed by this function.  The function has linear complexity in
+   the number of dead stmts with a constant factor like the average SSA
+   use operands number.  */
+
+void
+simple_dce_from_worklist (bitmap worklist)
+{
+  while (! bitmap_empty_p (worklist))
+    {
+      /* Pop item.  */
+      unsigned i = bitmap_first_set_bit (worklist);
+      bitmap_clear_bit (worklist, i);
+
+      tree def = ssa_name (i);
+      /* Removed by somebody else or still in use.  */
+      if (! def || ! has_zero_uses (def))
+	continue;
+
+      gimple *t = SSA_NAME_DEF_STMT (def);
+      if (gimple_has_side_effects (t))
+	continue;
+
+      /* Add uses to the worklist.  */
+      ssa_op_iter iter;
+      use_operand_p use_p;
+      FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
+	{
+	  tree use = USE_FROM_PTR (use_p);
+	  if (TREE_CODE (use) == SSA_NAME
+	      && ! SSA_NAME_IS_DEFAULT_DEF (use))
+	    bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
+	}
+
+      /* Remove stmt.  */
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Removing dead stmt:");
+	  print_gimple_stmt (dump_file, t, 0);
+	}
+      gimple_stmt_iterator gsi = gsi_for_stmt (t);
+      if (gimple_code (t) == GIMPLE_PHI)
+	remove_phi_node (&gsi, true);
+      else
+	{
+	  gsi_remove (&gsi, true);
+	  release_defs (t);
+	}
+    }
+}
diff --git a/gcc/tree-ssa-dce.h b/gcc/tree-ssa-dce.h
new file mode 100644
index 0000000..2adb086
--- /dev/null
+++ b/gcc/tree-ssa-dce.h
@@ -0,0 +1,22 @@
+/* Copyright (C) 2017 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef TREE_SSA_DCE_H
+#define TREE_SSA_DCE_H
+extern void simple_dce_from_worklist (bitmap);
+#endif
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 281f100..c19d486 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -49,6 +49,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "dbgcnt.h"
 #include "domwalk.h"
 #include "tree-ssa-propagate.h"
+#include "tree-ssa-dce.h"
 #include "tree-cfgcleanup.h"
 #include "alias.h"
 
@@ -4038,64 +4039,6 @@ compute_avail (void)
   free (worklist);
 }
 
-/* Cheap DCE of a known set of possibly dead stmts.
-
-   Because we don't follow exactly the standard PRE algorithm, and decide not
-   to insert PHI nodes sometimes, and because value numbering of casts isn't
-   perfect, we sometimes end up inserting dead code.   This simple DCE-like
-   pass removes any insertions we made that weren't actually used.  */
-
-static void
-remove_dead_inserted_code (void)
-{
-  /* ???  Re-use inserted_exprs as worklist not only as initial set.
-     This may end up removing non-inserted code as well.  If we
-     keep inserted_exprs unchanged we could restrict new worklist
-     elements to members of inserted_exprs.  */
-  bitmap worklist = inserted_exprs;
-  while (! bitmap_empty_p (worklist))
-    {
-      /* Pop item.  */
-      unsigned i = bitmap_first_set_bit (worklist);
-      bitmap_clear_bit (worklist, i);
-
-      tree def = ssa_name (i);
-      /* Removed by somebody else or still in use.  */
-      if (! def || ! has_zero_uses (def))
-	continue;
-
-      gimple *t = SSA_NAME_DEF_STMT (def);
-      if (gimple_has_side_effects (t))
-	continue;
-
-      /* Add uses to the worklist.  */
-      ssa_op_iter iter;
-      use_operand_p use_p;
-      FOR_EACH_PHI_OR_STMT_USE (use_p, t, iter, SSA_OP_USE)
-	{
-	  tree use = USE_FROM_PTR (use_p);
-	  if (TREE_CODE (use) == SSA_NAME
-	      && ! SSA_NAME_IS_DEFAULT_DEF (use))
-	    bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
-	}
-
-      /* Remove stmt.  */
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file, "Removing unnecessary insertion:");
-	  print_gimple_stmt (dump_file, t, 0);
-	}
-      gimple_stmt_iterator gsi = gsi_for_stmt (t);
-      if (gimple_code (t) == GIMPLE_PHI)
-	remove_phi_node (&gsi, true);
-      else
-	{
-	  gsi_remove (&gsi, true);
-	  release_defs (t);
-	}
-    }
-}
-
 
 /* Initialize data structures used by PRE.  */
 
@@ -4234,7 +4177,13 @@ pass_pre::execute (function *fun)
   clear_expression_ids ();
 
   scev_finalize ();
-  remove_dead_inserted_code ();
+
+  /* Because we don't follow exactly the standard PRE algorithm, and decide not
+     to insert PHI nodes sometimes, and because value numbering of casts isn't
+     perfect, we sometimes end up inserting dead code.   This simple DCE-like
+     pass removes any insertions we made that weren't actually used.  */
+  simple_dce_from_worklist (inserted_exprs);
+
   fini_pre ();
   loop_optimizer_finalize ();
 
-- 
1.9.1