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: 337928 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org 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 3A7F91400DD for ; Thu, 10 Apr 2014 06:07:37 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; q= dns; s=default; b=NX4VlBebwMCwjzg+VqQJPOAvgQaZ1oem0nhLD/Ixn0eKg2 e4FBV/Q4GsXEudrKMQfbUFIWDyMUwlnlSQyUZ9tYKl33vhAaQ4+Jg4ZMmsNHf7gn RNGuwsliBG002IGexIQ2VK+hTI4FlsjtiA9GNR6pja84SbjQeHdyhJgHo0tG4= 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 :message-id:date:from:mime-version:to:subject:content-type; s= default; bh=x5nKYhyBsdM+UmgUavSxlQPqnlQ=; b=Ig7CkHm4/6QepD6f1oOZ zO8rHkEG17/ECz6DjAwdkQHXUG9ME0I4QDqblemRmx2ovJ6Mm/IltcNNoJBuCxU5 80eqf9IeUQCSbDMuA175avwR2hkUMLYtz8BAtrM8piZ4vh5rBDCV9bgd3FB4kyqs W5m6Ltbytj7ZsO83lNnmmBA= Received: (qmail 3369 invoked by alias); 9 Apr 2014 20:07: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 3359 invoked by uid 89); 9 Apr 2014 20:07:30 -0000 Authentication-Results: sourceware.org; auth=none 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-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to :subject:content-type; bh=oKOKdxZ0zYy/fNW4lOGWr3Uc/a0Fdyqt6kjVZ6/IpSo=; b=l/cl3j7xPsftVCf3EfOQc6osdEoRBFb4OE85d5UKv5DF5VXDTcUXJpubDQFAoeSARI JUSQLbKMwlxyVG0SV6O45tWnVl/VygWr8YjNAxemNitcvXzl77B31YTcIIxo1DxRu9B3 VZqccJlSLZNNumRXuaL53CfO7fbk5BQl4zMeZhDsLol6si4FuY3oF/T4nVIUXKwOP3YS hGNi7kackidPjmRWdhtxHutU4Cp2cS6YhRXEsTX9eK0PDCetUfaNn9MLbRY1LMurXJjV ZQvgSLzFtj3hYT37Eps4G322vRhlVMXjgv0i9W4SRhwWfgzJdZi4DyotgGRHhywRLnVj TAMQ== X-Gm-Message-State: ALoCoQnqi/RCFKXM10ojUPTfoCXm5K8U+klNhqUOfXYKtiwDD3+GWeaEFQ3L/T0EGEew8g+QTE/R 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 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));