diff options
| -rw-r--r-- | gcc/Makefile.in | 2 | ||||
| -rw-r--r-- | gcc/gengtype-lex.l | 5 | ||||
| -rw-r--r-- | gcc/ipa-cp.c | 7 | ||||
| -rw-r--r-- | gcc/ipa-fnsummary.c | 20 | ||||
| -rw-r--r-- | gcc/ipa-prop.c | 2 | ||||
| -rw-r--r-- | gcc/ipa-prop.h | 2 | ||||
| -rw-r--r-- | gcc/range-op.cc | 1952 | ||||
| -rw-r--r-- | gcc/range-op.h | 22 | ||||
| -rw-r--r-- | gcc/tree-vrp.c | 32 | ||||
| -rw-r--r-- | gcc/tree-vrp.h | 2 | ||||
| -rw-r--r-- | gcc/tree.c | 85 | ||||
| -rw-r--r-- | gcc/value-range-equiv.cc | 20 | ||||
| -rw-r--r-- | gcc/value-range.cc | 1292 | ||||
| -rw-r--r-- | gcc/value-range.h | 597 | ||||
| -rw-r--r-- | gcc/vr-values.c | 3 |
15 files changed, 2868 insertions, 1175 deletions
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 4208c62..7251c00 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -2628,13 +2628,13 @@ GTFILES = $(CPPLIB_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/tree-ssa-alias.h \ $(srcdir)/tree-ssanames.h \ $(srcdir)/tree-vrp.h \ + $(srcdir)/value-range.h \ $(srcdir)/ipa-prop.h \ $(srcdir)/trans-mem.c \ $(srcdir)/lto-streamer.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-lex.l b/gcc/gengtype-lex.l index a5e9d2b..9bf6ffa 100644 --- a/gcc/gengtype-lex.l +++ b/gcc/gengtype-lex.l @@ -125,7 +125,10 @@ CXX_KEYWORD inline|public:|private:|protected:|template|operator|friend|static|m "ptr_alias"/{EOID} { return PTR_ALIAS; } "nested_ptr"/{EOID} { return NESTED_PTR; } "user"/{EOID} { return USER_GTY; } -[0-9]+ { return NUM; } +[0-9]+ { + *yylval = XDUPVAR (const char, yytext, yyleng, yyleng+1); + return NUM; +} {IWORD}({WS}{IWORD})*/{EOID} | "ENUM_BITFIELD"{WS}?"("{WS}?{ID}{WS}?")" { diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index fe010ff..10cc595 100644 --- a/gcc/ipa-cp.c +++ b/gcc/ipa-cp.c @@ -1270,6 +1270,7 @@ initialize_node_lattices (struct cgraph_node *node) plats->ctxlat.set_to_bottom (); set_agg_lats_to_bottom (plats); plats->bits_lattice.set_to_bottom (); + plats->m_value_range.m_vr = value_range (); plats->m_value_range.set_to_bottom (); } else @@ -3898,8 +3899,10 @@ ipcp_propagate_stage (class ipa_topo_info *topo) { class ipa_node_params *info = IPA_NODE_REF (node); determine_versionability (node, info); - info->lattices = XCNEWVEC (class ipcp_param_lattices, - ipa_get_param_count (info)); + + unsigned nlattices = ipa_get_param_count (info); + void *chunk = XCNEWVEC (class ipcp_param_lattices, nlattices); + info->lattices = new (chunk) ipcp_param_lattices[nlattices]; initialize_node_lattices (node); } ipa_size_summary *s = ipa_size_summaries->get (node); diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c index 55a0b27..49bab04 100644 --- a/gcc/ipa-fnsummary.c +++ b/gcc/ipa-fnsummary.c @@ -82,6 +82,7 @@ along with GCC; see the file COPYING3. If not see #include "gimplify.h" #include "stringpool.h" #include "attribs.h" +#include <vector> #include "tree-into-ssa.h" /* Summaries. */ @@ -330,7 +331,7 @@ static void evaluate_conditions_for_known_args (struct cgraph_node *node, bool inline_p, vec<tree> known_vals, - vec<value_range> known_value_ranges, + const std::vector<value_range> &known_value_ranges, vec<ipa_agg_value_set> known_aggs, clause_t *ret_clause, clause_t *ret_nonspec_clause) @@ -445,7 +446,7 @@ evaluate_conditions_for_known_args (struct cgraph_node *node, continue; } } - if (c->operand_num < (int) known_value_ranges.length () + if (c->operand_num < (int) known_value_ranges.size () && !c->agg_contents && !known_value_ranges[c->operand_num].undefined_p () && !known_value_ranges[c->operand_num].varying_p () @@ -554,7 +555,7 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p, { struct cgraph_node *callee = e->callee->ultimate_alias_target (); class ipa_fn_summary *info = ipa_fn_summaries->get (callee); - auto_vec<value_range, 32> known_value_ranges; + std::vector<value_range> known_value_ranges (32); class ipa_edge_args *args; if (clause_ptr) @@ -629,8 +630,12 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p, i)); if (!vr.undefined_p () && !vr.varying_p ()) { - if (!known_value_ranges.length ()) - known_value_ranges.safe_grow_cleared (count); + if (!known_value_ranges.size ()) + { + known_value_ranges.resize (count); + for (int i = 0; i < count; ++i) + known_value_ranges[i].set_undefined (); + } known_value_ranges[i] = vr; } } @@ -803,7 +808,7 @@ ipa_fn_summary_t::duplicate (cgraph_node *src, } evaluate_conditions_for_known_args (dst, false, known_vals, - vNULL, + std::vector<value_range> (), vNULL, &possible_truths, /* We are going to specialize, @@ -3687,7 +3692,8 @@ estimate_ipcp_clone_size_and_time (struct cgraph_node *node, clause_t clause, nonspec_clause; /* TODO: Also pass known value ranges. */ - evaluate_conditions_for_known_args (node, false, known_vals, vNULL, + evaluate_conditions_for_known_args (node, false, known_vals, + std::vector<value_range> (), known_aggs, &clause, &nonspec_clause); ipa_call_context ctx (node, clause, nonspec_clause, known_vals, known_contexts, diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c index 71ac0e1..da50f08 100644 --- a/gcc/ipa-prop.c +++ b/gcc/ipa-prop.c @@ -2059,7 +2059,7 @@ ipa_get_value_range (value_range *tmp) if (*slot) return *slot; - value_range *vr = ggc_alloc<value_range> (); + value_range *vr = new (ggc_alloc<value_range> ()) value_range; *vr = *tmp; *slot = vr; diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index 168c4c2..23fcf90 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -318,7 +318,7 @@ struct GTY (()) ipa_jump_func /* Information about value range, containing valid data only when vr_known is true. The pointed to structure is shared betweed different jump functions. Use ipa_set_jfunc_vr to set this field. */ - class value_range *m_vr; + value_range *m_vr; enum jump_func_type type; /* Represents a value of a jump function. pass_through is used only in jump diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 5df075b..c62e397 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -63,15 +63,17 @@ min_limit (const_tree type) } // If the range of either op1 or op2 is undefined, set the result to -// undefined and return TRUE. +// varying and return TRUE. If the caller truely cares about a result, +// they should pass in a varying if it has an undefined that it wants +// treated as a varying. inline bool -empty_range_check (value_range &r, - const value_range &op1, const value_range & op2) +empty_range_varying (irange &r, tree type, + const irange &op1, const irange & op2) { if (op1.undefined_p () || op2.undefined_p ()) { - r.set_undefined (); + r.set_varying (type); return true; } else @@ -82,11 +84,11 @@ empty_range_check (value_range &r, // the appropriate range. static inline bool -undefined_shift_range_check (value_range &r, tree type, const value_range op) +undefined_shift_range_check (irange &r, tree type, const irange &op) { if (op.undefined_p ()) { - r = value_range (); + r.set_undefined (); return true; } @@ -98,7 +100,7 @@ undefined_shift_range_check (value_range &r, tree type, const value_range op) || wi::ge_p (op.upper_bound (), TYPE_PRECISION (type), TYPE_SIGN (op.type ()))) { - r = value_range (type); + r.set_varying (type); return true; } return false; @@ -125,32 +127,43 @@ wi_zero_p (tree type, const wide_int &wmin, const wide_int &wmax) // Default wide_int fold operation returns [MIN, MAX]. void -range_operator::wi_fold (value_range &r, tree type, +range_operator::wi_fold (irange &r, tree type, const wide_int &lh_lb ATTRIBUTE_UNUSED, const wide_int &lh_ub ATTRIBUTE_UNUSED, const wide_int &rh_lb ATTRIBUTE_UNUSED, const wide_int &rh_ub ATTRIBUTE_UNUSED) const { - gcc_checking_assert (value_range::supports_type_p (type)); - r = value_range (type); + gcc_checking_assert (irange::supports_type_p (type)); + r.set_varying (type); } // The default for fold is to break all ranges into sub-ranges and // invoke the wi_fold method on each sub-range pair. bool -range_operator::fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const +range_operator::fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const { - gcc_checking_assert (value_range::supports_type_p (type)); - if (empty_range_check (r, lh, rh)) + gcc_checking_assert (irange::supports_type_p (type)); + if (empty_range_varying (r, type, lh, rh)) return true; - value_range tmp; + unsigned num_lh = lh.num_pairs (); + unsigned num_rh = rh.num_pairs (); + + // If both ranges are single pairs, fold directly into the result range. + if (num_lh == 1 && num_rh == 1) + { + wi_fold (r, type, lh.lower_bound (0), lh.upper_bound (0), + rh.lower_bound (0), rh.upper_bound (0)); + return true; + } + + widest_irange tmp; r.set_undefined (); - for (unsigned x = 0; x < lh.num_pairs (); ++x) - for (unsigned y = 0; y < rh.num_pairs (); ++y) + for (unsigned x = 0; x < num_lh; ++x) + for (unsigned y = 0; y < num_rh; ++y) { wide_int lh_lb = lh.lower_bound (x); wide_int lh_ub = lh.upper_bound (x); @@ -167,10 +180,10 @@ range_operator::fold_range (value_range &r, tree type, // The default for op1_range is to return false. bool -range_operator::op1_range (value_range &r ATTRIBUTE_UNUSED, +range_operator::op1_range (irange &r ATTRIBUTE_UNUSED, tree type ATTRIBUTE_UNUSED, - const value_range &lhs ATTRIBUTE_UNUSED, - const value_range &op2 ATTRIBUTE_UNUSED) const + const irange &lhs ATTRIBUTE_UNUSED, + const irange &op2 ATTRIBUTE_UNUSED) const { return false; } @@ -178,10 +191,10 @@ range_operator::op1_range (value_range &r ATTRIBUTE_UNUSED, // The default for op2_range is to return false. bool -range_operator::op2_range (value_range &r ATTRIBUTE_UNUSED, +range_operator::op2_range (irange &r ATTRIBUTE_UNUSED, tree type ATTRIBUTE_UNUSED, - const value_range &lhs ATTRIBUTE_UNUSED, - const value_range &op1 ATTRIBUTE_UNUSED) const + const irange &lhs ATTRIBUTE_UNUSED, + const irange &op1 ATTRIBUTE_UNUSED) const { return false; } @@ -191,7 +204,7 @@ range_operator::op2_range (value_range &r ATTRIBUTE_UNUSED, // to have overflowed (or underflowed). static void -value_range_from_overflowed_bounds (value_range &r, tree type, +value_range_from_overflowed_bounds (irange &r, tree type, const wide_int &wmin, const wide_int &wmax) { @@ -214,9 +227,13 @@ value_range_from_overflowed_bounds (value_range &r, tree type, // Likewise if the anti-range bounds are outside of the types // values. if (covers || wi::cmp (tmin, tmax, sgn) > 0) - r = value_range (type); + r.set_varying (type); else - r = value_range (type, tmin, tmax, VR_ANTI_RANGE); + { + tree tree_min = wide_int_to_tree (type, tmin); + tree tree_max = wide_int_to_tree (type, tmax); + r.set (tree_min, tree_max, VR_ANTI_RANGE); + } } // Create and return a range from a pair of wide-ints. MIN_OVF and @@ -224,7 +241,7 @@ value_range_from_overflowed_bounds (value_range &r, tree type, // calculating WMIN and WMAX respectively. static void -value_range_with_overflow (value_range &r, tree type, +value_range_with_overflow (irange &r, tree type, const wide_int &wmin, const wide_int &wmax, wi::overflow_type min_ovf = wi::OVF_NONE, wi::overflow_type max_ovf = wi::OVF_NONE) @@ -237,7 +254,7 @@ value_range_with_overflow (value_range &r, tree type, // values. if (prec == 1 && wi::ne_p (wmax, wmin)) { - r = value_range (type); + r.set_varying (type); return; } @@ -252,11 +269,12 @@ value_range_with_overflow (value_range &r, tree type, // If the limits are swapped, we wrapped around and cover // the entire range. if (wi::gt_p (tmin, tmax, sgn)) - r = value_range (type); + r.set_varying (type); else // No overflow or both overflow or underflow. The range // kind stays normal. - r = value_range (type, tmin, tmax); + r.set (wide_int_to_tree (type, tmin), + wide_int_to_tree (type, tmax)); return; } @@ -265,7 +283,7 @@ value_range_with_overflow (value_range &r, tree type, value_range_from_overflowed_bounds (r, type, wmin, wmax); else // Other underflow and/or overflow, drop to VR_VARYING. - r = value_range (type); + r.set_varying (type); } else { @@ -285,7 +303,8 @@ value_range_with_overflow (value_range &r, tree type, else new_ub = wmax; - r = value_range (type, new_lb, new_ub); + r.set (wide_int_to_tree (type, new_lb), + wide_int_to_tree (type, new_ub)); } } @@ -294,7 +313,7 @@ value_range_with_overflow (value_range &r, tree type, // [10,5] into [MIN,5][10,MAX]. static inline void -create_possibly_reversed_range (value_range &r, tree type, +create_possibly_reversed_range (irange &r, tree type, const wide_int &new_lb, const wide_int &new_ub) { signop s = TYPE_SIGN (type); @@ -302,35 +321,35 @@ create_possibly_reversed_range (value_range &r, tree type, if (wi::gt_p (new_lb, new_ub, s)) value_range_from_overflowed_bounds (r, type, new_lb, new_ub); else - // Otherwise its just a normal range. - r = value_range (type, new_lb, new_ub); + // Otherwise it's just a normal range. + r.set (wide_int_to_tree (type, new_lb), wide_int_to_tree (type, new_ub)); } -// Return a value_range instance that is a boolean TRUE. +// Return an irange instance that is a boolean TRUE. -static inline value_range +static inline int_range<1> range_true (tree type) { unsigned prec = TYPE_PRECISION (type); - return value_range (type, wi::one (prec), wi::one (prec)); + return int_range<1> (type, wi::one (prec), wi::one (prec)); } -// Return a value_range instance that is a boolean FALSE. +// Return an irange instance that is a boolean FALSE. -static inline value_range +static inline int_range<1> range_false (tree type) { unsigned prec = TYPE_PRECISION (type); - return value_range (type, wi::zero (prec), wi::zero (prec)); + return int_range<1> (type, wi::zero (prec), wi::zero (prec)); } -// Return a value_range that covers both true and false. +// Return an irange that covers both true and false. -static inline value_range +static inline int_range<1> range_true_and_false (tree type) { unsigned prec = TYPE_PRECISION (type); - return value_range (type, wi::zero (prec), wi::one (prec)); + return int_range<1> (type, wi::zero (prec), wi::one (prec)); } enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL }; @@ -341,7 +360,7 @@ enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL }; // the bool range. static bool_range_state -get_bool_state (value_range &r, const value_range &lhs, tree val_type) +get_bool_state (irange &r, const irange &lhs, tree val_type) { // If there is no result, then this is unexecutable. if (lhs.undefined_p ()) @@ -350,16 +369,16 @@ get_bool_state (value_range &r, const value_range &lhs, tree val_type) return BRS_EMPTY; } - // If the bounds aren't the same, then it's not a constant. - if (!wi::eq_p (lhs.upper_bound (), lhs.lower_bound ())) + if (lhs.zero_p ()) + return BRS_FALSE; + + // For TRUE, we can't just test for [1,1] because Ada can have + // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc. + if (lhs.contains_p (build_zero_cst (lhs.type ()))) { r.set_varying (val_type); return BRS_FULL; } - - if (lhs.zero_p ()) - return BRS_FALSE; - return BRS_TRUE; } @@ -367,23 +386,23 @@ get_bool_state (value_range &r, const value_range &lhs, tree val_type) class operator_equal : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &val) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &val) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &val) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &val) const; } op_equal; bool -operator_equal::fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const +operator_equal::fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const { - if (empty_range_check (r, op1, op2)) + if (empty_range_varying (r, type, op1, op2)) return true; // We can be sure the values are always equal or not if both ranges @@ -411,9 +430,9 @@ operator_equal::fold_range (value_range &r, tree type, } bool -operator_equal::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_equal::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { switch (get_bool_state (r, lhs, type)) { @@ -441,9 +460,9 @@ operator_equal::op1_range (value_range &r, tree type, } bool -operator_equal::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_equal::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { return operator_equal::op1_range (r, type, lhs, op1); } @@ -452,23 +471,23 @@ operator_equal::op2_range (value_range &r, tree type, class operator_not_equal : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_not_equal; bool -operator_not_equal::fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const +operator_not_equal::fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const { - if (empty_range_check (r, op1, op2)) + if (empty_range_varying (r, type, op1, op2)) return true; // We can be sure the values are always equal or not if both ranges @@ -496,9 +515,9 @@ operator_not_equal::fold_range (value_range &r, tree type, } bool -operator_not_equal::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_not_equal::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { switch (get_bool_state (r, lhs, type)) { @@ -527,9 +546,9 @@ operator_not_equal::op1_range (value_range &r, tree type, bool -operator_not_equal::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_not_equal::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { return operator_not_equal::op1_range (r, type, lhs, op1); } @@ -537,7 +556,7 @@ operator_not_equal::op2_range (value_range &r, tree type, // (X < VAL) produces the range of [MIN, VAL - 1]. static void -build_lt (value_range &r, tree type, const wide_int &val) +build_lt (irange &r, tree type, const wide_int &val) { wi::overflow_type ov; wide_int lim = wi::sub (val, 1, TYPE_SIGN (type), &ov); @@ -546,21 +565,21 @@ build_lt (value_range &r, tree type, const wide_int &val) if (ov) r.set_undefined (); else - r = value_range (type, min_limit (type), lim); + r = int_range<1> (type, min_limit (type), lim); } // (X <= VAL) produces the range of [MIN, VAL]. static void -build_le (value_range &r, tree type, const wide_int &val) +build_le (irange &r, tree type, const wide_int &val) { - r = value_range (type, min_limit (type), val); + r = int_range<1> (type, min_limit (type), val); } // (X > VAL) produces the range of [VAL + 1, MAX]. static void -build_gt (value_range &r, tree type, const wide_int &val) +build_gt (irange &r, tree type, const wide_int &val) { wi::overflow_type ov; wide_int lim = wi::add (val, 1, TYPE_SIGN (type), &ov); @@ -568,38 +587,38 @@ build_gt (value_range &r, tree type, const wide_int &val) if (ov) r.set_undefined (); else - r = value_range (type, lim, max_limit (type)); + r = int_range<1> (type, lim, max_limit (type)); } // (X >= val) produces the range of [VAL, MAX]. static void -build_ge (value_range &r, tree type, const wide_int &val) +build_ge (irange &r, tree type, const wide_int &val) { - r = value_range (type, val, max_limit (type)); + r = int_range<1> (type, val, max_limit (type)); } class operator_lt : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_lt; bool -operator_lt::fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const +operator_lt::fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const { - if (empty_range_check (r, op1, op2)) + if (empty_range_varying (r, type, op1, op2)) return true; signop sign = TYPE_SIGN (op1.type ()); @@ -615,9 +634,9 @@ operator_lt::fold_range (value_range &r, tree type, } bool -operator_lt::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_lt::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { switch (get_bool_state (r, lhs, type)) { @@ -636,9 +655,9 @@ operator_lt::op1_range (value_range &r, tree type, } bool -operator_lt::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_lt::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { switch (get_bool_state (r, lhs, type)) { @@ -660,23 +679,23 @@ operator_lt::op2_range (value_range &r, tree type, class operator_le : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_le; bool -operator_le::fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const +operator_le::fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const { - if (empty_range_check (r, op1, op2)) + if (empty_range_varying (r, type, op1, op2)) return true; signop sign = TYPE_SIGN (op1.type ()); @@ -692,9 +711,9 @@ operator_le::fold_range (value_range &r, tree type, } bool -operator_le::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_le::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { switch (get_bool_state (r, lhs, type)) { @@ -713,9 +732,9 @@ operator_le::op1_range (value_range &r, tree type, } bool -operator_le::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_le::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { switch (get_bool_state (r, lhs, type)) { @@ -737,22 +756,22 @@ operator_le::op2_range (value_range &r, tree type, class operator_gt : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_gt; bool -operator_gt::fold_range (value_range &r, tree type, - const value_range &op1, const value_range &op2) const +operator_gt::fold_range (irange &r, tree type, + const irange &op1, const irange &op2) const { - if (empty_range_check (r, op1, op2)) + if (empty_range_varying (r, type, op1, op2)) return true; signop sign = TYPE_SIGN (op1.type ()); @@ -768,8 +787,8 @@ operator_gt::fold_range (value_range &r, tree type, } bool -operator_gt::op1_range (value_range &r, tree type, - const value_range &lhs, const value_range &op2) const +operator_gt::op1_range (irange &r, tree type, + const irange &lhs, const irange &op2) const { switch (get_bool_state (r, lhs, type)) { @@ -788,9 +807,9 @@ operator_gt::op1_range (value_range &r, tree type, } bool -operator_gt::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_gt::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { switch (get_bool_state (r, lhs, type)) { @@ -812,23 +831,23 @@ operator_gt::op2_range (value_range &r, tree type, class operator_ge : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_ge; bool -operator_ge::fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const +operator_ge::fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const { - if (empty_range_check (r, op1, op2)) + if (empty_range_varying (r, type, op1, op2)) return true; signop sign = TYPE_SIGN (op1.type ()); @@ -844,9 +863,9 @@ operator_ge::fold_range (value_range &r, tree type, } bool -operator_ge::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_ge::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { switch (get_bool_state (r, lhs, type)) { @@ -865,9 +884,9 @@ operator_ge::op1_range (value_range &r, tree type, } bool -operator_ge::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_ge::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { switch (get_bool_state (r, lhs, type)) { @@ -889,13 +908,13 @@ operator_ge::op2_range (value_range &r, tree type, class operator_plus : public range_operator { public: - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; - virtual void wi_fold (value_range &r, tree type, + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -903,7 +922,7 @@ public: } op_plus; void -operator_plus::wi_fold (value_range &r, tree type, +operator_plus::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const { @@ -915,17 +934,17 @@ operator_plus::wi_fold (value_range &r, tree type, } bool -operator_plus::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_plus::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op2); } bool -operator_plus::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_plus::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op1); } @@ -934,13 +953,13 @@ operator_plus::op2_range (value_range &r, tree type, class operator_minus : public range_operator { public: - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; - virtual void wi_fold (value_range &r, tree type, + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -948,7 +967,7 @@ public: } op_minus; void -operator_minus::wi_fold (value_range &r, tree type, +operator_minus::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const { @@ -960,17 +979,17 @@ operator_minus::wi_fold (value_range &r, tree type, } bool -operator_minus::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_minus::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { return range_op_handler (PLUS_EXPR, type)->fold_range (r, type, lhs, op2); } bool -operator_minus::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_minus::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { return fold_range (r, type, op1, lhs); } @@ -979,7 +998,7 @@ operator_minus::op2_range (value_range &r, tree type, class operator_min : public range_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -987,7 +1006,7 @@ public: } op_min; void -operator_min::wi_fold (value_range &r, tree type, +operator_min::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const { @@ -1001,7 +1020,7 @@ operator_min::wi_fold (value_range &r, tree type, class operator_max : public range_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -1009,7 +1028,7 @@ public: } op_max; void -operator_max::wi_fold (value_range &r, tree type, +operator_max::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const { @@ -1031,7 +1050,7 @@ public: const wide_int &) const = 0; // Calculate the cross product of two sets of sub-ranges and return it. - void wi_cross_product (value_range &r, tree type, + void wi_cross_product (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -1052,7 +1071,7 @@ public: // figure the smallest and largest values to form the new range. void -cross_product_operator::wi_cross_product (value_range &r, tree type, +cross_product_operator::wi_cross_product (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -1060,7 +1079,7 @@ cross_product_operator::wi_cross_product (value_range &r, tree type, { wide_int cp1, cp2, cp3, cp4; // Default to varying. - r = value_range (type); + r.set_varying (type); // Compute the 4 cross operations, bailing if we get an overflow we // can't handle. @@ -1096,16 +1115,47 @@ cross_product_operator::wi_cross_product (value_range &r, tree type, class operator_mult : public cross_product_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; virtual bool wi_op_overflows (wide_int &res, tree type, const wide_int &w0, const wide_int &w1) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_mult; bool +operator_mult::op1_range (irange &r, tree type, + const irange &lhs, const irange &op2) const +{ + tree offset; + + // We can't solve 0 = OP1 * N by dividing by N with a wrapping type. + // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas + // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit) + if (TYPE_OVERFLOW_WRAPS (type)) + return false; + + if (op2.singleton_p (&offset) && !integer_zerop (offset)) + return range_op_handler (TRUNC_DIV_EXPR, type)->fold_range (r, type, + lhs, op2); + return false; +} + +bool +operator_mult::op2_range (irange &r, tree type, + const irange &lhs, const irange &op1) const +{ + return operator_mult::op1_range (r, type, lhs, op1); +} + +bool operator_mult::wi_op_overflows (wide_int &res, tree type, const wide_int &w0, const wide_int &w1) const { @@ -1126,7 +1176,7 @@ operator_mult::wi_op_overflows (wide_int &res, tree type, } void -operator_mult::wi_fold (value_range &r, tree type, +operator_mult::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const { @@ -1195,7 +1245,7 @@ operator_mult::wi_fold (value_range &r, tree type, prod2 = prod3 - prod0; if (wi::geu_p (prod2, sizem1)) // The range covers all values. - r = value_range (type); + r.set_varying (type); else { wide_int new_lb = wide_int::from (prod0, prec, sign); @@ -1209,7 +1259,7 @@ class operator_div : public cross_product_operator { public: operator_div (enum tree_code c) { code = c; } - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -1263,14 +1313,14 @@ operator_div::wi_op_overflows (wide_int &res, tree type, } void -operator_div::wi_fold (value_range &r, tree type, +operator_div::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const { // If we know we will divide by zero, return undefined. if (rh_lb == 0 && rh_ub == 0) { - r = value_range (); + r.set_undefined (); return; } @@ -1293,14 +1343,14 @@ operator_div::wi_fold (value_range &r, tree type, // If flag_non_call_exceptions, we must not eliminate a division by zero. if (cfun->can_throw_non_call_exceptions) { - r = value_range (type); + r.set_varying (type); return; } // If we're definitely dividing by zero, there's nothing to do. if (wi_zero_p (type, divisor_min, divisor_max)) { - r = value_range (); + r.set_undefined (); return; } @@ -1312,12 +1362,12 @@ operator_div::wi_fold (value_range &r, tree type, wi_cross_product (r, type, dividend_min, dividend_max, divisor_min, wi::minus_one (prec)); else - r = value_range (); + r.set_undefined (); // Then divide by the non-zero positive numbers, if any. if (wi::gt_p (divisor_max, wi::zero (prec), sign)) { - value_range tmp; + widest_irange tmp; wi_cross_product (tmp, type, dividend_min, dividend_max, wi::one (prec), divisor_max); r.union_ (tmp); @@ -1336,16 +1386,16 @@ class operator_exact_divide : public operator_div { public: operator_exact_divide () : operator_div (TRUNC_DIV_EXPR) { } - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; } op_exact_div; bool -operator_exact_divide::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_exact_divide::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { tree offset; // [2, 4] = op1 / [3,3] since its exact divide, no need to worry about @@ -1364,11 +1414,14 @@ operator_exact_divide::op1_range (value_range &r, tree type, class operator_lshift : public cross_product_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - - virtual void wi_fold (value_range &r, tree type, + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; virtual bool wi_op_overflows (wide_int &res, @@ -1378,9 +1431,9 @@ public: } op_lshift; bool -operator_lshift::fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const +operator_lshift::fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const { if (undefined_shift_range_check (r, type, op2)) return true; @@ -1390,15 +1443,14 @@ operator_lshift::fold_range (value_range &r, tree type, { unsigned shift = op2.lower_bound ().to_uhwi (); wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type)); - value_range mult (type, tmp, tmp); + int_range<1> mult (type, tmp, tmp); // Force wrapping multiplication. bool saved_flag_wrapv = flag_wrapv; bool saved_flag_wrapv_pointer = flag_wrapv_pointer; flag_wrapv = 1; flag_wrapv_pointer = 1; - bool b = range_op_handler (MULT_EXPR, type)->fold_range (r, type, op1, - mult); + bool b = op_mult.fold_range (r, type, op1, mult); flag_wrapv = saved_flag_wrapv; flag_wrapv_pointer = saved_flag_wrapv_pointer; return b; @@ -1409,7 +1461,7 @@ operator_lshift::fold_range (value_range &r, tree type, } void -operator_lshift::wi_fold (value_range &r, tree type, +operator_lshift::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const { @@ -1465,7 +1517,7 @@ operator_lshift::wi_fold (value_range &r, tree type, if (in_bounds) wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub); else - r = value_range (type); + r.set_varying (type); } bool @@ -1485,14 +1537,56 @@ operator_lshift::wi_op_overflows (wide_int &res, tree type, return false; } +bool +operator_lshift::op1_range (irange &r, + tree type, + const irange &lhs, + const irange &op2) const +{ + tree shift_amount; + if (op2.singleton_p (&shift_amount)) + { + int_range<1> shifted (shift_amount, shift_amount), ub, lb; + const range_operator *rshift_op = range_op_handler (RSHIFT_EXPR, type); + rshift_op->fold_range (ub, type, lhs, shifted); + if (TYPE_UNSIGNED (type)) + { + r = ub; + return true; + } + // For signed types, we can't just do an arithmetic rshift, + // because that will propagate the sign bit. + // + // LHS + // 1110 = OP1 << 1 + // + // Assuming a 4-bit signed integer, a right shift will result in + // OP1=1111, but OP1 could have also been 0111. What we want is + // a range from 0111 to 1111. That is, a range from the logical + // rshift (0111) to the arithmetic rshift (1111). + // + // Perform a logical rshift by doing the rshift as unsigned. + tree unsigned_type = unsigned_type_for (type); + widest_irange unsigned_lhs = lhs; + range_cast (unsigned_lhs, unsigned_type); + rshift_op = range_op_handler (RSHIFT_EXPR, unsigned_type); + rshift_op->fold_range (lb, unsigned_type, unsigned_lhs, shifted); + range_cast (lb, type); + r = lb; + r.union_ (ub); + return true; + } + return false; +} + class operator_rshift : public cross_product_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual void wi_fold (value_range &r, tree type, + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -1501,9 +1595,58 @@ public: tree type, const wide_int &w0, const wide_int &w1) const; + virtual bool op1_range (irange &, tree type, + const irange &lhs, + const irange &op2) const; } op_rshift; bool +operator_rshift::op1_range (irange &r, + tree type, + const irange &lhs, + const irange &op2) const +{ + tree shift; + if (op2.singleton_p (&shift)) + { + // Folding the original operation may discard some impossible + // ranges from the LHS. + widest_irange lhs_refined; + op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2); + lhs_refined.intersect (lhs); + if (lhs_refined.undefined_p ()) + { + r.set_undefined (); + return true; + } + widest_irange shift_range (shift, shift); + widest_irange lb, ub; + op_lshift.fold_range (lb, type, lhs_refined, shift_range); + // LHS + // 0000 0111 = OP1 >> 3 + // + // OP1 is anything from 0011 1000 to 0011 1111. That is, a + // range from LHS<<3 plus a mask of the 3 bits we shifted on the + // right hand side (0x07). + tree mask = fold_build1 (BIT_NOT_EXPR, type, + fold_build2 (LSHIFT_EXPR, type, + build_minus_one_cst (type), + shift)); + widest_irange mask_range (build_zero_cst (type), mask); + op_plus.fold_range (ub, type, lb, mask_range); + r = lb; + r.union_ (ub); + if (!lhs_refined.contains_p (build_zero_cst (type))) + { + mask_range.invert (); + r.intersect (mask_range); + } + return true; + } + return false; +} + +bool operator_rshift::wi_op_overflows (wide_int &res, tree type, const wide_int &w0, @@ -1523,9 +1666,9 @@ operator_rshift::wi_op_overflows (wide_int &res, } bool -operator_rshift::fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const +operator_rshift::fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const { // Invoke the generic fold routine if not undefined.. if (undefined_shift_range_check (r, type, op2)) @@ -1535,7 +1678,7 @@ operator_rshift::fold_range (value_range &r, tree type, } void -operator_rshift::wi_fold (value_range &r, tree type, +operator_rshift::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const { @@ -1546,139 +1689,180 @@ operator_rshift::wi_fold (value_range &r, tree type, class operator_cast: public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; +private: + bool truncating_cast_p (const irange &inner, const irange &outer) const; + bool inside_domain_p (const wide_int &min, const wide_int &max, + const irange &outer) const; + void fold_pair (irange &r, unsigned index, const irange &inner, + const irange &outer) const; } op_convert; +// Return TRUE if casting from INNER to OUTER is a truncating cast. + +inline bool +operator_cast::truncating_cast_p (const irange &inner, + const irange &outer) const +{ + return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ()); +} + +// Return TRUE if [MIN,MAX] is inside the domain of RANGE's type. + bool -operator_cast::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, - const value_range &lh, - const value_range &rh) const +operator_cast::inside_domain_p (const wide_int &min, + const wide_int &max, + const irange &range) const { - if (empty_range_check (r, lh, rh)) - return true; - - tree inner = lh.type (); - tree outer = rh.type (); - gcc_checking_assert (rh.varying_p ()); - gcc_checking_assert (types_compatible_p (outer, type)); - signop inner_sign = TYPE_SIGN (inner); - signop outer_sign = TYPE_SIGN (outer); - unsigned inner_prec = TYPE_PRECISION (inner); - unsigned outer_prec = TYPE_PRECISION (outer); - - // Start with an empty range and add subranges. - r = value_range (); - for (unsigned x = 0; x < lh.num_pairs (); ++x) - { - wide_int lh_lb = lh.lower_bound (x); - wide_int lh_ub = lh.upper_bound (x); - - // If the conversion is not truncating we can convert the min - // and max values and canonicalize the resulting range. - // Otherwise, we can do the conversion if the size of the range - // is less than what the precision of the target type can - // represent. - if (outer_prec >= inner_prec - || wi::rshift (wi::sub (lh_ub, lh_lb), - wi::uhwi (outer_prec, inner_prec), - inner_sign) == 0) + wide_int domain_min = wi::to_wide (vrp_val_min (range.type ())); + wide_int domain_max = wi::to_wide (vrp_val_max (range.type ())); + signop domain_sign = TYPE_SIGN (range.type ()); + return (wi::le_p (min, domain_max, domain_sign) + && wi::le_p (max, domain_max, domain_sign) + && wi::ge_p (min, domain_min, domain_sign) + && wi::ge_p (max, domain_min, domain_sign)); +} + + +// Helper for fold_range which work on a pair at a time. + +void +operator_cast::fold_pair (irange &r, unsigned index, + const irange &inner, + const irange &outer) const +{ + tree inner_type = inner.type (); + tree outer_type = outer.type (); + signop inner_sign = TYPE_SIGN (inner_type); + unsigned outer_prec = TYPE_PRECISION (outer_type); + + // check to see if casting from INNER to OUTER is a conversion that + // fits in the resulting OUTER type. + wide_int inner_lb = inner.lower_bound (index); + wide_int inner_ub = inner.upper_bound (index); + if (truncating_cast_p (inner, outer)) + { + // We may be able to accomodate a truncating cast if the + // resulting range can be represented in the target type... + if (wi::rshift (wi::sub (inner_ub, inner_lb), + wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())), + inner_sign) != 0) { - wide_int min = wide_int::from (lh_lb, outer_prec, inner_sign); - wide_int max = wide_int::from (lh_ub, outer_prec, inner_sign); - if (!wi::eq_p (min, wi::min_value (outer_prec, outer_sign)) - || !wi::eq_p (max, wi::max_value (outer_prec, outer_sign))) - { - value_range tmp; - create_possibly_reversed_range (tmp, type, min, max); - r.union_ (tmp); - continue; - } + r.set_varying (outer_type); + return; } - r = value_range (type); - break; + } + // ...but we must still verify that the final range fits in the + // domain. This catches -fstrict-enum restrictions where the domain + // range is smaller than what fits in the underlying type. + wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign); + wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign); + if (inside_domain_p (min, max, outer)) + create_possibly_reversed_range (r, outer_type, min, max); + else + r.set_varying (outer_type); +} + + +bool +operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, + const irange &inner, + const irange &outer) const +{ + if (empty_range_varying (r, type, inner, outer)) + return true; + + gcc_checking_assert (outer.varying_p ()); + gcc_checking_assert (inner.num_pairs () > 0); + + // Avoid a temporary by folding the first pair directly into the result. + fold_pair (r, 0, inner, outer); + + // Then process any additonal pairs by unioning with their results. + for (unsigned x = 1; x < inner.num_pairs (); ++x) + { + widest_irange tmp; + fold_pair (tmp, x, inner, outer); + r.union_ (tmp); + if (r.varying_p ()) + return true; } return true; } bool -operator_cast::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_cast::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { tree lhs_type = lhs.type (); - value_range tmp; gcc_checking_assert (types_compatible_p (op2.type(), type)); - // If the precision of the LHS is smaller than the precision of the - // RHS, then there would be truncation of the value on the RHS, and - // so we can tell nothing about it. - if (TYPE_PRECISION (lhs_type) < TYPE_PRECISION (type)) - { - // If we've been passed an actual value for the RHS rather than - // the type, see if it fits the LHS, and if so, then we can allow - // it. - fold_range (r, lhs_type, op2, value_range (lhs_type)); - fold_range (tmp, type, r, value_range (type)); - if (tmp == op2) + if (truncating_cast_p (op2, lhs)) + { + if (lhs.varying_p ()) + r.set_varying (type); + else { - // We know the value of the RHS fits in the LHS type, so - // convert the LHS and remove any values that arent in OP2. - fold_range (r, type, lhs, value_range (type)); - r.intersect (op2); - return true; - } - // Special case if the LHS is a boolean. A 0 means the RHS is - // zero, and a 1 means the RHS is non-zero. - if (TREE_CODE (lhs_type) == BOOLEAN_TYPE) - { - // If the LHS is unknown, the result is whatever op2 already is. - if (!lhs.singleton_p ()) - { - r = op2; - return true; - } - // Boolean casts are weird in GCC. It's actually an implied - // mask with 0x01, so all that is known is whether the - // rightmost bit is 0 or 1, which implies the only value - // *not* in the RHS is 0 or -1. - unsigned prec = TYPE_PRECISION (type); - if (lhs.zero_p ()) - r = value_range (type, wi::minus_one (prec), wi::minus_one (prec), - VR_ANTI_RANGE); - else - r = value_range (type, wi::zero (prec), wi::zero (prec), - VR_ANTI_RANGE); - // And intersect it with what we know about op2. - r.intersect (op2); + // We want to insert the LHS as an unsigned value since it + // would not trigger the signed bit of the larger type. + widest_irange converted_lhs = lhs; + range_cast (converted_lhs, unsigned_type_for (lhs_type)); + range_cast (converted_lhs, type); + // Start by building the positive signed outer range for the type. + wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type), + TYPE_PRECISION (type)); + r = int_range<1> (type, lim, wi::max_value (TYPE_PRECISION (type), + SIGNED)); + // For the signed part, we need to simply union the 2 ranges now. + r.union_ (converted_lhs); + + // Create maximal negative number outside of LHS bits. + lim = wi::mask (TYPE_PRECISION (lhs_type), true, + TYPE_PRECISION (type)); + // Add this to the unsigned LHS range(s). + widest_irange lim_range (type, lim, lim); + widest_irange lhs_neg; + range_op_handler (PLUS_EXPR, type)->fold_range (lhs_neg, + type, + converted_lhs, + lim_range); + // And union this with the entire outer types negative range. + widest_irange neg (type, + wi::min_value (TYPE_PRECISION (type), + SIGNED), + lim - 1); + neg.union_ (lhs_neg); + // And finally, munge the signed and unsigned portions. + r.union_ (neg); } - else - // Otherwise we'll have to assume it's whatever we know about op2. - r = op2; + // And intersect with any known value passed in the extra operand. + r.intersect (op2); return true; } - // If the LHS precision is greater than the rhs precision, the LHS - // range is restricted to the range of the RHS by this - // assignment. - if (TYPE_PRECISION (lhs_type) > TYPE_PRECISION (type)) + widest_irange tmp; + if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type)) + tmp = lhs; + else { + // The cast is not truncating, and the range is restricted to + // the range of the RHS by this assignment. + // // Cast the range of the RHS to the type of the LHS. - fold_range (tmp, lhs_type, value_range (type), value_range (lhs_type)); - // Intersect this with the LHS range will produce the range, which - // will be cast to the RHS type before returning. + fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type)); + // Intersect this with the LHS range will produce the range, + // which will be cast to the RHS type before returning. tmp.intersect (lhs); } - else - tmp = lhs; // Cast the calculated range to the type of the RHS. - fold_range (r, type, tmp, value_range (type)); + fold_range (r, type, tmp, int_range<1> (type)); return true; } @@ -1686,24 +1870,24 @@ operator_cast::op1_range (value_range &r, tree type, class operator_logical_and : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; + virtual bool fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_logical_and; bool -operator_logical_and::fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const +operator_logical_and::fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const { - if (empty_range_check (r, lh, rh)) + if (empty_range_varying (r, type, lh, rh)) return true; // 0 && anything is 0. @@ -1721,9 +1905,9 @@ operator_logical_and::fold_range (value_range &r, tree type, } bool -operator_logical_and::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2 ATTRIBUTE_UNUSED) const +operator_logical_and::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2 ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -1742,9 +1926,9 @@ operator_logical_and::op1_range (value_range &r, tree type, } bool -operator_logical_and::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_logical_and::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { return operator_logical_and::op1_range (r, type, lhs, op1); } @@ -1753,19 +1937,106 @@ operator_logical_and::op2_range (value_range &r, tree type, class operator_bitwise_and : public range_operator { public: - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; - virtual void wi_fold (value_range &r, tree type, + virtual bool fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; +private: + void simple_op1_range_solver (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + void remove_impossible_ranges (irange &r, const irange &rh) const; } op_bitwise_and; +static bool +unsigned_singleton_p (const irange &op) +{ + tree mask; + if (op.singleton_p (&mask)) + { + wide_int x = wi::to_wide (mask); + return wi::ge_p (x, 0, TYPE_SIGN (op.type ())); + } + return false; +} + +// Remove any ranges from R that are known to be impossible when an +// range is ANDed with MASK. + +void +operator_bitwise_and::remove_impossible_ranges (irange &r, + const irange &rmask) const +{ + if (r.undefined_p () || !unsigned_singleton_p (rmask)) + return; + + wide_int mask = rmask.lower_bound (); + tree type = r.type (); + int prec = TYPE_PRECISION (type); + int leading_zeros = wi::clz (mask); + widest_irange impossible_ranges; + + /* We know that starting at the most significant bit, any 0 in the + mask means the resulting range cannot contain a 1 in that same + position. This means the following ranges are impossible: + + x & 0b1001 1010 + IMPOSSIBLE RANGES + 01xx xxxx [0100 0000, 0111 1111] + 001x xxxx [0010 0000, 0011 1111] + 0000 01xx [0000 0100, 0000 0111] + 0000 0001 [0000 0001, 0000 0001] + */ + wide_int one = wi::one (prec); + for (int i = 0; i < prec - leading_zeros - 1; ++i) + if (wi::bit_and (mask, wi::lshift (one, wi::uhwi (i, prec))) == 0) + { + tree lb = fold_build2 (LSHIFT_EXPR, type, + build_one_cst (type), + build_int_cst (type, i)); + tree ub_left = fold_build1 (BIT_NOT_EXPR, type, + fold_build2 (LSHIFT_EXPR, type, + build_minus_one_cst (type), + build_int_cst (type, i))); + tree ub_right = fold_build2 (LSHIFT_EXPR, type, + build_one_cst (type), + build_int_cst (type, i)); + tree ub = fold_build2 (BIT_IOR_EXPR, type, ub_left, ub_right); + impossible_ranges.union_ (int_range<1> (lb, ub)); + } + if (!impossible_ranges.undefined_p ()) + { + impossible_ranges.invert (); + r.intersect (impossible_ranges); + } +} + +bool +operator_bitwise_and::fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const +{ + if (range_operator::fold_range (r, type, lh, rh)) + { + // FIXME: This is temporarily disabled because, though it + // generates better ranges, it's noticeably slower for evrp. + // remove_impossible_ranges (r, rh); + return true; + } + return false; +} + + // Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if // possible. Basically, see if we can optimize: // @@ -1777,7 +2048,7 @@ public: // return TRUE. static bool -wi_optimize_and_or (value_range &r, +wi_optimize_and_or (irange &r, enum tree_code code, tree type, const wide_int &lh_lb, const wide_int &lh_ub, @@ -1886,7 +2157,7 @@ wi_set_zero_nonzero_bits (tree type, } void -operator_bitwise_and::wi_fold (value_range &r, tree type, +operator_bitwise_and::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -1938,29 +2209,128 @@ operator_bitwise_and::wi_fold (value_range &r, tree type, } // If the limits got swapped around, return varying. if (wi::gt_p (new_lb, new_ub,sign)) - r = value_range (type); + r.set_varying (type); else value_range_with_overflow (r, type, new_lb, new_ub); } +static void +set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs) +{ + if (!lhs.contains_p (build_zero_cst (type))) + r = range_nonzero (type); + else + r.set_varying (type); +} + +// This was shamelessly stolen from register_edge_assert_for_2 and +// adjusted to work with iranges. + +void +operator_bitwise_and::simple_op1_range_solver (irange &r, tree type, + const irange &lhs, + const irange &op2) const +{ + if (!op2.singleton_p ()) + { + set_nonzero_range_from_mask (r, type, lhs); + return; + } + unsigned int nprec = TYPE_PRECISION (type); + wide_int cst2v = op2.lower_bound (); + bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type)); + wide_int sgnbit; + if (cst2n) + sgnbit = wi::set_bit_in_zero (nprec - 1, nprec); + else + sgnbit = wi::zero (nprec); + + // Solve [lhs.lower_bound (), +INF] = x & MASK. + // + // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and + // maximum unsigned value is ~0. For signed comparison, if CST2 + // doesn't have the most significant bit set, handle it similarly. If + // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2. + wide_int valv = lhs.lower_bound (); + wide_int minv = valv & cst2v, maxv; + bool we_know_nothing = false; + if (minv != valv) + { + // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL. + minv = masked_increment (valv, cst2v, sgnbit, nprec); + if (minv == valv) + { + // If we can't determine anything on this bound, fall + // through and conservatively solve for the other end point. + we_know_nothing = true; + } + } + maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec); + if (we_know_nothing) + r.set_varying (type); + else + r = int_range<1> (type, minv, maxv); + + // Solve [-INF, lhs.upper_bound ()] = x & MASK. + // + // Minimum unsigned value for <= is 0 and maximum unsigned value is + // VAL | ~CST2 if (VAL & CST2) == VAL. Otherwise, find smallest + // VAL2 where + // VAL2 > VAL && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2 + // as maximum. + // For signed comparison, if CST2 doesn't have most significant bit + // set, handle it similarly. If CST2 has MSB set, the maximum is + // the same and minimum is INT_MIN. + valv = lhs.upper_bound (); + minv = valv & cst2v; + if (minv == valv) + maxv = valv; + else + { + maxv = masked_increment (valv, cst2v, sgnbit, nprec); + if (maxv == valv) + { + // If we couldn't determine anything on either bound, return + // undefined. + if (we_know_nothing) + r.set_undefined (); + return; + } + maxv -= 1; + } + maxv |= ~cst2v; + minv = sgnbit; + int_range<1> upper_bits (type, minv, maxv); + r.intersect (upper_bits); +} + bool -operator_bitwise_and::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_bitwise_and::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { - // If this is really a logical wi_fold, call that. if (types_compatible_p (type, boolean_type_node)) return op_logical_and.op1_range (r, type, lhs, op2); - // For now do nothing with bitwise AND of value_range's. - r.set_varying (type); + r.set_undefined (); + for (unsigned i = 0; i < lhs.num_pairs (); ++i) + { + widest_irange chunk (lhs.type (), + lhs.lower_bound (i), + lhs.upper_bound (i)); + widest_irange res; + simple_op1_range_solver (res, type, chunk, op2); + r.union_ (res); + } + if (r.undefined_p ()) + set_nonzero_range_from_mask (r, type, lhs); return true; } bool -operator_bitwise_and::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_bitwise_and::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { return operator_bitwise_and::op1_range (r, type, lhs, op1); } @@ -1969,23 +2339,23 @@ operator_bitwise_and::op2_range (value_range &r, tree type, class operator_logical_or : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; + virtual bool fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_logical_or; bool -operator_logical_or::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, - const value_range &lh, - const value_range &rh) const +operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, + const irange &lh, + const irange &rh) const { - if (empty_range_check (r, lh, rh)) + if (empty_range_varying (r, type, lh, rh)) return true; r = lh; @@ -1994,9 +2364,9 @@ operator_logical_or::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, } bool -operator_logical_or::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2 ATTRIBUTE_UNUSED) const +operator_logical_or::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2 ATTRIBUTE_UNUSED) const { switch (get_bool_state (r, lhs, type)) { @@ -2015,9 +2385,9 @@ operator_logical_or::op1_range (value_range &r, tree type, } bool -operator_logical_or::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_logical_or::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { return operator_logical_or::op1_range (r, type, lhs, op1); } @@ -2026,13 +2396,13 @@ operator_logical_or::op2_range (value_range &r, tree type, class operator_bitwise_or : public range_operator { public: - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; - virtual void wi_fold (value_range &r, tree type, + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -2040,7 +2410,7 @@ public: } op_bitwise_or; void -operator_bitwise_or::wi_fold (value_range &r, tree type, +operator_bitwise_or::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -2076,29 +2446,34 @@ operator_bitwise_or::wi_fold (value_range &r, tree type, new_lb = wi::max (new_lb, rh_lb, sign); // If the limits got swapped around, return varying. if (wi::gt_p (new_lb, new_ub,sign)) - r = value_range (type); + r.set_varying (type); else value_range_with_overflow (r, type, new_lb, new_ub); } bool -operator_bitwise_or::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_bitwise_or::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { // If this is really a logical wi_fold, call that. if (types_compatible_p (type, boolean_type_node)) return op_logical_or.op1_range (r, type, lhs, op2); - // For now do nothing with bitwise OR of value_range's. + if (lhs.zero_p ()) + { + tree zero = build_zero_cst (type); + r = int_range<1> (zero, zero); + return true; + } r.set_varying (type); return true; } bool -operator_bitwise_or::op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const +operator_bitwise_or::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const { return operator_bitwise_or::op1_range (r, type, lhs, op1); } @@ -2107,15 +2482,21 @@ operator_bitwise_or::op2_range (value_range &r, tree type, class operator_bitwise_xor : public range_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; } op_bitwise_xor; void -operator_bitwise_xor::wi_fold (value_range &r, tree type, +operator_bitwise_xor::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -2142,14 +2523,55 @@ operator_bitwise_xor::wi_fold (value_range &r, tree type, if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign)) value_range_with_overflow (r, type, new_lb, new_ub); else - r = value_range (type); + r.set_varying (type); +} + +bool +operator_bitwise_xor::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const +{ + if (lhs.undefined_p () || lhs.varying_p ()) + { + r = lhs; + return true; + } + if (types_compatible_p (type, boolean_type_node)) + { + switch (get_bool_state (r, lhs, type)) + { + case BRS_TRUE: + if (op2.varying_p ()) + r.set_varying (type); + else if (op2.zero_p ()) + r = range_true (type); + else + r = range_false (type); + break; + case BRS_FALSE: + r = op2; + break; + default: + gcc_unreachable (); + } + return true; + } + r.set_varying (type); + return true; } +bool +operator_bitwise_xor::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const +{ + return operator_bitwise_xor::op1_range (r, type, lhs, op1); +} class operator_trunc_mod : public range_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -2157,7 +2579,7 @@ public: } op_trunc_mod; void -operator_trunc_mod::wi_fold (value_range &r, tree type, +operator_trunc_mod::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -2170,7 +2592,7 @@ operator_trunc_mod::wi_fold (value_range &r, tree type, // Mod 0 is undefined. Return undefined. if (wi_zero_p (type, rh_lb, rh_ub)) { - r = value_range (); + r.set_undefined (); return; } @@ -2204,12 +2626,12 @@ operator_trunc_mod::wi_fold (value_range &r, tree type, class operator_logical_not : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; + virtual bool fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; } op_logical_not; // Folding a logical NOT, oddly enough, involves doing nothing on the @@ -2227,11 +2649,11 @@ public: // which is the result we are looking for.. so.. pass it through. bool -operator_logical_not::fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh ATTRIBUTE_UNUSED) const +operator_logical_not::fold_range (irange &r, tree type, + const irange &lh, + const irange &rh ATTRIBUTE_UNUSED) const { - if (empty_range_check (r, lh, rh)) + if (empty_range_varying (r, type, lh, rh)) return true; if (lh.varying_p () || lh.undefined_p ()) @@ -2246,10 +2668,10 @@ operator_logical_not::fold_range (value_range &r, tree type, } bool -operator_logical_not::op1_range (value_range &r, +operator_logical_not::op1_range (irange &r, tree type ATTRIBUTE_UNUSED, - const value_range &lhs, - const value_range &op2 ATTRIBUTE_UNUSED) const + const irange &lhs, + const irange &op2 ATTRIBUTE_UNUSED) const { r = lhs; if (!lhs.varying_p () && !lhs.undefined_p ()) @@ -2261,33 +2683,33 @@ operator_logical_not::op1_range (value_range &r, class operator_bitwise_not : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; + virtual bool fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; } op_bitwise_not; bool -operator_bitwise_not::fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const +operator_bitwise_not::fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const { - if (empty_range_check (r, lh, rh)) + if (empty_range_varying (r, type, lh, rh)) return true; // ~X is simply -1 - X. - value_range minusone (type, wi::minus_one (TYPE_PRECISION (type)), - wi::minus_one (TYPE_PRECISION (type))); + int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)), + wi::minus_one (TYPE_PRECISION (type))); return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, minusone, lh); } bool -operator_bitwise_not::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_bitwise_not::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { // ~X is -1 - X and since bitwise NOT is involutary...do it again. return fold_range (r, type, lhs, op2); @@ -2297,15 +2719,15 @@ operator_bitwise_not::op1_range (value_range &r, tree type, class operator_cst : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; } op_integer_cst; bool -operator_cst::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, - const value_range &lh, - const value_range &rh ATTRIBUTE_UNUSED) const +operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, + const irange &lh, + const irange &rh ATTRIBUTE_UNUSED) const { r = lh; return true; @@ -2315,48 +2737,66 @@ operator_cst::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, class operator_identity : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; } op_identity; bool -operator_identity::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED, - const value_range &lh, - const value_range &rh ATTRIBUTE_UNUSED) const +operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED, + const irange &lh, + const irange &rh ATTRIBUTE_UNUSED) const { r = lh; return true; } bool -operator_identity::op1_range (value_range &r, tree type ATTRIBUTE_UNUSED, - const value_range &lhs, - const value_range &op2 ATTRIBUTE_UNUSED) const +operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED, + const irange &lhs, + const irange &op2 ATTRIBUTE_UNUSED) const { r = lhs; return true; } +class operator_unknown : public range_operator +{ +public: + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; +} op_unknown; + +bool +operator_unknown::fold_range (irange &r, tree type, + const irange &lh ATTRIBUTE_UNUSED, + const irange &rh ATTRIBUTE_UNUSED) const +{ + r.set_varying (type); + return true; +} + + class operator_abs : public range_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; } op_abs; void -operator_abs::wi_fold (value_range &r, tree type, +operator_abs::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb ATTRIBUTE_UNUSED, const wide_int &rh_ub ATTRIBUTE_UNUSED) const @@ -2368,7 +2808,7 @@ operator_abs::wi_fold (value_range &r, tree type, // Pass through LH for the easy cases. if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign)) { - r = value_range (type, lh_lb, lh_ub); + r = int_range<1> (type, lh_lb, lh_ub); return; } @@ -2378,7 +2818,7 @@ operator_abs::wi_fold (value_range &r, tree type, wide_int max_value = wi::max_value (prec, sign); if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value)) { - r = value_range (type); + r.set_varying (type); return; } @@ -2416,15 +2856,15 @@ operator_abs::wi_fold (value_range &r, tree type, min = wi::zero (prec); max = max_value; } - r = value_range (type, min, max); + r = int_range<1> (type, min, max); } bool -operator_abs::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_abs::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { - if (empty_range_check (r, lhs, op2)) + if (empty_range_varying (r, type, lhs, op2)) return true; if (TYPE_UNSIGNED (type)) { @@ -2432,15 +2872,15 @@ operator_abs::op1_range (value_range &r, tree type, return true; } // Start with the positives because negatives are an impossible result. - value_range positives = range_positives (type); + widest_irange positives = range_positives (type); positives.intersect (lhs); r = positives; // Then add the negative of each pair: // ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20]. for (unsigned i = 0; i < positives.num_pairs (); ++i) - r.union_ (value_range (type, - -positives.upper_bound (i), - -positives.lower_bound (i))); + r.union_ (int_range<1> (type, + -positives.upper_bound (i), + -positives.lower_bound (i))); return true; } @@ -2448,13 +2888,13 @@ operator_abs::op1_range (value_range &r, tree type, class operator_absu : public range_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; } op_absu; void -operator_absu::wi_fold (value_range &r, tree type, +operator_absu::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb ATTRIBUTE_UNUSED, const wide_int &rh_ub ATTRIBUTE_UNUSED) const @@ -2485,27 +2925,27 @@ operator_absu::wi_fold (value_range &r, tree type, } gcc_checking_assert (TYPE_UNSIGNED (type)); - r = value_range (type, new_lb, new_ub); + r = int_range<1> (type, new_lb, new_ub); } class operator_negate : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; } op_negate; bool -operator_negate::fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const +operator_negate::fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const { - if (empty_range_check (r, lh, rh)) + if (empty_range_varying (r, type, lh, rh)) return true; // -X is simply 0 - X. return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, @@ -2514,9 +2954,9 @@ operator_negate::fold_range (value_range &r, tree type, } bool -operator_negate::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_negate::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { // NEGATE is involutory. return fold_range (r, type, lhs, op2); @@ -2526,20 +2966,20 @@ operator_negate::op1_range (value_range &r, tree type, class operator_addr_expr : public range_operator { public: - virtual bool fold_range (value_range &r, tree type, - const value_range &op1, - const value_range &op2) const; - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; + virtual bool fold_range (irange &r, tree type, + const irange &op1, + const irange &op2) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; } op_addr; bool -operator_addr_expr::fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const +operator_addr_expr::fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const { - if (empty_range_check (r, lh, rh)) + if (empty_range_varying (r, type, lh, rh)) return true; // Return a non-null pointer of the LHS type (passed in op2). @@ -2548,14 +2988,14 @@ operator_addr_expr::fold_range (value_range &r, tree type, else if (!lh.contains_p (build_zero_cst (lh.type ()))) r = range_nonzero (type); else - r = value_range (type); + r.set_varying (type); return true; } bool -operator_addr_expr::op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const +operator_addr_expr::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const { return operator_addr_expr::fold_range (r, type, lhs, op2); } @@ -2564,7 +3004,7 @@ operator_addr_expr::op1_range (value_range &r, tree type, class pointer_plus_operator : public range_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -2572,7 +3012,7 @@ public: } op_pointer_plus; void -pointer_plus_operator::wi_fold (value_range &r, tree type, +pointer_plus_operator::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -2604,20 +3044,20 @@ pointer_plus_operator::wi_fold (value_range &r, tree type, && rh_lb == rh_ub && rh_lb == 0) r = range_zero (type); else - r = value_range (type); + r.set_varying (type); } class pointer_min_max_operator : public range_operator { public: - virtual void wi_fold (value_range & r, tree type, + virtual void wi_fold (irange & r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; } op_ptr_min_max; void -pointer_min_max_operator::wi_fold (value_range &r, tree type, +pointer_min_max_operator::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -2633,20 +3073,20 @@ pointer_min_max_operator::wi_fold (value_range &r, tree type, else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub)) r = range_zero (type); else - r = value_range (type); + r.set_varying (type); } class pointer_and_operator : public range_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; } op_pointer_and; void -pointer_and_operator::wi_fold (value_range &r, tree type, +pointer_and_operator::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb ATTRIBUTE_UNUSED, @@ -2657,20 +3097,49 @@ pointer_and_operator::wi_fold (value_range &r, tree type, if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub)) r = range_zero (type); else - r = value_range (type); + r.set_varying (type); } class pointer_or_operator : public range_operator { public: - virtual void wi_fold (value_range &r, tree type, + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, const wide_int &rh_ub) const; } op_pointer_or; +bool +pointer_or_operator::op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2 ATTRIBUTE_UNUSED) const +{ + if (lhs.zero_p ()) + { + tree zero = build_zero_cst (type); + r = int_range<1> (zero, zero); + return true; + } + r.set_varying (type); + return true; +} + +bool +pointer_or_operator::op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const +{ + return pointer_or_operator::op1_range (r, type, lhs, op1); +} + void -pointer_or_operator::wi_fold (value_range &r, tree type, +pointer_or_operator::wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -2684,7 +3153,7 @@ pointer_or_operator::wi_fold (value_range &r, tree type, else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub)) r = range_zero (type); else - r = value_range (type); + r.set_varying (type); } // This implements the range operator tables as local objects in this file. @@ -2760,6 +3229,8 @@ integral_table::integral_table () set (SSA_NAME, op_identity); set (PAREN_EXPR, op_identity); set (OBJ_TYPE_REF, op_identity); + set (IMAGPART_EXPR, op_unknown); + set (POINTER_DIFF_EXPR, op_unknown); set (ABS_EXPR, op_abs); set (ABSU_EXPR, op_absu); set (NEGATE_EXPR, op_negate); @@ -2811,13 +3282,13 @@ range_op_handler (enum tree_code code, tree type) // Cast the range in R to TYPE. void -range_cast (value_range &r, tree type) +range_cast (irange &r, tree type) { - value_range tmp = r; + widest_irange tmp = r; range_operator *op = range_op_handler (CONVERT_EXPR, type); // Call op_convert, if it fails, the result is varying. - if (!op->fold_range (r, type, tmp, value_range (type))) - r = value_range (type); + if (!op->fold_range (r, type, tmp, int_range<1> (type))) + r.set_varying (type); } #if CHECKING_P @@ -2836,37 +3307,280 @@ namespace selftest #define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N)) #define SCHAR(N) build_int_cst (signed_char_type_node, (N)) +static int_range<3> +build_range3 (int a, int b, int c, int d, int e, int f) +{ + int_range<3> i1 (INT (a), INT (b)); + int_range<3> i2 (INT (c), INT (d)); + int_range<3> i3 (INT (e), INT (f)); + i1.union_ (i2); + i1.union_ (i3); + return i1; +} + +static void +range3_tests () +{ + typedef int_range<3> irange3; + irange3 r0, r1, r2; + irange3 i1, i2, i3; + + // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20]. + r0 = irange3 (INT (10), INT (20)); + r1 = irange3 (INT (5), INT (8)); + r0.union_ (r1); + r1 = irange3 (INT (1), INT (3)); + r0.union_ (r1); + ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20)); + + // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20]. + r1 = irange3 (INT (-5), INT (0)); + r0.union_ (r1); + ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20)); + + // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60]. + r1 = irange3 (INT (50), INT (60)); + r0 = irange3 (INT (10), INT (20)); + r0.union_ (irange3 (INT (30), INT (40))); + r0.union_ (r1); + ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60)); + // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80]. + r1 = irange3 (INT (70), INT (80)); + r0.union_ (r1); + + r2 = build_range3 (10, 20, 30, 40, 50, 60); + r2.union_ (irange3 (INT (70), INT (80))); + ASSERT_TRUE (r0 == r2); + + // [10,20][30,40][50,60] U [6,35] => [6,40][50,60]. + r0 = build_range3 (10, 20, 30, 40, 50, 60); + r1 = irange3 (INT (6), INT (35)); + r0.union_ (r1); + r1 = irange3 (INT (6), INT (40)); + r1.union_ (irange3 (INT (50), INT (60))); + ASSERT_TRUE (r0 == r1); + + // [10,20][30,40][50,60] U [6,60] => [6,60]. + r0 = build_range3 (10, 20, 30, 40, 50, 60); + r1 = irange3 (INT (6), INT (60)); + r0.union_ (r1); + ASSERT_TRUE (r0 == irange3 (INT (6), INT (60))); + + // [10,20][30,40][50,60] U [6,70] => [6,70]. + r0 = build_range3 (10, 20, 30, 40, 50, 60); + r1 = irange3 (INT (6), INT (70)); + r0.union_ (r1); + ASSERT_TRUE (r0 == irange3 (INT (6), INT (70))); + + // [10,20][30,40][50,60] U [35,70] => [10,20][30,70]. + r0 = build_range3 (10, 20, 30, 40, 50, 60); + r1 = irange3 (INT (35), INT (70)); + r0.union_ (r1); + r1 = irange3 (INT (10), INT (20)); + r1.union_ (irange3 (INT (30), INT (70))); + ASSERT_TRUE (r0 == r1); + + // [10,20][30,40][50,60] U [15,35] => [10,40][50,60]. + r0 = build_range3 (10, 20, 30, 40, 50, 60); + r1 = irange3 (INT (15), INT (35)); + r0.union_ (r1); + r1 = irange3 (INT (10), INT (40)); + r1.union_ (irange3 (INT (50), INT (60))); + ASSERT_TRUE (r0 == r1); + + // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60]. + r0 = build_range3 (10, 20, 30, 40, 50, 60); + r1 = irange3 (INT (35), INT (35)); + r0.union_ (r1); + ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60)); +} + +static void +widest_irange_tests () +{ + widest_irange big; + unsigned int nrange; + + // Build a huge multi-range range. + for (nrange = 0; nrange < 50; ++nrange) + { + int_range<1> tmp (INT (nrange*10), INT (nrange*10 + 5)); + big.union_ (tmp); + } + ASSERT_TRUE (big.num_pairs () == nrange); + + // Verify that we can copy it without loosing precision. + widest_irange copy (big); + ASSERT_TRUE (copy.num_pairs () == nrange); + + // Inverting it should produce one more sub-range. + big.invert (); + ASSERT_TRUE (big.num_pairs () == nrange + 1); + + int_range<1> tmp (INT (5), INT (37)); + big.intersect (tmp); + ASSERT_TRUE (big.num_pairs () == 4); + + // Test that [10,10][20,20] does NOT contain 15. + { + widest_irange i1 (build_int_cst (integer_type_node, 10), + build_int_cst (integer_type_node, 10)); + widest_irange i2 (build_int_cst (integer_type_node, 20), + build_int_cst (integer_type_node, 20)); + i1.union_ (i2); + ASSERT_FALSE (i1.contains_p (build_int_cst (integer_type_node, 15))); + } + +} + +static void +multi_precision_range_tests () +{ + // Test truncating copy to int_range<1>. + int_range<3> big = build_range3 (10, 20, 30, 40, 50, 60); + int_range<1> small = big; + ASSERT_TRUE (small == int_range<1> (INT (10), INT (60))); + + // Test truncating copy to int_range<2>. + int_range<2> medium = big; + ASSERT_TRUE (!medium.undefined_p ()); + + // Test that a truncating copy of [MIN,20][22,40][80,MAX] + // ends up as a conservative anti-range of ~[21,21]. + big = int_range<3> (vrp_val_min (integer_type_node), INT (20)); + big.union_ (int_range<1> (INT (22), INT (40))); + big.union_ (int_range<1> (INT (80), vrp_val_max (integer_type_node))); + small = big; + ASSERT_TRUE (small == int_range<1> (INT (21), INT (21), VR_ANTI_RANGE)); + + range3_tests (); +} + +static void +operator_tests () +{ + tree min = vrp_val_min (integer_type_node); + tree max = vrp_val_max (integer_type_node); + tree tiny = fold_build2 (PLUS_EXPR, integer_type_node, min, + build_one_cst (integer_type_node)); + widest_irange res; + widest_irange i1 (tiny, max); + widest_irange i2 (build_int_cst (integer_type_node, 255), + build_int_cst (integer_type_node, 255)); + + // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING + op_bitwise_and.op1_range (res, integer_type_node, i1, i2); + ASSERT_TRUE (res == int_range<1> (integer_type_node)); + + // VARYING = OP1 & 255: OP1 is VARYING + i1 = int_range<1> (integer_type_node); + op_bitwise_and.op1_range (res, integer_type_node, i1, i2); + ASSERT_TRUE (res == int_range<1> (integer_type_node)); + + // Test that 0x808.... & 0x8.... still contains 0x8.... + // for a large set of numbers. + { + tree big_type = long_long_unsigned_type_node; + // big_num = 0x808,0000,0000,0000 + tree big_num = fold_build2 (LSHIFT_EXPR, big_type, + build_int_cst (big_type, 0x808), + build_int_cst (big_type, 48)); + op_bitwise_and.fold_range (res, big_type, + int_range <1> (big_type), + int_range <1> (big_num, big_num)); + // val = 0x8,0000,0000,0000 + tree val = fold_build2 (LSHIFT_EXPR, big_type, + build_int_cst (big_type, 0x8), + build_int_cst (big_type, 48)); + ASSERT_TRUE (res.contains_p (val)); + } + + // unsigned: [3, MAX] = OP1 >> 1 + { + widest_irange lhs (build_int_cst (unsigned_type_node, 3), + TYPE_MAX_VALUE (unsigned_type_node)); + widest_irange one (build_one_cst (unsigned_type_node), + build_one_cst (unsigned_type_node)); + widest_irange op1; + op_rshift.op1_range (op1, unsigned_type_node, lhs, one); + ASSERT_FALSE (op1.contains_p (UINT (3))); + } + + // signed: [3, MAX] = OP1 >> 1 + { + widest_irange lhs (INT (3), TYPE_MAX_VALUE (integer_type_node)); + widest_irange one (INT (1), INT (1)); + widest_irange op1; + op_rshift.op1_range (op1, integer_type_node, lhs, one); + ASSERT_FALSE (op1.contains_p (INT (-2))); + } + + // This is impossible, so OP1 should be []. + // signed: [MIN, MIN] = OP1 >> 1 + { + widest_irange lhs (TYPE_MIN_VALUE (integer_type_node), + TYPE_MIN_VALUE (integer_type_node)); + widest_irange one (INT (1), INT (1)); + widest_irange op1; + op_rshift.op1_range (op1, integer_type_node, lhs, one); + ASSERT_TRUE (op1.undefined_p ()); + } + + // signed: ~[-1] = OP1 >> 31 + { + widest_irange lhs (INT (-1), INT (-1), VR_ANTI_RANGE); + widest_irange shift (INT (31), INT (31)); + widest_irange op1; + op_rshift.op1_range (op1, integer_type_node, lhs, shift); + widest_irange negatives = range_negatives (integer_type_node); + negatives.intersect (op1); + ASSERT_TRUE (negatives.undefined_p ()); + } +} + // Run all of the selftests within this file. void range_tests () { tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1); - value_range i1, i2, i3; - value_range r0, r1, rold; + int_range<1> i1, i2, i3; + int_range<1> r0, r1, rold; + + // Test 1-bit signed integer union. + // [-1,-1] U [0,0] = VARYING. + tree one_bit_type = build_nonstandard_integer_type (1, 0); + { + tree one_bit_min = vrp_val_min (one_bit_type); + tree one_bit_max = vrp_val_max (one_bit_type); + int_range<2> min (one_bit_min, one_bit_min); + int_range<2> max (one_bit_max, one_bit_max); + max.union_ (min); + ASSERT_TRUE (max.varying_p ()); + } // Test that NOT(255) is [0..254] in 8-bit land. - value_range not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE); - ASSERT_TRUE (not_255 == value_range (UCHAR (0), UCHAR (254))); + int_range<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE); + ASSERT_TRUE (not_255 == int_range<1> (UCHAR (0), UCHAR (254))); // Test that NOT(0) is [1..255] in 8-bit land. - value_range not_zero = range_nonzero (unsigned_char_type_node); - ASSERT_TRUE (not_zero == value_range (UCHAR (1), UCHAR (255))); + int_range<1> not_zero = range_nonzero (unsigned_char_type_node); + ASSERT_TRUE (not_zero == int_range<1> (UCHAR (1), UCHAR (255))); // Check that [0,127][0x..ffffff80,0x..ffffff] // => ~[128, 0x..ffffff7f]. - r0 = value_range (UINT128 (0), UINT128 (127)); + r0 = int_range<1> (UINT128 (0), UINT128 (127)); tree high = build_minus_one_cst (u128_type); // low = -1 - 127 => 0x..ffffff80. tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127)); - r1 = value_range (low, high); // [0x..ffffff80, 0x..ffffffff] + r1 = int_range<1> (low, high); // [0x..ffffff80, 0x..ffffffff] // r0 = [0,127][0x..ffffff80,0x..fffffff]. r0.union_ (r1); // r1 = [128, 0x..ffffff7f]. - r1 = value_range (UINT128(128), - fold_build2 (MINUS_EXPR, u128_type, - build_minus_one_cst (u128_type), - UINT128(128))); + r1 = int_range<1> (UINT128(128), + fold_build2 (MINUS_EXPR, u128_type, + build_minus_one_cst (u128_type), + UINT128(128))); r0.invert (); ASSERT_TRUE (r0 == r1); @@ -2882,38 +3596,38 @@ range_tests () tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ()); // Check that ~[0,5] => [6,MAX] for unsigned int. - r0 = value_range (UINT (0), UINT (5)); + r0 = int_range<1> (UINT (0), UINT (5)); r0.invert (); - ASSERT_TRUE (r0 == value_range (UINT(6), maxuint)); + ASSERT_TRUE (r0 == int_range<1> (UINT(6), maxuint)); // Check that ~[10,MAX] => [0,9] for unsigned int. - r0 = value_range (UINT(10), maxuint); + r0 = int_range<1> (UINT(10), maxuint); r0.invert (); - ASSERT_TRUE (r0 == value_range (UINT (0), UINT (9))); + ASSERT_TRUE (r0 == int_range<1> (UINT (0), UINT (9))); // Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers. - r0 = value_range (UINT128 (0), UINT128 (5), VR_ANTI_RANGE); - r1 = value_range (UINT128(6), build_minus_one_cst (u128_type)); + r0 = int_range<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE); + r1 = int_range<1> (UINT128(6), build_minus_one_cst (u128_type)); ASSERT_TRUE (r0 == r1); // Check that [~5] is really [-MIN,4][6,MAX]. - r0 = value_range (INT (5), INT (5), VR_ANTI_RANGE); - r1 = value_range (minint, INT (4)); - r1.union_ (value_range (INT (6), maxint)); + r0 = int_range<1> (INT (5), INT (5), VR_ANTI_RANGE); + r1 = int_range<1> (minint, INT (4)); + r1.union_ (int_range<1> (INT (6), maxint)); ASSERT_FALSE (r1.undefined_p ()); ASSERT_TRUE (r0 == r1); - r1 = value_range (INT (5), INT (5)); - value_range r2 (r1); + r1 = int_range<1> (INT (5), INT (5)); + int_range<1> r2 (r1); ASSERT_TRUE (r1 == r2); - r1 = value_range (INT (5), INT (10)); + r1 = int_range<1> (INT (5), INT (10)); - r1 = value_range (integer_type_node, - wi::to_wide (INT (5)), wi::to_wide (INT (10))); + r1 = int_range<1> (integer_type_node, + wi::to_wide (INT (5)), wi::to_wide (INT (10))); ASSERT_TRUE (r1.contains_p (INT (7))); - r1 = value_range (SCHAR (0), SCHAR (20)); + r1 = int_range<1> (SCHAR (0), SCHAR (20)); ASSERT_TRUE (r1.contains_p (SCHAR(15))); ASSERT_FALSE (r1.contains_p (SCHAR(300))); @@ -2922,96 +3636,96 @@ range_tests () if (TYPE_PRECISION (TREE_TYPE (maxint)) > TYPE_PRECISION (short_integer_type_node)) { - r1 = value_range (integer_zero_node, maxint); + r1 = int_range<1> (integer_zero_node, maxint); range_cast (r1, short_integer_type_node); ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort) && r1.upper_bound() == wi::to_wide (maxshort)); } // (unsigned char)[-5,-1] => [251,255]. - r0 = rold = value_range (SCHAR (-5), SCHAR (-1)); + r0 = rold = int_range<1> (SCHAR (-5), SCHAR (-1)); range_cast (r0, unsigned_char_type_node); - ASSERT_TRUE (r0 == value_range (UCHAR (251), UCHAR (255))); + ASSERT_TRUE (r0 == int_range<1> (UCHAR (251), UCHAR (255))); range_cast (r0, signed_char_type_node); ASSERT_TRUE (r0 == rold); // (signed char)[15, 150] => [-128,-106][15,127]. - r0 = rold = value_range (UCHAR (15), UCHAR (150)); + r0 = rold = int_range<1> (UCHAR (15), UCHAR (150)); range_cast (r0, signed_char_type_node); - r1 = value_range (SCHAR (15), SCHAR (127)); - r2 = value_range (SCHAR (-128), SCHAR (-106)); + r1 = int_range<1> (SCHAR (15), SCHAR (127)); + r2 = int_range<1> (SCHAR (-128), SCHAR (-106)); r1.union_ (r2); ASSERT_TRUE (r1 == r0); range_cast (r0, unsigned_char_type_node); ASSERT_TRUE (r0 == rold); // (unsigned char)[-5, 5] => [0,5][251,255]. - r0 = rold = value_range (SCHAR (-5), SCHAR (5)); + r0 = rold = int_range<1> (SCHAR (-5), SCHAR (5)); range_cast (r0, unsigned_char_type_node); - r1 = value_range (UCHAR (251), UCHAR (255)); - r2 = value_range (UCHAR (0), UCHAR (5)); + r1 = int_range<1> (UCHAR (251), UCHAR (255)); + r2 = int_range<1> (UCHAR (0), UCHAR (5)); r1.union_ (r2); ASSERT_TRUE (r0 == r1); range_cast (r0, signed_char_type_node); ASSERT_TRUE (r0 == rold); // (unsigned char)[-5,5] => [0,5][251,255]. - r0 = value_range (INT (-5), INT (5)); + r0 = int_range<1> (INT (-5), INT (5)); range_cast (r0, unsigned_char_type_node); - r1 = value_range (UCHAR (0), UCHAR (5)); - r1.union_ (value_range (UCHAR (251), UCHAR (255))); + r1 = int_range<1> (UCHAR (0), UCHAR (5)); + r1.union_ (int_range<1> (UCHAR (251), UCHAR (255))); ASSERT_TRUE (r0 == r1); // (unsigned char)[5U,1974U] => [0,255]. - r0 = value_range (UINT (5), UINT (1974)); + r0 = int_range<1> (UINT (5), UINT (1974)); range_cast (r0, unsigned_char_type_node); - ASSERT_TRUE (r0 == value_range (UCHAR (0), UCHAR (255))); + ASSERT_TRUE (r0 == int_range<1> (UCHAR (0), UCHAR (255))); range_cast (r0, integer_type_node); // Going to a wider range should not sign extend. - ASSERT_TRUE (r0 == value_range (INT (0), INT (255))); + ASSERT_TRUE (r0 == int_range<1> (INT (0), INT (255))); // (unsigned char)[-350,15] => [0,255]. - r0 = value_range (INT (-350), INT (15)); + r0 = int_range<1> (INT (-350), INT (15)); range_cast (r0, unsigned_char_type_node); - ASSERT_TRUE (r0 == (value_range + ASSERT_TRUE (r0 == (int_range<1> (TYPE_MIN_VALUE (unsigned_char_type_node), TYPE_MAX_VALUE (unsigned_char_type_node)))); // Casting [-120,20] from signed char to unsigned short. // => [0, 20][0xff88, 0xffff]. - r0 = value_range (SCHAR (-120), SCHAR (20)); + r0 = int_range<1> (SCHAR (-120), SCHAR (20)); range_cast (r0, short_unsigned_type_node); - r1 = value_range (UINT16 (0), UINT16 (20)); - r2 = value_range (UINT16 (0xff88), UINT16 (0xffff)); + r1 = int_range<1> (UINT16 (0), UINT16 (20)); + r2 = int_range<1> (UINT16 (0xff88), UINT16 (0xffff)); r1.union_ (r2); ASSERT_TRUE (r0 == r1); // A truncating cast back to signed char will work because [-120, 20] // is representable in signed char. range_cast (r0, signed_char_type_node); - ASSERT_TRUE (r0 == value_range (SCHAR (-120), SCHAR (20))); + ASSERT_TRUE (r0 == int_range<1> (SCHAR (-120), SCHAR (20))); // unsigned char -> signed short // (signed short)[(unsigned char)25, (unsigned char)250] // => [(signed short)25, (signed short)250] - r0 = rold = value_range (UCHAR (25), UCHAR (250)); + r0 = rold = int_range<1> (UCHAR (25), UCHAR (250)); range_cast (r0, short_integer_type_node); - r1 = value_range (INT16 (25), INT16 (250)); + r1 = int_range<1> (INT16 (25), INT16 (250)); ASSERT_TRUE (r0 == r1); range_cast (r0, unsigned_char_type_node); ASSERT_TRUE (r0 == rold); // Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned. - r0 = value_range (TYPE_MIN_VALUE (long_long_integer_type_node), + r0 = int_range<1> (TYPE_MIN_VALUE (long_long_integer_type_node), TYPE_MAX_VALUE (long_long_integer_type_node)); range_cast (r0, short_unsigned_type_node); - r1 = value_range (TYPE_MIN_VALUE (short_unsigned_type_node), + r1 = int_range<1> (TYPE_MIN_VALUE (short_unsigned_type_node), TYPE_MAX_VALUE (short_unsigned_type_node)); ASSERT_TRUE (r0 == r1); // NOT([10,20]) ==> [-MIN,9][21,MAX]. - r0 = r1 = value_range (INT (10), INT (20)); - r2 = value_range (minint, INT(9)); - r2.union_ (value_range (INT(21), maxint)); + r0 = r1 = int_range<1> (INT (10), INT (20)); + r2 = int_range<1> (minint, INT(9)); + r2.union_ (int_range<1> (INT(21), maxint)); ASSERT_FALSE (r2.undefined_p ()); r1.invert (); ASSERT_TRUE (r1 == r2); @@ -3021,11 +3735,11 @@ range_tests () // Test that booleans and their inverse work as expected. r0 = range_zero (boolean_type_node); - ASSERT_TRUE (r0 == value_range (build_zero_cst (boolean_type_node), - build_zero_cst (boolean_type_node))); + ASSERT_TRUE (r0 == int_range<1> (build_zero_cst (boolean_type_node), + build_zero_cst (boolean_type_node))); r0.invert (); - ASSERT_TRUE (r0 == value_range (build_one_cst (boolean_type_node), - build_one_cst (boolean_type_node))); + ASSERT_TRUE (r0 == int_range<1> (build_one_cst (boolean_type_node), + build_one_cst (boolean_type_node))); // Casting NONZERO to a narrower type will wrap/overflow so // it's just the entire range for the narrower type. @@ -3038,8 +3752,8 @@ range_tests () { r0 = range_nonzero (integer_type_node); range_cast (r0, short_integer_type_node); - r1 = value_range (TYPE_MIN_VALUE (short_integer_type_node), - TYPE_MAX_VALUE (short_integer_type_node)); + r1 = int_range<1> (TYPE_MIN_VALUE (short_integer_type_node), + TYPE_MAX_VALUE (short_integer_type_node)); ASSERT_TRUE (r0 == r1); } @@ -3049,8 +3763,8 @@ range_tests () // Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16]. r0 = range_nonzero (short_integer_type_node); range_cast (r0, integer_type_node); - r1 = value_range (INT (-32768), INT (-1)); - r2 = value_range (INT (1), INT (32767)); + r1 = int_range<1> (INT (-32768), INT (-1)); + r2 = int_range<1> (INT (1), INT (32767)); r1.union_ (r2); ASSERT_TRUE (r0 == r1); @@ -3064,34 +3778,34 @@ range_tests () ASSERT_TRUE (r0 == r1); // [10,20] U [15, 30] => [10, 30]. - r0 = value_range (INT (10), INT (20)); - r1 = value_range (INT (15), INT (30)); + r0 = int_range<1> (INT (10), INT (20)); + r1 = int_range<1> (INT (15), INT (30)); r0.union_ (r1); - ASSERT_TRUE (r0 == value_range (INT (10), INT (30))); + ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (30))); // [15,40] U [] => [15,40]. - r0 = value_range (INT (15), INT (40)); + r0 = int_range<1> (INT (15), INT (40)); r1.set_undefined (); r0.union_ (r1); - ASSERT_TRUE (r0 == value_range (INT (15), INT (40))); + ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (40))); // [10,20] U [10,10] => [10,20]. - r0 = value_range (INT (10), INT (20)); - r1 = value_range (INT (10), INT (10)); + r0 = int_range<1> (INT (10), INT (20)); + r1 = int_range<1> (INT (10), INT (10)); r0.union_ (r1); - ASSERT_TRUE (r0 == value_range (INT (10), INT (20))); + ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (20))); // [10,20] U [9,9] => [9,20]. - r0 = value_range (INT (10), INT (20)); - r1 = value_range (INT (9), INT (9)); + r0 = int_range<1> (INT (10), INT (20)); + r1 = int_range<1> (INT (9), INT (9)); r0.union_ (r1); - ASSERT_TRUE (r0 == value_range (INT (9), INT (20))); + ASSERT_TRUE (r0 == int_range<1> (INT (9), INT (20))); // [10,20] ^ [15,30] => [15,20]. - r0 = value_range (INT (10), INT (20)); - r1 = value_range (INT (15), INT (30)); + r0 = int_range<1> (INT (10), INT (20)); + r1 = int_range<1> (INT (15), INT (30)); r0.intersect (r1); - ASSERT_TRUE (r0 == value_range (INT (15), INT (20))); + ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (20))); // Test the internal sanity of wide_int's wrt HWIs. ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node), @@ -3099,13 +3813,17 @@ range_tests () == wi::uhwi (1, TYPE_PRECISION (boolean_type_node))); // Test zero_p(). - r0 = value_range (INT (0), INT (0)); + r0 = int_range<1> (INT (0), INT (0)); ASSERT_TRUE (r0.zero_p ()); // Test nonzero_p(). - r0 = value_range (INT (0), INT (0)); + r0 = int_range<1> (INT (0), INT (0)); r0.invert (); ASSERT_TRUE (r0.nonzero_p ()); + + multi_precision_range_tests (); + widest_irange_tests (); + operator_tests (); } } // namespace selftest diff --git a/gcc/range-op.h b/gcc/range-op.h index 1311965..08f6bf9 100644 --- a/gcc/range-op.h +++ b/gcc/range-op.h @@ -50,9 +50,9 @@ class range_operator { public: // Perform an operation between 2 ranges and return it. - virtual bool fold_range (value_range &r, tree type, - const value_range &lh, - const value_range &rh) const; + virtual bool fold_range (irange &r, tree type, + const irange &lh, + const irange &rh) const; // Return the range for op[12] in the general case. LHS is the range for // the LHS of the expression, OP[12]is the range for the other @@ -65,16 +65,16 @@ public: // // i.e. [LHS] = ??? + OP2 // is re-formed as R = [LHS] - OP2. - virtual bool op1_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op2) const; - virtual bool op2_range (value_range &r, tree type, - const value_range &lhs, - const value_range &op1) const; + virtual bool op1_range (irange &r, tree type, + const irange &lhs, + const irange &op2) const; + virtual bool op2_range (irange &r, tree type, + const irange &lhs, + const irange &op1) const; protected: // Perform an integral operation between 2 sub-ranges and return it. - virtual void wi_fold (value_range &r, tree type, + virtual void wi_fold (irange &r, tree type, const wide_int &lh_lb, const wide_int &lh_ub, const wide_int &rh_lb, @@ -82,7 +82,7 @@ protected: }; extern range_operator *range_op_handler (enum tree_code code, tree type); -extern void range_cast (value_range &, tree type); +extern void range_cast (irange &, tree type); extern void wi_set_zero_nonzero_bits (tree type, const wide_int &, const wide_int &, wide_int &maybe_nonzero, diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 7193ca4..de84c1d 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -1151,25 +1151,29 @@ static bool range_fold_binary_symbolics_p (value_range *vr, tree_code code, tree expr_type, - const value_range *vr0, const value_range *vr1) + const value_range *vr0_, + const value_range *vr1_) { - if (vr0->symbolic_p () || vr1->symbolic_p ()) + if (vr0_->symbolic_p () || vr1_->symbolic_p ()) { + value_range vr0 = drop_undefines_to_varying (vr0_, expr_type); + value_range vr1 = drop_undefines_to_varying (vr1_, expr_type); if ((code == PLUS_EXPR || code == MINUS_EXPR)) { - extract_range_from_plus_minus_expr (vr, code, expr_type, vr0, vr1); + extract_range_from_plus_minus_expr (vr, code, expr_type, + &vr0, &vr1); return true; } if (POINTER_TYPE_P (expr_type) && code == POINTER_PLUS_EXPR) { - extract_range_from_pointer_plus_expr (vr, code, expr_type, vr0, vr1); + extract_range_from_pointer_plus_expr (vr, code, expr_type, + &vr0, &vr1); return true; } const range_operator *op = get_range_op_handler (vr, code, expr_type); - value_range vr0_cst (*vr0), vr1_cst (*vr1); - vr0_cst.normalize_symbolics (); - vr1_cst.normalize_symbolics (); - return op->fold_range (*vr, expr_type, vr0_cst, vr1_cst); + vr0.normalize_symbolics (); + vr1.normalize_symbolics (); + return op->fold_range (*vr, expr_type, vr0, vr1); } return false; } @@ -1225,11 +1229,15 @@ range_fold_binary_expr (value_range *vr, if (!op) return; - value_range vr0 = drop_undefines_to_varying (vr0_, expr_type); - value_range vr1 = drop_undefines_to_varying (vr1_, expr_type); - if (range_fold_binary_symbolics_p (vr, code, expr_type, &vr0, &vr1)) + if (range_fold_binary_symbolics_p (vr, code, expr_type, vr0_, vr1_)) return; + value_range vr0 (*vr0_); + value_range vr1 (*vr1_); + if (vr0.undefined_p ()) + vr0.set_varying (expr_type); + if (vr1.undefined_p ()) + vr1.set_varying (expr_type); vr0.normalize_addresses (); vr1.normalize_addresses (); op->fold_range (*vr, expr_type, vr0, vr1); @@ -1637,7 +1645,7 @@ extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code, (to transform signed values into unsigned) and at the end xor SGNBIT back. */ -static wide_int +wide_int masked_increment (const wide_int &val_in, const wide_int &mask, const wide_int &sgnbit, unsigned int prec) { diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h index b3d187f..371e58a 100644 --- a/gcc/tree-vrp.h +++ b/gcc/tree-vrp.h @@ -62,5 +62,7 @@ extern bool overflow_comparison_p (tree_code, tree, tree, bool, tree *); 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 *); +extern wide_int masked_increment (const wide_int &val_in, const wide_int &mask, + const wide_int &sgnbit, unsigned int prec); #endif /* GCC_TREE_VRP_H */ @@ -1483,6 +1483,31 @@ int_cst_hasher::equal (tree x, tree y) return true; } +/* Cache wide_int CST into the TYPE_CACHED_VALUES cache for TYPE. + SLOT is the slot entry to store it in, and MAX_SLOTS is the maximum + number of slots that can be cached for the type. */ + +static inline tree +cache_wide_int_in_type_cache (tree type, const wide_int &cst, + int slot, int max_slots) +{ + gcc_checking_assert (slot >= 0); + /* Initialize cache. */ + if (!TYPE_CACHED_VALUES_P (type)) + { + TYPE_CACHED_VALUES_P (type) = 1; + TYPE_CACHED_VALUES (type) = make_tree_vec (max_slots); + } + tree t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), slot); + if (!t) + { + /* Create a new shared int. */ + t = build_new_int_cst (type, cst); + TREE_VEC_ELT (TYPE_CACHED_VALUES (type), slot) = t; + } + return t; +} + /* Create an INT_CST node of TYPE and value CST. The returned node is always shared. For small integers we use a per-type vector cache, for larger ones we use a single hash table. @@ -1515,6 +1540,28 @@ wide_int_to_tree_1 (tree type, const wide_int_ref &pcst) wide_int cst = wide_int::from (pcst, prec, sgn); unsigned int ext_len = get_int_cst_ext_nunits (type, cst); + enum tree_code code = TREE_CODE (type); + if (code == POINTER_TYPE || code == REFERENCE_TYPE) + { + /* Cache NULL pointer and zero bounds. */ + if (cst == 0) + ix = 0; + /* Cache upper bounds of pointers. */ + else if (cst == wi::max_value (prec, sgn)) + ix = 1; + /* Cache 1 which is used for a non-zero range. */ + else if (cst == 1) + ix = 2; + + if (ix >= 0) + { + t = cache_wide_int_in_type_cache (type, cst, ix, 3); + /* Make sure no one is clobbering the shared constant. */ + gcc_checking_assert (TREE_TYPE (t) == type + && cst == wi::to_wide (t)); + return t; + } + } if (ext_len == 1) { /* We just need to store a single HOST_WIDE_INT. */ @@ -1524,7 +1571,7 @@ wide_int_to_tree_1 (tree type, const wide_int_ref &pcst) else hwi = cst.to_shwi (); - switch (TREE_CODE (type)) + switch (code) { case NULLPTR_TYPE: gcc_assert (hwi == 0); @@ -1532,12 +1579,7 @@ wide_int_to_tree_1 (tree type, const wide_int_ref &pcst) case POINTER_TYPE: case REFERENCE_TYPE: - /* Cache NULL pointer and zero bounds. */ - if (hwi == 0) - { - limit = 1; - ix = 0; - } + /* Ignore pointers, as they were already handled above. */ break; case BOOLEAN_TYPE: @@ -1574,27 +1616,14 @@ wide_int_to_tree_1 (tree type, const wide_int_ref &pcst) if (ix >= 0) { - /* Look for it in the type's vector of small shared ints. */ - if (!TYPE_CACHED_VALUES_P (type)) - { - TYPE_CACHED_VALUES_P (type) = 1; - TYPE_CACHED_VALUES (type) = make_tree_vec (limit); - } - - t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix); - if (t) - /* Make sure no one is clobbering the shared constant. */ - gcc_checking_assert (TREE_TYPE (t) == type - && TREE_INT_CST_NUNITS (t) == 1 - && TREE_INT_CST_OFFSET_NUNITS (t) == 1 - && TREE_INT_CST_EXT_NUNITS (t) == 1 - && TREE_INT_CST_ELT (t, 0) == hwi); - else - { - /* Create a new shared int. */ - t = build_new_int_cst (type, cst); - TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t; - } + t = cache_wide_int_in_type_cache (type, cst, ix, limit); + /* Make sure no one is clobbering the shared constant. */ + gcc_checking_assert (TREE_TYPE (t) == type + && TREE_INT_CST_NUNITS (t) == 1 + && TREE_INT_CST_OFFSET_NUNITS (t) == 1 + && TREE_INT_CST_EXT_NUNITS (t) == 1 + && TREE_INT_CST_ELT (t, 0) == hwi); + return t; } else { diff --git a/gcc/value-range-equiv.cc b/gcc/value-range-equiv.cc index 24132e3..7dc10b8 100644 --- a/gcc/value-range-equiv.cc +++ b/gcc/value-range-equiv.cc @@ -90,13 +90,13 @@ value_range_equiv::update (tree min, tree max, value_range_kind kind) void value_range_equiv::deep_copy (const value_range_equiv *from) { - set (from->min (), from->max (), from->m_equiv, from->m_kind); + set (from->min (), from->max (), from->m_equiv, from->kind ()); } void value_range_equiv::move (value_range_equiv *from) { - set (from->min (), from->max (), NULL, from->m_kind); + set (from->min (), from->max (), NULL, from->kind ()); m_equiv = from->m_equiv; from->m_equiv = NULL; } @@ -127,8 +127,8 @@ value_range_equiv::set_equiv (bitmap equiv) void value_range_equiv::check () { - value_range::check (); - switch (m_kind) + value_range::verify_range (); + switch (kind ()) { case VR_UNDEFINED: case VR_VARYING: @@ -206,8 +206,9 @@ value_range_equiv::intersect (const value_range_equiv *other) this->deep_copy (other); else { - value_range tem = intersect_helper (this, other); - this->update (tem.min (), tem.max (), tem.kind ()); + legacy_intersect (this, other); + if (varying_p () || undefined_p ()) + equiv_clear (); /* If the result is VR_UNDEFINED there is no need to mess with equivalencies. */ @@ -254,8 +255,9 @@ value_range_equiv::union_ (const value_range_equiv *other) this->deep_copy (other); else { - value_range tem = union_helper (this, other); - this->update (tem.min (), tem.max (), tem.kind ()); + legacy_union (this, other); + if (varying_p () || undefined_p ()) + equiv_clear (); /* The resulting set of equivalences is always the intersection of the two sets. */ @@ -277,7 +279,7 @@ void value_range_equiv::dump (FILE *file) const { value_range::dump (file); - if ((m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE) + if ((kind () == VR_RANGE || kind () == VR_ANTI_RANGE) && m_equiv) { bitmap_iterator bi; diff --git a/gcc/value-range.cc b/gcc/value-range.cc index bc4b061..93164b7 100644 --- a/gcc/value-range.cc +++ b/gcc/value-range.cc @@ -1,5 +1,7 @@ /* Support routines for value ranges. Copyright (C) 2019-2020 Free Software Foundation, Inc. + Major hacks by Aldy Hernandez <aldyh@redhat.com> and + Andrew MacLeod <amacleod@redhat.com>. This file is part of GCC. @@ -27,45 +29,168 @@ along with GCC; see the file COPYING3. If not see #include "tree-pretty-print.h" #include "fold-const.h" -value_range::value_range (tree min, tree max, value_range_kind kind) +// Here we copy between any two irange's. The ranges can be legacy or +// multi-ranges, and copying between any combination works correctly. + +irange & +irange::operator= (const irange &src) +{ + if (legacy_mode_p () != src.legacy_mode_p ()) + { + copy_legacy_range (src); + return *this; + } + if (legacy_mode_p ()) + { + gcc_checking_assert (src.legacy_mode_p ()); + m_num_ranges = src.m_num_ranges; + m_base[0] = src.m_base[0]; + m_base[1] = src.m_base[1]; + m_kind = src.m_kind; + return *this; + } + + unsigned x; + unsigned lim = src.m_num_ranges; + if (lim > m_max_ranges) + lim = m_max_ranges; + + for (x = 0; x < lim * 2; ++x) + m_base[x] = src.m_base[x]; + + // If the range didn't fit, the last range should cover the rest. + if (lim != src.m_num_ranges) + m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1]; + + m_num_ranges = lim; + return *this; +} + +// Return TRUE if range is a multi-range that can be represented as a +// VR_ANTI_RANGE. + +bool +irange::maybe_anti_range () const { - set (min, max, kind); + tree ttype = type (); + unsigned int precision = TYPE_PRECISION (ttype); + signop sign = TYPE_SIGN (ttype); + return (num_pairs () > 1 + && precision > 1 + && lower_bound () == wi::min_value (precision, sign) + && upper_bound () == wi::max_value (precision, sign)); } -value_range::value_range (tree type) +// Copy between a legacy and a multi-range, or vice-versa. + +void +irange::copy_legacy_range (const irange &src) { - set_varying (type); + gcc_checking_assert (src.legacy_mode_p () != legacy_mode_p ()); + if (src.undefined_p ()) + set_undefined (); + else if (src.varying_p ()) + set_varying (src.type ()); + else if (src.kind () == VR_ANTI_RANGE) + set (src.min (), src.max (), VR_ANTI_RANGE); + else if (legacy_mode_p () && src.maybe_anti_range ()) + { + int_range<3> tmp (src); + tmp.invert (); + set (tmp.min (), wide_int_to_tree (src.type (), tmp.upper_bound (0)), + VR_ANTI_RANGE); + } + else + set (src.min (), src.max (), VR_RANGE); } -value_range::value_range (tree type, - const wide_int &wmin, const wide_int &wmax, - enum value_range_kind kind) +// Swap min/max if they are out of order. Return TRUE if further +// processing of the range is necessary, FALSE otherwise. + +bool +irange::swap_out_of_order_endpoints (tree &min, tree &max, + 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); + /* 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 false; + } + + 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 false; + } + kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE; + } + return true; } void -value_range::set_undefined () +irange::irange_set (tree min, tree max) { - m_kind = VR_UNDEFINED; - m_min = m_max = NULL; + gcc_checking_assert (!POLY_INT_CST_P (min)); + gcc_checking_assert (!POLY_INT_CST_P (max)); + + m_base[0] = min; + m_base[1] = max; + m_num_ranges = 1; + if (flag_checking) + verify_range (); } void -value_range::set_varying (tree type) +irange::irange_set_anti_range (tree min, tree max) { - m_kind = VR_VARYING; - if (supports_type_p (type)) + gcc_checking_assert (!POLY_INT_CST_P (min)); + gcc_checking_assert (!POLY_INT_CST_P (max)); + + // set an anti-range + tree type = TREE_TYPE (min); + signop sign = TYPE_SIGN (type); + int_range<2> type_range (type); + // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX]. + m_num_ranges = 0; + wi::overflow_type ovf; + + wide_int w_min = wi::to_wide (min); + if (wi::ne_p (w_min, type_range.lower_bound ())) { - m_min = vrp_val_min (type); - m_max = vrp_val_max (type); + wide_int lim1 = wi::sub (w_min, 1, sign, &ovf); + gcc_checking_assert (ovf != wi::OVF_OVERFLOW); + m_base[0] = type_range.tree_lower_bound (0); + m_base[1] = wide_int_to_tree (type, lim1); + m_num_ranges = 1; } - else - /* We can't do anything range-wise with these types. */ - m_min = m_max = error_mark_node; + wide_int w_max = wi::to_wide (max); + if (wi::ne_p (w_max, type_range.upper_bound ())) + { + wide_int lim2 = wi::add (w_max, 1, sign, &ovf); + gcc_checking_assert (ovf != wi::OVF_OVERFLOW); + m_base[m_num_ranges * 2] = wide_int_to_tree (type, lim2); + m_base[m_num_ranges * 2 + 1] = type_range.tree_upper_bound (0); + ++m_num_ranges; + } + if (flag_checking) + verify_range (); } /* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}. @@ -78,15 +203,24 @@ value_range::set_varying (tree type) extract ranges from var + CST op limit. */ void -value_range::set (tree min, tree max, value_range_kind kind) +irange::set (tree min, tree max, value_range_kind kind) { - /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */ + if (!legacy_mode_p ()) + { + if (kind == VR_RANGE) + irange_set (min, max); + else + { + gcc_checking_assert (kind == VR_ANTI_RANGE); + irange_set_anti_range (min, max); + } + return; + } if (kind == VR_UNDEFINED) { set_undefined (); return; } - if (kind == VR_RANGE) { /* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */ @@ -109,68 +243,30 @@ value_range::set (tree min, tree max, value_range_kind kind) } else if (kind != VR_VARYING) { - if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max)) - kind = VR_VARYING; + if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max)) + kind = VR_VARYING; } - 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); + set_varying (TREE_TYPE (min)); return; } - /* Nothing to canonicalize for symbolic ranges. */ + tree type = TREE_TYPE (min); + // 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; + m_base[0] = min; + m_base[1] = max; + m_num_ranges = 1; return; } + if (!swap_out_of_order_endpoints (min, max, kind)) + goto cleanup_set; - /* 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. */ + // 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 @@ -211,109 +307,90 @@ value_range::set (tree min, tree max, value_range_kind kind) kind = VR_RANGE; } } + else if (!swap_out_of_order_endpoints (min, max, kind)) + goto cleanup_set; - /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED. + /* 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. */ + if (!normalize_min_max (type, min, max, kind)) + { + m_kind = kind; + m_base[0] = min; + m_base[1] = max; + m_num_ranges = 1; + if (flag_checking) + verify_range (); + } - 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. */ + cleanup_set: + // 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 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; + m_kind = VR_VARYING; + else if (undefined_p ()) + m_kind = VR_UNDEFINED; 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)); + verify_range (); } /* Check the validity of the range. */ void -value_range::check () +irange::verify_range () { - switch (m_kind) + if (!legacy_mode_p ()) { - 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)); + gcc_checking_assert (m_kind == VR_RANGE); + for (unsigned i = 0; i < m_num_ranges; ++i) + { + tree lb = tree_lower_bound (i); + tree ub = tree_upper_bound (i); + int c = compare_values (lb, ub); + gcc_assert (c == 0 || c == -1); + } + return; + } - int cmp = compare_values (m_min, m_max); - gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); - break; - } + switch (m_kind) + { case VR_UNDEFINED: - gcc_assert (!min () && !max ()); + gcc_assert (m_num_ranges == 0); break; + case VR_VARYING: - gcc_assert (m_min && m_max); + gcc_assert (m_num_ranges == 1); break; + + case VR_ANTI_RANGE: + case VR_RANGE: + { + gcc_assert (m_num_ranges == 1); + int cmp = compare_values (tree_lower_bound (0), tree_upper_bound (0)); + gcc_assert (cmp == 0 || cmp == -1 || cmp == -2); + return; + } + default: gcc_unreachable (); } } -/* Return the number of sub-ranges in a range. */ - unsigned -value_range::num_pairs () const +irange::legacy_num_pairs () const { + gcc_checking_assert (legacy_mode_p ()); + if (undefined_p ()) return 0; if (varying_p ()) return 1; - if (symbolic_p ()) + // Inlined symbolic_p for performance: + if (!is_gimple_min_invariant (min ()) || !is_gimple_min_invariant (max ())) { value_range numeric_range (*this); numeric_range.normalize_symbolics (); @@ -323,111 +400,124 @@ value_range::num_pairs () const { // ~[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)) + if (vrp_val_is_min (min ()) || vrp_val_is_max (max ())) return 1; return 2; } + gcc_checking_assert (m_num_ranges == 1); return 1; } -/* Return the lower bound for a sub-range. PAIR is the sub-range in - question. */ +// Return the lower bound for a sub-range. PAIR is the sub-range in +// question. wide_int -value_range::lower_bound (unsigned pair) const +irange::legacy_lower_bound (unsigned pair) const { + gcc_checking_assert (legacy_mode_p ()); if (symbolic_p ()) { value_range numeric_range (*this); numeric_range.normalize_symbolics (); - return numeric_range.lower_bound (pair); + return numeric_range.legacy_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); + tree typ = type (), t; + if (pair == 1 || vrp_val_is_min (min ())) + t = wide_int_to_tree (typ, wi::to_wide (max ()) + 1); else t = vrp_val_min (typ); + return wi::to_wide (t); } - else - t = m_min; - return wi::to_wide (t); + return wi::to_wide (tree_lower_bound (pair)); } -/* Return the upper bound for a sub-range. PAIR is the sub-range in - question. */ +// Return the upper bound for a sub-range. PAIR is the sub-range in +// question. wide_int -value_range::upper_bound (unsigned pair) const +irange::legacy_upper_bound (unsigned pair) const { + gcc_checking_assert (legacy_mode_p ()); if (symbolic_p ()) { value_range numeric_range (*this); numeric_range.normalize_symbolics (); - return numeric_range.upper_bound (pair); + return numeric_range.legacy_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)) + tree typ = type (), t; + if (pair == 1 || vrp_val_is_min (min ())) t = vrp_val_max (typ); else - t = wide_int_to_tree (typ, wi::to_wide (m_min) - 1); + t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1); + return wi::to_wide (t); } - 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 wi::to_wide (tree_upper_bound (pair)); } bool -value_range::equal_p (const value_range &other) const +irange::legacy_equal_p (const irange &other) const { - /* Ignore types for undefined. All undefines are equal. */ - if (undefined_p ()) - return m_kind == other.m_kind; + gcc_checking_assert (legacy_mode_p () && other.legacy_mode_p ()); - return (m_kind == other.m_kind - && vrp_operand_equal_p (m_min, other.m_min) - && vrp_operand_equal_p (m_max, other.m_max)); + if (m_kind != other.m_kind) + return false; + if (m_kind == VR_UNDEFINED || m_kind == VR_VARYING) + return true; + return (vrp_operand_equal_p (tree_lower_bound (0), + other.tree_lower_bound (0)) + && vrp_operand_equal_p (tree_upper_bound (0), + other.tree_upper_bound (0))); } bool -value_range::operator== (const value_range &r) const +irange::equal_p (const irange &other) const { - return equal_p (r); + if (legacy_mode_p ()) + { + if (other.legacy_mode_p ()) + return legacy_equal_p (other); + value_range tmp (other); + return legacy_equal_p (tmp); + } + if (other.legacy_mode_p ()) + { + value_range tmp2 (*this); + return tmp2.legacy_equal_p (other); + } + + if (m_num_ranges != other.m_num_ranges) + return false; + + for (unsigned i = 0; i < m_num_ranges; ++i) + { + tree lb = tree_lower_bound (i); + tree ub = tree_upper_bound (i); + tree lb_other = other.tree_lower_bound (i); + tree ub_other = other.tree_upper_bound (i); + if (!operand_equal_p (lb, lb_other, 0) + || !operand_equal_p (ub, ub_other, 0)) + return false; + } + return true; } -/* 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 +irange::symbolic_p () const { return (!varying_p () && !undefined_p () - && (!is_gimple_min_invariant (m_min) - || !is_gimple_min_invariant (m_max))); + && (!is_gimple_min_invariant (min ()) + || !is_gimple_min_invariant (max ()))); } /* NOTE: This is not the inverse of symbolic_p because the range @@ -436,17 +526,32 @@ value_range::symbolic_p () const constants would be represented as [-MIN, +MAX]. */ bool -value_range::constant_p () const +irange::constant_p () const { return (!varying_p () && !undefined_p () - && TREE_CODE (m_min) == INTEGER_CST - && TREE_CODE (m_max) == INTEGER_CST); + && TREE_CODE (min ()) == INTEGER_CST + && TREE_CODE (max ()) == INTEGER_CST); } +/* 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 +irange::singleton_p (tree *result) const { + if (!legacy_mode_p ()) + { + if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ()) + == wi::to_wide (tree_upper_bound ()))) + { + if (result) + *result = tree_lower_bound (); + return true; + } + return false; + } if (m_kind == VR_ANTI_RANGE) { if (nonzero_p ()) @@ -454,7 +559,7 @@ value_range::singleton_p (tree *result) const if (TYPE_PRECISION (type ()) == 1) { if (result) - *result = m_max; + *result = max (); return true; } return false; @@ -462,10 +567,11 @@ value_range::singleton_p (tree *result) const if (num_pairs () == 1) { value_range vr0, vr1; - ranges_from_anti_range (this, &vr0, &vr1); + ranges_from_anti_range ((const value_range *) this, &vr0, &vr1); return vr0.singleton_p (result); } } + // Catches non-numeric extremes as well. if (m_kind == VR_RANGE && vrp_operand_equal_p (min (), max ()) && is_gimple_min_invariant (min ())) @@ -478,30 +584,31 @@ value_range::singleton_p (tree *result) const } /* Return 1 if VAL is inside value range. - 0 if VAL is not 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 +irange::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 (!legacy_mode_p () && TREE_CODE (val) == INTEGER_CST) + return contains_p (val); + + int cmp1 = operand_less_p (val, min ()); if (cmp1 == -2) return -2; if (cmp1 == 1) return m_kind != VR_RANGE; - cmp2 = operand_less_p (m_max, val); + int cmp2 = operand_less_p (max (), val); if (cmp2 == -2) return -2; @@ -514,30 +621,56 @@ value_range::value_inside_range (tree val) const /* Return TRUE if it is possible that range contains VAL. */ bool -value_range::may_contain_p (tree val) const +irange::may_contain_p (tree val) const { return value_inside_range (val) != 0; } /* Return TRUE if range contains INTEGER_CST. */ +/* Return 1 if VAL is inside value range. + 0 if VAL is not inside value range. + + Benchmark compile/20001226-1.c compilation time after changing this + function. */ + bool -value_range::contains_p (tree cst) const +irange::contains_p (tree cst) const { + if (undefined_p ()) + return false; + + if (legacy_mode_p ()) + { + gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST); + if (symbolic_p ()) + { + value_range numeric_range (*this); + numeric_range.normalize_symbolics (); + return numeric_range.contains_p (cst); + } + return value_inside_range (cst) == 1; + } + gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST); - if (symbolic_p ()) + signop sign = TYPE_SIGN (TREE_TYPE (cst)); + wide_int v = wi::to_wide (cst); + for (unsigned r = 0; r < m_num_ranges; ++r) { - value_range numeric_range (*this); - numeric_range.normalize_symbolics (); - return numeric_range.contains_p (cst); + if (wi::lt_p (v, lower_bound (r), sign)) + return false; + if (wi::le_p (v, upper_bound (r), sign)) + return true; } - return value_inside_range (cst) == 1; + + return false; } + /* Normalize addresses into constants. */ void -value_range::normalize_addresses () +irange::normalize_addresses () { if (undefined_p ()) return; @@ -547,8 +680,8 @@ value_range::normalize_addresses () if (!range_includes_zero_p (this)) { - gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR - || TREE_CODE (m_max) == ADDR_EXPR); + gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR + || TREE_CODE (max ()) == ADDR_EXPR); set_nonzero (type ()); return; } @@ -558,7 +691,7 @@ value_range::normalize_addresses () /* Normalize symbolics and addresses into constants. */ void -value_range::normalize_symbolics () +irange::normalize_symbolics () { if (varying_p () || undefined_p ()) return; @@ -939,45 +1072,64 @@ intersect_ranges (enum value_range_kind *vr0type, } /* 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. */ + ranges VR0 and VR1, set VR0 to the intersection of both ranges. + This may not be the smallest possible such range. */ -value_range -value_range::intersect_helper (const value_range *vr0, const value_range *vr1) +void +irange::legacy_intersect (irange *vr0, const irange *vr1) { /* If either range is VR_VARYING the other one wins. */ if (vr1->varying_p ()) - return *vr0; + return; if (vr0->varying_p ()) - return *vr1; + { + /* Avoid the full copy if we already know both sides are simple + and can be trivially copied. */ + if (vr1->legacy_mode_p ()) + { + vr0->set (vr1->min (), vr1->max (), vr1->kind ()); + return; + } + *vr0 = *vr1; + return; + } /* When either range is VR_UNDEFINED the resulting range is VR_UNDEFINED, too. */ if (vr0->undefined_p ()) - return *vr0; + return; if (vr1->undefined_p ()) - return *vr1; + { + vr0->set_undefined (); + return; + } 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 ()); + /* Handle multi-ranges that can be represented as anti-ranges. */ + if (!vr1->legacy_mode_p () && vr1->maybe_anti_range ()) + { + int_range<3> tmp (*vr1); + tmp.invert (); + intersect_ranges (&vr0kind, &vr0min, &vr0max, + VR_ANTI_RANGE, tmp.min (), tmp.max ()); + } + else + 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; + VR_RANGE can still be a VR_RANGE. */ if (vr0kind == VR_UNDEFINED) - tem.set_undefined (); + vr0->set_undefined (); else if (vr0kind == VR_VARYING) - tem.set_varying (vr0->type ()); + { + /* If we failed, use the original VR0. */ + return; + } else - tem.set (vr0min, vr0max, vr0kind); - /* If that failed, use the saved original VR0. */ - if (tem.varying_p ()) - return *vr0; - - return tem; + vr0->set (vr0min, vr0max, vr0kind); } /* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and @@ -1253,50 +1405,67 @@ give_up: *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 +/* Helper for meet operation for value ranges. Given two ranges VR0 + and VR1, set VR0 to the union of both ranges. This may not be the smallest possible such range. */ -value_range -value_range::union_helper (const value_range *vr0, const value_range *vr1) +void +irange::legacy_union (irange *vr0, const irange *vr1) { /* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */ if (vr1->undefined_p () || vr0->varying_p ()) - return *vr0; + return; /* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */ - if (vr0->undefined_p () - || vr1->varying_p ()) - return *vr1; + if (vr0->undefined_p ()) + { + /* Avoid the full copy if we already know both sides are simple + and can be trivially copied. */ + if (vr1->legacy_mode_p ()) + { + vr0->set (vr1->min (), vr1->max (), vr1->kind ()); + return; + } + *vr0 = *vr1; + return; + } + if (vr1->varying_p ()) + { + vr0->set_varying (vr1->type ()); + return; + } 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 ()); + /* Handle multi-ranges that can be represented as anti-ranges. */ + if (!vr1->legacy_mode_p () && vr1->maybe_anti_range ()) + { + int_range<3> tmp (*vr1); + tmp.invert (); + union_ranges (&vr0kind, &vr0min, &vr0max, + VR_ANTI_RANGE, tmp.min (), tmp.max ()); + } + else + 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 (); + vr0->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; + /* Failed to find an efficient meet. Before giving up and + setting the result to VARYING, see if we can at least derive + a non-zero range. */ + if (range_includes_zero_p (vr0) == 0 + && range_includes_zero_p (vr1) == 0) + vr0->set_nonzero (vr0->type ()); + else + vr0->set_varying (vr0->type ()); } - - return tem; + else + vr0->set (vr0min, vr0max, vr0kind); } /* Meet operation for value ranges. Given two value ranges VR0 and @@ -1304,161 +1473,495 @@ value_range::union_helper (const value_range *vr0, const value_range *vr1) may not be the smallest possible such range. */ void -value_range::union_ (const value_range *other) +irange::union_ (const irange *other) { - if (dump_file && (dump_flags & TDF_DETAILS)) + if (legacy_mode_p ()) { - 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"); - } + 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); + legacy_union (this, other); - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "to\n "); + dump_value_range (dump_file, this); + fprintf (dump_file, "\n"); + } + return; + } + + if (other->legacy_mode_p ()) { - fprintf (dump_file, "to\n "); - dump_value_range (dump_file, this); - fprintf (dump_file, "\n"); + int_range<2> wider; + wider = *other; + irange_union (wider); } + else + irange_union (*other); } -/* Range union, but for references. */ - void -value_range::union_ (const value_range &r) +irange::intersect (const irange *other) { - /* 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; + if (legacy_mode_p ()) + { + 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"); + } + + legacy_intersect (this, other); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "to\n "); + dump_value_range (dump_file, this); + fprintf (dump_file, "\n"); + } + return; + } + + if (other->legacy_mode_p ()) + { + int_range<2> wider; + wider = *other; + irange_intersect (wider); + } + else + irange_intersect (*other); } +// union_ for multi-ranges. + void -value_range::intersect (const value_range *other) +irange::irange_union (const irange &r) { - if (dump_file && (dump_flags & TDF_DETAILS)) + gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); + + if (r.undefined_p () || varying_p ()) + return; + + if (undefined_p () || r.varying_p ()) { - 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"); + operator= (r); + return; } - *this = intersect_helper (this, other); + // Do not worry about merging and such by reserving twice as many + // pairs as needed, and then simply sort the 2 ranges into this + // intermediate form. + // + // The intermediate result will have the property that the beginning + // of each range is <= the beginning of the next range. There may + // be overlapping ranges at this point. I.e. this would be valid + // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this + // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r, + // the merge is performed. + // + // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp] + tree ttype = r.type (); + signop sign = TYPE_SIGN (ttype); + + auto_vec<tree, 20> res; + wide_int u1 ; + wi::overflow_type ovf; + unsigned i = 0, j = 0, k = 0; + + while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2) + { + // lower of Xi and Xj is the lowest point. + if (wi::le_p (wi::to_wide (m_base[i]), wi::to_wide (r.m_base[j]), sign)) + { + res.safe_push (m_base[i]); + res.safe_push (m_base[i + 1]); + k += 2; + i += 2; + } + else + { + res.safe_push (r.m_base[j]); + res.safe_push (r.m_base[j + 1]); + k += 2; + j += 2; + } + } + for ( ; i < m_num_ranges * 2; i += 2) + { + res.safe_push (m_base[i]); + res.safe_push (m_base[i + 1]); + k += 2; + } + for ( ; j < r.m_num_ranges * 2; j += 2) + { + res.safe_push (r.m_base[j]); + res.safe_push (r.m_base[j + 1]); + k += 2; + } - if (dump_file && (dump_flags & TDF_DETAILS)) + // Now normalize the vector removing any overlaps. + i = 2; + int prec = TYPE_PRECISION (ttype); + wide_int max_val = wi::max_value (prec, sign); + for (j = 2; j < k ; j += 2) { - fprintf (dump_file, "to\n "); - dump_value_range (dump_file, this); - fprintf (dump_file, "\n"); + wide_int val_im1 = wi::to_wide (res[i - 1]); + if (val_im1 == max_val) + break; + u1 = wi::add (val_im1, 1, sign, &ovf); + + // Overflow indicates we are at MAX already. + // A wide int bug requires the previous max_val check + // trigger: gcc.c-torture/compile/pr80443.c with -O3 + if (ovf == wi::OVF_OVERFLOW) + break; + + wide_int val_j = wi::to_wide (res[j]); + wide_int val_jp1 = wi::to_wide (res[j+1]); + // Current upper+1 is >= lower bound next pair, then we merge ranges. + if (wi::ge_p (u1, val_j, sign)) + { + // New upper bounds is greater of current or the next one. + if (wi::gt_p (val_jp1, val_im1, sign)) + res [i - 1] = res[j + 1]; + } + else + { + // This is a new distinct range, but no point in copying it + // if it is already in the right place. + if (i != j) + { + res[i++] = res[j]; + res[i++] = res[j + 1]; + } + else + i += 2; + } } + + // At this point, the vector should have i ranges, none overlapping. + // Now it simply needs to be copied, and if there are too many + // ranges, merge some. We wont do any analysis as to what the + // "best" merges are, simply combine the final ranges into one. + if (i > m_max_ranges * 2) + { + res[m_max_ranges * 2 - 1] = res[i - 1]; + i = m_max_ranges * 2; + } + + for (j = 0; j < i ; j++) + m_base[j] = res [j]; + m_num_ranges = i / 2; + + if (flag_checking) + verify_range (); } -/* Range intersect, but for references. */ +// intersect for multi-ranges. void -value_range::intersect (const value_range &r) +irange::irange_intersect (const irange &r) +{ + gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ()); + + if (undefined_p () || r.varying_p ()) + return; + if (r.undefined_p ()) + { + set_undefined (); + return; + } + if (varying_p ()) + { + operator= (r); + return; + } + + signop sign = TYPE_SIGN (TREE_TYPE(m_base[0])); + unsigned bld_pair = 0; + unsigned bld_lim = m_max_ranges; + widest_irange r2 (*this); + unsigned r2_lim = r2.num_pairs (); + unsigned i2 = 0; + for (unsigned i = 0; i < r.num_pairs (); ) + { + // If r1's upper is < r2's lower, we can skip r1's pair. + tree ru = r.m_base[i * 2 + 1]; + tree r2l = r2.m_base[i2 * 2]; + if (wi::lt_p (wi::to_wide (ru), wi::to_wide (r2l), sign)) + { + i++; + continue; + } + // Likewise, skip r2's pair if its excluded. + tree r2u = r2.m_base[i2 * 2 + 1]; + tree rl = r.m_base[i * 2]; + if (wi::lt_p (wi::to_wide (r2u), wi::to_wide (rl), sign)) + { + i2++; + if (i2 < r2_lim) + continue; + // No more r2, break. + break; + } + + // Must be some overlap. Find the highest of the lower bounds, + // and set it, unless the build limits lower bounds is already + // set. + if (bld_pair < bld_lim) + { + if (wi::ge_p (wi::to_wide (rl), wi::to_wide (r2l), sign)) + m_base[bld_pair * 2] = rl; + else + m_base[bld_pair * 2] = r2l; + } + else + // Decrease and set a new upper. + bld_pair--; + + // ...and choose the lower of the upper bounds. + if (wi::le_p (wi::to_wide (ru), wi::to_wide (r2u), sign)) + { + m_base[bld_pair * 2 + 1] = ru; + bld_pair++; + // Move past the r1 pair and keep trying. + i++; + continue; + } + else + { + m_base[bld_pair * 2 + 1] = r2u; + bld_pair++; + i2++; + if (i2 < r2_lim) + continue; + // No more r2, break. + break; + } + // r2 has the higher lower bound. + } + + // At the exit of this loop, it is one of 2 things: + // ran out of r1, or r2, but either means we are done. + m_num_ranges = bld_pair; + if (flag_checking) + verify_range (); +} + +static wide_int inline +subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow) { - /* 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; + // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1 + // overflows, since +1 is unrepresentable. This is why we have an + // addition of -1 here. + if (TYPE_SIGN (type) == SIGNED) + return wi::add (x, -1 , SIGNED, &overflow); + else + return wi::sub (x, 1, UNSIGNED, &overflow); } /* Return the inverse of a range. */ void -value_range::invert () +irange::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); + if (legacy_mode_p ()) + { + // 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 (min (), max (), VR_ANTI_RANGE); + else if (m_kind == VR_ANTI_RANGE) + *this = value_range (min (), max ()); + else + gcc_unreachable (); + return; + } + + gcc_assert (!undefined_p () && !varying_p ()); + + // We always need one more set of bounds to represent an inverse, so + // if we're at the limit, we can't properly represent things. + // + // For instance, to represent the inverse of a 2 sub-range set + // [5, 10][20, 30], we would need a 3 sub-range set + // [-MIN, 4][11, 19][31, MAX]. + // + // In this case, return the most conservative thing. + // + // However, if any of the extremes of the range are -MIN/+MAX, we + // know we will not need an extra bound. For example: + // + // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX] + // INVERT([-MIN,20][30,MAX]) => [21,29] + tree ttype = type (); + unsigned prec = TYPE_PRECISION (ttype); + signop sign = TYPE_SIGN (ttype); + wide_int type_min = wi::min_value (prec, sign); + wide_int type_max = wi::max_value (prec, sign); + if (m_num_ranges == m_max_ranges + && lower_bound () != type_min + && upper_bound () != type_max) + { + m_base[1] = wide_int_to_tree (ttype, type_max); + m_num_ranges = 1; + return; + } + // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we + // generate [-MIN, a-1][b+1, c-1][d+1, MAX]. + // + // If there is an over/underflow in the calculation for any + // sub-range, we eliminate that subrange. This allows us to easily + // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since + // we eliminate the underflow, only [6, MAX] remains. + unsigned i = 0; + wi::overflow_type ovf; + // Construct leftmost range. + widest_irange orig_range (*this); + unsigned nitems = 0; + wide_int tmp; + // If this is going to underflow on the MINUS 1, don't even bother + // checking. This also handles subtracting one from an unsigned 0, + // which doesn't set the underflow bit. + if (type_min != orig_range.lower_bound ()) + { + m_base[nitems++] = wide_int_to_tree (ttype, type_min); + tmp = subtract_one (orig_range.lower_bound (), ttype, ovf); + m_base[nitems++] = wide_int_to_tree (ttype, tmp); + if (ovf) + nitems = 0; + } + i++; + // Construct middle ranges if applicable. + if (orig_range.num_pairs () > 1) + { + unsigned j = i; + for (; j < (orig_range.num_pairs () * 2) - 1; j += 2) + { + // The middle ranges cannot have MAX/MIN, so there's no need + // to check for unsigned overflow on the +1 and -1 here. + tmp = wi::add (wi::to_wide (orig_range.m_base[j]), 1, sign, &ovf); + m_base[nitems++] = wide_int_to_tree (ttype, tmp); + tmp = subtract_one (wi::to_wide (orig_range.m_base[j + 1]), + ttype, ovf); + m_base[nitems++] = wide_int_to_tree (ttype, tmp); + if (ovf) + nitems -= 2; + } + i = j; + } + // Construct rightmost range. + // + // However, if this will overflow on the PLUS 1, don't even bother. + // This also handles adding one to an unsigned MAX, which doesn't + // set the overflow bit. + if (type_max != wi::to_wide (orig_range.m_base[i])) + { + tmp = wi::add (wi::to_wide (orig_range.m_base[i]), 1, sign, &ovf); + m_base[nitems++] = wide_int_to_tree (ttype, tmp); + m_base[nitems++] = wide_int_to_tree (ttype, type_max); + if (ovf) + nitems -= 2; + } + m_num_ranges = nitems / 2; + + if (flag_checking) + verify_range (); +} + +static void +dump_bound_with_infinite_markers (FILE *file, tree bound) +{ + tree type = TREE_TYPE (bound); + if (INTEGRAL_TYPE_P (type) + && !TYPE_UNSIGNED (type) + && vrp_val_is_min (bound) + && TYPE_PRECISION (type) != 1) + fprintf (file, "-INF"); + else if (vrp_val_is_max (bound) + && TYPE_PRECISION (type) != 1) + fprintf (file, "+INF"); else - gcc_unreachable (); + print_generic_expr (file, bound); } void -value_range::dump (FILE *file) const +irange::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, "UNDEFINED"); + return; + } + print_generic_expr (file, type ()); + fprintf (file, " "); + if (varying_p ()) + { + fprintf (file, "VARYING"); + return; + } + if (legacy_mode_p ()) + { 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 ()); - + dump_bound_with_infinite_markers (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 ()); - + dump_bound_with_infinite_markers (file, max ()); fprintf (file, "]"); + return; } - else if (varying_p ()) + for (unsigned i = 0; i < m_num_ranges; ++i) { - print_generic_expr (file, type ()); - fprintf (file, " VARYING"); + tree lb = m_base[i * 2]; + tree ub = m_base[i * 2 + 1]; + fprintf (file, "["); + dump_bound_with_infinite_markers (file, lb); + fprintf (file, ", "); + dump_bound_with_infinite_markers (file, ub); + fprintf (file, "]"); } - else - gcc_unreachable (); } void -value_range::dump () const +dump_value_range (FILE *file, const irange *vr) { - dump (stderr); + vr->dump (file); } -void -dump_value_range (FILE *file, const value_range *vr) +DEBUG_FUNCTION void +debug (const irange *vr) { - if (!vr) - fprintf (file, "[]"); - else - vr->dump (file); + dump_value_range (stderr, vr); + fprintf (stderr, "\n"); +} + +DEBUG_FUNCTION void +debug (const irange &vr) +{ + debug (&vr); } DEBUG_FUNCTION void debug (const value_range *vr) { dump_value_range (stderr, vr); + fprintf (stderr, "\n"); } DEBUG_FUNCTION void debug (const value_range &vr) { dump_value_range (stderr, &vr); + fprintf (stderr, "\n"); } /* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR @@ -1501,40 +2004,13 @@ ranges_from_anti_range (const value_range *ar, } bool -range_has_numeric_bounds_p (const value_range *vr) +range_has_numeric_bounds_p (const irange *vr) { - return (vr->min () + return (!vr->undefined_p () && 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<tree> (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<tree> (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 @@ -1571,3 +2047,41 @@ vrp_operand_equal_p (const_tree val1, const_tree val2) return false; return true; } + +#define DEFINE_INT_RANGE_GC_STUBS(N) \ + void \ + gt_pch_nx (int_range<N> *&x) \ + { \ + for (unsigned i = 0; i < N; ++i) \ + { \ + gt_pch_nx (x->m_ranges[i * 2]); \ + gt_pch_nx (x->m_ranges[i * 2 + 1]); \ + } \ + } \ + \ + void \ + gt_ggc_mx (int_range<N> *&x) \ + { \ + for (unsigned i = 0; i < N; ++i) \ + { \ + gt_ggc_mx (x->m_ranges[i * 2]); \ + gt_ggc_mx (x->m_ranges[i * 2 + 1]); \ + } \ + } + +#define DEFINE_INT_RANGE_INSTANCE(N) \ + template int_range<N>::int_range(tree, tree, value_range_kind); \ + template int_range<N>::int_range(tree_node *, \ + const wide_int &, \ + const wide_int &, \ + value_range_kind); \ + template int_range<N>::int_range(tree); \ + template int_range<N>::int_range(const irange &); \ + template int_range<N>::int_range(const int_range &); \ + template int_range<N>& int_range<N>::operator= (const int_range &); + +DEFINE_INT_RANGE_INSTANCE(1) +DEFINE_INT_RANGE_INSTANCE(2) +DEFINE_INT_RANGE_INSTANCE(3) +DEFINE_INT_RANGE_INSTANCE(255) +DEFINE_INT_RANGE_GC_STUBS(1) diff --git a/gcc/value-range.h b/gcc/value-range.h index 0a9dc6f..e3282c4 100644 --- a/gcc/value-range.h +++ b/gcc/value-range.h @@ -1,5 +1,7 @@ /* Support routines for value ranges. Copyright (C) 2019-2020 Free Software Foundation, Inc. + Contributed by Aldy Hernandez <aldyh@redhat.com> and + Andrew Macleod <amacleod@redhat.com>. This file is part of GCC. @@ -20,7 +22,7 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_VALUE_RANGE_H #define GCC_VALUE_RANGE_H -/* Types of value ranges. */ +// Types of value ranges. enum value_range_kind { /* Empty range. */ @@ -36,164 +38,292 @@ enum value_range_kind }; // Range of values that can be associated with an SSA_NAME. +// +// This is the base class without any storage. -class GTY((for_user)) value_range +class irange { 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); - + // In-place setters. 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; - + // Range types. static bool supports_type_p (tree); - void normalize_symbolics (); - void normalize_addresses (); + tree type () const; - static const unsigned int m_max_pairs = 2; - bool contains_p (tree) const; + // Iteration over sub-ranges. unsigned num_pairs () const; wide_int lower_bound (unsigned = 0) const; wide_int upper_bound (unsigned) const; wide_int upper_bound () const; + + // Predicates. + bool zero_p () const; + bool nonzero_p () const; + bool undefined_p () const; + bool varying_p () const; + bool singleton_p (tree *result = NULL) const; + bool contains_p (tree) const; + + // In-place operators. + void union_ (const irange &); + void intersect (const irange &); void invert (); + // Operator overloads. + irange& operator= (const irange &); + bool operator== (const irange &) const; + bool operator!= (const irange &r) const { return !(*this == r); } + + // Misc methods. + void dump (FILE * = stderr) const; + + // Deprecated legacy public methods. + enum value_range_kind kind () const; // DEPRECATED + tree min () const; // DEPRECATED + tree max () const; // DEPRECATED + bool symbolic_p () const; // DEPRECATED + bool constant_p () const; // DEPRECATED + void normalize_symbolics (); // DEPRECATED + void normalize_addresses (); // DEPRECATED + bool may_contain_p (tree) const; // DEPRECATED + void set (tree); // DEPRECATED + bool equal_p (const irange &) const; // DEPRECATED + void union_ (const class irange *); // DEPRECATED + void intersect (const irange *); // DEPRECATED + 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; + irange (tree *, unsigned); + // potential promotion to public? + tree tree_lower_bound (unsigned = 0) const; + tree tree_upper_bound (unsigned) const; + tree tree_upper_bound () const; + + // In-place operators. + void irange_union (const irange &); + void irange_intersect (const irange &); + void irange_set (tree, tree); + void irange_set_anti_range (tree, tree); + + bool swap_out_of_order_endpoints (tree &min, tree &max, value_range_kind &); + bool normalize_min_max (tree type, tree min, tree max, value_range_kind); + + bool legacy_mode_p () const; + bool legacy_equal_p (const irange &) const; + void legacy_union (irange *, const irange *); + void legacy_intersect (irange *, const irange *); + void verify_range (); + unsigned legacy_num_pairs () const; + wide_int legacy_lower_bound (unsigned = 0) const; + wide_int legacy_upper_bound (unsigned) const; + int value_inside_range (tree) const; + bool maybe_anti_range () const; + void copy_legacy_range (const irange &); private: - int value_inside_range (tree) const; + unsigned char m_num_ranges; + unsigned char m_max_ranges; + ENUM_BITFIELD(value_range_kind) m_kind : 8; + tree *m_base; }; -extern bool range_has_numeric_bounds_p (const value_range *); +// Here we describe an irange with N pairs of ranges. The storage for +// the pairs is embedded in the class as an array. + +template<unsigned N> +class GTY((user)) int_range : public irange +{ +public: + int_range (); + int_range (tree, tree, value_range_kind = VR_RANGE); + int_range (tree type, const wide_int &, const wide_int &, + value_range_kind = VR_RANGE); + int_range (tree type); + int_range (const int_range &); + int_range (const irange &); + int_range& operator= (const int_range &); +private: + template <unsigned X> friend void gt_ggc_mx (int_range<X> *); + template <unsigned X> friend void gt_pch_nx (int_range<X> *); + template <unsigned X> friend void gt_pch_nx (int_range<X> *, + gt_pointer_operator, void *); + // ?? hash-traits.h has its own extern for these, which is causing + // them to never be picked up by the templates. For now, define + // elsewhere. + //template<unsigned X> friend void gt_ggc_mx (int_range<X> *&); + //template<unsigned X> friend void gt_pch_nx (int_range<X> *&); + friend void gt_ggc_mx (int_range<1> *&); + friend void gt_pch_nx (int_range<1> *&); + + tree m_ranges[N*2]; +}; + +// This is a special int_range<1> with only one pair, plus +// VR_ANTI_RANGE magic to describe slightly more than can be described +// in one pair. It is described in the code as a "legacy range" (as +// opposed to multi-ranges which have multiple sub-ranges). It is +// provided for backward compatibility with code that has not been +// converted to multi-range irange's. +// +// There are copy operators to seamlessly copy to/fro multi-ranges. +typedef int_range<1> value_range; + +// This is an "infinite" precision irange for use in temporary +// calculations. +typedef int_range<255> widest_irange; + +// Returns true for an old-school value_range as described above. +inline bool +irange::legacy_mode_p () const +{ + return m_max_ranges == 1; +} + +extern bool range_has_numeric_bounds_p (const irange *); extern bool ranges_from_anti_range (const value_range *, value_range *, value_range *); -extern void dump_value_range (FILE *, const value_range *); +extern void dump_value_range (FILE *, const irange *); 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 () +inline value_range_kind +irange::kind () const +{ + if (legacy_mode_p ()) + return m_kind; + + if (undefined_p ()) + return VR_UNDEFINED; + + if (varying_p ()) + return VR_VARYING; + + return VR_RANGE; +} + +// Number of sub-ranges in a range. + +inline unsigned +irange::num_pairs () const { - m_kind = VR_UNDEFINED; - m_min = m_max = NULL; + if (!legacy_mode_p ()) + return m_num_ranges; + else + return legacy_num_pairs (); } -inline value_range_kind -value_range::kind () const +inline tree +irange::type () const +{ + gcc_checking_assert (!undefined_p ()); + return TREE_TYPE (m_base[0]); +} + +// Return the lower bound of a sub-range expressed as a tree. PAIR is +// the sub-range in question. + +inline tree +irange::tree_lower_bound (unsigned pair) const +{ + return m_base[pair * 2]; +} + +// Return the upper bound of a sub-range expressed as a tree. PAIR is +// the sub-range in question. + +inline tree +irange::tree_upper_bound (unsigned pair) const { - return m_kind; + return m_base[pair * 2 + 1]; } +// Return the highest bound of a range expressed as a tree. + inline tree -value_range::type () const +irange::tree_upper_bound () const { - return TREE_TYPE (min ()); + gcc_checking_assert (m_num_ranges); + return tree_upper_bound (m_num_ranges - 1); } inline tree -value_range::min () const +irange::min () const { - return m_min; + return tree_lower_bound (0); } inline tree -value_range::max () const +irange::max () const { - return m_max; + if (m_num_ranges) + return tree_upper_bound (); + else + return NULL; } inline bool -value_range::varying_p () const +irange::varying_p () const { - return m_kind == VR_VARYING; + if (legacy_mode_p ()) + return m_kind == VR_VARYING; + + if (m_num_ranges != 1) + return false; + + tree l = m_base[0]; + tree u = m_base[1]; + tree t = TREE_TYPE (l); + if (INTEGRAL_TYPE_P (t)) + return l == TYPE_MIN_VALUE (t) && u == TYPE_MAX_VALUE (t); + if (POINTER_TYPE_P (t)) + return wi::to_wide (l) == 0 + && wi::to_wide (u) == wi::max_value (TYPE_PRECISION (t), + TYPE_SIGN (t)); + return true; + } inline bool -value_range::undefined_p () const +irange::undefined_p () const { + if (!legacy_mode_p ()) + return m_num_ranges == 0; + + if (CHECKING_P && legacy_mode_p ()) + { + if (m_kind == VR_UNDEFINED) + gcc_checking_assert (m_num_ranges == 0); + else + gcc_checking_assert (m_num_ranges != 0); + } return m_kind == VR_UNDEFINED; } inline bool -value_range::zero_p () const +irange::zero_p () const { - return (m_kind == VR_RANGE - && integer_zerop (m_min) - && integer_zerop (m_max)); + return (m_kind == VR_RANGE && m_num_ranges == 1 + && integer_zerop (tree_lower_bound (0)) + && integer_zerop (tree_upper_bound (0))); } inline bool -value_range::nonzero_p () const +irange::nonzero_p () const { - if (m_kind == VR_ANTI_RANGE - && !TYPE_UNSIGNED (type ()) - && integer_zerop (m_min) - && integer_zerop (m_max)) - return true; + if (undefined_p ()) + return false; - return (m_kind == VR_RANGE - && TYPE_UNSIGNED (type ()) - && integer_onep (m_min) - && vrp_val_is_max (m_max)); + tree zero = build_zero_cst (type ()); + return *this == int_range<1> (zero, zero, VR_ANTI_RANGE); } inline bool -value_range::supports_type_p (tree type) +irange::supports_type_p (tree type) { if (type && (INTEGRAL_TYPE_P (type) || POINTER_TYPE_P (type))) return type; @@ -201,7 +331,7 @@ value_range::supports_type_p (tree type) } inline bool -range_includes_zero_p (const value_range *vr) +range_includes_zero_p (const irange *vr) { if (vr->undefined_p ()) return false; @@ -212,4 +342,281 @@ range_includes_zero_p (const value_range *vr) return vr->may_contain_p (build_zero_cst (vr->type ())); } +template<unsigned N> +static inline void +gt_ggc_mx (int_range<N> *x) +{ + for (unsigned i = 0; i < N; ++i) + { + gt_ggc_mx (x->m_ranges[i * 2]); + gt_ggc_mx (x->m_ranges[i * 2 + 1]); + } +} + +template<unsigned N> +static inline void +gt_pch_nx (int_range<N> *x) +{ + for (unsigned i = 0; i < N; ++i) + { + gt_pch_nx (x->m_ranges[i * 2]); + gt_pch_nx (x->m_ranges[i * 2 + 1]); + } +} + +template<unsigned N> +static inline void +gt_pch_nx (int_range<N> *x, gt_pointer_operator op, void *cookie) +{ + for (unsigned i = 0; i < N; ++i) + { + op (&x->m_ranges[i * 2], cookie); + op (&x->m_ranges[i * 2 + 1], cookie); + } +} + +// Constructors for irange + +inline +irange::irange (tree *base, unsigned nranges) +{ + m_base = base; + m_num_ranges = 0; + m_max_ranges = nranges; + if (legacy_mode_p ()) + m_kind = VR_UNDEFINED; + else + m_kind = VR_RANGE; +} + +// Constructors for int_range<>. + +template<unsigned N> +inline +int_range<N>::int_range () + : irange (m_ranges, N) +{ +} + +template<unsigned N> +int_range<N>::int_range (const int_range &other) + : irange (m_ranges, N) +{ + irange::operator= (other); +} + +template<unsigned N> +int_range<N>::int_range (tree min, tree max, value_range_kind kind) + : irange (m_ranges, N) +{ + irange::set (min, max, kind); +} + +template<unsigned N> +int_range<N>::int_range (tree type) + : irange (m_ranges, N) +{ + set_varying (type); +} + +template<unsigned N> +int_range<N>::int_range (tree type, const wide_int &wmin, const wide_int &wmax, + value_range_kind kind) + : irange (m_ranges, N) +{ + tree min = wide_int_to_tree (type, wmin); + tree max = wide_int_to_tree (type, wmax); + set (min, max, kind); +} + +template<unsigned N> +int_range<N>::int_range (const irange &other) + : irange (m_ranges, N) +{ + irange::operator= (other); +} + +template<unsigned N> +int_range<N>& +int_range<N>::operator= (const int_range &src) +{ + irange::operator= (src); + return *this; +} + +inline void +irange::set (tree val) +{ + set (val, val); +} + +inline void +irange::set_undefined () +{ + m_num_ranges = 0; + if (legacy_mode_p ()) + m_kind = VR_UNDEFINED; +} + +inline void +irange::set_varying (tree type) +{ + if (legacy_mode_p ()) + m_kind = VR_VARYING; + + m_num_ranges = 1; + if (INTEGRAL_TYPE_P (type)) + { + m_base[0] = TYPE_MIN_VALUE (type); + m_base[1] = TYPE_MAX_VALUE (type); + } + else if (POINTER_TYPE_P (type)) + { + m_base[0] = build_int_cst (type, 0); + m_base[1] = build_int_cst (type, -1); + } + else + m_base[0] = m_base[1] = error_mark_node; +} + +inline bool +irange::operator== (const irange &r) const +{ + return equal_p (r); +} + +// Return the lower bound of a sub-range. PAIR is the sub-range in +// question. + +inline wide_int +irange::lower_bound (unsigned pair) const +{ + if (legacy_mode_p ()) + return legacy_lower_bound (pair); + gcc_checking_assert (!undefined_p ()); + gcc_checking_assert (pair + 1 <= num_pairs ()); + return wi::to_wide (tree_lower_bound (pair)); +} + +// Return the upper bound of a sub-range. PAIR is the sub-range in +// question. + +inline wide_int +irange::upper_bound (unsigned pair) const +{ + if (legacy_mode_p ()) + return legacy_upper_bound (pair); + gcc_checking_assert (!undefined_p ()); + gcc_checking_assert (pair + 1 <= num_pairs ()); + return wi::to_wide (tree_upper_bound (pair)); +} + +// Return the highest bound of a range. + +inline wide_int +irange::upper_bound () const +{ + unsigned pairs = num_pairs (); + gcc_checking_assert (pairs > 0); + return upper_bound (pairs - 1); +} + +inline void +irange::union_ (const irange &r) +{ + dump_flags_t m_flags = dump_flags; + dump_flags &= ~TDF_DETAILS; + irange::union_ (&r); + dump_flags = m_flags; +} + +inline void +irange::intersect (const irange &r) +{ + dump_flags_t m_flags = dump_flags; + dump_flags &= ~TDF_DETAILS; + irange::intersect (&r); + dump_flags = m_flags; +} + +// Set value range VR to a nonzero range of type TYPE. + +inline void +irange::set_nonzero (tree type) +{ + tree zero = build_int_cst (type, 0); + if (legacy_mode_p ()) + set (zero, zero, VR_ANTI_RANGE); + else + irange_set_anti_range (zero, zero); +} + +// Set value range VR to a ZERO range of type TYPE. + +inline void +irange::set_zero (tree type) +{ + tree z = build_int_cst (type, 0); + if (legacy_mode_p ()) + set (z); + else + irange_set (z, z); +} + +// 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. + +inline bool +irange::normalize_min_max (tree type, tree min, tree max, + value_range_kind kind) +{ + 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 true; + } + return false; +} + +// Return the maximum value for TYPE. + +inline 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<tree> (type), max); + } + return NULL_TREE; +} + +// Return the minimum value for TYPE. + +inline 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<tree> (type)); + return NULL_TREE; +} + #endif // GCC_VALUE_RANGE_H diff --git a/gcc/vr-values.c b/gcc/vr-values.c index d030359..609375c 100644 --- a/gcc/vr-values.c +++ b/gcc/vr-values.c @@ -92,7 +92,8 @@ vr_values::get_lattice_entry (const_tree var) return vr; /* Create a default value range. */ - vr_value[ver] = vr = vrp_value_range_pool.allocate (); + vr = new (vrp_value_range_pool.allocate ()) value_range_equiv; + vr_value[ver] = vr; /* After propagation finished return varying. */ if (values_propagated) |