PR 80769: Incorrect strlen optimisation

In this testcase, we (correctly) record after:

  strcpy (p1, "abcde");
  char *p2 = strchr (p1, '\0');
  strcpy (p2, q);

that the length of p1 and p2 can be calculated by converting the
second strcpy to:

  tmp = stpcpy (p2, q)

and then doing tmp - p1 for p1 and tmp - p2 for p2.  This is delayed
until we know whether we actually need it.  Then:

  char *p3 = strchr (p2, '\0');

forces us to calculate the length of p2 in this way.  At this point
we had three related strinfos:

  p1: delayed length, calculated from tmp = stpcpy (p2, q)
  p2: known length, tmp - p2
  p3: known length, 0

After:

  memcpy (p3, "x", 2);

we use adjust_related_strinfos to add 1 to each length.  However,
that didn't do anything for delayed lengths because:

	  else if (si->stmt != NULL)
	    /* Delayed length computation is unaffected.  */
	    ;

So after the memcpy we had:

  p1: delayed length, calculated from tmp = stpcpy (p2, q)
  p2: known length, tmp - p2 + 1
  p3: known length, 1

where the length of p1 was no longer correct.

2017-05-16  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	PR tree-optimization/80769
	* tree-ssa-strlen.c (strinfo): Document that "stmt" is also used
	for malloc and calloc.  Document the new invariant that all related
	strinfos have delayed lengths or none do.
	(verify_related_strinfos): Move earlier in file.
	(set_endptr_and_length): New function, split out from...
	(get_string_length): ...here.  Also set the lengths of related
	strinfos.
	(zero_length_string): Assert that chainsi has known (rather than
	delayed) lengths.
	(adjust_related_strinfos): Likewise.

gcc/testsuite/
	PR tree-optimization/80769
	* gcc.dg/strlenopt-31.c: New test.
	* gcc.dg/strlenopt-31g.c: Likewise.

From-SVN: r249879

5 files changed, 125 insertions, 51 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 76944d5..67019a5 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,19 @@
 2017-07-02  Richard Sandiford  <richard.sandiford@linaro.org>
 
+	PR tree-optimization/80769
+	* tree-ssa-strlen.c (strinfo): Document that "stmt" is also used
+	for malloc and calloc.  Document the new invariant that all related
+	strinfos have delayed lengths or none do.
+	(verify_related_strinfos): Move earlier in file.
+	(set_endptr_and_length): New function, split out from...
+	(get_string_length): ...here.  Also set the lengths of related
+	strinfos.
+	(zero_length_string): Assert that chainsi has known (rather than
+	delayed) lengths.
+	(adjust_related_strinfos): Likewise.
+
+2017-07-02  Richard Sandiford  <richard.sandiford@linaro.org>
+
 	PR tree-optimization/81136
 	* tree-vect-data-refs.c (vect_update_misalignment_for_peel): Only
 	assert that two references with the same misalignment have the same
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 4625921..e4c6af6 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,11 @@
 2017-07-02  Richard Sandiford  <richard.sandiford@linaro.org>
 
+	PR tree-optimization/80769
+	* gcc.dg/strlenopt-31.c: New test.
+	* gcc.dg/strlenopt-31g.c: Likewise.
+
+2017-07-02  Richard Sandiford  <richard.sandiford@linaro.org>
+
 	PR tree-optimization/81136
 	* gcc.dg/vect/pr81136.c: New test.
 
diff --git a/gcc/testsuite/gcc.dg/strlenopt-31.c b/gcc/testsuite/gcc.dg/strlenopt-31.c
new file mode 100644
index 0000000..bdd46ba
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/strlenopt-31.c
@@ -0,0 +1,25 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+#include "strlenopt.h"
+
+__attribute__((noinline, noclone)) int
+bar (char *p1, const char *q)
+{
+  strcpy (p1, "abcde");
+  char *p2 = strchr (p1, '\0');
+  strcpy (p2, q);
+  char *p3 = strchr (p2, '\0');
+  memcpy (p3, "x", 2);
+  return strlen (p1);
+}
+
+int
+main (void)
+{
+  char buffer[10];
+  int res = bar (buffer, "foo");
+  if (strcmp (buffer, "abcdefoox") != 0 || res != 9)
+    abort ();
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/strlenopt-31g.c b/gcc/testsuite/gcc.dg/strlenopt-31g.c
new file mode 100644
index 0000000..45cc29c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/strlenopt-31g.c
@@ -0,0 +1,9 @@
+/* { dg-do run { target *-*-linux* *-*-gnu* } } */
+/* { dg-options "-O2 -fdump-tree-strlen" } */
+
+#define USE_GNU
+#include "strlenopt-31.c"
+
+/* { dg-final { scan-tree-dump-times "stpcpy \\(" 1 "strlen" } } */
+/* { dg-final { scan-tree-dump-times "memcpy \\(" 2 "strlen" } } */
+/* { dg-final { scan-tree-dump-not "strlen \\(" "strlen" } } */
diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
index e4f18db..f46e64d 100644
--- a/gcc/tree-ssa-strlen.c
+++ b/gcc/tree-ssa-strlen.c
@@ -61,7 +61,13 @@ struct strinfo
   tree length;
   /* Any of the corresponding pointers for querying alias oracle.  */
   tree ptr;
-  /* Statement for delayed length computation.  */
+  /* This is used for two things:
+
+     - To record the statement that should be used for delayed length
+       computations.  We maintain the invariant that all related strinfos
+       have delayed lengths or none do.
+
+     - To record the malloc or calloc call that produced this result.  */
   gimple *stmt;
   /* Pointer to '\0' if known, if NULL, it can be computed as
      ptr + length.  */
@@ -451,6 +457,45 @@ set_strinfo (int idx, strinfo *si)
   (*stridx_to_strinfo)[idx] = si;
 }
 
+/* Return the first strinfo in the related strinfo chain
+   if all strinfos in between belong to the chain, otherwise NULL.  */
+
+static strinfo *
+verify_related_strinfos (strinfo *origsi)
+{
+  strinfo *si = origsi, *psi;
+
+  if (origsi->first == 0)
+    return NULL;
+  for (; si->prev; si = psi)
+    {
+      if (si->first != origsi->first)
+	return NULL;
+      psi = get_strinfo (si->prev);
+      if (psi == NULL)
+	return NULL;
+      if (psi->next != si->idx)
+	return NULL;
+    }
+  if (si->idx != si->first)
+    return NULL;
+  return si;
+}
+
+/* Set SI's endptr to ENDPTR and compute its length based on SI->ptr.
+   Use LOC for folding.  */
+
+static void
+set_endptr_and_length (location_t loc, strinfo *si, tree endptr)
+{
+  si->endptr = endptr;
+  si->stmt = NULL;
+  tree start_as_size = fold_convert_loc (loc, size_type_node, si->ptr);
+  tree end_as_size = fold_convert_loc (loc, size_type_node, endptr);
+  si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
+				end_as_size, start_as_size);
+}
+
 /* Return string length, or NULL if it can't be computed.  */
 
 static tree
@@ -546,12 +591,12 @@ get_string_length (strinfo *si)
 	case BUILT_IN_STPCPY_CHK_CHKP:
 	  gcc_assert (lhs != NULL_TREE);
 	  loc = gimple_location (stmt);
-	  si->endptr = lhs;
-	  si->stmt = NULL;
-	  lhs = fold_convert_loc (loc, size_type_node, lhs);
-	  si->length = fold_convert_loc (loc, size_type_node, si->ptr);
-	  si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node,
-					lhs, si->length);
+	  set_endptr_and_length (loc, si, lhs);
+	  for (strinfo *chainsi = verify_related_strinfos (si);
+	       chainsi != NULL;
+	       chainsi = get_next_strinfo (chainsi))
+	    if (chainsi->length == NULL)
+	      set_endptr_and_length (loc, chainsi, lhs);
 	  break;
 	case BUILT_IN_MALLOC:
 	  break;
@@ -620,32 +665,6 @@ unshare_strinfo (strinfo *si)
   return nsi;
 }
 
-/* Return first strinfo in the related strinfo chain
-   if all strinfos in between belong to the chain, otherwise
-   NULL.  */
-
-static strinfo *
-verify_related_strinfos (strinfo *origsi)
-{
-  strinfo *si = origsi, *psi;
-
-  if (origsi->first == 0)
-    return NULL;
-  for (; si->prev; si = psi)
-    {
-      if (si->first != origsi->first)
-	return NULL;
-      psi = get_strinfo (si->prev);
-      if (psi == NULL)
-	return NULL;
-      if (psi->next != si->idx)
-	return NULL;
-    }
-  if (si->idx != si->first)
-    return NULL;
-  return si;
-}
-
 /* Attempt to create a new strinfo for BASESI + OFF, or find existing
    strinfo if there is any.  Return it's idx, or 0 if no strinfo has
    been created.  */
@@ -749,7 +768,8 @@ zero_length_string (tree ptr, strinfo *chainsi)
 	{
 	  do
 	    {
-	      gcc_assert (si->length || si->stmt);
+	      /* We shouldn't mix delayed and non-delayed lengths.  */
+	      gcc_assert (si->length);
 	      if (si->endptr == NULL_TREE)
 		{
 		  si = unshare_strinfo (si);
@@ -770,12 +790,17 @@ zero_length_string (tree ptr, strinfo *chainsi)
 	      return chainsi;
 	    }
 	}
-      else if (chainsi->first || chainsi->prev || chainsi->next)
+      else
 	{
-	  chainsi = unshare_strinfo (chainsi);
-	  chainsi->first = 0;
-	  chainsi->prev = 0;
-	  chainsi->next = 0;
+	  /* We shouldn't mix delayed and non-delayed lengths.  */
+	  gcc_assert (chainsi->length);
+	  if (chainsi->first || chainsi->prev || chainsi->next)
+	    {
+	      chainsi = unshare_strinfo (chainsi);
+	      chainsi->first = 0;
+	      chainsi->prev = 0;
+	      chainsi->next = 0;
+	    }
 	}
     }
   idx = new_stridx (ptr);
@@ -820,18 +845,13 @@ adjust_related_strinfos (location_t loc, strinfo *origsi, tree adj)
 	  tree tem;
 
 	  si = unshare_strinfo (si);
-	  if (si->length)
-	    {
-	      tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
-	      si->length = fold_build2_loc (loc, PLUS_EXPR,
-					    TREE_TYPE (si->length), si->length,
-					    tem);
-	    }
-	  else if (si->stmt != NULL)
-	    /* Delayed length computation is unaffected.  */
-	    ;
-	  else
-	    gcc_unreachable ();
+	  /* We shouldn't see delayed lengths here; the caller must have
+	     calculated the old length in order to calculate the
+	     adjustment.  */
+	  gcc_assert (si->length);
+	  tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj);
+	  si->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (si->length),
+					si->length, tem);
 
 	  si->endptr = NULL_TREE;
 	  si->dont_invalidate = true;