From patchwork Wed Nov 13 17:12:20 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 1194404 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-513281-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="vpt6zz1e"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.b="MB/EyhvG"; 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 47Crlr3ft6z9s7T for ; Thu, 14 Nov 2019 04:12:54 +1100 (AEDT) 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=gLVYi3wxBb/ImD46kJg/Oa2fLHGFbeSwUh2Tvw1pDbtEq2qk1i vcvTe4olEjWxL5mpzkAloSXLmHGjmuTl8/41Rn3geaBPcRo6JZpw/3hyDfzYR1Xn aFOq2gVLZ1N9Dj0PKfDULiqAqhOX6oxj9XxyM2wI4ie63feRYrb4zSLlQ= 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=+Y4XkiS7PXqQOUBDkXRiZclX+mQ=; b=vpt6zz1eGc58VJYxqZtC 0Cdo8m7W4gJ4hvJKnu6VsI/xlZTQVIq7w6+BEkY66rshw5AJnRwx7xuefqHK3khB HiLP+4nomSpaHQJrEfmKp/Mhxb+XC6T8jwA3AX22JBaLSSt9fUfyYyae62iq4z/f 4TPyakVo5sxrGAC1yCRXay8= Received: (qmail 57788 invoked by alias); 13 Nov 2019 17:12:41 -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 57779 invoked by uid 89); 13 Nov 2019 17:12:41 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT autolearn=ham version=3.3.1 spammy=Meet, guy, vr X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-1.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (207.211.31.81) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 13 Nov 2019 17:12:30 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1573665148; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type; bh=Q0rsEe/MUDLcYusOKUuyp1TN/L1R6oVwgPLTpwoTFZU=; b=MB/EyhvG7sU9OZ8w2+2HNizsMtrC7LQRHsmxRa3CgYNeNYMQN+w2YZFsCvHdGCZF55W/ld +h8JB1TXLVa7yZ3Y2+fc57avgKqvVwNEKYRSIUy3jmgpN1bfMP333lT8IVDy9ELxobSqjd WNsQbDzDM8ms6hDt0IDOQZK6rlquNww= Received: from mail-wr1-f71.google.com (mail-wr1-f71.google.com [209.85.221.71]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-233-Tc5WZe3GOriC_ou7RUVY_g-1; Wed, 13 Nov 2019 12:12:24 -0500 Received: by mail-wr1-f71.google.com with SMTP id k15so1925299wrp.22 for ; Wed, 13 Nov 2019 09:12:24 -0800 (PST) Received: from abulafia.quesejoda.com (149.red-81-32-135.dynamicip.rima-tde.net. [81.32.135.149]) by smtp.gmail.com with ESMTPSA id k125sm3366706wmf.2.2019.11.13.09.12.21 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 13 Nov 2019 09:12:21 -0800 (PST) To: Andrew MacLeod , gcc-patches From: Aldy Hernandez Subject: extract independent value_range bits to value-range.cc Message-ID: Date: Wed, 13 Nov 2019 18:12:20 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101 Thunderbird/68.2.0 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-IsSubscribed: yes tree-vrp.* is large and difficult to follow, in part because it has a hodgepodge of different interdependent things (value ranges bits, equivalences stuff, actual value range propagation things, etc etc). This patch pulls out the value_range functionality into its own files: value-range.h and value-range.cc. There are no functional changes, but I did shuffle the order of functions around for easier reading. While the old tree-vrp.c had everything spread out, the new value-range.cc file has functions grouped more or less by functionality (constructors first, setters next, predicates next, etc). I did pull out vrp_val* and vrp_operand_equal* because value_range depends on it. I didn't change the name to avoid churn. OK pending tests? Aldy commit 8ccfc09bf5b663b1a309ea5f404b92d6bcfa0f0b Author: Aldy Hernandez Date: Wed Nov 13 17:17:21 2019 +0100 Move plain value_range things to value-range.[hc]*. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 004711204a8..9b555e7a8b9 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,26 @@ 2019-11-13 Aldy Hernandez + * Makefile.in (OBJS): Add value-range.o. + (GTFILES): Add value-range.h. + * gengtype.c (open_base_files): Add value-range.h to list of + header files. + * tree-vrp.c: Move the following value_range related functions: + ranges_from_anti_range, value_range, check, equal_p, symbolic_p, + constant_p, set_undefined, set_varying, may_contain_p, + singleton_p, type, dump, dump_value_range, debug, vrp_val_max, + vrp_val_min, vrp_val_is_min, vrp_val_is_max, set, set_nonzero, + set_zero, vrp_operand_equal_p, range_has_numeric_bounds_p, + value_inside_range, ranges_from_anti_range, union_ranges, + intersect_ranges, intersect_helper, union_helper, union_, + normalize_addresses, normalize_symbolics, num_pairs, lower_bound, + upper_bound, contains_p, invert, intersect... + * value-range.cc: ...to here. + * tree-vrp.h: Move class value_range, enum_value_range_kind, and + associated inline methods from here... + * value-range.h: ...to here. + +(2019-11-13 Aldy Hernandez + * gimple-fold.c (size_must_be_zero_p): Rewrite use of value_range constructors and set methods so value_range_kind is the last argument and defaults to VR_RANGE. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 0004d46b93d..7d3c13230e4 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1602,6 +1602,7 @@ OBJS = \ typed-splay-tree.o \ unique-ptr-tests.o \ valtrack.o \ + value-range.o \ value-prof.o \ var-tracking.o \ varasm.o \ @@ -2589,6 +2590,7 @@ GTFILES = $(CPPLIB_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/target-globals.h \ $(srcdir)/ipa-predicate.h \ $(srcdir)/ipa-fnsummary.h \ + $(srcdir)/value-range.h \ $(srcdir)/vtable-verify.c \ $(srcdir)/asan.c \ $(srcdir)/ubsan.c \ diff --git a/gcc/gengtype.c b/gcc/gengtype.c index 53317337cf8..fa95776876d 100644 --- a/gcc/gengtype.c +++ b/gcc/gengtype.c @@ -1717,6 +1717,7 @@ open_base_files (void) "explow.h", "calls.h", "memmodel.h", "emit-rtl.h", "varasm.h", "stmt.h", "expr.h", "alloc-pool.h", "cselib.h", "insn-addr.h", "optabs.h", "libfuncs.h", "debug.h", "internal-fn.h", "gimple-fold.h", + "value-range.h", "tree-eh.h", "gimple-iterator.h", "gimple-ssa.h", "tree-cfg.h", "tree-vrp.h", "tree-phinodes.h", "ssa-iterators.h", "stringpool.h", "tree-ssanames.h", "tree-ssa-loop.h", "tree-ssa-loop-ivopts.h", diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 610b65dedec..c47c65bd294 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -68,10 +68,6 @@ along with GCC; see the file COPYING3. If not see #include "builtins.h" #include "range-op.h" -static bool -ranges_from_anti_range (const value_range *ar, - value_range *vr0, value_range *vr1); - /* Set of SSA names found live during the RPO traversal of the function for still active basic-blocks. */ static sbitmap *live; @@ -111,11 +107,6 @@ value_range_equiv::set (tree min, tree max, bitmap equiv, check (); } -value_range::value_range (tree min, tree max, value_range_kind kind) -{ - set (min, max, kind); -} - value_range_equiv::value_range_equiv (tree min, tree max, bitmap equiv, value_range_kind kind) { @@ -129,21 +120,6 @@ value_range_equiv::value_range_equiv (const value_range &other) set (other.min(), other.max (), NULL, other.kind ()); } -value_range::value_range (tree type) -{ - set_varying (type); -} - -value_range::value_range (tree type, - const wide_int &wmin, const wide_int &wmax, - enum value_range_kind kind) -{ - tree min = wide_int_to_tree (type, wmin); - tree max = wide_int_to_tree (type, wmax); - gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE); - set (min, max, kind); -} - /* Like set, but keep the equivalences in place. */ void @@ -173,42 +149,6 @@ value_range_equiv::move (value_range_equiv *from) from->m_equiv = NULL; } -/* Check the validity of the range. */ - -void -value_range::check () -{ - switch (m_kind) - { - case VR_RANGE: - case VR_ANTI_RANGE: - { - int cmp; - - gcc_assert (m_min && m_max); - - gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max)); - - /* Creating ~[-MIN, +MAX] is stupid because that would be - the empty set. */ - if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE) - gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max)); - - cmp = compare_values (m_min, m_max); - gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); - break; - } - case VR_UNDEFINED: - gcc_assert (!min () && !max ()); - break; - case VR_VARYING: - gcc_assert (m_min && m_max); - break; - default: - gcc_unreachable (); - } -} - void value_range_equiv::check () { @@ -222,22 +162,6 @@ value_range_equiv::check () } } -/* Equality operator. We purposely do not overload ==, to avoid - confusion with the equality bitmap in the derived value_range - class. */ - -bool -value_range::equal_p (const value_range &other) const -{ - /* Ignore types for undefined. All undefines are equal. */ - if (undefined_p ()) - return m_kind == other.m_kind; - - return (m_kind == other.m_kind - && vrp_operand_equal_p (m_min, other.m_min) - && vrp_operand_equal_p (m_max, other.m_max)); -} - /* Return true if the bitmaps B1 and B2 are equal. */ static bool @@ -262,58 +186,12 @@ value_range_equiv::equal_p (const value_range_equiv &other, || vrp_bitmap_equal_p (m_equiv, other.m_equiv))); } -/* Return TRUE if this is a symbolic range. */ - -bool -value_range::symbolic_p () const -{ - return (!varying_p () - && !undefined_p () - && (!is_gimple_min_invariant (m_min) - || !is_gimple_min_invariant (m_max))); -} - -/* NOTE: This is not the inverse of symbolic_p because the range - could also be varying or undefined. Ideally they should be inverse - of each other, with varying only applying to symbolics. Varying of - constants would be represented as [-MIN, +MAX]. */ - -bool -value_range::constant_p () const -{ - return (!varying_p () - && !undefined_p () - && TREE_CODE (m_min) == INTEGER_CST - && TREE_CODE (m_max) == INTEGER_CST); -} - -void -value_range::set_undefined () -{ - m_kind = VR_UNDEFINED; - m_min = m_max = NULL; -} - void value_range_equiv::set_undefined () { set (NULL, NULL, NULL, VR_UNDEFINED); } -void -value_range::set_varying (tree type) -{ - m_kind = VR_VARYING; - if (supports_type_p (type)) - { - m_min = vrp_val_min (type); - m_max = vrp_val_max (type); - } - else - /* We can't do anything range-wise with these types. */ - m_min = m_max = error_mark_node; -} - void value_range_equiv::set_varying (tree type) { @@ -321,14 +199,6 @@ value_range_equiv::set_varying (tree type) equiv_clear (); } -/* Return TRUE if it is possible that range contains VAL. */ - -bool -value_range::may_contain_p (tree val) const -{ - return value_inside_range (val) != 0; -} - void value_range_equiv::equiv_clear () { @@ -356,98 +226,6 @@ value_range_equiv::equiv_add (const_tree var, bitmap_ior_into (m_equiv, var_vr->m_equiv); } -/* If range is a singleton, place it in RESULT and return TRUE. - Note: A singleton can be any gimple invariant, not just constants. - So, [&x, &x] counts as a singleton. */ - -bool -value_range::singleton_p (tree *result) const -{ - if (m_kind == VR_ANTI_RANGE) - { - if (nonzero_p ()) - { - if (TYPE_PRECISION (type ()) == 1) - { - if (result) - *result = m_max; - return true; - } - return false; - } - if (num_pairs () == 1) - { - value_range vr0, vr1; - ranges_from_anti_range (this, &vr0, &vr1); - return vr0.singleton_p (result); - } - } - if (m_kind == VR_RANGE - && vrp_operand_equal_p (min (), max ()) - && is_gimple_min_invariant (min ())) - { - if (result) - *result = min (); - return true; - } - return false; -} - -tree -value_range::type () const -{ - gcc_checking_assert (m_min); - return TREE_TYPE (min ()); -} - -void -value_range::dump (FILE *file) const -{ - if (undefined_p ()) - fprintf (file, "UNDEFINED"); - else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE) - { - tree ttype = type (); - - print_generic_expr (file, ttype); - fprintf (file, " "); - - fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : ""); - - if (INTEGRAL_TYPE_P (ttype) - && !TYPE_UNSIGNED (ttype) - && vrp_val_is_min (min ()) - && TYPE_PRECISION (ttype) != 1) - fprintf (file, "-INF"); - else - print_generic_expr (file, min ()); - - fprintf (file, ", "); - - if (supports_type_p (ttype) - && vrp_val_is_max (max ()) - && TYPE_PRECISION (ttype) != 1) - fprintf (file, "+INF"); - else - print_generic_expr (file, max ()); - - fprintf (file, "]"); - } - else if (varying_p ()) - { - print_generic_expr (file, type ()); - fprintf (file, " VARYING"); - } - else - gcc_unreachable (); -} - -void -value_range::dump () const -{ - dump (stderr); -} - void value_range_equiv::dump (FILE *file) const { @@ -486,27 +264,6 @@ dump_value_range (FILE *file, const value_range_equiv *vr) vr->dump (file); } -void -dump_value_range (FILE *file, const value_range *vr) -{ - if (!vr) - fprintf (file, "[]"); - else - vr->dump (file); -} - -DEBUG_FUNCTION void -debug (const value_range *vr) -{ - dump_value_range (stderr, vr); -} - -DEBUG_FUNCTION void -debug (const value_range &vr) -{ - dump_value_range (stderr, &vr); -} - DEBUG_FUNCTION void debug (const value_range_equiv *vr) { @@ -567,58 +324,6 @@ static bitmap need_assert_for; ASSERT_EXPRs for SSA name N_I should be inserted. */ static assert_locus **asserts_for; -/* Return the maximum value for TYPE. */ - -tree -vrp_val_max (const_tree type) -{ - if (INTEGRAL_TYPE_P (type)) - return TYPE_MAX_VALUE (type); - if (POINTER_TYPE_P (type)) - { - wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); - return wide_int_to_tree (const_cast (type), max); - } - return NULL_TREE; -} - -/* Return the minimum value for TYPE. */ - -tree -vrp_val_min (const_tree type) -{ - if (INTEGRAL_TYPE_P (type)) - return TYPE_MIN_VALUE (type); - if (POINTER_TYPE_P (type)) - return build_zero_cst (const_cast (type)); - return NULL_TREE; -} - -/* Return whether VAL is equal to the maximum value of its type. - We can't do a simple equality comparison with TYPE_MAX_VALUE because - C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE - is not == to the integer constant with the same value in the type. */ - -bool -vrp_val_is_max (const_tree val) -{ - tree type_max = vrp_val_max (TREE_TYPE (val)); - return (val == type_max - || (type_max != NULL_TREE - && operand_equal_p (val, type_max, 0))); -} - -/* Return whether VAL is equal to the minimum value of its type. */ - -bool -vrp_val_is_min (const_tree val) -{ - tree type_min = vrp_val_min (TREE_TYPE (val)); - return (val == type_min - || (type_min != NULL_TREE - && operand_equal_p (val, type_min, 0))); -} - /* VR_TYPE describes a range with mininum value *MIN and maximum value *MAX. Restrict the range to the set of values that have no bits set outside NONZERO_BITS. Update *MIN and *MAX and @@ -691,184 +396,6 @@ intersect_range_with_nonzero_bits (enum value_range_kind vr_type, return vr_type; } - -/* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}. - This means adjusting VRTYPE, MIN and MAX representing the case of a - wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX] - as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges. - In corner cases where MAX+1 or MIN-1 wraps this will fall back - to varying. - This routine exists to ease canonicalization in the case where we - extract ranges from var + CST op limit. */ - -void -value_range::set (tree min, tree max, value_range_kind kind) -{ - /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */ - if (kind == VR_UNDEFINED) - { - set_undefined (); - return; - } - else if (kind == VR_VARYING) - { - gcc_assert (TREE_TYPE (min) == TREE_TYPE (max)); - tree typ = TREE_TYPE (min); - if (supports_type_p (typ)) - { - gcc_assert (vrp_val_min (typ)); - gcc_assert (vrp_val_max (typ)); - } - set_varying (typ); - return; - } - - /* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */ - if (POLY_INT_CST_P (min)) - { - tree type_min = vrp_val_min (TREE_TYPE (min)); - widest_int lb - = constant_lower_bound_with_limit (wi::to_poly_widest (min), - wi::to_widest (type_min)); - min = wide_int_to_tree (TREE_TYPE (min), lb); - } - if (POLY_INT_CST_P (max)) - { - tree type_max = vrp_val_max (TREE_TYPE (max)); - widest_int ub - = constant_upper_bound_with_limit (wi::to_poly_widest (max), - wi::to_widest (type_max)); - max = wide_int_to_tree (TREE_TYPE (max), ub); - } - - /* Nothing to canonicalize for symbolic ranges. */ - if (TREE_CODE (min) != INTEGER_CST - || TREE_CODE (max) != INTEGER_CST) - { - m_kind = kind; - m_min = min; - m_max = max; - return; - } - - /* Wrong order for min and max, to swap them and the VR type we need - to adjust them. */ - if (tree_int_cst_lt (max, min)) - { - tree one, tmp; - - /* For one bit precision if max < min, then the swapped - range covers all values, so for VR_RANGE it is varying and - for VR_ANTI_RANGE empty range, so drop to varying as well. */ - if (TYPE_PRECISION (TREE_TYPE (min)) == 1) - { - set_varying (TREE_TYPE (min)); - return; - } - - one = build_int_cst (TREE_TYPE (min), 1); - tmp = int_const_binop (PLUS_EXPR, max, one); - max = int_const_binop (MINUS_EXPR, min, one); - min = tmp; - - /* There's one corner case, if we had [C+1, C] before we now have - that again. But this represents an empty value range, so drop - to varying in this case. */ - if (tree_int_cst_lt (max, min)) - { - set_varying (TREE_TYPE (min)); - return; - } - - kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE; - } - - tree type = TREE_TYPE (min); - - /* Anti-ranges that can be represented as ranges should be so. */ - if (kind == VR_ANTI_RANGE) - { - /* For -fstrict-enums we may receive out-of-range ranges so consider - values < -INF and values > INF as -INF/INF as well. */ - bool is_min = vrp_val_is_min (min); - bool is_max = vrp_val_is_max (max); - - if (is_min && is_max) - { - /* We cannot deal with empty ranges, drop to varying. - ??? This could be VR_UNDEFINED instead. */ - set_varying (type); - return; - } - else if (TYPE_PRECISION (TREE_TYPE (min)) == 1 - && (is_min || is_max)) - { - /* Non-empty boolean ranges can always be represented - as a singleton range. */ - if (is_min) - min = max = vrp_val_max (TREE_TYPE (min)); - else - min = max = vrp_val_min (TREE_TYPE (min)); - kind = VR_RANGE; - } - else if (is_min) - { - tree one = build_int_cst (TREE_TYPE (max), 1); - min = int_const_binop (PLUS_EXPR, max, one); - max = vrp_val_max (TREE_TYPE (max)); - kind = VR_RANGE; - } - else if (is_max) - { - tree one = build_int_cst (TREE_TYPE (min), 1); - max = int_const_binop (MINUS_EXPR, min, one); - min = vrp_val_min (TREE_TYPE (min)); - kind = VR_RANGE; - } - } - - /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED. - - Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can - restrict those to a subset of what actually fits in the type. - Instead use the extremes of the type precision which will allow - compare_range_with_value() to check if a value is inside a range, - whereas if we used TYPE_*_VAL, said function would just punt - upon seeing a VARYING. */ - unsigned prec = TYPE_PRECISION (type); - signop sign = TYPE_SIGN (type); - if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign)) - && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign))) - { - if (kind == VR_RANGE) - set_varying (type); - else if (kind == VR_ANTI_RANGE) - set_undefined (); - else - gcc_unreachable (); - return; - } - - /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky - to make sure VRP iteration terminates, otherwise we can get into - oscillations. */ - - m_kind = kind; - m_min = min; - m_max = max; - if (flag_checking) - check (); -} - -void -value_range::set (tree val) -{ - gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val)); - if (TREE_OVERFLOW_P (val)) - val = drop_tree_overflow (val); - set (val, val); -} - void value_range_equiv::set (tree val) { @@ -878,43 +405,6 @@ value_range_equiv::set (tree val) set (val, val); } -/* Set value range VR to a nonzero range of type TYPE. */ - -void -value_range::set_nonzero (tree type) -{ - tree zero = build_int_cst (type, 0); - set (zero, zero, VR_ANTI_RANGE); -} - -/* Set value range VR to a ZERO range of type TYPE. */ - -void -value_range::set_zero (tree type) -{ - set (build_int_cst (type, 0)); -} - -/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ - -bool -vrp_operand_equal_p (const_tree val1, const_tree val2) -{ - if (val1 == val2) - return true; - if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) - return false; - return true; -} - -static bool -range_has_numeric_bounds_p (const value_range *vr) -{ - return (vr->min () - && TREE_CODE (vr->min ()) == INTEGER_CST - && TREE_CODE (vr->max ()) == INTEGER_CST); -} - /* Return true if max and min of VR are INTEGER_CST. It's not necessary a singleton. */ @@ -1210,91 +700,17 @@ compare_values (tree val1, tree val2) return compare_values_warnv (val1, val2, &sop); } +/* If BOUND will include a symbolic bound, adjust it accordingly, + otherwise leave it as is. -/* Return 1 if VAL is inside value range. - 0 if VAL is not inside value range. - -2 if we cannot tell either way. - - Benchmark compile/20001226-1.c compilation time after changing this - function. */ - -int -value_range::value_inside_range (tree val) const -{ - int cmp1, cmp2; + CODE is the original operation that combined the bounds (PLUS_EXPR + or MINUS_EXPR). - if (varying_p ()) - return 1; + TYPE is the type of the original operation. - if (undefined_p ()) - return 0; + SYM_OPn is the symbolic for OPn if it has a symbolic. - cmp1 = operand_less_p (val, m_min); - if (cmp1 == -2) - return -2; - if (cmp1 == 1) - return m_kind != VR_RANGE; - - cmp2 = operand_less_p (m_max, val); - if (cmp2 == -2) - return -2; - - if (m_kind == VR_RANGE) - return !cmp2; - else - return !!cmp2; -} - -/* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR - so that *VR0 U *VR1 == *AR. Returns true if that is possible, - false otherwise. If *AR can be represented with a single range - *VR1 will be VR_UNDEFINED. */ - -static bool -ranges_from_anti_range (const value_range *ar, - value_range *vr0, value_range *vr1) -{ - tree type = ar->type (); - - vr0->set_undefined (); - vr1->set_undefined (); - - /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U - [A+1, +INF]. Not sure if this helps in practice, though. */ - - if (ar->kind () != VR_ANTI_RANGE - || TREE_CODE (ar->min ()) != INTEGER_CST - || TREE_CODE (ar->max ()) != INTEGER_CST - || !vrp_val_min (type) - || !vrp_val_max (type)) - return false; - - if (tree_int_cst_lt (vrp_val_min (type), ar->min ())) - vr0->set (vrp_val_min (type), - wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1)); - if (tree_int_cst_lt (ar->max (), vrp_val_max (type))) - vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1), - vrp_val_max (type)); - if (vr0->undefined_p ()) - { - *vr0 = *vr1; - vr1->set_undefined (); - } - - return !vr0->undefined_p (); -} - -/* If BOUND will include a symbolic bound, adjust it accordingly, - otherwise leave it as is. - - CODE is the original operation that combined the bounds (PLUS_EXPR - or MINUS_EXPR). - - TYPE is the type of the original operation. - - SYM_OPn is the symbolic for OPn if it has a symbolic. - - NEG_OPn is TRUE if the OPn was negated. */ + NEG_OPn is TRUE if the OPn was negated. */ static void adjust_symbolic_bound (tree &bound, enum tree_code code, tree type, @@ -5224,669 +4640,6 @@ vrp_prop::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; } -/* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and - { VR1TYPE, VR0MIN, VR0MAX } and store the result - in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest - possible such range. The resulting range is not canonicalized. */ - -static void -union_ranges (enum value_range_kind *vr0type, - tree *vr0min, tree *vr0max, - enum value_range_kind vr1type, - tree vr1min, tree vr1max) -{ - int cmpmin = compare_values (*vr0min, vr1min); - int cmpmax = compare_values (*vr0max, vr1max); - bool mineq = cmpmin == 0; - bool maxeq = cmpmax == 0; - - /* [] is vr0, () is vr1 in the following classification comments. */ - if (mineq && maxeq) - { - /* [( )] */ - if (*vr0type == vr1type) - /* Nothing to do for equal ranges. */ - ; - else if ((*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - || (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE)) - { - /* For anti-range with range union the result is varying. */ - goto give_up; - } - else - gcc_unreachable (); - } - else if (operand_less_p (*vr0max, vr1min) == 1 - || operand_less_p (vr1max, *vr0min) == 1) - { - /* [ ] ( ) or ( ) [ ] - If the ranges have an empty intersection, result of the union - operation is the anti-range or if both are anti-ranges - it covers all. */ - if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - goto give_up; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - ; - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - { - /* The result is the convex hull of both ranges. */ - if (operand_less_p (*vr0max, vr1min) == 1) - { - /* If the result can be an anti-range, create one. */ - if (TREE_CODE (*vr0max) == INTEGER_CST - && TREE_CODE (vr1min) == INTEGER_CST - && vrp_val_is_min (*vr0min) - && vrp_val_is_max (vr1max)) - { - tree min = int_const_binop (PLUS_EXPR, - *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - tree max = int_const_binop (MINUS_EXPR, - vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - if (!operand_less_p (max, min)) - { - *vr0type = VR_ANTI_RANGE; - *vr0min = min; - *vr0max = max; - } - else - *vr0max = vr1max; - } - else - *vr0max = vr1max; - } - else - { - /* If the result can be an anti-range, create one. */ - if (TREE_CODE (vr1max) == INTEGER_CST - && TREE_CODE (*vr0min) == INTEGER_CST - && vrp_val_is_min (vr1min) - && vrp_val_is_max (*vr0max)) - { - tree min = int_const_binop (PLUS_EXPR, - vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - tree max = int_const_binop (MINUS_EXPR, - *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - if (!operand_less_p (max, min)) - { - *vr0type = VR_ANTI_RANGE; - *vr0min = min; - *vr0max = max; - } - else - *vr0min = vr1min; - } - else - *vr0min = vr1min; - } - } - else - gcc_unreachable (); - } - else if ((maxeq || cmpmax == 1) - && (mineq || cmpmin == -1)) - { - /* [ ( ) ] or [( ) ] or [ ( )] */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - ; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - /* Arbitrarily choose the right or left gap. */ - if (!mineq && TREE_CODE (vr1min) == INTEGER_CST) - *vr0max = int_const_binop (MINUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST) - *vr0min = int_const_binop (PLUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - else - goto give_up; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - /* The result covers everything. */ - goto give_up; - else - gcc_unreachable (); - } - else if ((maxeq || cmpmax == -1) - && (mineq || cmpmin == 1)) - { - /* ( [ ] ) or ([ ] ) or ( [ ]) */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - ; - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - *vr0type = VR_ANTI_RANGE; - if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST) - { - *vr0max = int_const_binop (MINUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - *vr0min = vr1min; - } - else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST) - { - *vr0min = int_const_binop (PLUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - *vr0max = vr1max; - } - else - goto give_up; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - /* The result covers everything. */ - goto give_up; - else - gcc_unreachable (); - } - else if (cmpmin == -1 - && cmpmax == -1 - && (operand_less_p (vr1min, *vr0max) == 1 - || operand_equal_p (vr1min, *vr0max, 0))) - { - /* [ ( ] ) or [ ]( ) */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - *vr0max = vr1max; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - *vr0min = vr1min; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - if (TREE_CODE (vr1min) == INTEGER_CST) - *vr0max = int_const_binop (MINUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - else - goto give_up; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - if (TREE_CODE (*vr0max) == INTEGER_CST) - { - *vr0type = vr1type; - *vr0min = int_const_binop (PLUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - *vr0max = vr1max; - } - else - goto give_up; - } - else - gcc_unreachable (); - } - else if (cmpmin == 1 - && cmpmax == 1 - && (operand_less_p (*vr0min, vr1max) == 1 - || operand_equal_p (*vr0min, vr1max, 0))) - { - /* ( [ ) ] or ( )[ ] */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - *vr0min = vr1min; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - *vr0max = vr1max; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - if (TREE_CODE (vr1max) == INTEGER_CST) - *vr0min = int_const_binop (PLUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - else - goto give_up; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - if (TREE_CODE (*vr0min) == INTEGER_CST) - { - *vr0type = vr1type; - *vr0max = int_const_binop (MINUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - *vr0min = vr1min; - } - else - goto give_up; - } - else - gcc_unreachable (); - } - else - goto give_up; - - return; - -give_up: - *vr0type = VR_VARYING; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; -} - -/* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and - { VR1TYPE, VR0MIN, VR0MAX } and store the result - in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest - possible such range. The resulting range is not canonicalized. */ - -static void -intersect_ranges (enum value_range_kind *vr0type, - tree *vr0min, tree *vr0max, - enum value_range_kind vr1type, - tree vr1min, tree vr1max) -{ - bool mineq = vrp_operand_equal_p (*vr0min, vr1min); - bool maxeq = vrp_operand_equal_p (*vr0max, vr1max); - - /* [] is vr0, () is vr1 in the following classification comments. */ - if (mineq && maxeq) - { - /* [( )] */ - if (*vr0type == vr1type) - /* Nothing to do for equal ranges. */ - ; - else if ((*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - || (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE)) - { - /* For anti-range with range intersection the result is empty. */ - *vr0type = VR_UNDEFINED; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; - } - else - gcc_unreachable (); - } - else if (operand_less_p (*vr0max, vr1min) == 1 - || operand_less_p (vr1max, *vr0min) == 1) - { - /* [ ] ( ) or ( ) [ ] - If the ranges have an empty intersection, the result of the - intersect operation is the range for intersecting an - anti-range with a range or empty when intersecting two ranges. */ - if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - ; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - { - *vr0type = VR_UNDEFINED; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - { - /* If the anti-ranges are adjacent to each other merge them. */ - if (TREE_CODE (*vr0max) == INTEGER_CST - && TREE_CODE (vr1min) == INTEGER_CST - && operand_less_p (*vr0max, vr1min) == 1 - && integer_onep (int_const_binop (MINUS_EXPR, - vr1min, *vr0max))) - *vr0max = vr1max; - else if (TREE_CODE (vr1max) == INTEGER_CST - && TREE_CODE (*vr0min) == INTEGER_CST - && operand_less_p (vr1max, *vr0min) == 1 - && integer_onep (int_const_binop (MINUS_EXPR, - *vr0min, vr1max))) - *vr0min = vr1min; - /* Else arbitrarily take VR0. */ - } - } - else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1) - && (mineq || operand_less_p (*vr0min, vr1min) == 1)) - { - /* [ ( ) ] or [( ) ] or [ ( )] */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - { - /* If both are ranges the result is the inner one. */ - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - /* Choose the right gap if the left one is empty. */ - if (mineq) - { - if (TREE_CODE (vr1max) != INTEGER_CST) - *vr0min = vr1max; - else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1 - && !TYPE_UNSIGNED (TREE_TYPE (vr1max))) - *vr0min - = int_const_binop (MINUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), -1)); - else - *vr0min - = int_const_binop (PLUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - } - /* Choose the left gap if the right one is empty. */ - else if (maxeq) - { - if (TREE_CODE (vr1min) != INTEGER_CST) - *vr0max = vr1min; - else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1 - && !TYPE_UNSIGNED (TREE_TYPE (vr1min))) - *vr0max - = int_const_binop (PLUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), -1)); - else - *vr0max - = int_const_binop (MINUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - } - /* Choose the anti-range if the range is effectively varying. */ - else if (vrp_val_is_min (*vr0min) - && vrp_val_is_max (*vr0max)) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - /* Else choose the range. */ - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - /* If both are anti-ranges the result is the outer one. */ - ; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - /* The intersection is empty. */ - *vr0type = VR_UNDEFINED; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; - } - else - gcc_unreachable (); - } - else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1) - && (mineq || operand_less_p (vr1min, *vr0min) == 1)) - { - /* ( [ ] ) or ([ ] ) or ( [ ]) */ - if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - /* Choose the inner range. */ - ; - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - /* Choose the right gap if the left is empty. */ - if (mineq) - { - *vr0type = VR_RANGE; - if (TREE_CODE (*vr0max) != INTEGER_CST) - *vr0min = *vr0max; - else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1 - && !TYPE_UNSIGNED (TREE_TYPE (*vr0max))) - *vr0min - = int_const_binop (MINUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), -1)); - else - *vr0min - = int_const_binop (PLUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - *vr0max = vr1max; - } - /* Choose the left gap if the right is empty. */ - else if (maxeq) - { - *vr0type = VR_RANGE; - if (TREE_CODE (*vr0min) != INTEGER_CST) - *vr0max = *vr0min; - else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1 - && !TYPE_UNSIGNED (TREE_TYPE (*vr0min))) - *vr0max - = int_const_binop (PLUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), -1)); - else - *vr0max - = int_const_binop (MINUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - *vr0min = vr1min; - } - /* Choose the anti-range if the range is effectively varying. */ - else if (vrp_val_is_min (vr1min) - && vrp_val_is_max (vr1max)) - ; - /* Choose the anti-range if it is ~[0,0], that range is special - enough to special case when vr1's range is relatively wide. - At least for types bigger than int - this covers pointers - and arguments to functions like ctz. */ - else if (*vr0min == *vr0max - && integer_zerop (*vr0min) - && ((TYPE_PRECISION (TREE_TYPE (*vr0min)) - >= TYPE_PRECISION (integer_type_node)) - || POINTER_TYPE_P (TREE_TYPE (*vr0min))) - && TREE_CODE (vr1max) == INTEGER_CST - && TREE_CODE (vr1min) == INTEGER_CST - && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min)) - < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2)) - ; - /* Else choose the range. */ - else - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - { - /* If both are anti-ranges the result is the outer one. */ - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } - else if (vr1type == VR_ANTI_RANGE - && *vr0type == VR_RANGE) - { - /* The intersection is empty. */ - *vr0type = VR_UNDEFINED; - *vr0min = NULL_TREE; - *vr0max = NULL_TREE; - } - else - gcc_unreachable (); - } - else if ((operand_less_p (vr1min, *vr0max) == 1 - || operand_equal_p (vr1min, *vr0max, 0)) - && operand_less_p (*vr0min, vr1min) == 1) - { - /* [ ( ] ) or [ ]( ) */ - if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - *vr0max = vr1max; - else if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - *vr0min = vr1min; - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - if (TREE_CODE (vr1min) == INTEGER_CST) - *vr0max = int_const_binop (MINUS_EXPR, vr1min, - build_int_cst (TREE_TYPE (vr1min), 1)); - else - *vr0max = vr1min; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - *vr0type = VR_RANGE; - if (TREE_CODE (*vr0max) == INTEGER_CST) - *vr0min = int_const_binop (PLUS_EXPR, *vr0max, - build_int_cst (TREE_TYPE (*vr0max), 1)); - else - *vr0min = *vr0max; - *vr0max = vr1max; - } - else - gcc_unreachable (); - } - else if ((operand_less_p (*vr0min, vr1max) == 1 - || operand_equal_p (*vr0min, vr1max, 0)) - && operand_less_p (vr1min, *vr0min) == 1) - { - /* ( [ ) ] or ( )[ ] */ - if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_ANTI_RANGE) - *vr0min = vr1min; - else if (*vr0type == VR_RANGE - && vr1type == VR_RANGE) - *vr0max = vr1max; - else if (*vr0type == VR_RANGE - && vr1type == VR_ANTI_RANGE) - { - if (TREE_CODE (vr1max) == INTEGER_CST) - *vr0min = int_const_binop (PLUS_EXPR, vr1max, - build_int_cst (TREE_TYPE (vr1max), 1)); - else - *vr0min = vr1max; - } - else if (*vr0type == VR_ANTI_RANGE - && vr1type == VR_RANGE) - { - *vr0type = VR_RANGE; - if (TREE_CODE (*vr0min) == INTEGER_CST) - *vr0max = int_const_binop (MINUS_EXPR, *vr0min, - build_int_cst (TREE_TYPE (*vr0min), 1)); - else - *vr0max = *vr0min; - *vr0min = vr1min; - } - else - gcc_unreachable (); - } - - /* If we know the intersection is empty, there's no need to - conservatively add anything else to the set. */ - if (*vr0type == VR_UNDEFINED) - return; - - /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as - result for the intersection. That's always a conservative - correct estimate unless VR1 is a constant singleton range - in which case we choose that. */ - if (vr1type == VR_RANGE - && is_gimple_min_invariant (vr1min) - && vrp_operand_equal_p (vr1min, vr1max)) - { - *vr0type = vr1type; - *vr0min = vr1min; - *vr0max = vr1max; - } -} - - -/* Helper for the intersection operation for value ranges. Given two - value ranges VR0 and VR1, return the intersection of the two - ranges. This may not be the smallest possible such range. */ - -value_range -value_range::intersect_helper (const value_range *vr0, const value_range *vr1) -{ - /* If either range is VR_VARYING the other one wins. */ - if (vr1->varying_p ()) - return *vr0; - if (vr0->varying_p ()) - return *vr1; - - /* When either range is VR_UNDEFINED the resulting range is - VR_UNDEFINED, too. */ - if (vr0->undefined_p ()) - return *vr0; - if (vr1->undefined_p ()) - return *vr1; - - value_range_kind vr0kind = vr0->kind (); - tree vr0min = vr0->min (); - tree vr0max = vr0->max (); - intersect_ranges (&vr0kind, &vr0min, &vr0max, - vr1->kind (), vr1->min (), vr1->max ()); - /* Make sure to canonicalize the result though as the inversion of a - VR_RANGE can still be a VR_RANGE. Work on a temporary so we can - fall back to vr0 when this turns things to varying. */ - value_range tem; - if (vr0kind == VR_UNDEFINED) - tem.set_undefined (); - else if (vr0kind == VR_VARYING) - tem.set_varying (vr0->type ()); - else - tem.set (vr0min, vr0max, vr0kind); - /* If that failed, use the saved original VR0. */ - if (tem.varying_p ()) - return *vr0; - - return tem; -} - -void -value_range::intersect (const value_range *other) -{ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Intersecting\n "); - dump_value_range (dump_file, this); - fprintf (dump_file, "\nand\n "); - dump_value_range (dump_file, other); - fprintf (dump_file, "\n"); - } - - *this = intersect_helper (this, other); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "to\n "); - dump_value_range (dump_file, this); - fprintf (dump_file, "\n"); - } -} - void value_range_equiv::intersect (const value_range_equiv *other) { @@ -5936,79 +4689,6 @@ value_range_equiv::intersect (const value_range_equiv *other) } } -/* Helper for meet operation for value ranges. Given two value ranges VR0 and - VR1, return a range that contains both VR0 and VR1. This may not be the - smallest possible such range. */ - -value_range -value_range::union_helper (const value_range *vr0, const value_range *vr1) -{ - /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */ - if (vr1->undefined_p () - || vr0->varying_p ()) - return *vr0; - - /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */ - if (vr0->undefined_p () - || vr1->varying_p ()) - return *vr1; - - value_range_kind vr0kind = vr0->kind (); - tree vr0min = vr0->min (); - tree vr0max = vr0->max (); - union_ranges (&vr0kind, &vr0min, &vr0max, - vr1->kind (), vr1->min (), vr1->max ()); - - /* Work on a temporary so we can still use vr0 when union returns varying. */ - value_range tem; - if (vr0kind == VR_UNDEFINED) - tem.set_undefined (); - else if (vr0kind == VR_VARYING) - tem.set_varying (vr0->type ()); - else - tem.set (vr0min, vr0max, vr0kind); - - /* Failed to find an efficient meet. Before giving up and setting - the result to VARYING, see if we can at least derive a useful - anti-range. */ - if (tem.varying_p () - && range_includes_zero_p (vr0) == 0 - && range_includes_zero_p (vr1) == 0) - { - tem.set_nonzero (vr0->type ()); - return tem; - } - - return tem; -} - - -/* Meet operation for value ranges. Given two value ranges VR0 and - VR1, store in VR0 a range that contains both VR0 and VR1. This - may not be the smallest possible such range. */ - -void -value_range::union_ (const value_range *other) -{ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Meeting\n "); - dump_value_range (dump_file, this); - fprintf (dump_file, "\nand\n "); - dump_value_range (dump_file, other); - fprintf (dump_file, "\n"); - } - - *this = union_helper (this, other); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "to\n "); - dump_value_range (dump_file, this); - fprintf (dump_file, "\n"); - } -} - void value_range_equiv::union_ (const value_range_equiv *other) { @@ -6046,222 +4726,6 @@ value_range_equiv::union_ (const value_range_equiv *other) } } -/* Normalize addresses into constants. */ - -value_range -value_range::normalize_addresses () const -{ - if (undefined_p ()) - return *this; - - if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this)) - return *this; - - if (!range_includes_zero_p (this)) - { - gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR - || TREE_CODE (m_max) == ADDR_EXPR); - return range_nonzero (type ()); - } - return value_range (type ()); -} - -/* Normalize symbolics and addresses into constants. */ - -value_range -value_range::normalize_symbolics () const -{ - if (varying_p () || undefined_p ()) - return *this; - tree ttype = type (); - bool min_symbolic = !is_gimple_min_invariant (min ()); - bool max_symbolic = !is_gimple_min_invariant (max ()); - if (!min_symbolic && !max_symbolic) - return normalize_addresses (); - - // [SYM, SYM] -> VARYING - if (min_symbolic && max_symbolic) - { - value_range var; - var.set_varying (ttype); - return var; - } - if (kind () == VR_RANGE) - { - // [SYM, NUM] -> [-MIN, NUM] - if (min_symbolic) - return value_range (vrp_val_min (ttype), max ()); - // [NUM, SYM] -> [NUM, +MAX] - return value_range (min (), vrp_val_max (ttype)); - } - gcc_checking_assert (kind () == VR_ANTI_RANGE); - // ~[SYM, NUM] -> [NUM + 1, +MAX] - if (min_symbolic) - { - if (!vrp_val_is_max (max ())) - { - tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1); - return value_range (n, vrp_val_max (ttype)); - } - value_range var; - var.set_varying (ttype); - return var; - } - // ~[NUM, SYM] -> [-MIN, NUM - 1] - if (!vrp_val_is_min (min ())) - { - tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1); - return value_range (vrp_val_min (ttype), n); - } - value_range var; - var.set_varying (ttype); - return var; -} - -/* Return the number of sub-ranges in a range. */ - -unsigned -value_range::num_pairs () const -{ - if (undefined_p ()) - return 0; - if (varying_p ()) - return 1; - if (symbolic_p ()) - return normalize_symbolics ().num_pairs (); - if (m_kind == VR_ANTI_RANGE) - { - // ~[MIN, X] has one sub-range of [X+1, MAX], and - // ~[X, MAX] has one sub-range of [MIN, X-1]. - if (vrp_val_is_min (m_min) || vrp_val_is_max (m_max)) - return 1; - return 2; - } - return 1; -} - -/* Return the lower bound for a sub-range. PAIR is the sub-range in - question. */ - -wide_int -value_range::lower_bound (unsigned pair) const -{ - if (symbolic_p ()) - return normalize_symbolics ().lower_bound (pair); - - gcc_checking_assert (!undefined_p ()); - gcc_checking_assert (pair + 1 <= num_pairs ()); - tree t = NULL; - if (m_kind == VR_ANTI_RANGE) - { - tree typ = type (); - if (pair == 1 || vrp_val_is_min (m_min)) - t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1); - else - t = vrp_val_min (typ); - } - else - t = m_min; - return wi::to_wide (t); -} - -/* Return the upper bound for a sub-range. PAIR is the sub-range in - question. */ - -wide_int -value_range::upper_bound (unsigned pair) const -{ - if (symbolic_p ()) - return normalize_symbolics ().upper_bound (pair); - - gcc_checking_assert (!undefined_p ()); - gcc_checking_assert (pair + 1 <= num_pairs ()); - tree t = NULL; - if (m_kind == VR_ANTI_RANGE) - { - tree typ = type (); - if (pair == 1 || vrp_val_is_min (m_min)) - t = vrp_val_max (typ); - else - t = wide_int_to_tree (typ, wi::to_wide (m_min) - 1); - } - else - t = m_max; - return wi::to_wide (t); -} - -/* Return the highest bound in a range. */ - -wide_int -value_range::upper_bound () const -{ - unsigned pairs = num_pairs (); - gcc_checking_assert (pairs > 0); - return upper_bound (pairs - 1); -} - -/* Return TRUE if range contains INTEGER_CST. */ - -bool -value_range::contains_p (tree cst) const -{ - gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST); - if (symbolic_p ()) - return normalize_symbolics ().contains_p (cst); - return value_inside_range (cst) == 1; -} - -/* Return the inverse of a range. */ - -void -value_range::invert () -{ - /* We can't just invert VR_RANGE and VR_ANTI_RANGE because we may - create non-canonical ranges. Use the constructors instead. */ - if (m_kind == VR_RANGE) - *this = value_range (m_min, m_max, VR_ANTI_RANGE); - else if (m_kind == VR_ANTI_RANGE) - *this = value_range (m_min, m_max); - else - gcc_unreachable (); -} - -/* Range union, but for references. */ - -void -value_range::union_ (const value_range &r) -{ - /* Disable details for now, because it makes the ranger dump - unnecessarily verbose. */ - bool details = dump_flags & TDF_DETAILS; - if (details) - dump_flags &= ~TDF_DETAILS; - union_ (&r); - if (details) - dump_flags |= TDF_DETAILS; -} - -/* Range intersect, but for references. */ - -void -value_range::intersect (const value_range &r) -{ - /* Disable details for now, because it makes the ranger dump - unnecessarily verbose. */ - bool details = dump_flags & TDF_DETAILS; - if (details) - dump_flags &= ~TDF_DETAILS; - intersect (&r); - if (details) - dump_flags |= TDF_DETAILS; -} - -bool -value_range::operator== (const value_range &r) const -{ - return equal_p (r); -} - /* Visit all arguments for PHI node PHI that flow through executable edges. If a valid value range can be derived from all the incoming value ranges, set a new range for the LHS of PHI. */ diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index 4b0e9c7a226..81f0a7b5921 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -20,103 +20,7 @@ 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 -{ - friend void range_tests (); -public: - value_range (); - value_range (tree, tree, value_range_kind = VR_RANGE); - value_range (tree type, const wide_int &, const wide_int &, - value_range_kind = VR_RANGE); - value_range (tree type); - - void set (tree, tree, value_range_kind = VR_RANGE); - void set (tree); - void set_nonzero (tree); - void set_zero (tree); - - enum value_range_kind kind () const; - tree min () const; - tree max () const; - - /* Types of value ranges. */ - bool symbolic_p () const; - bool constant_p () const; - bool undefined_p () const; - bool varying_p () const; - void set_varying (tree type); - void set_undefined (); - - void union_ (const value_range *); - void intersect (const value_range *); - void union_ (const value_range &); - void intersect (const value_range &); - - bool operator== (const value_range &) const; - bool operator!= (const value_range &) const /* = delete */; - bool equal_p (const value_range &) const; - - /* Misc methods. */ - tree type () const; - bool may_contain_p (tree) const; - bool zero_p () const; - bool nonzero_p () const; - bool singleton_p (tree *result = NULL) const; - void dump (FILE *) const; - void dump () const; - - static bool supports_type_p (tree); - value_range normalize_symbolics () const; - value_range normalize_addresses () const; - - static const unsigned int m_max_pairs = 2; - bool contains_p (tree) const; - unsigned num_pairs () const; - wide_int lower_bound (unsigned = 0) const; - wide_int upper_bound (unsigned) const; - wide_int upper_bound () const; - void invert (); - -protected: - void check (); - static value_range union_helper (const value_range *, const value_range *); - static value_range intersect_helper (const value_range *, - const value_range *); - - enum value_range_kind m_kind; - - tree m_min; - tree m_max; - - friend void gt_ggc_mx_value_range (void *); - friend void gt_pch_p_11value_range (void *, void *, - gt_pointer_operator, void *); - friend void gt_pch_nx_value_range (void *); - friend void gt_ggc_mx (value_range &); - friend void gt_ggc_mx (value_range *&); - friend void gt_pch_nx (value_range &); - friend void gt_pch_nx (value_range *, gt_pointer_operator, void *); - -private: - int value_inside_range (tree) const; -}; +#include "value-range.h" /* Note value_range_equiv cannot currently be used with GC memory, only value_range is fully set up for this. */ @@ -173,13 +77,6 @@ class GTY((user)) value_range_equiv : public value_range bitmap m_equiv; }; -inline -value_range::value_range () -{ - m_kind = VR_UNDEFINED; - m_min = m_max = NULL; -} - inline value_range_equiv::value_range_equiv () : value_range () @@ -187,64 +84,13 @@ value_range_equiv::value_range_equiv () m_equiv = NULL; } -/* Return the kind of this range. */ - -inline value_range_kind -value_range::kind () const -{ - return m_kind; -} - inline bitmap value_range_equiv::equiv () const { return m_equiv; } -/* Return the lower bound. */ - -inline tree -value_range::min () const -{ - return m_min; -} - -/* Return the upper bound. */ - -inline tree -value_range::max () const -{ - return m_max; -} - -/* Return TRUE if range spans the entire possible domain. */ - -inline bool -value_range::varying_p () const -{ - return m_kind == VR_VARYING; -} - -/* Return TRUE if range is undefined (essentially the empty set). */ - -inline bool -value_range::undefined_p () const -{ - return m_kind == VR_UNDEFINED; -} - -/* Return TRUE if range is the constant zero. */ - -inline bool -value_range::zero_p () const -{ - return (m_kind == VR_RANGE - && integer_zerop (m_min) - && integer_zerop (m_max)); -} - extern void dump_value_range (FILE *, const value_range_equiv *); -extern void dump_value_range (FILE *, const value_range *); struct assert_info { @@ -261,17 +107,6 @@ struct assert_info tree expr; }; -// Return true if TYPE is a valid type for value_range to operate on. -// Otherwise return FALSE. - -inline bool -value_range::supports_type_p (tree type) -{ - if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))) - return type; - return false; -} - extern void register_edge_assert_for (tree, edge, enum tree_code, tree, tree, vec &); extern bool stmt_interesting_for_vrp (gimple *); @@ -282,18 +117,12 @@ extern bool range_int_cst_p (const value_range *); extern int compare_values (tree, tree); extern int compare_values_warnv (tree, tree, bool *); extern int operand_less_p (tree, tree); -extern bool vrp_val_is_min (const_tree); -extern bool vrp_val_is_max (const_tree); - -extern tree vrp_val_min (const_tree); -extern tree vrp_val_max (const_tree); void range_fold_unary_expr (value_range *, enum tree_code, tree type, const value_range *, tree op0_type); void range_fold_binary_expr (value_range *, enum tree_code, tree type, const value_range *, const value_range *); -extern bool vrp_operand_equal_p (const_tree, const_tree); extern enum value_range_kind intersect_range_with_nonzero_bits (enum value_range_kind, wide_int *, wide_int *, const wide_int &, signop); @@ -304,35 +133,4 @@ extern tree get_single_symbol (tree, bool *, tree *); extern void maybe_set_nonzero_bits (edge, tree); extern value_range_kind determine_value_range (tree, wide_int *, wide_int *); -/* Return TRUE if range is nonzero. */ - -inline bool -value_range::nonzero_p () const -{ - if (m_kind == VR_ANTI_RANGE - && !TYPE_UNSIGNED (type ()) - && integer_zerop (m_min) - && integer_zerop (m_max)) - return true; - - return (m_kind == VR_RANGE - && TYPE_UNSIGNED (type ()) - && integer_onep (m_min) - && vrp_val_is_max (m_max)); -} - -/* Return TRUE if *VR includes the value zero. */ - -inline bool -range_includes_zero_p (const value_range *vr) -{ - if (vr->undefined_p ()) - return false; - - if (vr->varying_p ()) - return true; - - return vr->may_contain_p (build_zero_cst (vr->type ())); -} - #endif /* GCC_TREE_VRP_H */ diff --git a/gcc/value-range.cc b/gcc/value-range.cc new file mode 100644 index 00000000000..3d926005743 --- /dev/null +++ b/gcc/value-range.cc @@ -0,0 +1,1541 @@ +/* Support routines for value ranges. + Copyright (C) 2019 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "tree-pretty-print.h" +#include "fold-const.h" + +value_range::value_range (tree min, tree max, value_range_kind kind) +{ + set (min, max, kind); +} + +value_range::value_range (tree type) +{ + set_varying (type); +} + +value_range::value_range (tree type, + const wide_int &wmin, const wide_int &wmax, + enum value_range_kind kind) +{ + tree min = wide_int_to_tree (type, wmin); + tree max = wide_int_to_tree (type, wmax); + gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE); + set (min, max, kind); +} + +void +value_range::set_undefined () +{ + m_kind = VR_UNDEFINED; + m_min = m_max = NULL; +} + +void +value_range::set_varying (tree type) +{ + m_kind = VR_VARYING; + if (supports_type_p (type)) + { + m_min = vrp_val_min (type); + m_max = vrp_val_max (type); + } + else + /* We can't do anything range-wise with these types. */ + m_min = m_max = error_mark_node; +} + +/* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}. + This means adjusting VRTYPE, MIN and MAX representing the case of a + wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX] + as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges. + In corner cases where MAX+1 or MIN-1 wraps this will fall back + to varying. + This routine exists to ease canonicalization in the case where we + extract ranges from var + CST op limit. */ + +void +value_range::set (tree min, tree max, value_range_kind kind) +{ + /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */ + if (kind == VR_UNDEFINED) + { + set_undefined (); + return; + } + else if (kind == VR_VARYING) + { + gcc_assert (TREE_TYPE (min) == TREE_TYPE (max)); + tree typ = TREE_TYPE (min); + if (supports_type_p (typ)) + { + gcc_assert (vrp_val_min (typ)); + gcc_assert (vrp_val_max (typ)); + } + set_varying (typ); + return; + } + + /* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */ + if (POLY_INT_CST_P (min)) + { + tree type_min = vrp_val_min (TREE_TYPE (min)); + widest_int lb + = constant_lower_bound_with_limit (wi::to_poly_widest (min), + wi::to_widest (type_min)); + min = wide_int_to_tree (TREE_TYPE (min), lb); + } + if (POLY_INT_CST_P (max)) + { + tree type_max = vrp_val_max (TREE_TYPE (max)); + widest_int ub + = constant_upper_bound_with_limit (wi::to_poly_widest (max), + wi::to_widest (type_max)); + max = wide_int_to_tree (TREE_TYPE (max), ub); + } + + /* Nothing to canonicalize for symbolic ranges. */ + if (TREE_CODE (min) != INTEGER_CST + || TREE_CODE (max) != INTEGER_CST) + { + m_kind = kind; + m_min = min; + m_max = max; + return; + } + + /* Wrong order for min and max, to swap them and the VR type we need + to adjust them. */ + if (tree_int_cst_lt (max, min)) + { + tree one, tmp; + + /* For one bit precision if max < min, then the swapped + range covers all values, so for VR_RANGE it is varying and + for VR_ANTI_RANGE empty range, so drop to varying as well. */ + if (TYPE_PRECISION (TREE_TYPE (min)) == 1) + { + set_varying (TREE_TYPE (min)); + return; + } + + one = build_int_cst (TREE_TYPE (min), 1); + tmp = int_const_binop (PLUS_EXPR, max, one); + max = int_const_binop (MINUS_EXPR, min, one); + min = tmp; + + /* There's one corner case, if we had [C+1, C] before we now have + that again. But this represents an empty value range, so drop + to varying in this case. */ + if (tree_int_cst_lt (max, min)) + { + set_varying (TREE_TYPE (min)); + return; + } + + kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE; + } + + tree type = TREE_TYPE (min); + + /* Anti-ranges that can be represented as ranges should be so. */ + if (kind == VR_ANTI_RANGE) + { + /* For -fstrict-enums we may receive out-of-range ranges so consider + values < -INF and values > INF as -INF/INF as well. */ + bool is_min = vrp_val_is_min (min); + bool is_max = vrp_val_is_max (max); + + if (is_min && is_max) + { + /* We cannot deal with empty ranges, drop to varying. + ??? This could be VR_UNDEFINED instead. */ + set_varying (type); + return; + } + else if (TYPE_PRECISION (TREE_TYPE (min)) == 1 + && (is_min || is_max)) + { + /* Non-empty boolean ranges can always be represented + as a singleton range. */ + if (is_min) + min = max = vrp_val_max (TREE_TYPE (min)); + else + min = max = vrp_val_min (TREE_TYPE (min)); + kind = VR_RANGE; + } + else if (is_min) + { + tree one = build_int_cst (TREE_TYPE (max), 1); + min = int_const_binop (PLUS_EXPR, max, one); + max = vrp_val_max (TREE_TYPE (max)); + kind = VR_RANGE; + } + else if (is_max) + { + tree one = build_int_cst (TREE_TYPE (min), 1); + max = int_const_binop (MINUS_EXPR, min, one); + min = vrp_val_min (TREE_TYPE (min)); + kind = VR_RANGE; + } + } + + /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED. + + Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can + restrict those to a subset of what actually fits in the type. + Instead use the extremes of the type precision which will allow + compare_range_with_value() to check if a value is inside a range, + whereas if we used TYPE_*_VAL, said function would just punt + upon seeing a VARYING. */ + unsigned prec = TYPE_PRECISION (type); + signop sign = TYPE_SIGN (type); + if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign)) + && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign))) + { + if (kind == VR_RANGE) + set_varying (type); + else if (kind == VR_ANTI_RANGE) + set_undefined (); + else + gcc_unreachable (); + return; + } + + /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky + to make sure VRP iteration terminates, otherwise we can get into + oscillations. */ + + m_kind = kind; + m_min = min; + m_max = max; + if (flag_checking) + check (); +} + +void +value_range::set (tree val) +{ + gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val)); + if (TREE_OVERFLOW_P (val)) + val = drop_tree_overflow (val); + set (val, val); +} + +/* Set value range VR to a nonzero range of type TYPE. */ + +void +value_range::set_nonzero (tree type) +{ + tree zero = build_int_cst (type, 0); + set (zero, zero, VR_ANTI_RANGE); +} + +/* Set value range VR to a ZERO range of type TYPE. */ + +void +value_range::set_zero (tree type) +{ + set (build_int_cst (type, 0)); +} + +/* Check the validity of the range. */ + +void +value_range::check () +{ + switch (m_kind) + { + case VR_RANGE: + case VR_ANTI_RANGE: + { + gcc_assert (m_min && m_max); + gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max)); + + /* Creating ~[-MIN, +MAX] is stupid because that would be + the empty set. */ + if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE) + gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max)); + + int cmp = compare_values (m_min, m_max); + gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); + break; + } + case VR_UNDEFINED: + gcc_assert (!min () && !max ()); + break; + case VR_VARYING: + gcc_assert (m_min && m_max); + break; + default: + gcc_unreachable (); + } +} + +/* Return the number of sub-ranges in a range. */ + +unsigned +value_range::num_pairs () const +{ + if (undefined_p ()) + return 0; + if (varying_p ()) + return 1; + if (symbolic_p ()) + return normalize_symbolics ().num_pairs (); + if (m_kind == VR_ANTI_RANGE) + { + // ~[MIN, X] has one sub-range of [X+1, MAX], and + // ~[X, MAX] has one sub-range of [MIN, X-1]. + if (vrp_val_is_min (m_min) || vrp_val_is_max (m_max)) + return 1; + return 2; + } + return 1; +} + +/* Return the lower bound for a sub-range. PAIR is the sub-range in + question. */ + +wide_int +value_range::lower_bound (unsigned pair) const +{ + if (symbolic_p ()) + return normalize_symbolics ().lower_bound (pair); + + gcc_checking_assert (!undefined_p ()); + gcc_checking_assert (pair + 1 <= num_pairs ()); + tree t = NULL; + if (m_kind == VR_ANTI_RANGE) + { + tree typ = type (); + if (pair == 1 || vrp_val_is_min (m_min)) + t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1); + else + t = vrp_val_min (typ); + } + else + t = m_min; + return wi::to_wide (t); +} + +/* Return the upper bound for a sub-range. PAIR is the sub-range in + question. */ + +wide_int +value_range::upper_bound (unsigned pair) const +{ + if (symbolic_p ()) + return normalize_symbolics ().upper_bound (pair); + + gcc_checking_assert (!undefined_p ()); + gcc_checking_assert (pair + 1 <= num_pairs ()); + tree t = NULL; + if (m_kind == VR_ANTI_RANGE) + { + tree typ = type (); + if (pair == 1 || vrp_val_is_min (m_min)) + t = vrp_val_max (typ); + else + t = wide_int_to_tree (typ, wi::to_wide (m_min) - 1); + } + else + t = m_max; + return wi::to_wide (t); +} + +/* Return the highest bound in a range. */ + +wide_int +value_range::upper_bound () const +{ + unsigned pairs = num_pairs (); + gcc_checking_assert (pairs > 0); + return upper_bound (pairs - 1); +} + +bool +value_range::equal_p (const value_range &other) const +{ + /* Ignore types for undefined. All undefines are equal. */ + if (undefined_p ()) + return m_kind == other.m_kind; + + return (m_kind == other.m_kind + && vrp_operand_equal_p (m_min, other.m_min) + && vrp_operand_equal_p (m_max, other.m_max)); +} + +bool +value_range::operator== (const value_range &r) const +{ + return equal_p (r); +} + +/* If range is a singleton, place it in RESULT and return TRUE. + Note: A singleton can be any gimple invariant, not just constants. + So, [&x, &x] counts as a singleton. */ +/* Return TRUE if this is a symbolic range. */ + +bool +value_range::symbolic_p () const +{ + return (!varying_p () + && !undefined_p () + && (!is_gimple_min_invariant (m_min) + || !is_gimple_min_invariant (m_max))); +} + +/* NOTE: This is not the inverse of symbolic_p because the range + could also be varying or undefined. Ideally they should be inverse + of each other, with varying only applying to symbolics. Varying of + constants would be represented as [-MIN, +MAX]. */ + +bool +value_range::constant_p () const +{ + return (!varying_p () + && !undefined_p () + && TREE_CODE (m_min) == INTEGER_CST + && TREE_CODE (m_max) == INTEGER_CST); +} + +bool +value_range::singleton_p (tree *result) const +{ + if (m_kind == VR_ANTI_RANGE) + { + if (nonzero_p ()) + { + if (TYPE_PRECISION (type ()) == 1) + { + if (result) + *result = m_max; + return true; + } + return false; + } + if (num_pairs () == 1) + { + value_range vr0, vr1; + ranges_from_anti_range (this, &vr0, &vr1); + return vr0.singleton_p (result); + } + } + if (m_kind == VR_RANGE + && vrp_operand_equal_p (min (), max ()) + && is_gimple_min_invariant (min ())) + { + if (result) + *result = min (); + return true; + } + return false; +} + +/* Return 1 if VAL is inside value range. + 0 if VAL is not inside value range. + -2 if we cannot tell either way. + + Benchmark compile/20001226-1.c compilation time after changing this + function. */ + +int +value_range::value_inside_range (tree val) const +{ + int cmp1, cmp2; + + if (varying_p ()) + return 1; + + if (undefined_p ()) + return 0; + + cmp1 = operand_less_p (val, m_min); + if (cmp1 == -2) + return -2; + if (cmp1 == 1) + return m_kind != VR_RANGE; + + cmp2 = operand_less_p (m_max, val); + if (cmp2 == -2) + return -2; + + if (m_kind == VR_RANGE) + return !cmp2; + else + return !!cmp2; +} + +/* Return TRUE if it is possible that range contains VAL. */ + +bool +value_range::may_contain_p (tree val) const +{ + return value_inside_range (val) != 0; +} + +/* Return TRUE if range contains INTEGER_CST. */ + +bool +value_range::contains_p (tree cst) const +{ + gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST); + if (symbolic_p ()) + return normalize_symbolics ().contains_p (cst); + return value_inside_range (cst) == 1; +} + +/* Normalize addresses into constants. */ + +value_range +value_range::normalize_addresses () const +{ + if (undefined_p ()) + return *this; + + if (!POINTER_TYPE_P (type ()) || range_has_numeric_bounds_p (this)) + return *this; + + if (!range_includes_zero_p (this)) + { + gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR + || TREE_CODE (m_max) == ADDR_EXPR); + return range_nonzero (type ()); + } + return value_range (type ()); +} + +/* Normalize symbolics and addresses into constants. */ + +value_range +value_range::normalize_symbolics () const +{ + if (varying_p () || undefined_p ()) + return *this; + tree ttype = type (); + bool min_symbolic = !is_gimple_min_invariant (min ()); + bool max_symbolic = !is_gimple_min_invariant (max ()); + if (!min_symbolic && !max_symbolic) + return normalize_addresses (); + + // [SYM, SYM] -> VARYING + if (min_symbolic && max_symbolic) + { + value_range var; + var.set_varying (ttype); + return var; + } + if (kind () == VR_RANGE) + { + // [SYM, NUM] -> [-MIN, NUM] + if (min_symbolic) + return value_range (vrp_val_min (ttype), max ()); + // [NUM, SYM] -> [NUM, +MAX] + return value_range (min (), vrp_val_max (ttype)); + } + gcc_checking_assert (kind () == VR_ANTI_RANGE); + // ~[SYM, NUM] -> [NUM + 1, +MAX] + if (min_symbolic) + { + if (!vrp_val_is_max (max ())) + { + tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1); + return value_range (n, vrp_val_max (ttype)); + } + value_range var; + var.set_varying (ttype); + return var; + } + // ~[NUM, SYM] -> [-MIN, NUM - 1] + if (!vrp_val_is_min (min ())) + { + tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1); + return value_range (vrp_val_min (ttype), n); + } + value_range var; + var.set_varying (ttype); + return var; +} + +/* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and + { VR1TYPE, VR0MIN, VR0MAX } and store the result + in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest + possible such range. The resulting range is not canonicalized. */ + +static void +intersect_ranges (enum value_range_kind *vr0type, + tree *vr0min, tree *vr0max, + enum value_range_kind vr1type, + tree vr1min, tree vr1max) +{ + bool mineq = vrp_operand_equal_p (*vr0min, vr1min); + bool maxeq = vrp_operand_equal_p (*vr0max, vr1max); + + /* [] is vr0, () is vr1 in the following classification comments. */ + if (mineq && maxeq) + { + /* [( )] */ + if (*vr0type == vr1type) + /* Nothing to do for equal ranges. */ + ; + else if ((*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + || (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE)) + { + /* For anti-range with range intersection the result is empty. */ + *vr0type = VR_UNDEFINED; + *vr0min = NULL_TREE; + *vr0max = NULL_TREE; + } + else + gcc_unreachable (); + } + else if (operand_less_p (*vr0max, vr1min) == 1 + || operand_less_p (vr1max, *vr0min) == 1) + { + /* [ ] ( ) or ( ) [ ] + If the ranges have an empty intersection, the result of the + intersect operation is the range for intersecting an + anti-range with a range or empty when intersecting two ranges. */ + if (*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + ; + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + { + *vr0type = vr1type; + *vr0min = vr1min; + *vr0max = vr1max; + } + else if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + { + *vr0type = VR_UNDEFINED; + *vr0min = NULL_TREE; + *vr0max = NULL_TREE; + } + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + { + /* If the anti-ranges are adjacent to each other merge them. */ + if (TREE_CODE (*vr0max) == INTEGER_CST + && TREE_CODE (vr1min) == INTEGER_CST + && operand_less_p (*vr0max, vr1min) == 1 + && integer_onep (int_const_binop (MINUS_EXPR, + vr1min, *vr0max))) + *vr0max = vr1max; + else if (TREE_CODE (vr1max) == INTEGER_CST + && TREE_CODE (*vr0min) == INTEGER_CST + && operand_less_p (vr1max, *vr0min) == 1 + && integer_onep (int_const_binop (MINUS_EXPR, + *vr0min, vr1max))) + *vr0min = vr1min; + /* Else arbitrarily take VR0. */ + } + } + else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1) + && (mineq || operand_less_p (*vr0min, vr1min) == 1)) + { + /* [ ( ) ] or [( ) ] or [ ( )] */ + if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + { + /* If both are ranges the result is the inner one. */ + *vr0type = vr1type; + *vr0min = vr1min; + *vr0max = vr1max; + } + else if (*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + { + /* Choose the right gap if the left one is empty. */ + if (mineq) + { + if (TREE_CODE (vr1max) != INTEGER_CST) + *vr0min = vr1max; + else if (TYPE_PRECISION (TREE_TYPE (vr1max)) == 1 + && !TYPE_UNSIGNED (TREE_TYPE (vr1max))) + *vr0min + = int_const_binop (MINUS_EXPR, vr1max, + build_int_cst (TREE_TYPE (vr1max), -1)); + else + *vr0min + = int_const_binop (PLUS_EXPR, vr1max, + build_int_cst (TREE_TYPE (vr1max), 1)); + } + /* Choose the left gap if the right one is empty. */ + else if (maxeq) + { + if (TREE_CODE (vr1min) != INTEGER_CST) + *vr0max = vr1min; + else if (TYPE_PRECISION (TREE_TYPE (vr1min)) == 1 + && !TYPE_UNSIGNED (TREE_TYPE (vr1min))) + *vr0max + = int_const_binop (PLUS_EXPR, vr1min, + build_int_cst (TREE_TYPE (vr1min), -1)); + else + *vr0max + = int_const_binop (MINUS_EXPR, vr1min, + build_int_cst (TREE_TYPE (vr1min), 1)); + } + /* Choose the anti-range if the range is effectively varying. */ + else if (vrp_val_is_min (*vr0min) + && vrp_val_is_max (*vr0max)) + { + *vr0type = vr1type; + *vr0min = vr1min; + *vr0max = vr1max; + } + /* Else choose the range. */ + } + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + /* If both are anti-ranges the result is the outer one. */ + ; + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + { + /* The intersection is empty. */ + *vr0type = VR_UNDEFINED; + *vr0min = NULL_TREE; + *vr0max = NULL_TREE; + } + else + gcc_unreachable (); + } + else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1) + && (mineq || operand_less_p (vr1min, *vr0min) == 1)) + { + /* ( [ ] ) or ([ ] ) or ( [ ]) */ + if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + /* Choose the inner range. */ + ; + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + { + /* Choose the right gap if the left is empty. */ + if (mineq) + { + *vr0type = VR_RANGE; + if (TREE_CODE (*vr0max) != INTEGER_CST) + *vr0min = *vr0max; + else if (TYPE_PRECISION (TREE_TYPE (*vr0max)) == 1 + && !TYPE_UNSIGNED (TREE_TYPE (*vr0max))) + *vr0min + = int_const_binop (MINUS_EXPR, *vr0max, + build_int_cst (TREE_TYPE (*vr0max), -1)); + else + *vr0min + = int_const_binop (PLUS_EXPR, *vr0max, + build_int_cst (TREE_TYPE (*vr0max), 1)); + *vr0max = vr1max; + } + /* Choose the left gap if the right is empty. */ + else if (maxeq) + { + *vr0type = VR_RANGE; + if (TREE_CODE (*vr0min) != INTEGER_CST) + *vr0max = *vr0min; + else if (TYPE_PRECISION (TREE_TYPE (*vr0min)) == 1 + && !TYPE_UNSIGNED (TREE_TYPE (*vr0min))) + *vr0max + = int_const_binop (PLUS_EXPR, *vr0min, + build_int_cst (TREE_TYPE (*vr0min), -1)); + else + *vr0max + = int_const_binop (MINUS_EXPR, *vr0min, + build_int_cst (TREE_TYPE (*vr0min), 1)); + *vr0min = vr1min; + } + /* Choose the anti-range if the range is effectively varying. */ + else if (vrp_val_is_min (vr1min) + && vrp_val_is_max (vr1max)) + ; + /* Choose the anti-range if it is ~[0,0], that range is special + enough to special case when vr1's range is relatively wide. + At least for types bigger than int - this covers pointers + and arguments to functions like ctz. */ + else if (*vr0min == *vr0max + && integer_zerop (*vr0min) + && ((TYPE_PRECISION (TREE_TYPE (*vr0min)) + >= TYPE_PRECISION (integer_type_node)) + || POINTER_TYPE_P (TREE_TYPE (*vr0min))) + && TREE_CODE (vr1max) == INTEGER_CST + && TREE_CODE (vr1min) == INTEGER_CST + && (wi::clz (wi::to_wide (vr1max) - wi::to_wide (vr1min)) + < TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2)) + ; + /* Else choose the range. */ + else + { + *vr0type = vr1type; + *vr0min = vr1min; + *vr0max = vr1max; + } + } + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + { + /* If both are anti-ranges the result is the outer one. */ + *vr0type = vr1type; + *vr0min = vr1min; + *vr0max = vr1max; + } + else if (vr1type == VR_ANTI_RANGE + && *vr0type == VR_RANGE) + { + /* The intersection is empty. */ + *vr0type = VR_UNDEFINED; + *vr0min = NULL_TREE; + *vr0max = NULL_TREE; + } + else + gcc_unreachable (); + } + else if ((operand_less_p (vr1min, *vr0max) == 1 + || operand_equal_p (vr1min, *vr0max, 0)) + && operand_less_p (*vr0min, vr1min) == 1) + { + /* [ ( ] ) or [ ]( ) */ + if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + *vr0max = vr1max; + else if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + *vr0min = vr1min; + else if (*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + { + if (TREE_CODE (vr1min) == INTEGER_CST) + *vr0max = int_const_binop (MINUS_EXPR, vr1min, + build_int_cst (TREE_TYPE (vr1min), 1)); + else + *vr0max = vr1min; + } + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + { + *vr0type = VR_RANGE; + if (TREE_CODE (*vr0max) == INTEGER_CST) + *vr0min = int_const_binop (PLUS_EXPR, *vr0max, + build_int_cst (TREE_TYPE (*vr0max), 1)); + else + *vr0min = *vr0max; + *vr0max = vr1max; + } + else + gcc_unreachable (); + } + else if ((operand_less_p (*vr0min, vr1max) == 1 + || operand_equal_p (*vr0min, vr1max, 0)) + && operand_less_p (vr1min, *vr0min) == 1) + { + /* ( [ ) ] or ( )[ ] */ + if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + *vr0min = vr1min; + else if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + *vr0max = vr1max; + else if (*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + { + if (TREE_CODE (vr1max) == INTEGER_CST) + *vr0min = int_const_binop (PLUS_EXPR, vr1max, + build_int_cst (TREE_TYPE (vr1max), 1)); + else + *vr0min = vr1max; + } + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + { + *vr0type = VR_RANGE; + if (TREE_CODE (*vr0min) == INTEGER_CST) + *vr0max = int_const_binop (MINUS_EXPR, *vr0min, + build_int_cst (TREE_TYPE (*vr0min), 1)); + else + *vr0max = *vr0min; + *vr0min = vr1min; + } + else + gcc_unreachable (); + } + + /* If we know the intersection is empty, there's no need to + conservatively add anything else to the set. */ + if (*vr0type == VR_UNDEFINED) + return; + + /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as + result for the intersection. That's always a conservative + correct estimate unless VR1 is a constant singleton range + in which case we choose that. */ + if (vr1type == VR_RANGE + && is_gimple_min_invariant (vr1min) + && vrp_operand_equal_p (vr1min, vr1max)) + { + *vr0type = vr1type; + *vr0min = vr1min; + *vr0max = vr1max; + } +} + +/* Helper for the intersection operation for value ranges. Given two + value ranges VR0 and VR1, return the intersection of the two + ranges. This may not be the smallest possible such range. */ + +value_range +value_range::intersect_helper (const value_range *vr0, const value_range *vr1) +{ + /* If either range is VR_VARYING the other one wins. */ + if (vr1->varying_p ()) + return *vr0; + if (vr0->varying_p ()) + return *vr1; + + /* When either range is VR_UNDEFINED the resulting range is + VR_UNDEFINED, too. */ + if (vr0->undefined_p ()) + return *vr0; + if (vr1->undefined_p ()) + return *vr1; + + value_range_kind vr0kind = vr0->kind (); + tree vr0min = vr0->min (); + tree vr0max = vr0->max (); + intersect_ranges (&vr0kind, &vr0min, &vr0max, + vr1->kind (), vr1->min (), vr1->max ()); + /* Make sure to canonicalize the result though as the inversion of a + VR_RANGE can still be a VR_RANGE. Work on a temporary so we can + fall back to vr0 when this turns things to varying. */ + value_range tem; + if (vr0kind == VR_UNDEFINED) + tem.set_undefined (); + else if (vr0kind == VR_VARYING) + tem.set_varying (vr0->type ()); + else + tem.set (vr0min, vr0max, vr0kind); + /* If that failed, use the saved original VR0. */ + if (tem.varying_p ()) + return *vr0; + + return tem; +} + +/* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and + { VR1TYPE, VR0MIN, VR0MAX } and store the result + in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest + possible such range. The resulting range is not canonicalized. */ + +static void +union_ranges (enum value_range_kind *vr0type, + tree *vr0min, tree *vr0max, + enum value_range_kind vr1type, + tree vr1min, tree vr1max) +{ + int cmpmin = compare_values (*vr0min, vr1min); + int cmpmax = compare_values (*vr0max, vr1max); + bool mineq = cmpmin == 0; + bool maxeq = cmpmax == 0; + + /* [] is vr0, () is vr1 in the following classification comments. */ + if (mineq && maxeq) + { + /* [( )] */ + if (*vr0type == vr1type) + /* Nothing to do for equal ranges. */ + ; + else if ((*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + || (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE)) + { + /* For anti-range with range union the result is varying. */ + goto give_up; + } + else + gcc_unreachable (); + } + else if (operand_less_p (*vr0max, vr1min) == 1 + || operand_less_p (vr1max, *vr0min) == 1) + { + /* [ ] ( ) or ( ) [ ] + If the ranges have an empty intersection, result of the union + operation is the anti-range or if both are anti-ranges + it covers all. */ + if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + goto give_up; + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + ; + else if (*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + { + *vr0type = vr1type; + *vr0min = vr1min; + *vr0max = vr1max; + } + else if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + { + /* The result is the convex hull of both ranges. */ + if (operand_less_p (*vr0max, vr1min) == 1) + { + /* If the result can be an anti-range, create one. */ + if (TREE_CODE (*vr0max) == INTEGER_CST + && TREE_CODE (vr1min) == INTEGER_CST + && vrp_val_is_min (*vr0min) + && vrp_val_is_max (vr1max)) + { + tree min = int_const_binop (PLUS_EXPR, + *vr0max, + build_int_cst (TREE_TYPE (*vr0max), 1)); + tree max = int_const_binop (MINUS_EXPR, + vr1min, + build_int_cst (TREE_TYPE (vr1min), 1)); + if (!operand_less_p (max, min)) + { + *vr0type = VR_ANTI_RANGE; + *vr0min = min; + *vr0max = max; + } + else + *vr0max = vr1max; + } + else + *vr0max = vr1max; + } + else + { + /* If the result can be an anti-range, create one. */ + if (TREE_CODE (vr1max) == INTEGER_CST + && TREE_CODE (*vr0min) == INTEGER_CST + && vrp_val_is_min (vr1min) + && vrp_val_is_max (*vr0max)) + { + tree min = int_const_binop (PLUS_EXPR, + vr1max, + build_int_cst (TREE_TYPE (vr1max), 1)); + tree max = int_const_binop (MINUS_EXPR, + *vr0min, + build_int_cst (TREE_TYPE (*vr0min), 1)); + if (!operand_less_p (max, min)) + { + *vr0type = VR_ANTI_RANGE; + *vr0min = min; + *vr0max = max; + } + else + *vr0min = vr1min; + } + else + *vr0min = vr1min; + } + } + else + gcc_unreachable (); + } + else if ((maxeq || cmpmax == 1) + && (mineq || cmpmin == -1)) + { + /* [ ( ) ] or [( ) ] or [ ( )] */ + if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + ; + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + { + *vr0type = vr1type; + *vr0min = vr1min; + *vr0max = vr1max; + } + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + { + /* Arbitrarily choose the right or left gap. */ + if (!mineq && TREE_CODE (vr1min) == INTEGER_CST) + *vr0max = int_const_binop (MINUS_EXPR, vr1min, + build_int_cst (TREE_TYPE (vr1min), 1)); + else if (!maxeq && TREE_CODE (vr1max) == INTEGER_CST) + *vr0min = int_const_binop (PLUS_EXPR, vr1max, + build_int_cst (TREE_TYPE (vr1max), 1)); + else + goto give_up; + } + else if (*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + /* The result covers everything. */ + goto give_up; + else + gcc_unreachable (); + } + else if ((maxeq || cmpmax == -1) + && (mineq || cmpmin == 1)) + { + /* ( [ ] ) or ([ ] ) or ( [ ]) */ + if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + { + *vr0type = vr1type; + *vr0min = vr1min; + *vr0max = vr1max; + } + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + ; + else if (*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + { + *vr0type = VR_ANTI_RANGE; + if (!mineq && TREE_CODE (*vr0min) == INTEGER_CST) + { + *vr0max = int_const_binop (MINUS_EXPR, *vr0min, + build_int_cst (TREE_TYPE (*vr0min), 1)); + *vr0min = vr1min; + } + else if (!maxeq && TREE_CODE (*vr0max) == INTEGER_CST) + { + *vr0min = int_const_binop (PLUS_EXPR, *vr0max, + build_int_cst (TREE_TYPE (*vr0max), 1)); + *vr0max = vr1max; + } + else + goto give_up; + } + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + /* The result covers everything. */ + goto give_up; + else + gcc_unreachable (); + } + else if (cmpmin == -1 + && cmpmax == -1 + && (operand_less_p (vr1min, *vr0max) == 1 + || operand_equal_p (vr1min, *vr0max, 0))) + { + /* [ ( ] ) or [ ]( ) */ + if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + *vr0max = vr1max; + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + *vr0min = vr1min; + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + { + if (TREE_CODE (vr1min) == INTEGER_CST) + *vr0max = int_const_binop (MINUS_EXPR, vr1min, + build_int_cst (TREE_TYPE (vr1min), 1)); + else + goto give_up; + } + else if (*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + { + if (TREE_CODE (*vr0max) == INTEGER_CST) + { + *vr0type = vr1type; + *vr0min = int_const_binop (PLUS_EXPR, *vr0max, + build_int_cst (TREE_TYPE (*vr0max), 1)); + *vr0max = vr1max; + } + else + goto give_up; + } + else + gcc_unreachable (); + } + else if (cmpmin == 1 + && cmpmax == 1 + && (operand_less_p (*vr0min, vr1max) == 1 + || operand_equal_p (*vr0min, vr1max, 0))) + { + /* ( [ ) ] or ( )[ ] */ + if (*vr0type == VR_RANGE + && vr1type == VR_RANGE) + *vr0min = vr1min; + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_ANTI_RANGE) + *vr0max = vr1max; + else if (*vr0type == VR_ANTI_RANGE + && vr1type == VR_RANGE) + { + if (TREE_CODE (vr1max) == INTEGER_CST) + *vr0min = int_const_binop (PLUS_EXPR, vr1max, + build_int_cst (TREE_TYPE (vr1max), 1)); + else + goto give_up; + } + else if (*vr0type == VR_RANGE + && vr1type == VR_ANTI_RANGE) + { + if (TREE_CODE (*vr0min) == INTEGER_CST) + { + *vr0type = vr1type; + *vr0max = int_const_binop (MINUS_EXPR, *vr0min, + build_int_cst (TREE_TYPE (*vr0min), 1)); + *vr0min = vr1min; + } + else + goto give_up; + } + else + gcc_unreachable (); + } + else + goto give_up; + + return; + +give_up: + *vr0type = VR_VARYING; + *vr0min = NULL_TREE; + *vr0max = NULL_TREE; +} + +/* Helper for meet operation for value ranges. Given two value ranges VR0 and + VR1, return a range that contains both VR0 and VR1. This may not be the + smallest possible such range. */ + +value_range +value_range::union_helper (const value_range *vr0, const value_range *vr1) +{ + /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */ + if (vr1->undefined_p () + || vr0->varying_p ()) + return *vr0; + + /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */ + if (vr0->undefined_p () + || vr1->varying_p ()) + return *vr1; + + value_range_kind vr0kind = vr0->kind (); + tree vr0min = vr0->min (); + tree vr0max = vr0->max (); + union_ranges (&vr0kind, &vr0min, &vr0max, + vr1->kind (), vr1->min (), vr1->max ()); + + /* Work on a temporary so we can still use vr0 when union returns varying. */ + value_range tem; + if (vr0kind == VR_UNDEFINED) + tem.set_undefined (); + else if (vr0kind == VR_VARYING) + tem.set_varying (vr0->type ()); + else + tem.set (vr0min, vr0max, vr0kind); + + /* Failed to find an efficient meet. Before giving up and setting + the result to VARYING, see if we can at least derive a useful + anti-range. */ + if (tem.varying_p () + && range_includes_zero_p (vr0) == 0 + && range_includes_zero_p (vr1) == 0) + { + tem.set_nonzero (vr0->type ()); + return tem; + } + + return tem; +} + +/* Meet operation for value ranges. Given two value ranges VR0 and + VR1, store in VR0 a range that contains both VR0 and VR1. This + may not be the smallest possible such range. */ + +void +value_range::union_ (const value_range *other) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Meeting\n "); + dump_value_range (dump_file, this); + fprintf (dump_file, "\nand\n "); + dump_value_range (dump_file, other); + fprintf (dump_file, "\n"); + } + + *this = union_helper (this, other); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "to\n "); + dump_value_range (dump_file, this); + fprintf (dump_file, "\n"); + } +} + +/* Range union, but for references. */ + +void +value_range::union_ (const value_range &r) +{ + /* Disable details for now, because it makes the ranger dump + unnecessarily verbose. */ + bool details = dump_flags & TDF_DETAILS; + if (details) + dump_flags &= ~TDF_DETAILS; + union_ (&r); + if (details) + dump_flags |= TDF_DETAILS; +} + +void +value_range::intersect (const value_range *other) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Intersecting\n "); + dump_value_range (dump_file, this); + fprintf (dump_file, "\nand\n "); + dump_value_range (dump_file, other); + fprintf (dump_file, "\n"); + } + + *this = intersect_helper (this, other); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "to\n "); + dump_value_range (dump_file, this); + fprintf (dump_file, "\n"); + } +} + +/* Range intersect, but for references. */ + +void +value_range::intersect (const value_range &r) +{ + /* Disable details for now, because it makes the ranger dump + unnecessarily verbose. */ + bool details = dump_flags & TDF_DETAILS; + if (details) + dump_flags &= ~TDF_DETAILS; + intersect (&r); + if (details) + dump_flags |= TDF_DETAILS; +} + +/* Return the inverse of a range. */ + +void +value_range::invert () +{ + /* We can't just invert VR_RANGE and VR_ANTI_RANGE because we may + create non-canonical ranges. Use the constructors instead. */ + if (m_kind == VR_RANGE) + *this = value_range (m_min, m_max, VR_ANTI_RANGE); + else if (m_kind == VR_ANTI_RANGE) + *this = value_range (m_min, m_max); + else + gcc_unreachable (); +} + +void +value_range::dump (FILE *file) const +{ + if (undefined_p ()) + fprintf (file, "UNDEFINED"); + else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE) + { + tree ttype = type (); + + print_generic_expr (file, ttype); + fprintf (file, " "); + + fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : ""); + + if (INTEGRAL_TYPE_P (ttype) + && !TYPE_UNSIGNED (ttype) + && vrp_val_is_min (min ()) + && TYPE_PRECISION (ttype) != 1) + fprintf (file, "-INF"); + else + print_generic_expr (file, min ()); + + fprintf (file, ", "); + + if (supports_type_p (ttype) + && vrp_val_is_max (max ()) + && TYPE_PRECISION (ttype) != 1) + fprintf (file, "+INF"); + else + print_generic_expr (file, max ()); + + fprintf (file, "]"); + } + else if (varying_p ()) + { + print_generic_expr (file, type ()); + fprintf (file, " VARYING"); + } + else + gcc_unreachable (); +} + +void +value_range::dump () const +{ + dump (stderr); +} + +void +dump_value_range (FILE *file, const value_range *vr) +{ + if (!vr) + fprintf (file, "[]"); + else + vr->dump (file); +} + +DEBUG_FUNCTION void +debug (const value_range *vr) +{ + dump_value_range (stderr, vr); +} + +DEBUG_FUNCTION void +debug (const value_range &vr) +{ + dump_value_range (stderr, &vr); +} + +/* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR + so that *VR0 U *VR1 == *AR. Returns true if that is possible, + false otherwise. If *AR can be represented with a single range + *VR1 will be VR_UNDEFINED. */ + +bool +ranges_from_anti_range (const value_range *ar, + value_range *vr0, value_range *vr1) +{ + tree type = ar->type (); + + vr0->set_undefined (); + vr1->set_undefined (); + + /* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U + [A+1, +INF]. Not sure if this helps in practice, though. */ + + if (ar->kind () != VR_ANTI_RANGE + || TREE_CODE (ar->min ()) != INTEGER_CST + || TREE_CODE (ar->max ()) != INTEGER_CST + || !vrp_val_min (type) + || !vrp_val_max (type)) + return false; + + if (tree_int_cst_lt (vrp_val_min (type), ar->min ())) + vr0->set (vrp_val_min (type), + wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1)); + if (tree_int_cst_lt (ar->max (), vrp_val_max (type))) + vr1->set (wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1), + vrp_val_max (type)); + if (vr0->undefined_p ()) + { + *vr0 = *vr1; + vr1->set_undefined (); + } + + return !vr0->undefined_p (); +} + +bool +range_has_numeric_bounds_p (const value_range *vr) +{ + return (vr->min () + && TREE_CODE (vr->min ()) == INTEGER_CST + && TREE_CODE (vr->max ()) == INTEGER_CST); +} + +/* Return the maximum value for TYPE. */ + +tree +vrp_val_max (const_tree type) +{ + if (INTEGRAL_TYPE_P (type)) + return TYPE_MAX_VALUE (type); + if (POINTER_TYPE_P (type)) + { + wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)); + return wide_int_to_tree (const_cast (type), max); + } + return NULL_TREE; +} + +/* Return the minimum value for TYPE. */ + +tree +vrp_val_min (const_tree type) +{ + if (INTEGRAL_TYPE_P (type)) + return TYPE_MIN_VALUE (type); + if (POINTER_TYPE_P (type)) + return build_zero_cst (const_cast (type)); + return NULL_TREE; +} + +/* Return whether VAL is equal to the maximum value of its type. + We can't do a simple equality comparison with TYPE_MAX_VALUE because + C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE + is not == to the integer constant with the same value in the type. */ + +bool +vrp_val_is_max (const_tree val) +{ + tree type_max = vrp_val_max (TREE_TYPE (val)); + return (val == type_max + || (type_max != NULL_TREE + && operand_equal_p (val, type_max, 0))); +} + +/* Return whether VAL is equal to the minimum value of its type. */ + +bool +vrp_val_is_min (const_tree val) +{ + tree type_min = vrp_val_min (TREE_TYPE (val)); + return (val == type_min + || (type_min != NULL_TREE + && operand_equal_p (val, type_min, 0))); +} + +/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */ + +bool +vrp_operand_equal_p (const_tree val1, const_tree val2) +{ + if (val1 == val2) + return true; + if (!val1 || !val2 || !operand_equal_p (val1, val2, 0)) + return false; + return true; +} diff --git a/gcc/value-range.h b/gcc/value-range.h new file mode 100644 index 00000000000..8a88e9a6e8c --- /dev/null +++ b/gcc/value-range.h @@ -0,0 +1,216 @@ +/* Support routines for value ranges. + Copyright (C) 2019 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_VALUE_RANGE_H +#define GCC_VALUE_RANGE_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. + +class GTY((for_user)) value_range +{ + friend void range_tests (); +public: + value_range (); + value_range (tree, tree, value_range_kind = VR_RANGE); + value_range (tree type, const wide_int &, const wide_int &, + value_range_kind = VR_RANGE); + value_range (tree type); + + void set (tree, tree, value_range_kind = VR_RANGE); + void set (tree); + void set_nonzero (tree); + void set_zero (tree); + + enum value_range_kind kind () const; + tree min () const; + tree max () const; + + /* Types of value ranges. */ + bool symbolic_p () const; + bool constant_p () const; + bool undefined_p () const; + bool varying_p () const; + void set_varying (tree type); + void set_undefined (); + + void union_ (const value_range *); + void intersect (const value_range *); + void union_ (const value_range &); + void intersect (const value_range &); + + bool operator== (const value_range &) const; + bool operator!= (const value_range &) const /* = delete */; + bool equal_p (const value_range &) const; + + /* Misc methods. */ + tree type () const; + bool may_contain_p (tree) const; + bool zero_p () const; + bool nonzero_p () const; + bool singleton_p (tree *result = NULL) const; + void dump (FILE *) const; + void dump () const; + + static bool supports_type_p (tree); + value_range normalize_symbolics () const; + value_range normalize_addresses () const; + + static const unsigned int m_max_pairs = 2; + bool contains_p (tree) const; + unsigned num_pairs () const; + wide_int lower_bound (unsigned = 0) const; + wide_int upper_bound (unsigned) const; + wide_int upper_bound () const; + void invert (); + +protected: + void check (); + static value_range union_helper (const value_range *, const value_range *); + static value_range intersect_helper (const value_range *, + const value_range *); + + friend void gt_ggc_mx_value_range (void *); + friend void gt_pch_p_11value_range (void *, void *, + gt_pointer_operator, void *); + friend void gt_pch_nx_value_range (void *); + friend void gt_ggc_mx (value_range &); + friend void gt_ggc_mx (value_range *&); + friend void gt_pch_nx (value_range &); + friend void gt_pch_nx (value_range *, gt_pointer_operator, void *); + + enum value_range_kind m_kind; + tree m_min; + tree m_max; + +private: + int value_inside_range (tree) const; +}; + +extern bool range_has_numeric_bounds_p (const value_range *); +extern bool ranges_from_anti_range (const value_range *, + value_range *, value_range *); +extern void dump_value_range (FILE *, const value_range *); +extern bool vrp_val_is_min (const_tree); +extern bool vrp_val_is_max (const_tree); +extern tree vrp_val_min (const_tree); +extern tree vrp_val_max (const_tree); +extern bool vrp_operand_equal_p (const_tree, const_tree); + +inline +value_range::value_range () +{ + m_kind = VR_UNDEFINED; + m_min = m_max = NULL; +} + +inline value_range_kind +value_range::kind () const +{ + return m_kind; +} + +inline tree +value_range::type () const +{ + return TREE_TYPE (min ()); +} + +inline tree +value_range::min () const +{ + return m_min; +} + +inline tree +value_range::max () const +{ + return m_max; +} + +inline bool +value_range::varying_p () const +{ + return m_kind == VR_VARYING; +} + +inline bool +value_range::undefined_p () const +{ + return m_kind == VR_UNDEFINED; +} + +inline bool +value_range::zero_p () const +{ + return (m_kind == VR_RANGE + && integer_zerop (m_min) + && integer_zerop (m_max)); +} + +inline bool +value_range::nonzero_p () const +{ + if (m_kind == VR_ANTI_RANGE + && !TYPE_UNSIGNED (type ()) + && integer_zerop (m_min) + && integer_zerop (m_max)) + return true; + + return (m_kind == VR_RANGE + && TYPE_UNSIGNED (type ()) + && integer_onep (m_min) + && vrp_val_is_max (m_max)); +} + +inline bool +value_range::supports_type_p (tree type) +{ + if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))) + return type; + return false; +} + +inline bool +range_includes_zero_p (const value_range *vr) +{ + if (vr->undefined_p ()) + return false; + + if (vr->varying_p ()) + return true; + + return vr->may_contain_p (build_zero_cst (vr->type ())); +} + +#endif // GCC_VALUE_RANGE_H