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: 839504 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-467389-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="yZjrrSyM"; 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 3ygQLp1k7wz9s03 for ; Mon, 20 Nov 2017 21:44:02 +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 :mime-version:from:date:message-id:subject:to:content-type; q= dns; s=default; b=mMtkrBboLre7HTAWxvtpwYy6ksR4Y2K556Ukfztni3kOOn d4ql1jH0ICSqROacfSl3Ih9ngfNqb68Qbd9qkudk0FjyFlTsylbxe3hGK7wpBcZK Cv3tWdicqvKxsH/Bp8RMvKNG2deWzeGheROTf1PcDGsgmRK75htbDnPHvKEy4= 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=yZjrrSyMVpDfPkiNSZLl CZ/4x0WmU4Yj14RInsnZ3WPOj6d1d160fMFVYoX4QA6gUWQtM8cZ12QxGAlT9JnA 7orht8rDPj2/+z/lwgQIjK8hExTc6fD/PSC2JQ74vTGWlgd3csIpfK3OqSbun3m0 eQ7zlHn+0rPSMkahBQetoDU= 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-Google-Smtp-Source: AGs4zMaL2zKQmW3iCuUYqlhtjsSGOxlYo8DewW1dXwQVH9Cz/pkdxnWnyxYRLAnAFS+Soo/CjDUHFIW50Wbg96XN/po= 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