From: Richard Biener <richard.guenther@gmail.com>
To: "H.J. Lu" <hjl.tools@gmail.com>
Cc: GCC Patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH v3] Simplify memchr with small constant strings
Date: Thu, 14 Jul 2022 08:42:23 +0200 [thread overview]
Message-ID: <CAFiYyc3HFo03W4U0GLmNSYSLxi6rRTJ+EcuX-Beg+y-kN+1k_A@mail.gmail.com> (raw)
In-Reply-To: <20220713165014.36469-1-hjl.tools@gmail.com>
On Wed, Jul 13, 2022 at 6:50 PM H.J. Lu <hjl.tools@gmail.com> wrote:
>
> When memchr is applied on a constant string of no more than the bytes of
> a word, simplify memchr by checking each byte in the constant string.
>
> int f (int a)
> {
> return __builtin_memchr ("AE", a, 2) != 0;
> }
>
> is simplified to
>
> int f (int a)
> {
> return ((char) a == 'A' || (char) a == 'E') != 0;
> }
>
> gcc/
>
> PR tree-optimization/103798
> * tree-ssa-forwprop.cc: Include "tree-ssa-strlen.h".
> (simplify_builtin_call): Inline memchr with constant strings of
> no more than the bytes of a word.
> * tree-ssa-strlen.cc (use_in_zero_equality): Make it global.
> * tree-ssa-strlen.h (use_in_zero_equality): New.
>
> gcc/testsuite/
>
> PR tree-optimization/103798
> * c-c++-common/pr103798-1.c: New test.
> * c-c++-common/pr103798-2.c: Likewise.
> * c-c++-common/pr103798-3.c: Likewise.
> * c-c++-common/pr103798-4.c: Likewise.
> * c-c++-common/pr103798-5.c: Likewise.
> * c-c++-common/pr103798-6.c: Likewise.
> * c-c++-common/pr103798-7.c: Likewise.
> * c-c++-common/pr103798-8.c: Likewise.
> * c-c++-common/pr103798-9.c: Likewise.
> * c-c++-common/pr103798-10.c: Likewise.
> ---
> gcc/testsuite/c-c++-common/pr103798-1.c | 28 +++++++++
> gcc/testsuite/c-c++-common/pr103798-10.c | 10 ++++
> gcc/testsuite/c-c++-common/pr103798-2.c | 30 ++++++++++
> gcc/testsuite/c-c++-common/pr103798-3.c | 28 +++++++++
> gcc/testsuite/c-c++-common/pr103798-4.c | 28 +++++++++
> gcc/testsuite/c-c++-common/pr103798-5.c | 26 +++++++++
> gcc/testsuite/c-c++-common/pr103798-6.c | 27 +++++++++
> gcc/testsuite/c-c++-common/pr103798-7.c | 27 +++++++++
> gcc/testsuite/c-c++-common/pr103798-8.c | 27 +++++++++
> gcc/testsuite/c-c++-common/pr103798-9.c | 10 ++++
> gcc/tree-ssa-forwprop.cc | 73 ++++++++++++++++++++++++
> gcc/tree-ssa-strlen.cc | 4 +-
> gcc/tree-ssa-strlen.h | 2 +
> 13 files changed, 318 insertions(+), 2 deletions(-)
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-1.c
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-10.c
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-2.c
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-3.c
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-4.c
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-5.c
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-6.c
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-7.c
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-8.c
> create mode 100644 gcc/testsuite/c-c++-common/pr103798-9.c
>
> diff --git a/gcc/testsuite/c-c++-common/pr103798-1.c b/gcc/testsuite/c-c++-common/pr103798-1.c
> new file mode 100644
> index 00000000000..cd3edf569fc
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-1.c
> @@ -0,0 +1,28 @@
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-optimized -save-temps" } */
> +
> +__attribute__ ((weak))
> +int
> +f (char a)
> +{
> + return __builtin_memchr ("a", a, 1) == 0;
> +}
> +
> +__attribute__ ((weak))
> +int
> +g (char a)
> +{
> + return a != 'a';
> +}
> +
> +int
> +main ()
> +{
> + for (int i = 0; i < 255; i++)
> + if (f (i) != g (i))
> + __builtin_abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "memchr" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr103798-10.c b/gcc/testsuite/c-c++-common/pr103798-10.c
> new file mode 100644
> index 00000000000..4677e9539fa
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-10.c
> @@ -0,0 +1,10 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Os -fdump-tree-optimized -save-temps" } */
> +
> +int
> +f (char a)
> +{
> + return __builtin_memchr ("ac", a, 1) == 0;
> +}
> +
> +/* { dg-final { scan-assembler "memchr" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr103798-2.c b/gcc/testsuite/c-c++-common/pr103798-2.c
> new file mode 100644
> index 00000000000..e7e99c3679e
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-2.c
> @@ -0,0 +1,30 @@
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-optimized -save-temps" } */
> +
> +#include <string.h>
> +
> +__attribute__ ((weak))
> +int
> +f (int a)
> +{
> + return memchr ("aE", a, 2) != NULL;
> +}
> +
> +__attribute__ ((weak))
> +int
> +g (char a)
> +{
> + return a == 'a' || a == 'E';
> +}
> +
> +int
> +main ()
> +{
> + for (int i = 0; i < 255; i++)
> + if (f (i + 256) != g (i + 256))
> + __builtin_abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "memchr" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr103798-3.c b/gcc/testsuite/c-c++-common/pr103798-3.c
> new file mode 100644
> index 00000000000..ddcedc7e238
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-3.c
> @@ -0,0 +1,28 @@
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-optimized -save-temps" } */
> +
> +__attribute__ ((weak))
> +int
> +f (char a)
> +{
> + return __builtin_memchr ("aEgZ", a, 3) == 0;
> +}
> +
> +__attribute__ ((weak))
> +int
> +g (char a)
> +{
> + return a != 'a' && a != 'E' && a != 'g';
> +}
> +
> +int
> +main ()
> +{
> + for (int i = 0; i < 255; i++)
> + if (f (i) != g (i))
> + __builtin_abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "memchr" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr103798-4.c b/gcc/testsuite/c-c++-common/pr103798-4.c
> new file mode 100644
> index 00000000000..00e8302a833
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-4.c
> @@ -0,0 +1,28 @@
> +/* { dg-do run } */
> +/* { dg-options "-O2 -fdump-tree-optimized -save-temps" } */
> +
> +__attribute__ ((weak))
> +int
> +f (char a)
> +{
> + return __builtin_memchr ("aEgi", a, 4) != 0;
> +}
> +
> +__attribute__ ((weak))
> +int
> +g (char a)
> +{
> + return a == 'a' || a == 'E' || a == 'g' || a == 'i';
> +}
> +
> +int
> +main ()
> +{
> + for (int i = 0; i < 255; i++)
> + if (f (i) != g (i))
> + __builtin_abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "memchr" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr103798-5.c b/gcc/testsuite/c-c++-common/pr103798-5.c
> new file mode 100644
> index 00000000000..0d6487a13df
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-5.c
> @@ -0,0 +1,26 @@
> +/* { dg-do run { target int128 } } */
> +/* { dg-options "-O2 -fdump-tree-optimized -save-temps" } */
> +
> +__attribute__ ((weak))
> +int f(char a)
> +{
> + return __builtin_memchr ("aEgiH", a, 5) == 0;
> +}
> +
> +__attribute__ ((weak))
> +int g(char a)
> +{
> + return a != 'a' && a != 'E' && a != 'g' && a != 'i' && a != 'H';
> +}
> +
> +int
> +main ()
> +{
> + for (int i = 0; i < 255; i++)
> + if (f (i) != g (i))
> + __builtin_abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "memchr" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr103798-6.c b/gcc/testsuite/c-c++-common/pr103798-6.c
> new file mode 100644
> index 00000000000..5ccb5ee66e0
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-6.c
> @@ -0,0 +1,27 @@
> +/* { dg-do run { target int128 } } */
> +/* { dg-options "-O2 -fdump-tree-optimized -save-temps" } */
> +
> +__attribute__ ((weak))
> +int f(char a)
> +{
> + return __builtin_memchr ("aEgiHx", a, 6) != 0;
> +}
> +
> +__attribute__ ((weak))
> +int g(char a)
> +{
> + return (a == 'a' || a == 'E' || a == 'g' || a == 'i' || a == 'H'
> + || a == 'x');
> +}
> +
> +int
> +main ()
> +{
> + for (int i = 0; i < 255; i++)
> + if (f (i) != g (i))
> + __builtin_abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "memchr" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr103798-7.c b/gcc/testsuite/c-c++-common/pr103798-7.c
> new file mode 100644
> index 00000000000..40fd38257d1
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-7.c
> @@ -0,0 +1,27 @@
> +/* { dg-do run { target int128 } } */
> +/* { dg-options "-O2 -fdump-tree-optimized -save-temps" } */
> +
> +__attribute__ ((weak))
> +int f(char a)
> +{
> + return __builtin_memchr ("aEgiHjZ", a, 7) == 0;
> +}
> +
> +__attribute__ ((weak))
> +int g(char a)
> +{
> + return (a != 'a' && a != 'E' && a != 'g' && a != 'i' && a != 'H'
> + && a != 'j' && a != 'Z');
> +}
> +
> +int
> +main ()
> +{
> + for (int i = 0; i < 255; i++)
> + if (f (i) != g (i))
> + __builtin_abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "memchr" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr103798-8.c b/gcc/testsuite/c-c++-common/pr103798-8.c
> new file mode 100644
> index 00000000000..0841b18cea4
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-8.c
> @@ -0,0 +1,27 @@
> +/* { dg-do run { target int128 } } */
> +/* { dg-options "-O2 -fdump-tree-optimized -save-temps" } */
> +
> +__attribute__ ((weak))
> +int f(int a)
> +{
> + return __builtin_memchr ("aEgiHx19ABC", a, 8) != 0;
> +}
> +
> +__attribute__ ((weak))
> +int g(char a)
> +{
> + return (a == 'a' || a == 'E' || a == 'g' || a == 'i' || a == 'H'
> + || a == 'x' || a == '1' || a == '9');
> +}
> +
> +int
> +main ()
> +{
> + for (int i = 0; i < 255; i++)
> + if (f (i + 256) != g (i + 256))
> + __builtin_abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "memchr" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr103798-9.c b/gcc/testsuite/c-c++-common/pr103798-9.c
> new file mode 100644
> index 00000000000..c5f0f94a4b5
> --- /dev/null
> +++ b/gcc/testsuite/c-c++-common/pr103798-9.c
> @@ -0,0 +1,10 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Os -fdump-tree-optimized -save-temps" } */
> +
> +int
> +f (char a)
> +{
> + return __builtin_memchr ("a", a, 1) == 0;
> +}
> +
> +/* { dg-final { scan-assembler-not "memchr" } } */
> diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
> index 69567ab3275..28549c85f76 100644
> --- a/gcc/tree-ssa-forwprop.cc
> +++ b/gcc/tree-ssa-forwprop.cc
> @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-dfa.h"
> #include "tree-ssa-propagate.h"
> #include "tree-ssa-dom.h"
> +#include "tree-ssa-strlen.h"
> #include "builtins.h"
> #include "tree-cfgcleanup.h"
> #include "cfganal.h"
> @@ -1177,6 +1178,15 @@ constant_pointer_difference (tree p1, tree p2)
> memcpy (p, "abcd ", 7);
> call if the latter can be stored by pieces during expansion.
>
> + Optimize
> + memchr ("abcd", a, 4) == 0;
> + or
> + memchr ("abcd", a, 4) != 0;
> + to
> + (a == 'a' || a == 'b' || a == 'c' || a == 'd') == 0
> + or
> + (a == 'a' || a == 'b' || a == 'c' || a == 'd') != 0
> +
> Also canonicalize __atomic_fetch_op (p, x, y) op x
> to __atomic_op_fetch (p, x, y) or
> __atomic_op_fetch (p, x, y) iop x
> @@ -1193,8 +1203,71 @@ simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
> return false;
> stmt1 = SSA_NAME_DEF_STMT (vuse);
>
> + tree res;
> +
> switch (DECL_FUNCTION_CODE (callee2))
> {
> + case BUILT_IN_MEMCHR:
> + if (gimple_call_num_args (stmt2) == 3
> + && (res = gimple_call_lhs (stmt2)) != nullptr
> + && use_in_zero_equality (res) != nullptr
> + && CHAR_BIT == 8
> + && BITS_PER_UNIT == 8)
> + {
> + tree ptr = gimple_call_arg (stmt2, 0);
> + if (TREE_CODE (ptr) != ADDR_EXPR
> + || TREE_CODE (TREE_OPERAND (ptr, 0)) != STRING_CST)
> + break;
> + unsigned HOST_WIDE_INT slen
> + = TREE_STRING_LENGTH (TREE_OPERAND (ptr, 0));
> + /* It must be a non-empty string constant. */
> + if (slen < 2)
> + break;
> + /* For -Os, only simplify strings with a single character. */
> + if (!optimize_bb_for_speed_p (gimple_bb (stmt2))
> + && slen > 2)
> + break;
> + tree size = gimple_call_arg (stmt2, 2);
> + /* Size must be a constant which is <= UNITS_PER_WORD and
> + <= the string length. */
> + if (TREE_CODE (size) != INTEGER_CST || integer_zerop (size))
> + break;
> +
> + if (!tree_fits_uhwi_p (size))
> + break;
> +
> + unsigned HOST_WIDE_INT sz = tree_to_uhwi (size);
> + if (sz > UNITS_PER_WORD || sz >= slen)
> + break;
> +
> + tree ch = gimple_call_arg (stmt2, 1);
> + location_t loc = gimple_location (stmt2);
> + if (!useless_type_conversion_p (char_type_node,
> + TREE_TYPE (ch)))
> + ch = fold_convert_loc (loc, char_type_node, ch);
> + const char *p = TREE_STRING_POINTER (TREE_OPERAND (ptr, 0));
> + unsigned int isize = sz;
> + tree *op = new tree[isize];
minor nit - sorry for not spotting earlier. Please use
tree *op = XALLOCAVEC (tree, isize);
Ok with that change.
Richard.
> + for (unsigned int i = 0; i < isize; i++)
> + {
> + op[i] = build_int_cst (char_type_node, p[i]);
> + op[i] = fold_build2_loc (loc, EQ_EXPR, boolean_type_node,
> + op[i], ch);
> + }
> + for (unsigned int i = isize - 1; i >= 1; i--)
> + op[i - 1] = fold_convert_loc (loc, boolean_type_node,
> + fold_build2_loc (loc,
> + BIT_IOR_EXPR,
> + boolean_type_node,
> + op[i - 1],
> + op[i]));
> + res = fold_convert_loc (loc, TREE_TYPE (res), op[0]);
> + gimplify_and_update_call_from_tree (gsi_p, res);
> + delete[] op;
> + return true;
> + }
> + break;
> +
> case BUILT_IN_MEMSET:
> if (gimple_call_num_args (stmt2) != 3
> || gimple_call_lhs (stmt2)
> diff --git a/gcc/tree-ssa-strlen.cc b/gcc/tree-ssa-strlen.cc
> index 7b3e3899ea2..5afbae1b72e 100644
> --- a/gcc/tree-ssa-strlen.cc
> +++ b/gcc/tree-ssa-strlen.cc
> @@ -3913,8 +3913,8 @@ strlen_pass::handle_builtin_memset (bool *zero_write)
> nonnull if and only RES is used in such expressions exclusively and
> in none other. */
>
> -static gimple *
> -use_in_zero_equality (tree res, bool exclusive = true)
> +gimple *
> +use_in_zero_equality (tree res, bool exclusive)
> {
> gimple *first_use = NULL;
>
> diff --git a/gcc/tree-ssa-strlen.h b/gcc/tree-ssa-strlen.h
> index 8d155450db8..fdb4d9d7783 100644
> --- a/gcc/tree-ssa-strlen.h
> +++ b/gcc/tree-ssa-strlen.h
> @@ -35,6 +35,8 @@ struct c_strlen_data;
> extern void get_range_strlen_dynamic (tree, gimple *, c_strlen_data *,
> pointer_query &);
>
> +extern gimple *use_in_zero_equality (tree, bool = true);
> +
> /* APIs internal to strlen pass. Defined in gimple-ssa-sprintf.cc. */
> extern bool handle_printf_call (gimple_stmt_iterator *, pointer_query &);
>
> --
> 2.36.1
>
next prev parent reply other threads:[~2022-07-14 6:42 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-07-13 16:50 H.J. Lu
2022-07-14 6:42 ` Richard Biener [this message]
2022-07-14 21:09 ` H.J. Lu
2022-09-07 10:57 ` Jan-Benedict Glaw
2022-09-07 12:00 ` Richard Biener
2022-09-10 5:38 ` Jan-Benedict Glaw
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=CAFiYyc3HFo03W4U0GLmNSYSLxi6rRTJ+EcuX-Beg+y-kN+1k_A@mail.gmail.com \
--to=richard.guenther@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hjl.tools@gmail.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).