From patchwork Wed Dec 14 07:57:44 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Prathamesh Kulkarni X-Patchwork-Id: 87987 Delivered-To: patch@linaro.org Received: by 10.140.20.101 with SMTP id 92csp66674qgi; Tue, 13 Dec 2016 23:58:19 -0800 (PST) X-Received: by 10.84.225.147 with SMTP id u19mr1329333plj.109.1481702299743; Tue, 13 Dec 2016 23:58:19 -0800 (PST) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id z190si51630207pgd.290.2016.12.13.23.58.19 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 13 Dec 2016 23:58:19 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-return-444358-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org; spf=pass (google.com: domain of gcc-patches-return-444358-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-444358-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; q=dns; s=default; b=Zw7GqqmQG1mMwUg zUC78AeT5aaGQbbLhIk289DY/x3iWkjk4i9lOKg2JEl/9piZuvw/DzmRMLeZxi1t 2Mps9Z9O9fq63gJZdUzS26fA5tb6bxV66sJbav8xi4T92hzLzFoRpjR5h0V2iuRJ F8MyrIYdm/VQ1rDIWPeHoLCvC6aU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:cc:content-type; s=default; bh=DtMGh45QEAT9vlV8xt1Hk nxkU7M=; b=ijRuS+bE13iDbD36YygYhB4y/LQ28SDHYnkVekhnpRxqFF9i4KBXY 2ajXj1xPRzbJZlyF55YHO52XzFgJ6TybGk/6njmg8RbjKwdtWJubqx9uWQtMNV+6 FEqUUaaxLO/Le+th5zID7p9UZaijQOvGTcLpaMEiDkcjHGiaCzL2AQ= Received: (qmail 115263 invoked by alias); 14 Dec 2016 07:57:58 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 115233 invoked by uid 89); 14 Dec 2016 07:57:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.5 required=5.0 tests=AWL, BAYES_50, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=sk:pratham, U*prathamesh.kulkarni, prathamesh.kulkarni@linaro.org, prathameshkulkarnilinaroorg X-HELO: mail-io0-f180.google.com Received: from mail-io0-f180.google.com (HELO mail-io0-f180.google.com) (209.85.223.180) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 14 Dec 2016 07:57:47 +0000 Received: by mail-io0-f180.google.com with SMTP id h30so27166039iod.2 for ; Tue, 13 Dec 2016 23:57:46 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=n+Q+m387RBfjVIK/Vzch+suo9bAP+RJloMZnJ2HtTkk=; b=ooaprDgzquQhlT2OSzm9ReeA1jk1DZ8HsB9ceK5WkDtVwpvY7BWt1erb6vT8nZAtB8 4US9mjYnt4AiMpkfOF4QSAYYKKacr1M0dtZ9sN6laT5NUxuSpW0lULOBcOf5QWedqdY8 tKia0mOqvVxRa+kvzMW8JYBkheLpfA8VMqaExa2nX7Q0pXT+hGvcYO00JXowBgx0Lnjx AI7gLfl0ZG4o0mowHhe69sslL3O7CnE7doAMNpDhvZlWZX+nwQKycb1RkFUhOoMnOIp8 Wix6MPNhtVKykM/4mGmiyO2eWY14MRcYqq2JYe2YwO7LcCYLz5xZhgxhUw4c0XvmtlKT knlw== X-Gm-Message-State: AKaTC02qq489os1KHzdhftoH7fIdvTznLJ677UHaLYeBOj62d3CokW1KFQsjuggmnoYm3E/+pphnQueWnf+hl+qB X-Received: by 10.107.3.168 with SMTP id e40mr83689012ioi.89.1481702264785; Tue, 13 Dec 2016 23:57:44 -0800 (PST) MIME-Version: 1.0 Received: by 10.107.47.92 with HTTP; Tue, 13 Dec 2016 23:57:44 -0800 (PST) In-Reply-To: <20161213122425.GR3541@tucnak.redhat.com> References: <20161205181742.GS3541@tucnak.redhat.com> <20161207120627.GN3541@tucnak.redhat.com> <20161209122932.GA3541@tucnak.redhat.com> <20161213095726.GM3541@tucnak.redhat.com> <20161213122425.GR3541@tucnak.redhat.com> From: Prathamesh Kulkarni Date: Wed, 14 Dec 2016 13:27:44 +0530 Message-ID: Subject: Re: Fold strstr (s, t) eq/ne s to strcmp (s, t) eq/ne 0 if strlen (t) is known To: Jakub Jelinek Cc: gcc Patches , Richard Biener X-IsSubscribed: yes On 13 December 2016 at 17:54, Jakub Jelinek wrote: > On Tue, Dec 13, 2016 at 05:41:09PM +0530, Prathamesh Kulkarni wrote: >> --- a/gcc/tree-ssa-strlen.c >> +++ b/gcc/tree-ssa-strlen.c >> @@ -2222,6 +2222,90 @@ handle_char_store (gimple_stmt_iterator *gsi) >> return true; >> } >> >> +/* Try to fold strstr (s, t) eq/ne s to memcmp (s, t, strlen (t)) eq/ne 0. */ >> + >> +static void >> +fold_strstr_to_memcmp (enum tree_code code, tree rhs1, tree rhs2, gimple *stmt) > > You can drop code argument here, see below. And I'd say it is better to > do the > if (TREE_CODE (rhs1) != SSA_NAME || TREE_CODE (rhs2) != SSA_NAME) > return; > here than repeat it in all the callers. > >> + if (gimple_assign_rhs_code (stmt) == COND_EXPR) >> + { >> + tree cond = gimple_assign_rhs1 (stmt); >> + TREE_SET_CODE (cond, code); > > TREE_CODE (cond) is already code, so no need to set it again. > >> + gcond *cond = as_a (stmt); >> + gimple_cond_set_lhs (cond, memcmp_lhs); >> + gimple_cond_set_rhs (cond, zero); >> + gimple_cond_set_code (cond, code); > > And gimple_cond_code (cond) == code here too. > >> + update_stmt (cond); >> + } > > You can perhaps move the update_stmt (stmt); to a single spot after > all the 3 cases are handled. > >> + if (cond_code == EQ_EXPR || cond_code == NE_EXPR) >> + { >> + tree rhs1 = TREE_OPERAND (cond, 0); >> + tree rhs2 = TREE_OPERAND (cond, 1); > > While it is necessary to check cond_code here and in the other spots > similarly, because otherwise you don't know if it has 2 arguments etc., > you can avoid the SSA_NAME tests here. > >> + if (TREE_CODE (rhs1) == SSA_NAME >> + && TREE_CODE (rhs2) == SSA_NAME) >> + fold_strstr_to_memcmp (cond_code, rhs1, rhs2, stmt); >> + } >> + } >> + else if (code == EQ_EXPR || code == NE_EXPR) >> + { >> + tree rhs1 = gimple_assign_rhs1 (stmt); >> + tree rhs2 = gimple_assign_rhs2 (stmt); >> + >> + if (TREE_CODE (rhs1) == SSA_NAME >> + && TREE_CODE (rhs2) == SSA_NAME) > > And here. >> + fold_strstr_to_memcmp (code, rhs1, rhs2, stmt); >> + } >> + } >> + else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) >> { >> tree type = TREE_TYPE (lhs); >> if (TREE_CODE (type) == ARRAY_TYPE) >> @@ -2316,6 +2427,17 @@ strlen_optimize_stmt (gimple_stmt_iterator *gsi) >> } >> } >> } >> + else if (gcond *cond = dyn_cast (stmt)) >> + { >> + enum tree_code code = gimple_cond_code (cond); >> + tree lhs = gimple_cond_lhs (stmt); >> + tree rhs = gimple_cond_rhs (stmt); >> + >> + if ((code == EQ_EXPR || code == NE_EXPR) >> + && TREE_CODE (lhs) == SSA_NAME >> + && TREE_CODE (rhs) == SSA_NAME) > > And here. >> + fold_strstr_to_memcmp (code, lhs, rhs, stmt); >> + } >> >> if (gimple_vdef (stmt)) >> maybe_invalidate (stmt); > > Otherwise LGTM, but it would be nice to cover also the COND_EXPR case by a > testcase (can be done incrementally). Hi Jakub, Done the changes in attached version. Bootstrap+tested on x86_64-unknown-linux-gnu with default languages and cross-tested on arm*-*-*, aarch64*-*-* with c,c++,fortran. It it OK to commit ? I am trying to come up with COND_EXPR test-case. Thanks, Prathamesh > > Jakub 2016-12-14 Jakub Jelinek Prathamesh Kulkarni * tree-ssa-strlen.c (fold_strstr_to_memcmp): New function. (strlen_optimize_stmt): Call fold_strstr_to_memcmp. testsuite/ * gcc.dg/strlenopt-30.c: New test-case. diff --git a/gcc/testsuite/gcc.dg/strlenopt-30.c b/gcc/testsuite/gcc.dg/strlenopt-30.c new file mode 100644 index 0000000..089b3a2 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-30.c @@ -0,0 +1,63 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +__attribute__((no_icf)) +_Bool f1(char *s) +{ + return __builtin_strstr (s, "hello") == s; +} + +__attribute__((no_icf)) +_Bool f2(char *s) +{ + return s == __builtin_strstr (s, "hello"); +} + +__attribute__((no_icf)) +_Bool f3(char *s) +{ + return s != __builtin_strstr (s, "hello"); +} + +__attribute__((no_icf)) +_Bool f4() +{ + char *foo_f4(void); + char *t1 = foo_f4(); + char *t2 = __builtin_strstr (t1, "hello"); + _Bool t3 = t2 == t1; + return t3; +} + +__attribute__((no_icf)) +void f5(char *s) +{ + char *t1 = __builtin_strstr (s, "hello"); + void foo_f5(void); + if (t1 != s) + foo_f5(); +} + +/* Do not perform transform, since strlen (t) + is unknown. */ + +__attribute__((no_icf)) +_Bool f6(char *s, char *t) +{ + return __builtin_strstr (s, t) == s; +} + +/* Do not perform transform in this case, since + t1 doesn't have single use. */ + +__attribute__((no_icf)) +_Bool f7(char *s) +{ + void foo_f7(char *); + + char *t1 = __builtin_strstr (s, "hello"); + foo_f7 (t1); + return (t1 == s); +} + +/* { dg-final { scan-tree-dump-times "__builtin_memcmp" 5 "strlen" } } */ diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c index 339812e..67075f0 100644 --- a/gcc/tree-ssa-strlen.c +++ b/gcc/tree-ssa-strlen.c @@ -2222,6 +2222,90 @@ handle_char_store (gimple_stmt_iterator *gsi) return true; } +/* Try to fold strstr (s, t) eq/ne s to memcmp (s, t, strlen (t)) eq/ne 0. */ + +static void +fold_strstr_to_memcmp (tree rhs1, tree rhs2, gimple *stmt) +{ + if (TREE_CODE (rhs1) != SSA_NAME + || TREE_CODE (rhs2) != SSA_NAME) + return; + + gimple *call_stmt = NULL; + for (int pass = 0; pass < 2; pass++) + { + gimple *g = SSA_NAME_DEF_STMT (rhs1); + if (gimple_call_builtin_p (g, BUILT_IN_STRSTR) + && has_single_use (rhs1) + && gimple_call_arg (g, 0) == rhs2) + { + call_stmt = g; + break; + } + std::swap (rhs1, rhs2); + } + + if (call_stmt) + { + tree arg0 = gimple_call_arg (call_stmt, 0); + + if (arg0 == rhs2) + { + tree arg1 = gimple_call_arg (call_stmt, 1); + tree arg1_len = NULL_TREE; + int idx = get_stridx (arg1); + + if (idx) + { + if (idx < 0) + arg1_len = build_int_cst (size_type_node, ~idx); + else + { + strinfo *si = get_strinfo (idx); + if (si) + arg1_len = get_string_length (si); + } + } + + if (arg1_len != NULL_TREE) + { + gimple_stmt_iterator gsi = gsi_for_stmt (call_stmt); + tree memcmp_decl = builtin_decl_explicit (BUILT_IN_MEMCMP); + gcall *memcmp_call = gimple_build_call (memcmp_decl, 3, + arg0, arg1, arg1_len); + tree memcmp_lhs = make_ssa_name (integer_type_node); + gimple_set_vuse (memcmp_call, gimple_vuse (call_stmt)); + gimple_call_set_lhs (memcmp_call, memcmp_lhs); + gsi_remove (&gsi, true); + gsi_insert_before (&gsi, memcmp_call, GSI_SAME_STMT); + tree zero = build_zero_cst (TREE_TYPE (memcmp_lhs)); + + if (is_gimple_assign (stmt)) + { + if (gimple_assign_rhs_code (stmt) == COND_EXPR) + { + tree cond = gimple_assign_rhs1 (stmt); + TREE_OPERAND (cond, 0) = memcmp_lhs; + TREE_OPERAND (cond, 1) = zero; + } + else + { + gimple_assign_set_rhs1 (stmt, memcmp_lhs); + gimple_assign_set_rhs2 (stmt, zero); + } + } + else + { + gcond *cond = as_a (stmt); + gimple_cond_set_lhs (cond, memcmp_lhs); + gimple_cond_set_rhs (cond, zero); + } + update_stmt (stmt); + } + } + } +} + /* Attempt to optimize a single statement at *GSI using string length knowledge. */ @@ -2302,7 +2386,23 @@ strlen_optimize_stmt (gimple_stmt_iterator *gsi) else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) handle_pointer_plus (gsi); } - else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) + else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs))) + { + enum tree_code code = gimple_assign_rhs_code (stmt); + if (code == COND_EXPR) + { + tree cond = gimple_assign_rhs1 (stmt); + enum tree_code cond_code = TREE_CODE (cond); + + if (cond_code == EQ_EXPR || cond_code == NE_EXPR) + fold_strstr_to_memcmp (TREE_OPERAND (cond, 0), + TREE_OPERAND (cond, 1), stmt); + } + else if (code == EQ_EXPR || code == NE_EXPR) + fold_strstr_to_memcmp (gimple_assign_rhs1 (stmt), + gimple_assign_rhs2 (stmt), stmt); + } + else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) { tree type = TREE_TYPE (lhs); if (TREE_CODE (type) == ARRAY_TYPE) @@ -2316,6 +2416,13 @@ strlen_optimize_stmt (gimple_stmt_iterator *gsi) } } } + else if (gcond *cond = dyn_cast (stmt)) + { + enum tree_code code = gimple_cond_code (cond); + if (code == EQ_EXPR || code == NE_EXPR) + fold_strstr_to_memcmp (gimple_cond_lhs (stmt), + gimple_cond_rhs (stmt), stmt); + } if (gimple_vdef (stmt)) maybe_invalidate (stmt);