Re: [2/2] PR 80769: Incorrect strlen optimisation

[Richard Sandiford <richard dot sandiford at linaro dot org>]

Ping*3

Richard Sandiford <richard.sandiford@linaro.org> writes:
> Ping*2
>
> Richard Sandiford <richard.sandiford@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.sandiford@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" } } */