From patchwork Wed Apr 9 20:07:21 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 28118 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-ie0-f198.google.com (mail-ie0-f198.google.com [209.85.223.198]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 30414202DD for ; Wed, 9 Apr 2014 20:07:44 +0000 (UTC) Received: by mail-ie0-f198.google.com with SMTP id to1sf13401171ieb.5 for ; Wed, 09 Apr 2014 13:07:43 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:mailing-list:precedence:list-id :list-unsubscribe:list-archive:list-post:list-help:sender :delivered-to:message-id:date:from:user-agent:mime-version:to :subject:x-original-sender:x-original-authentication-results :content-type; bh=oKOKdxZ0zYy/fNW4lOGWr3Uc/a0Fdyqt6kjVZ6/IpSo=; b=DSp5gKQDqaCVMVRSSob4cPx9APRE+2mbjgmyI002YA//9GwIC9ApLS9sOIi++UFnOT 2XuJSzjPSWVl2wl7PbZ3zFBjf0EgAq0cJwR5ObKARVOiAniNCrLJV3RXTv3Q9+WIi81l OFF4JKJv8uj+JtNmq+Cbv+WHrHEcoXHl75f1J4ygcmVn+07yt6NA4M1EhAmxjqrolllA cO5uNQI//XQ5Rx/Mi3ZgoCTwEv7KN8T4I1l8iAXTZbu5qokzvrnQSgo4jDbmoibU1H+M DnLODFxlLslqqPCG3wfiLgZTKeRfqtKeOCukFLQ6wHZdqaQIzBSGbU05rRHhRIw9NP4g ksaA== X-Gm-Message-State: ALoCoQmPiG7ohIi3xWXGlKyjwvjTfs+7ComZ4yI+Nbevjcp0s63p4nVO/dvQwCV4L1299/ZxAPPl X-Received: by 10.182.108.136 with SMTP id hk8mr5996572obb.11.1397074063434; Wed, 09 Apr 2014 13:07:43 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.140.27.138 with SMTP id 10ls880752qgx.52.gmail; Wed, 09 Apr 2014 13:07:43 -0700 (PDT) X-Received: by 10.58.96.36 with SMTP id dp4mr10306188veb.21.1397074063262; Wed, 09 Apr 2014 13:07:43 -0700 (PDT) Received: from mail-ve0-x22a.google.com (mail-ve0-x22a.google.com [2607:f8b0:400c:c01::22a]) by mx.google.com with ESMTPS id kj3si318324vdb.123.2014.04.09.13.07.43 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 09 Apr 2014 13:07:43 -0700 (PDT) Received-SPF: neutral (google.com: 2607:f8b0:400c:c01::22a is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) client-ip=2607:f8b0:400c:c01::22a; Received: by mail-ve0-f170.google.com with SMTP id pa12so2657988veb.1 for ; Wed, 09 Apr 2014 13:07:43 -0700 (PDT) X-Received: by 10.221.34.7 with SMTP id sq7mr10526281vcb.5.1397074063165; Wed, 09 Apr 2014 13:07:43 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.220.12.8 with SMTP id v8csp357877vcv; Wed, 9 Apr 2014 13:07:42 -0700 (PDT) X-Received: by 10.66.233.169 with SMTP id tx9mr14400769pac.7.1397074062127; Wed, 09 Apr 2014 13:07:42 -0700 (PDT) Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id td10si928877pac.386.2014.04.09.13.07.41 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 09 Apr 2014 13:07:42 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-364747-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Received: (qmail 3369 invoked by alias); 9 Apr 2014 20:07:30 -0000 Mailing-List: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org Precedence: list 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 3359 invoked by uid 89); 9 Apr 2014 20:07:30 -0000 X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-pd0-f176.google.com Received: from mail-pd0-f176.google.com (HELO mail-pd0-f176.google.com) (209.85.192.176) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Wed, 09 Apr 2014 20:07:28 +0000 Received: by mail-pd0-f176.google.com with SMTP id r10so2883632pdi.35 for ; Wed, 09 Apr 2014 13:07:26 -0700 (PDT) X-Received: by 10.66.150.228 with SMTP id ul4mr14750516pab.16.1397074046703; Wed, 09 Apr 2014 13:07:26 -0700 (PDT) Received: from [10.1.1.2] (58-6-183-210.dyn.iinet.net.au. [58.6.183.210]) by mx.google.com with ESMTPSA id ci4sm4347921pbb.50.2014.04.09.13.07.24 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 09 Apr 2014 13:07:25 -0700 (PDT) Message-ID: <5345A879.5070406@linaro.org> Date: Thu, 10 Apr 2014 06:07:21 +1000 From: Kugan User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 MIME-Version: 1.0 To: "gcc-patches@gcc.gnu.org" Subject: [VRP][PATCH] Improve value range for loop index X-IsSubscribed: yes X-Original-Sender: kugan.vivekanandarajah@linaro.org X-Original-Authentication-Results: mx.google.com; spf=neutral (google.com: 2607:f8b0:400c:c01::22a is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org; dkim=pass header.i=@gcc.gnu.org X-Google-Group-Id: 836684582541 Value range propagation simplifies convergence in vrp_visit_phi_node by setting minimum to TYPE_MIN when the computed minimum is smaller than the previous minimum. This can however result in pessimistic value ranges in some cases. for example, unsigned int i; for (i = 0; i < 8; i++) { .... } # ivtmp_19 = PHI ... : ivtmp_17 = ivtmp_19 - 1; if (ivtmp_17 != 0) .... goto ; min value of ivtmp_19 is simplified to 0 (in tree-vrp.c:8465) where as it should have been 1. This prevents correct value ranges being calculated for ivtmp_17 in the example. We should be able to see the step (the difference from previous minimum to computed minimum) and if there is scope for more iterations (computed minimum is greater than step), and then we should be able set minimum to do one more iteration and converge to the right minimum value. Attached patch fixes this. Is this OK for stage-1? Bootstrapped and regression tested on X86_64-unknown-linux-gnu with no new regressions. Thanks, Kugan gcc/ +2014-04-09 Kugan Vivekanandarajah + + * tree-vrp.c (vrp_visit_phi_node) : Improve value ranges of loop + index when simplifying convergence towards minimum. + gcc/testsuite +2014-04-09 Kugan Vivekanandarajah + + * gcc.dg/tree-ssa/vrp91.c: New test + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c index e69de29..26e857c 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-S -O2 -fdump-tree-vrp2" } */ + +unsigned short data; +void foo () +{ + unsigned char x16; + unsigned int i; + for (i = 0; i < 8; i++) + { + x16 = data & 1; + data >>= 1; + if (x16 == 1) + { + data ^= 0x4; + } + data >>= 1; + } +} + +/* { dg-final { scan-tree-dump "\\\[0, 7\\\]" "vrp2" } } */ +/* { dg-final { cleanup-tree-dump "vrp2" } } */ + diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 14f1526..c63f794 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -8461,7 +8461,30 @@ vrp_visit_phi_node (gimple phi) { if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)) || !vrp_var_may_overflow (lhs, phi)) - vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); + { + tree step = ((cmp_min > 0) && TYPE_UNSIGNED (TREE_TYPE (lhs))) ? + int_const_binop (MINUS_EXPR, lhs_vr->min, vr_result.min) : NULL_TREE; + + /* If the type minimum is zero, while avoiding repeated + iterations, let us stop at step and let the iterations take + it to zero (if necessary) from there. This will improve + value ranges for cases like below, when the value range + for ivtemp_17 is [0, 7] and range for ivtmp_19 is [1, 8]. + + # ivtmp_19 = PHI + ... + : + ivtmp_17 = ivtmp_19 - 1; + if (ivtmp_17 != 0) + .... + goto ; + */ + if ((cmp_min > 0) && (TYPE_UNSIGNED (TREE_TYPE (lhs))) + && (tree_int_cst_compare (vr_result.min, step) != -1)) + vr_result.min = step; + else + vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)); + } else if (supports_overflow_infinity (TREE_TYPE (vr_result.min))) vr_result.min = negative_overflow_infinity (TREE_TYPE (vr_result.min));