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
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
