[PATCH] fix and improve strlen conditional handling of merged stores (PR 91183, 91294, 91315)

public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed

* [PATCH] fix and improve strlen conditional handling of merged stores (PR 91183, 91294, 91315)
@ 2019-08-01  0:36 Martin Sebor
  2019-08-09  7:15 ` Jeff Law
  0 siblings, 1 reply; 6+ messages in thread
From: Martin Sebor @ 2019-08-01  0:36 UTC (permalink / raw)
  To: gcc-patches, Jeff Law

[-- Attachment #1: Type: text/plain, Size: 1357 bytes --]

More extensive testing of the last week's strlen patch for
PR91183 on various non-mainstream targets and with better tests
has exposed a few gaps and a couple of bugs.  The attached patch
addresses all in one change.  I considered splitting it up but
in the end decided the changes were small and sufficiently
isolated that it wasn't necessary.  (If someone feels strongly
otherwise it can be easily split t up.)

The wrong-code bug (PR 91294) is due to handle_store neglecting
to fully consider the case when a single multi-byte store
involving a PHI of two "strings" the same size (so they are merged
into a single int store) but of unequal length.  The function
simply takes the length of the shorter string as the resulting
length when it needs to only set the lower bound of the length
(it does that treating the result as potentially not nul-
terminated).

The gaps are in not handling some MEM_REF forms that come up
in multi-byte assignments (this is the rest of PR 91183 and was
exposed on strictly aligned targets), and in handle_builtin_strlen
discarding the lower bound on a string length instead of exposing
it to downstream passes.  This is PR 91315 that was exposed by
a few cases in the existing tests for PR 91294 failing after
the fix for PR 91294.

Tested on x86_64-linux and spot-checked with a sparc-solaris2.11
cross-compiler.

Martin

[-- Attachment #2: gcc-91294-2.diff --]
[-- Type: text/x-patch, Size: 32541 bytes --]

PR tree-optimization/91315 - missing strlen lower bound of a string known to be at least N characters
PR tree-optimization/91294 - wrong strlen result of a conditional with an offset
PR tree-optimization/91183 - strlen of a strcpy result with a conditional source not folded

gcc/testsuite/ChangeLog:

	PR tree-optimization/91315
	PR tree-optimization/91294
	PR tree-optimization/91183
	* gcc.dg/strlenopt-44.c: Avoid using length of 1.
	* gcc.dg/strlenopt-70.c: Disable overly optimistic tests.
	* gcc.dg/strlenopt-73.c: New test.
	* gcc.dg/strlenopt-74.c: New test.
	* gcc.dg/strlenopt-75.c: New test.
	* gcc.dg/strlenopt-76.c: New test.
	* gcc.dg/strlenopt-77.c: New test.

gcc/ChangeLog:

	PR tree-optimization/91315
	PR tree-optimization/91294
	PR tree-optimization/91183
	* gimple-fold.c (gimple_fold_builtin_strlen): Add expected argument.
	* tree-ssa-strlen.c (set_strlen_range): Add function argument.
	(maybe_set_strlen_range): Add expected argument.
	(handle_builtin_strlen): Call set_strlen_range.
	(count_nonzero_bytes): Add function arguments.  Handle strinfo
	first.  Handle "single" assignment.
	(handle_store): Set the lower bound of length for multibyte stores
	of unequal lengths.
	* tree-ssa-strlen.h (set_strlen_range): Add function argument.

Index: gcc/gimple-fold.c
===================================================================
--- gcc/gimple-fold.c	(revision 273914)
+++ gcc/gimple-fold.c	(working copy)
@@ -3751,7 +3751,7 @@ gimple_fold_builtin_strlen (gimple_stmt_iterator *
 
   /* Set the strlen() range to [0, MAXLEN].  */
   if (tree lhs = gimple_call_lhs (stmt))
-    set_strlen_range (lhs, maxlen);
+    set_strlen_range (lhs, minlen, maxlen);
 
   return false;
 }
Index: gcc/testsuite/gcc.dg/strlenopt-44.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-44.c	(revision 273914)
+++ gcc/testsuite/gcc.dg/strlenopt-44.c	(working copy)
@@ -83,7 +83,7 @@ void test_keep (void)
   size_t uchar_max = (unsigned char)-1;
 
   KEEP ("1",     0, UR (1, uchar_max + 1), 1);
-  KEEP ("1\0\3", 1, UR (1, 2), 1);
+  KEEP ("1\0\3", 1, UR (1, 2), 2);
 }
 
 /* { dg-final { scan-tree-dump-times "call_in_true_branch_not_eliminated_" 0 "optimized" } }
Index: gcc/testsuite/gcc.dg/strlenopt-70.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-70.c	(revision 273914)
+++ gcc/testsuite/gcc.dg/strlenopt-70.c	(working copy)
@@ -201,14 +201,17 @@ void store_32bit (volatile int i)
   T ("xxx",  uint32_t, 0, I32 ("\1\2\3\0"), == 3);
   T ("xxx",  uint32_t, 0, I32 ("\0\1\2\3"), == 0);
 
-  uint32_t x00332211 = I32 ("123\0");
-  uint32_t x00002211 = I32 ("12\0\0");
-  uint32_t x00000011 = I32 ("1\0\0\0");
+  uint32_t x123_ = I32 ("123\0");
+  uint32_t x12__ = I32 ("12\0\0");
+  uint32_t x1___ = I32 ("1\0\0\0");
 
-  T ("xxxx", uint32_t, 0, i ? x00332211 : x00002211, <= 3);
-  T ("xxxx", uint32_t, 0, i ? x00332211 : x00002211, >= 2);
-  T ("xxxx", uint32_t, 0, i ? x00332211 : x00000011, <= 3);
-  T ("xxxx", uint32_t, 0, i ? x00332211 : x00000011, >= 1);
+  // FIXME: Upper bound not implemented yet.
+  /* T ("xxxx", uint32_t, 0, i ? x123_ : x12__, <= 3); */
+  T ("xxxx", uint32_t, 0, i ? x123_ : x12__, >= 2);
+  T ("xxxx", uint32_t, 0, i ? x12__ : x123_, >= 2);
+  /* T ("xxxx", uint32_t, 0, i ? x123_ : x1___, <= 3); */
+  T ("xxxx", uint32_t, 0, i ? x123_ : x1___, >= 1);
+  T ("xxxx", uint32_t, 0, i ? x1___ : x123_, >= 1);
 
   TX ("abcde",  uint32_t, 0, i ? I32 ("1234") : I32 ("1235"), == 5);
   TX ("abcde",  uint32_t, 1, i ? I32 ("1234") : I32 ("1235"), == 5);
@@ -220,7 +223,8 @@ void store_32bit (volatile int i)
   TX ("abcdef", uint32_t, 3, i ? I32 ("12\0\0") : I32 ("13\0\0"), == 5);
 
   TX ("abcdef", uint32_t, 3, i ? I32 ("12\0\0") : I32 ("123\0"), >= 5);
-  TX ("abcdef", uint32_t, 3, i ? I32 ("12\0\0") : I32 ("123\0"), < 7);
+  /* FIXME: Upper bound not implemented yet.  */
+  /* TX ("abcdef", uint32_t, 3, i ? I32 ("12\0\0") : I32 ("123\0"), < 7); */
 }
 
 void store_64bit (int i)
@@ -246,17 +250,19 @@ void store_64bit (int i)
   T ("xxxxxxx", uint64_t, 0, I64 ("\1\2\3\4\5\6\0\0\0"), == 6);
   T ("xxxxxxx", uint64_t, 0, I64 ("\1\2\3\4\5\6\7\0\0"), == 7);
 
-  uint64_t x7777777 = I64 ("\7\7\7\7\7\7\7");
-  uint64_t x666666 = I64 ("\6\6\6\6\6\6\0");
-  uint64_t x4444 = I64 ("\4\4\4\4\0\0\0");
-  uint64_t x3333 = I64 ("\3\3\3\3\0\0\0");
-  uint64_t x1 = I64 ("\1\0\0\0\0\0\0");
+  uint64_t x7777777_ = I64 ("\7\7\7\7\7\7\7");
+  uint64_t x666666__ = I64 ("\6\6\6\6\6\6\0");
+  uint64_t x4444____ = I64 ("\4\4\4\4\0\0\0");
+  uint64_t x4343____ = I64 ("\4\3\4\3\0\0\0");
+  uint64_t x1_______ = I64 ("\1\0\0\0\0\0\0");
 
-  T ("x\0xxxxxx", uint64_t, 0, i ? x7777777 : x666666, <= 7);
-  T ("xx\0xxxxx", uint64_t, 0, i ? x7777777 : x666666, >= 6);
-  T ("xxx\0xxxx", uint64_t, 0, i ? x666666 : x1, <= 6);
-  T ("xxxx\0xxx", uint64_t, 0, i ? x666666 : x1, >= 1);
-  T ("xxxxxx\0x", uint64_t, 0, i ? x4444 : x3333, == 4);
+  /* FIXME: Upper bound not implemented yet.  */
+  /* T ("x\0xxxxxx", uint64_t, 0, i ? x7777777_ : x666666__, <= 7); */
+  T ("xx\0xxxxx", uint64_t, 0, i ? x7777777_ : x666666__, >= 6);
+  T ("xxx\0xxxx", uint64_t, 1, i ? x7777777_ : x666666__, >= 7);
+  /* T ("xxx\0xxxx", uint64_t, 0, i ? x666666__ : x1, <= 6); */
+  T ("xxxx\0xxx", uint64_t, 0, i ? x666666__ : x1_______, >= 1);
+  T ("xxxxxx\0x", uint64_t, 0, i ? x4444____ : x4343____, == 4);
 }
 
 #if __SIZEOF_INT128__
Index: gcc/testsuite/gcc.dg/strlenopt-73.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-73.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-73.c	(working copy)
@@ -0,0 +1,94 @@
+/* PR tree-optimization/91183 - strlen of a strcpy result with a conditional
+   source not folded
+   Test to verify that strlen can determine string lengths from stores
+   involving PHI nodes with distinct strings of the same length of at
+   least 16 bytes.
+
+   { dg-do compile }
+   { dg-options "-O2 -fdump-tree-optimized" }
+   On strictly aligned targets the consecutive char assignments used
+   by the test aren't merged.  When they involve multiple trailing nuls
+   these assignments then defeat the strlen optimization as a result of
+   pr83821.  When the bug is resolved the directive below can be removed.
+   { dg-require-effective-target non_strict_align } */
+
+#include "strlenopt.h"
+
+#define CAT(x, y) x ## y
+#define CONCAT(x, y) CAT (x, y)
+#define FAILNAME(name) CONCAT (call_ ## name ##_on_line_, __LINE__)
+
+#define FAIL(name) do {				\
+    extern void FAILNAME (name) (void);		\
+    FAILNAME (name)();				\
+  } while (0)
+
+/* Macros to emit a call to function named
+     call_failed_to_be_eliminated_on_line_NNN()
+   for each call that's expected to be eliminated.  The dg-final
+   scan-tree-dump-time directive at the bottom of the test verifies
+   that no such call appears in output.  */
+#define ELIM(expr)					\
+  if ((expr)) FAIL (not_eliminated); else (void)0
+
+#define T(N, ncpy, expect, cond) do {		\
+    char CONCAT (arr_, __LINE__)[N];		\
+    char *pa = CONCAT (arr_, __LINE__);		\
+    memcpy (pa, cond, ncpy);			\
+    ELIM (!(expect == strlen (pa)));		\
+    sink (pa);					\
+  } while (0)
+
+void sink (void*);
+
+const char a32[33] = "0123456789abcdef0123456789abcdef";
+const char b32[33] = "fedcba9876543210fedcba9876543210";
+
+const char a16[17] = "0123456789abcdef";
+const char b16[17] = "fedcba9876543210";
+
+int i0, i1, i2;
+
+void test_copy_cond_equal_length (void)
+{
+  // The test below is represented as this:
+  //   # iftmp.0_3 = PHI <&b16(2), &a16(3)>
+  //   MEM <unsigned char[17]> [(char * {ref-all})&a]
+  //     = MEM <unsigned char[17]> [(char * {ref-all})iftmp.0_3];
+  //   _2 = strlen (&a);
+  T (17, 17, 16, i0 ? a16 : b16);
+  T (17, 17, 16, i0 ? a16 : b16);
+  T (17, 16, 15, (i0 ? a16 : b16) +  1);
+  T (17, 15, 14, (i0 ? a16 : b16) +  2);
+  T (17,  1,  0, (i0 ? a16 : b16) + 16);
+
+  T (33, 32, 31, (i0 ? a32 : b32) +  1);
+  T (33, 31, 30, (i0 ? a32 : b32) +  2);
+  T (33, 30, 29, (i0 ? a32 : b32) +  3);
+  T (33,  2,  1, (i0 ? a32 : b32) + 31);
+  T (33,  1,  0, (i0 ? a32 : b32) + 32);
+}
+
+
+void test_copy_cond_unequal_length (void)
+{
+  // The test below is represented as this:
+  //   # iftmp.0_3 = PHI <&b16(2), &a16(3)>
+  //   MEM <unsigned char[17]> [(char * {ref-all})&a]
+  //     = MEM <unsigned char[17]> [(char * {ref-all})iftmp.0_3];
+  //   _2 = strlen (&a);
+  T (17, 17, 16, i0 ? a16 : b16);
+  T (17, 17, 16, i0 ? a16 : b16);
+  T (17, 16, 15, (i0 ? a16 : b16) +  1);
+  T (17, 15, 14, (i0 ? a16 : b16) +  2);
+  T (17,  1,  0, (i0 ? a16 : b16) + 16);
+
+  T (33, 32, 31, (i0 ? a32 : b32) +  1);
+  T (33, 31, 30, (i0 ? a32 : b32) +  2);
+  T (33, 30, 29, (i0 ? a32 : b32) +  3);
+  T (33,  2,  1, (i0 ? a32 : b32) + 31);
+  T (33,  1,  0, (i0 ? a32 : b32) + 32);
+}
+
+/* { dg-final { scan-tree-dump-times "strlen" 0 "optimized" } }
+   { dg-final { scan-tree-dump-times "_not_eliminated_" 0 "optimized" } } */
Index: gcc/testsuite/gcc.dg/strlenopt-74.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-74.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-74.c	(working copy)
@@ -0,0 +1,121 @@
+/* PR tree-optimization/91294 - wrong strlen result of a conditional with
+   an offset
+   { dg-do run }
+   { dg-options "-O2 -Wall" } */
+
+#include "strlenopt.h"
+
+#define NOIPA __attribute__ ((noclone, noinline, noipa))
+
+#define CAT(a, b) a ## b
+#define CONCAT(a, b) CAT (a, b)
+#define UNIQ_NAME(name) CONCAT (name, __LINE__)
+
+extern int last_line;
+int nfails;
+
+#define VERIFY(expr, nbytes, expect)					\
+  NOIPA void UNIQ_NAME (test_)(void)					\
+  {									\
+    char buf[32];							\
+    memcpy (buf, (expr), (nbytes));					\
+    const size_t len = strlen (buf);					\
+    if (len != expect)							\
+      {									\
+	++nfails;							\
+	__builtin_printf ("line %i: strlen(%s) == %zu failed: "		\
+			  "got %zu\n",					\
+			  __LINE__ - 1000 + last_line + 2,		\
+			  #expr, (size_t)expect,			\
+			  len);						\
+      }									\
+  } typedef void DummyType
+
+const char a8[12] = "01234567\0\0\0";
+const char b8[12] = "76543210\0\0\0";
+
+int i0;
+
+int last_line = __LINE__;
+#line 1000
+VERIFY (i0 ? (a8 + 0) : (b8 + 0), 9, 8);
+VERIFY (i0 ? (a8 + 0) : (b8 + 1), 8, 7);
+VERIFY (i0 ? (a8 + 0) : (b8 + 2), 8, 6);
+VERIFY (i0 ? (a8 + 0) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 0) : (b8 + 3), 8, 5);
+VERIFY (i0 ? (a8 + 0) : (b8 + 3), 7, 5);
+VERIFY (i0 ? (a8 + 0) : (b8 + 3), 6, 5);
+VERIFY (i0 ? (a8 + 0) : (b8 + 4), 8, 4);
+VERIFY (i0 ? (a8 + 0) : (b8 + 4), 7, 4);
+VERIFY (i0 ? (a8 + 0) : (b8 + 4), 6, 4);
+VERIFY (i0 ? (a8 + 0) : (b8 + 4), 5, 4);
+VERIFY (i0 ? (a8 + 0) : (b8 + 5), 7, 3);
+VERIFY (i0 ? (a8 + 0) : (b8 + 5), 6, 3);
+VERIFY (i0 ? (a8 + 0) : (b8 + 5), 5, 3);
+VERIFY (i0 ? (a8 + 0) : (b8 + 5), 4, 3);
+VERIFY (i0 ? (a8 + 0) : (b8 + 6), 3, 2);
+VERIFY (i0 ? (a8 + 0) : (b8 + 7), 2, 1);
+VERIFY (i0 ? (a8 + 1) : (b8 + 0), 8, 8);
+VERIFY (i0 ? (a8 + 2) : (b8 + 0), 7, 8);
+VERIFY (i0 ? (a8 + 1) : (b8 + 1), 8, 7);
+VERIFY (i0 ? (a8 + 1) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 2) : (b8 + 1), 8, 7);   // FAIL
+VERIFY (i0 ? (a8 + 2) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 0) : (b8 + 0), 9, 8);
+VERIFY (i0 ? (a8 + 0) : (b8 + 1), 8, 7);
+VERIFY (i0 ? (a8 + 0) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 1) : (b8 + 0), 9, 8);
+VERIFY (i0 ? (a8 + 2) : (b8 + 0), 9, 8);
+VERIFY (i0 ? (a8 + 1) : (b8 + 1), 8, 7);
+VERIFY (i0 ? (a8 + 1) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 2) : (b8 + 1), 8, 7);   // FAIL
+VERIFY (i0 ? (a8 + 2) : (b8 + 2), 7, 6);
+VERIFY ((i0 ? a8 : b8) + 1, 8, 7);
+VERIFY ((i0 ? a8 : b8) + 2, 8, 6);
+VERIFY ((i0 ? a8 : b8) + 2, 7, 6);
+
+int main (void)
+{
+  test_1000 ();
+  test_1001 ();
+  test_1002 ();
+  test_1003 ();
+  test_1004 ();
+  test_1005 ();
+  test_1006 ();
+  test_1007 ();
+  test_1008 ();
+  test_1009 ();
+
+  test_1010 ();
+  test_1011 ();
+  test_1012 ();
+  test_1013 ();
+  test_1014 ();
+  test_1015 ();
+  test_1016 ();
+  test_1017 ();
+  test_1018 ();
+  test_1019 ();
+
+  test_1020 ();
+  test_1021 ();
+  test_1022 ();
+  test_1023 ();
+  test_1024 ();
+  test_1025 ();
+  test_1026 ();
+  test_1027 ();
+  test_1028 ();
+  test_1029 ();
+
+  test_1030 ();
+  test_1031 ();
+  test_1032 ();
+  test_1033 ();
+  test_1034 ();
+
+  if (nfails)
+    abort ();
+}
+
Index: gcc/testsuite/gcc.dg/strlenopt-75.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-75.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-75.c	(working copy)
@@ -0,0 +1,118 @@
+/* PR tree-optimization/91294 - strlen result of a conditional with
+   an offset
+   { dg-do run }
+   { dg-options "-O2 -Wall" } */
+
+#include "strlenopt.h"
+
+#define NOIPA __attribute__ ((noclone, noinline, noipa))
+
+int i = 0;
+
+const char s[] = "1234567";
+
+char a[32];
+
+/* Exercise a memcpy overwriting a destination string of known length
+   with a source argument involving a conditional expression with strings
+   of unqual lengths, with the selected one being the longer of the two
+   and resulting in no change to the length of the overwritten destination
+   string.  */
+NOIPA void test_memcpy_same_length ()
+{
+  memcpy (a, "123456789a", 11);
+  memcpy (a + 6, i ? "78\0" : "789\0", 4);
+  if (strlen (a) != 9)
+    abort ();
+}
+
+/* Same as above but with strcpy/strcat.  */
+
+NOIPA void test_strcpy_strcat_same_length ()
+{
+  strcpy (a, "12345678");
+  strcat (a, "9a");
+  memcpy (a + 6, i ? "78\0" : "789\0", 4);
+  if (strlen (a) != 9)
+    abort ();
+}
+
+/* Same as above but using a memcpy of a power-of-two size that gets
+   (on some targets) transformed into a single MEM_REF assignment.  */
+
+NOIPA void test_assign_same_length ()
+{
+  memcpy (a, s, 8);
+  memcpy (a + 5, i ? "67\0" : "678\0", 4);
+  if (strlen (a) != 8)
+    abort ();
+}
+
+/* Same as above but resulting in increasing the length of the destination
+   string.  */
+
+NOIPA void test_memcpy_lengthen ()
+{
+  memcpy (a, "123456789a", 11);
+  memcpy (a + 8, i ? "9a\0" : "9ab\0", 4);
+  if (strlen (a) != 11)
+    abort ();
+}
+
+NOIPA void test_strcpy_strcat_lengthen ()
+{
+  strcpy (a, "12345678");
+  strcat (a, "9a");
+  memcpy (a + 8, i ? "9a\0" : "9ab\0", 4);
+  if (strlen (a) != 11)
+    abort ();
+}
+
+NOIPA void test_assign_lengthen ()
+{
+  memcpy (a, s, 8);
+  memcpy (a + 6, i ? "78\0" : "789\0", 4);
+  if (strlen (a) != 9)
+    abort ();
+}
+
+NOIPA void test_memcpy_shorten ()
+{
+  memcpy (a, "123456789a", 11);
+  memcpy (a + 6, i ? "789\0" : "78\0", 4);
+  if (strlen (a) != 8)
+    abort ();
+}
+
+NOIPA void test_strcpy_strcat_shorten ()
+{
+  strcpy (a, "12345678");
+  strcat (a, "9a");
+  memcpy (a + 6, i ? "789\0" : "78\0", 4);
+  if (strlen (a) != 8)
+    abort ();
+}
+
+NOIPA void test_assign_shorten ()
+{
+  memcpy (a, s, 8);
+  memcpy (a + 6, i ? "789\0" : "78\0", 4);
+  if (strlen (a) != 8)
+    abort ();
+}
+
+
+int main (void)
+{
+  test_memcpy_same_length ();
+  test_strcpy_strcat_same_length ();
+  test_assign_same_length ();
+
+  test_memcpy_lengthen ();
+  test_strcpy_strcat_lengthen ();
+  test_assign_lengthen ();
+
+  test_memcpy_shorten ();
+  test_strcpy_strcat_shorten ();
+  test_assign_shorten ();
+}
Index: gcc/testsuite/gcc.dg/strlenopt-76.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-76.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-76.c	(working copy)
@@ -0,0 +1,174 @@
+/* PR tree-optimization/91294 - strlen result of a conditional with
+   an offset
+   { dg-do run }
+   { dg-options "-O2 -Wall" } */
+
+#include "strlenopt.h"
+
+#define NOIPA __attribute__ ((noclone, noinline, noipa))
+
+#define assert(expr)						\
+  ((expr)                                                       \
+   ? (void)0                                                    \
+   : (__builtin_printf ("line %i %s: assertion failed: %s\n",	\
+                        __LINE__, __func__, #expr),		\
+      __builtin_abort ()))
+
+int i = 0;
+
+const char s[] = "1234567";
+
+char a[32];
+
+NOIPA void lower_bound_assign_into_empty (void)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  assert (strlen (a) == 3);
+}
+
+NOIPA void lower_bound_assign_into_longest (void)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  assert (strlen (a) == 31);
+}
+
+
+NOIPA void lower_bound_assign_into_empty_idx_3 (int idx)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  a[idx] = 'x';
+  assert (strlen (a) == 4);
+}
+
+NOIPA void lower_bound_assign_into_longest_idx_2 (int idx)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  a[idx] = '\0';
+  assert (strlen (a) == 2);
+}
+
+
+NOIPA void lower_bound_memcpy_into_empty (void)
+{
+  memcpy (a, "123", 3);
+  assert (strlen (a) == 3);
+}
+
+NOIPA void lower_bound_memcpy_into_longest (void)
+{
+  memcpy (a, "123", 3);
+  assert (strlen (a) == 31);
+}
+
+
+NOIPA void lower_bound_memcpy_memcpy_into_empty (void)
+{
+  memcpy (a, "123", 3);
+  memcpy (a + 2, "345", 3);
+  assert (strlen (a) == 5);
+}
+
+NOIPA void lower_bound_memcpy_memcpy_into_longest (void)
+{
+  memcpy (a, "123", 3);
+  memcpy (a + 2, "345", 3);
+  assert (strlen (a) == 31);
+}
+
+
+NOIPA void memove_forward_strlen (void)
+{
+  char a[] = "123456";
+
+  memmove (a, a + 1, sizeof a - 1);
+
+  assert (strlen (a) == 5);
+}
+
+NOIPA void memove_backward_into_empty_strlen (void)
+{
+  strcpy (a, "123456");
+
+  memmove (a + 1, a, 6);
+
+  assert (strlen (a) == 7);
+}
+
+NOIPA void memove_backward_into_longest_strlen (void)
+{
+  memcpy (a, "123456", 6);
+
+  memmove (a + 1, a, 6);
+
+  assert (strlen (a) == 31);
+}
+
+NOIPA void memove_strcmp (void)
+{
+  /* Test derived from libstdc++-v3's
+     20_util/specialized_algorithms/memory_management_tools/1.cc  */
+
+  char a[] = "123456";
+  char b[] = "000000";
+
+  memmove (b, a, sizeof a);
+
+  assert (strlen (a) == 6);
+  assert (strlen (b) == 6);
+  assert (strcmp (a, b) == 0);
+}
+
+
+int main (void)
+{
+  memset (a, '\0', sizeof a);
+  lower_bound_assign_into_empty ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_assign_into_longest ();
+
+  memset (a, '\0', sizeof a);
+  lower_bound_assign_into_empty_idx_3 (3);
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_assign_into_longest_idx_2 (2);
+
+  memset (a, '\0', sizeof a);
+  lower_bound_memcpy_into_empty ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_memcpy_into_longest ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_memcpy_into_longest ();
+
+  memset (a, '\0', sizeof a);
+  lower_bound_memcpy_memcpy_into_empty ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_memcpy_memcpy_into_longest ();
+
+  memove_forward_strlen ();
+
+  memset (a, '\0', sizeof a);
+  memove_backward_into_empty_strlen ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  memove_backward_into_longest_strlen ();
+
+  memove_strcmp ();
+}
Index: gcc/testsuite/gcc.dg/strlenopt-77.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-77.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-77.c	(working copy)
@@ -0,0 +1,84 @@
+/* PR tree-optimization/91315 - missing strlen lower bound of a string
+   known to be at least N characters
+   { dg-do compile }
+   { dg-options "-O2 -Wall -fdump-tree-optimized" } */
+
+#include "strlenopt.h"
+
+#define CAT(x, y) x ## y
+#define CONCAT(x, y) CAT (x, y)
+#define FAILNAME(name) CONCAT (call_ ## name ##_on_line_, __LINE__)
+
+#define FAIL(name) do {				\
+    extern void FAILNAME (name) (void);		\
+    FAILNAME (name)();				\
+  } while (0)
+
+/* Macro to emit a call to function named
+     call_in_true_branch_not_eliminated_on_line_NNN()
+   for each call that's expected to be eliminated.  The dg-final
+   scan-tree-dump-time directive at the bottom of the test verifies
+   that no such call appears in output.  */
+#define ASSERT_ELIM(expr)						\
+  if (!!(expr)) FAIL (in_true_branch_not_eliminated); else (void)0
+
+char a[32];
+
+void lower_bound_assign_1 (void)
+{
+  a[0] = '1';
+  ASSERT_ELIM (strlen (a) < 1);
+}
+
+void lower_bound_assign_2 (void)
+{
+  a[0] = '1';
+  a[1] = '2';
+  ASSERT_ELIM (strlen (a) < 2);
+}
+
+void lower_bound_assign_3 (void)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  ASSERT_ELIM (strlen (a) < 3);
+}
+
+void lower_bound_memcpy (void)
+{
+  memcpy (a, "123", 3);
+  ASSERT_ELIM (strlen (a) < 3);
+}
+
+void lower_bound_memcpy_memcpy_2 (void)
+{
+  memcpy (a, "123", 3);
+  memcpy (a + 2, "345", 3);
+  ASSERT_ELIM (strlen (a) < 5);
+}
+
+void lower_bound_memcpy_memcpy_3 (void)
+{
+  memcpy (a, "123", 3);
+  memcpy (a + 3, "456", 3);
+  ASSERT_ELIM (strlen (a) < 6);
+}
+
+/* FIXME: Not optimized yet.
+void lower_bound_stpcpy_stpcpy_assign (void)
+{
+  *stpcpy (strcpy (a, "123"), "4567") = '8';
+  ASSERT_ELIM (strlen (a) < 8);
+}
+*/
+
+void lower_bound_strcpy_strcat_assign (void)
+{
+  strcpy (a, "123");
+  strcat (a, "45");
+  a[5] = '6';
+  ASSERT_ELIM (strlen (a) < 6);
+}
+
+/* { dg-final { scan-tree-dump-times "call_in_true_branch_not_eliminated_" 0 "optimized" } } */
Index: gcc/tree-ssa-strlen.c
===================================================================
--- gcc/tree-ssa-strlen.c	(revision 273914)
+++ gcc/tree-ssa-strlen.c	(working copy)
@@ -1195,14 +1195,13 @@ adjust_last_stmt (strinfo *si, gimple *stmt, bool
    to constants.  */
 
 tree
-set_strlen_range (tree lhs, wide_int max, tree bound /* = NULL_TREE */)
+set_strlen_range (tree lhs, wide_int min, wide_int max,
+		  tree bound /* = NULL_TREE */)
 {
   if (TREE_CODE (lhs) != SSA_NAME
       || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
     return NULL_TREE;
 
-  wide_int min = wi::zero (max.get_precision ());
-
   if (bound)
     {
       /* For strnlen, adjust MIN and MAX as necessary.  If the bound
@@ -1312,7 +1311,8 @@ maybe_set_strlen_range (tree lhs, tree src, tree b
 	}
     }
 
-  return set_strlen_range (lhs, max, bound);
+  wide_int min = wi::zero (max.get_precision ());
+  return set_strlen_range (lhs, min, max, bound);
 }
 
 /* Handle a strlen call.  If strlen of the argument is known, replace
@@ -1434,6 +1434,12 @@ handle_builtin_strlen (gimple_stmt_iterator *gsi)
 		  tree adj = fold_build2_loc (loc, MINUS_EXPR,
 					      TREE_TYPE (lhs), lhs, old);
 		  adjust_related_strinfos (loc, si, adj);
+		  /* Use the constant minimim length as the lower bound
+		     of the non-constant length.  */
+		  wide_int min = wi::to_wide (old);
+		  wide_int max
+		    = wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node)) - 2;
+		  set_strlen_range (lhs, min, max);
 		}
 	      else
 		{
@@ -3386,9 +3392,51 @@ int ssa_name_limit_t::next_ssa_name (tree ssa_name
    on success and false otherwise.  */
 
 static bool
-count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm,
+count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
+		     unsigned HOST_WIDE_INT nbytes,
+		     unsigned lenrange[3], bool *nulterm,
 		     bool *allnul, bool *allnonnul, ssa_name_limit_t &snlim)
 {
+  int idx = get_stridx (exp);
+  if (idx > 0)
+    {
+      strinfo *si = get_strinfo (idx);
+      /* FIXME: Handle non-constant lengths in some range.  */
+      if (!si || !tree_fits_shwi_p (si->nonzero_chars))
+	return false;
+
+      unsigned len = tree_to_shwi (si->nonzero_chars);
+      unsigned size = len + si->full_string_p;
+      if (size <= offset)
+	return false;
+
+      len -= offset;
+      size -= offset;
+
+      if (size < nbytes)
+	return false;
+
+      if (len < lenrange[0])
+	lenrange[0] = len;
+      if (lenrange[1] < len)
+	lenrange[1] = len;
+
+      if (!si->full_string_p)
+	*nulterm = false;
+
+      /* Since only the length of the string are known and
+	 its contents, clear ALLNUL and ALLNONNUL purely on
+	 the basis of the length.  */
+      if (len)
+	*allnul = false;
+      else
+	*allnonnul = false;
+      return true;
+    }
+
+  if (TREE_CODE (exp) == ADDR_EXPR)
+    exp = TREE_OPERAND (exp, 0);
+
   if (TREE_CODE (exp) == SSA_NAME)
     {
       /* Handle a single-character specially.  */
@@ -3401,7 +3449,8 @@ static bool
 	     (even if its exact value is not known) and if so, recurse
 	     once to set the range, etc.  */
 	  if (tree_expr_nonzero_p (exp))
-	    return count_nonzero_bytes (build_int_cst (type, 1), lenrange,
+	    return count_nonzero_bytes (build_int_cst (type, 1),
+					offset, nbytes, lenrange,
 					nulterm, allnul, allnonnul, snlim);
 	  /* Don't know whether EXP is or isn't nonzero.  */
 	  return false;
@@ -3408,7 +3457,13 @@ static bool
 	}
 
       gimple *stmt = SSA_NAME_DEF_STMT (exp);
-      if (gimple_code (stmt) != GIMPLE_PHI)
+      if (gimple_assign_single_p (stmt))
+	{
+	  tree rhs = gimple_assign_rhs1 (stmt);
+	  return count_nonzero_bytes (rhs, offset, nbytes, lenrange, nulterm,
+				      allnul, allnonnul, snlim);
+	}
+      else if (gimple_code (stmt) != GIMPLE_PHI)
 	return false;
 
       /* Avoid processing an SSA_NAME that has already been visited
@@ -3422,8 +3477,8 @@ static bool
       for (unsigned i = 0; i != n; i++)
 	{
 	  tree def = gimple_phi_arg_def (stmt, i);
-	  if (!count_nonzero_bytes (def, lenrange, nulterm, allnul, allnonnul,
-				    snlim))
+	  if (!count_nonzero_bytes (def, offset, nbytes, lenrange, nulterm,
+				    allnul, allnonnul, snlim))
 	    return false;
 	}
 
@@ -3430,27 +3485,20 @@ static bool
       return true;
     }
 
-  /* Offset from the beginning of the representation bytes, a pointer
-     to the representation, and the number of bytes of the representation
-     to consider (may be less than the object size for MEM_REF).  */
-  unsigned HOST_WIDE_INT offset = 0;
-  const char *prep = NULL;
-  unsigned nbytes = 0;
-
   if (TREE_CODE (exp) == MEM_REF)
     {
-      /* If the MEM_REF operand is the address of an object such as
-	 a string or integer, extract it and the offset into it.  */
       tree arg = TREE_OPERAND (exp, 0);
-      if (TREE_CODE (arg) != ADDR_EXPR)
-	return false;
+      tree off = TREE_OPERAND (exp, 1);
 
-      tree off = TREE_OPERAND (exp, 1);
       if (TREE_CODE (off) != INTEGER_CST
 	  || !tree_fits_uhwi_p (off))
 	return false;
 
-      offset = tree_to_uhwi (off);
+      unsigned HOST_WIDE_INT wioff = tree_to_uhwi (off);
+      if (INT_MAX < wioff)
+	return false;
+
+      offset += wioff;
       if (INT_MAX < offset)
 	return false;
 
@@ -3458,38 +3506,12 @@ static bool
       tree type = TREE_TYPE (exp);
       if (tree typesize = TYPE_SIZE_UNIT (type))
 	nbytes = tree_to_uhwi (typesize);
+      else
+	return false;
 
-      if (offset == 0 && TREE_CODE (exp) != STRING_CST)
-	{
-	  int idx = get_stridx (arg);
-	  if (idx > 0)
-	    {
-	      strinfo *si = get_strinfo (idx);
-	      if (si && tree_fits_shwi_p (si->nonzero_chars))
-		{
-		  unsigned len = tree_to_shwi (si->nonzero_chars);
-		  if (len < lenrange[0])
-		    lenrange[0] = len;
-		  if (lenrange[1] < len)
-		    lenrange[1] = len;
-
-		  if (!si->full_string_p)
-		    *nulterm = false;
-
-		  /* Since only the length of the string are known and
-		     its contents, clear ALLNUL and ALLNONNUL purely on
-		     the basis of the length.  */
-		  if (len)
-		    *allnul = false;
-		  else
-		    *allnonnul = false;
-		  return true;
-		}
-	    }
-	}
-
-      /* Proceed to extract the object representation below.  */
-      exp = TREE_OPERAND (arg, 0);
+      /* Handle MEM_REF = SSA_NAME types of assignments.  */
+      return count_nonzero_bytes (arg, offset, nbytes, lenrange, nulterm,
+				  allnul, allnonnul, snlim);
     }
 
   if (TREE_CODE (exp) == VAR_DECL && TREE_READONLY (exp))
@@ -3499,20 +3521,21 @@ static bool
 	return false;
     }
 
+  const char *prep = NULL;
   if (TREE_CODE (exp) == STRING_CST)
     {
-      /* Set PREP and NBYTES to the string representation.  */
-      gcc_assert (offset <= INT_MAX);
+      unsigned nchars = TREE_STRING_LENGTH (exp);
+      if (nchars < offset)
+	return false;
 
+      if (nchars < nbytes)
+	return false;
+
       if (!nbytes)
-	{
-	  /* Unless NBYTES has already been determined above from
-	     MEM_REF, set it here.  It includes all internal nuls,
-	     including the terminating one if the string has one.  */
-	  nbytes = TREE_STRING_LENGTH (exp);
-	  if (nbytes <= offset)
-	    return false;
-	}
+	/* If NBYTES hasn't been determined earlier from MEM_REF,
+	   set it here.  It includes all internal nuls, including
+	   the terminating one if the string has one.  */
+	nbytes = nchars - offset;
 
       prep = TREE_STRING_POINTER (exp) + offset;
     }
@@ -3520,12 +3543,14 @@ static bool
   unsigned char buf[256];
   if (!prep)
     {
-      /* Try to extract the representation of the constant object.  */
-      nbytes = native_encode_expr (exp, buf, sizeof buf, -1);
+      /* If the pointer to representation hasn't been set above
+	 for STRING_CST point it at the buffer.  */
+      prep = reinterpret_cast <char *>(buf);
+      /* Try to extract the representation of the constant object
+	 or expression starting from the offset.  */
+      nbytes = native_encode_expr (exp, buf, sizeof buf, offset);
       if (!nbytes)
 	return false;
-
-      prep = reinterpret_cast <char *>(buf);
     }
 
   /* Compute the number of leading nonzero bytes in the representation
@@ -3591,7 +3616,8 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3
   *allnonnul = true;
 
   ssa_name_limit_t snlim;
-  return count_nonzero_bytes (exp, lenrange, nulterm, allnul, allnonnul, snlim);
+  return count_nonzero_bytes (exp, 0, 0, lenrange, nulterm, allnul, allnonnul,
+			      snlim);
 }
 
 /* Handle a single or multibyte store other than by a built-in function,
@@ -3664,11 +3690,14 @@ handle_store (gimple_stmt_iterator *gsi)
 
       if (tree dstsize = compute_objsize (lhs, 1))
 	if (compare_tree_int (dstsize, lenrange[2]) < 0)
-	  warning_n (gimple_location (stmt), OPT_Wstringop_overflow_,
-		     lenrange[2],
-		     "%Gwriting %u byte into a region of size %E",
-		     "%Gwriting %u bytes into a region of size %E",
-		     stmt, lenrange[2], dstsize);
+	  {
+	    location_t loc = gimple_nonartificial_location (stmt);
+	    warning_n (loc, OPT_Wstringop_overflow_,
+		       lenrange[2],
+		       "%Gwriting %u byte into a region of size %E",
+		       "%Gwriting %u bytes into a region of size %E",
+		       stmt, lenrange[2], dstsize);
+	  }
     }
   else
     {
@@ -3795,7 +3824,14 @@ handle_store (gimple_stmt_iterator *gsi)
 	    }
 	  else
 	    si->nonzero_chars = build_int_cst (size_type_node, offset);
-	  si->full_string_p = full_string_p;
+
+	  /* Set FULL_STRING_P only if the length of the strings being
+	     written is the same, and clear it if the strings have
+	     different lengths.  In the latter case the length stored
+	     in si->NONZERO_CHARS becomes the lower bound.
+	     FIXME: Handle the upper bound of the length if possible.  */
+	  si->full_string_p = full_string_p && lenrange[0] == lenrange[1];
+
 	  if (storing_all_zeros_p
 	      && ssaname
 	      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
@@ -3825,10 +3861,23 @@ handle_store (gimple_stmt_iterator *gsi)
       if (idx != 0)
 	{
 	  tree ptr = (ssaname ? ssaname : build_fold_addr_expr (lhs));
-	  HOST_WIDE_INT slen = (storing_all_zeros_p
-				? 0
-				: (storing_nonzero_p
-				   && ranges_valid ? lenrange[0] : -1));
+
+	  HOST_WIDE_INT slen;
+	  if (storing_all_zeros_p)
+	    slen = 0;
+	  else if (storing_nonzero_p && ranges_valid)
+	    {
+	      /* FIXME: Handle the upper bound of the length when
+		 LENRANGE[0] != LENRANGE[1].  */
+	      slen = lenrange[0];
+	      if (lenrange[0] != lenrange[1])
+		/* Set the minimum length but ignore the maximum
+		   for now.  */
+		full_string_p = false;
+	    }
+	  else
+	    slen = -1;
+
 	  tree len = (slen <= 0
 		      ? size_zero_node
 		      : build_int_cst (size_type_node, slen));
Index: gcc/tree-ssa-strlen.h
===================================================================
--- gcc/tree-ssa-strlen.h	(revision 273914)
+++ gcc/tree-ssa-strlen.h	(working copy)
@@ -23,6 +23,6 @@
 
 extern bool is_strlen_related_p (tree, tree);
 extern bool maybe_diag_stxncpy_trunc (gimple_stmt_iterator, tree, tree);
-extern tree set_strlen_range (tree, wide_int, tree = NULL_TREE);
+extern tree set_strlen_range (tree, wide_int, wide_int, tree = NULL_TREE);
 
 #endif   // GCC_TREE_SSA_STRLEN_H

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [PATCH] fix and improve strlen conditional handling of merged stores (PR 91183, 91294, 91315)
  2019-08-01  0:36 [PATCH] fix and improve strlen conditional handling of merged stores (PR 91183, 91294, 91315) Martin Sebor
@ 2019-08-09  7:15 ` Jeff Law
  2019-08-10  5:26   ` Martin Sebor
  0 siblings, 1 reply; 6+ messages in thread
From: Jeff Law @ 2019-08-09  7:15 UTC (permalink / raw)
  To: Martin Sebor, gcc-patches

On 7/31/19 6:36 PM, Martin Sebor wrote:
> MoreÂ extensiveÂ testingÂ ofÂ theÂ lastÂ week'sÂ strlenÂ patchÂ for
> PR91183Â onÂ variousÂ non-mainstreamÂ targetsÂ andÂ withÂ betterÂ tests
> hasÂ exposedÂ aÂ fewÂ gapsÂ andÂ aÂ coupleÂ ofÂ bugs.Â Â TheÂ attachedÂ patch
> addressesÂ allÂ inÂ oneÂ change.Â Â IÂ consideredÂ splittingÂ itÂ upÂ but
> inÂ theÂ endÂ decidedÂ theÂ changesÂ wereÂ smallÂ andÂ sufficiently
> isolatedÂ thatÂ itÂ wasn'tÂ necessary.Â Â (IfÂ someoneÂ feelsÂ strongly
> otherwiseÂ itÂ canÂ beÂ easilyÂ splitÂ tÂ up.)
> 
> TheÂ wrong-codeÂ bugÂ (PRÂ 91294)Â isÂ dueÂ toÂ handle_storeÂ neglecting
> toÂ fullyÂ considerÂ theÂ caseÂ whenÂ aÂ singleÂ multi-byteÂ store
> involvingÂ aÂ PHIÂ ofÂ twoÂ "strings"Â theÂ sameÂ sizeÂ (soÂ theyÂ areÂ merged
> intoÂ aÂ singleÂ intÂ store)Â butÂ ofÂ unequalÂ length.Â Â TheÂ function
> simplyÂ takesÂ theÂ lengthÂ ofÂ theÂ shorterÂ stringÂ asÂ theÂ resulting
> lengthÂ whenÂ itÂ needsÂ toÂ onlyÂ setÂ theÂ lowerÂ boundÂ ofÂ theÂ length
> (itÂ doesÂ thatÂ treatingÂ theÂ resultÂ asÂ potentiallyÂ notÂ nul-
> terminated).
> 
> TheÂ gapsÂ areÂ inÂ notÂ handlingÂ someÂ MEM_REFÂ formsÂ thatÂ comeÂ up
> inÂ multi-byteÂ assignmentsÂ (thisÂ isÂ theÂ restÂ ofÂ PRÂ 91183Â andÂ was
> exposedÂ onÂ strictlyÂ alignedÂ targets),Â andÂ inÂ handle_builtin_strlen
> discardingÂ theÂ lowerÂ boundÂ onÂ aÂ stringÂ lengthÂ insteadÂ ofÂ exposing
> itÂ toÂ downstreamÂ passes.Â Â ThisÂ isÂ PRÂ 91315Â thatÂ wasÂ exposedÂ by
> aÂ fewÂ casesÂ inÂ theÂ existingÂ testsÂ forÂ PRÂ 91294Â failingÂ after
> theÂ fixÂ forÂ PRÂ 91294.
> 
> TestedÂ onÂ x86_64-linuxÂ andÂ spot-checkedÂ withÂ aÂ sparc-solaris2.11
> cross-compiler.
> 
> Martin
> 
> gcc-91294-2.diff
> 
> PR tree-optimization/91315 - missing strlen lower bound of a string known to be at least N characters
> PR tree-optimization/91294 - wrong strlen result of a conditional with an offset
> PR tree-optimization/91183 - strlen of a strcpy result with a conditional source not folded
> 
> gcc/testsuite/ChangeLog:
> 
> 	PR tree-optimization/91315
> 	PR tree-optimization/91294
> 	PR tree-optimization/91183
> 	* gcc.dg/strlenopt-44.c: Avoid using length of 1.
> 	* gcc.dg/strlenopt-70.c: Disable overly optimistic tests.
> 	* gcc.dg/strlenopt-73.c: New test.
> 	* gcc.dg/strlenopt-74.c: New test.
> 	* gcc.dg/strlenopt-75.c: New test.
> 	* gcc.dg/strlenopt-76.c: New test.
> 	* gcc.dg/strlenopt-77.c: New test.
> 
> gcc/ChangeLog:
> 
> 	PR tree-optimization/91315
> 	PR tree-optimization/91294
> 	PR tree-optimization/91183
> 	* gimple-fold.c (gimple_fold_builtin_strlen): Add expected argument.
> 	* tree-ssa-strlen.c (set_strlen_range): Add function argument.
> 	(maybe_set_strlen_range): Add expected argument.
> 	(handle_builtin_strlen): Call set_strlen_range.
> 	(count_nonzero_bytes): Add function arguments.  Handle strinfo
> 	first.  Handle "single" assignment.
> 	(handle_store): Set the lower bound of length for multibyte stores
> 	of unequal lengths.
> 	* tree-ssa-strlen.h (set_strlen_range): Add function argument.
> 
> Index: gcc/tree-ssa-strlen.c
> ===================================================================
> --- gcc/tree-ssa-strlen.c	(revision 273914)
> +++ gcc/tree-ssa-strlen.c	(working copy)
> @@ -1434,6 +1434,12 @@ handle_builtin_strlen (gimple_stmt_iterator *gsi)
>  		  tree adj = fold_build2_loc (loc, MINUS_EXPR,
>  					      TREE_TYPE (lhs), lhs, old);
>  		  adjust_related_strinfos (loc, si, adj);
> +		  /* Use the constant minimim length as the lower bound
s/minimim/minimum/


> @@ -3408,7 +3457,13 @@ static bool
>  	}
>  
>        gimple *stmt = SSA_NAME_DEF_STMT (exp);
> -      if (gimple_code (stmt) != GIMPLE_PHI)
> +      if (gimple_assign_single_p (stmt))
> +	{
> +	  tree rhs = gimple_assign_rhs1 (stmt);
> +	  return count_nonzero_bytes (rhs, offset, nbytes, lenrange, nulterm,
> +				      allnul, allnonnul, snlim);
> +	}
> +      else if (gimple_code (stmt) != GIMPLE_PHI)
>  	return false;
What cases are you handling here?  Are there any cases where a single
operand expression on the RHS affects the result.  For example, if we've
got a NOP_EXPR which zero extends RHS?  Does that change the nonzero
bytes in a way that is significant?

I'm not opposed to handling single operand objects here, I'm just
concerned that we're being very lenient in just stripping away the
operator and looking at the underlying object.



> @@ -3795,7 +3824,14 @@ handle_store (gimple_stmt_iterator *gsi)
>  	    }
>  	  else
>  	    si->nonzero_chars = build_int_cst (size_type_node, offset);
> -	  si->full_string_p = full_string_p;
> +
> +	  /* Set FULL_STRING_P only if the length of the strings being
> +	     written is the same, and clear it if the strings have
> +	     different lengths.  In the latter case the length stored
> +	     in si->NONZERO_CHARS becomes the lower bound.
> +	     FIXME: Handle the upper bound of the length if possible.  */
> +	  si->full_string_p = full_string_p && lenrange[0] == lenrange[1];
So there seems to be a disconnect between the comment and the code.

The comment indicates you care about the lengths of the two strings
being the same.  But what you're really comparing when the lenrange[0]
== lenrange[1] test is that the min and max of RHS are the same.


It generally looks reasonable, so I think we just need to reach a
conclusion on the gimple_assign_single_p cases we're trying to handle
and the possible mismatch between the comment and the code.

jeff

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [PATCH] fix and improve strlen conditional handling of merged stores (PR 91183, 91294, 91315)
  2019-08-09  7:15 ` Jeff Law
@ 2019-08-10  5:26   ` Martin Sebor
  2019-08-12 20:04     ` Jeff Law
  0 siblings, 1 reply; 6+ messages in thread
From: Martin Sebor @ 2019-08-10  5:26 UTC (permalink / raw)
  To: Jeff Law, gcc-patches

On 8/8/19 7:05 PM, Jeff Law wrote:
> On 7/31/19 6:36 PM, Martin Sebor wrote:
>> MoreÂ extensiveÂ testingÂ ofÂ theÂ lastÂ week'sÂ strlenÂ patchÂ for
>> PR91183Â onÂ variousÂ non-mainstreamÂ targetsÂ andÂ withÂ betterÂ tests
>> hasÂ exposedÂ aÂ fewÂ gapsÂ andÂ aÂ coupleÂ ofÂ bugs.Â Â TheÂ attachedÂ patch
>> addressesÂ allÂ inÂ oneÂ change.Â Â IÂ consideredÂ splittingÂ itÂ upÂ but
>> inÂ theÂ endÂ decidedÂ theÂ changesÂ wereÂ smallÂ andÂ sufficiently
>> isolatedÂ thatÂ itÂ wasn'tÂ necessary.Â Â (IfÂ someoneÂ feelsÂ strongly
>> otherwiseÂ itÂ canÂ beÂ easilyÂ splitÂ tÂ up.)
>>
>> TheÂ wrong-codeÂ bugÂ (PRÂ 91294)Â isÂ dueÂ toÂ handle_storeÂ neglecting
>> toÂ fullyÂ considerÂ theÂ caseÂ whenÂ aÂ singleÂ multi-byteÂ store
>> involvingÂ aÂ PHIÂ ofÂ twoÂ "strings"Â theÂ sameÂ sizeÂ (soÂ theyÂ areÂ merged
>> intoÂ aÂ singleÂ intÂ store)Â butÂ ofÂ unequalÂ length.Â Â TheÂ function
>> simplyÂ takesÂ theÂ lengthÂ ofÂ theÂ shorterÂ stringÂ asÂ theÂ resulting
>> lengthÂ whenÂ itÂ needsÂ toÂ onlyÂ setÂ theÂ lowerÂ boundÂ ofÂ theÂ length
>> (itÂ doesÂ thatÂ treatingÂ theÂ resultÂ asÂ potentiallyÂ notÂ nul-
>> terminated).
>>
>> TheÂ gapsÂ areÂ inÂ notÂ handlingÂ someÂ MEM_REFÂ formsÂ thatÂ comeÂ up
>> inÂ multi-byteÂ assignmentsÂ (thisÂ isÂ theÂ restÂ ofÂ PRÂ 91183Â andÂ was
>> exposedÂ onÂ strictlyÂ alignedÂ targets),Â andÂ inÂ handle_builtin_strlen
>> discardingÂ theÂ lowerÂ boundÂ onÂ aÂ stringÂ lengthÂ insteadÂ ofÂ exposing
>> itÂ toÂ downstreamÂ passes.Â Â ThisÂ isÂ PRÂ 91315Â thatÂ wasÂ exposedÂ by
>> aÂ fewÂ casesÂ inÂ theÂ existingÂ testsÂ forÂ PRÂ 91294Â failingÂ after
>> theÂ fixÂ forÂ PRÂ 91294.
>>
>> TestedÂ onÂ x86_64-linuxÂ andÂ spot-checkedÂ withÂ aÂ sparc-solaris2.11
>> cross-compiler.
>>
>> Martin
>>
>> gcc-91294-2.diff
>>
>> PR tree-optimization/91315 - missing strlen lower bound of a string known to be at least N characters
>> PR tree-optimization/91294 - wrong strlen result of a conditional with an offset
>> PR tree-optimization/91183 - strlen of a strcpy result with a conditional source not folded
>>
>> gcc/testsuite/ChangeLog:
>>
>> 	PR tree-optimization/91315
>> 	PR tree-optimization/91294
>> 	PR tree-optimization/91183
>> 	* gcc.dg/strlenopt-44.c: Avoid using length of 1.
>> 	* gcc.dg/strlenopt-70.c: Disable overly optimistic tests.
>> 	* gcc.dg/strlenopt-73.c: New test.
>> 	* gcc.dg/strlenopt-74.c: New test.
>> 	* gcc.dg/strlenopt-75.c: New test.
>> 	* gcc.dg/strlenopt-76.c: New test.
>> 	* gcc.dg/strlenopt-77.c: New test.
>>
>> gcc/ChangeLog:
>>
>> 	PR tree-optimization/91315
>> 	PR tree-optimization/91294
>> 	PR tree-optimization/91183
>> 	* gimple-fold.c (gimple_fold_builtin_strlen): Add expected argument.
>> 	* tree-ssa-strlen.c (set_strlen_range): Add function argument.
>> 	(maybe_set_strlen_range): Add expected argument.
>> 	(handle_builtin_strlen): Call set_strlen_range.
>> 	(count_nonzero_bytes): Add function arguments.  Handle strinfo
>> 	first.  Handle "single" assignment.
>> 	(handle_store): Set the lower bound of length for multibyte stores
>> 	of unequal lengths.
>> 	* tree-ssa-strlen.h (set_strlen_range): Add function argument.
>>
>> Index: gcc/tree-ssa-strlen.c
>> ===================================================================
>> --- gcc/tree-ssa-strlen.c	(revision 273914)
>> +++ gcc/tree-ssa-strlen.c	(working copy)
>> @@ -1434,6 +1434,12 @@ handle_builtin_strlen (gimple_stmt_iterator *gsi)
>>   		  tree adj = fold_build2_loc (loc, MINUS_EXPR,
>>   					      TREE_TYPE (lhs), lhs, old);
>>   		  adjust_related_strinfos (loc, si, adj);
>> +		  /* Use the constant minimim length as the lower bound
> s/minimim/minimum/
> 
> 
>> @@ -3408,7 +3457,13 @@ static bool
>>   	}
>>   
>>         gimple *stmt = SSA_NAME_DEF_STMT (exp);
>> -      if (gimple_code (stmt) != GIMPLE_PHI)
>> +      if (gimple_assign_single_p (stmt))
>> +	{
>> +	  tree rhs = gimple_assign_rhs1 (stmt);
>> +	  return count_nonzero_bytes (rhs, offset, nbytes, lenrange, nulterm,
>> +				      allnul, allnonnul, snlim);
>> +	}
>> +      else if (gimple_code (stmt) != GIMPLE_PHI)
>>   	return false;
> What cases are you handling here?  Are there any cases where a single
> operand expression on the RHS affects the result.  For example, if we've
> got a NOP_EXPR which zero extends RHS?  Does that change the nonzero
> bytes in a way that is significant?
> 
> I'm not opposed to handling single operand objects here, I'm just
> concerned that we're being very lenient in just stripping away the
> operator and looking at the underlying object.

I remember adding the code because of a test failure but not
the specifics anymore.  No tests fail with it removed so it
may not be needed.  As you know, I've been juggling a few
enhancements in this area and copying code between them as
I need it so it's possible that I copied too much, or that
some other change has obviated it, or also that the test
failed somewhere else and I forgot to copy the test along
with the code  I'll remove it until it's needed.

>> @@ -3795,7 +3824,14 @@ handle_store (gimple_stmt_iterator *gsi)
>>   	    }
>>   	  else
>>   	    si->nonzero_chars = build_int_cst (size_type_node, offset);
>> -	  si->full_string_p = full_string_p;
>> +
>> +	  /* Set FULL_STRING_P only if the length of the strings being
>> +	     written is the same, and clear it if the strings have
>> +	     different lengths.  In the latter case the length stored
>> +	     in si->NONZERO_CHARS becomes the lower bound.
>> +	     FIXME: Handle the upper bound of the length if possible.  */
>> +	  si->full_string_p = full_string_p && lenrange[0] == lenrange[1];
> So there seems to be a disconnect between the comment and the code.
> 
> The comment indicates you care about the lengths of the two strings
> being the same.  But what you're really comparing when the lenrange[0]
> == lenrange[1] test is that the min and max of RHS are the same.

The comment tries to make clear that all the arrays on the RHS
of the assignment must have the same length in order to set
FULL_STRING_P.  Like here where LENRANGE = { 4, 4, 4 }:

   void f (char *s)
   {
     if (__builtin_strlen (s) != 2)
       return;

     *(int*)a = i ? 0x11111111 : 0x22222222;
   }

but not here where LENRANGE = { 1, 4, 4 }:

     *(int*)a = i < 0 ? 0x11111111 : i ? 0x22220022 : 0x33003333;

If the bounds of the range of lengths of all the strings on
the RHS are the same they're all the same length.

I'm open to phrasing it better.

> It generally looks reasonable, so I think we just need to reach a
> conclusion on the gimple_assign_single_p cases we're trying to handle
> and the possible mismatch between the comment and the code.

Do you want me to post another revision with
the gimple_assign_single_p test removed?

Martin

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [PATCH] fix and improve strlen conditional handling of merged stores (PR 91183, 91294, 91315)
  2019-08-10  5:26   ` Martin Sebor
@ 2019-08-12 20:04     ` Jeff Law
  2019-08-14 16:49       ` Martin Sebor
  0 siblings, 1 reply; 6+ messages in thread
From: Jeff Law @ 2019-08-12 20:04 UTC (permalink / raw)
  To: Martin Sebor, gcc-patches

On 8/9/19 5:42 PM, Martin Sebor wrote:
>>> @@ -3408,7 +3457,13 @@ static bool
>>> Â Â Â Â Â  }
>>> Â  Â Â Â Â Â Â Â  gimple *stmt = SSA_NAME_DEF_STMT (exp);
>>> -Â Â Â Â Â  if (gimple_code (stmt) != GIMPLE_PHI)
>>> +Â Â Â Â Â  if (gimple_assign_single_p (stmt))
>>> +Â Â Â  {
>>> +Â Â Â Â Â  tree rhs = gimple_assign_rhs1 (stmt);
>>> +Â Â Â Â Â  return count_nonzero_bytes (rhs, offset, nbytes, lenrange,
>>> nulterm,
>>> +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  allnul, allnonnul, snlim);
>>> +Â Â Â  }
>>> +Â Â Â Â Â  else if (gimple_code (stmt) != GIMPLE_PHI)
>>> Â Â Â Â Â  return false;
>> What cases are you handling here?Â  Are there any cases where a single
>> operand expression on the RHS affects the result.Â  For example, if we've
>> got a NOP_EXPR which zero extends RHS?Â  Does that change the nonzero
>> bytes in a way that is significant?
>>
>> I'm not opposed to handling single operand objects here, I'm just
>> concerned that we're being very lenient in just stripping away the
>> operator and looking at the underlying object.
> 
> I remember adding the code because of a test failure but not
> the specifics anymore.Â  No tests fail with it removed so it
> may not be needed.Â  As you know, I've been juggling a few
> enhancements in this area and copying code between them as
> I need it so it's possible that I copied too much, or that
> some other change has obviated it, or also that the test
> failed somewhere else and I forgot to copy the test along
> with the codeÂ  I'll remove it until it's needed.
Let's pull it for now.  If we come across the need again, we can
obviously revisit with a testcase.


> 
>>> @@ -3795,7 +3824,14 @@ handle_store (gimple_stmt_iterator *gsi)
>>> Â Â Â Â Â Â Â Â Â  }
>>> Â Â Â Â Â Â Â  else
>>> Â Â Â Â Â Â Â Â Â  si->nonzero_chars = build_int_cst (size_type_node, offset);
>>> -Â Â Â Â Â  si->full_string_p = full_string_p;
>>> +
>>> +Â Â Â Â Â  /* Set FULL_STRING_P only if the length of the strings being
>>> +Â Â Â Â Â Â Â Â  written is the same, and clear it if the strings have
>>> +Â Â Â Â Â Â Â Â  different lengths.Â  In the latter case the length stored
>>> +Â Â Â Â Â Â Â Â  in si->NONZERO_CHARS becomes the lower bound.
>>> +Â Â Â Â Â Â Â Â  FIXME: Handle the upper bound of the length if possible.Â  */
>>> +Â Â Â Â Â  si->full_string_p = full_string_p && lenrange[0] == lenrange[1];
>> So there seems to be a disconnect between the comment and the code.
>>
>> The comment indicates you care about the lengths of the two strings
>> being the same.Â  But what you're really comparing when the lenrange[0]
>> == lenrange[1] test is that the min and max of RHS are the same.
> 
> The comment tries to make clear that all the arrays on the RHS
> of the assignment must have the same length in order to set
> FULL_STRING_P.Â  Like here where LENRANGE = { 4, 4, 4 }:
> 
> Â  void f (char *s)
> Â  {
> Â Â Â  if (__builtin_strlen (s) != 2)
> Â Â Â Â Â  return;
> 
> Â Â Â  *(int*)a = i ? 0x11111111 : 0x22222222;
> Â  }
> 
> but not here where LENRANGE = { 1, 4, 4 }:
> 
> Â Â Â  *(int*)a = i < 0 ? 0x11111111 : i ? 0x22220022 : 0x33003333;
> 
> If the bounds of the range of lengths of all the strings on
> the RHS are the same they're all the same length.
> 
> I'm open to phrasing it better.
Oh, I think I see what I was missing.  In the case where RHS is a
conditional (or perhaps a SSA_NAME which was set from a PHI) LENRANGE
will have the min/max/# bytes for the RHS was a whole, not just a single
component of the RHS.


>> It generally looks reasonable, so I think we just need to reach a
>> conclusion on the gimple_assign_single_p cases we're trying to handle
>> and the possible mismatch between the comment and the code.
> 
> Do you want me to post another revision with
> the gimple_assign_single_p test removed?
I think remove that hunk, bootstrap, test, commit and post for archival
purposes.  I do not think another round of review is necessary.

jeff

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [PATCH] fix and improve strlen conditional handling of merged stores (PR 91183, 91294, 91315)
  2019-08-12 20:04     ` Jeff Law
@ 2019-08-14 16:49       ` Martin Sebor
  2019-08-14 16:51         ` Martin Sebor
  0 siblings, 1 reply; 6+ messages in thread
From: Martin Sebor @ 2019-08-14 16:49 UTC (permalink / raw)
  To: Jeff Law, gcc-patches

[-- Attachment #1: Type: text/plain, Size: 4452 bytes --]

On 8/12/19 1:57 PM, Jeff Law wrote:
> On 8/9/19 5:42 PM, Martin Sebor wrote:
>>>> @@ -3408,7 +3457,13 @@ static bool
>>>>  Â Â Â Â Â  }
>>>>  Â  Â Â Â Â Â Â Â  gimple *stmt = SSA_NAME_DEF_STMT (exp);
>>>> -Â Â Â Â Â  if (gimple_code (stmt) != GIMPLE_PHI)
>>>> +Â Â Â Â Â  if (gimple_assign_single_p (stmt))
>>>> +Â Â Â  {
>>>> +Â Â Â Â Â  tree rhs = gimple_assign_rhs1 (stmt);
>>>> +Â Â Â Â Â  return count_nonzero_bytes (rhs, offset, nbytes, lenrange,
>>>> nulterm,
>>>> +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  allnul, allnonnul, snlim);
>>>> +Â Â Â  }
>>>> +Â Â Â Â Â  else if (gimple_code (stmt) != GIMPLE_PHI)
>>>>  Â Â Â Â Â  return false;
>>> What cases are you handling here?Â  Are there any cases where a single
>>> operand expression on the RHS affects the result.Â  For example, if we've
>>> got a NOP_EXPR which zero extends RHS?Â  Does that change the nonzero
>>> bytes in a way that is significant?
>>>
>>> I'm not opposed to handling single operand objects here, I'm just
>>> concerned that we're being very lenient in just stripping away the
>>> operator and looking at the underlying object.
>>
>> I remember adding the code because of a test failure but not
>> the specifics anymore.Â  No tests fail with it removed so it
>> may not be needed.Â  As you know, I've been juggling a few
>> enhancements in this area and copying code between them as
>> I need it so it's possible that I copied too much, or that
>> some other change has obviated it, or also that the test
>> failed somewhere else and I forgot to copy the test along
>> with the codeÂ  I'll remove it until it's needed.
> Let's pull it for now.  If we come across the need again, we can
> obviously revisit with a testcase.
> 
> 
>>
>>>> @@ -3795,7 +3824,14 @@ handle_store (gimple_stmt_iterator *gsi)
>>>>  Â Â Â Â Â Â Â Â Â  }
>>>>  Â Â Â Â Â Â Â  else
>>>>  Â Â Â Â Â Â Â Â Â  si->nonzero_chars = build_int_cst (size_type_node, offset);
>>>> -Â Â Â Â Â  si->full_string_p = full_string_p;
>>>> +
>>>> +Â Â Â Â Â  /* Set FULL_STRING_P only if the length of the strings being
>>>> +Â Â Â Â Â Â Â Â  written is the same, and clear it if the strings have
>>>> +Â Â Â Â Â Â Â Â  different lengths.Â  In the latter case the length stored
>>>> +Â Â Â Â Â Â Â Â  in si->NONZERO_CHARS becomes the lower bound.
>>>> +Â Â Â Â Â Â Â Â  FIXME: Handle the upper bound of the length if possible.Â  */
>>>> +Â Â Â Â Â  si->full_string_p = full_string_p && lenrange[0] == lenrange[1];
>>> So there seems to be a disconnect between the comment and the code.
>>>
>>> The comment indicates you care about the lengths of the two strings
>>> being the same.Â  But what you're really comparing when the lenrange[0]
>>> == lenrange[1] test is that the min and max of RHS are the same.
>>
>> The comment tries to make clear that all the arrays on the RHS
>> of the assignment must have the same length in order to set
>> FULL_STRING_P.Â  Like here where LENRANGE = { 4, 4, 4 }:
>>
>>  Â  void f (char *s)
>>  Â  {
>>  Â Â Â  if (__builtin_strlen (s) != 2)
>>  Â Â Â Â Â  return;
>>
>>  Â Â Â  *(int*)a = i ? 0x11111111 : 0x22222222;
>>  Â  }
>>
>> but not here where LENRANGE = { 1, 4, 4 }:
>>
>>  Â Â Â  *(int*)a = i < 0 ? 0x11111111 : i ? 0x22220022 : 0x33003333;
>>
>> If the bounds of the range of lengths of all the strings on
>> the RHS are the same they're all the same length.
>>
>> I'm open to phrasing it better.
> Oh, I think I see what I was missing.  In the case where RHS is a
> conditional (or perhaps a SSA_NAME which was set from a PHI) LENRANGE
> will have the min/max/# bytes for the RHS was a whole, not just a single
> component of the RHS.
> 
> 
>>> It generally looks reasonable, so I think we just need to reach a
>>> conclusion on the gimple_assign_single_p cases we're trying to handle
>>> and the possible mismatch between the comment and the code.
>>
>> Do you want me to post another revision with
>> the gimple_assign_single_p test removed?
> I think remove that hunk, bootstrap, test, commit and post for archival
> purposes.  I do not think another round of review is necessary.

Done in r274486 (also attached).

Martin

[-- Attachment #2: gcc-91294.diff --]
[-- Type: text/x-patch, Size: 34360 bytes --]

Index: gcc/tree-ssa-strlen.c
===================================================================
--- gcc/tree-ssa-strlen.c	(revision 274485)
+++ gcc/tree-ssa-strlen.c	(revision 274486)
@@ -1195,14 +1195,13 @@ adjust_last_stmt (strinfo *si, gimple *stmt, bool
    to constants.  */
 
 tree
-set_strlen_range (tree lhs, wide_int max, tree bound /* = NULL_TREE */)
+set_strlen_range (tree lhs, wide_int min, wide_int max,
+		  tree bound /* = NULL_TREE */)
 {
   if (TREE_CODE (lhs) != SSA_NAME
       || !INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
     return NULL_TREE;
 
-  wide_int min = wi::zero (max.get_precision ());
-
   if (bound)
     {
       /* For strnlen, adjust MIN and MAX as necessary.  If the bound
@@ -1312,7 +1311,8 @@ maybe_set_strlen_range (tree lhs, tree src, tree b
 	}
     }
 
-  return set_strlen_range (lhs, max, bound);
+  wide_int min = wi::zero (max.get_precision ());
+  return set_strlen_range (lhs, min, max, bound);
 }
 
 /* Handle a strlen call.  If strlen of the argument is known, replace
@@ -1434,6 +1434,12 @@ handle_builtin_strlen (gimple_stmt_iterator *gsi)
 		  tree adj = fold_build2_loc (loc, MINUS_EXPR,
 					      TREE_TYPE (lhs), lhs, old);
 		  adjust_related_strinfos (loc, si, adj);
+		  /* Use the constant minimim length as the lower bound
+		     of the non-constant length.  */
+		  wide_int min = wi::to_wide (old);
+		  wide_int max
+		    = wi::to_wide (TYPE_MAX_VALUE (ptrdiff_type_node)) - 2;
+		  set_strlen_range (lhs, min, max);
 		}
 	      else
 		{
@@ -3386,9 +3392,51 @@ int ssa_name_limit_t::next_ssa_name (tree ssa_name
    on success and false otherwise.  */
 
 static bool
-count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm,
+count_nonzero_bytes (tree exp, unsigned HOST_WIDE_INT offset,
+		     unsigned HOST_WIDE_INT nbytes,
+		     unsigned lenrange[3], bool *nulterm,
 		     bool *allnul, bool *allnonnul, ssa_name_limit_t &snlim)
 {
+  int idx = get_stridx (exp);
+  if (idx > 0)
+    {
+      strinfo *si = get_strinfo (idx);
+      /* FIXME: Handle non-constant lengths in some range.  */
+      if (!si || !tree_fits_shwi_p (si->nonzero_chars))
+	return false;
+
+      unsigned len = tree_to_shwi (si->nonzero_chars);
+      unsigned size = len + si->full_string_p;
+      if (size <= offset)
+	return false;
+
+      len -= offset;
+      size -= offset;
+
+      if (size < nbytes)
+	return false;
+
+      if (len < lenrange[0])
+	lenrange[0] = len;
+      if (lenrange[1] < len)
+	lenrange[1] = len;
+
+      if (!si->full_string_p)
+	*nulterm = false;
+
+      /* Since only the length of the string are known and
+	 its contents, clear ALLNUL and ALLNONNUL purely on
+	 the basis of the length.  */
+      if (len)
+	*allnul = false;
+      else
+	*allnonnul = false;
+      return true;
+    }
+
+  if (TREE_CODE (exp) == ADDR_EXPR)
+    exp = TREE_OPERAND (exp, 0);
+
   if (TREE_CODE (exp) == SSA_NAME)
     {
       /* Handle a single-character specially.  */
@@ -3401,7 +3449,8 @@ static bool
 	     (even if its exact value is not known) and if so, recurse
 	     once to set the range, etc.  */
 	  if (tree_expr_nonzero_p (exp))
-	    return count_nonzero_bytes (build_int_cst (type, 1), lenrange,
+	    return count_nonzero_bytes (build_int_cst (type, 1),
+					offset, nbytes, lenrange,
 					nulterm, allnul, allnonnul, snlim);
 	  /* Don't know whether EXP is or isn't nonzero.  */
 	  return false;
@@ -3422,8 +3471,8 @@ static bool
       for (unsigned i = 0; i != n; i++)
 	{
 	  tree def = gimple_phi_arg_def (stmt, i);
-	  if (!count_nonzero_bytes (def, lenrange, nulterm, allnul, allnonnul,
-				    snlim))
+	  if (!count_nonzero_bytes (def, offset, nbytes, lenrange, nulterm,
+				    allnul, allnonnul, snlim))
 	    return false;
 	}
 
@@ -3430,27 +3479,20 @@ static bool
       return true;
     }
 
-  /* Offset from the beginning of the representation bytes, a pointer
-     to the representation, and the number of bytes of the representation
-     to consider (may be less than the object size for MEM_REF).  */
-  unsigned HOST_WIDE_INT offset = 0;
-  const char *prep = NULL;
-  unsigned nbytes = 0;
-
   if (TREE_CODE (exp) == MEM_REF)
     {
-      /* If the MEM_REF operand is the address of an object such as
-	 a string or integer, extract it and the offset into it.  */
       tree arg = TREE_OPERAND (exp, 0);
-      if (TREE_CODE (arg) != ADDR_EXPR)
-	return false;
+      tree off = TREE_OPERAND (exp, 1);
 
-      tree off = TREE_OPERAND (exp, 1);
       if (TREE_CODE (off) != INTEGER_CST
 	  || !tree_fits_uhwi_p (off))
 	return false;
 
-      offset = tree_to_uhwi (off);
+      unsigned HOST_WIDE_INT wioff = tree_to_uhwi (off);
+      if (INT_MAX < wioff)
+	return false;
+
+      offset += wioff;
       if (INT_MAX < offset)
 	return false;
 
@@ -3458,38 +3500,12 @@ static bool
       tree type = TREE_TYPE (exp);
       if (tree typesize = TYPE_SIZE_UNIT (type))
 	nbytes = tree_to_uhwi (typesize);
+      else
+	return false;
 
-      if (offset == 0 && TREE_CODE (exp) != STRING_CST)
-	{
-	  int idx = get_stridx (arg);
-	  if (idx > 0)
-	    {
-	      strinfo *si = get_strinfo (idx);
-	      if (si && tree_fits_shwi_p (si->nonzero_chars))
-		{
-		  unsigned len = tree_to_shwi (si->nonzero_chars);
-		  if (len < lenrange[0])
-		    lenrange[0] = len;
-		  if (lenrange[1] < len)
-		    lenrange[1] = len;
-
-		  if (!si->full_string_p)
-		    *nulterm = false;
-
-		  /* Since only the length of the string are known and
-		     its contents, clear ALLNUL and ALLNONNUL purely on
-		     the basis of the length.  */
-		  if (len)
-		    *allnul = false;
-		  else
-		    *allnonnul = false;
-		  return true;
-		}
-	    }
-	}
-
-      /* Proceed to extract the object representation below.  */
-      exp = TREE_OPERAND (arg, 0);
+      /* Handle MEM_REF = SSA_NAME types of assignments.  */
+      return count_nonzero_bytes (arg, offset, nbytes, lenrange, nulterm,
+				  allnul, allnonnul, snlim);
     }
 
   if (TREE_CODE (exp) == VAR_DECL && TREE_READONLY (exp))
@@ -3499,20 +3515,18 @@ static bool
 	return false;
     }
 
+  const char *prep = NULL;
   if (TREE_CODE (exp) == STRING_CST)
     {
-      /* Set PREP and NBYTES to the string representation.  */
-      gcc_assert (offset <= INT_MAX);
+      unsigned nchars = TREE_STRING_LENGTH (exp);
+      if (nchars < offset)
+	return false;
 
       if (!nbytes)
-	{
-	  /* Unless NBYTES has already been determined above from
-	     MEM_REF, set it here.  It includes all internal nuls,
-	     including the terminating one if the string has one.  */
-	  nbytes = TREE_STRING_LENGTH (exp);
-	  if (nbytes <= offset)
-	    return false;
-	}
+	/* If NBYTES hasn't been determined earlier from MEM_REF,
+	   set it here.  It includes all internal nuls, including
+	   the terminating one if the string has one.  */
+	nbytes = nchars - offset;
 
       prep = TREE_STRING_POINTER (exp) + offset;
     }
@@ -3520,12 +3534,14 @@ static bool
   unsigned char buf[256];
   if (!prep)
     {
-      /* Try to extract the representation of the constant object.  */
-      nbytes = native_encode_expr (exp, buf, sizeof buf, -1);
+      /* If the pointer to representation hasn't been set above
+	 for STRING_CST point it at the buffer.  */
+      prep = reinterpret_cast <char *>(buf);
+      /* Try to extract the representation of the constant object
+	 or expression starting from the offset.  */
+      nbytes = native_encode_expr (exp, buf, sizeof buf, offset);
       if (!nbytes)
 	return false;
-
-      prep = reinterpret_cast <char *>(buf);
     }
 
   /* Compute the number of leading nonzero bytes in the representation
@@ -3591,7 +3607,8 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3
   *allnonnul = true;
 
   ssa_name_limit_t snlim;
-  return count_nonzero_bytes (exp, lenrange, nulterm, allnul, allnonnul, snlim);
+  return count_nonzero_bytes (exp, 0, 0, lenrange, nulterm, allnul, allnonnul,
+			      snlim);
 }
 
 /* Handle a single or multibyte store other than by a built-in function,
@@ -3664,11 +3681,14 @@ handle_store (gimple_stmt_iterator *gsi)
 
       if (tree dstsize = compute_objsize (lhs, 1))
 	if (compare_tree_int (dstsize, lenrange[2]) < 0)
-	  warning_n (gimple_location (stmt), OPT_Wstringop_overflow_,
-		     lenrange[2],
-		     "%Gwriting %u byte into a region of size %E",
-		     "%Gwriting %u bytes into a region of size %E",
-		     stmt, lenrange[2], dstsize);
+	  {
+	    location_t loc = gimple_nonartificial_location (stmt);
+	    warning_n (loc, OPT_Wstringop_overflow_,
+		       lenrange[2],
+		       "%Gwriting %u byte into a region of size %E",
+		       "%Gwriting %u bytes into a region of size %E",
+		       stmt, lenrange[2], dstsize);
+	  }
     }
   else
     {
@@ -3795,7 +3815,14 @@ handle_store (gimple_stmt_iterator *gsi)
 	    }
 	  else
 	    si->nonzero_chars = build_int_cst (size_type_node, offset);
-	  si->full_string_p = full_string_p;
+
+	  /* Set FULL_STRING_P only if the length of the strings being
+	     written is the same, and clear it if the strings have
+	     different lengths.  In the latter case the length stored
+	     in si->NONZERO_CHARS becomes the lower bound.
+	     FIXME: Handle the upper bound of the length if possible.  */
+	  si->full_string_p = full_string_p && lenrange[0] == lenrange[1];
+
 	  if (storing_all_zeros_p
 	      && ssaname
 	      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname))
@@ -3825,10 +3852,23 @@ handle_store (gimple_stmt_iterator *gsi)
       if (idx != 0)
 	{
 	  tree ptr = (ssaname ? ssaname : build_fold_addr_expr (lhs));
-	  HOST_WIDE_INT slen = (storing_all_zeros_p
-				? 0
-				: (storing_nonzero_p
-				   && ranges_valid ? lenrange[0] : -1));
+
+	  HOST_WIDE_INT slen;
+	  if (storing_all_zeros_p)
+	    slen = 0;
+	  else if (storing_nonzero_p && ranges_valid)
+	    {
+	      /* FIXME: Handle the upper bound of the length when
+		 LENRANGE[0] != LENRANGE[1].  */
+	      slen = lenrange[0];
+	      if (lenrange[0] != lenrange[1])
+		/* Set the minimum length but ignore the maximum
+		   for now.  */
+		full_string_p = false;
+	    }
+	  else
+	    slen = -1;
+
 	  tree len = (slen <= 0
 		      ? size_zero_node
 		      : build_int_cst (size_type_node, slen));
Index: gcc/tree-ssa-strlen.h
===================================================================
--- gcc/tree-ssa-strlen.h	(revision 274485)
+++ gcc/tree-ssa-strlen.h	(revision 274486)
@@ -23,6 +23,6 @@
 
 extern bool is_strlen_related_p (tree, tree);
 extern bool maybe_diag_stxncpy_trunc (gimple_stmt_iterator, tree, tree);
-extern tree set_strlen_range (tree, wide_int, tree = NULL_TREE);
+extern tree set_strlen_range (tree, wide_int, wide_int, tree = NULL_TREE);
 
 #endif   // GCC_TREE_SSA_STRLEN_H
Index: gcc/ChangeLog
===================================================================
--- gcc/ChangeLog	(revision 274485)
+++ gcc/ChangeLog	(revision 274486)
@@ -1,3 +1,9 @@
+2019-08-14  Martin Sebor  <msebor@redhat.com>
+
+	PR tree-optimization/91294
+	* tree-ssa-strlen.c (handle_store): Avoid treating lower bound of
+	source length as exact.
+
 2019-08-14  Christophe Lyon  <christophe.lyon@linaro.org>
 
 	* doc/extend.texi: Add "noinit" attribute documentation.
Index: gcc/testsuite/gcc.dg/strlenopt-77.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-77.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-77.c	(revision 274486)
@@ -0,0 +1,84 @@
+/* PR tree-optimization/91315 - missing strlen lower bound of a string
+   known to be at least N characters
+   { dg-do compile }
+   { dg-options "-O2 -Wall -fdump-tree-optimized" } */
+
+#include "strlenopt.h"
+
+#define CAT(x, y) x ## y
+#define CONCAT(x, y) CAT (x, y)
+#define FAILNAME(name) CONCAT (call_ ## name ##_on_line_, __LINE__)
+
+#define FAIL(name) do {				\
+    extern void FAILNAME (name) (void);		\
+    FAILNAME (name)();				\
+  } while (0)
+
+/* Macro to emit a call to function named
+     call_in_true_branch_not_eliminated_on_line_NNN()
+   for each call that's expected to be eliminated.  The dg-final
+   scan-tree-dump-time directive at the bottom of the test verifies
+   that no such call appears in output.  */
+#define ASSERT_ELIM(expr)						\
+  if (!!(expr)) FAIL (in_true_branch_not_eliminated); else (void)0
+
+char a[32];
+
+void lower_bound_assign_1 (void)
+{
+  a[0] = '1';
+  ASSERT_ELIM (strlen (a) < 1);
+}
+
+void lower_bound_assign_2 (void)
+{
+  a[0] = '1';
+  a[1] = '2';
+  ASSERT_ELIM (strlen (a) < 2);
+}
+
+void lower_bound_assign_3 (void)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  ASSERT_ELIM (strlen (a) < 3);
+}
+
+void lower_bound_memcpy (void)
+{
+  memcpy (a, "123", 3);
+  ASSERT_ELIM (strlen (a) < 3);
+}
+
+void lower_bound_memcpy_memcpy_2 (void)
+{
+  memcpy (a, "123", 3);
+  memcpy (a + 2, "345", 3);
+  ASSERT_ELIM (strlen (a) < 5);
+}
+
+void lower_bound_memcpy_memcpy_3 (void)
+{
+  memcpy (a, "123", 3);
+  memcpy (a + 3, "456", 3);
+  ASSERT_ELIM (strlen (a) < 6);
+}
+
+/* FIXME: Not optimized yet.
+void lower_bound_stpcpy_stpcpy_assign (void)
+{
+  *stpcpy (strcpy (a, "123"), "4567") = '8';
+  ASSERT_ELIM (strlen (a) < 8);
+}
+*/
+
+void lower_bound_strcpy_strcat_assign (void)
+{
+  strcpy (a, "123");
+  strcat (a, "45");
+  a[5] = '6';
+  ASSERT_ELIM (strlen (a) < 6);
+}
+
+/* { dg-final { scan-tree-dump-times "call_in_true_branch_not_eliminated_" 0 "optimized" } } */
Index: gcc/testsuite/gcc.dg/strlenopt-70.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-70.c	(revision 274485)
+++ gcc/testsuite/gcc.dg/strlenopt-70.c	(revision 274486)
@@ -201,14 +201,17 @@ void store_32bit (volatile int i)
   T ("xxx",  uint32_t, 0, I32 ("\1\2\3\0"), == 3);
   T ("xxx",  uint32_t, 0, I32 ("\0\1\2\3"), == 0);
 
-  uint32_t x00332211 = I32 ("123\0");
-  uint32_t x00002211 = I32 ("12\0\0");
-  uint32_t x00000011 = I32 ("1\0\0\0");
+  uint32_t x123_ = I32 ("123\0");
+  uint32_t x12__ = I32 ("12\0\0");
+  uint32_t x1___ = I32 ("1\0\0\0");
 
-  T ("xxxx", uint32_t, 0, i ? x00332211 : x00002211, <= 3);
-  T ("xxxx", uint32_t, 0, i ? x00332211 : x00002211, >= 2);
-  T ("xxxx", uint32_t, 0, i ? x00332211 : x00000011, <= 3);
-  T ("xxxx", uint32_t, 0, i ? x00332211 : x00000011, >= 1);
+  // FIXME: Upper bound not implemented yet.
+  /* T ("xxxx", uint32_t, 0, i ? x123_ : x12__, <= 3); */
+  T ("xxxx", uint32_t, 0, i ? x123_ : x12__, >= 2);
+  T ("xxxx", uint32_t, 0, i ? x12__ : x123_, >= 2);
+  /* T ("xxxx", uint32_t, 0, i ? x123_ : x1___, <= 3); */
+  T ("xxxx", uint32_t, 0, i ? x123_ : x1___, >= 1);
+  T ("xxxx", uint32_t, 0, i ? x1___ : x123_, >= 1);
 
   TX ("abcde",  uint32_t, 0, i ? I32 ("1234") : I32 ("1235"), == 5);
   TX ("abcde",  uint32_t, 1, i ? I32 ("1234") : I32 ("1235"), == 5);
@@ -220,7 +223,8 @@ void store_32bit (volatile int i)
   TX ("abcdef", uint32_t, 3, i ? I32 ("12\0\0") : I32 ("13\0\0"), == 5);
 
   TX ("abcdef", uint32_t, 3, i ? I32 ("12\0\0") : I32 ("123\0"), >= 5);
-  TX ("abcdef", uint32_t, 3, i ? I32 ("12\0\0") : I32 ("123\0"), < 7);
+  /* FIXME: Upper bound not implemented yet.  */
+  /* TX ("abcdef", uint32_t, 3, i ? I32 ("12\0\0") : I32 ("123\0"), < 7); */
 }
 
 void store_64bit (int i)
@@ -246,17 +250,19 @@ void store_64bit (int i)
   T ("xxxxxxx", uint64_t, 0, I64 ("\1\2\3\4\5\6\0\0\0"), == 6);
   T ("xxxxxxx", uint64_t, 0, I64 ("\1\2\3\4\5\6\7\0\0"), == 7);
 
-  uint64_t x7777777 = I64 ("\7\7\7\7\7\7\7");
-  uint64_t x666666 = I64 ("\6\6\6\6\6\6\0");
-  uint64_t x4444 = I64 ("\4\4\4\4\0\0\0");
-  uint64_t x3333 = I64 ("\3\3\3\3\0\0\0");
-  uint64_t x1 = I64 ("\1\0\0\0\0\0\0");
+  uint64_t x7777777_ = I64 ("\7\7\7\7\7\7\7");
+  uint64_t x666666__ = I64 ("\6\6\6\6\6\6\0");
+  uint64_t x4444____ = I64 ("\4\4\4\4\0\0\0");
+  uint64_t x4343____ = I64 ("\4\3\4\3\0\0\0");
+  uint64_t x1_______ = I64 ("\1\0\0\0\0\0\0");
 
-  T ("x\0xxxxxx", uint64_t, 0, i ? x7777777 : x666666, <= 7);
-  T ("xx\0xxxxx", uint64_t, 0, i ? x7777777 : x666666, >= 6);
-  T ("xxx\0xxxx", uint64_t, 0, i ? x666666 : x1, <= 6);
-  T ("xxxx\0xxx", uint64_t, 0, i ? x666666 : x1, >= 1);
-  T ("xxxxxx\0x", uint64_t, 0, i ? x4444 : x3333, == 4);
+  /* FIXME: Upper bound not implemented yet.  */
+  /* T ("x\0xxxxxx", uint64_t, 0, i ? x7777777_ : x666666__, <= 7); */
+  T ("xx\0xxxxx", uint64_t, 0, i ? x7777777_ : x666666__, >= 6);
+  T ("xxx\0xxxx", uint64_t, 1, i ? x7777777_ : x666666__, >= 7);
+  /* T ("xxx\0xxxx", uint64_t, 0, i ? x666666__ : x1, <= 6); */
+  T ("xxxx\0xxx", uint64_t, 0, i ? x666666__ : x1_______, >= 1);
+  T ("xxxxxx\0x", uint64_t, 0, i ? x4444____ : x4343____, == 4);
 }
 
 #if __SIZEOF_INT128__
Index: gcc/testsuite/gcc.dg/strlenopt-44.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-44.c	(revision 274485)
+++ gcc/testsuite/gcc.dg/strlenopt-44.c	(revision 274486)
@@ -83,7 +83,7 @@ void test_keep (void)
   size_t uchar_max = (unsigned char)-1;
 
   KEEP ("1",     0, UR (1, uchar_max + 1), 1);
-  KEEP ("1\0\3", 1, UR (1, 2), 1);
+  KEEP ("1\0\3", 1, UR (1, 2), 2);
 }
 
 /* { dg-final { scan-tree-dump-times "call_in_true_branch_not_eliminated_" 0 "optimized" } }
Index: gcc/testsuite/gcc.dg/strlenopt-73.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-73.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-73.c	(revision 274486)
@@ -0,0 +1,133 @@
+/* PR tree-optimization/91183 - strlen of a strcpy result with a conditional
+   source not folded
+   Test to verify that strlen can determine string lengths from stores
+   involving PHI nodes with distinct strings of the same length of at
+   least 16 bytes.
+
+   { dg-do compile }
+   { dg-options "-O2 -fdump-tree-optimized" }
+   On strictly aligned targets the consecutive char assignments used
+   by the test aren't merged.  When they involve multiple trailing nuls
+   these assignments then defeat the strlen optimization as a result of
+   pr83821.  When the bug is resolved the directive below can be removed.
+   { dg-require-effective-target non_strict_align } */
+
+#include "strlenopt.h"
+
+#define CAT(x, y) x ## y
+#define CONCAT(x, y) CAT (x, y)
+#define FAILNAME(name) CONCAT (call_ ## name ##_on_line_, __LINE__)
+
+#define FAIL(name) do {				\
+    extern void FAILNAME (name) (void);		\
+    FAILNAME (name)();				\
+  } while (0)
+
+/* Macros to emit a call to function named
+     call_failed_to_be_eliminated_on_line_NNN()
+   for each call that's expected to be eliminated.  The dg-final
+   scan-tree-dump-time directive at the bottom of the test verifies
+   that no such call appears in output.  */
+#define ELIM(expr)				\
+  if ((expr)) FAIL (not_eliminated); else (void)0
+
+#define T(expect, N, ncpy, cond) do {		\
+    char CONCAT (arr_, __LINE__)[N];		\
+    char *pa = CONCAT (arr_, __LINE__);		\
+    memcpy (pa, cond, ncpy);			\
+    ELIM (!(expect strlen (pa)));		\
+    sink (pa);					\
+  } while (0)
+
+void sink (void*);
+
+const char a32[33] = "0123456789abcdef0123456789abcdef";
+const char b32[33] = "fedcba9876543210fedcba9876543210";
+
+const char a16[33] = "0123456789abcdef";
+const char b16[33] = "fedcba9876543210";
+
+int i0, i1, i2;
+
+void test_copy_cond_equal_length (void)
+{
+  // The test below is represented as this:
+  //   # iftmp.0_3 = PHI <&b16(2), &a16(3)>
+  //   MEM <unsigned char[17]> [(char * {ref-all})&a]
+  //     = MEM <unsigned char[17]> [(char * {ref-all})iftmp.0_3];
+  //   _2 = strlen (&a);
+  T (16 ==, 17, 17, i0 ? a16 : b16);
+  T (16 ==, 17, 17, i0 ? a16 : b16);
+  T (15 ==, 17, 16, (i0 ? a16 : b16) +  1);
+  T (14 ==, 17, 15, (i0 ? a16 : b16) +  2);
+  T ( 0 ==, 17,  1, (i0 ? a16 : b16) + 16);
+
+  T (31 ==, 33, 32, (i0 ? a32 : b32) +  1);
+  T (30 ==, 33, 31, (i0 ? a32 : b32) +  2);
+  T (29 ==, 33, 30, (i0 ? a32 : b32) +  3);
+  T ( 1 ==, 33,  2, (i0 ? a32 : b32) + 31);
+  T ( 0 ==, 33,  1, (i0 ? a32 : b32) + 32);
+}
+
+
+const char a4[16] = "0123";
+const char b4[16] = "3210";
+
+void test_copy_cond_unequal_length_i64 (void)
+{
+  T (2 <, 16, 8, i0 ? a4 + 1 : b4 + 0);
+  T (1 <, 16, 8, i0 ? a4 + 1 : b4 + 2);
+  T (0 <, 16, 8, i0 ? a4 + 1 : b4 + 3);
+
+  T (1 <, 16, 8, i0 ? a4 + 2 : b4 + 0);
+  T (1 <, 16, 8, i0 ? a4 + 2 : b4 + 1);
+  T (0 <, 16, 8, i0 ? a4 + 2 : b4 + 3);
+}
+
+
+#if __SIZEOF_INT128__ == 16
+
+/* The following tests assume GCC transforms the memcpy calls into
+   int128_t assignments which it does only when int128_t is supported.  */
+
+const char a8[32] = "01234567";
+const char b8[32] = "76543210";
+
+void test_copy_cond_unequal_length_i128 (void)
+{
+  T (6 <, 32, 16, i0 ? a8 + 1 : b8 + 0);
+  T (5 <, 32, 16, i0 ? a8 + 1 : b8 + 2);
+  T (4 <, 32, 16, i0 ? a8 + 1 : b8 + 3);
+  T (3 <, 32, 16, i0 ? a8 + 1 : b8 + 4);
+  T (2 <, 32, 16, i0 ? a8 + 1 : b8 + 5);
+  T (1 <, 32, 16, i0 ? a8 + 1 : b8 + 6);
+  T (0 <, 32, 16, i0 ? a8 + 1 : b8 + 7);
+
+  T (5 <, 32, 16, i0 ? a8 + 2 : b8 + 0);
+  T (5 <, 32, 16, i0 ? a8 + 2 : b8 + 1);
+  T (3 <, 32, 16, i0 ? a8 + 2 : b8 + 3);
+  T (2 <, 32, 16, i0 ? a8 + 2 : b8 + 4);
+  T (1 <, 32, 16, i0 ? a8 + 2 : b8 + 5);
+  T (0 <, 32, 16, i0 ? a8 + 2 : b8 + 6);
+
+  T (4 <, 32, 16, i0 ? a8 + 3 : b8 + 0);
+  T (4 <, 32, 16, i0 ? a8 + 3 : b8 + 1);
+  T (4 <, 32, 16, i0 ? a8 + 3 : b8 + 2);
+  T (3 <, 32, 16, i0 ? a8 + 3 : b8 + 4);
+  T (2 <, 32, 16, i0 ? a8 + 3 : b8 + 5);
+  T (1 <, 32, 16, i0 ? a8 + 3 : b8 + 6);
+  T (0 <, 32, 16, i0 ? a8 + 3 : b8 + 7);
+
+  T (3 <, 32, 16, i0 ? a8 + 4 : b8 + 0);
+  T (3 <, 32, 16, i0 ? a8 + 4 : b8 + 1);
+  T (3 <, 32, 16, i0 ? a8 + 4 : b8 + 2);
+  T (3 <, 32, 16, i0 ? a8 + 4 : b8 + 3);
+  T (2 <, 32, 16, i0 ? a8 + 4 : b8 + 5);
+  T (1 <, 32, 16, i0 ? a8 + 4 : b8 + 6);
+  T (0 <, 32, 16, i0 ? a8 + 4 : b8 + 7);
+}
+
+#endif   /* int128_t exists */
+
+/* { dg-final { scan-tree-dump-times "strlen" 0 "optimized" } }
+   { dg-final { scan-tree-dump-times "_not_eliminated_" 0 "optimized" } } */
Index: gcc/testsuite/gcc.dg/strlenopt-74.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-74.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-74.c	(revision 274486)
@@ -0,0 +1,175 @@
+/* PR tree-optimization/91294 - wrong strlen result of a conditional with
+   an offset
+   { dg-do run }
+   { dg-options "-O2 -Wall" } */
+
+#include "strlenopt.h"
+
+#define NOIPA __attribute__ ((noclone, noinline, noipa))
+
+#define CAT(a, b) a ## b
+#define CONCAT(a, b) CAT (a, b)
+#define UNIQ_NAME(name) CONCAT (name, __LINE__)
+
+extern int last_line;
+int nfails;
+
+char buf[32];
+
+#define VERIFY(expr, nbytes, expect)					\
+  NOIPA void UNIQ_NAME (test_)(void)					\
+  {									\
+    memcpy (buf, (expr), (nbytes));					\
+    const size_t len = strlen (buf);					\
+    if (len != expect)							\
+      {									\
+	++nfails;							\
+	__builtin_printf ("line %i: strlen(%s) == %zu failed: "		\
+			  "got %zu\n",					\
+			  __LINE__ - 1000 + last_line + 2,		\
+			  #expr, (size_t)expect,			\
+			  len);						\
+      }									\
+  } typedef void DummyType
+
+const char a8[12] = "01234567";
+const char b8[12] = "76543210";
+const char c4[12] = "0123";
+
+int i0, i1 = 1, i2 = 2;
+
+int last_line = __LINE__;
+#line 1000
+VERIFY (i0 ? (a8 + 0) : (b8 + 0), 9, 8);
+VERIFY (i0 ? (a8 + 0) : (b8 + 1), 8, 7);
+VERIFY (i0 ? (a8 + 0) : (b8 + 2), 8, 6);
+VERIFY (i0 ? (a8 + 0) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 0) : (b8 + 3), 8, 5);
+VERIFY (i0 ? (a8 + 0) : (b8 + 3), 7, 5);
+VERIFY (i0 ? (a8 + 0) : (b8 + 3), 6, 5);
+VERIFY (i0 ? (a8 + 0) : (b8 + 4), 8, 4);
+VERIFY (i0 ? (a8 + 0) : (b8 + 4), 7, 4);
+VERIFY (i0 ? (a8 + 0) : (b8 + 4), 6, 4);
+VERIFY (i0 ? (a8 + 0) : (b8 + 4), 5, 4);
+VERIFY (i0 ? (a8 + 0) : (b8 + 5), 7, 3);
+VERIFY (i0 ? (a8 + 0) : (b8 + 5), 6, 3);
+VERIFY (i0 ? (a8 + 0) : (b8 + 5), 5, 3);
+VERIFY (i0 ? (a8 + 0) : (b8 + 5), 4, 3);
+VERIFY (i0 ? (a8 + 0) : (b8 + 6), 3, 2);
+VERIFY (i0 ? (a8 + 0) : (b8 + 7), 2, 1);
+VERIFY (i0 ? (a8 + 1) : (b8 + 0), 8, 8);
+VERIFY (i0 ? (a8 + 2) : (b8 + 0), 7, 7);
+VERIFY (i0 ? (a8 + 1) : (b8 + 1), 8, 7);
+VERIFY (i0 ? (a8 + 1) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 2) : (b8 + 1), 8, 7);   // FAIL
+VERIFY (i0 ? (a8 + 2) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 0) : (b8 + 0), 9, 8);
+VERIFY (i0 ? (a8 + 0) : (b8 + 1), 8, 7);
+VERIFY (i0 ? (a8 + 0) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 1) : (b8 + 0), 9, 8);
+VERIFY (i0 ? (a8 + 2) : (b8 + 0), 9, 8);
+VERIFY (i0 ? (a8 + 1) : (b8 + 1), 8, 7);
+VERIFY (i0 ? (a8 + 1) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 2) : (b8 + 1), 8, 7);   // FAIL
+VERIFY (i0 ? (a8 + 2) : (b8 + 2), 7, 6);
+VERIFY (i0 ? (a8 + 0) : (c4 + 0), 9, 4);
+VERIFY (i0 ? (a8 + 0) : (c4 + 1), 9, 3);
+VERIFY (i0 ? (a8 + 0) : (c4 + 3), 9, 1);
+VERIFY (i0 ? (a8 + 0) : (c4 + 4), 9, 0);
+VERIFY (i0 ? (a8 + 1) : (c4 + 0), 8, 4);
+VERIFY (i0 ? (a8 + 1) : (c4 + 1), 8, 3);
+VERIFY (i0 ? (a8 + 1) : (c4 + 2), 8, 2);
+VERIFY (i0 ? (a8 + 1) : (c4 + 3), 8, 1);
+VERIFY (i0 ? (a8 + 1) : (c4 + 4), 8, 0);
+VERIFY (i0 ? (a8 + 2) : (c4 + 0), 8, 4);
+VERIFY (i0 ? (a8 + 2) : (c4 + 1), 8, 3);
+VERIFY (i0 ? (a8 + 2) : (c4 + 2), 8, 2);
+VERIFY (i0 ? (a8 + 2) : (c4 + 3), 8, 1);
+VERIFY (i0 ? (a8 + 2) : (c4 + 4), 8, 0);
+VERIFY ((i0 ? a8 : b8) + 1, 8, 7);
+VERIFY ((i0 ? a8 : b8) + 2, 8, 6);
+VERIFY ((i0 ? a8 : b8) + 2, 7, 6);
+VERIFY ((i0 ? a8 : b8) + 3, 3, 3);
+VERIFY ((i0 ? a8 : b8) + 3, 1, 1);
+VERIFY ((i0 ? a8 : c4) + 1, 8, 3);
+VERIFY ((i0 ? a8 : c4) + 3, 8, 1);
+VERIFY ((i0 ? a8 : c4) + 4, 8, 0);
+VERIFY ((i0 ? a8 + 1: b8 + 2) + 1, 9, 5);
+VERIFY ((i0 ? a8 + i1: b8 + i2) + 1, 8, 5);
+VERIFY ((i0 ? a8 + i1: b8 + 2) + 1, 8, 5);
+VERIFY ((i0 ? a8 + i2: b8 + i1) + 1, 8, 6);
+VERIFY ((i0 ? a8 + 2: b8 + i1) + 1, 8, 6);
+
+#define T(N) test_ ## N (); memset (buf, 0, sizeof buf)
+
+int main (void)
+{
+  T (1000);
+  T (1001);
+  T (1002);
+  T (1003);
+  T (1004);
+  T (1005);
+  T (1006);
+  T (1007);
+  T (1008);
+  T (1009);
+
+  T (1010);
+  T (1011);
+  T (1012);
+  T (1013);
+  T (1014);
+  T (1015);
+  T (1016);
+  T (1017);
+  T (1018);
+  T (1019);
+
+  T (1020);
+  T (1021);
+  T (1022);
+  T (1023);
+  T (1024);
+  T (1025);
+  T (1026);
+  T (1027);
+  T (1028);
+  T (1029);
+
+  T (1030);
+  T (1031);
+  T (1032);
+  T (1033);
+  T (1034);
+  T (1035);
+  T (1036);
+  T (1037);
+  T (1038);
+  T (1039);
+
+  T (1040);
+  T (1041);
+  T (1042);
+  T (1043);
+  T (1044);
+  T (1045);
+  T (1046);
+  T (1047);
+  T (1048);
+  T (1049);
+
+  T (1050);
+  T (1051);
+  T (1052);
+  T (1053);
+  T (1054);
+  T (1055);
+  T (1056);
+  T (1057);
+  T (1058);
+
+  if (nfails)
+    abort ();
+}
+
Index: gcc/testsuite/gcc.dg/strlenopt-75.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-75.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-75.c	(revision 274486)
@@ -0,0 +1,118 @@
+/* PR tree-optimization/91294 - strlen result of a conditional with
+   an offset
+   { dg-do run }
+   { dg-options "-O2 -Wall" } */
+
+#include "strlenopt.h"
+
+#define NOIPA __attribute__ ((noclone, noinline, noipa))
+
+int i = 0;
+
+const char s[] = "1234567";
+
+char a[32];
+
+/* Exercise a memcpy overwriting a destination string of known length
+   with a source argument involving a conditional expression with strings
+   of unqual lengths, with the selected one being the longer of the two
+   and resulting in no change to the length of the overwritten destination
+   string.  */
+NOIPA void test_memcpy_same_length ()
+{
+  memcpy (a, "123456789a", 11);
+  memcpy (a + 6, i ? "78\0" : "789\0", 4);
+  if (strlen (a) != 9)
+    abort ();
+}
+
+/* Same as above but with strcpy/strcat.  */
+
+NOIPA void test_strcpy_strcat_same_length ()
+{
+  strcpy (a, "12345678");
+  strcat (a, "9a");
+  memcpy (a + 6, i ? "78\0" : "789\0", 4);
+  if (strlen (a) != 9)
+    abort ();
+}
+
+/* Same as above but using a memcpy of a power-of-two size that gets
+   (on some targets) transformed into a single MEM_REF assignment.  */
+
+NOIPA void test_assign_same_length ()
+{
+  memcpy (a, s, 8);
+  memcpy (a + 5, i ? "67\0" : "678\0", 4);
+  if (strlen (a) != 8)
+    abort ();
+}
+
+/* Same as above but resulting in increasing the length of the destination
+   string.  */
+
+NOIPA void test_memcpy_lengthen ()
+{
+  memcpy (a, "123456789a", 11);
+  memcpy (a + 8, i ? "9a\0" : "9ab\0", 4);
+  if (strlen (a) != 11)
+    abort ();
+}
+
+NOIPA void test_strcpy_strcat_lengthen ()
+{
+  strcpy (a, "12345678");
+  strcat (a, "9a");
+  memcpy (a + 8, i ? "9a\0" : "9ab\0", 4);
+  if (strlen (a) != 11)
+    abort ();
+}
+
+NOIPA void test_assign_lengthen ()
+{
+  memcpy (a, s, 8);
+  memcpy (a + 6, i ? "78\0" : "789\0", 4);
+  if (strlen (a) != 9)
+    abort ();
+}
+
+NOIPA void test_memcpy_shorten ()
+{
+  memcpy (a, "123456789a", 11);
+  memcpy (a + 6, i ? "789\0" : "78\0", 4);
+  if (strlen (a) != 8)
+    abort ();
+}
+
+NOIPA void test_strcpy_strcat_shorten ()
+{
+  strcpy (a, "12345678");
+  strcat (a, "9a");
+  memcpy (a + 6, i ? "789\0" : "78\0", 4);
+  if (strlen (a) != 8)
+    abort ();
+}
+
+NOIPA void test_assign_shorten ()
+{
+  memcpy (a, s, 8);
+  memcpy (a + 6, i ? "789\0" : "78\0", 4);
+  if (strlen (a) != 8)
+    abort ();
+}
+
+
+int main (void)
+{
+  test_memcpy_same_length ();
+  test_strcpy_strcat_same_length ();
+  test_assign_same_length ();
+
+  test_memcpy_lengthen ();
+  test_strcpy_strcat_lengthen ();
+  test_assign_lengthen ();
+
+  test_memcpy_shorten ();
+  test_strcpy_strcat_shorten ();
+  test_assign_shorten ();
+}
Index: gcc/testsuite/gcc.dg/strlenopt-76.c
===================================================================
--- gcc/testsuite/gcc.dg/strlenopt-76.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/strlenopt-76.c	(revision 274486)
@@ -0,0 +1,174 @@
+/* PR tree-optimization/91294 - strlen result of a conditional with
+   an offset
+   { dg-do run }
+   { dg-options "-O2 -Wall" } */
+
+#include "strlenopt.h"
+
+#define NOIPA __attribute__ ((noclone, noinline, noipa))
+
+#define assert(expr)						\
+  ((expr)                                                       \
+   ? (void)0                                                    \
+   : (__builtin_printf ("line %i %s: assertion failed: %s\n",	\
+                        __LINE__, __func__, #expr),		\
+      __builtin_abort ()))
+
+int i = 0;
+
+const char s[] = "1234567";
+
+char a[32];
+
+NOIPA void lower_bound_assign_into_empty (void)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  assert (strlen (a) == 3);
+}
+
+NOIPA void lower_bound_assign_into_longest (void)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  assert (strlen (a) == 31);
+}
+
+
+NOIPA void lower_bound_assign_into_empty_idx_3 (int idx)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  a[idx] = 'x';
+  assert (strlen (a) == 4);
+}
+
+NOIPA void lower_bound_assign_into_longest_idx_2 (int idx)
+{
+  a[0] = '1';
+  a[1] = '2';
+  a[2] = '3';
+  a[idx] = '\0';
+  assert (strlen (a) == 2);
+}
+
+
+NOIPA void lower_bound_memcpy_into_empty (void)
+{
+  memcpy (a, "123", 3);
+  assert (strlen (a) == 3);
+}
+
+NOIPA void lower_bound_memcpy_into_longest (void)
+{
+  memcpy (a, "123", 3);
+  assert (strlen (a) == 31);
+}
+
+
+NOIPA void lower_bound_memcpy_memcpy_into_empty (void)
+{
+  memcpy (a, "123", 3);
+  memcpy (a + 2, "345", 3);
+  assert (strlen (a) == 5);
+}
+
+NOIPA void lower_bound_memcpy_memcpy_into_longest (void)
+{
+  memcpy (a, "123", 3);
+  memcpy (a + 2, "345", 3);
+  assert (strlen (a) == 31);
+}
+
+
+NOIPA void memove_forward_strlen (void)
+{
+  char a[] = "123456";
+
+  memmove (a, a + 1, sizeof a - 1);
+
+  assert (strlen (a) == 5);
+}
+
+NOIPA void memove_backward_into_empty_strlen (void)
+{
+  strcpy (a, "123456");
+
+  memmove (a + 1, a, 6);
+
+  assert (strlen (a) == 7);
+}
+
+NOIPA void memove_backward_into_longest_strlen (void)
+{
+  memcpy (a, "123456", 6);
+
+  memmove (a + 1, a, 6);
+
+  assert (strlen (a) == 31);
+}
+
+NOIPA void memove_strcmp (void)
+{
+  /* Test derived from libstdc++-v3's
+     20_util/specialized_algorithms/memory_management_tools/1.cc  */
+
+  char a[] = "123456";
+  char b[] = "000000";
+
+  memmove (b, a, sizeof a);
+
+  assert (strlen (a) == 6);
+  assert (strlen (b) == 6);
+  assert (strcmp (a, b) == 0);
+}
+
+
+int main (void)
+{
+  memset (a, '\0', sizeof a);
+  lower_bound_assign_into_empty ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_assign_into_longest ();
+
+  memset (a, '\0', sizeof a);
+  lower_bound_assign_into_empty_idx_3 (3);
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_assign_into_longest_idx_2 (2);
+
+  memset (a, '\0', sizeof a);
+  lower_bound_memcpy_into_empty ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_memcpy_into_longest ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_memcpy_into_longest ();
+
+  memset (a, '\0', sizeof a);
+  lower_bound_memcpy_memcpy_into_empty ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  lower_bound_memcpy_memcpy_into_longest ();
+
+  memove_forward_strlen ();
+
+  memset (a, '\0', sizeof a);
+  memove_backward_into_empty_strlen ();
+
+  memset (a, 'x', sizeof a - 1);
+  a[sizeof a - 1] = '\0';
+  memove_backward_into_longest_strlen ();
+
+  memove_strcmp ();
+}
Index: gcc/testsuite/ChangeLog
===================================================================
--- gcc/testsuite/ChangeLog	(revision 274485)
+++ gcc/testsuite/ChangeLog	(revision 274486)
@@ -1,3 +1,14 @@
+2019-08-14  Martin Sebor  <msebor@redhat.com>
+
+	PR tree-optimization/91294
+	* gcc.dg/strlenopt-44.c: Adjust tested result.
+	* gcc.dg/strlenopt-70.c: Avoid exercising unimplemnted optimization.
+	* gcc.dg/strlenopt-73.c: New test.
+	* gcc.dg/strlenopt-74.c: New test.
+	* gcc.dg/strlenopt-75.c: New test.
+	* gcc.dg/strlenopt-76.c: New test.
+	* gcc.dg/strlenopt-77.c: New test.
+
 2019-08-14  Jakub Jelinek  <jakub@redhat.com>
 	    Marek Polacek  <polacek@redhat.com>
 
Index: gcc/gimple-fold.c
===================================================================
--- gcc/gimple-fold.c	(revision 274485)
+++ gcc/gimple-fold.c	(revision 274486)
@@ -3726,7 +3726,7 @@ gimple_fold_builtin_strlen (gimple_stmt_iterator *
 
   /* Set the strlen() range to [0, MAXLEN].  */
   if (tree lhs = gimple_call_lhs (stmt))
-    set_strlen_range (lhs, maxlen);
+    set_strlen_range (lhs, minlen, maxlen);
 
   return false;
 }

^ permalink raw reply	[flat|nested] 6+ messages in thread

* Re: [PATCH] fix and improve strlen conditional handling of merged stores (PR 91183, 91294, 91315)
  2019-08-14 16:49       ` Martin Sebor
@ 2019-08-14 16:51         ` Martin Sebor
  0 siblings, 0 replies; 6+ messages in thread
From: Martin Sebor @ 2019-08-14 16:51 UTC (permalink / raw)
  To: Jeff Law, gcc-patches

>>> Do you want me to post another revision with
>>> the gimple_assign_single_p test removed?
>> I think remove that hunk, bootstrap, test, commit and post for archival
>> purposes.Â  I do not think another round of review is necessary.
> 
> Done in r274486 (also attached).

I should add that the early store merging on loosely aligned
targets makes the strlen tests prone to failures on strictly
aligned targets (or even ILP32 targets).  The handle_store
function can now deal with all sorts of MEM_REF assignments
that result from the store merging, but because
the handle_builtin_memcpy function lacks the same support,
the tests that expect the assignments to be folded fail when
they are not merged.  For example, the strlen call below is
folded on i386:

   const char a4[32] = "0123";
   const char b4[32] = "3210";

   void f (int i)
   {
     char a[32];
     memcpy (a, i ? a4 + 1 : b4, 8);   // copy just 8 bytes
     if (strlen (a) < 3)
       abort ();
   }

but the equivalent call below is not:

   void g (int i)
   {
     char a[32];
     memcpy (a, i ? a4 + 1 : b4, 16);   // copy 16 bytes
     if (strlen (a) < 3)
       abort ();
   }

This pattern may not be very common in the wild but having
the pass behave consistently without these target dependencies
would be helpful in avoiding these test failures.  I will try
to remember to extend the same enhancement as in handle_store
to handle_builtin_memcpy (ideally by factoring the code out
of handle_store into a helper and letting both functions call
it to do the folding).

Martin

^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, other threads:[~2019-08-14 16:40 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-08-01  0:36 [PATCH] fix and improve strlen conditional handling of merged stores (PR 91183, 91294, 91315) Martin Sebor
2019-08-09  7:15 ` Jeff Law
2019-08-10  5:26   ` Martin Sebor
2019-08-12 20:04     ` Jeff Law
2019-08-14 16:49       ` Martin Sebor
2019-08-14 16:51         ` Martin Sebor

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).