From patchwork Wed Jul 25 10:21:55 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marc Glisse X-Patchwork-Id: 173134 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]) by ozlabs.org (Postfix) with SMTP id 5CCD82C008A for ; Wed, 25 Jul 2012 20:22:19 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1343816540; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Date:From:To:Subject:Message-ID:User-Agent:MIME-Version: Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=Zur02sn Cz1E6k7Y2vEQIQnvfxnQ=; b=jJEY1PVJE5Sg4xS99KcmqGkqOV0Ks2aIdXt3+xp xycBo0afREH694bUOpljBZbmQDYgWbOLX+v53xtknqK3f9ICNVZ4pWBD+1trlhdx VhRd7EWrlzAnfFj6nLLNGnK4QO+a5xwLAieLD4WPh9mDMGz2Eip/4a8WXrWFMSgj Y8uY= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Date:From:To:Subject:Message-ID:User-Agent:MIME-Version:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=FR4DWvU1tRebroLUrtYzI0gvkG9Yd6UCajXoSaeXl1JV8HnKW3mltsgbsZfu6q yd+yZlGVnjTfsgHY8E3TVeeSpja387+rn6ySOmOXBJAIMaHErJHJNM7r+9w73xsr GZOSQCErF5AvSwA4BUNH2SkJFqb4FXPwfpWJ6pYA2HOTA=; Received: (qmail 1545 invoked by alias); 25 Jul 2012 10:22:15 -0000 Received: (qmail 1535 invoked by uid 22791); 25 Jul 2012 10:22:13 -0000 X-SWARE-Spam-Status: No, hits=-5.6 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_HI, SUBJ_ALL_CAPS, TW_OV, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail1-relais-roc.national.inria.fr (HELO mail1-relais-roc.national.inria.fr) (192.134.164.82) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 25 Jul 2012 10:21:58 +0000 Received: from stedding.saclay.inria.fr ([193.55.250.194]) by mail1-relais-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES128-SHA; 25 Jul 2012 12:21:55 +0200 Received: from glisse (helo=localhost) by stedding.saclay.inria.fr with local-esmtp (Exim 4.80) (envelope-from ) id 1Styj5-0008FY-IG for gcc-patches@gcc.gnu.org; Wed, 25 Jul 2012 12:21:55 +0200 Date: Wed, 25 Jul 2012 12:21:55 +0200 (CEST) From: Marc Glisse To: gcc-patches@gcc.gnu.org Subject: VRP PLUS/MINUS_EXPR Message-ID: User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) MIME-Version: 1.0 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 Hello, here is a slight improvement to VRP for sum and difference of intervals. There are some things I left because I didn't understand them enough: * range_int_cst_p (&vr0): I thought it was always true by that time, but it isn't obvious * TYPE_PRECISION (expr_type) <= HOST_BITS_PER_DOUBLE_INT: the __int256 patch scared me (though I would love to have larger types, especially with a proper range analysis to use only 2 or 3 of the 4 64-bit integers that make up an __int256 when it is enough, see PR 53100 for the __int128 version) * when is the value range of a type smaller than the one given by its precision? Is it for enum? 2012-07-25 Marc Glisse PR tree-optimization/30318 * tree-vrp.c (extract_range_from_binary_expr_1) [PLUS_EXPR]: Handle __int128. [MINUS_EXPR] merge with PLUS_EXPR. bootstrapped just c and c++ and ran the testsuite with no new regression. Index: tree-vrp.c =================================================================== --- tree-vrp.c (revision 189779) +++ tree-vrp.c (working copy) @@ -2345,157 +2345,194 @@ extract_range_from_binary_expr_1 (value_ set_value_range_to_varying (vr); } else set_value_range_to_varying (vr); return; } /* For integer ranges, apply the operation to each end of the range and see what we end up with. */ - if (code == PLUS_EXPR) + if (code == PLUS_EXPR || code == MINUS_EXPR) { /* If we have a PLUS_EXPR with two VR_RANGE integer constant ranges compute the precise range for such case if possible. */ if (range_int_cst_p (&vr0) && range_int_cst_p (&vr1) - /* We attempt to do infinite precision signed integer arithmetic, - thus we need two more bits than the possibly unsigned inputs. */ - && TYPE_PRECISION (expr_type) < HOST_BITS_PER_DOUBLE_INT - 1) + /* We need as many bits as the possibly unsigned inputs. */ + && TYPE_PRECISION (expr_type) <= HOST_BITS_PER_DOUBLE_INT) { double_int min0 = tree_to_double_int (vr0.min); double_int max0 = tree_to_double_int (vr0.max); double_int min1 = tree_to_double_int (vr1.min); double_int max1 = tree_to_double_int (vr1.max); bool uns = TYPE_UNSIGNED (expr_type); double_int type_min = double_int_min_value (TYPE_PRECISION (expr_type), uns); double_int type_max = double_int_max_value (TYPE_PRECISION (expr_type), uns); double_int dmin, dmax; + int min_ovf = 0; + int max_ovf = 0; - dmin = double_int_add (min0, min1); - dmax = double_int_add (max0, max1); + if (code == PLUS_EXPR) + { + dmin = double_int_add (min0, min1); + dmax = double_int_add (max0, max1); + + /* Check for overflow in double_int. */ + if (double_int_cmp (min1, double_int_zero, uns) + != double_int_cmp (dmin, min0, uns)) + min_ovf = double_int_cmp (min0, dmin, uns); + if (double_int_cmp (max1, double_int_zero, uns) + != double_int_cmp (dmax, max0, uns)) + max_ovf = double_int_cmp (max0, dmax, uns); + } + else /* if (code == MINUS_EXPR) */ + { + dmin = double_int_sub (min0, max1); + dmax = double_int_sub (max0, min1); + + if (double_int_cmp (double_int_zero, max1, uns) + != double_int_cmp (dmin, min0, uns)) + min_ovf = double_int_cmp (min0, max1, uns); + if (double_int_cmp (double_int_zero, min1, uns) + != double_int_cmp (dmax, max0, uns)) + max_ovf = double_int_cmp (max0, min1, uns); + } + + /* For non-wrapping arithmetic look at possibly smaller + value-ranges of the type. */ + if (!TYPE_OVERFLOW_WRAPS (expr_type)) + { + if (vrp_val_min (expr_type)) + type_min = tree_to_double_int (vrp_val_min (expr_type)); + if (vrp_val_max (expr_type)) + type_max = tree_to_double_int (vrp_val_max (expr_type)); + } + + /* Check for type overflow. */ + if (min_ovf == 0) + { + if (double_int_cmp (dmin, type_min, uns) == -1) + min_ovf = -1; + else if (double_int_cmp (dmin, type_max, uns) == 1) + min_ovf = 1; + } + if (max_ovf == 0) + { + if (double_int_cmp (dmax, type_min, uns) == -1) + max_ovf = -1; + else if (double_int_cmp (dmax, type_max, uns) == 1) + max_ovf = 1; + } if (TYPE_OVERFLOW_WRAPS (expr_type)) { /* If overflow wraps, truncate the values and adjust the range kind and bounds appropriately. */ double_int tmin = double_int_ext (dmin, TYPE_PRECISION (expr_type), uns); double_int tmax = double_int_ext (dmax, TYPE_PRECISION (expr_type), uns); - gcc_assert (double_int_scmp (dmin, dmax) <= 0); - if ((double_int_scmp (dmin, type_min) == -1 - && double_int_scmp (dmax, type_min) == -1) - || (double_int_scmp (dmin, type_max) == 1 - && double_int_scmp (dmax, type_max) == 1) - || (double_int_scmp (type_min, dmin) <= 0 - && double_int_scmp (dmax, type_max) <= 0)) + if (min_ovf == max_ovf) { /* No overflow or both overflow or underflow. The range kind stays VR_RANGE. */ min = double_int_to_tree (expr_type, tmin); max = double_int_to_tree (expr_type, tmax); } - else if (double_int_scmp (dmin, type_min) == -1 - && double_int_scmp (dmax, type_max) == 1) + else if (min_ovf == -1 + && max_ovf == 1) { /* Underflow and overflow, drop to VR_VARYING. */ set_value_range_to_varying (vr); return; } else { /* Min underflow or max overflow. The range kind changes to VR_ANTI_RANGE. */ double_int tem = tmin; - gcc_assert ((double_int_scmp (dmin, type_min) == -1 - && double_int_scmp (dmax, type_min) >= 0 - && double_int_scmp (dmax, type_max) <= 0) - || (double_int_scmp (dmax, type_max) == 1 - && double_int_scmp (dmin, type_min) >= 0 - && double_int_scmp (dmin, type_max) <= 0)); + gcc_assert ((min_ovf == -1 && max_ovf == 0) + || (max_ovf == 1 && min_ovf == 0)); type = VR_ANTI_RANGE; tmin = double_int_add (tmax, double_int_one); tmax = double_int_add (tem, double_int_minus_one); /* If the anti-range would cover nothing, drop to varying. Likewise if the anti-range bounds are outside of the types values. */ if (double_int_cmp (tmin, tmax, uns) > 0 || double_int_cmp (tmin, type_min, uns) < 0 || double_int_cmp (tmax, type_max, uns) > 0) { set_value_range_to_varying (vr); return; } min = double_int_to_tree (expr_type, tmin); max = double_int_to_tree (expr_type, tmax); } } else { - /* For non-wrapping arithmetic look at possibly smaller - value-ranges of the type. */ - if (vrp_val_min (expr_type)) - type_min = tree_to_double_int (vrp_val_min (expr_type)); - if (vrp_val_max (expr_type)) - type_max = tree_to_double_int (vrp_val_max (expr_type)); - /* If overflow does not wrap, saturate to the types min/max value. */ - if (double_int_scmp (dmin, type_min) == -1) + if (min_ovf == -1) { if (needs_overflow_infinity (expr_type) && supports_overflow_infinity (expr_type)) min = negative_overflow_infinity (expr_type); else min = double_int_to_tree (expr_type, type_min); } - else if (double_int_scmp (dmin, type_max) == 1) + else if (min_ovf == 1) { if (needs_overflow_infinity (expr_type) && supports_overflow_infinity (expr_type)) min = positive_overflow_infinity (expr_type); else min = double_int_to_tree (expr_type, type_max); } else min = double_int_to_tree (expr_type, dmin); - if (double_int_scmp (dmax, type_min) == -1) + if (max_ovf == -1) { if (needs_overflow_infinity (expr_type) && supports_overflow_infinity (expr_type)) max = negative_overflow_infinity (expr_type); else max = double_int_to_tree (expr_type, type_min); } - else if (double_int_scmp (dmax, type_max) == 1) + else if (max_ovf == 1) { if (needs_overflow_infinity (expr_type) && supports_overflow_infinity (expr_type)) max = positive_overflow_infinity (expr_type); else max = double_int_to_tree (expr_type, type_max); } else max = double_int_to_tree (expr_type, dmax); } if (needs_overflow_infinity (expr_type) && supports_overflow_infinity (expr_type)) { if (is_negative_overflow_infinity (vr0.min) - || is_negative_overflow_infinity (vr1.min)) + || (code == PLUS_EXPR + ? is_negative_overflow_infinity (vr1.min) + : is_positive_overflow_infinity (vr1.max))) min = negative_overflow_infinity (expr_type); if (is_positive_overflow_infinity (vr0.max) - || is_positive_overflow_infinity (vr1.max)) + || (code == PLUS_EXPR + ? is_positive_overflow_infinity (vr1.max) + : is_negative_overflow_infinity (vr1.min))) max = positive_overflow_infinity (expr_type); } } else { /* For other cases, for example if we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to VR_VARYING. It would take more effort to compute a precise range for such a case. ??? General even mixed range kind operations can be expressed by for example transforming ~[3, 5] + [1, 2] to range-only @@ -2710,40 +2747,20 @@ extract_range_from_binary_expr_1 (value_ max = vr1.max; max = int_const_binop (MINUS_EXPR, max, integer_one_node); /* If the dividend is non-negative the modulus will be non-negative as well. */ if (TYPE_UNSIGNED (expr_type) || value_range_nonnegative_p (&vr0)) min = build_int_cst (TREE_TYPE (max), 0); else min = fold_unary_to_constant (NEGATE_EXPR, expr_type, max); } - else if (code == MINUS_EXPR) - { - /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to - VR_VARYING. It would take more effort to compute a precise - range for such a case. For example, if we have op0 == 1 and - op1 == 1 with their ranges both being ~[0,0], we would have - op0 - op1 == 0, so we cannot claim that the difference is in - ~[0,0]. Note that we are guaranteed to have - vr0.type == vr1.type at this point. */ - if (vr0.type == VR_ANTI_RANGE) - { - set_value_range_to_varying (vr); - return; - } - - /* For MINUS_EXPR, apply the operation to the opposite ends of - each range. */ - min = vrp_int_const_binop (code, vr0.min, vr1.max); - max = vrp_int_const_binop (code, vr0.max, vr1.min); - } else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR) { bool int_cst_range0, int_cst_range1; double_int may_be_nonzero0, may_be_nonzero1; double_int must_be_nonzero0, must_be_nonzero1; int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0, &must_be_nonzero0); int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1, &must_be_nonzero1);