From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pj1-x1033.google.com (mail-pj1-x1033.google.com [IPv6:2607:f8b0:4864:20::1033]) by sourceware.org (Postfix) with ESMTPS id 57F523857BA9 for ; Mon, 20 Jun 2022 21:42:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 57F523857BA9 Received: by mail-pj1-x1033.google.com with SMTP id w24so2960214pjg.5 for ; Mon, 20 Jun 2022 14:42:25 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=WwSVHc0k6+ZKFowDcA3LSafZatG/m7DkHpuLF5BQDdw=; b=MQzbJycSqznlYjYu0Ai6oAoWak65GISpaBPmgJmxB+vN3E34oClU7+k1A5cvWjmOnp YnZTMvCo1Vi5qlpjldhGpNkn2GUBRROdBrnOE5hGhKgp1wDEvSq1tERmdP7om5wEofet YvQEpWboZtz7pBMjuU+dkMGme3wyAGB5ddRrfWwv297NZ3yL9RxqCqXxXLmlD8xjlRLT DgtNtVymf3JAI8lZ4nIENDeBVH04O591/pUuRt1zp13P7yRhpUtDUgAh1L+o2bSGOb0d IXW3ok+ZF08TZmtEi9h9BZ3XBldyHxWU3xKD1q7SjoCjvC3OGaDtyas8YOpemTfN/VeC rxzQ== X-Gm-Message-State: AJIora86Hv8TDauN39vbX8873S0Dg1zMApp31Ga8j1TiiG14sTO5gExv lTtbi6FaDyGJtNkdfWAXl6bbHP3daoc= X-Google-Smtp-Source: AGRyM1vphRuMVxzBhYWSf6IlamV/c0HXNW6Yu4Aab6tO34OTeTb0pLrtVnDzxIUttz8aswz2zxdA9w== X-Received: by 2002:a17:90b:1b0d:b0:1ec:9f74:30ab with SMTP id nu13-20020a17090b1b0d00b001ec9f7430abmr9794459pjb.58.1655761343948; Mon, 20 Jun 2022 14:42:23 -0700 (PDT) Received: from noah-tgl.. ([192.55.60.47]) by smtp.gmail.com with ESMTPSA id h14-20020a170902f7ce00b0016909678e2csm4931839plw.292.2022.06.20.14.42.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Jun 2022 14:42:23 -0700 (PDT) From: Noah Goldstein To: gcc-patches@gcc.gnu.org Cc: goldstein.w.n@gmail.com, hjl.tools@gmail.com, jakub@redhat.com Subject: [PATCH v2] tree-optimization/95821 - Convert strlen + strchr to memchr Date: Mon, 20 Jun 2022 14:42:20 -0700 Message-Id: <20220620214220.2776648-1-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220620163536.2653437-1-goldstein.w.n@gmail.com> References: <20220620163536.2653437-1-goldstein.w.n@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 20 Jun 2022 21:42:28 -0000 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. --- gcc/testsuite/c-c++-common/pr95821-1.c | 15 +++++ gcc/testsuite/c-c++-common/pr95821-2.c | 17 +++++ gcc/testsuite/c-c++-common/pr95821-3.c | 17 +++++ gcc/testsuite/c-c++-common/pr95821-4.c | 16 +++++ gcc/testsuite/c-c++-common/pr95821-5.c | 19 ++++++ gcc/testsuite/c-c++-common/pr95821-6.c | 18 ++++++ gcc/testsuite/c-c++-common/pr95821-7.c | 18 ++++++ gcc/testsuite/c-c++-common/pr95821-8.c | 19 ++++++ gcc/tree-ssa-strlen.cc | 89 ++++++++++++++++++++------ 9 files changed, 209 insertions(+), 19 deletions(-) create mode 100644 gcc/testsuite/c-c++-common/pr95821-1.c create mode 100644 gcc/testsuite/c-c++-common/pr95821-2.c create mode 100644 gcc/testsuite/c-c++-common/pr95821-3.c create mode 100644 gcc/testsuite/c-c++-common/pr95821-4.c create mode 100644 gcc/testsuite/c-c++-common/pr95821-5.c create mode 100644 gcc/testsuite/c-c++-common/pr95821-6.c create mode 100644 gcc/testsuite/c-c++-common/pr95821-7.c create mode 100644 gcc/testsuite/c-c++-common/pr95821-8.c diff --git a/gcc/testsuite/c-c++-common/pr95821-1.c b/gcc/testsuite/c-c++-common/pr95821-1.c new file mode 100644 index 00000000000..e0beb609ea2 --- /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" } } */ + +#include + +char * +foo (char *s, char c) +{ + size_t slen = __builtin_strlen(s); + if(slen < 1000) + return NULL; + + return __builtin_strchr(s, c); +} diff --git a/gcc/testsuite/c-c++-common/pr95821-2.c b/gcc/testsuite/c-c++-common/pr95821-2.c new file mode 100644 index 00000000000..5429f0586be --- /dev/null +++ b/gcc/testsuite/c-c++-common/pr95821-2.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ +/* { dg-final { scan-assembler-not "memchr" } } */ + +#include + +char * +foo (char *s, char c, char * other) +{ + size_t slen = __builtin_strlen(s); + if(slen < 1000) + return NULL; + + *other = 0; + + return __builtin_strchr(s, c); +} diff --git a/gcc/testsuite/c-c++-common/pr95821-3.c b/gcc/testsuite/c-c++-common/pr95821-3.c new file mode 100644 index 00000000000..bc929c6044b --- /dev/null +++ b/gcc/testsuite/c-c++-common/pr95821-3.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ +/* { dg-final { scan-assembler "memchr" } } */ + +#include + +char * +foo (char * __restrict s, char c, char * __restrict other) +{ + size_t slen = __builtin_strlen(s); + if(slen < 1000) + return NULL; + + *other = 0; + + return __builtin_strchr(s, c); +} diff --git a/gcc/testsuite/c-c++-common/pr95821-4.c b/gcc/testsuite/c-c++-common/pr95821-4.c new file mode 100644 index 00000000000..684b41d5b70 --- /dev/null +++ b/gcc/testsuite/c-c++-common/pr95821-4.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ +/* { dg-final { scan-assembler "memchr" } } */ + +#include +#include + +char * +foo (char *s, char c) +{ + size_t slen = strlen(s); + if(slen < 1000) + return NULL; + + return strchr(s, c); +} diff --git a/gcc/testsuite/c-c++-common/pr95821-5.c b/gcc/testsuite/c-c++-common/pr95821-5.c new file mode 100644 index 00000000000..00c1d93b614 --- /dev/null +++ b/gcc/testsuite/c-c++-common/pr95821-5.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ +/* { dg-final { scan-assembler-not "memchr" } } */ + +#include +#include + +char * +foo (char *s, char c, char * other) +{ + size_t slen = strlen(s); + if(slen < 1000) + return NULL; + + *other = 0; + + return strchr(s, c); +} +int main() {} diff --git a/gcc/testsuite/c-c++-common/pr95821-6.c b/gcc/testsuite/c-c++-common/pr95821-6.c new file mode 100644 index 00000000000..dec839de5ea --- /dev/null +++ b/gcc/testsuite/c-c++-common/pr95821-6.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ +/* { dg-final { scan-assembler "memchr" } } */ + +#include +#include + +char * +foo (char * __restrict s, char c, char * __restrict other) +{ + size_t slen = strlen(s); + if(slen < 1000) + return NULL; + + *other = 0; + + return strchr(s, c); +} diff --git a/gcc/testsuite/c-c++-common/pr95821-7.c b/gcc/testsuite/c-c++-common/pr95821-7.c new file mode 100644 index 00000000000..9da0fff7250 --- /dev/null +++ b/gcc/testsuite/c-c++-common/pr95821-7.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ +/* { dg-final { scan-assembler "memchr" } } */ + +#include +#include + +char * +foo (char * __restrict s, char c, char * __restrict other) +{ + size_t slen = strlen(s); + if(slen < 1000 || c == 0) + return NULL; + + *other = 0; + + return strchr(s, c); +} diff --git a/gcc/testsuite/c-c++-common/pr95821-8.c b/gcc/testsuite/c-c++-common/pr95821-8.c new file mode 100644 index 00000000000..5eb02c6fea4 --- /dev/null +++ b/gcc/testsuite/c-c++-common/pr95821-8.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O2" } */ +/* { dg-final { scan-assembler-not "strchr" } } */ +/* { dg-final { scan-assembler-not "memchr" } } */ + +#include +#include + +char * +foo (char * __restrict s, int c, char * __restrict other) +{ + size_t slen = strlen(s); + if(slen < 1000 || c != 0x100) + return NULL; + + *other = 0; + + return strchr(s, c); +} diff --git a/gcc/tree-ssa-strlen.cc b/gcc/tree-ssa-strlen.cc index 1d4c0f78fbf..807624adc94 100644 --- 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 + 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))); tree src = gimple_call_arg (stmt, 0); @@ -2452,32 +2459,72 @@ 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 + 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 + 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. 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)) + { + tree one = build_int_cst (TREE_TYPE (rhs), 1); + rhs = fold_build2_loc (loc, PLUS_EXPR, TREE_TYPE (rhs), + unshare_expr (rhs), one); + tree size = make_ssa_name (TREE_TYPE (rhs)); + gassign *size_stmt = gimple_build_assign (size, rhs); + gsi_insert_before (&m_gsi, size_stmt, GSI_SAME_STMT); + rhs = size; + } + if (!update_gimple_call (&m_gsi, fn, 3, src, chr, rhs)) + return; } else { - rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs)); - rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR, - TREE_TYPE (src), src, rhs); - if (!useless_type_conversion_p (TREE_TYPE (lhs), - TREE_TYPE (rhs))) - rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); + if (si != NULL && si->endptr != NULL_TREE) + { + 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); + } + else + { + rhs = fold_convert_loc (loc, sizetype, unshare_expr (rhs)); + rhs = fold_build2_loc (loc, POINTER_PLUS_EXPR, + TREE_TYPE (src), src, rhs); + if (!useless_type_conversion_p (TREE_TYPE (lhs), + TREE_TYPE (rhs))) + rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); + } + gimplify_and_update_call_from_tree (&m_gsi, rhs); } - gimplify_and_update_call_from_tree (&m_gsi, rhs); + stmt = gsi_stmt (m_gsi); update_stmt (stmt); + if (dump_file && (dump_flags & TDF_DETAILS) != 0) { fprintf (dump_file, "into: "); print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); } - if (si != NULL - && si->endptr == NULL_TREE + + /* Don't update strlen of lhs if search-char wasn't know to be zero. */ + if (!is_strchr_zerop) + return; + + if (si != NULL && si->endptr == NULL_TREE && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) { si = unshare_strinfo (si); @@ -2487,6 +2534,10 @@ strlen_pass::handle_builtin_strchr () return; } } + + if (!is_strchr_zerop) + return; + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) return; if (TREE_CODE (src) != SSA_NAME || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (src)) -- 2.34.1