Patch to builtin strcat for constant strings

["Kaveh R. Ghazi" <ghazi at caip dot rutgers dot edu>]

Currently, builtin strcat only optimizes the case where the src string
is "".  This patch optimizes builtin strcat to handle other constant
strings by using store by pieces into (dst + strlen (dst)).  We only
perform this if store by pieces is successful, I do this by calling
expand_builtin_mempcpy with the appropriate arglist.  Naturally, I
bypass this if optimize_size is set.

Running strcat in a loop as shown below, I see speedups of around 30%
on x86-linux and around 50% on sparc-solaris2.

  unsigned int i, len = strlen (dst);
  for (i=0; i<MAX_ITER; i++)
    {
      dst[len]=0;
      strcat (strcat (strcat (strcat (strcat (strcat (dst, "this "), ""),
				      "is "), "a "), "test"), ".");
    }

The patch was tested on sparc-sun-solaris2.7 (minus java), no
regressions and the new testcase additions pass.

While I was updating the testcase I took the opportunity to prepare it
for some better checks.  IMHO we shouldn't check strings with strcmp
in testcases, we should use memcmp and check past the NULL terminator
to ensure the builtins don't write past it.  I haven't fixed the whole
testcase, just the additions I made, but I added macro infrastructure
to make it easier.

Ok for mainline?

		Thanks,
		--Kaveh


2003-07-26  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>

	* builtins.c (expand_builtin_strcat): Optimize constant strings.

testsuite:
	* gcc.c-torture/execute/string-opt-9.c: Add more strcat cases.

diff -rup orig/egcc-CVS20030725/gcc/builtins.c egcc-CVS20030725/gcc/builtins.c
--- orig/egcc-CVS20030725/gcc/builtins.c	2003-07-24 20:01:15.000000000 -0400
+++ egcc-CVS20030725/gcc/builtins.c	2003-07-26 00:45:33.070991000 -0400
@@ -3572,9 +3572,52 @@ expand_builtin_strcat (tree arglist, rtx
 	src = TREE_VALUE (TREE_CHAIN (arglist));
       const char *p = c_getstr (src);
 
-      /* If the string length is zero, return the dst parameter.  */
-      if (p && *p == '\0')
-	return expand_expr (dst, target, mode, EXPAND_NORMAL);
+      if (p)
+	{
+	  /* If the string length is zero, return the dst parameter.  */
+	  if (*p == '\0')
+	    return expand_expr (dst, target, mode, EXPAND_NORMAL);
+	  else if (!optimize_size)
+	    {
+	      /* Otherwise if !optimize_size, see if we can store by
+                 pieces into (dst + strlen(dst)).  */
+	      tree newdst, arglist,
+		strlen_fn = implicit_built_in_decls[BUILT_IN_STRLEN];
+	      
+	      /* This is the length argument.  */
+	      arglist = build_tree_list (NULL_TREE,
+					 fold (size_binop (PLUS_EXPR,
+							   c_strlen (src, 0),
+							   ssize_int (1))));
+	      /* Prepend src argument.  */
+	      arglist = tree_cons (NULL_TREE, src, arglist);
+	      
+	      /* We're going to use dst more than once.  */
+	      dst = save_expr (dst);
+
+	      /* Create strlen (dst).  */
+	      newdst =
+		fold (build_function_call_expr (strlen_fn,
+						build_tree_list (NULL_TREE,
+								 dst)));
+	      /* Create (dst + strlen (dst)).  */
+	      newdst = fold (build (PLUS_EXPR, TREE_TYPE (dst), dst, newdst));
+
+	      /* Prepend the new dst argument.  */
+	      arglist = tree_cons (NULL_TREE, newdst, arglist);
+	      
+	      /* We don't want to get turned into a memcpy if the
+                 target is const0_rtx, i.e. when the return value
+                 isn't used.  That would produce pessimized code so
+                 pass in a target of zero, it should never actually be
+                 used.  If this was successful return the original
+                 dst, not the result of mempcpy.  */
+	      if (expand_builtin_mempcpy (arglist, /*target=*/0, mode, /*endp=*/0))
+		return expand_expr (dst, target, mode, EXPAND_NORMAL);
+	      else
+		return 0;
+	    }
+	}
 
       return 0;
     }
diff -rup orig/egcc-CVS20030725/gcc/testsuite/gcc.c-torture/execute/string-opt-9.c egcc-CVS20030725/gcc/testsuite/gcc.c-torture/execute/string-opt-9.c
--- orig/egcc-CVS20030725/gcc/testsuite/gcc.c-torture/execute/string-opt-9.c	2003-01-21 14:43:53.000000000 -0500
+++ egcc-CVS20030725/gcc/testsuite/gcc.c-torture/execute/string-opt-9.c	2003-07-26 00:35:22.779498000 -0400
@@ -10,6 +10,10 @@ typedef __SIZE_TYPE__ size_t;
 extern char *strcat (char *, const char *);
 extern char *strcpy (char *, const char *);
 extern char *strcmp (const char *, const char *);
+extern void *memset (void *, int, size_t);
+extern int memcmp (const void *, const void *, size_t);
+#define RESET_DST_WITH(FILLER) \
+  do { memset (dst, 'X', sizeof (dst)); strcpy (dst, (FILLER)); } while (0)
 
 int main ()
 {
@@ -17,25 +21,48 @@ int main ()
   const char *const s2 = "";
   char dst[64], *d2;
   
-  strcpy (dst, s1);
+  RESET_DST_WITH (s1);
   if (strcat (dst, "") != dst || strcmp (dst, s1))
     abort();
-  strcpy (dst, s1);
+  RESET_DST_WITH (s1);
   if (strcat (dst, s2) != dst || strcmp (dst, s1))
     abort();
-  strcpy (dst, s1); d2 = dst;
+  RESET_DST_WITH (s1); d2 = dst;
   if (strcat (++d2, s2) != dst+1 || d2 != dst+1 || strcmp (dst, s1))
     abort();
-  strcpy (dst, s1); d2 = dst;
+  RESET_DST_WITH (s1); d2 = dst;
   if (strcat (++d2+5, s2) != dst+6 || d2 != dst+1 || strcmp (dst, s1))
     abort();
-  strcpy (dst, s1); d2 = dst;
+  RESET_DST_WITH (s1); d2 = dst;
   if (strcat (++d2+5, s1+11) != dst+6 || d2 != dst+1 || strcmp (dst, s1))
     abort();
 
+#ifndef __OPTIMIZE_SIZE__
+  RESET_DST_WITH (s1);
+  if (strcat (dst, " 1111") != dst
+      || memcmp (dst, "hello world 1111\0XXX", 20))
+    abort();
+  
+  RESET_DST_WITH (s1);
+  if (strcat (dst+5, " 2222") != dst+5
+      || memcmp (dst, "hello world 2222\0XXX", 20))
+    abort();
+  
+  RESET_DST_WITH (s1); d2 = dst;
+  if (strcat (++d2+5, " 3333") != dst+6 || d2 != dst+1
+      || memcmp (dst, "hello world 3333\0XXX", 20))
+    abort();
+  
+  RESET_DST_WITH (s1);
+  strcat (strcat (strcat (strcat (strcat (strcat (dst, ": this "), ""),
+				  "is "), "a "), "test"), ".");
+  if (memcmp (dst, "hello world: this is a test.\0X", 30))
+    abort();
+#endif
+
   /* Test at least one instance of the __builtin_ style.  We do this
      to ensure that it works and that the prototype is correct.  */
-  strcpy (dst, s1);
+  RESET_DST_WITH (s1);
   if (__builtin_strcat (dst, "") != dst || strcmp (dst, s1))
     abort();