From patchwork Thu Dec 21 21:25:07 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Qing Zhao X-Patchwork-Id: 852146 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-469751-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="wJjjt1Cg"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3z2lK74zQBz9s84 for ; Fri, 22 Dec 2017 08:34:34 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; q=dns; s= default; b=UuVpYmI7EHn4ioYzdpsoal1SegWrDJ4YlYpQyABOsgXpWKQAXQlS8 /u4xdXueuto/BewHsVnI+WnO4SuVzIlZCR31HNTJNhD4lQQS+joKYAMHdaqD29j0 XsRMR1nMKmnF6JQF4/TD2q5XDerlnrPuyzdGJdDb1rr6oVGrHXU4fM= 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 :content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; s=default; bh=bko+zjtES3JK+j1EKeyxT/vAAV8=; b=wJjjt1CgHnDyxlPSTSIHoQku1QXH my8GeEGN9XHxje4ARTchXvWw169ntzLVkGnrV53oEuTQvY9JxX0TtNs8JuVKMj2n XTnZlpxZZsPkF9eTrc9ed7mnx8RqA3tCJ05I87mvHVA3hbqczAuN4BpPTr8ePuUa 6L85BK5g/PNmX6o= Received: (qmail 57795 invoked by alias); 21 Dec 2017 21:34:25 -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 57777 invoked by uid 89); 21 Dec 2017 21:34:24 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.4 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_NUMSUBJECT, SPF_PASS, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.2 spammy=H*r:sk:dhcp-10, Havent, Haven't X-HELO: aserp2120.oracle.com Received: from aserp2120.oracle.com (HELO aserp2120.oracle.com) (141.146.126.78) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 21 Dec 2017 21:34:21 +0000 Received: from pps.filterd (aserp2120.oracle.com [127.0.0.1]) by aserp2120.oracle.com (8.16.0.21/8.16.0.21) with SMTP id vBLLM4lA187596; Thu, 21 Dec 2017 21:34:18 GMT Received: from userv0021.oracle.com (userv0021.oracle.com [156.151.31.71]) by aserp2120.oracle.com with ESMTP id 2f0mps8439-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 21 Dec 2017 21:34:17 +0000 Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by userv0021.oracle.com (8.14.4/8.14.4) with ESMTP id vBLLP96C012149 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Thu, 21 Dec 2017 21:25:09 GMT Received: from abhmp0008.oracle.com (abhmp0008.oracle.com [141.146.116.14]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id vBLLP8qY021787; Thu, 21 Dec 2017 21:25:09 GMT Received: from dhcp-10-154-102-7.vpn.oracle.com (/10.154.102.7) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Thu, 21 Dec 2017 13:25:08 -0800 Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\)) Subject: [PATCH][Middle-end][version 2]2nd patch of PR78809 and PR83026 From: Qing Zhao In-Reply-To: <20171214204542.GB2353@tucnak> Date: Thu, 21 Dec 2017 15:25:07 -0600 Cc: gcc-patches , jeff Law , richard Biener Message-Id: References: <20171214204542.GB2353@tucnak> To: Jakub Jelinek X-Proofpoint-Virus-Version: vendor=nai engine=5900 definitions=8752 signatures=668651 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=3 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1711220000 definitions=main-1712210285 X-IsSubscribed: yes Hi, I updated my patch based on all your comments. the major changes are the following: 1. replace the candidate calls with __builtin_str(n)cmp_eq instead of __builtin_memcmp_eq; in builtins.c, when expanding the new __builtin_str(n)cmp_eq call, expand them first as __builtin_memcmp_eq, if Not succeed, change the call back to __builtin_str(n)cmp. 2. change the call to “get_range_strlen” with “compute_objsize”. 3. add the missing case for equality checking with zero; 4. adjust the new testing case for PR83026; add a new testing case for the missing case added in 3. 5. update “uhwi” to “shwi” for where it needs; 6. some other minor format changes. the changes are retested on x86 and aarch64, bootstrapped and regression tested. no issue. Okay for trunk? thanks. Qing Please see the updated patch: gcc/ChangeLog: +2017-12-21 Qing Zhao + + PR middle-end/78809 + PR middle-end/83026 + * builtins.c (expand_builtin): Add the handling of BUILT_IN_STRCMP_EQ + and BUILT_IN_STRNCMP_EQ. + * builtins.def: Add new builtins BUILT_IN_STRCMP_EQ and + BUILT_IN_STRNCMP_EQ. + * tree-ssa-strlen.c (compute_string_length): New function. + (handle_builtin_string_cmp): New function to handle calls to + string compare functions. + (strlen_optimize_stmt): Add handling to builtin string compare + calls. + * tree.c (build_common_builtin_nodes): Add new defines of + BUILT_IN_STRNCMP_EQ and BUILT_IN_STRCMP_EQ. + gcc/testsuite/ChangeLog +2017-12-21 Qing Zhao + + PR middle-end/78809 + * gcc.dg/strcmpopt_2.c: New testcase. + * gcc.dg/strcmpopt_3.c: New testcase. + + PR middle-end/83026 + * gcc.dg/strcmpopt_3.c: New testcase. + --- gcc/builtins.c | 33 ++++++ gcc/builtins.def | 5 + gcc/testsuite/gcc.dg/strcmpopt_2.c | 67 ++++++++++++ gcc/testsuite/gcc.dg/strcmpopt_3.c | 31 ++++++ gcc/testsuite/gcc.dg/strcmpopt_4.c | 16 +++ gcc/tree-ssa-strlen.c | 215 +++++++++++++++++++++++++++++++++++++ gcc/tree.c | 8 ++ 7 files changed, 375 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/strcmpopt_2.c create mode 100644 gcc/testsuite/gcc.dg/strcmpopt_3.c create mode 100644 gcc/testsuite/gcc.dg/strcmpopt_4.c diff --git a/gcc/builtins.c b/gcc/builtins.c index 6b25253..a5f6885 100644 --- a/gcc/builtins.c +++ b/gcc/builtins.c @@ -6953,12 +6953,45 @@ expand_builtin (tree exp, rtx target, rtx subtarget, machine_mode mode, return target; break; + /* expand it as BUILT_IN_MEMCMP_EQ first. If not successful, change it + back to a BUILT_IN_STRCMP. Remember to delete the 3rd paramater + when changing it to a strcmp call. */ + case BUILT_IN_STRCMP_EQ: + target = expand_builtin_memcmp (exp, target, true); + if (target) + return target; + + /* change this call back to a BUILT_IN_STRCMP. */ + TREE_OPERAND (exp, 1) + = build_fold_addr_expr (builtin_decl_explicit (BUILT_IN_STRCMP)); + + /* delete the last parameter. */ + unsigned int i; + vec *arg_vec; + vec_alloc (arg_vec, 2); + for (i = 0; i < 2; i++) + arg_vec->quick_push (CALL_EXPR_ARG (exp, i)); + exp = build_call_vec (TREE_TYPE (exp), CALL_EXPR_FN (exp), arg_vec); + /* FALLTHROUGH */ + case BUILT_IN_STRCMP: target = expand_builtin_strcmp (exp, target); if (target) return target; break; + /* expand it as BUILT_IN_MEMCMP_EQ first. If not successful, change it + back to a BUILT_IN_STRNCMP. */ + case BUILT_IN_STRNCMP_EQ: + target = expand_builtin_memcmp (exp, target, true); + if (target) + return target; + + /* change it back to a BUILT_IN_STRNCMP. */ + TREE_OPERAND (exp, 1) + = build_fold_addr_expr (builtin_decl_explicit (BUILT_IN_STRNCMP)); + /* FALLTHROUGH */ + case BUILT_IN_STRNCMP: target = expand_builtin_strncmp (exp, target, mode); if (target) diff --git a/gcc/builtins.def b/gcc/builtins.def index 2281021..9eb79fd 100644 --- a/gcc/builtins.def +++ b/gcc/builtins.def @@ -949,6 +949,11 @@ DEF_BUILTIN_STUB (BUILT_IN_ALLOCA_WITH_ALIGN_AND_MAX, "__builtin_alloca_with_ali equality with zero. */ DEF_BUILTIN_STUB (BUILT_IN_MEMCMP_EQ, "__builtin_memcmp_eq") +/* An internal version of strcmp/strncmp, used when the result is only + tested for equality with zero. */ +DEF_BUILTIN_STUB (BUILT_IN_STRCMP_EQ, "__builtin_strcmp_eq") +DEF_BUILTIN_STUB (BUILT_IN_STRNCMP_EQ, "__builtin_strncmp_eq") + /* Object size checking builtins. */ DEF_GCC_BUILTIN (BUILT_IN_OBJECT_SIZE, "object_size", BT_FN_SIZE_CONST_PTR_INT, ATTR_PURE_NOTHROW_LEAF_LIST) DEF_EXT_LIB_BUILTIN_CHKP (BUILT_IN_MEMCPY_CHK, "__memcpy_chk", BT_FN_PTR_PTR_CONST_PTR_SIZE_SIZE, ATTR_RET1_NOTHROW_NONNULL_LEAF) diff --git a/gcc/testsuite/gcc.dg/strcmpopt_2.c b/gcc/testsuite/gcc.dg/strcmpopt_2.c new file mode 100644 index 0000000..0131b8f --- /dev/null +++ b/gcc/testsuite/gcc.dg/strcmpopt_2.c @@ -0,0 +1,67 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +char s[100] = {'a','b','c','d'}; +typedef struct { char s[8]; int x; } S; + +__attribute__ ((noinline)) int +f1 (S *s) +{ + return __builtin_strcmp (s->s, "abc") != 0; +} + +__attribute__ ((noinline)) int +f2 (void) +{ + return __builtin_strcmp (s, "abc") != 0; +} + +__attribute__ ((noinline)) int +f3 (S *s) +{ + return __builtin_strcmp ("abc", s->s) != 0; +} + +__attribute__ ((noinline)) int +f4 (void) +{ + return __builtin_strcmp ("abc", s) != 0; +} + +__attribute__ ((noinline)) int +f5 (S *s) +{ + return __builtin_strncmp (s->s, "abc", 3) != 0; +} + +__attribute__ ((noinline)) int +f6 (void) +{ + return __builtin_strncmp (s, "abc", 2) != 0; +} + +__attribute__ ((noinline)) int +f7 (S *s) +{ + return __builtin_strncmp ("abc", s->s, 3) != 0; +} + +__attribute__ ((noinline)) int +f8 (void) +{ + return __builtin_strncmp ("abc", s, 2) != 0; +} + +int main (void) +{ + S ss = {{'a','b','c'}, 2}; + + if (f1 (&ss) != 0 || f2 () != 1 || f3 (&ss) != 0 || + f4 () != 1 || f5 (&ss) != 0 || f6 () != 0 || + f7 (&ss) != 0 || f8 () != 0) + __builtin_abort (); + + return 0; +} + +/* { dg-final { scan-tree-dump-times "cmp_eq \\(" 8 "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strcmpopt_3.c b/gcc/testsuite/gcc.dg/strcmpopt_3.c new file mode 100644 index 0000000..86a0d7a --- /dev/null +++ b/gcc/testsuite/gcc.dg/strcmpopt_3.c @@ -0,0 +1,31 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +__attribute__ ((noinline)) int +f1 (void) +{ + char *s0= "abcd"; + char s[8]; + __builtin_strcpy (s, s0); + return __builtin_strcmp(s, "abc") != 0; +} + +__attribute__ ((noinline)) int +f2 (void) +{ + char *s0 = "ab"; + char s[8]; + __builtin_strcpy (s, s0); + return __builtin_strcmp("abc", s) != 0; +} + +int main (void) +{ + if (f1 () != 1 + || f2 () != 1) + __builtin_abort (); + + return 0; +} + +/* { dg-final { scan-tree-dump-times "strcmp" 0 "strlen" } } */ diff --git a/gcc/testsuite/gcc.dg/strcmpopt_4.c b/gcc/testsuite/gcc.dg/strcmpopt_4.c new file mode 100644 index 0000000..d727bc3 --- /dev/null +++ b/gcc/testsuite/gcc.dg/strcmpopt_4.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-strlen" } */ + +typedef struct { char s[8]; int x; } S; +extern int max_i; + +int +f1 (S * s) +{ + int result, i; + for (i = 0; i < max_i; i++) + result += __builtin_strcmp (s->s, "abc") != 0 ? 2 : 1; + return result; +} + +/* { dg-final { scan-tree-dump-times "cmp_eq \\(" 1 "strlen" } } */ diff --git a/gcc/tree-ssa-strlen.c b/gcc/tree-ssa-strlen.c index 94f20ef..57563ef 100644 --- a/gcc/tree-ssa-strlen.c +++ b/gcc/tree-ssa-strlen.c @@ -2540,6 +2540,216 @@ handle_builtin_memcmp (gimple_stmt_iterator *gsi) return false; } +/* Given an index to the strinfo vector, compute the string length for the + corresponding string. Return -1 when unknown. */ + +static HOST_WIDE_INT +compute_string_length (int idx) +{ + HOST_WIDE_INT string_leni = -1; + gcc_assert (idx != 0); + + if (idx < 0) + string_leni = ~idx; + else + { + strinfo *si = get_strinfo (idx); + if (si) + { + tree const_string_len = get_string_length (si); + if (const_string_len && tree_fits_shwi_p (const_string_len)) + string_leni = tree_to_shwi (const_string_len); + } + } + + if (string_leni < 0) + return -1; + + return string_leni; +} + +/* Handle a call to strcmp or strncmp. When the result is ONLY used to do + equality test against zero: + + A. When both arguments are constant strings and it's a strcmp: + * if the length of the strings are NOT equal, we can safely fold the call + to a non-zero value. + * otherwise, do nothing now. + + B. When one of the arguments is constant string, try to replace the call with + a __builtin_str(n)cmp_eq call where possible, i.e: + + strncmp (s, STR, C) (!)= 0 in which, s is a pointer to a string, STR is a + constant string, C is a constant. + if (C <= strlen(STR) && sizeof_array(s) > C) + { + replace this call with + strncmp_eq (s, STR, C) (!)= 0 + } + if (C > strlen(STR) + { + it can be safely treated as a call to strcmp (s, STR) (!)= 0 + can handled by the following strcmp. + } + + strcmp (s, STR) (!)= 0 in which, s is a pointer to a string, STR is a + constant string. + if (sizeof_array(s) > strlen(STR)) + { + replace this call with + strcmp_eq (s, STR, strlen(STR)+1) (!)= 0 + } + */ + +static bool +handle_builtin_string_cmp (gimple_stmt_iterator *gsi) +{ + gcall *stmt = as_a (gsi_stmt (*gsi)); + tree res = gimple_call_lhs (stmt); + use_operand_p use_p; + imm_use_iterator iter; + tree arg1 = gimple_call_arg (stmt, 0); + tree arg2 = gimple_call_arg (stmt, 1); + int idx1 = get_stridx (arg1); + int idx2 = get_stridx (arg2); + HOST_WIDE_INT length = -1; + bool is_ncmp = false; + + if (!res) + return true; + + /* When both arguments are unknown, do nothing. */ + if (idx1 == 0 && idx2 == 0) + return true; + + /* Handle strncmp function. */ + if (gimple_call_num_args (stmt) == 3) + { + tree len = gimple_call_arg (stmt, 2); + if (tree_fits_shwi_p (len)) + length = tree_to_shwi (len); + + is_ncmp = true; + } + + /* For strncmp, if the length argument is NOT known, do nothing. */ + if (is_ncmp && length < 0) + return true; + + /* When the result is ONLY used to do equality test against zero. */ + FOR_EACH_IMM_USE_FAST (use_p, iter, res) + { + gimple *use_stmt = USE_STMT (use_p); + + if (is_gimple_debug (use_stmt)) + continue; + if (gimple_code (use_stmt) == GIMPLE_ASSIGN) + { + tree_code code = gimple_assign_rhs_code (use_stmt); + if (code == COND_EXPR) + { + tree cond_expr = gimple_assign_rhs1 (use_stmt); + if ((TREE_CODE (cond_expr) != EQ_EXPR + && (TREE_CODE (cond_expr) != NE_EXPR)) + || !integer_zerop (TREE_OPERAND (cond_expr, 1))) + return true; + } + else if (code == EQ_EXPR || code == NE_EXPR) + { + if (!integer_zerop (gimple_assign_rhs2 (use_stmt))) + return true; + } + else + return true; + } + else if (gimple_code (use_stmt) == GIMPLE_COND) + { + tree_code code = gimple_cond_code (use_stmt); + if ((code != EQ_EXPR && code != NE_EXPR) + || !integer_zerop (gimple_cond_rhs (use_stmt))) + return true; + } + else + return true; + } + + /* When both arguments are known, and their strlens are unequal, we can + safely fold the call to a non-zero value for strcmp; + othewise, do nothing now. */ + if (idx1 != 0 && idx2 != 0) + { + HOST_WIDE_INT const_string_leni1 = compute_string_length (idx1); + HOST_WIDE_INT const_string_leni2 = compute_string_length (idx2); + + if (!is_ncmp + && const_string_leni1 != -1 + && const_string_leni2 != -1 + && const_string_leni1 != const_string_leni2) + { + replace_call_with_value (gsi, integer_one_node); + return false; + } + return true; + } + + /* When one of args is constant string. */ + tree var_string = NULL_TREE; + HOST_WIDE_INT const_string_leni = -1; + + if (idx1) + { + const_string_leni = compute_string_length (idx1); + var_string = arg2; + } + else + { + gcc_checking_assert (idx2); + const_string_leni = compute_string_length (idx2); + var_string = arg1; + } + + if (const_string_leni < 0) + return true; + + unsigned HOST_WIDE_INT var_sizei = 0; + /* try to determine the minimum size of the object pointed by var_string. */ + tree size = compute_objsize (var_string, 2); + + if (!size) + return true; + + if (tree_fits_uhwi_p (size)) + var_sizei = tree_to_uhwi (size); + + if (var_sizei == 0) + return true; + + /* For strncmp, if length > const_string_leni , this call can be safely + transformed to a strcmp. */ + if (is_ncmp && length > const_string_leni) + is_ncmp = false; + + unsigned HOST_WIDE_INT final_length + = is_ncmp ? length : const_string_leni + 1; + + /* Replace strcmp or strncmp with the corresponding str(n)cmp_eq. */ + if (var_sizei > final_length) + { + tree fn + = (is_ncmp + ? builtin_decl_implicit (BUILT_IN_STRNCMP_EQ) + : builtin_decl_implicit (BUILT_IN_STRCMP_EQ)); + if (!fn) + return true; + tree const_string_len = build_int_cst (size_type_node, final_length); + update_gimple_call (gsi, fn, 3, arg1, arg2, const_string_len); + } + else + return true; + + return false; +} + /* Handle a POINTER_PLUS_EXPR statement. For p = "abcd" + 2; compute associated length, or if p = q + off is pointing to a '\0' character of a string, call @@ -2939,6 +3149,11 @@ strlen_optimize_stmt (gimple_stmt_iterator *gsi) if (!handle_builtin_memcmp (gsi)) return false; break; + case BUILT_IN_STRCMP: + case BUILT_IN_STRNCMP: + if (!handle_builtin_string_cmp (gsi)) + return false; + break; default: break; } diff --git a/gcc/tree.c b/gcc/tree.c index ed1852b..e23b3cd 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -10047,6 +10047,14 @@ build_common_builtin_nodes (void) "__builtin_memcmp_eq", ECF_PURE | ECF_NOTHROW | ECF_LEAF); + local_define_builtin ("__builtin_strncmp_eq", ftype, BUILT_IN_STRNCMP_EQ, + "__builtin_strncmp_eq", + ECF_PURE | ECF_NOTHROW | ECF_LEAF); + + local_define_builtin ("__builtin_strcmp_eq", ftype, BUILT_IN_STRCMP_EQ, + "__builtin_strcmp_eq", + ECF_PURE | ECF_NOTHROW | ECF_LEAF); + /* If there's a possibility that we might use the ARM EABI, build the alternate __cxa_end_cleanup node used to resume from C++. */ if (targetm.arm_eabi_unwinder)