From patchwork Mon Dec 5 18:02:15 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Prathamesh Kulkarni X-Patchwork-Id: 86606 Delivered-To: patch@linaro.org Received: by 10.140.20.101 with SMTP id 92csp1615500qgi; Mon, 5 Dec 2016 10:02:42 -0800 (PST) X-Received: by 10.98.108.3 with SMTP id h3mr58623048pfc.65.1480960962293; Mon, 05 Dec 2016 10:02:42 -0800 (PST) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id t124si15407188pgt.334.2016.12.05.10.02.42 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 05 Dec 2016 10:02:42 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-return-443503-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-443503-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-443503-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:from:date:message-id:subject:to:content-type; q= dns; s=default; b=lYnSzQWB3PCYW9sHZGafeXd+RejkFklne5GQghTb842ngz NSiTgOSCmDF6cgJeAijo6ejzbmbzGrUdSJQZ8cZ9cccmtgdv3LyqyJHSl/EfRmqp zqywWfgtTVkaa4+iV+CZDtPkMn3MBkrz6QRK+1iZ94Vo1/SptQ3OixaD1kekE= 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:from:date:message-id:subject:to:content-type; s= default; bh=vZ2FbOD5isd4xK2m8pzx5/UYozI=; b=eXmOTTtwts559U9SdWq2 L9EfdvbanZLynbFoFZiisUcRQ4cCxjmWVcaIFElWaS7xZcyoeu6Rdg3oLze/Gp/V x6AZW/DcpCVJR/uy6rxPGF/2iYJNzym9zNk5vAehQ8DH0DkMgeIEyuqzJnq8V4xW jY4CLB1XCLj3BeHGCrknq0k= Received: (qmail 17033 invoked by alias); 5 Dec 2016 18:02:30 -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 17021 invoked by uid 89); 5 Dec 2016 18:02:29 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=gsi, Hx-languages-length:4055 X-HELO: mail-io0-f177.google.com Received: from mail-io0-f177.google.com (HELO mail-io0-f177.google.com) (209.85.223.177) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 05 Dec 2016 18:02:19 +0000 Received: by mail-io0-f177.google.com with SMTP id c21so562112736ioj.1 for ; Mon, 05 Dec 2016 10:02:19 -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:from:date:message-id:subject:to; bh=CHdw7X8Lvw8ZYg2uSn/8OVKps/PnTkGwunN7UXbGpWQ=; b=Gmvq5xf1i6qwtrFL3+LPEarCqXx3MxGHm5hjaEabfJg6SujuTzzQq3UTSrPNz0SOnA aG6/C3IOz+PQEwECpPAb81uHfJOEdZiKQXwWbTop8qIEs0TLY32BwHehjt8joPCEG9Kb t6Xe/S9HVAg8UONVRQeLxeBpxlzIQDW7KyXK+gfB6aS+8YlDTKp/pZT6hunpzIynhfVY s8X3JzpfuVf2e5DPCv4gPWqWKMt14+SUyeCaap9s9iPM11rVtRi4BhVFZSBFH1DB1MLq qRx1J5grVIEYzHwcvGD/e5JE3BNE3Itbvm8jqOM3UI0yRidxZXhblLiv5kyCW1CMJK9t BFog== X-Gm-Message-State: AKaTC00mbgxGCb3crZzatIgN6DEAVmgGaQesJqR6d/WyF/CHOCLXnJZO3oXMqUTxLINg3Ff5yi8QjGig9+UkWKTt X-Received: by 10.107.57.193 with SMTP id g184mr52665929ioa.183.1480960936249; Mon, 05 Dec 2016 10:02:16 -0800 (PST) MIME-Version: 1.0 Received: by 10.107.47.92 with HTTP; Mon, 5 Dec 2016 10:02:15 -0800 (PST) From: Prathamesh Kulkarni Date: Mon, 5 Dec 2016 23:32:15 +0530 Message-ID: Subject: Fold strstr (s, t) eq/ne s to strcmp (s, t) eq/ne 0 if strlen (t) is known To: gcc Patches , Richard Biener X-IsSubscribed: yes Hi, This patch folds strstr (s, t) eq/ne s to strcmp (s, t) eq/ne 0 if strlen (t) is known. One issue I came across was forwprop1 reverses the order of operands in eq_expr below: eg test-case: _Bool f(char *s, int cond) { char *t1 = __builtin_strstr (s, "hello"); _Bool t2 = (t1 == s); return t2; } forwprop1 dump: f (char * s, int cond) { _Bool t2; char * t1; [0.0%]: t1_3 = __builtin_strstr (s_2(D), "hello"); t2_4 = s_2(D) == t1_3; return t2_4; } So I had to check if SSA_NAME_DEF_STMT (rhs2) was call to strstr rather than rhs1. I suppose that's OK ? clang unconditionally transforms strstr (s, t) == s to strncmp (s, t, strlen (t)) However I am not sure what algorithm glibc's strstr uses, so didn't attempt to transform if strlen (t) is unknown. Should we do the transform even if strlen (t) is unknown ? Thanks, Prathamesh 2016-12-05 Prathamesh Kulkarni * tree-ssa-strlen.c (strlen_optimize_stmt): Fold strstr(s, t) == s to strcmp (s, t) == 0. (pass_data_strlen): Set todo_flags_finish to TODO_update_ssa. 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..737f37d --- /dev/null +++ b/gcc/testsuite/gcc.dg/strlenopt-30.c @@ -0,0 +1,27 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +_Bool f1(char *s) +{ + char *t = "hello"; + char *t1 = __builtin_strstr (s, t); + _Bool t2 = (t1 == s); + return t2; +} + +_Bool f2(char *s) +{ + char *t = "hello"; + char *t1 = __builtin_strstr (s, t); + _Bool t2 = (t1 != s); + return t2; +} + +_Bool f3(char *s, char *t) +{ + char *t1 = __builtin_strstr (s, t); + _Bool t2 = (t1 == s); + return t2; +} + +/* { dg-final { scan-tree-dump-times "__builtin_strcmp" 2 "strlen" } } */ diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c index 339812e..8977e80 100644 --- a/gcc/tree-ssa-strlen.c +++ b/gcc/tree-ssa-strlen.c @@ -2302,6 +2302,55 @@ strlen_optimize_stmt (gimple_stmt_iterator *gsi) else if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR) handle_pointer_plus (gsi); } + + /* Fold strstr (s, t) == s to strcmp (s, t) == 0. if strlen (t) + is known. */ + 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 (rhs2) == SSA_NAME) + { + gcall *call_stmt = dyn_cast (SSA_NAME_DEF_STMT (rhs2)); + if (call_stmt + && gimple_call_builtin_p (call_stmt, BUILT_IN_STRSTR)) + { + tree arg0 = gimple_call_arg (call_stmt, 0); + if (operand_equal_p (arg0, rhs1, 0)) + { + /* Check if strlen(arg1) is known. */ + tree arg1 = gimple_call_arg (call_stmt, 1); + int idx = get_stridx (arg1); + strinfo *si = NULL; + if (idx) + si = get_strinfo (idx); + if ((idx < 0) + || (si && (get_string_length (si) != NULL_TREE))) + { + gimple_stmt_iterator gsi = gsi_for_stmt (call_stmt); + tree strcmp_decl = builtin_decl_explicit (BUILT_IN_STRCMP); + gcall *strcmp_call = gimple_build_call (strcmp_decl, 2, + arg0, arg1); + tree strcmp_lhs = make_ssa_name (integer_type_node); + gimple_call_set_lhs (strcmp_call, strcmp_lhs); + update_stmt (strcmp_call); + gsi_remove (&gsi, true); + gsi_insert_before (&gsi, strcmp_call, GSI_SAME_STMT); + + gsi = gsi_for_stmt (stmt); + tree zero = build_zero_cst (TREE_TYPE (strcmp_lhs)); + gassign *ga = gimple_build_assign (lhs, code, + strcmp_lhs, zero); + gsi_replace (&gsi, ga, false); + } + } + } + } + } + } else if (TREE_CODE (lhs) != SSA_NAME && !TREE_SIDE_EFFECTS (lhs)) { tree type = TREE_TYPE (lhs); @@ -2505,7 +2554,7 @@ const pass_data pass_data_strlen = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - 0, /* todo_flags_finish */ + TODO_update_ssa, /* todo_flags_finish */ }; class pass_strlen : public gimple_opt_pass