Ping*2
Richard Sandiford <richard.sandif...@linaro.org> writes:
> 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.
>
> I thought about three fixes:
>
> (1) Make adjust_related_strinfos drop strinfos with a delayed length.
>
> (2) Make adjust_related_strinfos compute the length itself
> (via get_string_length).
>
> (3) Make get_string_length update all related strinfos. We can then
> maintain the invariant that all lengths in a chain are delayed or
> none are.
>
> (3) seemed like the best. get_string_length has already made the
> invasive step of changing the code and computing the length for one
> strinfo. Updating the related strinfos is just a couple of fold_builds,
> of the kind that the pass already does in several places.
>
> The point is that the code above only triggers if one of the delayed
> lengths has been computed. That makes (1) unnecessarily pessimistic.
> It also wasn't obvious (to me) from first glance, so (2) might look
> more intrusive than it is. I think it becomes easier to reason about
> if we do (3) and can assume that all lengths are delayed or none are.
> It also makes the min-length/maybe-not-terminated patch easier.
>
> [ I can go into more detail about why this should be enough to
> maintain the invariant, and why the asserts should be valid,
> but the message is already pretty long. ]
>
> Tested on aarch64-linux-gnu and x86_64-linux-gnu. OK to install?
>
> Thanks,
> Richard
>
>
> 2017-05-16 Richard Sandiford <richard.sandif...@linaro.org>
>
> 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.
>
> Index: gcc/tree-ssa-strlen.c
> ===================================================================
> --- gcc/tree-ssa-strlen.c 2017-05-16 08:00:03.808133862 +0100
> +++ gcc/tree-ssa-strlen.c 2017-05-16 08:20:51.408572143 +0100
> @@ -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 *c
> {
> 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 *c
> 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,
> 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;
> Index: gcc/testsuite/gcc.dg/strlenopt-31.c
> ===================================================================
> --- /dev/null 2017-05-11 19:11:40.989165404 +0100
> +++ gcc/testsuite/gcc.dg/strlenopt-31.c 2017-05-16 08:20:26.780371709
> +0100
> @@ -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;
> +}
> Index: gcc/testsuite/gcc.dg/strlenopt-31g.c
> ===================================================================
> --- /dev/null 2017-05-11 19:11:40.989165404 +0100
> +++ gcc/testsuite/gcc.dg/strlenopt-31g.c 2017-05-16 08:20:26.780371709
> +0100
> @@ -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" } } */
