This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

DSE calls to builtins (memset, etc)


Hello,

here is a patch extending DSE to handle calls to memset, memcpy and memmove. A number of alias functions didn't have a version taking an ao_ref*, so I added those. Instead of naming things _1, _2, etc I took advantage of C++ and overloaded. I kept ref_maybe_used_by_call_p so we are still updating the stats, but I am not sure how reliable they are, for instance there are a number of direct calls to refs_may_alias_p_1 that skip the stats in refs_may_alias_p (so I didn't add counters to the new refs_may_alias_p overload).

The piece of code I removed from dse_optimize_stmt was dead, the test has already been done in dse_possible_dead_store_p (and I ran bootstrap+testsuite with an assertion to confirm).

I only listed 3 builtins, but it should be easy to add more. The condition about the third argument is unnecessary for now, but copied from tree-ssa-alias.c to make it easier to add more builtins like strcpy.

Bootstrap+testsuite (really all languages) on x86_64-linux-gnu.

2014-08-18  Marc Glisse  <marc.glisse@inria.fr>

	PR tree-optimization/62112
gcc/
	tree-ssa-alias.c (ref_may_alias_global_p, refs_may_alias_p,
	ref_maybe_used_by_stmt_p): New overloads.
	(ref_maybe_used_by_call_p): Take ao_ref* instead of tree.
	(stmt_kills_ref_p_1): Rename...
	(stmt_kills_ref_p): ... to this.
	tree-ssa-alias.h (ref_may_alias_global_p, ref_maybe_used_by_stmt_p,
	stmt_kills_ref_p): Declare.
	tree-ssa-dse.c (dse_possible_dead_store_p): New argument, use it.
	Move the self-assignment case...
	(dse_optimize_stmt): ... here. Handle builtin calls. Remove dead code.
gcc/testsuite/
	gcc.dg/tree-ssa/pr62112-1.c: New file.
	gcc.dg/tree-ssa/pr62112-2.c: Likewise.

--
Marc Glisse
Index: gcc/testsuite/gcc.dg/tree-ssa/pr62112-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/pr62112-1.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/pr62112-1.c	(working copy)
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-dse1-details" } */
+
+void f(){
+  char*p=__builtin_malloc(42);
+  __builtin_memset(p,3,10);
+  __builtin_memset(p,7,33);
+}
+char*g;
+void h(){
+  char*p=__builtin_malloc(42);
+  g=__builtin_memset(p,3,10);
+  __builtin_free(p);
+}
+char*i(){
+  char*p=__builtin_malloc(42);
+  __builtin_memset(p,3,10);
+  __builtin_memset(p,7,33);
+  return p;
+}
+
+/* { dg-final { scan-tree-dump-times "Deleted dead store" 4 "dse1" } } */
+/* { dg-final { cleanup-tree-dump "dse1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/pr62112-2.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/pr62112-2.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/pr62112-2.c	(working copy)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-dse1-details" } */
+
+char*g;
+char* f(){
+  char*p=__builtin_malloc(42);
+  __builtin_memset(p,3,33);
+  __builtin_memset(p,7,10);
+  return p;
+}
+void h(){
+  char*p=__builtin_malloc(42);
+  g=__builtin_memset(p,3,10);
+}
+
+/* { dg-final { scan-tree-dump-not "Deleted dead store" "dse1" } } */
+/* { dg-final { cleanup-tree-dump "dse1" } } */
Index: gcc/tree-ssa-alias.c
===================================================================
--- gcc/tree-ssa-alias.c	(revision 214066)
+++ gcc/tree-ssa-alias.c	(working copy)
@@ -326,31 +326,39 @@ ptr_deref_may_alias_ref_p_1 (tree ptr, a
     return ptr_derefs_may_alias_p (ptr, TREE_OPERAND (base, 0));
   else if (DECL_P (base))
     return ptr_deref_may_alias_decl_p (ptr, base);
 
   return true;
 }
 
 /* Return true whether REF may refer to global memory.  */
 
 bool
-ref_may_alias_global_p (tree ref)
+ref_may_alias_global_p (ao_ref *ref)
 {
-  tree base = get_base_address (ref);
+  tree base = ao_ref_base (ref);
   if (DECL_P (base))
     return is_global_var (base);
   else if (TREE_CODE (base) == MEM_REF
 	   || TREE_CODE (base) == TARGET_MEM_REF)
     return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0));
   return true;
 }
 
+bool
+ref_may_alias_global_p (tree ref)
+{
+  ao_ref r;
+  ao_ref_init (&r, ref);
+  return ref_may_alias_global_p (&r);
+}
+
 /* Return true whether STMT may clobber global memory.  */
 
 bool
 stmt_may_clobber_global_p (gimple stmt)
 {
   tree lhs;
 
   if (!gimple_vdef (stmt))
     return false;
 
@@ -1406,20 +1414,28 @@ refs_may_alias_p_1 (ao_ref *ref1, ao_ref
 				      tbaa_p);
 
   /* We really do not want to end up here, but returning true is safe.  */
 #ifdef ENABLE_CHECKING
   gcc_unreachable ();
 #else
   return true;
 #endif
 }
 
+static bool
+refs_may_alias_p (tree ref1, ao_ref *ref2)
+{
+  ao_ref r1;
+  ao_ref_init (&r1, ref1);
+  return refs_may_alias_p_1 (&r1, ref2, true);
+}
+
 bool
 refs_may_alias_p (tree ref1, tree ref2)
 {
   ao_ref r1, r2;
   bool res;
   ao_ref_init (&r1, ref1);
   ao_ref_init (&r2, ref2);
   res = refs_may_alias_p_1 (&r1, &r2, true);
   if (res)
     ++alias_stats.refs_may_alias_p_may_alias;
@@ -1762,39 +1778,37 @@ process_args:
 	  ao_ref_init (&r, op);
 	  if (refs_may_alias_p_1 (&r, ref, true))
 	    return true;
 	}
     }
 
   return false;
 }
 
 static bool
-ref_maybe_used_by_call_p (gimple call, tree ref)
+ref_maybe_used_by_call_p (gimple call, ao_ref *ref)
 {
-  ao_ref r;
   bool res;
-  ao_ref_init (&r, ref);
-  res = ref_maybe_used_by_call_p_1 (call, &r);
+  res = ref_maybe_used_by_call_p_1 (call, ref);
   if (res)
     ++alias_stats.ref_maybe_used_by_call_p_may_alias;
   else
     ++alias_stats.ref_maybe_used_by_call_p_no_alias;
   return res;
 }
 
 
 /* If the statement STMT may use the memory reference REF return
    true, otherwise return false.  */
 
 bool
-ref_maybe_used_by_stmt_p (gimple stmt, tree ref)
+ref_maybe_used_by_stmt_p (gimple stmt, ao_ref *ref)
 {
   if (is_gimple_assign (stmt))
     {
       tree rhs;
 
       /* All memory assign statements are single.  */
       if (!gimple_assign_single_p (stmt))
 	return false;
 
       rhs = gimple_assign_rhs1 (stmt);
@@ -1803,41 +1817,48 @@ ref_maybe_used_by_stmt_p (gimple stmt, t
 	  || gimple_assign_rhs_code (stmt) == CONSTRUCTOR)
 	return false;
 
       return refs_may_alias_p (rhs, ref);
     }
   else if (is_gimple_call (stmt))
     return ref_maybe_used_by_call_p (stmt, ref);
   else if (gimple_code (stmt) == GIMPLE_RETURN)
     {
       tree retval = gimple_return_retval (stmt);
-      tree base;
       if (retval
 	  && TREE_CODE (retval) != SSA_NAME
 	  && !is_gimple_min_invariant (retval)
 	  && refs_may_alias_p (retval, ref))
 	return true;
       /* If ref escapes the function then the return acts as a use.  */
-      base = get_base_address (ref);
+      tree base = ao_ref_base (ref);
       if (!base)
 	;
       else if (DECL_P (base))
 	return is_global_var (base);
       else if (TREE_CODE (base) == MEM_REF
 	       || TREE_CODE (base) == TARGET_MEM_REF)
 	return ptr_deref_may_alias_global_p (TREE_OPERAND (base, 0));
       return false;
     }
 
   return true;
 }
 
+bool
+ref_maybe_used_by_stmt_p (gimple stmt, tree ref)
+{
+  ao_ref r;
+  ao_ref_init (&r, ref);
+  return ref_maybe_used_by_stmt_p (stmt, &r);
+}
+
 /* If the call in statement CALL may clobber the memory reference REF
    return true, otherwise return false.  */
 
 bool
 call_may_clobber_ref_p_1 (gimple call, ao_ref *ref)
 {
   tree base;
   tree callee;
 
   /* If the call is pure or const it cannot clobber anything.  */
@@ -2162,22 +2183,22 @@ bool
 stmt_may_clobber_ref_p (gimple stmt, tree ref)
 {
   ao_ref r;
   ao_ref_init (&r, ref);
   return stmt_may_clobber_ref_p_1 (stmt, &r);
 }
 
 /* If STMT kills the memory reference REF return true, otherwise
    return false.  */
 
-static bool
-stmt_kills_ref_p_1 (gimple stmt, ao_ref *ref)
+bool
+stmt_kills_ref_p (gimple stmt, ao_ref *ref)
 {
   if (!ao_ref_base (ref))
     return false;
 
   if (gimple_has_lhs (stmt)
       && TREE_CODE (gimple_get_lhs (stmt)) != SSA_NAME
       /* The assignment is not necessarily carried out if it can throw
 	 and we can catch it in the current function where we could inspect
 	 the previous value.
 	 ???  We only need to care about the RHS throwing.  For aggregate
@@ -2350,21 +2371,21 @@ stmt_kills_ref_p_1 (gimple stmt, ao_ref
 	  }
     }
   return false;
 }
 
 bool
 stmt_kills_ref_p (gimple stmt, tree ref)
 {
   ao_ref r;
   ao_ref_init (&r, ref);
-  return stmt_kills_ref_p_1 (stmt, &r);
+  return stmt_kills_ref_p (stmt, &r);
 }
 
 
 /* Walk the virtual use-def chain of VUSE until hitting the virtual operand
    TARGET or a statement clobbering the memory reference REF in which
    case false is returned.  The walk starts with VUSE, one argument of PHI.  */
 
 static bool
 maybe_skip_until (gimple phi, tree target, ao_ref *ref,
 		  tree vuse, unsigned int *cnt, bitmap *visited,
Index: gcc/tree-ssa-alias.h
===================================================================
--- gcc/tree-ssa-alias.h	(revision 214066)
+++ gcc/tree-ssa-alias.h	(working copy)
@@ -94,31 +94,34 @@ struct ao_ref
 
 
 /* In tree-ssa-alias.c  */
 extern void ao_ref_init (ao_ref *, tree);
 extern void ao_ref_init_from_ptr_and_size (ao_ref *, tree, tree);
 extern tree ao_ref_base (ao_ref *);
 extern alias_set_type ao_ref_alias_set (ao_ref *);
 extern bool ptr_deref_may_alias_global_p (tree);
 extern bool ptr_derefs_may_alias_p (tree, tree);
 extern bool ref_may_alias_global_p (tree);
+extern bool ref_may_alias_global_p (ao_ref *);
 extern bool refs_may_alias_p (tree, tree);
 extern bool refs_may_alias_p_1 (ao_ref *, ao_ref *, bool);
 extern bool refs_anti_dependent_p (tree, tree);
 extern bool refs_output_dependent_p (tree, tree);
 extern bool ref_maybe_used_by_stmt_p (gimple, tree);
+extern bool ref_maybe_used_by_stmt_p (gimple, ao_ref *);
 extern bool stmt_may_clobber_global_p (gimple);
 extern bool stmt_may_clobber_ref_p (gimple, tree);
 extern bool stmt_may_clobber_ref_p_1 (gimple, ao_ref *);
 extern bool call_may_clobber_ref_p (gimple, tree);
 extern bool call_may_clobber_ref_p_1 (gimple, ao_ref *);
 extern bool stmt_kills_ref_p (gimple, tree);
+extern bool stmt_kills_ref_p (gimple, ao_ref *);
 extern tree get_continuation_for_phi (gimple, ao_ref *,
 				      unsigned int *, bitmap *, bool,
 				      void *(*)(ao_ref *, tree, void *, bool),
 				      void *);
 extern void *walk_non_aliased_vuses (ao_ref *, tree,
 				     void *(*)(ao_ref *, tree,
 					       unsigned int, void *),
 				     void *(*)(ao_ref *, tree, void *, bool),
 				     void *);
 extern unsigned int walk_aliased_vdefs (ao_ref *, tree,
Index: gcc/tree-ssa-dse.c
===================================================================
--- gcc/tree-ssa-dse.c	(revision 214066)
+++ gcc/tree-ssa-dse.c	(working copy)
@@ -75,39 +75,32 @@ along with GCC; see the file COPYING3.
    fact, they are the same transformation applied to different views of
    the CFG.  */
 
 
 /* Bitmap of blocks that have had EH statements cleaned.  We should
    remove their dead edges eventually.  */
 static bitmap need_eh_cleanup;
 
 
 /* A helper of dse_optimize_stmt.
-   Given a GIMPLE_ASSIGN in STMT, find a candidate statement *USE_STMT that
-   may prove STMT to be dead.
+   Given a GIMPLE_ASSIGN in STMT that writes to REF, find a candidate
+   statement *USE_STMT that may prove STMT to be dead.
    Return TRUE if the above conditions are met, otherwise FALSE.  */
 
 static bool
-dse_possible_dead_store_p (gimple stmt, gimple *use_stmt)
+dse_possible_dead_store_p (ao_ref *ref, gimple stmt, gimple *use_stmt)
 {
   gimple temp;
   unsigned cnt = 0;
 
   *use_stmt = NULL;
 
-  /* Self-assignments are zombies.  */
-  if (operand_equal_p (gimple_assign_rhs1 (stmt), gimple_assign_lhs (stmt), 0))
-    {
-      *use_stmt = stmt;
-      return true;
-    }
-
   /* Find the first dominated statement that clobbers (part of) the
      memory stmt stores to with no intermediate statement that may use
      part of the memory stmt stores.  That is, find a store that may
      prove stmt to be a dead store.  */
   temp = stmt;
   do
     {
       gimple use_stmt, defvar_def;
       imm_use_iterator ui;
       bool fail = false;
@@ -157,22 +150,21 @@ dse_possible_dead_store_p (gimple stmt,
 	      /* Do not consider the PHI as use if it dominates the 
 	         stmt defining the virtual operand we are processing,
 		 we have processed it already in this case.  */
 	      if (gimple_bb (defvar_def) != gimple_bb (use_stmt)
 		  && !dominated_by_p (CDI_DOMINATORS,
 				      gimple_bb (defvar_def),
 				      gimple_bb (use_stmt)))
 		temp = use_stmt;
 	    }
 	  /* If the statement is a use the store is not dead.  */
-	  else if (ref_maybe_used_by_stmt_p (use_stmt,
-					     gimple_assign_lhs (stmt)))
+	  else if (ref_maybe_used_by_stmt_p (use_stmt, ref))
 	    {
 	      fail = true;
 	      BREAK_FROM_IMM_USE_STMT (ui);
 	    }
 	  /* If this is a store, remember it or bail out if we have
 	     multiple ones (the will be in different CFG parts then).  */
 	  else if (gimple_vdef (use_stmt))
 	    {
 	      if (temp)
 		{
@@ -184,29 +176,29 @@ dse_possible_dead_store_p (gimple stmt,
 	}
 
       if (fail)
 	return false;
 
       /* If we didn't find any definition this means the store is dead
          if it isn't a store to global reachable memory.  In this case
 	 just pretend the stmt makes itself dead.  Otherwise fail.  */
       if (!temp)
 	{
-	  if (stmt_may_clobber_global_p (stmt))
+	  if (ref_may_alias_global_p (ref))
 	    return false;
 
 	  temp = stmt;
 	  break;
 	}
     }
   /* Continue walking until we reach a kill.  */
-  while (!stmt_kills_ref_p (temp, gimple_assign_lhs (stmt)));
+  while (!stmt_kills_ref_p (temp, ref));
 
   *use_stmt = temp;
 
   return true;
 }
 
 
 /* Attempt to eliminate dead stores in the statement referenced by BSI.
 
    A dead store is a store into a memory location which will later be
@@ -221,75 +213,119 @@ dse_possible_dead_store_p (gimple stmt,
 static void
 dse_optimize_stmt (gimple_stmt_iterator *gsi)
 {
   gimple stmt = gsi_stmt (*gsi);
 
   /* If this statement has no virtual defs, then there is nothing
      to do.  */
   if (!gimple_vdef (stmt))
     return;
 
-  /* We know we have virtual definitions.  If this is a GIMPLE_ASSIGN
-     that's not also a function call, then record it into our table.  */
-  if (is_gimple_call (stmt) && gimple_call_fndecl (stmt))
-    return;
-
   /* Don't return early on *this_2(D) ={v} {CLOBBER}.  */
   if (gimple_has_volatile_ops (stmt)
       && (!gimple_clobber_p (stmt)
 	  || TREE_CODE (gimple_assign_lhs (stmt)) != MEM_REF))
     return;
 
+  /* We know we have virtual definitions.  We can handle assignments and
+     some builtin calls.  */
+  if (is_gimple_call (stmt))
+    {
+      tree callee = gimple_call_fndecl (stmt);
+      if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
+	return;
+      switch (DECL_FUNCTION_CODE (callee))
+	{
+	  case BUILT_IN_MEMCPY:
+	  case BUILT_IN_MEMMOVE:
+	  case BUILT_IN_MEMSET:
+	    {
+	      gimple use_stmt;
+	      ao_ref ref;
+	      tree size = NULL_TREE;
+	      int nargs = gimple_call_num_args (stmt);
+	      if (nargs < 2)
+		return;
+	      if (nargs == 3)
+		size = gimple_call_arg (stmt, 2);
+	      tree ptr = gimple_call_arg (stmt, 0);
+	      ao_ref_init_from_ptr_and_size (&ref, ptr, size);
+	      if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
+		return;
+
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		{
+		  fprintf (dump_file, "  Deleted dead store '");
+		  print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
+		  fprintf (dump_file, "'\n");
+		}
+
+	      tree lhs = gimple_call_lhs (stmt);
+	      if (lhs)
+		{
+		  gimple new_stmt = gimple_build_assign (lhs, ptr);
+		  unlink_stmt_vdef (stmt);
+		  gsi_replace (gsi, new_stmt, true);
+		}
+	      else
+		{
+		  /* Then we need to fix the operand of the consuming stmt.  */
+		  unlink_stmt_vdef (stmt);
+
+		  /* Remove the dead store.  */
+		  basic_block bb = gimple_bb (stmt);
+		  if (gsi_remove (gsi, true))
+		    bitmap_set_bit (need_eh_cleanup, bb->index);
+		}
+	      break;
+	    }
+	  default:
+	    return;
+	}
+    }
+
   if (is_gimple_assign (stmt))
     {
       gimple use_stmt;
 
-      if (!dse_possible_dead_store_p (stmt, &use_stmt))
-	return;
+      /* Self-assignments are zombies.  */
+      if (operand_equal_p (gimple_assign_rhs1 (stmt),
+			   gimple_assign_lhs (stmt), 0))
+	use_stmt = stmt;
+      else
+	{
+	  ao_ref ref;
+	  ao_ref_init (&ref, gimple_assign_lhs (stmt));
+  	  if (!dse_possible_dead_store_p (&ref, stmt, &use_stmt))
+	    return;
+	}
 
       /* Now we know that use_stmt kills the LHS of stmt.  */
 
       /* But only remove *this_2(D) ={v} {CLOBBER} if killed by
 	 another clobber stmt.  */
       if (gimple_clobber_p (stmt)
 	  && !gimple_clobber_p (use_stmt))
 	return;
 
-      basic_block bb;
-
-      /* If use_stmt is or might be a nop assignment, e.g. for
-	   struct { ... } S a, b, *p; ...
-	   b = a; b = b;
-	 or
-	   b = a; b = *p; where p might be &b,
-	 or
-           *p = a; *p = b; where p might be &b,
-	 or
-           *p = *u; *p = *v; where p might be v, then USE_STMT
-         acts as a use as well as definition, so store in STMT
-         is not dead.  */
-      if (stmt != use_stmt
-	  && ref_maybe_used_by_stmt_p (use_stmt, gimple_assign_lhs (stmt)))
-	return;
-
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "  Deleted dead store '");
 	  print_gimple_stmt (dump_file, gsi_stmt (*gsi), dump_flags, 0);
 	  fprintf (dump_file, "'\n");
 	}
 
       /* Then we need to fix the operand of the consuming stmt.  */
       unlink_stmt_vdef (stmt);
 
       /* Remove the dead store.  */
-      bb = gimple_bb (stmt);
+      basic_block bb = gimple_bb (stmt);
       if (gsi_remove (gsi, true))
 	bitmap_set_bit (need_eh_cleanup, bb->index);
 
       /* And release any SSA_NAMEs set in this statement back to the
 	 SSA_NAME manager.  */
       release_defs (stmt);
     }
 }
 
 class dse_dom_walker : public dom_walker

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]