Patchwork Don't invalidate string length cache when not needed

login
register
mail settings
Submitter Marek Polacek
Date May 16, 2013, 4:44 p.m.
Message ID <20130516164403.GI14240@redhat.com>
Download mbox | patch
Permalink /patch/244398/
State New
Headers show

Comments

Marek Polacek - May 16, 2013, 4:44 p.m.
On Thu, May 16, 2013 at 04:28:19PM +0200, Jakub Jelinek wrote:
> On Thu, May 16, 2013 at 04:18:27PM +0200, Jakub Jelinek wrote:
> > As q could point to p, if we didn't do what your patch does on the p[0] = 'X';
> > store, then we'd need to invalidate the recorded length of the q string.
> > Similarly if there is p[0] = '\0' or p[0] = var.
> 
> Ah, another thing while we are at it.
> For p[0] = '\0'; case when p[0] is known to be '\0' already, we
> remove it if:
>               /* When storing '\0', the store can be removed
>                  if we know it has been stored in the current function.  */
>               if (!stmt_could_throw_p (stmt) && si->writable)
> (and in that case don't invalidate anything either).  But the above
> condition is false, we set si->writable (correct) and si->dont_invalidate,
> while we could do instead of that the same what you do for non-zero store to
> non-zero location, i.e. gsi_next (gsi); return false;.
> Perhaps a testcase for that is:
> size_t
> bar (char *p, char *r)
> {
>   size_t len1 = strlen (r);
>   char *q = strchr (p, '\0');
>   *q = '\0';
>   return len1 - strlen (r); // This strlen should be optimized into len1.
> }
> 
> strlen (q) should be known to be zero at that point, but si->writable should
> be false, we don't know if p doesn't point say into .rodata, and
> stmt_could_throw_p probably should return true too.

Nice, thanks!  In the patch below I hopefully addressed all the
issues; I also set si->writable to false, but we can't return true in
the stmt_could_throw_p case.  So, how does it look now?

Regtested/bootstrapped on x86_64-linux.

2013-05-16  Marek Polacek  <polacek@redhat.com>

	* tree-ssa-strlen.c (handle_char_store): Don't invalidate
	cached length when doing non-zero store of storing '\0' to
	'\0', don't mark string as writable.

	* gcc.dg/strlenopt-25.c: New test.
	* gcc.dg/strlenopt-26.c: Likewise.


	Marek
Jakub Jelinek - May 16, 2013, 8:33 p.m.
On Thu, May 16, 2013 at 06:44:03PM +0200, Marek Polacek wrote:
> --- gcc/tree-ssa-strlen.c.mp	2013-05-15 14:11:20.079707492 +0200
> +++ gcc/tree-ssa-strlen.c	2013-05-16 17:57:33.963150006 +0200
> @@ -1693,8 +1693,10 @@ handle_char_store (gimple_stmt_iterator
>  		}
>  	      else
>  		{
> -		  si->writable = true;
> -		  si->dont_invalidate = true;
> +		  /* The string might be e.g. in the .rodata section.  */
> +		  si->writable = false;

No, this really should be si->writable = true; (and comment not needed).
Ok with that change.

The thing is, while the string might not be known to be writable before,
i.e. we can't optimize away this store, because supposedly it should
trap, if we notice e.g. another write to the same location (writing zero
there again), we can optimize that other write already, because we know
that this store stored there something.

> +#include "strlenopt.h"
> +
> +__attribute__((noinline, noclone)) size_t
> +fn1 (char *p, const char *r)
> +{
> +  size_t len1 = __builtin_strlen (r);
> +  char *q = __builtin_strchr (p, '\0');
> +  *q = '\0';
> +  return len1 - __builtin_strlen (r); // This strlen should be optimized into len1.

With strlenopt.h include you can avoid using __builtin_ prefixes, all the
builtins needed are prototyped in that header.

	Jakub

Patch

--- gcc/tree-ssa-strlen.c.mp	2013-05-15 14:11:20.079707492 +0200
+++ gcc/tree-ssa-strlen.c	2013-05-16 17:57:33.963150006 +0200
@@ -1693,8 +1693,10 @@  handle_char_store (gimple_stmt_iterator
 		}
 	      else
 		{
-		  si->writable = true;
-		  si->dont_invalidate = true;
+		  /* The string might be e.g. in the .rodata section.  */
+		  si->writable = false;
+		  gsi_next (gsi);
+		  return false;
 		}
 	    }
 	  else
@@ -1717,6 +1719,33 @@  handle_char_store (gimple_stmt_iterator
 	    si->endptr = ssaname;
 	  si->dont_invalidate = true;
 	}
+      /* If si->length is non-zero constant, we aren't overwriting '\0',
+	 and if we aren't storing '\0', we know that the length of the
+	 string and any other zero terminated string in memory remains
+	 the same.  In that case we move to the next gimple statement and
+	 return to signal the caller that it shouldn't invalidate anything.  
+
+	 This is benefical for cases like:
+
+	 char p[20];
+	 void foo (char *q)
+	 {
+	   strcpy (p, "foobar");
+	   size_t len = strlen (p);        // This can be optimized into 6
+	   size_t len2 = strlen (q);        // This has to be computed
+	   p[0] = 'X';
+	   size_t len3 = strlen (p);        // This can be optimized into 6
+	   size_t len4 = strlen (q);        // This can be optimized into len2
+	   bar (len, len2, len3, len4);
+        }
+	*/ 
+      else if (si != NULL && si->length != NULL_TREE
+	       && TREE_CODE (si->length) == INTEGER_CST
+	       && integer_nonzerop (gimple_assign_rhs1 (stmt)))
+	{
+	  gsi_next (gsi);
+	  return false;
+	}
     }
   else if (idx == 0 && initializer_zerop (gimple_assign_rhs1 (stmt)))
     {
--- gcc/testsuite/gcc.dg/strlenopt-25.c.mp	2013-05-15 17:15:18.702118637 +0200
+++ gcc/testsuite/gcc.dg/strlenopt-25.c	2013-05-15 18:26:27.881030317 +0200
@@ -0,0 +1,18 @@ 
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-strlen" } */
+
+#include "strlenopt.h"
+
+int
+main ()
+{
+  char p[] = "foobar";
+  int len, len2;
+  len = strlen (p);
+  p[0] = 'O';
+  len2 = strlen (p);
+  return len - len2;
+}
+
+/* { dg-final { scan-tree-dump-times "strlen \\(" 0 "strlen" } } */
+/* { dg-final { cleanup-tree-dump "strlen" } } */
--- gcc/testsuite/gcc.dg/strlenopt-26.c.mp	2013-05-16 17:33:00.302060413 +0200
+++ gcc/testsuite/gcc.dg/strlenopt-26.c	2013-05-16 18:30:51.906342948 +0200
@@ -0,0 +1,25 @@ 
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-strlen" } */
+
+#include "strlenopt.h"
+
+__attribute__((noinline, noclone)) size_t
+fn1 (char *p, const char *r)
+{
+  size_t len1 = __builtin_strlen (r);
+  char *q = __builtin_strchr (p, '\0');
+  *q = '\0';
+  return len1 - __builtin_strlen (r); // This strlen should be optimized into len1.
+}
+
+int
+main (void)
+{
+  char p[] = "foobar";
+  const char *volatile q = "xyzzy";
+  fn1 (p, q);
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "strlen \\(" 1 "strlen" } } */
+/* { dg-final { cleanup-tree-dump "strlen" } } */