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

[Noah Goldstein <goldstein.w.n@gmail.com>]

On Tue, Jun 21, 2022 at 5:01 AM Jakub Jelinek <jakub@redhat.com> wrote:
>
> 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.

Fixed in V3
> >
> > 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.

Sorry, fixed that in V3.
>
> > +   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
>

Fixed in V3.
>   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.

Sorry, have emacs with 4-space tabs so things that look right arent
as they seem :/

Fixed in V3 I believe.
>
> > +           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

Added your code in V3. Thanks for the help.
>               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
>