From: Noah Goldstein <goldstein.w.n@gmail.com>
To: Jakub Jelinek <jakub@redhat.com>
Cc: gcc-patches List <gcc-patches@gcc.gnu.org>,
"H.J. Lu" <hjl.tools@gmail.com>
Subject: Re: [PATCH v2] tree-optimization/95821 - Convert strlen + strchr to memchr
Date: Thu, 7 Jul 2022 09:26:22 -0700 [thread overview]
Message-ID: <CAFUsyfJ5_6GkUNExvmL+PRFBTCPLSMCQHt62AE1zQmP=Yy8L9g@mail.gmail.com> (raw)
In-Reply-To: <CAFUsyfJYLo0BCDa2tMq1tfaQ+psdZqrjwX4e4s=gDGVKBvBccg@mail.gmail.com>
On Tue, Jun 21, 2022 at 11:13 AM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> 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
> >
Ping 1
next prev parent reply other threads:[~2022-07-07 16:26 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-06-20 16:35 [PATCH v1] " Noah Goldstein
2022-06-20 17:29 ` Jakub Jelinek
2022-06-20 17:54 ` H.J. Lu
2022-06-20 18:48 ` Noah Goldstein
2022-06-20 19:04 ` Jakub Jelinek
2022-06-20 19:12 ` Noah Goldstein
2022-06-20 19:57 ` Jakub Jelinek
2022-06-20 20:59 ` Noah Goldstein
2022-06-20 21:42 ` [PATCH v2] " Noah Goldstein
2022-06-21 12:01 ` Jakub Jelinek
2022-06-21 18:13 ` Noah Goldstein
2022-07-07 16:26 ` Noah Goldstein [this message]
2022-06-21 18:12 ` [PATCH v3] " Noah Goldstein
2022-07-09 15:59 ` Jeff Law
2022-09-21 22:02 ` Noah Goldstein
2022-09-22 12:22 ` Jakub Jelinek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAFUsyfJ5_6GkUNExvmL+PRFBTCPLSMCQHt62AE1zQmP=Yy8L9g@mail.gmail.com' \
--to=goldstein.w.n@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hjl.tools@gmail.com \
--cc=jakub@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).