From 862088aa6349851465388eb0c691a79325c5eb7a Mon Sep 17 00:00:00 2001 From: Richard Sandiford Date: Sun, 2 Jul 2017 08:43:11 +0000 Subject: 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/tree-ssa-strlen.c | 122 +++++++++++++++++++++++++++++--------------------- 1 file changed, 71 insertions(+), 51 deletions(-) (limited to 'gcc/tree-ssa-strlen.c') diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c index e4f18db..f46e64d 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; -- cgit v1.1