From patchwork Mon Nov 20 10:43:49 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Prathamesh Kulkarni X-Patchwork-Id: 119267 Delivered-To: patch@linaro.org Received: by 10.140.22.164 with SMTP id 33csp3677595qgn; Mon, 20 Nov 2017 02:44:08 -0800 (PST) X-Google-Smtp-Source: AGs4zMaCoFrc21west5BNDOWeKFcMV5kNZk0bBCeeNOmiFaH6BUpAaywD2mFdDn8uEqr+GDRmdHJ X-Received: by 10.101.101.131 with SMTP id u3mr5853112pgv.76.1511174648211; Mon, 20 Nov 2017 02:44:08 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1511174648; cv=none; d=google.com; s=arc-20160816; b=Unu/2iyFpY3Y6BLOBciynwJuhNfbkc+1cZPqoFw0HeOUFqCf15tp5x1Ude3sRX5ah/ L7jejQy6jvGeED8J1bhy354LFi1RuC2tur/CBNS53xSqWAgJ6NAoQQ7us/Ixy1TZuRkF v3Hx1Ks1e8vhkuY9xSPZrZ8XW+1JG4ibfa5G7u3eeBscwPc+/7Rx7KGurxpRWbsSYo0n bjLqRaV4lN2ZFSno5I/eysTECMAU89beMRIDC/+xFdlxKKvZy5djDYSzbFUKsI31PzYp NdksOMWANbqcqSnHwTeDvaSmVgCsfOnf1AV+2KppRKbTKT1iNtn2hRSYI+lVRvgxTFk3 KeSw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:subject:message-id:date:from:mime-version:delivered-to:sender :list-help:list-post:list-archive:list-unsubscribe:list-id :precedence:mailing-list:dkim-signature:domainkey-signature :arc-authentication-results; bh=hBbWPHE7aKswZ3eHCU9vmIUrR8JmBodks34yOjbacTM=; b=UMQb9Otg4GokHU0h84K5o+TMrNGDokihNhezqwjc3S3JY9otwjb2ucasjkdm5epPEX dCFx1ZNXsbwM9lYYyeL1cq0PFmLlnxyIJyDBy9VTLk3t/LRQZnSLR1RsK88hC//v6tgz DD8fO+WI7vfAnj5o6uyc6TdedXPzC4Pg1XS7J8lsZEOtTwrS4jymPjLK+cqQ3nOOMF4r IzRCNk4LB4ol3QuCupNfioQ8coT7HaSJAjJVV3lRnEJ1SeRVDlNSYzJIp2BfH5ehruCc uPBSZuokRZmCMOUbJLBt8xjVgw6S5zPEfJYlTbBZH2awtJgDUawVr6s//ySarn9idY1Y Cz1A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=pzZYI3P/; spf=pass (google.com: domain of gcc-patches-return-467389-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-467389-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id l3si8713699pff.82.2017.11.20.02.44.07 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 20 Nov 2017 02:44:08 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-return-467389-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 header.s=default header.b=pzZYI3P/; spf=pass (google.com: domain of gcc-patches-return-467389-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-467389-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE sp=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=VyK9nSIyEOgAe+gFxw7dWytqE1enxIFA7tFcDauioVXown g7WFJAFNtXm61HYPGcnq+nltqPT5XmJsD9BkOcMAt+h8ERLKaNDAknjzzCFc+63U y0OpNAPxpPNTXFrhmPJy1dVjIqtNIVuo6pOuAQYWjoECp1/LQnFkNp+1gC/Wg= 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=djnQFX6PcaF15LWD2xd8iIlTQgc=; b=pzZYI3P/kyymj23foD8P rqJzJ76OmPGO1cyKRIh70K4/7ZtZ9u14yd9plATBpWBl4BmZxxEQ0RWM57rqA6au yIhINfuh0rVksO32J8wBTBmpCL8mnwyqldc1brf3zfUU2bQ76MaTI0hckObll2At 0qkbNant88KJmO9xCMXKpUo= Received: (qmail 94430 invoked by alias); 20 Nov 2017 10:43:55 -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 94418 invoked by uid 89); 20 Nov 2017 10:43:54 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.9 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KB_WAM_FROM_NAME_SINGLEWORD, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=HX-Received:10.28.10.147 X-HELO: mail-wm0-f46.google.com Received: from mail-wm0-f46.google.com (HELO mail-wm0-f46.google.com) (74.125.82.46) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 20 Nov 2017 10:43:53 +0000 Received: by mail-wm0-f46.google.com with SMTP id x63so5004051wmf.4 for ; Mon, 20 Nov 2017 02:43:52 -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:from:date:message-id:subject:to; bh=q6eawrClfcURQ2N3cTqp4+sLbYhKCIeZ+pQ90fESWpQ=; b=b86SQE2UR1FJtxJA1tzT/kQ4RQIARxGeDgx18gS5dI9CFYejTXhP0dAvS/fTnsW6iN xeLs1bA2BrkaADHdjXuraVAgwPTBsVLfjX2kOiw6fPdEoxv7qtgwjM4ltLx9jXvAiq+7 m2i1cU5fmFj5RArrLwAOxjjxX0bxfL+Xj3EKEm2OaSbRuIKSgVl+/amiz7olAsAVF3tI /7FzFkepl/QRfQpk5/0UATJYBb8T+RRUiaO26zZoW8G2763vv6nt4h1kVkm3cmrDmMDy ZRC5foFZOe8DJV6CJglioEjTXLIwpB/SdGDDwWoOvf2ZyKPkGTfYmlDe7GS/syr3Gqbt qFIQ== X-Gm-Message-State: AJaThX4x+8CqIpCHkBWL+EBbN8LIXbA+c9IzsTbVOX4VfVg5jbDDqYQ9 rwx90Z9WwnsXg9doumBEQLaeiCCoiWaqvnuxur0Kd+cD X-Received: by 10.28.10.147 with SMTP id 141mr8862111wmk.40.1511174629889; Mon, 20 Nov 2017 02:43:49 -0800 (PST) MIME-Version: 1.0 Received: by 10.223.131.129 with HTTP; Mon, 20 Nov 2017 02:43:49 -0800 (PST) From: Prathamesh Kulkarni Date: Mon, 20 Nov 2017 16:13:49 +0530 Message-ID: Subject: PR82665 - missing value range optimization for memchr To: gcc Patches X-IsSubscribed: yes Hi, The attached patch tries to fix PR82665 by adding value-range for 'n' to [0, PTRDIFF_MAX - 1] in the following case: def = memchr(arg, 0, sz); n = def - arg where def and arg are char *. I suppose it's safe to assume that if arg is char *, then memchr(arg, 0, sz) would return a non NULL pointer ? The patch could also be extended to handle more functions like memrchr, but I was wondering if it is in right direction ? Bootstrapped+tested on x86_64-unknown-linux-gnu and cross-tested on arm*-*-*, aarch64*-*-*. Thanks, Prathamesh diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr82665.c b/gcc/testsuite/gcc.dg/tree-ssa/pr82665.c new file mode 100644 index 00000000000..17be6ec4e4b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr82665.c @@ -0,0 +1,22 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +void f1 (char *p, __SIZE_TYPE__ sz) +{ + char *q = __builtin_memchr (p, 0, sz); + long n = q - p; + + if (n >= __PTRDIFF_MAX__) + __builtin_abort (); +} + +void f2 (unsigned char *p, __SIZE_TYPE__ sz) +{ + unsigned char *q = __builtin_memchr (p, 0, sz); + long n = q - p; + + if (n >= __PTRDIFF_MAX__) + __builtin_abort (); +} + +/* { dg-final { scan-tree-dump-times "memchr" 1 "optimized" } } */ diff --git a/gcc/vr-values.c b/gcc/vr-values.c index 3e760a378fc..ca9dca84ebc 100644 --- a/gcc/vr-values.c +++ b/gcc/vr-values.c @@ -773,6 +773,54 @@ vr_values::extract_range_from_binary_expr (value_range *vr, extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1); + /* Set value_range for n in following sequence: + def = __builtin_memchr (arg, 0, sz) + op0 = convert_expr def + op1 = convert_expr arg + n = op0 - op1 + Here the range for n can be set to [0, PTRDIFF_MAX - 1]. */ + + if (vr->type == VR_VARYING + && (code == MINUS_EXPR) + && (TREE_CODE (op0) == SSA_NAME) + && (TREE_CODE (op1) == SSA_NAME) + && INTEGRAL_TYPE_P (TREE_TYPE (op0)) + && INTEGRAL_TYPE_P (TREE_TYPE (op1))) + { + tree def = NULL_TREE; + tree arg = NULL_TREE; + + gassign *s = dyn_cast (SSA_NAME_DEF_STMT (op0)); + if (s && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (s))) + def = gimple_assign_rhs1 (s); + + s = dyn_cast (SSA_NAME_DEF_STMT (op1)); + if (s && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (s))) + arg = gimple_assign_rhs1 (s); + + gcall *call_stmt = NULL; + if (def && arg + && (TREE_CODE (def) == SSA_NAME) + && ((TREE_CODE (TREE_TYPE (def)) == POINTER_TYPE) + && (TREE_TYPE (TREE_TYPE (def)) == char_type_node)) + && (TREE_CODE (arg) == SSA_NAME) + && ((TREE_CODE (TREE_TYPE (arg)) == POINTER_TYPE) + && (TREE_TYPE (TREE_TYPE (arg)) == char_type_node)) + && (call_stmt = dyn_cast(SSA_NAME_DEF_STMT (def))) + && (gimple_call_combined_fn (call_stmt) == CFN_BUILT_IN_MEMCHR) + && operand_equal_p (def, gimple_call_lhs (call_stmt), 0) + && operand_equal_p (arg, gimple_call_arg (call_stmt, 0), 0) + && integer_zerop (gimple_call_arg (call_stmt, 1))) + { + tree max = vrp_val_max (ptrdiff_type_node); + wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max))); + tree range_min = build_zero_cst (expr_type); + tree range_max = wide_int_to_tree (expr_type, wmax - 1); + set_value_range (vr, VR_RANGE, range_min, range_max, NULL); + return; + } + } + /* Try harder for PLUS and MINUS if the range of one operand is symbolic and based on the other operand, for example if it was deduced from a symbolic comparison. When a bound of the range of the first operand