Patchwork Don't invalidate string length cache when not needed

login
register
mail settings
Submitter Marek Polacek
Date May 15, 2013, 4:59 p.m.
Message ID <20130515165909.GD14240@redhat.com>
Download mbox | patch
Permalink /patch/244142/
State New
Headers show

Comments

Marek Polacek - May 15, 2013, 4:59 p.m.
This is a strlen opt patch that better optimizes attached testcase;
there's just no need to call strlen again, as we're not changing
the length of the string.  Unfortunately this still handles only
p[0], not for instance p[1], p[2], ... so we likely don't want to put
this in now.  But I'm posting it at least for archive reasons anyway.
It works by not invalidating the length cache if we're not storing
\0 into a string and the length of a string is > 0.

Bootstrapped/regtested on x86_64-linux.

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

	* tree-ssa-strlen.c (handle_char_store): Don't invalidate
	cached length when doing non-zero store.

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


	Marek
Jakub Jelinek - May 15, 2013, 5:20 p.m.
On Wed, May 15, 2013 at 06:59:09PM +0200, Marek Polacek wrote:
> This is a strlen opt patch that better optimizes attached testcase;
> there's just no need to call strlen again, as we're not changing
> the length of the string.  Unfortunately this still handles only
> p[0], not for instance p[1], p[2], ... so we likely don't want to put
> this in now.  But I'm posting it at least for archive reasons anyway.
> It works by not invalidating the length cache if we're not storing
> \0 into a string and the length of a string is > 0.
> 
> Bootstrapped/regtested on x86_64-linux.
> 
> 2013-05-15  Marek Polacek  <polacek@redhat.com>
> 
> 	* tree-ssa-strlen.c (handle_char_store): Don't invalidate
> 	cached length when doing non-zero store.
> 
> 	* gcc.dg/strlenopt-25.c: New test.
> 
> --- gcc/tree-ssa-strlen.c.mp	2013-05-15 14:11:20.079707492 +0200
> +++ gcc/tree-ssa-strlen.c	2013-05-15 17:21:23.772094679 +0200
> @@ -1717,6 +1717,11 @@ handle_char_store (gimple_stmt_iterator
>  	    si->endptr = ssaname;
>  	  si->dont_invalidate = true;
>  	}
> +      else if (si != NULL && si->length != NULL_TREE
> +	       && TREE_CODE (si->length) == INTEGER_CST
> +	       && integer_nonzerop (gimple_assign_rhs1 (stmt))
> +	       && tree_int_cst_sgn (si->length) > 0)
> +	si->dont_invalidate = true;

Well, if si->length is known constant != 0 (note, it is enough to
test that it is non-zero and probably the code above this has
tested that already?) and we are storing non-zero, then that
should mean we are overwriting a non-zero value with another (or same)
non-zero value.  Such operation shouldn't change the length of any strings
at all, not just the ones related to the current strinfo.
That is either just setting all current strinfos to dont_invalidate, or
perhaps faster doing gsi_next (gsi); return false; (that means the caller
won't call maybe_invalidate - of course in that case you must not set
any dont_invalidate on any strinfo on that stmt) and the caller of
strlen_optimize_stmt will not do gsi_next (&gsi) - that is why you need
to do it instead.

	Jakub
Richard Guenther - May 16, 2013, 8:54 a.m.
On Wed, May 15, 2013 at 7:20 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Wed, May 15, 2013 at 06:59:09PM +0200, Marek Polacek wrote:
>> This is a strlen opt patch that better optimizes attached testcase;
>> there's just no need to call strlen again, as we're not changing
>> the length of the string.  Unfortunately this still handles only
>> p[0], not for instance p[1], p[2], ... so we likely don't want to put
>> this in now.  But I'm posting it at least for archive reasons anyway.
>> It works by not invalidating the length cache if we're not storing
>> \0 into a string and the length of a string is > 0.
>>
>> Bootstrapped/regtested on x86_64-linux.
>>
>> 2013-05-15  Marek Polacek  <polacek@redhat.com>
>>
>>       * tree-ssa-strlen.c (handle_char_store): Don't invalidate
>>       cached length when doing non-zero store.
>>
>>       * gcc.dg/strlenopt-25.c: New test.
>>
>> --- gcc/tree-ssa-strlen.c.mp  2013-05-15 14:11:20.079707492 +0200
>> +++ gcc/tree-ssa-strlen.c     2013-05-15 17:21:23.772094679 +0200
>> @@ -1717,6 +1717,11 @@ handle_char_store (gimple_stmt_iterator
>>           si->endptr = ssaname;
>>         si->dont_invalidate = true;
>>       }
>> +      else if (si != NULL && si->length != NULL_TREE
>> +            && TREE_CODE (si->length) == INTEGER_CST
>> +            && integer_nonzerop (gimple_assign_rhs1 (stmt))
>> +            && tree_int_cst_sgn (si->length) > 0)
>> +     si->dont_invalidate = true;
>
> Well, if si->length is known constant != 0 (note, it is enough to
> test that it is non-zero and probably the code above this has
> tested that already?) and we are storing non-zero, then that
> should mean we are overwriting a non-zero value with another (or same)
> non-zero value.  Such operation shouldn't change the length of any strings
> at all, not just the ones related to the current strinfo.
> That is either just setting all current strinfos to dont_invalidate, or
> perhaps faster doing gsi_next (gsi); return false; (that means the caller
> won't call maybe_invalidate - of course in that case you must not set
> any dont_invalidate on any strinfo on that stmt) and the caller of
> strlen_optimize_stmt will not do gsi_next (&gsi) - that is why you need
> to do it instead.

Can we properly distinguish the case of

  char *s = "Hello\0World!";
  s[5] = ' ';

(minor the imperfections in that example)?  Thus, overwriting the terminating
0?

Richard.


>         Jakub
Jakub Jelinek - May 16, 2013, 9:04 a.m.
On Thu, May 16, 2013 at 10:54:53AM +0200, Richard Biener wrote:
> Can we properly distinguish the case of
> 
>   char *s = "Hello\0World!";
>   s[5] = ' ';
> 
> (minor the imperfections in that example)?  Thus, overwriting the terminating
> 0?

I think so.  Because then for &s[5], either si should be NULL, or si->length
should be NULL (either case suggests we either never knew or don't know any
longer the string length at that address), or should be non-constant, or should be zero.
Because if it is constant non-zero at that point, it would mean that
strlen (&s[5]) at that point would return non-zero constant, but should have
returned 0.

	Jakub

Patch

--- gcc/tree-ssa-strlen.c.mp	2013-05-15 14:11:20.079707492 +0200
+++ gcc/tree-ssa-strlen.c	2013-05-15 17:21:23.772094679 +0200
@@ -1717,6 +1717,11 @@  handle_char_store (gimple_stmt_iterator
 	    si->endptr = ssaname;
 	  si->dont_invalidate = true;
 	}
+      else if (si != NULL && si->length != NULL_TREE
+	       && TREE_CODE (si->length) == INTEGER_CST
+	       && integer_nonzerop (gimple_assign_rhs1 (stmt))
+	       && tree_int_cst_sgn (si->length) > 0)
+	si->dont_invalidate = true;
     }
   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" } } */