Make tree-ssa-strlen.c handle partial unterminated strings

Richard Sandiford <richard.sandiford@linaro.org> writes:
> Jakub Jelinek <jakub@redhat.com> writes:
>> Hi!
>>
>> Note the intent of the pass is to handle the most common cases, it is fine
>> if some cases that aren't common aren't handled, it is all about the extra
>> complexity vs. how much it helps on real-world code.
>
> OK.
>
>> On Sun, May 07, 2017 at 10:10:48AM +0100, Richard Sandiford wrote:
>>> I've got most of the way through a version that uses min_length instead.
>>> But one thing that the terminated flag allows that a constant min_length
>>> doesn't is:
>>> 
>>>   size_t
>>>   f1 (char *a1)
>>>   {
>>>     size_t x = strlen (a1);
>>>     char *a3 = a1 + x;
>>>     a3[0] = '1';  // a1 length x + 1, unterminated  (min length x + 1)
>>>     a3[1] = '2';  // a1 length x + 2, unterminated  (min length x + 2)
>>>     a3[2] = '3';  // a1 length x + 3, unterminated  (min length x + 3)
>>>     a3[3] = 0;    // a1 length x + 3, terminated
>>>     return strlen (a1);
>>>   }
>>> 
>>> For the a3[3] = 0, we know a3's min_length is 3 and so it's obvious
>>> that we can convert its min_length to a length.  But even if we allow
>>> a1's min_length to be nonconstant, it seems a bit risky to assume that
>>> we can convert its min_length to a length as well.  It would only work
>>> if the min_lengths in related strinfos are kept in sync, whereas it
>>> ought to be safe to say that the minimum length of something is 0.
>>
>> And we have code for that.  If verify_related_strinfos returns non-NULL,
>> we can adjust all the related strinfos that need adjusting.
>> See e.g. zero_length_string on how it uses that.  It is just that we should
>> decide what is the acceptable complexity of the length/min_length
>> expressions (whether INTEGER_CST or SSA_NAME is enough, then the above
>> would not work, but is that really that important), or if we e.g. allow
>> SSA_NAME + INTEGER_CST in addition to that, or sum of 2 SSA_NAMEs, etc.).
>> I don't see how terminated vs. unterminated (which is misnamed anyway, it
>> means that it isn't known to be terminated, it might be terminated or not)
>> would help with that.
>
> The example above works with the flag because we already allow
> SSA_NAME + INTEGER_CST for the length field, thanks to:
>
>       tree adj = NULL_TREE;
>       if (oldlen == NULL_TREE)
> 	;
>       else if (integer_zerop (oldlen))
> 	adj = srclen;
>       else if (TREE_CODE (oldlen) == INTEGER_CST
> 	       || TREE_CODE (srclen) == INTEGER_CST)
> 	adj = fold_build2_loc (loc, MINUS_EXPR,
> 			       TREE_TYPE (srclen), srclen,
> 			       fold_convert_loc (loc, TREE_TYPE (srclen),
> 						 oldlen));
>       if (adj != NULL_TREE)
> 	adjust_related_strinfos (loc, dsi, adj);
>
> etc.  So with a constant min_length we lose out (compared to the flag)
> by making min_length more restrictive.
>
> Like you say later, min_length is the number of characters that are
> known to be nonzero, and length is the number of characters that are
> known to be nonzero and followed by a zero, so even if we do relax the
> rules for min_length to match length, I think in almost all useful cases
> the length will be equal to the min_length or will be null (i.e. it'll
> act almost like a de facto flag).

How about the patch below?  It renames "length" to "nonzero_chars"
and adds a "full_string_p" flag to indicate that the nonzero characters
are known to be followed by a zero.  It keeps the current decisions
about which kinds of length/nonzero_chars expression are valid and
worth tracking.  It also handles strings built up a character at
a time (unlike the original).

Tested on aarch64-linux-gnu and x86_64-linux-gnu.

Thanks,
Richard

2017-05-17  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	* tree-ssa-strlen.c (strinfo): Rename the length field to
	nonzero_chars.  Add a full_string_p field.
	(compare_nonzero_chars, zero_length_string_p): New functions.
	(get_addr_stridx): Add an offset_out parameter.
	Use compare_nonzero_chars.
	(get_stridx): Update accordingly.  Use compare_nonzero_chars.
	(new_strinfo): Update after above changes to strinfo.
	(set_endptr_and_length): Set full_string_p.
	(get_string_length): Update after above changes to strinfo.
	(unshare_strinfo): Update call to new_strinfo.
	(maybe_invalidate): Likewise.
	(get_stridx_plus_constant): Change off to unsigned HOST_WIDE_INT.
	Use compare_nonzero_chars and zero_string_p.  Treat nonzero_chars
	as a uhwi instead of an shwi.  Update after above changes to
	strinfo and new_strinfo.
	(zero_length_string): Assert that chainsi contains full strings.
	Use zero_length_string_p.  Update call to new_strinfo.
	(adjust_related_strinfos): Update after above changes to strinfo.
	Copy full_string_p from origsi.
	(adjust_last_stmt): Use zero_length_string_p.
	(handle_builtin_strlen): Update after above changes to strinfo and
	new_strinfo.  Install the lhs as the string length if the previous
	entry didn't describe a full string.
	(handle_builtin_strchr): Update after above changes to strinfo
	and new_strinfo.
	(handle_builtin_strcpy): Likewise.
	(handle_builtin_strcat): Likewise.
	(handle_builtin_malloc): Likewise.
	(handle_pointer_plus): Likewise.
	(handle_builtin_memcpy): Likewise.  Track nonzero characters
	that aren't necessarily followed by a nul terminator.
	(handle_char_store): Likewise.

gcc/testsuite/
	* gcc.dg/strlenopt-32.c: New testcase.
	* gcc.dg/strlenopt-33.c: Likewise.
	* gcc.dg/strlenopt-33g.c: Likewise.
	* gcc.dg/strlenopt-34.c: Likewise.
	* gcc.dg/strlenopt-35.c: Likewise.

Make tree-ssa-strlen.c handle partial unterminated strings

Commit Message

Comments

Patch