From 862088aa6349851465388eb0c691a79325c5eb7a Mon Sep 17 00:00:00 2001 From: Richard Sandiford Date: Sun, 2 Jul 2017 08:43:11 +0000 Subject: [PATCH] PR 80769: Incorrect strlen optimisation In this testcase, we (correctly) record after: strcpy (p1, "abcde"); char *p2 = strchr (p1, '\0'); strcpy (p2, q); that the length of p1 and p2 can be calculated by converting the second strcpy to: tmp = stpcpy (p2, q) and then doing tmp - p1 for p1 and tmp - p2 for p2. This is delayed until we know whether we actually need it. Then: char *p3 = strchr (p2, '\0'); forces us to calculate the length of p2 in this way. At this point we had three related strinfos: p1: delayed length, calculated from tmp = stpcpy (p2, q) p2: known length, tmp - p2 p3: known length, 0 After: memcpy (p3, "x", 2); we use adjust_related_strinfos to add 1 to each length. However, that didn't do anything for delayed lengths because: else if (si->stmt != NULL) /* Delayed length computation is unaffected. */ ; So after the memcpy we had: p1: delayed length, calculated from tmp = stpcpy (p2, q) p2: known length, tmp - p2 + 1 p3: known length, 1 where the length of p1 was no longer correct. 2017-05-16 Richard Sandiford gcc/ PR tree-optimization/80769 * tree-ssa-strlen.c (strinfo): Document that "stmt" is also used for malloc and calloc. Document the new invariant that all related strinfos have delayed lengths or none do. (verify_related_strinfos): Move earlier in file. (set_endptr_and_length): New function, split out from... (get_string_length): ...here. Also set the lengths of related strinfos. (zero_length_string): Assert that chainsi has known (rather than delayed) lengths. (adjust_related_strinfos): Likewise. gcc/testsuite/ PR tree-optimization/80769 * gcc.dg/strlenopt-31.c: New test. * gcc.dg/strlenopt-31g.c: Likewise. From-SVN: r249879 --- gcc/ChangeLog | 14 +++ gcc/testsuite/ChangeLog | 6 ++ gcc/testsuite/gcc.dg/strlenopt-31.c | 25 ++++++ gcc/testsuite/gcc.dg/strlenopt-31g.c | 9 ++ gcc/tree-ssa-strlen.c | 122 ++++++++++++++++----------- 5 files changed, 125 insertions(+), 51 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/strlenopt-31.c create mode 100644 gcc/testsuite/gcc.dg/strlenopt-31g.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 76944d5ea01..67019a53d4f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2017-07-02 Richard Sandiford + + PR tree-optimization/80769 + * tree-ssa-strlen.c (strinfo): Document that "stmt" is also used + for malloc and calloc. Document the new invariant that all related + strinfos have delayed lengths or none do. + (verify_related_strinfos): Move earlier in file. + (set_endptr_and_length): New function, split out from... + (get_string_length): ...here. Also set the lengths of related + strinfos. + (zero_length_string): Assert that chainsi has known (rather than + delayed) lengths. + (adjust_related_strinfos): Likewise. + 2017-07-02 Richard Sandiford PR tree-optimization/81136 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 46259217cc0..e4c6af6558b 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2017-07-02 Richard Sandiford + + PR tree-optimization/80769 + * gcc.dg/strlenopt-31.c: New test. + * gcc.dg/strlenopt-31g.c: Likewise. + 2017-07-02 Richard Sandiford PR tree-optimization/81136 diff --git a/gcc/testsuite/gcc.dg/strlenopt-31.c b/gcc/testsuite/gcc.dg/strlenopt-31.c new file mode 100644 index 00000000000..bdd46ba0000 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-31.c @@ -0,0 +1,25 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +#include "strlenopt.h" + +__attribute__((noinline, noclone)) int +bar (char *p1, const char *q) +{ + strcpy (p1, "abcde"); + char *p2 = strchr (p1, '\0'); + strcpy (p2, q); + char *p3 = strchr (p2, '\0'); + memcpy (p3, "x", 2); + return strlen (p1); +} + +int +main (void) +{ + char buffer[10]; + int res = bar (buffer, "foo"); + if (strcmp (buffer, "abcdefoox") != 0 || res != 9) + abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/strlenopt-31g.c b/gcc/testsuite/gcc.dg/strlenopt-31g.c new file mode 100644 index 00000000000..45cc29c1024 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-31g.c @@ -0,0 +1,9 @@ +/* { dg-do run { target *-*-linux* *-*-gnu* } } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +#define USE_GNU +#include "strlenopt-31.c" + +/* { dg-final { scan-tree-dump-times "stpcpy \\(" 1 "strlen" } } */ +/* { dg-final { scan-tree-dump-times "memcpy \\(" 2 "strlen" } } */ +/* { dg-final { scan-tree-dump-not "strlen \\(" "strlen" } } */ diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c index e4f18dba1e7..f46e64dee9a 100644 --- a/gcc/tree-ssa-strlen.c +++ b/gcc/tree-ssa-strlen.c @@ -61,7 +61,13 @@ struct strinfo tree length; /* Any of the corresponding pointers for querying alias oracle. */ tree ptr; - /* Statement for delayed length computation. */ + /* This is used for two things: + + - To record the statement that should be used for delayed length + computations. We maintain the invariant that all related strinfos + have delayed lengths or none do. + + - To record the malloc or calloc call that produced this result. */ gimple *stmt; /* Pointer to '\0' if known, if NULL, it can be computed as ptr + length. */ @@ -451,6 +457,45 @@ set_strinfo (int idx, strinfo *si) (*stridx_to_strinfo)[idx] = si; } +/* Return the first strinfo in the related strinfo chain + if all strinfos in between belong to the chain, otherwise NULL. */ + +static strinfo * +verify_related_strinfos (strinfo *origsi) +{ + strinfo *si = origsi, *psi; + + if (origsi->first == 0) + return NULL; + for (; si->prev; si = psi) + { + if (si->first != origsi->first) + return NULL; + psi = get_strinfo (si->prev); + if (psi == NULL) + return NULL; + if (psi->next != si->idx) + return NULL; + } + if (si->idx != si->first) + return NULL; + return si; +} + +/* Set SI's endptr to ENDPTR and compute its length based on SI->ptr. + Use LOC for folding. */ + +static void +set_endptr_and_length (location_t loc, strinfo *si, tree endptr) +{ + si->endptr = endptr; + si->stmt = NULL; + tree start_as_size = fold_convert_loc (loc, size_type_node, si->ptr); + tree end_as_size = fold_convert_loc (loc, size_type_node, endptr); + si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node, + end_as_size, start_as_size); +} + /* Return string length, or NULL if it can't be computed. */ static tree @@ -546,12 +591,12 @@ get_string_length (strinfo *si) case BUILT_IN_STPCPY_CHK_CHKP: gcc_assert (lhs != NULL_TREE); loc = gimple_location (stmt); - si->endptr = lhs; - si->stmt = NULL; - lhs = fold_convert_loc (loc, size_type_node, lhs); - si->length = fold_convert_loc (loc, size_type_node, si->ptr); - si->length = fold_build2_loc (loc, MINUS_EXPR, size_type_node, - lhs, si->length); + set_endptr_and_length (loc, si, lhs); + for (strinfo *chainsi = verify_related_strinfos (si); + chainsi != NULL; + chainsi = get_next_strinfo (chainsi)) + if (chainsi->length == NULL) + set_endptr_and_length (loc, chainsi, lhs); break; case BUILT_IN_MALLOC: break; @@ -620,32 +665,6 @@ unshare_strinfo (strinfo *si) return nsi; } -/* Return first strinfo in the related strinfo chain - if all strinfos in between belong to the chain, otherwise - NULL. */ - -static strinfo * -verify_related_strinfos (strinfo *origsi) -{ - strinfo *si = origsi, *psi; - - if (origsi->first == 0) - return NULL; - for (; si->prev; si = psi) - { - if (si->first != origsi->first) - return NULL; - psi = get_strinfo (si->prev); - if (psi == NULL) - return NULL; - if (psi->next != si->idx) - return NULL; - } - if (si->idx != si->first) - return NULL; - return si; -} - /* Attempt to create a new strinfo for BASESI + OFF, or find existing strinfo if there is any. Return it's idx, or 0 if no strinfo has been created. */ @@ -749,7 +768,8 @@ zero_length_string (tree ptr, strinfo *chainsi) { do { - gcc_assert (si->length || si->stmt); + /* We shouldn't mix delayed and non-delayed lengths. */ + gcc_assert (si->length); if (si->endptr == NULL_TREE) { si = unshare_strinfo (si); @@ -770,12 +790,17 @@ zero_length_string (tree ptr, strinfo *chainsi) return chainsi; } } - else if (chainsi->first || chainsi->prev || chainsi->next) + else { - chainsi = unshare_strinfo (chainsi); - chainsi->first = 0; - chainsi->prev = 0; - chainsi->next = 0; + /* We shouldn't mix delayed and non-delayed lengths. */ + gcc_assert (chainsi->length); + if (chainsi->first || chainsi->prev || chainsi->next) + { + chainsi = unshare_strinfo (chainsi); + chainsi->first = 0; + chainsi->prev = 0; + chainsi->next = 0; + } } } idx = new_stridx (ptr); @@ -820,18 +845,13 @@ adjust_related_strinfos (location_t loc, strinfo *origsi, tree adj) tree tem; si = unshare_strinfo (si); - if (si->length) - { - tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj); - si->length = fold_build2_loc (loc, PLUS_EXPR, - TREE_TYPE (si->length), si->length, - tem); - } - else if (si->stmt != NULL) - /* Delayed length computation is unaffected. */ - ; - else - gcc_unreachable (); + /* We shouldn't see delayed lengths here; the caller must have + calculated the old length in order to calculate the + adjustment. */ + gcc_assert (si->length); + tem = fold_convert_loc (loc, TREE_TYPE (si->length), adj); + si->length = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (si->length), + si->length, tem); si->endptr = NULL_TREE; si->dont_invalidate = true; -- 2.30.2