From patchwork Fri Dec 9 12:06:41 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Prathamesh Kulkarni X-Patchwork-Id: 87456 Delivered-To: patch@linaro.org Received: by 10.140.20.101 with SMTP id 92csp269329qgi; Fri, 9 Dec 2016 04:07:07 -0800 (PST) X-Received: by 10.99.61.6 with SMTP id k6mr142728547pga.154.1481285227387; Fri, 09 Dec 2016 04:07:07 -0800 (PST) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id 37si33632511plq.20.2016.12.09.04.07.07 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 09 Dec 2016 04:07:07 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-return-443893-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-443893-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-443893-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=vFDfD2QXHZa/K+j QxCl86IG1xmZbjuyABW6hLEJ5C0218W2lF0EiZkATeZb1gi2lJZrGmK2Qz82ct/0 iDXLeWvdDONDidXVnSf8s/ewPKzsEZxbjdef+O2P21i3QUjMnIblSUUtJgwcUQuq jxWQ+CnY73btW0/mzgZ6q56vMyU0= 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=WUamtJCxLQa+uu82x8MVf nM7nPs=; b=xLY+4thW2HFk7Loj3k9E0YzoLz9UHZII9YDSQm8mq8vohAnPKIe5H 2/56GkKd9Pv/0kT53iXYZGsHCSGD/ptgclxtqLrHjZG9Vsg+ia6QgyxzR+8sxLtc FDkanvZIsxD3s0ykclQxmKe4kKxnT2W6lqRiHZzcCHj/4U5aCGWRcM= Received: (qmail 94011 invoked by alias); 9 Dec 2016 12:06:53 -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 93992 invoked by uid 89); 9 Dec 2016 12:06:53 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.4 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=no version=3.3.2 spammy=_Bool, _bool, H*Ad:U*rguenther, Kulkarni X-HELO: mail-io0-f171.google.com Received: from mail-io0-f171.google.com (HELO mail-io0-f171.google.com) (209.85.223.171) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 09 Dec 2016 12:06:44 +0000 Received: by mail-io0-f171.google.com with SMTP id d9so52511338ioe.0 for ; Fri, 09 Dec 2016 04:06:43 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=7dL46gNKxkZI2JK39qU7a0ZM0+SNWwfZ1pAL6KfuN4U=; b=OKLxuMS6p2WvDEs5fUDIqNA3/f42zzrnYS7hVAwMTW24iJcSQa2W9U67MvMBIad+IQ zX2OqGkV9MiV6GhF4wKp05qyniZvQ69mVhI7iRvPLKh8Xo9KVoE1L1JKSU6zzQbzqQT9 LAE6UVtNA2YH/bMttW9b5pwbRY7PPYbFMvg8H9OgW7s3SngApSSWgrQpDBOAm/zfVXsL jvzeTtcMwVK2LfZjLa2KSHy2Vfv3H+jJW2u1VCa8eYhXRWv9TDS5uH2DGkK+dxwe8QAu zSKx9Ul4UCvbnpuXxQXHxyCdBESZWfw1lmLuOl8/W7IFKx/S1T81/Vz9rFghvyC/XnCw 3PBA== X-Gm-Message-State: AKaTC02upe46voEJTtN9XMLDUng8jbofIzKc8pwzurdjkxuDPHsI6XDuNjuyGfuqMUxJVqPWjgL7nRefBKRNBtpx X-Received: by 10.36.194.70 with SMTP id i67mr6105420itg.21.1481285202402; Fri, 09 Dec 2016 04:06:42 -0800 (PST) MIME-Version: 1.0 Received: by 10.107.47.92 with HTTP; Fri, 9 Dec 2016 04:06:41 -0800 (PST) In-Reply-To: <20161207120627.GN3541@tucnak.redhat.com> References: <20161205181742.GS3541@tucnak.redhat.com> <20161207120627.GN3541@tucnak.redhat.com> From: Prathamesh Kulkarni Date: Fri, 9 Dec 2016 17:36:41 +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 7 December 2016 at 17:36, Jakub Jelinek wrote: > On Wed, Dec 07, 2016 at 05:02:46PM +0530, Prathamesh Kulkarni wrote: >> + if (arg1_len == NULL_TREE) >> + { >> + gimple_stmt_iterator gsi; >> + tree strlen_decl; >> + gimple *strlen_call; >> + >> + strlen_decl = builtin_decl_explicit (BUILT_IN_STRLEN); >> + strlen_call = gimple_build_call (strlen_decl, 1, >> + arg1); >> + arg1_len = make_ssa_name (size_type_node); >> + gimple_call_set_lhs (strlen_call, arg1_len); >> + update_stmt (strlen_call); >> + gsi = gsi_for_stmt (call_stmt); >> + gsi_insert_before (&gsi, strlen_call, GSI_SAME_STMT); >> + } > > Why? If the strlen isn't readily available, do you really think it is > always a win to replace one call with 2 calls? The string you want to do > strlen on can be huge, the haystack could be empty or very short, etc. > I'd just punt if strlen isn't known. >> + >> + 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_call_set_lhs (memcmp_call, memcmp_lhs); >> + update_stmt (memcmp_call); >> + gsi_remove (&gsi, true); >> + gsi_insert_before (&gsi, memcmp_call, GSI_SAME_STMT); >> + >> + gsi = gsi_for_stmt (stmt); >> + tree zero = build_zero_cst (TREE_TYPE (memcmp_lhs)); >> + gassign *ga = gimple_build_assign (lhs, code, >> + memcmp_lhs, zero); >> + gsi_replace (&gsi, ga, false); >> + update_ssa (TODO_update_ssa); > > And this is certainly even more wrong than the old TODO_update_ssa at the > end of the pass, now you'll do it for every single replacement in the > function. Why do you need it? The old call stmt has gimple_vdef and > gimple_vuse, so just copy those over, see how e.g. > replace_call_with_call_and_fold in gimple-fold.c does that. > If you don't add strlen, you need to move the vdef/vuse from stmt to > memcmp_call, if you really want to add strlen (see above note though), > then that call should have a vuse added (same vuse as the stmt originally > had). Hi, Thanks for the suggestions. In attached patch, I dropped the transform if strlen (t) is unknown. Since strstr is marked pure, so IIUC call_stmt for strstr shouldn't have vdef assoicated with it ? (gimple_vdef for call_stmt returned NULL for test-cases I tried it with). Moving gimple_vuse from call_stmt to memcmp_call worked for me. Does the patch look OK ? Bootstrap+tested on x86_64-unknown-linux-gnu with --enable-langauges=all,ada Cross-tested on arm*-*-*, aarch64*-*-*. Thanks, Prathamesh > > Jakub diff --git a/gcc/testsuite/gcc.dg/strlenopt-30.c b/gcc/testsuite/gcc.dg/strlenopt-30.c new file mode 100644 index 0000000..329bc25 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-30.c @@ -0,0 +1,44 @@ +/* { 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"); +} + +/* Do not perform transform, since strlen (t) + is unknown. */ + +__attribute__((no_icf)) +_Bool f4(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 f5(char *s) +{ + void foo(char *); + + char *t1 = __builtin_strstr (s, "hello"); + foo (t1); + return (t1 == s); +} + +/* { dg-final { scan-tree-dump-times "__builtin_memcmp" 3 "strlen" } } */ diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c index 339812e..06b07b0 100644 --- a/gcc/tree-ssa-strlen.c +++ b/gcc/tree-ssa-strlen.c @@ -2302,7 +2302,81 @@ 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)) + + /* Fold strstr (s, t) == s to memcmp (s, t, strlen (t)) == 0. + if strlen (t) is known and var holding return value of strstr + has single use. */ + + else if (TREE_CODE (lhs) == SSA_NAME && INTEGRAL_TYPE_P (TREE_TYPE (lhs))) + { + enum tree_code code = gimple_assign_rhs_code (stmt); + 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) + { + gcall *call_stmt = dyn_cast (SSA_NAME_DEF_STMT (rhs1)); + if (!call_stmt) + { + call_stmt = dyn_cast (SSA_NAME_DEF_STMT (rhs2)); + tree tmp = rhs1; + rhs1 = rhs2; + rhs2 = tmp; + } + + tree call_lhs; + if (call_stmt + && gimple_call_builtin_p (call_stmt, BUILT_IN_STRSTR) + && (call_lhs = gimple_call_lhs (call_stmt)) + && has_single_use (call_lhs)) + { + tree arg0 = gimple_call_arg (call_stmt, 0); + if (operand_equal_p (arg0, rhs2, 0)) + { + 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); + gsi = gsi_for_stmt (stmt); + tree zero = build_zero_cst (TREE_TYPE (memcmp_lhs)); + gassign *ga = gimple_build_assign (lhs, code, + memcmp_lhs, + zero); + gsi_replace (&gsi, ga, false); + } + } + } + } + } + } + else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) { tree type = TREE_TYPE (lhs); if (TREE_CODE (type) == ARRAY_TYPE)