From 34fcf41e30ff56155e996f5e04f6ca13948a19b6 Mon Sep 17 00:00:00 2001 From: Martin Sebor Date: Wed, 14 Aug 2019 16:27:59 +0000 Subject: [PATCH] PR tree-optimization/91294 - [10 Regression] wrong strlen result of a conditional with an offset gcc/testsuite/ChangeLog: 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. gcc/ChangeLog: PR tree-optimization/91294 * tree-ssa-strlen.c (handle_store): Avoid treating lower bound of source length as exact. From-SVN: r274486 --- gcc/ChangeLog | 6 + gcc/gimple-fold.c | 2 +- gcc/testsuite/ChangeLog | 11 ++ gcc/testsuite/gcc.dg/strlenopt-44.c | 2 +- gcc/testsuite/gcc.dg/strlenopt-70.c | 46 ++++--- gcc/testsuite/gcc.dg/strlenopt-73.c | 133 +++++++++++++++++++ gcc/testsuite/gcc.dg/strlenopt-74.c | 175 +++++++++++++++++++++++++ gcc/testsuite/gcc.dg/strlenopt-75.c | 118 +++++++++++++++++ gcc/testsuite/gcc.dg/strlenopt-76.c | 174 +++++++++++++++++++++++++ gcc/testsuite/gcc.dg/strlenopt-77.c | 84 ++++++++++++ gcc/tree-ssa-strlen.c | 194 +++++++++++++++++----------- gcc/tree-ssa-strlen.h | 2 +- 12 files changed, 847 insertions(+), 100 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/strlenopt-73.c create mode 100644 gcc/testsuite/gcc.dg/strlenopt-74.c create mode 100644 gcc/testsuite/gcc.dg/strlenopt-75.c create mode 100644 gcc/testsuite/gcc.dg/strlenopt-76.c create mode 100644 gcc/testsuite/gcc.dg/strlenopt-77.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 30665a69f0c..7e2158be4a1 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2019-08-14 Martin Sebor + + PR tree-optimization/91294 + * tree-ssa-strlen.c (handle_store): Avoid treating lower bound of + source length as exact. + 2019-08-14 Christophe Lyon * doc/extend.texi: Add "noinit" attribute documentation. diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c index fc57fb45e3a..d576b0842f9 100644 --- a/gcc/gimple-fold.c +++ b/gcc/gimple-fold.c @@ -3726,7 +3726,7 @@ gimple_fold_builtin_strlen (gimple_stmt_iterator *gsi) /* 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; } diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index db9cba6532f..ceb12b37eee 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,14 @@ +2019-08-14 Martin Sebor + + 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 Marek Polacek diff --git a/gcc/testsuite/gcc.dg/strlenopt-44.c b/gcc/testsuite/gcc.dg/strlenopt-44.c index 0c0108832fc..0af78acaf1d 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-44.c +++ b/gcc/testsuite/gcc.dg/strlenopt-44.c @@ -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" } } diff --git a/gcc/testsuite/gcc.dg/strlenopt-70.c b/gcc/testsuite/gcc.dg/strlenopt-70.c index 97ba1408f10..0853023c3b6 100644 --- a/gcc/testsuite/gcc.dg/strlenopt-70.c +++ b/gcc/testsuite/gcc.dg/strlenopt-70.c @@ -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"); - - 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); + uint32_t x123_ = I32 ("123\0"); + uint32_t x12__ = I32 ("12\0\0"); + uint32_t x1___ = I32 ("1\0\0\0"); + + // 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"); - - 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); + 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"); + + /* 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__ diff --git a/gcc/testsuite/gcc.dg/strlenopt-73.c b/gcc/testsuite/gcc.dg/strlenopt-73.c new file mode 100644 index 00000000000..4f13afd5ee5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-73.c @@ -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 [(char * {ref-all})&a] + // = MEM [(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" } } */ diff --git a/gcc/testsuite/gcc.dg/strlenopt-74.c b/gcc/testsuite/gcc.dg/strlenopt-74.c new file mode 100644 index 00000000000..0a9ac6c1da2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-74.c @@ -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 (); +} + diff --git a/gcc/testsuite/gcc.dg/strlenopt-75.c b/gcc/testsuite/gcc.dg/strlenopt-75.c new file mode 100644 index 00000000000..e57f0c4bcfb --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-75.c @@ -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 (); +} diff --git a/gcc/testsuite/gcc.dg/strlenopt-76.c b/gcc/testsuite/gcc.dg/strlenopt-76.c new file mode 100644 index 00000000000..30ccd166a11 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-76.c @@ -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 (); +} diff --git a/gcc/testsuite/gcc.dg/strlenopt-77.c b/gcc/testsuite/gcc.dg/strlenopt-77.c new file mode 100644 index 00000000000..76cd11d6ac1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-77.c @@ -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" } } */ diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c index 4af47855e7c..ef2b6ae65f2 100644 --- a/gcc/tree-ssa-strlen.c +++ b/gcc/tree-ssa-strlen.c @@ -1195,14 +1195,13 @@ adjust_last_stmt (strinfo *si, gimple *stmt, bool is_strcat) 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 bound) } } - 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 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm, (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,35 +3471,28 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm, 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; } 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); + 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 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm, 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 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm, 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 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm, 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 (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 (buf); } /* Compute the number of leading nonzero bytes in the representation @@ -3591,7 +3607,8 @@ count_nonzero_bytes (tree exp, unsigned lenrange[3], bool *nulterm, *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)); diff --git a/gcc/tree-ssa-strlen.h b/gcc/tree-ssa-strlen.h index 0b68465eb2b..395c74e88e1 100644 --- a/gcc/tree-ssa-strlen.h +++ b/gcc/tree-ssa-strlen.h @@ -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 -- 2.30.2