constrain strcat destination offset (PR 83642)

The ICE in the test case submitted in PR tree-optimization/83640
is triggered by the tree-ssa-strlen pass transforming calls to
strcat to strcpy with an offset pointing to the terminating NUL
of the destination string, and allowing the upper bound of the
offset's range to exceed PTRDIFF_MAX by the length of
the appended constant string.  Although the ICE itself is due
to an unsafe assumption in the -Wrestrict checker, the excessive
upper bound in the strcat case suggests an optimization opportunity
that's missing from the tree-ssa-strlen pass: namely, to reduce
the offset's upper bound by the length of the appended string.
The attached patch adds this minor optimization.

Martin

Martin Sebor <msebor@gmail.com> writes:
> The ICE in the test case submitted in PR tree-optimization/83640
> is triggered by the tree-ssa-strlen pass transforming calls to
> strcat to strcpy with an offset pointing to the terminating NUL
> of the destination string, and allowing the upper bound of the
> offset's range to exceed PTRDIFF_MAX by the length of
> the appended constant string.  Although the ICE itself is due
> to an unsafe assumption in the -Wrestrict checker, the excessive
> upper bound in the strcat case suggests an optimization opportunity
> that's missing from the tree-ssa-strlen pass: namely, to reduce
> the offset's upper bound by the length of the appended string.
> The attached patch adds this minor optimization.
>
> Martin
>
> PR tree-optimization/83642 - excessive strlen range after a strcat of non-empty string
>
> gcc/ChangeLog:
>
> 	PR tree-optimization/83642
> 	* tree-ssa-strlen.c (handle_builtin_strcat): Set offset range.
>
> gcc/testsuite/ChangeLog:
>
> 	PR tree-optimization/83642
> 	* gcc.dg/strlenopt-39.c: New test.
>
> diff --git a/gcc/testsuite/gcc.dg/strlenopt-39.c b/gcc/testsuite/gcc.dg/strlenopt-39.c
> new file mode 100644
> index 0000000..b070b6b
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/strlenopt-39.c
> @@ -0,0 +1,84 @@
> +/* PR tree-optimization/83642] excessive strlen range after a strcat
> +   of non-empty string
> +   { dg-do compile }
> +   { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +void test_strcat_0_strlen_range (char *dst, char *src)
> +{
> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
> +
> +  __builtin_strcat (dst, "");
> +  __builtin_strcat (dst, src);
> +
> +  if (n >= __PTRDIFF_MAX__)
> +    __builtin_abort ();
> +}
> +
> +void test_strcat_1_strlen_range (char *dst, char *src)
> +{
> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
> +
> +  __builtin_strcat (dst, "1");
> +  __builtin_strcat (dst, src);
> +
> +  if (n >= __PTRDIFF_MAX__ - 1)
> +    __builtin_abort ();
> +}
> +
> +void test_strcat_2_strlen_range (char *dst, char *src)
> +{
> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
> +
> +  __builtin_strcat (dst, "12");
> +  __builtin_strcat (dst, src);
> +
> +  if (n >= __PTRDIFF_MAX__ - 2)
> +    __builtin_abort ();
> +}
> +
> +void test_strcat_3_strlen_range (char *dst, char *src)
> +{
> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
> +  char a[] = "123";
> +
> +  __builtin_strcat (dst, a);
> +  __builtin_strcat (dst, src);
> +
> +  if (n >= __PTRDIFF_MAX__ - 3)
> +    __builtin_abort ();
> +}
> +
> +void test_stpcpy_7_strlen_range (char *dst, char *src)
> +{
> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
> +
> +  __builtin_stpcpy (dst + n, "1234567");
> +  __builtin_strcat (dst, src);
> +
> +  if (n >= __PTRDIFF_MAX__ - 7)
> +    __builtin_abort ();
> +}
> +
> +void test_strcpy_8_strlen_range (char *dst, char *src)
> +{
> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
> +
> +  __builtin_strcpy (dst + n, "12345678");
> +  __builtin_strcat (dst, src);
> +
> +  if (n >= __PTRDIFF_MAX__ - 8)
> +    __builtin_abort ();
> +}
> +
> +void test_memcpy_9_strlen_range (char *dst, char *src)
> +{
> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
> +
> +  __builtin_memcpy (dst + n, "123456789", 10);
> +  __builtin_strcat (dst, src);
> +
> +  if (n >= __PTRDIFF_MAX__ - 9)
> +    __builtin_abort ();
> +}
> +
> +/* { dg-final { scan-tree-dump-not "abort \\(\\)" "optimized" } } */
> diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
> index be6ab9f..9e42232 100644
> --- a/gcc/tree-ssa-strlen.c
> +++ b/gcc/tree-ssa-strlen.c
> @@ -2486,10 +2486,35 @@ handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
>    if (endptr)
>      dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
>    else
> -    dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
> -			   TREE_TYPE (dst), unshare_expr (dst),
> -			   fold_convert_loc (loc, sizetype,
> -					     unshare_expr (dstlen)));
> +    {
> +      if (TREE_CODE (dstlen) == PLUS_EXPR
> +	  && TREE_CODE (TREE_OPERAND (dstlen, 0)) == SSA_NAME
> +	  && TREE_CODE (TREE_OPERAND (dstlen, 1)) == INTEGER_CST)
> +	{
> +	  /* For a call to strcat (DST, SRC) where DST = D + OFFSET and
> +	     where OFFSET = VAROFF + CSTOFF, adjust the upper bound of
> +	     VAROFF's range by the constant CSTOFF so that the result
> +	     is still guaranteed to be less than PTRDIFF_MAX, the size
> +	     of the longest possible string.  */
> +	  tree varoff = TREE_OPERAND (dstlen, 0);
> +	  wide_int minoff, maxoff;
> +	  value_range_type rng = get_range_info (varoff, &minoff, &maxoff);
> +
> +	  if (rng == VR_RANGE)
> +	    {
> +	      tree cstoff = TREE_OPERAND (dstlen, 1);
> +
> +	      maxoff -= wi::to_wide (cstoff);
> +	      set_range_info (varoff, rng, minoff, maxoff);
> +	    }
> +	}

I'm probably missing the point, but it seems unlikely that we can
unconditionally subtract CSTOFF from whatever the current recorded
maximum of VAROFF happens to be.  Shouldn't it be a maximum of
the current maxoff and PTRDIFF_MAX-cstoff instead?

Thanks,
Richard

Richard Sandiford <richard.sandiford@linaro.org> writes:
> Martin Sebor <msebor@gmail.com> writes:
>> The ICE in the test case submitted in PR tree-optimization/83640
>> is triggered by the tree-ssa-strlen pass transforming calls to
>> strcat to strcpy with an offset pointing to the terminating NUL
>> of the destination string, and allowing the upper bound of the
>> offset's range to exceed PTRDIFF_MAX by the length of
>> the appended constant string.  Although the ICE itself is due
>> to an unsafe assumption in the -Wrestrict checker, the excessive
>> upper bound in the strcat case suggests an optimization opportunity
>> that's missing from the tree-ssa-strlen pass: namely, to reduce
>> the offset's upper bound by the length of the appended string.
>> The attached patch adds this minor optimization.
>>
>> Martin
>>
>> PR tree-optimization/83642 - excessive strlen range after a strcat of non-empty string
>>
>> gcc/ChangeLog:
>>
>> 	PR tree-optimization/83642
>> 	* tree-ssa-strlen.c (handle_builtin_strcat): Set offset range.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 	PR tree-optimization/83642
>> 	* gcc.dg/strlenopt-39.c: New test.
>>
>> diff --git a/gcc/testsuite/gcc.dg/strlenopt-39.c b/gcc/testsuite/gcc.dg/strlenopt-39.c
>> new file mode 100644
>> index 0000000..b070b6b
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/strlenopt-39.c
>> @@ -0,0 +1,84 @@
>> +/* PR tree-optimization/83642] excessive strlen range after a strcat
>> +   of non-empty string
>> +   { dg-do compile }
>> +   { dg-options "-O2 -fdump-tree-optimized" } */
>> +
>> +void test_strcat_0_strlen_range (char *dst, char *src)
>> +{
>> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
>> +
>> +  __builtin_strcat (dst, "");
>> +  __builtin_strcat (dst, src);
>> +
>> +  if (n >= __PTRDIFF_MAX__)
>> +    __builtin_abort ();
>> +}
>> +
>> +void test_strcat_1_strlen_range (char *dst, char *src)
>> +{
>> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
>> +
>> +  __builtin_strcat (dst, "1");
>> +  __builtin_strcat (dst, src);
>> +
>> +  if (n >= __PTRDIFF_MAX__ - 1)
>> +    __builtin_abort ();
>> +}
>> +
>> +void test_strcat_2_strlen_range (char *dst, char *src)
>> +{
>> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
>> +
>> +  __builtin_strcat (dst, "12");
>> +  __builtin_strcat (dst, src);
>> +
>> +  if (n >= __PTRDIFF_MAX__ - 2)
>> +    __builtin_abort ();
>> +}
>> +
>> +void test_strcat_3_strlen_range (char *dst, char *src)
>> +{
>> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
>> +  char a[] = "123";
>> +
>> +  __builtin_strcat (dst, a);
>> +  __builtin_strcat (dst, src);
>> +
>> +  if (n >= __PTRDIFF_MAX__ - 3)
>> +    __builtin_abort ();
>> +}
>> +
>> +void test_stpcpy_7_strlen_range (char *dst, char *src)
>> +{
>> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
>> +
>> +  __builtin_stpcpy (dst + n, "1234567");
>> +  __builtin_strcat (dst, src);
>> +
>> +  if (n >= __PTRDIFF_MAX__ - 7)
>> +    __builtin_abort ();
>> +}
>> +
>> +void test_strcpy_8_strlen_range (char *dst, char *src)
>> +{
>> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
>> +
>> +  __builtin_strcpy (dst + n, "12345678");
>> +  __builtin_strcat (dst, src);
>> +
>> +  if (n >= __PTRDIFF_MAX__ - 8)
>> +    __builtin_abort ();
>> +}
>> +
>> +void test_memcpy_9_strlen_range (char *dst, char *src)
>> +{
>> +  __SIZE_TYPE__ n = __builtin_strlen (dst);
>> +
>> +  __builtin_memcpy (dst + n, "123456789", 10);
>> +  __builtin_strcat (dst, src);
>> +
>> +  if (n >= __PTRDIFF_MAX__ - 9)
>> +    __builtin_abort ();
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-not "abort \\(\\)" "optimized" } } */
>> diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c
>> index be6ab9f..9e42232 100644
>> --- a/gcc/tree-ssa-strlen.c
>> +++ b/gcc/tree-ssa-strlen.c
>> @@ -2486,10 +2486,35 @@ handle_builtin_strcat (enum built_in_function bcode, gimple_stmt_iterator *gsi)
>>    if (endptr)
>>      dst = fold_convert_loc (loc, TREE_TYPE (dst), unshare_expr (endptr));
>>    else
>> -    dst = fold_build2_loc (loc, POINTER_PLUS_EXPR,
>> -			   TREE_TYPE (dst), unshare_expr (dst),
>> -			   fold_convert_loc (loc, sizetype,
>> -					     unshare_expr (dstlen)));
>> +    {
>> +      if (TREE_CODE (dstlen) == PLUS_EXPR
>> +	  && TREE_CODE (TREE_OPERAND (dstlen, 0)) == SSA_NAME
>> +	  && TREE_CODE (TREE_OPERAND (dstlen, 1)) == INTEGER_CST)
>> +	{
>> +	  /* For a call to strcat (DST, SRC) where DST = D + OFFSET and
>> +	     where OFFSET = VAROFF + CSTOFF, adjust the upper bound of
>> +	     VAROFF's range by the constant CSTOFF so that the result
>> +	     is still guaranteed to be less than PTRDIFF_MAX, the size
>> +	     of the longest possible string.  */
>> +	  tree varoff = TREE_OPERAND (dstlen, 0);
>> +	  wide_int minoff, maxoff;
>> +	  value_range_type rng = get_range_info (varoff, &minoff, &maxoff);
>> +
>> +	  if (rng == VR_RANGE)
>> +	    {
>> +	      tree cstoff = TREE_OPERAND (dstlen, 1);
>> +
>> +	      maxoff -= wi::to_wide (cstoff);
>> +	      set_range_info (varoff, rng, minoff, maxoff);
>> +	    }
>> +	}
>
> I'm probably missing the point, but it seems unlikely that we can
> unconditionally subtract CSTOFF from whatever the current recorded
> maximum of VAROFF happens to be.  Shouldn't it be a maximum of
> the current maxoff and PTRDIFF_MAX-cstoff instead?

er, of course I meant minimum :-)

On Mon, Jan 01, 2018 at 03:31:46PM -0700, Martin Sebor wrote:
> The ICE in the test case submitted in PR tree-optimization/83640
> is triggered by the tree-ssa-strlen pass transforming calls to
> strcat to strcpy with an offset pointing to the terminating NUL
> of the destination string, and allowing the upper bound of the
> offset's range to exceed PTRDIFF_MAX by the length of
> the appended constant string.  Although the ICE itself is due
> to an unsafe assumption in the -Wrestrict checker, the excessive
> upper bound in the strcat case suggests an optimization opportunity
> that's missing from the tree-ssa-strlen pass: namely, to reduce
> the offset's upper bound by the length of the appended string.
> The attached patch adds this minor optimization.

This is wrong for many reasons.

The recorded range info is a property of the SSA_NAME, can't be dependent on
where it is used, you are changing it globally.  You don't really know how
the minoff and maxoff of the previous range were computed, so blindly
decreasing it is wrong, you can decrease it that way multiple times, or from
bounds that were computed some other way.  And you aren't checking what
cstoff is, it could be excessively large, or could make the range invalid
(larger minoff than maxoff), etc.

Just 4 random examples that will be miscompiled by your patch:

void
foo (char *dst, char *src, int x)
{
  __SIZE_TYPE__ n = __builtin_strlen (dst);
  if (x)
    {
      __builtin_strcat (dst, "1");
      __builtin_strcat (dst, src);
    }
  else
    {
      __builtin_strcat (dst, "234567890");
      __builtin_strcat (dst, src);
    }
  if (n >= __PTRDIFF_MAX__ - 4)
    __builtin_abort ();
}

void
bar (char *dst, char *src, int x)
{
  __SIZE_TYPE__ n = __builtin_strlen (dst);
  if (n > 145)
    __builtin_unreachable ();
  if (x)
    {
      __builtin_strcat (dst, "1");
      __builtin_strcat (dst, src);
    }
  else
    {
      __builtin_strcat (dst, "234567890");
      __builtin_strcat (dst, src);
    }
  if (n >= 140)
    __builtin_abort ();
}

void
baz (char *dst, char *src)
{
  __SIZE_TYPE__ n = __builtin_strlen (dst);
  if (n > __PTRDIFF_MAX__ - 10)
    __builtin_abort ();
  might_not_return ();
  __builtin_strcat (dst, "234abcdefghijklmnopqrstuv");
  __builtin_strcat (dst, src);
}

void
boo (char *dst, char *src, int x)
{
  __SIZE_TYPE__ n = __builtin_strlen (dst);
  if (n < __PTRDIFF_MAX__ - 10)
    {
      __builtin_strcat (dst, "234abcdefghijklmnopqrstuv");
      __builtin_strcat (dst, src);
    }
}

In foo, while the range of n comes from the restriction that strlen should
return < (size_t) PTRDIFF_MAX value, you are decreasing the maxoff not once,
but twice.  In bar, additionally the range of n comes from the builtin
unreachable assertion, the user says that strlen return value will be 0 to
145 inclusive, trying to decrease it in any way doesn't make sense.
In baz, if might_not_return returns, then it is true that n will need to be
smaller than __PTRDIFF_MAX__ - 10, but if might_not_return doesn't return,
n might be in a valid program __PTRDIFF_MAX__ - 1.
And finally in boo, the strcat calls are conditional you are changing it
again globally.

	Jakub

On 01/02/2018 02:57 AM, Jakub Jelinek wrote:
> On Mon, Jan 01, 2018 at 03:31:46PM -0700, Martin Sebor wrote:
>> The ICE in the test case submitted in PR tree-optimization/83640
>> is triggered by the tree-ssa-strlen pass transforming calls to
>> strcat to strcpy with an offset pointing to the terminating NUL
>> of the destination string, and allowing the upper bound of the
>> offset's range to exceed PTRDIFF_MAX by the length of
>> the appended constant string.  Although the ICE itself is due
>> to an unsafe assumption in the -Wrestrict checker, the excessive
>> upper bound in the strcat case suggests an optimization opportunity
>> that's missing from the tree-ssa-strlen pass: namely, to reduce
>> the offset's upper bound by the length of the appended string.
>> The attached patch adds this minor optimization.
> 
> This is wrong for many reasons.
> 
> The recorded range info is a property of the SSA_NAME, can't be dependent on
> where it is used, you are changing it globally. 
Right.  And that's precisely the way to think about it -- does the range
hold everywhere the SSA_NAME is or might be used.  If so, then the range
can be recorded via set_range_info.

Otherwise the range is context sensitive.  The best way to handle
context sensitive ranges is discover them within the EVRP analyzer which
has mechanisms to record temporary ranges and reset them to their prior
values when leaving scope.

tree-ssa-strlen is already a dominator walker, so embedding an EVRP
range analyzer in there ought to be trivial.

Jeff

On 01/02/2018 09:44 AM, Jeff Law wrote:
> On 01/02/2018 02:57 AM, Jakub Jelinek wrote:
>> On Mon, Jan 01, 2018 at 03:31:46PM -0700, Martin Sebor wrote:
>>> The ICE in the test case submitted in PR tree-optimization/83640
>>> is triggered by the tree-ssa-strlen pass transforming calls to
>>> strcat to strcpy with an offset pointing to the terminating NUL
>>> of the destination string, and allowing the upper bound of the
>>> offset's range to exceed PTRDIFF_MAX by the length of
>>> the appended constant string.  Although the ICE itself is due
>>> to an unsafe assumption in the -Wrestrict checker, the excessive
>>> upper bound in the strcat case suggests an optimization opportunity
>>> that's missing from the tree-ssa-strlen pass: namely, to reduce
>>> the offset's upper bound by the length of the appended string.
>>> The attached patch adds this minor optimization.
>>
>> This is wrong for many reasons.
>>
>> The recorded range info is a property of the SSA_NAME, can't be dependent on
>> where it is used, you are changing it globally.
> Right.  And that's precisely the way to think about it -- does the range
> hold everywhere the SSA_NAME is or might be used.  If so, then the range
> can be recorded via set_range_info.
>
> Otherwise the range is context sensitive.  The best way to handle
> context sensitive ranges is discover them within the EVRP analyzer which
> has mechanisms to record temporary ranges and reset them to their prior
> values when leaving scope.

I assumed the call to unshare_expr would somehow avoid this sharing
problem but it looks like I misunderstood the purpose of the function
and didn't do enough testing to find out.

> tree-ssa-strlen is already a dominator walker, so embedding an EVRP
> range analyzer in there ought to be trivial.

This might be a good opportunity for me to get some experience with
the analyzer.  Let me look into it.

FWIW, the strlen pass is only good for tracking constant string
lengths but not for ranges.  It would be a nice enhancement to
have it keep track of ranges of lengths as well (or instead).
That way things like the following test case could also be
optimized:

   void f (char *d, int i)
   {
     strcpy (d, i < 0 ? "1" : "123");

     if (strlen (d) < 1 || strlen (d) > 3)
       abort ();
   }

Martin

On 01/02/2018 10:27 AM, Martin Sebor wrote:
> On 01/02/2018 09:44 AM, Jeff Law wrote:
>> On 01/02/2018 02:57 AM, Jakub Jelinek wrote:
>>> On Mon, Jan 01, 2018 at 03:31:46PM -0700, Martin Sebor wrote:
>>>> The ICE in the test case submitted in PR tree-optimization/83640
>>>> is triggered by the tree-ssa-strlen pass transforming calls to
>>>> strcat to strcpy with an offset pointing to the terminating NUL
>>>> of the destination string, and allowing the upper bound of the
>>>> offset's range to exceed PTRDIFF_MAX by the length of
>>>> the appended constant string.  Although the ICE itself is due
>>>> to an unsafe assumption in the -Wrestrict checker, the excessive
>>>> upper bound in the strcat case suggests an optimization opportunity
>>>> that's missing from the tree-ssa-strlen pass: namely, to reduce
>>>> the offset's upper bound by the length of the appended string.
>>>> The attached patch adds this minor optimization.
>>>
>>> This is wrong for many reasons.
>>>
>>> The recorded range info is a property of the SSA_NAME, can't be
>>> dependent on
>>> where it is used, you are changing it globally.
>> Right.  And that's precisely the way to think about it -- does the range
>> hold everywhere the SSA_NAME is or might be used.  If so, then the range
>> can be recorded via set_range_info.
>>
>> Otherwise the range is context sensitive.  The best way to handle
>> context sensitive ranges is discover them within the EVRP analyzer which
>> has mechanisms to record temporary ranges and reset them to their prior
>> values when leaving scope.
> 
> I assumed the call to unshare_expr would somehow avoid this sharing
> problem but it looks like I misunderstood the purpose of the function
> and didn't do enough testing to find out.
Yea.  unshare_expr is more concerned with unsharing within the tree
structures rather than creating a unique SSA_NAME within a context.
unshare_rtl is similar to unshare_expr, except it works on RTL bits.

> 
>> tree-ssa-strlen is already a dominator walker, so embedding an EVRP
>> range analyzer in there ought to be trivial.
> 
> This might be a good opportunity for me to get some experience with
> the analyzer.  Let me look into it.
Don't hesitate to pass along questions.  Happy to help.  I think I was
supposed to pass you some skeleton code in this space, but haven't
gotten around to it.

jeff