From patchwork Wed Aug 15 01:33:39 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 957758 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-483670-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="jhZfgVIm"; 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 41qsSQ4SQZz9sCW for ; Wed, 15 Aug 2018 11:33:56 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=EAXipn80/5Rb0ILR5s27KSJ16+uC+xV+vy9Wr4svPjP4p6VJ4n WcbLlzQRec6oJYG/O9z+bayTjrYxE7MXNl1T1Apq6SL8B1dHRGYiwOzdaVsNM4C0 Mm5+WnFd8FbTMI84lsIIEJnDJ0w5V/aD+7V1F+K+ddgmM6ZB2oSRnjmbI= 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:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=ZpYCwXy1ArnIFNd2mOcO5wczyoo=; b=jhZfgVImsmwj8f2N6+aB Vcj7uDn1LGuRYZdvlFBB3IQj/CZREhAU2lScVukOPypp8M6l2muDbrD0Hg6sNDxv fKJ7eqYOf0iMQOUY0XIjtmbCLuxoophCxw7E5P7hJ2QHRqYz/cFe8L97l4OAoFls SHkKHgGbn5dJQlcE/1Y+9Es= Received: (qmail 79984 invoked by alias); 15 Aug 2018 01:33:48 -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 79973 invoked by uid 89); 15 Aug 2018 01:33:47 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-24.8 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_LAZY_DOMAIN_SECURITY, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.2 spammy=pleased, auditing, anti, 1124 X-HELO: mail-wr1-f49.google.com Received: from mail-wr1-f49.google.com (HELO mail-wr1-f49.google.com) (209.85.221.49) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 15 Aug 2018 01:33:44 +0000 Received: by mail-wr1-f49.google.com with SMTP id h14-v6so18727189wrw.13 for ; Tue, 14 Aug 2018 18:33:44 -0700 (PDT) Received: from abulafia.quesejoda.com (247.red-79-147-188.dynamicip.rima-tde.net. [79.147.188.247]) by smtp.gmail.com with ESMTPSA id i15-v6sm15566198wro.7.2018.08.14.18.33.40 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 14 Aug 2018 18:33:41 -0700 (PDT) To: Richard Biener , gcc-patches From: Aldy Hernandez Subject: VRP: rewrite the division code (to handle corner cases including 0) Message-ID: Date: Tue, 14 Aug 2018 21:33:39 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 X-IsSubscribed: yes Howdy! In auditing the *_DIV_EXPR code I noticed that we were really botching some divisions where the divisor included 0. Particularly interesting was that we were botching something as simple as dividing by [0,0]. We were also incorrectly calculating things like [-2,-2] / [0, 5555], where we should have removed the 0 from the divisor. Also, the symbolic special casing could be handled by just treating symbolic ranges as [-MIN, +MAX] and letting the common code handle then. Similarly for anti ranges, which actually never happen except for the constant case, since they've been normalized earlier. All in all, it was much easier to normalize all the symbolic ranges and treat everything generically by performing the division in two chunks... the negative numbers and the (non-zero) positive numbers. And finally, unioning the results. This makes everything much simpler to read with minimal special casing. Finally, my apologies for including a tiny change to the POINTER_PLUS_EXPR handling code as well. It came about the same set of auditing tests. It turns out we can handle POINTER_PLUS_EXPR(~[0,0], [X,Y]) without bailing as VR_VARYING in extract_range_from_binary_expr_1. In doing so, I also noticed that ~[0,0] is not the only non-null. We could also have ~[0,2] and still know that the pointer is not zero. I have adjusted range_is_nonnull accordingly. (Yes, we can get something like ~[0,2] for a pointer for things like the following in libgcc: if (segment_arg == (void *) (uintptr_type) 1) ... else if (segment_arg == (void *) (uintptr_type) 2) return NULL; else if (segment_arg != NULL) segment = (struct stack_segment *) segment_arg; ) BTW, I am still not happy with the entire interface to wide-int-range.*, and have another pending patchset that will simplify things even further. I think everyone will be pleased ;-). OK pending another round of tests? Aldy gcc/ * tree-vrp.c (abs_extent_range): Remove. (range_includes_zero_p): Move further up in file. (range_is_nonnull): Make it return true if VR does not contain 0, not just if VR is ~[0,0]. (extract_range_into_wide_ints): Pass wide ints by reference. (extract_range_from_binary_expr_1): Handle the case where POINTER_PLUS_EXPR's pointer is known to be non-zero. Rewrite the *DIV_EXPR code. Pass wide ints by reference in all calls to extract_range_into_wide_ints. * wide-int-range.cc (wide_int_range_div): New. * wide-int-range.h (wide_int_range_div): New. (wide_int_range_includes_zero_p): New. (wide_int_range_zero_p): New. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index d553a254878..adfdc01f2d1 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -478,42 +478,6 @@ set_value_range_to_null (value_range *vr, tree type) set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv); } - -/* If abs (min) < abs (max), set VR to [-max, max], if - abs (min) >= abs (max), set VR to [-min, min]. */ - -static void -abs_extent_range (value_range *vr, tree min, tree max) -{ - int cmp; - - gcc_assert (TREE_CODE (min) == INTEGER_CST); - gcc_assert (TREE_CODE (max) == INTEGER_CST); - gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (min))); - gcc_assert (!TYPE_UNSIGNED (TREE_TYPE (min))); - min = fold_unary (ABS_EXPR, TREE_TYPE (min), min); - max = fold_unary (ABS_EXPR, TREE_TYPE (max), max); - if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max)) - { - set_value_range_to_varying (vr); - return; - } - cmp = compare_values (min, max); - if (cmp == -1) - min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), max); - else if (cmp == 0 || cmp == 1) - { - max = min; - min = fold_unary (NEGATE_EXPR, TREE_TYPE (min), min); - } - else - { - set_value_range_to_varying (vr); - return; - } - set_and_canonicalize_value_range (vr, VR_RANGE, min, max, NULL); -} - /* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ bool @@ -538,14 +502,34 @@ vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2) && bitmap_equal_p (b1, b2))); } -/* Return true if VR is ~[0, 0]. */ + +/* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not + include the value zero, -2 if we cannot tell. */ + +int +range_includes_zero_p (tree min, tree max) +{ + tree zero = build_int_cst (TREE_TYPE (min), 0); + return value_inside_range (zero, min, max); +} + +/* Return true if VR does not contain 0. */ bool range_is_nonnull (value_range *vr) { - return vr->type == VR_ANTI_RANGE - && integer_zerop (vr->min) - && integer_zerop (vr->max); + if (vr->type == VR_VARYING + || vr->type == VR_UNDEFINED + || TREE_CODE (vr->min) != INTEGER_CST + || TREE_CODE (vr->max) != INTEGER_CST) + return false; + if (vr->type == VR_RANGE) + return !range_includes_zero_p (vr->min, vr->max); + /* ~[0,0] is not the only non-null. We could also have ~[0,5]. */ + else if (vr->type == VR_ANTI_RANGE) + return range_includes_zero_p (vr->min, vr->max); + else + gcc_unreachable (); } @@ -915,17 +899,6 @@ value_ranges_intersect_p (value_range *vr0, value_range *vr1) return true; } - -/* Return 1 if [MIN, MAX] includes the value zero, 0 if it does not - include the value zero, -2 if we cannot tell. */ - -int -range_includes_zero_p (tree min, tree max) -{ - tree zero = build_int_cst (TREE_TYPE (min), 0); - return value_inside_range (zero, min, max); -} - /* Return true if *VR is know to only contain nonnegative values. */ static inline bool @@ -1034,17 +1007,17 @@ ranges_from_anti_range (value_range *ar, static void inline extract_range_into_wide_ints (value_range *vr, signop sign, unsigned prec, - wide_int *wmin, wide_int *wmax) + wide_int &wmin, wide_int &wmax) { if (range_int_cst_p (vr)) { - *wmin = wi::to_wide (vr->min); - *wmax = wi::to_wide (vr->max); + wmin = wi::to_wide (vr->min); + wmax = wi::to_wide (vr->max); } else { - *wmin = wi::min_value (prec, sign); - *wmax = wi::max_value (prec, sign); + wmin = wi::min_value (prec, sign); + wmax = wi::max_value (prec, sign); } } @@ -1439,7 +1412,10 @@ extract_range_from_binary_expr_1 (value_range *vr, && code != RSHIFT_EXPR && (vr0.type == VR_VARYING || vr1.type == VR_VARYING - || vr0.type != vr1.type + || (vr0.type != vr1.type + /* We can handle POINTER_PLUS_EXPR(~[0,0], [x,y]) below, + even though we have differing range kinds. */ + && code != POINTER_PLUS_EXPR) || symbolic_range_p (&vr0) || symbolic_range_p (&vr1))) { @@ -1694,109 +1670,38 @@ extract_range_from_binary_expr_1 (value_range *vr, || code == EXACT_DIV_EXPR || code == ROUND_DIV_EXPR) { - if (vr0.type != VR_RANGE || symbolic_range_p (&vr0)) - { - /* For division, if op1 has VR_RANGE but op0 does not, something - can be deduced just from that range. Say [min, max] / [4, max] - gives [min / 4, max / 4] range. */ - if (vr1.type == VR_RANGE - && !symbolic_range_p (&vr1) - && range_includes_zero_p (vr1.min, vr1.max) == 0) - { - vr0.type = type = VR_RANGE; - vr0.min = vrp_val_min (expr_type); - vr0.max = vrp_val_max (expr_type); - } - else - { - set_value_range_to_varying (vr); - return; - } - } - - /* For divisions, if flag_non_call_exceptions is true, we must - not eliminate a division by zero. */ - if (cfun->can_throw_non_call_exceptions - && (vr1.type != VR_RANGE - || range_includes_zero_p (vr1.min, vr1.max) != 0)) + wide_int dividend_min, dividend_max, divisor_min, divisor_max; + wide_int wmin, wmax, extra_min, extra_max; + bool extra_range_p; + /* First, normalize ranges into constants we can handle. Note + that VR_ANTI_RANGE's of constants were already normalized + before arriving here. */ + extract_range_into_wide_ints (&vr0, sign, prec, + dividend_min, dividend_max); + extract_range_into_wide_ints (&vr1, sign, prec, + divisor_min, divisor_max); + if (!wide_int_range_div (wmin, wmax, code, sign, prec, + dividend_min, dividend_max, + divisor_min, divisor_max, + TYPE_OVERFLOW_UNDEFINED (expr_type), + TYPE_OVERFLOW_WRAPS (expr_type), + extra_range_p, extra_min, extra_max)) { set_value_range_to_varying (vr); return; } - - /* For divisions, if op0 is VR_RANGE, we can deduce a range - even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can - include 0. */ - if (vr0.type == VR_RANGE - && (vr1.type != VR_RANGE - || range_includes_zero_p (vr1.min, vr1.max) != 0)) - { - tree zero = build_int_cst (TREE_TYPE (vr0.min), 0); - int cmp; - - min = NULL_TREE; - max = NULL_TREE; - if (TYPE_UNSIGNED (expr_type) - || value_range_nonnegative_p (&vr1)) - { - /* For unsigned division or when divisor is known - to be non-negative, the range has to cover - all numbers from 0 to max for positive max - and all numbers from min to 0 for negative min. */ - cmp = compare_values (vr0.max, zero); - if (cmp == -1) - { - /* When vr0.max < 0, vr1.min != 0 and value - ranges for dividend and divisor are available. */ - if (vr1.type == VR_RANGE - && !symbolic_range_p (&vr0) - && !symbolic_range_p (&vr1) - && compare_values (vr1.min, zero) != 0) - max = int_const_binop (code, vr0.max, vr1.min); - else - max = zero; - } - else if (cmp == 0 || cmp == 1) - max = vr0.max; - else - type = VR_VARYING; - cmp = compare_values (vr0.min, zero); - if (cmp == 1) - { - /* For unsigned division when value ranges for dividend - and divisor are available. */ - if (vr1.type == VR_RANGE - && !symbolic_range_p (&vr0) - && !symbolic_range_p (&vr1) - && compare_values (vr1.max, zero) != 0) - min = int_const_binop (code, vr0.min, vr1.max); - else - min = zero; - } - else if (cmp == 0 || cmp == -1) - min = vr0.min; - else - type = VR_VARYING; - } - else - { - /* Otherwise the range is -max .. max or min .. -min - depending on which bound is bigger in absolute value, - as the division can change the sign. */ - abs_extent_range (vr, vr0.min, vr0.max); - return; - } - if (type == VR_VARYING) - { - set_value_range_to_varying (vr); - return; - } - } - else if (range_int_cst_p (&vr0) && range_int_cst_p (&vr1)) + set_value_range (vr, VR_RANGE, + wide_int_to_tree (expr_type, wmin), + wide_int_to_tree (expr_type, wmax), NULL); + if (extra_range_p) { - extract_range_from_multiplicative_op (vr, code, &vr0, &vr1); - return; + value_range extra_range = VR_INITIALIZER; + set_value_range (&extra_range, VR_RANGE, + wide_int_to_tree (expr_type, extra_min), + wide_int_to_tree (expr_type, extra_max), NULL); + vrp_meet (vr, &extra_range); } + return; } else if (code == TRUNC_MOD_EXPR) { @@ -1807,8 +1712,8 @@ extract_range_from_binary_expr_1 (value_range *vr, } wide_int wmin, wmax, tmp; wide_int vr0_min, vr0_max, vr1_min, vr1_max; - extract_range_into_wide_ints (&vr0, sign, prec, &vr0_min, &vr0_max); - extract_range_into_wide_ints (&vr1, sign, prec, &vr1_min, &vr1_max); + extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max); + extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max); wide_int_range_trunc_mod (wmin, wmax, sign, prec, vr0_min, vr0_max, vr1_min, vr1_max); min = wide_int_to_tree (expr_type, wmin); @@ -1829,8 +1734,8 @@ extract_range_from_binary_expr_1 (value_range *vr, &may_be_nonzero0, &must_be_nonzero0); vrp_set_zero_nonzero_bits (expr_type, &vr1, &may_be_nonzero1, &must_be_nonzero1); - extract_range_into_wide_ints (&vr0, sign, prec, &vr0_min, &vr0_max); - extract_range_into_wide_ints (&vr1, sign, prec, &vr1_min, &vr1_max); + extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max); + extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max); if (code == BIT_AND_EXPR) { if (wide_int_range_bit_and (wmin, wmax, sign, prec, diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc index 3491d89664d..bfc574c42e7 100644 --- a/gcc/wide-int-range.cc +++ b/gcc/wide-int-range.cc @@ -21,6 +21,7 @@ along with GCC; see the file COPYING3. If not see #include "system.h" #include "coretypes.h" #include "tree.h" +#include "function.h" #include "fold-const.h" #include "wide-int-range.h" @@ -605,3 +606,75 @@ wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax, tmp = wi::zero (prec); wmax = wi::min (wmax, tmp, sign); } + +/* Calculate a division operation on two ranges and store the result in + [WMIN, WMAX] U [EXTRA_MIN, EXTRA_MAX]. + + If EXTRA_RANGE_P is set upon return, EXTRA_MIN/EXTRA_MAX hold + meaningful information, otherwise they should be ignored. + + Return TRUE if we were able to successfully calculate the new range. */ + +bool +wide_int_range_div (wide_int &wmin, wide_int &wmax, + tree_code code, signop sign, unsigned prec, + const wide_int ÷nd_min, const wide_int ÷nd_max, + const wide_int &divisor_min, const wide_int &divisor_max, + bool overflow_undefined, + bool overflow_wraps, + bool &extra_range_p, + wide_int &extra_min, wide_int &extra_max) +{ + extra_range_p = false; + + /* If we know we won't divide by zero, just do the division. */ + if (!wide_int_range_includes_zero_p (divisor_min, divisor_max, sign)) + { + wide_int_range_multiplicative_op (wmin, wmax, code, sign, prec, + dividend_min, dividend_max, + divisor_min, divisor_max, + overflow_undefined, + overflow_wraps); + return true; + } + + /* If flag_non_call_exceptions, we must not eliminate a division + by zero. */ + if (cfun->can_throw_non_call_exceptions) + return false; + + /* If we're definitely dividing by zero, there's nothing to do. */ + if (wide_int_range_zero_p (divisor_min, divisor_max, prec)) + return false; + + /* Perform the division in 2 parts, [LB, -1] and [1, UB], + which will skip any division by zero. + + First divide by the negative numbers, if any. */ + if (wi::neg_p (divisor_min, sign)) + { + if (!wide_int_range_multiplicative_op (wmin, wmax, + code, sign, prec, + dividend_min, dividend_max, + divisor_min, wi::minus_one (prec), + overflow_undefined, + overflow_wraps)) + return false; + extra_range_p = true; + } + /* Then divide by the non-zero positive numbers, if any. */ + if (wi::gt_p (divisor_max, wi::zero (prec), sign)) + { + if (!wide_int_range_multiplicative_op (extra_range_p ? extra_min : wmin, + extra_range_p ? extra_max : wmax, + code, sign, prec, + dividend_min, dividend_max, + wi::one (prec), divisor_max, + overflow_undefined, + overflow_wraps)) + return false; + } + else + extra_range_p = false; + return true; +} diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h index 4421bc8aeca..541a73c6172 100644 --- a/gcc/wide-int-range.h +++ b/gcc/wide-int-range.h @@ -94,6 +94,17 @@ extern void wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax, const wide_int &vr0_max, const wide_int &vr1_min, const wide_int &vr1_max); +extern bool wide_int_range_div (wide_int &wmin, wide_int &wmax, + enum tree_code code, + signop sign, unsigned prec, + const wide_int ÷nd_min, + const wide_int ÷nd_max, + const wide_int &divisor_min, + const wide_int &divisor_max, + bool overflow_undefined, + bool overflow_wraps, + bool &extra_range_p, + wide_int &extra_min, wide_int &extra_max); /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior. */ @@ -112,4 +123,22 @@ wide_int_range_shift_undefined_p (signop sign, unsigned prec, return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign); } +/* Return TRUE if 0 is within [WMIN, WMAX]. */ + +inline bool +wide_int_range_includes_zero_p (const wide_int &wmin, const wide_int &wmax, + signop sign) +{ + return wi::le_p (wmin, 0, sign) && wi::ge_p (wmax, 0, sign); +} + +/* Return TRUE if [WMIN, WMAX] is the singleton 0. */ + +inline bool +wide_int_range_zero_p (const wide_int &wmin, const wide_int &wmax, + unsigned prec) +{ + return wmin == wmax && wi::eq_p (wmin, wi::zero (prec)); +} + #endif /* GCC_WIDE_INT_RANGE_H */