* builtins.c (fold_builtin_memory_op): Optimize memmove

	into memcpy if we can prove source and destination don't overlap.

	* gcc.dg/memmove-2.c: New test.
	* gcc.dg/memmove-3.c: New test.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@145127 138bc75d-0d04-0410-961f-82ee72b054a4

5 files changed, 102 insertions, 5 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b1e391a249e..89c62b59cc0 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,8 @@
 2009-03-27  Jakub Jelinek  <jakub@redhat.com>
 
+	* builtins.c (fold_builtin_memory_op): Optimize memmove
+	into memcpy if we can prove source and destination don't overlap.
+
 	* tree-inline.c: Include gt-tree-inline.h.
 	(clone_fn_id_num): New variable.
 	(clone_function_name): New function.
diff --git a/gcc/builtins.c b/gcc/builtins.c
index 929ea9069cb..83ce8eb8d68 100644
--- a/gcc/builtins.c
+++ b/gcc/builtins.c
@@ -8879,17 +8879,76 @@ fold_builtin_memory_op (tree dest, tree src, tree len, tree type, bool ignore, i
 	     really mandatory?
 
 	     If either SRC is readonly or length is 1, we can use memcpy.  */
-	  if (dest_align && src_align
-	      && (readonly_data_expr (src)
-	          || (host_integerp (len, 1)
-		      && (MIN (src_align, dest_align) / BITS_PER_UNIT >=
-			  tree_low_cst (len, 1)))))
+	  if (!dest_align || !src_align)
+	    return NULL_TREE;
+	  if (readonly_data_expr (src)
+	      || (host_integerp (len, 1)
+		  && (MIN (src_align, dest_align) / BITS_PER_UNIT
+		      >= tree_low_cst (len, 1))))
 	    {
 	      tree fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
 	      if (!fn)
 		return NULL_TREE;
               return build_call_expr (fn, 3, dest, src, len);
 	    }
+
+	  /* If *src and *dest can't overlap, optimize into memcpy as well.  */
+	  srcvar = build_fold_indirect_ref (src);
+	  destvar = build_fold_indirect_ref (dest);
+	  if (srcvar
+	      && !TREE_THIS_VOLATILE (srcvar)
+	      && destvar
+	      && !TREE_THIS_VOLATILE (destvar))
+	    {
+	      tree src_base, dest_base, fn;
+	      HOST_WIDE_INT src_offset = 0, dest_offset = 0;
+	      HOST_WIDE_INT size = -1;
+	      HOST_WIDE_INT maxsize = -1;
+
+	      src_base = srcvar;
+	      if (handled_component_p (src_base))
+		src_base = get_ref_base_and_extent (src_base, &src_offset,
+						    &size, &maxsize);
+	      dest_base = destvar;
+	      if (handled_component_p (dest_base))
+		dest_base = get_ref_base_and_extent (dest_base, &dest_offset,
+						     &size, &maxsize);
+	      if (host_integerp (len, 1))
+		{
+		  maxsize = tree_low_cst (len, 1);
+		  if (maxsize
+		      > INTTYPE_MAXIMUM (HOST_WIDE_INT) / BITS_PER_UNIT)
+		    maxsize = -1;
+		  else
+		    maxsize *= BITS_PER_UNIT;
+		}
+	      else
+		maxsize = -1;
+	      if (SSA_VAR_P (src_base)
+		  && SSA_VAR_P (dest_base))
+		{
+		  if (operand_equal_p (src_base, dest_base, 0)
+		      && ranges_overlap_p (src_offset, maxsize,
+					   dest_offset, maxsize))
+		    return NULL_TREE;
+		}
+	      else if (TREE_CODE (src_base) == INDIRECT_REF
+		       && TREE_CODE (dest_base) == INDIRECT_REF)
+		{
+		  if (! operand_equal_p (TREE_OPERAND (src_base, 0),
+					 TREE_OPERAND (dest_base, 0), 0)
+		      || ranges_overlap_p (src_offset, maxsize,
+					   dest_offset, maxsize))
+		    return NULL_TREE;
+		}
+	      else
+		return NULL_TREE;
+
+	      fn = implicit_built_in_decls[BUILT_IN_MEMCPY];
+	      if (!fn)
+		return NULL_TREE;
+	      return build_call_expr (fn, 3, dest, src, len);
+	    }
 	  return NULL_TREE;
 	}
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 295eb89745a..9aecc57d27e 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,8 @@
 2009-03-27  Jakub Jelinek  <jakub@redhat.com>
 
+	* gcc.dg/memmove-2.c: New test.
+	* gcc.dg/memmove-3.c: New test.
+
 	* gcc.dg/ipa/ipacost-1.c: Adjust match pattern for change
 	in clone naming.
 
diff --git a/gcc/testsuite/gcc.dg/memmove-2.c b/gcc/testsuite/gcc.dg/memmove-2.c
new file mode 100644
index 00000000000..9c691ef01c3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/memmove-2.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump-times "memmove" 0 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
+
+char a[40];
+extern void bar (char *);
+
+void
+foo (void)
+{
+  char b[10];
+  __builtin_memmove (&a[0], &a[20], 20);
+  __builtin_memmove (&b[1], &a[25], 9);
+  bar (b);
+}
diff --git a/gcc/testsuite/gcc.dg/memmove-3.c b/gcc/testsuite/gcc.dg/memmove-3.c
new file mode 100644
index 00000000000..98493b3d42c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/memmove-3.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump-times "memmove" 3 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
+
+char a[40];
+struct A { char a[30]; };
+
+void
+foo (struct A *p, char *q, char *r)
+{
+  char b[10];
+  __builtin_memmove (&a[1], &a[19], 20);
+  __builtin_memmove (&p->a[1], &p->a[9], 10);
+  __builtin_memmove (q, r, 9);
+}