Re: [PATCH v3] tree-optimization/95821 - Convert strlen + strchr to memchr

[Jakub Jelinek <jakub@redhat.com>]

On Tue, Jun 21, 2022 at 11:12:15AM -0700, Noah Goldstein wrote:
> This patch allows for strchr(x, c) to the replace with memchr(x, c,
> strlen(x) + 1) if strlen(x) has already been computed earlier in the
> tree.
> 
> Handles PR95821: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95821
> 
> Since memchr doesn't need to re-find the null terminator it is faster
> than strchr.
> 
> bootstrapped and tested on x86_64-linux.
> 
> 	PR tree-optimization/95821
> 
> gcc/
> 
> 	* tree-ssa-strlen.cc (strlen_pass::handle_builtin_strchr): Emit
> 	memchr instead of strchr if strlen already computed.
> 
> gcc/testsuite/
> 
> 	* c-c++-common/pr95821-1.c: New test.
> 	* c-c++-common/pr95821-2.c: New test.
> 	* c-c++-common/pr95821-3.c: New test.
> 	* c-c++-common/pr95821-4.c: New test.
> 	* c-c++-common/pr95821-5.c: New test.
> 	* c-c++-common/pr95821-6.c: New test.
> 	* c-c++-common/pr95821-7.c: New test.
> 	* c-c++-common/pr95821-8.c: New test.

Sorry for the delay.

> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr95821-1.c
> @@ -0,0 +1,15 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2" } */
> +/* { dg-final { scan-assembler "memchr" } } */

Please don't scan assembler, whether memchr will expand
to a call or be expanded inline etc. is not known.
Better use "-O2 -fdump-tree-optimize" in dg-options
and scan the optimized dump for "memchr \\\(".
Ditto for other tests.

> @@ -2452,32 +2459,96 @@ strlen_pass::handle_builtin_strchr ()
>  	      fprintf (dump_file, "Optimizing: ");
>  	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
>  	    }
> -	  if (si != NULL && si->endptr != NULL_TREE)
> +	  /* Three potential optimizations assume t=strlen (s) has already been
> +	     computed:
> +	        1. strchr (s, chr) where chr is known to be zero -> t

-> s + t
rather than
-> t
actually.

> +	        2. strchr (s, chr) where chr is known not to be zero ->
> +	           memchr (s, chr, t)
> +	        3. strchr (s, chr) where chr is not known to be zero or

nor instead of or?

> +	           non-zero -> memchr (s, chr, t + 1).  */
> +	  if (!is_strchr_zerop)
>  	    {
> -	      rhs = unshare_expr (si->endptr);
> -	      if (!useless_type_conversion_p (TREE_TYPE (lhs),
> -					      TREE_TYPE (rhs)))
> -		rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
> +	      /* If its not strchr (s, zerop) then try and convert to
> +	         memchr since strlen has already been computed.  */
> +	      tree fn = builtin_decl_explicit (BUILT_IN_MEMCHR);
> +
> +	      /* Only need to check length strlen (s) + 1 if chr may be zero.
> +	         Otherwise the last chr (which is known to be zero) can never
> +	         be a match.  */
> +	      bool chr_nonzero = false;
> +	      if (TREE_CODE (chr) == INTEGER_CST
> +		  && integer_nonzerop (fold_convert (char_type_node, chr)))
> +		chr_nonzero = true;
> +	      else if (TREE_CODE (chr) == SSA_NAME
> +		       && CHAR_TYPE_SIZE < INT_TYPE_SIZE)
> +		{
> +		  value_range r;
> +		  /* Try to determine using ranges if (char) chr must
> +		     be always 0.  That is true e.g. if all the subranges

must be always non-zero ?

> +		     have the INT_TYPE_SIZE - CHAR_TYPE_SIZE bits
> +		     the same on lower and upper bounds.  */

That is actually not enough, see below.

> +		  if (get_range_query (cfun)->range_of_expr (r, chr, stmt)
> +		      && r.kind () == VR_RANGE)
> +		    {
> +		      wide_int mask
> +			  = wi::mask (CHAR_TYPE_SIZE, true, INT_TYPE_SIZE);

Wrong indentation, = should be 2 columns left of wide_int.

> +		      for (unsigned i = 0; i < r.num_pairs (); ++i)
> +			if ((r.lower_bound (i) & mask)
> +			    != (r.upper_bound (i) & mask))
> +			  {
> +			    chr_nonzero = false;
> +			    break;
> +			  }

This else if actually can't do what it indends to, because
chr_nonzero is initialized to false at the start and in the loop you
also just set it to false, so it is always false.
You need to add chr_nonzero = true; before the for loop above.
With that, all the above test proves is that there is no range like
[15, 257] where it would include 256 in the middle of the range or
at the end.  But the above doesn't clear chr_nonzero on ranges like
[0, 32] or [256, 511] where (char) chr can still be zero.
So, the test should be:
			if ((r.lower_bound (i) & mask)
			    != (r.upper_bound (i) & mask)
			    || (r.lower_bound (i) & ~mask) == 0)
or so, that will rule out also the above ranges and if one just has ranges
like:
[1, 32] U [48, 56] U [257, 511]
all is fine, (char) chr is non-zero.

But this also shows that the testsuite coverage is insufficient because
nothing caught this.
I don't see almost any tests where the second argument to strchr would be
constant (ideally check for all of 0, ~0 & ~(unsigned char) ~0, ' ',
(~0 & ~(unsigned char) ~0) + ' ') - I see you have one test with
if (c != 0x100) return else strchr which effectively is strchr (, 0x100)
and one if (c != 0) return else strchr which has c range of ~[0, 0] with
which you can't do much (just can verify that we don't treat that as
(char) c can't be zero).  Beyond the tests with constant strchr arguments
(and I think you want to check in each case if there is
"= slen\[a-zA-Z.0-9_]* \\\+ 1;"
or not (and how many times if you e.g. stick more tests into one source
file, ideally all where you want the + 1 and in another one all that should
not have it)) it would be nice to have at least some tests where you
test the above problematic cases, say something like:
  if (c < 256)
    {
      if (c < 1 || c > 64)
	return ...;
    }
  else
    {
      if (c < 257 || c > 511)
	return ...;
    }
...
  strchr (..., c);
c above should be (needs to be verified in the debugger) [1, 64] U [257, 511]
and so chr_nonzero.  Similarly construct cases like [1, 32] U [48, 56] U [257, 511]
(chr_nonzero) or [0, 32] U [256, 511] (unknown whether c is zero or
non-zero) or [15, 257] (unknown too).

	Jakub