From aca8570e11d28b8c33d26593df6d4725a6140aab Mon Sep 17 00:00:00 2001 From: Martin Sebor Date: Thu, 26 Jul 2018 16:45:43 +0000 Subject: [PATCH] PR tree-optimization/86043 - strlen after memcpy partially overwriting a string not optimized PR tree-optimization/86043 - strlen after memcpy partially overwriting a string not optimized PR tree-optimization/86042 - missing strlen optimization after second strcpy gcc/ChangeLog: PR tree-optimization/86043 PR tree-optimization/86042 * tree-ssa-strlen.c (handle_builtin_memcpy): Handle strict overlaps. (get_string_cst_length): Rename... (get_min_string_length): ...to this. Add argument. (handle_char_store): Extend to handle multi-character stores by MEM_REF. * tree.c (initializer_zerop): Use new argument. Handle MEM_REF. * tree.h (initializer_zerop): Add argument. gcc/testsuite/ChangeLog: PR tree-optimization/86043 PR tree-optimization/86042 * gcc/testsuite/gcc.dg/attr-nonstring-2.c: Xfail test cases due to pr86688. * gcc.dg/strlenopt-44.c: New test. From-SVN: r263018 --- gcc/ChangeLog | 12 +++ gcc/testsuite/ChangeLog | 8 ++ gcc/testsuite/gcc.dg/attr-nonstring-2.c | 8 +- gcc/testsuite/gcc.dg/strlenopt-54.c | 109 ++++++++++++++++++++++++ gcc/tree-ssa-strlen.c | 109 ++++++++++++++++++------ gcc/tree.c | 103 +++++++++++++++++----- gcc/tree.h | 8 +- 7 files changed, 306 insertions(+), 51 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/strlenopt-54.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index ceaa404c9ba..f5e8d62c7b9 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2018-07-26 Martin Sebor + + PR tree-optimization/86043 + PR tree-optimization/86042 + * tree-ssa-strlen.c (handle_builtin_memcpy): Handle strict overlaps. + (get_string_cst_length): Rename... + (get_min_string_length): ...to this. Add argument. + (handle_char_store): Extend to handle multi-character stores by + MEM_REF. + * tree.c (initializer_zerop): Use new argument. Handle MEM_REF. + * tree.h (initializer_zerop): Add argument. + 2018-07-26 Jakub Jelinek PR middle-end/86660 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 7642560f276..30f528eea86 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,11 @@ +2018-07-26 Martin Sebor + + PR tree-optimization/86043 + PR tree-optimization/86042 + * gcc/testsuite/gcc.dg/attr-nonstring-2.c: Xfail test cases due to + pr86688. + * gcc.dg/strlenopt-44.c: New test. + 2018-07-26 Martin Liska PR gcov-profile/86536 diff --git a/gcc/testsuite/gcc.dg/attr-nonstring-2.c b/gcc/testsuite/gcc.dg/attr-nonstring-2.c index ef2144d6207..246a3729a2a 100644 --- a/gcc/testsuite/gcc.dg/attr-nonstring-2.c +++ b/gcc/testsuite/gcc.dg/attr-nonstring-2.c @@ -73,8 +73,8 @@ void test_strnlen_string_cst (void) T (3, "12", 3, 1); T (3, "12", 3, 9); T (3, "123", 3, 1); - T (3, "123", 3, 4); /* { dg-warning "argument 1 declared attribute .nonstring. is smaller than the specified bound 4" } */ - T (3, "123", 3, 9); /* { dg-warning "argument 1 declared attribute .nonstring. is smaller than the specified bound 9" } */ + T (3, "123", 3, 4); /* { dg-warning "argument 1 declared attribute .nonstring. is smaller than the specified bound 4" "bug 86688" { xfail *-*-* } } */ + T (3, "123", 3, 9); /* { dg-warning "argument 1 declared attribute .nonstring. is smaller than the specified bound 9" "bug 86688" { xfail *-*-* } } */ T (5, "1", 2, 1); T (5, "1", 2, 2); @@ -110,6 +110,6 @@ void test_strnlen_string_range (void) { T (3, "1", 2, UR (0, 1)); T (3, "1", 2, UR (3, 9)); - T (3, "123", 3, UR (4, 5)); /* { dg-warning "argument 1 declared attribute .nonstring. is smaller than the specified bound \\\[4, 5]" } */ - T (3, "123", 3, UR (5, 9)); /* { dg-warning "argument 1 declared attribute .nonstring. is smaller than the specified bound \\\[5, 9]" } */ + T (3, "123", 3, UR (4, 5)); /* { dg-warning "argument 1 declared attribute .nonstring. is smaller than the specified bound \\\[4, 5]" "bug 86688" { xfail *-*-* } } */ + T (3, "123", 3, UR (5, 9)); /* { dg-warning "argument 1 declared attribute .nonstring. is smaller than the specified bound \\\[5, 9]" "bug 86688" { xfail *-*-* } } */ } diff --git a/gcc/testsuite/gcc.dg/strlenopt-54.c b/gcc/testsuite/gcc.dg/strlenopt-54.c new file mode 100644 index 00000000000..c38e7918f8b --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-54.c @@ -0,0 +1,109 @@ +/* PR tree-optimization/86042 - missing strlen optimization after second strcpy + { 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 ELIM(expr) \ + if (!(expr)) FAIL (in_true_branch_not_eliminated); else (void)0 + +void elim_after_duplicate_strcpy (void) +{ +#define T(N, assign, off, str, r0, r1) \ + do { \ + char a[N]; \ + strcpy (a, assign); \ + unsigned n0 = strlen (a); \ + strcpy (a + off, str); \ + unsigned n1 = strlen (a); \ + ELIM (n0 == r0 && n1 == r1); \ + } while (0) + + T (2, "", 0, "1", 0, 1); + + T (2, "1", 0, "2", 1, 1); + T (2, "1", 1, "", 1, 1); + + T (3, "\0", 0, "1", 0, 1); + T (3, "1", 1, "2", 1, 2); + + T (3, "12", 0, "23", 2, 2); + T (3, "12", 1, "3", 2, 2); + T (3, "12", 2, "", 2, 2); + + T (4, "1", 1, "23", 1, 3); + T (4, "12", 1, "23", 2, 3); + + T (4, "123", 0, "234", 3, 3); + T (4, "123", 1, "34", 3, 3); + T (4, "123", 2, "4", 3, 3); + T (4, "123", 3, "", 3, 3); + + T (5, "1234", 0, "1", 4, 1); + T (5, "1234", 0, "12", 4, 2); + T (5, "1234", 0, "123", 4, 3); + T (5, "1234", 0, "1234", 4, 4); + + T (5, "123", 1, "234", 3, 4); + T (6, "123", 2, "234", 3, 5); +} + +void elim_after_init_memcpy (void) +{ +#undef T +#define T(init, off, str, n, res) \ + do { \ + char a[] = init; \ + memcpy (a + off, str, n); \ + ELIM (strlen (a) == res); \ + } while (0) + + T ("\0", 0, "1", 2, 1); + T ("\0\0", 0, "12", 3, 2); + +#define INIT { '1', '2', '3', '4' } + T (INIT, 0, "", 1, 0); + T (INIT, 0, "1", 2, 1); + T (INIT, 0, "12", 3, 2); + T (INIT, 0, "123", 4, 3); + + T ("1234", 0, "2", 1, 4); + T ("1234", 0, "23", 2, 4); + T ("1234", 0, "234", 3, 4); + T ("1234", 0, "2345", 4, 4); + T ("1234", 0, "2345", 5, 4); + + T ("1234", 1, "2", 1, 4); + T ("1234", 1, "23", 2, 4); + T ("1234", 1, "234", 3, 4); + T ("1234", 1, "234", 4, 4); + + T ("1234", 2, "3", 1, 4); + T ("1234", 2, "3", 2, 3); + T ("1234", 2, "34", 2, 4); + T ("1234", 2, "34", 3, 4); + + T ("12\00034", 0, "1", 1, 2); + T ("12\00034", 0, "1", 2, 1); + + T ("AB\000CD", 0, "ab", 2, 2); + T ("AB\000CD", 0, "ab", 3, 2); + T ("AB\000CD", 0, "ab\000c", 4, 2); +} + +/* { dg-final { scan-tree-dump-times "strlen" 0 "optimized" } } + { 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 736e2d946fc..eca88a56f72 100644 --- a/gcc/tree-ssa-strlen.c +++ b/gcc/tree-ssa-strlen.c @@ -2326,6 +2326,18 @@ handle_builtin_memcpy (enum built_in_function bcode, gimple_stmt_iterator *gsi) full_string_p = clen > nonzero_chars; } + if (!full_string_p + && olddsi + && olddsi->nonzero_chars + && TREE_CODE (olddsi->nonzero_chars) == INTEGER_CST + && tree_int_cst_le (newlen, olddsi->nonzero_chars)) + { + /* The SRC substring being written strictly overlaps + a subsequence of the existing string OLDDSI. */ + newlen = olddsi->nonzero_chars; + full_string_p = olddsi->full_string_p; + } + if (olddsi != NULL && TREE_CODE (len) == SSA_NAME) adjust_last_stmt (olddsi, stmt, false); @@ -3131,11 +3143,25 @@ handle_pointer_plus (gimple_stmt_iterator *gsi) } /* If RHS, either directly or indirectly, refers to a string of constant - length, return it. Otherwise return a negative value. */ + length, return the length. Otherwise, if it refers to a character + constant, return 1 if the constant is non-zero and 0 if it is nul. + Otherwise, return a negative value. */ static HOST_WIDE_INT -get_string_cst_length (tree rhs) +get_min_string_length (tree rhs, bool *full_string_p) { + if (TREE_CODE (TREE_TYPE (rhs)) == INTEGER_TYPE) + { + if (tree_expr_nonzero_p (rhs)) + { + *full_string_p = false; + return 1; + } + + *full_string_p = true; + return 0; + } + if (TREE_CODE (rhs) == MEM_REF && integer_zerop (TREE_OPERAND (rhs, 1))) { @@ -3152,9 +3178,11 @@ get_string_cst_length (tree rhs) { strinfo *si = get_strinfo (idx); if (si - && si->full_string_p && tree_fits_shwi_p (si->nonzero_chars)) - return tree_to_shwi (si->nonzero_chars); + { + *full_string_p = si->full_string_p; + return tree_to_shwi (si->nonzero_chars); + } } } } @@ -3165,12 +3193,17 @@ get_string_cst_length (tree rhs) rhs = DECL_INITIAL (rhs); if (rhs && TREE_CODE (rhs) == STRING_CST) - return strlen (TREE_STRING_POINTER (rhs)); + { + *full_string_p = true; + return strlen (TREE_STRING_POINTER (rhs)); + } return -1; } -/* Handle a single character store. */ +/* Handle a single or multiple character store either by single + character assignment or by multi-character assignment from + MEM_REF. */ static bool handle_char_store (gimple_stmt_iterator *gsi) @@ -3208,8 +3241,15 @@ handle_char_store (gimple_stmt_iterator *gsi) si = get_strinfo (idx); } - bool storing_zero_p = initializer_zerop (rhs); - bool storing_nonzero_p = !storing_zero_p && tree_expr_nonzero_p (rhs); + /* STORING_NONZERO_P is true iff not all stored characters are zero. + STORING_ALL_ZEROS_P is true iff all stored characters are zero. + Both are false when it's impossible to determine which is true. */ + bool storing_nonzero_p; + bool storing_all_zeros_p = initializer_zerop (rhs, &storing_nonzero_p); + if (!storing_nonzero_p) + storing_nonzero_p = tree_expr_nonzero_p (rhs); + bool full_string_p = storing_all_zeros_p; + /* Set to the length of the string being assigned if known. */ HOST_WIDE_INT rhslen; @@ -3217,7 +3257,7 @@ handle_char_store (gimple_stmt_iterator *gsi) { int cmp = compare_nonzero_chars (si, offset); gcc_assert (offset == 0 || cmp >= 0); - if (storing_zero_p && cmp == 0 && si->full_string_p) + if (storing_all_zeros_p && cmp == 0 && si->full_string_p) { /* When overwriting a '\0' with a '\0', the store can be removed if we know it has been stored in the current function. */ @@ -3260,17 +3300,25 @@ handle_char_store (gimple_stmt_iterator *gsi) gsi_next (gsi); return false; } - else if (storing_zero_p || storing_nonzero_p || (offset != 0 && cmp > 0)) + else if (storing_all_zeros_p || storing_nonzero_p || (offset != 0 && cmp > 0)) { - /* When storing_nonzero_p, we know that the string now starts - with OFFSET + 1 nonzero characters, but don't know whether - there's a following nul terminator. + /* When STORING_NONZERO_P, we know that the string will start + with at least OFFSET + 1 nonzero characters. If storing + a single character, set si->NONZERO_CHARS to the result. + If storing multiple characters, try to determine the number + of leading non-zero characters and set si->NONZERO_CHARS to + the result instead. - When storing_zero_p, we know that the string is now OFFSET - characters long. + When STORING_ALL_ZEROS_P, we know that the string is now + OFFSET characters long. Otherwise, we're storing an unknown value at offset OFFSET, so need to clip the nonzero_chars to OFFSET. */ + bool full_string_p = storing_all_zeros_p; + HOST_WIDE_INT len = (storing_nonzero_p + ? get_min_string_length (rhs, &full_string_p) + : 1); + location_t loc = gimple_location (stmt); tree oldlen = si->nonzero_chars; if (cmp == 0 && si->full_string_p) @@ -3280,11 +3328,14 @@ handle_char_store (gimple_stmt_iterator *gsi) adjust_last_stmt (si, stmt, false); si = unshare_strinfo (si); if (storing_nonzero_p) - si->nonzero_chars = build_int_cst (size_type_node, offset + 1); + { + gcc_assert (len >= 0); + si->nonzero_chars = build_int_cst (size_type_node, offset + len); + } else si->nonzero_chars = build_int_cst (size_type_node, offset); - si->full_string_p = storing_zero_p; - if (storing_zero_p + si->full_string_p = full_string_p; + if (storing_all_zeros_p && ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) si->endptr = ssaname; @@ -3304,7 +3355,7 @@ handle_char_store (gimple_stmt_iterator *gsi) si->prev = 0; } } - else if (idx == 0 && (storing_zero_p || storing_nonzero_p)) + else if (idx == 0 && (storing_all_zeros_p || storing_nonzero_p)) { if (ssaname) idx = new_stridx (ssaname); @@ -3313,10 +3364,17 @@ handle_char_store (gimple_stmt_iterator *gsi) if (idx != 0) { tree ptr = (ssaname ? ssaname : build_fold_addr_expr (lhs)); - tree len = storing_nonzero_p ? size_one_node : size_zero_node; - si = new_strinfo (ptr, idx, len, storing_zero_p); + HOST_WIDE_INT slen = (storing_all_zeros_p + ? 0 + : (storing_nonzero_p + ? get_min_string_length (rhs, &full_string_p) + : -1)); + tree len = (slen <= 0 + ? size_zero_node + : build_int_cst (size_type_node, slen)); + si = new_strinfo (ptr, idx, len, slen >= 0 && full_string_p); set_strinfo (idx, si); - if (storing_zero_p + if (storing_all_zeros_p && ssaname && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssaname)) si->endptr = ssaname; @@ -3325,7 +3383,7 @@ handle_char_store (gimple_stmt_iterator *gsi) } } else if (idx == 0 - && (rhslen = get_string_cst_length (gimple_assign_rhs1 (stmt))) >= 0 + && (rhslen = get_min_string_length (rhs, &full_string_p)) >= 0 && ssaname == NULL_TREE && TREE_CODE (TREE_TYPE (lhs)) == ARRAY_TYPE) { @@ -3336,14 +3394,15 @@ handle_char_store (gimple_stmt_iterator *gsi) if (idx != 0) { si = new_strinfo (build_fold_addr_expr (lhs), idx, - build_int_cst (size_type_node, rhslen), true); + build_int_cst (size_type_node, rhslen), + full_string_p); set_strinfo (idx, si); si->dont_invalidate = true; } } } - if (si != NULL && offset == 0 && storing_zero_p) + if (si != NULL && offset == 0 && storing_all_zeros_p) { /* Allow adjust_last_stmt to remove it if the stored '\0' is immediately overwritten. */ diff --git a/gcc/tree.c b/gcc/tree.c index bace9c8af2e..28952e5b1cd 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -10643,61 +10643,124 @@ vector_cst_elt (const_tree t, unsigned int i) } /* Given an initializer INIT, return TRUE if INIT is zero or some - aggregate of zeros. Otherwise return FALSE. */ + aggregate of zeros. Otherwise return FALSE. If NONZERO is not + null, set *NONZERO if and only if INIT is known not to be all + zeros. The combination of return value of false and *NONZERO + false implies that INIT may but need not be all zeros. Other + combinations indicate definitive answers. */ + bool -initializer_zerop (const_tree init) +initializer_zerop (const_tree init, bool *nonzero /* = NULL */) { - tree elt; + bool dummy; + if (!nonzero) + nonzero = &dummy; + + /* Conservatively clear NONZERO and set it only if INIT is definitely + not all zero. */ + *nonzero = false; STRIP_NOPS (init); + unsigned HOST_WIDE_INT off = 0; + switch (TREE_CODE (init)) { case INTEGER_CST: - return integer_zerop (init); + if (integer_zerop (init)) + return true; + + *nonzero = true; + return false; case REAL_CST: /* ??? Note that this is not correct for C4X float formats. There, a bit pattern of all zeros is 1.0; 0.0 is encoded with the most negative exponent. */ - return real_zerop (init) - && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init)); + if (real_zerop (init) + && !REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init))) + return true; + + *nonzero = true; + return false; case FIXED_CST: - return fixed_zerop (init); + if (fixed_zerop (init)) + return true; + + *nonzero = true; + return false; case COMPLEX_CST: - return integer_zerop (init) - || (real_zerop (init) - && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init))) - && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init)))); + if (integer_zerop (init) + || (real_zerop (init) + && !REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init))) + && !REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))))) + return true; + + *nonzero = true; + return false; case VECTOR_CST: - return (VECTOR_CST_NPATTERNS (init) == 1 - && VECTOR_CST_DUPLICATE_P (init) - && initializer_zerop (VECTOR_CST_ENCODED_ELT (init, 0))); + if (VECTOR_CST_NPATTERNS (init) == 1 + && VECTOR_CST_DUPLICATE_P (init) + && initializer_zerop (VECTOR_CST_ENCODED_ELT (init, 0))) + return true; + + *nonzero = true; + return false; case CONSTRUCTOR: { - unsigned HOST_WIDE_INT idx; - if (TREE_CLOBBER_P (init)) return false; + + unsigned HOST_WIDE_INT idx; + tree elt; + FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt) - if (!initializer_zerop (elt)) + if (!initializer_zerop (elt, nonzero)) return false; + return true; } + case MEM_REF: + { + tree arg = TREE_OPERAND (init, 0); + if (TREE_CODE (arg) != ADDR_EXPR) + return false; + tree offset = TREE_OPERAND (init, 1); + if (TREE_CODE (offset) != INTEGER_CST + || !tree_fits_uhwi_p (offset)) + return false; + off = tree_to_uhwi (offset); + if (INT_MAX < off) + return false; + arg = TREE_OPERAND (arg, 0); + if (TREE_CODE (arg) != STRING_CST) + return false; + init = arg; + } + /* Fall through. */ + case STRING_CST: { - int i; + gcc_assert (off <= INT_MAX); + + int i = off; + int n = TREE_STRING_LENGTH (init); + if (n <= i) + return false; /* We need to loop through all elements to handle cases like "\0" and "\0foobar". */ - for (i = 0; i < TREE_STRING_LENGTH (init); ++i) + for (i = 0; i < n; ++i) if (TREE_STRING_POINTER (init)[i] != '\0') - return false; + { + *nonzero = true; + return false; + } return true; } diff --git a/gcc/tree.h b/gcc/tree.h index 70ac78130c0..7bed03553b2 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -4429,9 +4429,13 @@ extern int list_length (const_tree); extern tree first_field (const_tree); /* Given an initializer INIT, return TRUE if INIT is zero or some - aggregate of zeros. Otherwise return FALSE. */ + aggregate of zeros. Otherwise return FALSE. If NONZERO is not + null, set *NONZERO if and only if INIT is known not to be all + zeros. The combination of return value of false and *NONZERO + false implies that INIT may but need not be all zeros. Other + combinations indicate definitive answers. */ -extern bool initializer_zerop (const_tree); +extern bool initializer_zerop (const_tree, bool * = NULL); extern wide_int vector_cst_int_elt (const_tree, unsigned int); extern tree vector_cst_elt (const_tree, unsigned int); -- 2.30.2