From patchwork Mon Jul 1 09:19:18 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1125156 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-504043-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="xNHGq892"; 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 45chdy6hsyz9s4V for ; Mon, 1 Jul 2019 19:19:34 +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:from :subject:to:cc:message-id:date:mime-version:content-type; q=dns; s=default; b=kuI5TypN6brFeZHvB6UqnbVmXoUUXaZqBqkBAlN32+wWfIYLRw Hkpo9/hn+sEkX6pfbqHiZvzxmhob1d7aXonPaG4/q6VqP01seZ2pYXiKyI3JVyqN fBW6S1yOSjKDq9zorzu+DR+Pj5BBeyhAzOowg+Rj8HUVzzko0b5Ky/nTQ= 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:from :subject:to:cc:message-id:date:mime-version:content-type; s= default; bh=zqi1BIvC6i9fX+lG4fUkyRoBW2s=; b=xNHGq892hniEk/abNQJm oUvnQvlXMkv5nuEX2OZ3EVuBsFncKvB3yqPuuxxdUFNCK5uPXNCzORVTJMaFyJHd HARh/vr2rOg1nAmvECpYzZJRLAyj1pi7e19NABotwlvNhF27Fyv4XBK75HukxlHv SRzC7C7zv3pblLsXmnbIsVk= Received: (qmail 122331 invoked by alias); 1 Jul 2019 09:19:26 -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 122320 invoked by uid 89); 1 Jul 2019 09:19:26 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.7 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 spammy=2022 X-HELO: mail-wr1-f43.google.com Received: from mail-wr1-f43.google.com (HELO mail-wr1-f43.google.com) (209.85.221.43) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 01 Jul 2019 09:19:22 +0000 Received: by mail-wr1-f43.google.com with SMTP id f9so12895430wre.12 for ; Mon, 01 Jul 2019 02:19:22 -0700 (PDT) Received: from abulafia.quesejoda.com ([188.119.240.43]) by smtp.gmail.com with ESMTPSA id y16sm7911951wru.28.2019.07.01.02.19.19 (version=TLS1_3 cipher=AEAD-AES128-GCM-SHA256 bits=128/128); Mon, 01 Jul 2019 02:19:20 -0700 (PDT) From: Aldy Hernandez Subject: [range-ops] patch 03/04: abstract out a few things from extract_range_from* To: Richard Biener Cc: gcc-patches , Andrew MacLeod Message-ID: <82a0c8a9-13ba-9981-889f-a22fa5965eb9@redhat.com> Date: Mon, 1 Jul 2019 05:19:18 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 X-IsSubscribed: yes I hate duplicating code, and the symbolic handling of pointer_plus_expr, plus_minus_expr, and the code dealing with overflows, is ripe for sharing with the ranger. I've abstracted these into their own functions. No changes in functionality is expected. You will notice that I moved value_range_kind into coretypes.h, as I'd like to use it for value_range, wide-int-range.h, and the ranger header files. For value_range, all options are valid. For wide-int-range.h (adjust_range_for_overflow), everything but VR_UNDEFINED is valid. For the ranger, all values are valid but only for the constructors as our internal implementation has no need for this field. The ranger accesses things with the higher-level num_pairs(), lower/upper_bound(), etc. Tested on x86-64 Linux with --enable-languages=all. Aldy commit e58c0f8b8a27fa91fe22f1f12d19f3d37cc729ae Author: Aldy Hernandez Date: Fri Jun 28 10:41:05 2019 +0200 Move set_value_range_with_overflow into wide-int-range.cc as adjust_range_for_overflow. Move the POINTER_PLUS_EXPR symbolics code into handle_symbolics_in_pointer_plus_expr. Move the PLUS/MINUS_EXPR handling code into extract_range_from_plus_expr. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 866200d9594..40a51fc67dc 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,18 @@ +2019-07-01 Aldy Hernandez + + * tree-vrp.h (value_range_kind): Move from here... + * coretypes.h (value_range_kind): ...to here. + * tree-vrp.c (extract_range_from_binary_expr): Abstract pointer + plus handling of symbolics to + handle_symbolics_in_pointer_plus_expr(). + Abstract plus/minus handling code to + extract_range_from_plus_expr. + Move set_value_range_with_overflow to wide-int-range.cc. + (handle_symbolics_in_pointer_plus_expr): New. + (extract_range_from_plus_expr): New. + * wide-int-range.cc (adjust_range_for_overflow): New. + * wide-int-range.h (adjust_range_for_overflow): New. + 2019-07-01 Aldy Hernandez * tree-vrp.c (value_range_base::set_and_canonicalize): Rename to diff --git a/gcc/coretypes.h b/gcc/coretypes.h index 2f6b8599d7c..4bb1282b1b9 100644 --- a/gcc/coretypes.h +++ b/gcc/coretypes.h @@ -202,6 +202,24 @@ enum profile_update { PROFILE_UPDATE_PREFER_ATOMIC }; +/* Types of ranges. + + This is still prefixed with VR_*, even though it is more general + purpose, to avoid having to replace everything across the compiler. + Perhaps we should change it later. */ +enum value_range_kind { + /* Empty range. */ + VR_UNDEFINED, + /* Range spans the entire domain. */ + VR_VARYING, + /* Range is [MIN, MAX]. */ + VR_RANGE, + /* Range is ~[MIN, MAX]. */ + VR_ANTI_RANGE, + /* Range is a nice guy. */ + VR_LAST +}; + /* Types of unwind/exception handling info that can be generated. */ enum unwind_info_type diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index f78517b5b3b..efd51735022 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -1470,112 +1470,196 @@ combine_bound (enum tree_code code, wide_int &wi, wi::overflow_type &ovf, wi = wi::shwi (0, prec); } -/* Given a range in [WMIN, WMAX], adjust it for possible overflow and - put the result in VR. +/* Fold two value range's of a POINTER_PLUS_EXPR into VR. Return TRUE + if successful. */ - TYPE is the type of the range. +static bool +handle_symbolics_in_pointer_plus_expr (value_range_base *vr, + enum tree_code code, + tree expr_type, + const value_range_base *vr0, + const value_range_base *vr1) +{ + if (POINTER_TYPE_P (expr_type) && code == POINTER_PLUS_EXPR) + { + /* For pointer types, we are really only interested in asserting + whether the expression evaluates to non-NULL. + With -fno-delete-null-pointer-checks we need to be more + conservative. As some object might reside at address 0, + then some offset could be added to it and the same offset + subtracted again and the result would be NULL. + E.g. + static int a[12]; where &a[0] is NULL and + ptr = &a[6]; + ptr -= 6; + ptr will be NULL here, even when there is POINTER_PLUS_EXPR + where the first range doesn't include zero and the second one + doesn't either. As the second operand is sizetype (unsigned), + consider all ranges where the MSB could be set as possible + subtractions where the result might be NULL. */ + if ((!range_includes_zero_p (vr0) + || !range_includes_zero_p (vr1)) + && !TYPE_OVERFLOW_WRAPS (expr_type) + && (flag_delete_null_pointer_checks + || (range_int_cst_p (vr1) + && !tree_int_cst_sign_bit (vr1->max ())))) + vr->set_nonzero (expr_type); + else if (vr0->zero_p () && vr1->zero_p ()) + vr->set_zero (expr_type); + else + vr->set_varying (expr_type); + return true; + } + return false; +} - MIN_OVF and MAX_OVF indicate what type of overflow, if any, - occurred while originally calculating WMIN or WMAX. -1 indicates - underflow. +1 indicates overflow. 0 indicates neither. */ +/* Extract range information from a PLUS_EXPR or MINUS_EXPR based on + the ranges of each of its operands *VR0 and *VR1 with resulting + type EXPR_TYPE. The resulting range is stored in *VR. */ static void -set_value_range_with_overflow (value_range_kind &kind, tree &min, tree &max, - tree type, - const wide_int &wmin, const wide_int &wmax, - wi::overflow_type min_ovf, - wi::overflow_type max_ovf) +extract_range_from_plus_expr (value_range_base *vr, + enum tree_code code, tree expr_type, + const value_range_base *vr0, + const value_range_base *vr1) { - const signop sgn = TYPE_SIGN (type); - const unsigned int prec = TYPE_PRECISION (type); - - /* For one bit precision if max < min, then the swapped - range covers all values. */ - if (prec == 1 && wi::lt_p (wmax, wmin, sgn)) + gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR); + enum value_range_kind type; + tree min = NULL, max = NULL; + value_range_kind vr0_kind = vr0->kind (), vr1_kind = vr1->kind (); + tree vr0_min = vr0->min (), vr0_max = vr0->max (); + tree vr1_min = vr1->min (), vr1_max = vr1->max (); + /* This will normalize things such that calculating + [0,0] - VR_VARYING is not dropped to varying, but is + calculated as [MIN+1, MAX]. */ + if (vr0->varying_p ()) { - kind = VR_VARYING; - return; + vr0_kind = VR_RANGE; + vr0_min = vrp_val_min (expr_type); + vr0_max = vrp_val_max (expr_type); } - - if (TYPE_OVERFLOW_WRAPS (type)) + if (vr1->varying_p ()) { - /* If overflow wraps, truncate the values and adjust the - range kind and bounds appropriately. */ - wide_int tmin = wide_int::from (wmin, prec, sgn); - wide_int tmax = wide_int::from (wmax, prec, sgn); - if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE)) + vr1_kind = VR_RANGE; + vr1_min = vrp_val_min (expr_type); + vr1_max = vrp_val_max (expr_type); + } + 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; + + neg_min_op0 = neg_min_op1 = neg_max_op0 = neg_max_op1 = false; + + /* 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_kind == VR_RANGE && vr1_kind == 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)))) + { + wide_int wmin, wmax; + wi::overflow_type min_ovf = wi::OVF_NONE; + wi::overflow_type max_ovf = wi::OVF_NONE; + + /* Build the bounds. */ + combine_bound (code, wmin, min_ovf, expr_type, min_op0, min_op1); + combine_bound (code, wmax, max_ovf, expr_type, max_op0, max_op1); + + /* If we have overflow for the constant part and the resulting + range will be symbolic, drop to VR_VARYING. */ + if (((bool)min_ovf && sym_min_op0 != sym_min_op1) + || ((bool)max_ovf && sym_max_op0 != sym_max_op1)) { - /* If the limits are swapped, we wrapped around and cover - the entire range. We have a similar check at the end of - extract_range_from_binary_expr. */ - if (wi::gt_p (tmin, tmax, sgn)) - kind = VR_VARYING; - else - { - kind = VR_RANGE; - /* No overflow or both overflow or underflow. The - range kind stays VR_RANGE. */ - min = wide_int_to_tree (type, tmin); - max = wide_int_to_tree (type, tmax); - } + vr->set_varying (expr_type); return; } - else if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE) - || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE)) + + adjust_range_for_overflow (type, wmin, wmax, expr_type, + min_ovf, max_ovf, + TYPE_OVERFLOW_WRAPS (expr_type)); + if (type == VR_VARYING) { - /* Min underflow or max overflow. The range kind - changes to VR_ANTI_RANGE. */ - bool covers = false; - wide_int tem = tmin; - tmin = tmax + 1; - if (wi::cmp (tmin, tmax, sgn) < 0) - covers = true; - tmax = tem - 1; - if (wi::cmp (tmax, tem, sgn) > 0) - covers = true; - /* If the anti-range would cover nothing, drop to varying. - Likewise if the anti-range bounds are outside of the - types values. */ - if (covers || wi::cmp (tmin, tmax, sgn) > 0) - { - kind = VR_VARYING; - return; - } - kind = VR_ANTI_RANGE; - min = wide_int_to_tree (type, tmin); - max = wide_int_to_tree (type, tmax); + vr->set_varying (expr_type); return; } - else + gcc_assert (type != VR_UNDEFINED); + min = wide_int_to_tree (expr_type, wmin); + max = wide_int_to_tree (expr_type, wmax); + + /* Build the symbolic bounds if needed. */ + adjust_symbolic_bound (min, code, expr_type, + sym_min_op0, sym_min_op1, + neg_min_op0, neg_min_op1); + adjust_symbolic_bound (max, code, expr_type, + sym_max_op0, sym_max_op1, + neg_max_op0, neg_max_op1); + + /* If either MIN or MAX overflowed, then set the resulting range to + VARYING. */ + if (min == NULL_TREE + || TREE_OVERFLOW_P (min) + || max == NULL_TREE + || TREE_OVERFLOW_P (max)) { - /* Other underflow and/or overflow, drop to VR_VARYING. */ - kind = VR_VARYING; + vr->set_varying (expr_type); return; } + + int 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. */ + vr->set_varying (expr_type); + } + else + vr->set (type, min, max); + return; } else { - /* If overflow does not wrap, saturate to the types min/max - value. */ - wide_int type_min = wi::min_value (prec, sgn); - wide_int type_max = wi::max_value (prec, sgn); - kind = VR_RANGE; - if (min_ovf == wi::OVF_UNDERFLOW) - min = wide_int_to_tree (type, type_min); - else if (min_ovf == wi::OVF_OVERFLOW) - min = wide_int_to_tree (type, type_max); - else - min = wide_int_to_tree (type, wmin); - - if (max_ovf == wi::OVF_UNDERFLOW) - max = wide_int_to_tree (type, type_min); - else if (max_ovf == wi::OVF_OVERFLOW) - max = wide_int_to_tree (type, type_max); - else - max = wide_int_to_tree (type, wmax); + /* 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 + operations and a union primitive: + [-INF, 2] + [1, 2] U [5, +INF] + [1, 2] + [-INF+1, 4] U [6, +INF(OVF)] + though usually the union is not exactly representable with + a single range or anti-range as the above is + [-INF+1, +INF(OVF)] intersected with ~[5, 5] + but one could use a scheme similar to equivalences for this. */ + vr->set_varying (expr_type); } } + /* Extract range information from a binary operation CODE based on the ranges of each of its operands *VR0 and *VR1 with resulting type EXPR_TYPE. The resulting range is stored in *VR. */ @@ -1731,34 +1815,7 @@ extract_range_from_binary_expr (value_range_base *vr, vr->set_varying (expr_type); } else if (code == POINTER_PLUS_EXPR) - { - /* For pointer types, we are really only interested in asserting - whether the expression evaluates to non-NULL. - With -fno-delete-null-pointer-checks we need to be more - conservative. As some object might reside at address 0, - then some offset could be added to it and the same offset - subtracted again and the result would be NULL. - E.g. - static int a[12]; where &a[0] is NULL and - ptr = &a[6]; - ptr -= 6; - ptr will be NULL here, even when there is POINTER_PLUS_EXPR - where the first range doesn't include zero and the second one - doesn't either. As the second operand is sizetype (unsigned), - consider all ranges where the MSB could be set as possible - subtractions where the result might be NULL. */ - if ((!range_includes_zero_p (&vr0) - || !range_includes_zero_p (&vr1)) - && !TYPE_OVERFLOW_WRAPS (expr_type) - && (flag_delete_null_pointer_checks - || (range_int_cst_p (&vr1) - && !tree_int_cst_sign_bit (vr1.max ())))) - vr->set_nonzero (expr_type); - else if (vr0.zero_p () && vr1.zero_p ()) - vr->set_zero (expr_type); - else - vr->set_varying (expr_type); - } + handle_symbolics_in_pointer_plus_expr (vr, code, expr_type, &vr0, &vr1); else if (code == BIT_AND_EXPR) { /* For pointer types, we are really only interested in asserting @@ -1780,115 +1837,8 @@ extract_range_from_binary_expr (value_range_base *vr, range and see what we end up with. */ if (code == PLUS_EXPR || code == MINUS_EXPR) { - value_range_kind vr0_kind = vr0.kind (), vr1_kind = vr1.kind (); - tree vr0_min = vr0.min (), vr0_max = vr0.max (); - tree vr1_min = vr1.min (), vr1_max = vr1.max (); - /* This will normalize things such that calculating - [0,0] - VR_VARYING is not dropped to varying, but is - calculated as [MIN+1, MAX]. */ - if (vr0.varying_p ()) - { - vr0_kind = VR_RANGE; - vr0_min = vrp_val_min (expr_type); - vr0_max = vrp_val_max (expr_type); - } - if (vr1.varying_p ()) - { - vr1_kind = VR_RANGE; - vr1_min = vrp_val_min (expr_type); - vr1_max = vrp_val_max (expr_type); - } - - 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; - - neg_min_op0 = neg_min_op1 = neg_max_op0 = neg_max_op1 = false; - - /* 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_kind == VR_RANGE && vr1_kind == 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)))) - { - wide_int wmin, wmax; - wi::overflow_type min_ovf = wi::OVF_NONE; - wi::overflow_type max_ovf = wi::OVF_NONE; - - /* Build the bounds. */ - combine_bound (code, wmin, min_ovf, expr_type, min_op0, min_op1); - combine_bound (code, wmax, max_ovf, expr_type, max_op0, max_op1); - - /* If we have overflow for the constant part and the resulting - range will be symbolic, drop to VR_VARYING. */ - if (((bool)min_ovf && sym_min_op0 != sym_min_op1) - || ((bool)max_ovf && sym_max_op0 != sym_max_op1)) - { - vr->set_varying (expr_type); - return; - } - - /* Adjust the range for possible overflow. */ - min = NULL_TREE; - max = NULL_TREE; - set_value_range_with_overflow (type, min, max, expr_type, - wmin, wmax, min_ovf, max_ovf); - if (type == VR_VARYING) - { - vr->set_varying (expr_type); - return; - } - - /* Build the symbolic bounds if needed. */ - adjust_symbolic_bound (min, code, expr_type, - sym_min_op0, sym_min_op1, - neg_min_op0, neg_min_op1); - adjust_symbolic_bound (max, code, expr_type, - sym_max_op0, sym_max_op1, - neg_max_op0, neg_max_op1); - } - 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 - operations and a union primitive: - [-INF, 2] + [1, 2] U [5, +INF] + [1, 2] - [-INF+1, 4] U [6, +INF(OVF)] - though usually the union is not exactly representable with - a single range or anti-range as the above is - [-INF+1, +INF(OVF)] intersected with ~[5, 5] - but one could use a scheme similar to equivalences for this. */ - vr->set_varying (expr_type); - return; - } + extract_range_from_plus_expr (vr, code, expr_type, &vr0, &vr1); + return; } else if (code == MIN_EXPR || code == MAX_EXPR) diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index 3511cfaf0fc..e4268cd4742 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -20,22 +20,6 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_TREE_VRP_H #define GCC_TREE_VRP_H -/* Types of value ranges. */ -enum value_range_kind -{ - /* Empty range. */ - VR_UNDEFINED, - /* Range spans the entire domain. */ - VR_VARYING, - /* Range is [MIN, MAX]. */ - VR_RANGE, - /* Range is ~[MIN, MAX]. */ - VR_ANTI_RANGE, - /* Range is a nice guy. */ - VR_LAST -}; - - /* Range of values that can be associated with an SSA_NAME after VRP has executed. */ class GTY((for_user)) value_range_base diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc index 90c58f6bb6e..5f81f21a125 100644 --- a/gcc/wide-int-range.cc +++ b/gcc/wide-int-range.cc @@ -863,3 +863,105 @@ wide_int_range_div (wide_int &wmin, wide_int &wmax, extra_range_p = false; return true; } + +/* Adjust the range in [WMIN, WMAX] for possible overflow and store the + parts of the resulting range in KIND, WMIN, WMAX. + + TYPE is the type of the range. + + MIN_OVF and MAX_OVF indicate what type of overflow, if any, + occurred while originally calculating WMIN or WMAX. */ + +void +adjust_range_for_overflow (value_range_kind &kind, + wide_int &wmin, wide_int &wmax, + tree type, + wi::overflow_type min_ovf, + wi::overflow_type max_ovf, + bool overflow_wraps) +{ + const signop sgn = TYPE_SIGN (type); + const unsigned int prec = TYPE_PRECISION (type); + + /* For one bit precision if max < min, then the swapped + range covers all values. */ + if (prec == 1 && wi::lt_p (wmax, wmin, sgn)) + { + kind = VR_VARYING; + return; + } + + if (overflow_wraps) + { + /* If overflow wraps, truncate the values and adjust the + range kind and bounds appropriately. */ + wide_int tmin = wide_int::from (wmin, prec, sgn); + wide_int tmax = wide_int::from (wmax, prec, sgn); + if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE)) + { + /* If the limits are swapped, we wrapped around and cover + the entire range. We have a similar check at the end of + extract_range_from_binary_expr. */ + if (wi::gt_p (tmin, tmax, sgn)) + kind = VR_VARYING; + else + { + kind = VR_RANGE; + /* No overflow or both overflow or underflow. The + range kind stays VR_RANGE. */ + wmin = tmin; + wmax = tmax; + } + return; + } + else if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE) + || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE)) + { + /* Min underflow or max overflow. The range kind + changes to VR_ANTI_RANGE. */ + bool covers = false; + wide_int tem = tmin; + tmin = tmax + 1; + if (wi::cmp (tmin, tmax, sgn) < 0) + covers = true; + tmax = tem - 1; + if (wi::cmp (tmax, tem, sgn) > 0) + covers = true; + /* If the anti-range would cover nothing, drop to varying. + Likewise if the anti-range bounds are outside of the + types values. */ + if (covers || wi::cmp (tmin, tmax, sgn) > 0) + { + kind = VR_VARYING; + return; + } + kind = VR_ANTI_RANGE; + wmin = tmin; + wmax = tmax; + return; + } + else + { + /* Other underflow and/or overflow, drop to VR_VARYING. */ + kind = VR_VARYING; + return; + } + } + else + { + /* If overflow does not wrap, saturate to the types min/max + value. */ + wide_int type_min = wi::min_value (prec, sgn); + wide_int type_max = wi::max_value (prec, sgn); + kind = VR_RANGE; + if (min_ovf == wi::OVF_UNDERFLOW) + wmin = type_min; + else if (min_ovf == wi::OVF_OVERFLOW) + wmin = type_max; + + if (max_ovf == wi::OVF_UNDERFLOW) + wmax = type_min; + else if (max_ovf == wi::OVF_OVERFLOW) + wmax = type_max; + } +} diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h index fc9af72b127..2592f9c7540 100644 --- a/gcc/wide-int-range.h +++ b/gcc/wide-int-range.h @@ -185,4 +185,11 @@ wide_int_range_zero_p (const wide_int &wmin, const wide_int &wmax, return wmin == wmax && wi::eq_p (wmin, wi::zero (prec)); } +void +adjust_range_for_overflow (value_range_kind &, + wide_int &, wide_int &, + tree type, + wi::overflow_type, wi::overflow_type, + bool overflow_wraps); + #endif /* GCC_WIDE_INT_RANGE_H */