From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16269 invoked by alias); 29 Sep 2014 23:01:49 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 16196 invoked by uid 89); 29 Sep 2014 23:01:48 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.0 required=5.0 tests=AWL,BAYES_00,T_FILL_THIS_FORM_SHORT autolearn=ham version=3.3.2 X-HELO: smtp.eu.adacore.com Received: from mel.act-europe.fr (HELO smtp.eu.adacore.com) (194.98.77.210) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Mon, 29 Sep 2014 23:01:45 +0000 Received: from localhost (localhost [127.0.0.1]) by filtered-smtp.eu.adacore.com (Postfix) with ESMTP id A0FC4275AF5F; Tue, 30 Sep 2014 01:01:41 +0200 (CEST) Received: from smtp.eu.adacore.com ([127.0.0.1]) by localhost (smtp.eu.adacore.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Gh9hiPSHgd2g; Tue, 30 Sep 2014 01:01:41 +0200 (CEST) Received: from polaris.localnet (bon31-6-88-161-99-133.fbx.proxad.net [88.161.99.133]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by smtp.eu.adacore.com (Postfix) with ESMTPSA id 53E34274FA95; Tue, 30 Sep 2014 01:01:41 +0200 (CEST) From: Eric Botcazou To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: Re: [RFC] optimize x - y cmp 0 with undefined overflow Date: Mon, 29 Sep 2014 23:01:00 -0000 Message-ID: <1457137.5d3aUFRXh7@polaris> User-Agent: KMail/4.7.2 (Linux/3.1.10-1.29-desktop; KDE/4.7.2; x86_64; ; ) In-Reply-To: References: <1466969.VvFMuDKXoD@polaris> <3415746.rtOLWSx8DO@polaris> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="nextPart2346107.Kv9GypKaXs" Content-Transfer-Encoding: 7Bit X-SW-Source: 2014-09/txt/msg02590.txt.bz2 --nextPart2346107.Kv9GypKaXs Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" Content-length: 741 > Yeah, that sounds good to me. Here's what I have at last commited after testing on x86-64/Linux. 2014-09-29 Eric Botcazou * tree-vrp.c (get_single_symbol): New function. (build_symbolic_expr): Likewise. (symbolic_range_based_on_p): New predicate. (extract_range_from_binary_expr_1): Deal with single-symbolic ranges for PLUS and MINUS. Do not drop symbolic ranges at the end. (extract_range_from_binary_expr): Try harder for PLUS and MINUS if operand is symbolic and based on the other operand. 2014-09-29 Eric Botcazou * gcc.dg/tree-ssa/vrp94.c: New test. * gnat.dg/opt40.adb: Likewise. -- Eric Botcazou --nextPart2346107.Kv9GypKaXs Content-Disposition: attachment; filename="vrp_symbolic-2.diff" Content-Transfer-Encoding: 7Bit Content-Type: text/x-patch; charset="utf-8"; name="vrp_symbolic-2.diff" Content-length: 16928 Index: tree-vrp.c =================================================================== --- tree-vrp.c (revision 215656) +++ tree-vrp.c (working copy) @@ -916,6 +916,98 @@ symbolic_range_p (value_range_t *vr) || !is_gimple_min_invariant (vr->max)); } +/* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE + otherwise. We only handle additive operations and set NEG to true if the + symbol is negated and INV to the invariant part, if any. */ + +static tree +get_single_symbol (tree t, bool *neg, tree *inv) +{ + bool neg_; + tree inv_; + + if (TREE_CODE (t) == PLUS_EXPR + || TREE_CODE (t) == POINTER_PLUS_EXPR + || TREE_CODE (t) == MINUS_EXPR) + { + if (is_gimple_min_invariant (TREE_OPERAND (t, 0))) + { + neg_ = (TREE_CODE (t) == MINUS_EXPR); + inv_ = TREE_OPERAND (t, 0); + t = TREE_OPERAND (t, 1); + } + else if (is_gimple_min_invariant (TREE_OPERAND (t, 1))) + { + neg_ = false; + inv_ = TREE_OPERAND (t, 1); + t = TREE_OPERAND (t, 0); + } + else + return NULL_TREE; + } + else + { + neg_ = false; + inv_ = NULL_TREE; + } + + if (TREE_CODE (t) == NEGATE_EXPR) + { + t = TREE_OPERAND (t, 0); + neg_ = !neg_; + } + + if (TREE_CODE (t) != SSA_NAME) + return NULL_TREE; + + *neg = neg_; + *inv = inv_; + return t; +} + +/* The reverse operation: build a symbolic expression with TYPE + from symbol SYM, negated according to NEG, and invariant INV. */ + +static tree +build_symbolic_expr (tree type, tree sym, bool neg, tree inv) +{ + const bool pointer_p = POINTER_TYPE_P (type); + tree t = sym; + + if (neg) + t = build1 (NEGATE_EXPR, type, t); + + if (integer_zerop (inv)) + return t; + + return build2 (pointer_p ? POINTER_PLUS_EXPR : PLUS_EXPR, type, t, inv); +} + +/* Return true if value range VR involves exactly one symbol SYM. */ + +static bool +symbolic_range_based_on_p (value_range_t *vr, const_tree sym) +{ + bool neg, min_has_symbol, max_has_symbol; + tree inv; + + if (is_gimple_min_invariant (vr->min)) + min_has_symbol = false; + else if (get_single_symbol (vr->min, &neg, &inv) == sym) + min_has_symbol = true; + else + return false; + + if (is_gimple_min_invariant (vr->max)) + max_has_symbol = false; + else if (get_single_symbol (vr->max, &neg, &inv) == sym) + max_has_symbol = true; + else + return false; + + return (min_has_symbol || max_has_symbol); +} + /* Return true if value range VR uses an overflow infinity. */ static inline bool @@ -1199,25 +1291,30 @@ compare_values_warnv (tree val1, tree va both integers. */ gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1)) == POINTER_TYPE_P (TREE_TYPE (val2))); + /* Convert the two values into the same type. This is needed because sizetype causes sign extension even for unsigned types. */ val2 = fold_convert (TREE_TYPE (val1), val2); STRIP_USELESS_TYPE_CONVERSION (val2); if ((TREE_CODE (val1) == SSA_NAME + || (TREE_CODE (val1) == NEGATE_EXPR + && TREE_CODE (TREE_OPERAND (val1, 0)) == SSA_NAME) || TREE_CODE (val1) == PLUS_EXPR || TREE_CODE (val1) == MINUS_EXPR) && (TREE_CODE (val2) == SSA_NAME + || (TREE_CODE (val2) == NEGATE_EXPR + && TREE_CODE (TREE_OPERAND (val2, 0)) == SSA_NAME) || TREE_CODE (val2) == PLUS_EXPR || TREE_CODE (val2) == MINUS_EXPR)) { tree n1, c1, n2, c2; enum tree_code code1, code2; - /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME', + /* If VAL1 and VAL2 are of the form '[-]NAME [+-] CST' or 'NAME', return -1 or +1 accordingly. If VAL1 and VAL2 don't use the same name, return -2. */ - if (TREE_CODE (val1) == SSA_NAME) + if (TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == NEGATE_EXPR) { code1 = SSA_NAME; n1 = val1; @@ -1239,7 +1336,7 @@ compare_values_warnv (tree val1, tree va } } - if (TREE_CODE (val2) == SSA_NAME) + if (TREE_CODE (val2) == SSA_NAME || TREE_CODE (val2) == NEGATE_EXPR) { code2 = SSA_NAME; n2 = val2; @@ -1262,11 +1359,15 @@ compare_values_warnv (tree val1, tree va } /* Both values must use the same name. */ + if (TREE_CODE (n1) == NEGATE_EXPR && TREE_CODE (n2) == NEGATE_EXPR) + { + n1 = TREE_OPERAND (n1, 0); + n2 = TREE_OPERAND (n2, 0); + } if (n1 != n2) return -2; - if (code1 == SSA_NAME - && code2 == SSA_NAME) + if (code1 == SSA_NAME && code2 == SSA_NAME) /* NAME == NAME */ return 0; @@ -2209,7 +2310,7 @@ extract_range_from_multiplicative_op_1 ( } /* Extract range information from a binary operation CODE based on - the ranges of each of its operands, *VR0 and *VR1 with resulting + the ranges of each of its operands *VR0 and *VR1 with resulting type EXPR_TYPE. The resulting range is stored in *VR. */ static void @@ -2303,11 +2404,12 @@ extract_range_from_binary_expr_1 (value_ type = vr0.type; /* Refuse to operate on VARYING ranges, ranges of different kinds - and symbolic ranges. As an exception, we allow BIT_AND_EXPR + and symbolic ranges. As an exception, we allow BIT_{AND,IOR} because we may be able to derive a useful range even if one of the operands is VR_VARYING or symbolic range. Similarly for - divisions. TODO, we may be able to derive anti-ranges in - some cases. */ + divisions, MIN/MAX and PLUS/MINUS. + + TODO, we may be able to derive anti-ranges in some cases. */ if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR && code != TRUNC_DIV_EXPR @@ -2318,6 +2420,8 @@ extract_range_from_binary_expr_1 (value_ && code != TRUNC_MOD_EXPR && code != MIN_EXPR && code != MAX_EXPR + && code != PLUS_EXPR + && code != MINUS_EXPR && (vr0.type == VR_VARYING || vr1.type == VR_VARYING || vr0.type != vr1.type @@ -2376,50 +2480,115 @@ extract_range_from_binary_expr_1 (value_ range and see what we end up with. */ 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)) - { - signop sgn = TYPE_SIGN (expr_type); - unsigned int prec = TYPE_PRECISION (expr_type); - wide_int type_min = wi::min_value (TYPE_PRECISION (expr_type), sgn); - wide_int type_max = wi::max_value (TYPE_PRECISION (expr_type), sgn); - wide_int wmin, wmax; + const bool minus_p = (code == MINUS_EXPR); + tree min_op0 = vr0.min; + tree min_op1 = minus_p ? vr1.max : vr1.min; + tree max_op0 = vr0.max; + tree max_op1 = minus_p ? vr1.min : vr1.max; + tree sym_min_op0 = NULL_TREE; + tree sym_min_op1 = NULL_TREE; + tree sym_max_op0 = NULL_TREE; + tree sym_max_op1 = NULL_TREE; + bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1; + + /* If we have a PLUS or MINUS with two VR_RANGEs, either constant or + single-symbolic ranges, try to compute the precise resulting range, + but only if we know that this resulting range will also be constant + or single-symbolic. */ + if (vr0.type == VR_RANGE && vr1.type == VR_RANGE + && (TREE_CODE (min_op0) == INTEGER_CST + || (sym_min_op0 + = get_single_symbol (min_op0, &neg_min_op0, &min_op0))) + && (TREE_CODE (min_op1) == INTEGER_CST + || (sym_min_op1 + = get_single_symbol (min_op1, &neg_min_op1, &min_op1))) + && (!(sym_min_op0 && sym_min_op1) + || (sym_min_op0 == sym_min_op1 + && neg_min_op0 == (minus_p ? neg_min_op1 : !neg_min_op1))) + && (TREE_CODE (max_op0) == INTEGER_CST + || (sym_max_op0 + = get_single_symbol (max_op0, &neg_max_op0, &max_op0))) + && (TREE_CODE (max_op1) == INTEGER_CST + || (sym_max_op1 + = get_single_symbol (max_op1, &neg_max_op1, &max_op1))) + && (!(sym_max_op0 && sym_max_op1) + || (sym_max_op0 == sym_max_op1 + && neg_max_op0 == (minus_p ? neg_max_op1 : !neg_max_op1)))) + { + const signop sgn = TYPE_SIGN (expr_type); + const unsigned int prec = TYPE_PRECISION (expr_type); + wide_int type_min, type_max, wmin, wmax; int min_ovf = 0; int max_ovf = 0; - if (code == PLUS_EXPR) + /* Get the lower and upper bounds of the type. */ + if (TYPE_OVERFLOW_WRAPS (expr_type)) { - wmin = wi::add (vr0.min, vr1.min); - wmax = wi::add (vr0.max, vr1.max); - - /* Check for overflow. */ - if (wi::cmp (vr1.min, 0, sgn) != wi::cmp (wmin, vr0.min, sgn)) - min_ovf = wi::cmp (vr0.min, wmin, sgn); - if (wi::cmp (vr1.max, 0, sgn) != wi::cmp (wmax, vr0.max, sgn)) - max_ovf = wi::cmp (vr0.max, wmax, sgn); + type_min = wi::min_value (prec, sgn); + type_max = wi::max_value (prec, sgn); } - else /* if (code == MINUS_EXPR) */ + else { - wmin = wi::sub (vr0.min, vr1.max); - wmax = wi::sub (vr0.max, vr1.min); + type_min = vrp_val_min (expr_type); + type_max = vrp_val_max (expr_type); + } - if (wi::cmp (0, vr1.max, sgn) != wi::cmp (wmin, vr0.min, sgn)) - min_ovf = wi::cmp (vr0.min, vr1.max, sgn); - if (wi::cmp (0, vr1.min, sgn) != wi::cmp (wmax, vr0.max, sgn)) - max_ovf = wi::cmp (vr0.max, vr1.min, sgn); + /* Combine the lower bounds, if any. */ + if (min_op0 && min_op1) + { + if (minus_p) + { + wmin = wi::sub (min_op0, min_op1); + + /* Check for overflow. */ + if (wi::cmp (0, min_op1, sgn) + != wi::cmp (wmin, min_op0, sgn)) + min_ovf = wi::cmp (min_op0, min_op1, sgn); + } + else + { + wmin = wi::add (min_op0, min_op1); + + /* Check for overflow. */ + if (wi::cmp (min_op1, 0, sgn) + != wi::cmp (wmin, min_op0, sgn)) + min_ovf = wi::cmp (min_op0, wmin, sgn); + } } + else if (min_op0) + wmin = min_op0; + else if (min_op1) + wmin = minus_p ? wi::neg (min_op1) : min_op1; + else + wmin = wi::shwi (0, prec); - /* For non-wrapping arithmetic look at possibly smaller - value-ranges of the type. */ - if (!TYPE_OVERFLOW_WRAPS (expr_type)) + /* Combine the upper bounds, if any. */ + if (max_op0 && max_op1) { - if (vrp_val_min (expr_type)) - type_min = vrp_val_min (expr_type); - if (vrp_val_max (expr_type)) - type_max = vrp_val_max (expr_type); + if (minus_p) + { + wmax = wi::sub (max_op0, max_op1); + + /* Check for overflow. */ + if (wi::cmp (0, max_op1, sgn) + != wi::cmp (wmax, max_op0, sgn)) + max_ovf = wi::cmp (max_op0, max_op1, sgn); + } + else + { + wmax = wi::add (max_op0, max_op1); + + if (wi::cmp (max_op1, 0, sgn) + != wi::cmp (wmax, max_op0, sgn)) + max_ovf = wi::cmp (max_op0, wmax, sgn); + } } + else if (max_op0) + wmax = max_op0; + else if (max_op1) + wmax = minus_p ? wi::neg (max_op1) : max_op1; + else + wmax = wi::shwi (0, prec); /* Check for type overflow. */ if (min_ovf == 0) @@ -2437,6 +2606,15 @@ extract_range_from_binary_expr_1 (value_ max_ovf = 1; } + /* If we have overflow for the constant part and the resulting + range will be symbolic, drop to VR_VARYING. */ + if ((min_ovf && sym_min_op0 != sym_min_op1) + || (max_ovf && sym_max_op0 != sym_max_op1)) + { + set_value_range_to_varying (vr); + return; + } + if (TYPE_OVERFLOW_WRAPS (expr_type)) { /* If overflow wraps, truncate the values and adjust the @@ -2450,8 +2628,7 @@ extract_range_from_binary_expr_1 (value_ min = wide_int_to_tree (expr_type, tmin); max = wide_int_to_tree (expr_type, tmax); } - else if (min_ovf == -1 - && max_ovf == 1) + else if (min_ovf == -1 && max_ovf == 1) { /* Underflow and overflow, drop to VR_VARYING. */ set_value_range_to_varying (vr); @@ -2526,20 +2703,44 @@ extract_range_from_binary_expr_1 (value_ else max = wide_int_to_tree (expr_type, wmax); } + if (needs_overflow_infinity (expr_type) && supports_overflow_infinity (expr_type)) { - if (is_negative_overflow_infinity (vr0.min) - || (code == PLUS_EXPR - ? is_negative_overflow_infinity (vr1.min) - : is_positive_overflow_infinity (vr1.max))) + if ((min_op0 && is_negative_overflow_infinity (min_op0)) + || (min_op1 + && (minus_p + ? is_positive_overflow_infinity (min_op1) + : is_negative_overflow_infinity (min_op1)))) min = negative_overflow_infinity (expr_type); - if (is_positive_overflow_infinity (vr0.max) - || (code == PLUS_EXPR - ? is_positive_overflow_infinity (vr1.max) - : is_negative_overflow_infinity (vr1.min))) + if ((max_op0 && is_positive_overflow_infinity (max_op0)) + || (max_op1 + && (minus_p + ? is_negative_overflow_infinity (max_op1) + : is_positive_overflow_infinity (max_op1)))) max = positive_overflow_infinity (expr_type); } + + /* If the result lower bound is constant, we're done; + otherwise, build the symbolic lower bound. */ + if (sym_min_op0 == sym_min_op1) + ; + else if (sym_min_op0) + min = build_symbolic_expr (expr_type, sym_min_op0, + neg_min_op0, min); + else if (sym_min_op1) + min = build_symbolic_expr (expr_type, sym_min_op1, + neg_min_op1 ^ minus_p, min); + + /* Likewise for the upper bound. */ + if (sym_max_op0 == sym_max_op1) + ; + else if (sym_max_op0) + max = build_symbolic_expr (expr_type, sym_max_op0, + neg_max_op0, max); + else if (sym_max_op1) + max = build_symbolic_expr (expr_type, sym_max_op1, + neg_max_op1 ^ minus_p, max); } else { @@ -3024,14 +3225,11 @@ extract_range_from_binary_expr_1 (value_ gcc_unreachable (); /* If either MIN or MAX overflowed, then set the resulting range to - VARYING. But we do accept an overflow infinity - representation. */ + VARYING. But we do accept an overflow infinity representation. */ if (min == NULL_TREE - || !is_gimple_min_invariant (min) - || (TREE_OVERFLOW (min) && !is_overflow_infinity (min)) + || (TREE_OVERFLOW_P (min) && !is_overflow_infinity (min)) || max == NULL_TREE - || !is_gimple_min_invariant (max) - || (TREE_OVERFLOW (max) && !is_overflow_infinity (max))) + || (TREE_OVERFLOW_P (max) && !is_overflow_infinity (max))) { set_value_range_to_varying (vr); return; @@ -3093,6 +3291,59 @@ extract_range_from_binary_expr (value_ra set_value_range_to_varying (&vr1); extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1); + + /* 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 + is invariant, we set the corresponding bound of the new range to INF + in order to avoid recursing on the range of the second operand. */ + if (vr->type == VR_VARYING + && (code == PLUS_EXPR || code == MINUS_EXPR) + && TREE_CODE (op1) == SSA_NAME + && vr0.type == VR_RANGE + && symbolic_range_based_on_p (&vr0, op1)) + { + const bool minus_p = (code == MINUS_EXPR); + value_range_t n_vr1 = VR_INITIALIZER; + + /* Try with VR0 and [-INF, OP1]. */ + if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min)) + set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL); + + /* Try with VR0 and [OP1, +INF]. */ + else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max)) + set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL); + + /* Try with VR0 and [OP1, OP1]. */ + else + set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL); + + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1); + } + + if (vr->type == VR_VARYING + && (code == PLUS_EXPR || code == MINUS_EXPR) + && TREE_CODE (op0) == SSA_NAME + && vr1.type == VR_RANGE + && symbolic_range_based_on_p (&vr1, op0)) + { + const bool minus_p = (code == MINUS_EXPR); + value_range_t n_vr0 = VR_INITIALIZER; + + /* Try with [-INF, OP0] and VR1. */ + if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min)) + set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL); + + /* Try with [OP0, +INF] and VR1. */ + else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max)) + set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL); + + /* Try with [OP0, OP0] and VR1. */ + else + set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL); + + extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1); + } } /* Extract range information from a unary operation CODE based on --nextPart2346107.Kv9GypKaXs Content-Disposition: attachment; filename="vrp94.c" Content-Transfer-Encoding: 7Bit Content-Type: text/x-csrc; charset="UTF-8"; name="vrp94.c" Content-length: 496 /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-optimized" } */ extern void abort (void); int foo1 (int x, int y) { int z; if (x >= y) return 1; z = y - x; if (z <= 0) abort (); return z; } unsigned int foo2 (unsigned int x, unsigned int y) { unsigned int z; if (x >= y) return 1; z = y - x; if (z == 0) abort (); return z; } /* { dg-final { scan-tree-dump-not "abort" "optimized" } } */ /* { dg-final { cleanup-tree-dump "optimized" } } */ --nextPart2346107.Kv9GypKaXs Content-Disposition: attachment; filename="opt40.adb" Content-Transfer-Encoding: 7Bit Content-Type: text/x-adasrc; charset="UTF-8"; name="opt40.adb" Content-length: 380 -- { dg-do compile } -- { dg-options "-O2 -fdump-tree-optimized" } pragma Suppress (Overflow_Check); function Opt40 (X : Integer; Y : Integer) return Positive is Z : Integer; begin if X >= Y then return 1; end if; Z := Y - X; return Z; end; -- { dg-final { scan-tree-dump-not "gnat_rcheck" "optimized" } } -- { dg-final { cleanup-tree-dump "optimized" } } --nextPart2346107.Kv9GypKaXs--