From 39c55f4b6a9f79a65d569c8fc7cd787e5c636395 Mon Sep 17 00:00:00 2001 From: Aldy Hernandez Date: Tue, 27 Aug 2019 14:43:22 +0000 Subject: Cleanups to bring branch more in line with trunk. git-svn-id: https://gcc.gnu.org/svn/gcc/branches/ssa-range@274957 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/coretypes.h | 18 ------ gcc/gimple-ssa-warn-restrict.c | 2 +- gcc/range-op.cc | 2 +- gcc/ssa-range.cc | 4 +- gcc/ssa.h | 2 +- gcc/tree-vrp.c | 135 ++++++++++++++++++++++++++++++++++++++--- gcc/tree-vrp.h | 20 ++++-- gcc/vr-values.c | 90 ++------------------------- gcc/vr-values.h | 1 - gcc/wide-int-range.cc | 104 +------------------------------ gcc/wide-int-range.h | 13 ---- 11 files changed, 153 insertions(+), 238 deletions(-) diff --git a/gcc/coretypes.h b/gcc/coretypes.h index 7f866333e1e..eac2f3931aa 100644 --- a/gcc/coretypes.h +++ b/gcc/coretypes.h @@ -202,24 +202,6 @@ enum profile_update { PROFILE_UPDATE_PREFER_ATOMIC }; -/* Types of ranges. - - This is still prefixed with VR_*, even though it is more general - purpose, to avoid having to replace everything across the compiler. - Perhaps we should change it later. */ -enum value_range_kind { - /* Empty range. */ - VR_UNDEFINED, - /* Range spans the entire domain. */ - VR_VARYING, - /* Range is [MIN, MAX]. */ - VR_RANGE, - /* Range is ~[MIN, MAX]. */ - VR_ANTI_RANGE, - /* Range is a nice guy. */ - VR_LAST -}; - /* Types of unwind/exception handling info that can be generated. */ enum unwind_info_type diff --git a/gcc/gimple-ssa-warn-restrict.c b/gcc/gimple-ssa-warn-restrict.c index c799b0f2a26..95b4bd51132 100644 --- a/gcc/gimple-ssa-warn-restrict.c +++ b/gcc/gimple-ssa-warn-restrict.c @@ -302,7 +302,7 @@ ranger_get_range_info (gimple *stmt, tree ssa, wide_int *min, wide_int *max) if (r.undefined_p ()) return VR_UNDEFINED; - value_range_base vr = r; + value_range_base vr = irange_to_value_range (r); *min = wi::to_wide (vr.min ()); *max = wi::to_wide (vr.max ()); return vr.kind (); diff --git a/gcc/range-op.cc b/gcc/range-op.cc index c2ffbcc42b8..6b27fb242a9 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -3416,7 +3416,7 @@ range_tests () #undef value_range_base { irange r0 = irange (VR_ANTI_RANGE, INT (10), INT (20)); - value_range_base vr = r0; + value_range_base vr = irange_to_value_range (r0); ASSERT_TRUE (vr.kind () == VR_ANTI_RANGE); ASSERT_TRUE (wi::eq_p (10, wi::to_wide (vr.min ())) && wi::eq_p (20, wi::to_wide (vr.max ()))); diff --git a/gcc/ssa-range.cc b/gcc/ssa-range.cc index ad9797bcdb7..189c054f868 100644 --- a/gcc/ssa-range.cc +++ b/gcc/ssa-range.cc @@ -971,7 +971,7 @@ global_ranger::export_global_ranges () if (!dbg_cnt (ranger_export_count)) return; - value_range_base vr = r; + value_range_base vr = irange_to_value_range (r); set_range_info (name, vr); if (dump_file) { @@ -1139,7 +1139,7 @@ loop_ranger::adjust_phi_with_loop_info (irange &r, gphi *phi) if (l && l->header == gimple_bb (phi)) { tree phi_result = PHI_RESULT (phi); - value_range_base vr = r; + value_range_base vr = irange_to_value_range (r); m_vr_values->adjust_range_with_scev (&vr, l, phi, phi_result); if (vr.constant_p ()) { diff --git a/gcc/ssa.h b/gcc/ssa.h index 74dcc732cd2..2fe4addedf2 100644 --- a/gcc/ssa.h +++ b/gcc/ssa.h @@ -25,8 +25,8 @@ along with GCC; see the file COPYING3. If not see #include "stringpool.h" #include "gimple-ssa.h" -#include "range.h" #include "tree-vrp.h" +#include "range.h" #include "tree-ssanames.h" #include "tree-phinodes.h" #include "ssa-iterators.h" diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 968c44c235a..57ba08e0bc1 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -223,6 +223,7 @@ value_range_base::check () break; } case VR_UNDEFINED: + gcc_assert (!min () && !max ()); break; case VR_VARYING: gcc_assert (m_min && m_max); @@ -405,7 +406,7 @@ value_range_base::singleton_p (tree *result) const tree value_range_base::type () const { - gcc_assert (m_min); + gcc_assert (m_min || undefined_p ()); return TREE_TYPE (min ()); } @@ -713,6 +714,7 @@ intersect_range_with_nonzero_bits (enum value_range_kind vr_type, void value_range_base::set (enum value_range_kind kind, tree min, tree max) { + /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */ if (kind == VR_UNDEFINED) { set_undefined (); @@ -1488,6 +1490,112 @@ combine_bound (enum tree_code code, wide_int &wi, wi::overflow_type &ovf, wi = wi::shwi (0, prec); } +/* Given a range in [WMIN, WMAX], adjust it for possible overflow and + put the result in VR. + + TYPE is the type of the range. + + MIN_OVF and MAX_OVF indicate what type of overflow, if any, + occurred while originally calculating WMIN or WMAX. -1 indicates + underflow. +1 indicates overflow. 0 indicates neither. */ + +static void +set_value_range_with_overflow (value_range_kind &kind, tree &min, tree &max, + tree type, + const wide_int &wmin, const wide_int &wmax, + wi::overflow_type min_ovf, + wi::overflow_type max_ovf) +{ + const signop sgn = TYPE_SIGN (type); + const unsigned int prec = TYPE_PRECISION (type); + + /* For one bit precision if max < min, then the swapped + range covers all values. */ + if (prec == 1 && wi::lt_p (wmax, wmin, sgn)) + { + kind = VR_VARYING; + return; + } + + if (TYPE_OVERFLOW_WRAPS (type)) + { + /* If overflow wraps, truncate the values and adjust the + range kind and bounds appropriately. */ + wide_int tmin = wide_int::from (wmin, prec, sgn); + wide_int tmax = wide_int::from (wmax, prec, sgn); + if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE)) + { + /* If the limits are swapped, we wrapped around and cover + the entire range. We have a similar check at the end of + extract_range_from_binary_expr. */ + if (wi::gt_p (tmin, tmax, sgn)) + kind = VR_VARYING; + else + { + kind = VR_RANGE; + /* No overflow or both overflow or underflow. The + range kind stays VR_RANGE. */ + min = wide_int_to_tree (type, tmin); + max = wide_int_to_tree (type, tmax); + } + return; + } + else if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE) + || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE)) + { + /* Min underflow or max overflow. The range kind + changes to VR_ANTI_RANGE. */ + bool covers = false; + wide_int tem = tmin; + tmin = tmax + 1; + if (wi::cmp (tmin, tmax, sgn) < 0) + covers = true; + tmax = tem - 1; + if (wi::cmp (tmax, tem, sgn) > 0) + covers = true; + /* If the anti-range would cover nothing, drop to varying. + Likewise if the anti-range bounds are outside of the + types values. */ + if (covers || wi::cmp (tmin, tmax, sgn) > 0) + { + kind = VR_VARYING; + return; + } + kind = VR_ANTI_RANGE; + min = wide_int_to_tree (type, tmin); + max = wide_int_to_tree (type, tmax); + return; + } + else + { + /* Other underflow and/or overflow, drop to VR_VARYING. */ + kind = VR_VARYING; + return; + } + } + else + { + /* If overflow does not wrap, saturate to the types min/max + value. */ + wide_int type_min = wi::min_value (prec, sgn); + wide_int type_max = wi::max_value (prec, sgn); + kind = VR_RANGE; + if (min_ovf == wi::OVF_UNDERFLOW) + min = wide_int_to_tree (type, type_min); + else if (min_ovf == wi::OVF_OVERFLOW) + min = wide_int_to_tree (type, type_max); + else + min = wide_int_to_tree (type, wmin); + + if (max_ovf == wi::OVF_UNDERFLOW) + max = wide_int_to_tree (type, type_min); + else if (max_ovf == wi::OVF_OVERFLOW) + max = wide_int_to_tree (type, type_max); + else + max = wide_int_to_tree (type, wmax); + } +} + /* Fold two value range's of a POINTER_PLUS_EXPR into VR. Return TRUE if successful. */ @@ -1781,17 +1889,16 @@ extract_range_from_binary_expr (value_range_base *vr, return; } - adjust_range_for_overflow (type, wmin, wmax, expr_type, - min_ovf, max_ovf, - TYPE_OVERFLOW_WRAPS (expr_type)); + /* Adjust the range for possible overflow. */ + min = NULL_TREE; + max = NULL_TREE; + set_value_range_with_overflow (type, min, max, expr_type, + wmin, wmax, min_ovf, max_ovf); if (type == VR_VARYING) { vr->set_varying (expr_type); return; } - gcc_assert (type != VR_UNDEFINED); - min = wide_int_to_tree (expr_type, wmin); - max = wide_int_to_tree (expr_type, wmax); /* Build the symbolic bounds if needed. */ adjust_symbolic_bound (min, code, expr_type, @@ -2419,7 +2526,11 @@ range_ops_fold_binary_expr (value_range_base *vr, /* Do the range-ops dance. */ value_range_base n0 = normalize_for_range_ops (vr0); value_range_base n1 = normalize_for_range_ops (vr1); +#if USE_IRANGE + *vr = irange_to_value_range (op->fold_range (expr_type, n0, n1)); +#else *vr = op->fold_range (expr_type, n0, n1); +#endif } /* Fold a unary expression of a value_range with range-ops. */ @@ -2477,7 +2588,11 @@ range_ops_fold_unary_expr (value_range_base *vr, /* Do the range-ops dance. */ value_range_base n0 = normalize_for_range_ops (*vr0); value_range_base n1 (expr_type); +#if USE_IRANGE + *vr = irange_to_value_range (op->fold_range (expr_type, n0, n1)); +#else *vr = op->fold_range (expr_type, n0, n1); +#endif } /* Generic folding of a binary expression between two value_ranges. @@ -6426,7 +6541,7 @@ value_range_base::intersect_helper (const value_range_base *vr0, if (vr0type == VR_UNDEFINED) tem.set_undefined (); else if (vr0type == VR_VARYING) - tem.set_varying (TREE_TYPE (vr0->min ())); + tem.set_varying (vr0->type ()); else tem.set (vr0type, vr0min, vr0max); /* If that failed, use the saved original VR0. */ @@ -6665,7 +6780,9 @@ value_range_base::normalize_symbolics () const tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1); return value_range_base (VR_RANGE, vrp_val_min (ttype), n); } - return value_range_base (ttype); + value_range_base var; + var.set_varying (ttype); + return var; } unsigned diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index 595a37fd0fc..a934a34efb6 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -20,6 +20,21 @@ 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 +}; + class value_range_storage; /* Range of values that can be associated with an SSA_NAME after VRP @@ -37,10 +52,6 @@ public: value_range_base (tree type, const wide_int &, const wide_int &); value_range_base (tree type, const value_range_storage *); value_range_base (tree type); -#if USE_IRANGE - /* Only for branch. */ - value_range_base (const irange &ir) { *this = irange_to_value_range (ir); } -#endif void set (value_range_kind, tree, tree); void set (tree); @@ -78,7 +89,6 @@ public: static bool supports_type_p (tree); value_range_base normalize_symbolics () const; - /* Support machinery for irange. */ static const unsigned int m_max_pairs = 2; static bool supports_ssa_p (tree ssa); static bool supports_p (tree expr); diff --git a/gcc/vr-values.c b/gcc/vr-values.c index 04e7573e3ad..b71291580dc 100644 --- a/gcc/vr-values.c +++ b/gcc/vr-values.c @@ -52,67 +52,6 @@ along with GCC; see the file COPYING3. If not see #include "range-op.h" #include "wide-int-range.h" - -/* Cache VARYING value_ranges indexed by type. */ -class type_range_cache -{ -public: - type_range_cache (); - ~type_range_cache (); - value_range *varying_range (tree type); -private: - value_range *new_varying (tree type); - hash_map *m_type_table; - obstack m_range_obj; -}; - -/* Delete type cache. */ -type_range_cache::~type_range_cache () -{ - delete m_type_table; - obstack_free (&m_range_obj, NULL); -} - -/* Create a new type cache. */ -type_range_cache::type_range_cache () -{ - /* Allocate a map and a local obstack. */ - m_type_table = new hash_map; - gcc_obstack_init (&m_range_obj); -} - -/* Allocate a new range from the obstack and set it to VARYING for TYPE. */ -inline value_range * -type_range_cache::new_varying (tree type) -{ - /* Allocate memory. */ - void *p = XOBNEW (&m_range_obj, value_range); - /* Invoke the constructors on the memory using placement new. */ - value_range *new_p = new (p) value_range (); - /* Initialize it to varying. */ - new_p->set_varying (type); - return new_p; -} - -/* Return a varying object for TYPE. If it already exists, return it. - Otherwise allocate a new one and register it in the table. */ -value_range * -type_range_cache::varying_range (tree type) -{ - bool existed; - value_range *&slot = m_type_table->get_or_insert (type, &existed); - if (!existed) - slot = new_varying (type); - else - { - /* Sanity check to ensure this varying hasn't been modified. */ - value_range v; - v.set_varying (type); - gcc_checking_assert (v.equal_p (*slot, true)); - } - return slot; -} - /* Convert the value_range in this object to an irange. This function will normalize non-constant ranges into constant ranges by degrading them to VARYING. */ @@ -889,23 +828,6 @@ vr_values::extract_range_from_binary_expr (value_range *vr, vrp_val_max (expr_type)); } - /* Temporary testing hack. */ - if (getenv("HACK")) - { - value_range_base v; - tree type = signed_char_type_node; - enum tree_code code = BIT_AND_EXPR; - tree small = TYPE_MIN_VALUE (type); - small = fold_build2 (PLUS_EXPR, type, small, build_one_cst (type)); - value_range_base vr0 (VR_ANTI_RANGE, - small, - build_int_cst (type, 0)); - value_range_base vr1 (VR_RANGE, - build_int_cst (type, -1), - build_int_cst (type, 0)); - range_fold_binary_expr (&v, code, type, &vr0, &vr1); - } - range_fold_binary_expr (vr, code, expr_type, &vr0, &vr1); /* Set value_range for n in following sequence: @@ -1918,8 +1840,10 @@ range_misc::adjust_range_with_loop (irange &ir, class loop *loop, /* Normalize the ranges for INIT and TEM to a constant range, and call the generic extract_range_from_binary_expr. */ - value_range_base vr0 = get_irange (init, stmt); - value_range_base vr1 = get_irange (tem, stmt); + value_range_base vr0 + = irange_to_value_range (get_irange (init, stmt)); + value_range_base vr1 + = irange_to_value_range (get_irange (tem, stmt)); value_range_base maxvr; range_fold_binary_expr (&maxvr, PLUS_EXPR, TREE_TYPE (init), &vr0, &vr1); @@ -2030,7 +1954,7 @@ vr_values::adjust_range_with_scev (value_range_base *vr, struct loop *loop, return; irange ir = *vr; adjust_range_with_loop (ir, loop, stmt, var); - *vr = ir; + *vr = irange_to_value_range (ir); } /* Dump value ranges of all SSA_NAMEs to FILE. */ @@ -2065,14 +1989,12 @@ vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges") bitmap_obstack_initialize (&vrp_equiv_obstack); to_remove_edges = vNULL; to_update_switch_stmts = vNULL; - type_cache = new type_range_cache; } /* Free VRP lattice. */ vr_values::~vr_values () { - delete type_cache; /* Free allocated memory. */ free (vr_value); free (vr_phi_edge_counts); @@ -3762,7 +3684,7 @@ vr_values::simplify_switch_using_ranges (gswitch *stmt) if (TREE_CODE (op) == SSA_NAME) { // FIXME: We should convert this entire function to iranges. - vr_obj = get_irange (op, stmt); + vr_obj = irange_to_value_range (get_irange (op, stmt)); vr = &vr_obj; /* We can only handle integer ranges. */ diff --git a/gcc/vr-values.h b/gcc/vr-values.h index ea4c6b6e3ba..adf72a16f69 100644 --- a/gcc/vr-values.h +++ b/gcc/vr-values.h @@ -168,7 +168,6 @@ class vr_values : public range_misc tree vec; }; - class type_range_cache *type_cache; vec to_remove_edges; vec to_update_switch_stmts; }; diff --git a/gcc/wide-int-range.cc b/gcc/wide-int-range.cc index 09538aff995..90c58f6bb6e 100644 --- a/gcc/wide-int-range.cc +++ b/gcc/wide-int-range.cc @@ -36,7 +36,7 @@ along with GCC; see the file COPYING3. If not see Return false for division by zero, for which the result is indeterminate. */ -bool +static bool wide_int_binop_overflow (wide_int &res, enum tree_code code, const wide_int &w0, const wide_int &w1, @@ -863,105 +863,3 @@ wide_int_range_div (wide_int &wmin, wide_int &wmax, extra_range_p = false; return true; } - -/* Adjust the range in [WMIN, WMAX] for possible overflow and store the - parts of the resulting range in KIND, WMIN, WMAX. - - TYPE is the type of the range. - - MIN_OVF and MAX_OVF indicate what type of overflow, if any, - occurred while originally calculating WMIN or WMAX. */ - -void -adjust_range_for_overflow (value_range_kind &kind, - wide_int &wmin, wide_int &wmax, - tree type, - wi::overflow_type min_ovf, - wi::overflow_type max_ovf, - bool overflow_wraps) -{ - const signop sgn = TYPE_SIGN (type); - const unsigned int prec = TYPE_PRECISION (type); - - /* For one bit precision if max < min, then the swapped - range covers all values. */ - if (prec == 1 && wi::lt_p (wmax, wmin, sgn)) - { - kind = VR_VARYING; - return; - } - - if (overflow_wraps) - { - /* If overflow wraps, truncate the values and adjust the - range kind and bounds appropriately. */ - wide_int tmin = wide_int::from (wmin, prec, sgn); - wide_int tmax = wide_int::from (wmax, prec, sgn); - if ((min_ovf != wi::OVF_NONE) == (max_ovf != wi::OVF_NONE)) - { - /* If the limits are swapped, we wrapped around and cover - the entire range. We have a similar check at the end of - extract_range_from_binary_expr. */ - if (wi::gt_p (tmin, tmax, sgn)) - kind = VR_VARYING; - else - { - kind = VR_RANGE; - /* No overflow or both overflow or underflow. The - range kind stays VR_RANGE. */ - wmin = tmin; - wmax = tmax; - } - return; - } - else if ((min_ovf == wi::OVF_UNDERFLOW && max_ovf == wi::OVF_NONE) - || (max_ovf == wi::OVF_OVERFLOW && min_ovf == wi::OVF_NONE)) - { - /* Min underflow or max overflow. The range kind - changes to VR_ANTI_RANGE. */ - bool covers = false; - wide_int tem = tmin; - tmin = tmax + 1; - if (wi::cmp (tmin, tmax, sgn) < 0) - covers = true; - tmax = tem - 1; - if (wi::cmp (tmax, tem, sgn) > 0) - covers = true; - /* If the anti-range would cover nothing, drop to varying. - Likewise if the anti-range bounds are outside of the - types values. */ - if (covers || wi::cmp (tmin, tmax, sgn) > 0) - { - kind = VR_VARYING; - return; - } - kind = VR_ANTI_RANGE; - wmin = tmin; - wmax = tmax; - return; - } - else - { - /* Other underflow and/or overflow, drop to VR_VARYING. */ - kind = VR_VARYING; - return; - } - } - else - { - /* If overflow does not wrap, saturate to the types min/max - value. */ - wide_int type_min = wi::min_value (prec, sgn); - wide_int type_max = wi::max_value (prec, sgn); - kind = VR_RANGE; - if (min_ovf == wi::OVF_UNDERFLOW) - wmin = type_min; - else if (min_ovf == wi::OVF_OVERFLOW) - wmin = type_max; - - if (max_ovf == wi::OVF_UNDERFLOW) - wmax = type_min; - else if (max_ovf == wi::OVF_OVERFLOW) - wmax = type_max; - } -} diff --git a/gcc/wide-int-range.h b/gcc/wide-int-range.h index e2c8f88a38e..fc9af72b127 100644 --- a/gcc/wide-int-range.h +++ b/gcc/wide-int-range.h @@ -185,17 +185,4 @@ wide_int_range_zero_p (const wide_int &wmin, const wide_int &wmax, return wmin == wmax && wi::eq_p (wmin, wi::zero (prec)); } -void -adjust_range_for_overflow (value_range_kind &, - wide_int &, wide_int &, - tree type, - wi::overflow_type, wi::overflow_type, - bool overflow_wraps); - -bool -wide_int_binop_overflow (wide_int &res, - enum tree_code code, - const wide_int &w0, const wide_int &w1, - signop sign, bool overflow_undefined); - #endif /* GCC_WIDE_INT_RANGE_H */ -- cgit v1.2.3