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

[Jakub Jelinek <jakub@redhat.com>]

On Mon, Jun 20, 2022 at 02:42:20PM -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

This should be indented by a single tab, not two.
> 
> 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.
> --- a/gcc/tree-ssa-strlen.cc
> +++ b/gcc/tree-ssa-strlen.cc
> @@ -2405,9 +2405,12 @@ strlen_pass::handle_builtin_strlen ()
>      }
>  }
>  
> -/* Handle a strchr call.  If strlen of the first argument is known, replace
> -   the strchr (x, 0) call with the endptr or x + strlen, otherwise remember
> -   that lhs of the call is endptr and strlen of the argument is endptr - x.  */
> +/* Handle a strchr call.  If strlen of the first argument is known,
> +   replace the strchr (x, 0) call with the endptr or x + strlen,
> +   otherwise remember that lhs of the call is endptr and strlen of the
> +   argument is endptr - x.  If strlen of x is not know but has been
> +   computed earlier in the tree then replace strchr(x, c) to

Still missing space before ( above.

> +   memchr (x, c, strlen + 1).  */
>  
>  void
>  strlen_pass::handle_builtin_strchr ()
> @@ -2418,8 +2421,12 @@ strlen_pass::handle_builtin_strchr ()
>    if (lhs == NULL_TREE)
>      return;
>  
> -  if (!integer_zerop (gimple_call_arg (stmt, 1)))
> -    return;
> +  tree chr = gimple_call_arg (stmt, 1);
> +  /* strchr only uses the lower char of input so to check if its
> +     strchr (s, zerop) only take into account the lower char.  */
> +  bool is_strchr_zerop
> +      = (TREE_CODE (chr) == INTEGER_CST
> +	 && integer_zerop (fold_convert (char_type_node, chr)));

The indentation rule is that = should be 2 columns to the right from bool,
so

  bool is_strchr_zerop
    = (TREE_CODE (chr) == INTEGER_CST
       && integer_zerop (fold_convert (char_type_node, chr)));

> +	      /* If its not strchr (s, zerop) then try and convert to
> +		     memchr since strlen has already been computed.  */

This comment still has the second line weirdly indented.

> +	      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.  NB: We don't need to test if chr is a non-zero
> +             integer const with zero char bits because that is taken into
> +             account with is_strchr_zerop.  */
> +	      if (!tree_expr_nonzero_p (chr))

The above is unsafe though.  tree_expr_nonzero_p (chr) will return true
if say VRP can prove it is not zero, but because of the implicit
(char) chr cast done by the function we need something different.
Say if VRP determines that chr is in [1, INT_MAX] or even just [255, 257]
it doesn't mean (char) chr won't be 0.
So, as I've tried to explain in the previous mail, it can be done e.g. with
	      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
		     have the INT_TYPE_SIZE - CHAR_TYPE_SIZE bits
		     the same on lower and upper bounds.  */
		  if (get_range_query (cfun)->range_of_expr (r, chr, stmt)
		      && r.kind () == VR_RANGE)
		    {
		      chr_nonzero = true;
		      wide_int mask = wi::mask (CHAR_TYPE_SIZE, true,
						INT_TYPE_SIZE);
		      for (int i = 0; i < r.num_pairs (); ++i)
			if ((r.lower_bound (i) & mask)
			    != (r.upper_bound (i) & mask))
			  {
			    chr_nonzero = false;
			    break;
			  }
		    }
		}
	      if (!chr_nonzero)

	Jakub