Patchwork Fix up strlen pass invalidation (PR tree-optimization/58277)

login
register
mail settings
Submitter Jakub Jelinek
Date Aug. 30, 2013, 12:23 p.m.
Message ID <20130830122342.GL21876@tucnak.zalov.cz>
Download mbox | patch
Permalink /patch/271244/
State New
Headers show

Comments

Jakub Jelinek - Aug. 30, 2013, 12:23 p.m.
Hi!

Apparently I forgot to add code for complete invalidation of everything, if
more than 100 stmts with vdefs are seen in between immediate dominator and
current basic block.  That cutoff is there so that we don't spend too much
time on invalidation, but without this patch it actually ignored all the
other vdef stmts in between those two bbs rather than just starting with no
known string lengths at the start of the bb.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk/4.8?

2013-08-30  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/58277
	* tree-ssa-strlen.c (strlen_enter_block): If do_invalidate gave up
	after seeing too many stmts with vdef in between dombb and current
	bb, invalidate everything.

	* gcc.c-torture/execute/pr58277-1.c: New test.
	* gcc.c-torture/execute/pr58277-2.c: New test.


	Jakub
Richard Guenther - Aug. 30, 2013, 12:28 p.m.
On Fri, 30 Aug 2013, Jakub Jelinek wrote:

> Hi!
> 
> Apparently I forgot to add code for complete invalidation of everything, if
> more than 100 stmts with vdefs are seen in between immediate dominator and
> current basic block.  That cutoff is there so that we don't spend too much
> time on invalidation, but without this patch it actually ignored all the
> other vdef stmts in between those two bbs rather than just starting with no
> known string lengths at the start of the bb.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk/4.8?

Ok.

Thanks,
Richard.

> 2013-08-30  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/58277
> 	* tree-ssa-strlen.c (strlen_enter_block): If do_invalidate gave up
> 	after seeing too many stmts with vdef in between dombb and current
> 	bb, invalidate everything.
> 
> 	* gcc.c-torture/execute/pr58277-1.c: New test.
> 	* gcc.c-torture/execute/pr58277-2.c: New test.
> 
> --- gcc/tree-ssa-strlen.c.jj	2013-08-13 12:20:27.000000000 +0200
> +++ gcc/tree-ssa-strlen.c	2013-08-30 11:02:39.717691590 +0200
> @@ -1952,6 +1952,28 @@ strlen_enter_block (struct dom_walk_data
>  		  int count_vdef = 100;
>  		  do_invalidate (dombb, phi, visited, &count_vdef);
>  		  BITMAP_FREE (visited);
> +		  if (count_vdef == 0)
> +		    {
> +		      /* If there were too many vdefs in between immediate
> +			 dominator and current bb, invalidate everything.
> +			 If stridx_to_strinfo has been unshared, we need
> +			 to free it, otherwise just set it to NULL.  */
> +		      if (!strinfo_shared ())
> +			{
> +			  unsigned int i;
> +			  strinfo si;
> +
> +			  for (i = 1;
> +			       vec_safe_iterate (stridx_to_strinfo, i, &si);
> +			       ++i)
> +			    {
> +			      free_strinfo (si);
> +			      (*stridx_to_strinfo)[i] = NULL;
> +			    }
> +			}
> +		      else
> +			stridx_to_strinfo = NULL;
> +		    }
>  		  break;
>  		}
>  	    }
> --- gcc/testsuite/gcc.c-torture/execute/pr58277-1.c.jj	2013-08-30 11:10:36.590005465 +0200
> +++ gcc/testsuite/gcc.c-torture/execute/pr58277-1.c	2013-08-30 11:10:05.000000000 +0200
> @@ -0,0 +1,102 @@
> +/* PR tree-optimization/58277 */
> +
> +extern void abort (void);
> +static int a[2];
> +int b, c, d, *e, f, g, h, **i = &e, k, l = 1, n, o, p;
> +static int **volatile j = &e;
> +const int m;
> +char u;
> +
> +int
> +bar ()
> +{
> +  u = 0;
> +  return m;
> +}
> +
> +__attribute__((noinline, noclone)) void
> +baz ()
> +{
> +  asm ("");
> +}
> +
> +static int
> +foo ()
> +{
> +  int t1;
> +  g = bar ();
> +  if (l)
> +    ;
> +  else
> +    for (;; h++)
> +      {
> +	*i = 0;
> +	o = *e = 0;
> +	if (p)
> +	  {
> +	    f = 0;
> +	    return 0;
> +	  }
> +	for (;; k++)
> +	  {
> +	    int *t2 = 0;
> +	    int *const *t3[] = {
> +	      0, 0, 0, 0, 0, 0, 0, 0, 0, &t2, 0, 0, &t2, &t2, &t2,
> +	      &t2, &t2, 0, 0, 0, 0, 0, 0, 0, &t2, 0, 0, 0, 0, 0, 0,
> +	      0, 0, 0, 0, &t2, 0, 0, 0, 0, 0, 0, 0, &t2, &t2,
> +	      &t2, &t2, &t2, 0, 0, 0, 0, 0, 0, 0, &t2, 0, 0, 0,
> +	      &t2, 0, 0, 0, &t2, 0, &t2, 0, 0, &t2, 0, 0, 0, 0,
> +	      0, &t2, 0, 0, 0, 0, &t2, &t2, 0, 0, 0, 0, &t2, 0,
> +	      0, 0, 0, 0, 0, 0, &t2, 0, 0, 0, 0, 0, &t2, 0, 0, 0,
> +	      &t2, &t2
> +	    };
> +	    int *const **t4[] = {&t3[0]};
> +	    **i = 0;
> +	    if (**j)
> +	      break;
> +	    u = 0;
> +	  }
> +	*i = *j;
> +	t1 = 0;
> +	for (; t1 < 5; t1++)
> +	  *i = *j;
> +      }
> +  *j = 0;
> +  return 1;
> +}
> +
> +int
> +main ()
> +{
> +  int t5;
> +  a[0] = 1;
> +  {
> +    int *t6[6] = {&d, &d};
> +    for (n = 1; n; n--)
> +      if (foo())
> +	{
> +	  int *t7[] = {0};
> +	  d = 0;
> +	  for (; u < 1; u++)
> +	    *i = *j;
> +	  *i = 0;
> +	  *i = 0;
> +	  int t8[5] = {0};
> +	  *i = &t8[0];
> +	  int *const *t9 = &t6[0];
> +	  int *const **t10 = &t9;
> +	  *t10 = &t7[0];
> +	}
> +  }
> +  u = 0;
> +  for (; b; b++)
> +    for (t5 = 0; t5 < 10; t5++)
> +      c = a[a[a[a[a[a[a[a[c]]]]]]]];
> +
> +  baz ();
> +
> +  if (!a[a[a[a[a[a[a[a[a[a[a[a[a[a[a[u]]]]]]]]]]]]]]])
> +    abort ();
> +
> +  return 0;
> +}
> --- gcc/testsuite/gcc.c-torture/execute/pr58277-2.c.jj	2013-08-30 11:10:39.613988421 +0200
> +++ gcc/testsuite/gcc.c-torture/execute/pr58277-2.c	2013-08-30 11:06:17.000000000 +0200
> @@ -0,0 +1,98 @@
> +/* PR tree-optimization/58277 */
> +
> +extern void abort (void);
> +static int a[1], b, c, e, i, j, k, m, q[] = { 1, 1 }, t;
> +int volatile d;
> +int **r;
> +static int ***volatile s = &r;
> +int f, g, o, x;
> +static int *volatile h = &f, *p;
> +char n;
> +
> +static void
> +fn1 ()
> +{
> +  b = a[a[a[a[a[a[a[a[b]]]]]]]];
> +  b = a[a[a[a[a[a[a[a[b]]]]]]]];
> +  b = a[a[b]];
> +  b = a[a[a[a[a[a[a[a[b]]]]]]]];
> +  b = a[a[a[a[a[a[a[a[b]]]]]]]];
> +}
> +
> +static int
> +fn2 ()
> +{
> +  n = 0;
> +  for (; g; t++)
> +    {
> +      for (;; m++)
> +	{
> +	  d;
> +	  int *u;
> +	  int **v[] = {
> +	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> +	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> +	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> +	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> +	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> +	    0, 0, 0, 0, 0, &u, 0, 0, 0, 0, &u, &u, &u, &u, &u, &u, &u, 0,
> +	    &u, 0, &u, &u, &u, 0, &u, &u, 0, &u, &u, &u, &u, 0, &u, &u, &u,
> +	    &u, &u, 0, &u, &u, 0, &u, 0, &u, &u, 0, &u, &u, &u, &u, &u, 0,
> +	    &u, 0, 0, 0, &u, &u, &u, 0, 0, &u, &u, &u, 0, &u, 0, &u, &u
> +	  };
> +	  int ***w[] = { &v[0] };
> +	  if (*p)
> +	    break;
> +	  return 0;
> +	}
> +      *h = 0;
> +    }
> +  return 1;
> +}
> +
> +static void
> +fn3 ()
> +{
> +  int *y[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
> +  for (; i; i++)
> +    x = 0;
> +  if (fn2 ())
> +    {
> +      int *z[6] = { };
> +      for (; n < 1; n++)
> +	*h = 0;
> +      int t1[7];
> +      for (; c; c++)
> +	o = t1[0];
> +      for (; e; e--)
> +	{
> +	  int **t2 = &y[0];
> +	  int ***t3 = &t2;
> +	  *t3 = &z[0];
> +	}
> +    }
> +  *s = 0;
> +  for (n = 0;; n = 0)
> +    {
> +      int t4 = 0;
> +      if (q[n])
> +	break;
> +      *r = &t4;
> +    }
> +}
> +
> +int
> +main ()
> +{
> +  for (; j; j--)
> +    a[0] = 0;
> +  fn3 ();
> +  for (; k; k++)
> +    fn1 ();
> +  fn1 ();
> + 
> +  if (n)
> +    abort ();
> +
> +  return 0;
> +}
> 
> 	Jakub
> 
>

Patch

--- gcc/tree-ssa-strlen.c.jj	2013-08-13 12:20:27.000000000 +0200
+++ gcc/tree-ssa-strlen.c	2013-08-30 11:02:39.717691590 +0200
@@ -1952,6 +1952,28 @@  strlen_enter_block (struct dom_walk_data
 		  int count_vdef = 100;
 		  do_invalidate (dombb, phi, visited, &count_vdef);
 		  BITMAP_FREE (visited);
+		  if (count_vdef == 0)
+		    {
+		      /* If there were too many vdefs in between immediate
+			 dominator and current bb, invalidate everything.
+			 If stridx_to_strinfo has been unshared, we need
+			 to free it, otherwise just set it to NULL.  */
+		      if (!strinfo_shared ())
+			{
+			  unsigned int i;
+			  strinfo si;
+
+			  for (i = 1;
+			       vec_safe_iterate (stridx_to_strinfo, i, &si);
+			       ++i)
+			    {
+			      free_strinfo (si);
+			      (*stridx_to_strinfo)[i] = NULL;
+			    }
+			}
+		      else
+			stridx_to_strinfo = NULL;
+		    }
 		  break;
 		}
 	    }
--- gcc/testsuite/gcc.c-torture/execute/pr58277-1.c.jj	2013-08-30 11:10:36.590005465 +0200
+++ gcc/testsuite/gcc.c-torture/execute/pr58277-1.c	2013-08-30 11:10:05.000000000 +0200
@@ -0,0 +1,102 @@ 
+/* PR tree-optimization/58277 */
+
+extern void abort (void);
+static int a[2];
+int b, c, d, *e, f, g, h, **i = &e, k, l = 1, n, o, p;
+static int **volatile j = &e;
+const int m;
+char u;
+
+int
+bar ()
+{
+  u = 0;
+  return m;
+}
+
+__attribute__((noinline, noclone)) void
+baz ()
+{
+  asm ("");
+}
+
+static int
+foo ()
+{
+  int t1;
+  g = bar ();
+  if (l)
+    ;
+  else
+    for (;; h++)
+      {
+	*i = 0;
+	o = *e = 0;
+	if (p)
+	  {
+	    f = 0;
+	    return 0;
+	  }
+	for (;; k++)
+	  {
+	    int *t2 = 0;
+	    int *const *t3[] = {
+	      0, 0, 0, 0, 0, 0, 0, 0, 0, &t2, 0, 0, &t2, &t2, &t2,
+	      &t2, &t2, 0, 0, 0, 0, 0, 0, 0, &t2, 0, 0, 0, 0, 0, 0,
+	      0, 0, 0, 0, &t2, 0, 0, 0, 0, 0, 0, 0, &t2, &t2,
+	      &t2, &t2, &t2, 0, 0, 0, 0, 0, 0, 0, &t2, 0, 0, 0,
+	      &t2, 0, 0, 0, &t2, 0, &t2, 0, 0, &t2, 0, 0, 0, 0,
+	      0, &t2, 0, 0, 0, 0, &t2, &t2, 0, 0, 0, 0, &t2, 0,
+	      0, 0, 0, 0, 0, 0, &t2, 0, 0, 0, 0, 0, &t2, 0, 0, 0,
+	      &t2, &t2
+	    };
+	    int *const **t4[] = {&t3[0]};
+	    **i = 0;
+	    if (**j)
+	      break;
+	    u = 0;
+	  }
+	*i = *j;
+	t1 = 0;
+	for (; t1 < 5; t1++)
+	  *i = *j;
+      }
+  *j = 0;
+  return 1;
+}
+
+int
+main ()
+{
+  int t5;
+  a[0] = 1;
+  {
+    int *t6[6] = {&d, &d};
+    for (n = 1; n; n--)
+      if (foo())
+	{
+	  int *t7[] = {0};
+	  d = 0;
+	  for (; u < 1; u++)
+	    *i = *j;
+	  *i = 0;
+	  *i = 0;
+	  int t8[5] = {0};
+	  *i = &t8[0];
+	  int *const *t9 = &t6[0];
+	  int *const **t10 = &t9;
+	  *t10 = &t7[0];
+	}
+  }
+  u = 0;
+  for (; b; b++)
+    for (t5 = 0; t5 < 10; t5++)
+      c = a[a[a[a[a[a[a[a[c]]]]]]]];
+
+  baz ();
+
+  if (!a[a[a[a[a[a[a[a[a[a[a[a[a[a[a[u]]]]]]]]]]]]]]])
+    abort ();
+
+  return 0;
+}
--- gcc/testsuite/gcc.c-torture/execute/pr58277-2.c.jj	2013-08-30 11:10:39.613988421 +0200
+++ gcc/testsuite/gcc.c-torture/execute/pr58277-2.c	2013-08-30 11:06:17.000000000 +0200
@@ -0,0 +1,98 @@ 
+/* PR tree-optimization/58277 */
+
+extern void abort (void);
+static int a[1], b, c, e, i, j, k, m, q[] = { 1, 1 }, t;
+int volatile d;
+int **r;
+static int ***volatile s = &r;
+int f, g, o, x;
+static int *volatile h = &f, *p;
+char n;
+
+static void
+fn1 ()
+{
+  b = a[a[a[a[a[a[a[a[b]]]]]]]];
+  b = a[a[a[a[a[a[a[a[b]]]]]]]];
+  b = a[a[b]];
+  b = a[a[a[a[a[a[a[a[b]]]]]]]];
+  b = a[a[a[a[a[a[a[a[b]]]]]]]];
+}
+
+static int
+fn2 ()
+{
+  n = 0;
+  for (; g; t++)
+    {
+      for (;; m++)
+	{
+	  d;
+	  int *u;
+	  int **v[] = {
+	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	    0, 0, 0, 0, 0, &u, 0, 0, 0, 0, &u, &u, &u, &u, &u, &u, &u, 0,
+	    &u, 0, &u, &u, &u, 0, &u, &u, 0, &u, &u, &u, &u, 0, &u, &u, &u,
+	    &u, &u, 0, &u, &u, 0, &u, 0, &u, &u, 0, &u, &u, &u, &u, &u, 0,
+	    &u, 0, 0, 0, &u, &u, &u, 0, 0, &u, &u, &u, 0, &u, 0, &u, &u
+	  };
+	  int ***w[] = { &v[0] };
+	  if (*p)
+	    break;
+	  return 0;
+	}
+      *h = 0;
+    }
+  return 1;
+}
+
+static void
+fn3 ()
+{
+  int *y[] = { 0, 0, 0, 0, 0, 0, 0, 0 };
+  for (; i; i++)
+    x = 0;
+  if (fn2 ())
+    {
+      int *z[6] = { };
+      for (; n < 1; n++)
+	*h = 0;
+      int t1[7];
+      for (; c; c++)
+	o = t1[0];
+      for (; e; e--)
+	{
+	  int **t2 = &y[0];
+	  int ***t3 = &t2;
+	  *t3 = &z[0];
+	}
+    }
+  *s = 0;
+  for (n = 0;; n = 0)
+    {
+      int t4 = 0;
+      if (q[n])
+	break;
+      *r = &t4;
+    }
+}
+
+int
+main ()
+{
+  for (; j; j--)
+    a[0] = 0;
+  fn3 ();
+  for (; k; k++)
+    fn1 ();
+  fn1 ();
+ 
+  if (n)
+    abort ();
+
+  return 0;
+}