From patchwork Fri Aug 17 07:11:04 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 958677 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-483829-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="It+hT4Kd"; 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 41sDrp6yw0z9s3x for ; Fri, 17 Aug 2018 17:11:20 +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=RFN9Z0whOyjZDR2oLD/7rIGMV3fK3MWsE4syytF4z67HSvv95l CS9Lmpo2yuWZardyGrDmULdkjRRH1OLo3Oke5vq4QwNw4IwhPQOkNxYr9wYFXh2s B3WkIB2+q9G1X1qtLFJ1DYyE+OWEBnDk+KgMS0UNV2GwxaPvgHC+PDQGM= 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=nKCEbs9zZesyslmJj3i9NTU59g0=; b=It+hT4Kd0XjP0zKEF6wE LB2keOfP40BmaiI3AbkOVH54xnAtko1xbhaVxRr4VLuG4CijkrDt8sj1+k3qXij+ ozsXONicNYHdSV0UNJKbC0QjKq/3vdkAL3ulJK7sfjmexWtr1nkc+itsO5vqn33l J+eMvI5hifmpqe+hjR0wxsU= Received: (qmail 106700 invoked by alias); 17 Aug 2018 07:11:12 -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 106689 invoked by uid 89); 17 Aug 2018 07:11:11 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-24.1 required=5.0 tests=AWL, BAYES_20, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.2 spammy=flip, VR_RANGE, sk:TYPE_OV, UD:vr0.type X-HELO: mail-wm0-f54.google.com Received: from mail-wm0-f54.google.com (HELO mail-wm0-f54.google.com) (74.125.82.54) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 17 Aug 2018 07:11:08 +0000 Received: by mail-wm0-f54.google.com with SMTP id y9-v6so6480691wma.5 for ; Fri, 17 Aug 2018 00:11:08 -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 t4-v6sm2185307wrb.45.2018.08.17.00.11.05 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 17 Aug 2018 00:11:05 -0700 (PDT) To: gcc-patches From: Aldy Hernandez Subject: VRP: abstract out MIN/MAX/ABS wide int code Message-ID: <3aa38fec-82aa-614e-4ef0-61f2dbf2eefa@redhat.com> Date: Fri, 17 Aug 2018 03:11:04 -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 No change in functionality, just a straight up conversion. OK for trunk? gcc/ * wide-int-range.cc (wide_int_range_abs): New. (wide_int_range_order_set): Rename from wide_int_range_min_max. * wide-int-range.h (wide_int_range_abs): New. (wide_int_range_min_max): New. * tree-vrp.c (extract_range_from_unary_expr): Rewrite ABS_EXPR case to call wide_int_range_abs. Rewrite MIN/MAX_EXPR to call wide_int_range_min_max. (extract_range_from_abs_expr): Delete. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index d553a254878..50e9eb0da07 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -1589,50 +1589,19 @@ extract_range_from_binary_expr_1 (value_range *vr, else if (code == MIN_EXPR || code == MAX_EXPR) { - if (vr0.type == VR_RANGE - && !symbolic_range_p (&vr0)) - { - type = VR_RANGE; - if (vr1.type == VR_RANGE - && !symbolic_range_p (&vr1)) - { - /* For operations that make the resulting range directly - proportional to the original ranges, apply the operation to - the same end of each range. */ - min = int_const_binop (code, vr0.min, vr1.min); - max = int_const_binop (code, vr0.max, vr1.max); - } - else if (code == MIN_EXPR) - { - min = vrp_val_min (expr_type); - max = vr0.max; - } - else if (code == MAX_EXPR) - { - min = vr0.min; - max = vrp_val_max (expr_type); - } - } - else if (vr1.type == VR_RANGE - && !symbolic_range_p (&vr1)) - { - type = VR_RANGE; - if (code == MIN_EXPR) - { - min = vrp_val_min (expr_type); - max = vr1.max; - } - else if (code == MAX_EXPR) - { - min = vr1.min; - max = vrp_val_max (expr_type); - } - } + wide_int wmin, wmax; + wide_int vr0_min, vr0_max; + wide_int 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 (wide_int_range_min_max (wmin, wmax, code, sign, prec, + vr0_min, vr0_max, vr1_min, vr1_max)) + set_value_range (vr, VR_RANGE, + wide_int_to_tree (expr_type, wmin), + wide_int_to_tree (expr_type, wmax), NULL); else - { - set_value_range_to_varying (vr); - return; - } + set_value_range_to_varying (vr); + return; } else if (code == MULT_EXPR) { @@ -1919,85 +1888,6 @@ extract_range_from_binary_expr_1 (value_range *vr, set_value_range (vr, type, min, max, NULL); } -/* Calculates the absolute value of a range and puts the result in VR. - VR0 is the input range. TYPE is the type of the resulting - range. */ - -static void -extract_range_from_abs_expr (value_range &vr, tree type, value_range &vr0) -{ - /* Pass through vr0 in the easy cases. */ - if (TYPE_UNSIGNED (type) - || value_range_nonnegative_p (&vr0)) - { - copy_value_range (&vr, &vr0); - return; - } - - /* For the remaining varying or symbolic ranges we can't do anything - useful. */ - if (vr0.type == VR_VARYING - || symbolic_range_p (&vr0)) - { - set_value_range_to_varying (&vr); - return; - } - - /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a - useful range. */ - if (!TYPE_OVERFLOW_UNDEFINED (type) - && ((vr0.type == VR_RANGE - && vrp_val_is_min (vr0.min)) - || (vr0.type == VR_ANTI_RANGE - && !vrp_val_is_min (vr0.min)))) - { - set_value_range_to_varying (&vr); - return; - } - - /* ABS_EXPR may flip the range around, if the original range - included negative values. */ - tree min, max; - if (!vrp_val_is_min (vr0.min)) - min = fold_unary_to_constant (ABS_EXPR, type, vr0.min); - else - min = TYPE_MAX_VALUE (type); - - if (!vrp_val_is_min (vr0.max)) - max = fold_unary_to_constant (ABS_EXPR, type, vr0.max); - else - max = TYPE_MAX_VALUE (type); - - int cmp = compare_values (min, max); - gcc_assert (vr0.type != VR_ANTI_RANGE); - - /* If the range contains zero then we know that the minimum value in the - range will be zero. */ - if (range_includes_zero_p (vr0.min, vr0.max) == 1) - { - if (cmp == 1) - max = min; - min = build_int_cst (type, 0); - } - else - { - /* If the range was reversed, swap MIN and MAX. */ - if (cmp == 1) - std::swap (min, max); - } - - cmp = compare_values (min, max); - if (cmp == -2 || cmp == 1) - { - /* If the new range has its limits swapped around (MIN > MAX), - then the operation caused one of them to wrap around, mark - the new range VARYING. */ - set_value_range_to_varying (&vr); - } - else - set_value_range (&vr, vr0.type, min, max, NULL); -} - /* Extract range information from a unary operation CODE based on the range of its operand *VR0 with type OP0_TYPE with resulting type TYPE. The resulting range is stored in *VR. */ @@ -2007,6 +1897,8 @@ extract_range_from_unary_expr (value_range *vr, enum tree_code code, tree type, value_range *vr0_, tree op0_type) { + signop sign = TYPE_SIGN (type); + unsigned int prec = TYPE_PRECISION (type); value_range vr0 = *vr0_, vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER; /* VRP only operates on integral and pointer types. */ @@ -2128,7 +2020,24 @@ extract_range_from_unary_expr (value_range *vr, return; } else if (code == ABS_EXPR) - return extract_range_from_abs_expr (*vr, type, vr0); + { + if (vr0.type != VR_RANGE || symbolic_range_p (&vr0)) + { + set_value_range_to_varying (vr); + return; + } + wide_int wmin, wmax; + wide_int vr0_min, vr0_max; + extract_range_into_wide_ints (&vr0, sign, prec, &vr0_min, &vr0_max); + if (wide_int_range_abs (wmin, wmax, sign, prec, vr0_min, vr0_max, + TYPE_OVERFLOW_UNDEFINED (type))) + set_value_range (vr, VR_RANGE, + wide_int_to_tree (type, wmin), + wide_int_to_tree (type, wmax), NULL); + else + set_value_range_to_varying (vr); + return; + } /* For unhandled operations fall back to varying. */ set_value_range_to_varying (vr); diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc index 3491d89664d..1228b2c4d1b 100644 --- a/gcc/wide-int-range.cc +++ b/gcc/wide-int-range.cc @@ -119,9 +119,10 @@ wide_int_range_set_zero_nonzero_bits (signop sign, accordingly. */ static void -wide_int_range_min_max (wide_int &min, wide_int &max, - wide_int &w0, wide_int &w1, wide_int &w2, wide_int &w3, - signop sign) +wide_int_range_order_set (wide_int &min, wide_int &max, + wide_int &w0, wide_int &w1, + wide_int &w2, wide_int &w3, + signop sign) { /* Order pairs w0,w1 and w2,w3. */ if (wi::gt_p (w0, w1, sign)) @@ -177,7 +178,7 @@ wide_int_range_cross_product (wide_int &res_lb, wide_int &res_ub, overflow_undefined)) return false; - wide_int_range_min_max (res_lb, res_ub, cp1, cp2, cp3, cp4, sign); + wide_int_range_order_set (res_lb, res_ub, cp1, cp2, cp3, cp4, sign); return true; } @@ -605,3 +606,60 @@ wide_int_range_trunc_mod (wide_int &wmin, wide_int &wmax, tmp = wi::zero (prec); wmax = wi::min (wmax, tmp, sign); } + +/* Calculate ABS_EXPR on a range and store the result in [MIN, MAX]. */ + +bool +wide_int_range_abs (wide_int &min, wide_int &max, + signop sign, unsigned prec, + const wide_int &vr0_min, const wide_int &vr0_max, + bool overflow_undefined) +{ + /* Pass through VR0 the easy cases. */ + if (sign == UNSIGNED || wi::ge_p (vr0_min, 0, sign)) + { + min = vr0_min; + max = vr0_max; + return true; + } + + /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a + useful range. */ + wide_int min_value = wi::min_value (prec, sign); + wide_int max_value = wi::max_value (prec, sign); + if (!overflow_undefined && wi::eq_p (vr0_min, min_value)) + return false; + + /* ABS_EXPR may flip the range around, if the original range + included negative values. */ + if (wi::eq_p (vr0_min, min_value)) + min = max_value; + else + min = wi::abs (vr0_min); + if (wi::eq_p (vr0_max, min_value)) + max = max_value; + else + max = wi::abs (vr0_max); + + /* If the range contains zero then we know that the minimum value in the + range will be zero. */ + if (wi::le_p (vr0_min, 0, sign) && wi::ge_p (vr0_max, 0, sign)) + { + if (wi::gt_p (min, max, sign)) + max = min; + min = wi::zero (prec); + } + else + { + /* If the range was reversed, swap MIN and MAX. */ + if (wi::gt_p (min, max, sign)) + std::swap (min, max); + } + + /* If the new range has its limits swapped around (MIN > MAX), then + the operation caused one of them to wrap around, mark the new + range VARYING. */ + if (wi::gt_p (min, max, sign)) + return false; + return true; +} diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h index 4421bc8aeca..41198e05b13 100644 --- a/gcc/wide-int-range.h +++ b/gcc/wide-int-range.h @@ -94,6 +94,11 @@ 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_abs (wide_int &min, wide_int &max, + signop sign, unsigned prec, + const wide_int &vr0_min, + const wide_int &vr0_max, + bool overflow_undefined); /* Return TRUE if shifting by range [MIN, MAX] is undefined behavior. */ @@ -112,4 +117,24 @@ wide_int_range_shift_undefined_p (signop sign, unsigned prec, return wi::lt_p (min, 0, sign) || wi::ge_p (max, prec, sign); } +/* Calculate MIN/MAX_EXPR of two ranges and store the result in [MIN, MAX]. */ + +inline bool +wide_int_range_min_max (wide_int &min, wide_int &max, + tree_code code, + signop sign, unsigned prec, + const wide_int &vr0_min, const wide_int &vr0_max, + const wide_int &vr1_min, const wide_int &vr1_max) +{ + wi::overflow_type overflow; + wide_int_binop (min, code, vr0_min, vr1_min, sign, &overflow); + wide_int_binop (max, code, vr0_max, vr1_max, sign, &overflow); + /* If the new range covers the entire domain, that's really no range + at all. */ + if (min == wi::min_value (prec, sign) + && max == wi::max_value (prec, sign)) + return false; + return true; +} + #endif /* GCC_WIDE_INT_RANGE_H */