Multi-range implementation for value_range (irange).

Implement class irange, a generic multi-range implementation for
value ranges.  This class is API compatible with value_range, and is meant
to seamlessly coexist with it.

gcc/ChangeLog:

	* Makefile.in (GTFILES): Move value-range.h up.
	* gengtype-lex.l: Set yylval to handle GTY markers on templates.
	* ipa-cp.c (initialize_node_lattices): Call value_range
	constructor.
	(ipcp_propagate_stage): Use in-place new so value_range construct
	is called.
	* ipa-fnsummary.c (evaluate_conditions_for_known_args): Use std
	vec instead of GCC's vec<>.
	(evaluate_properties_for_edge): Adjust for std vec.
	(ipa_fn_summary_t::duplicate): Same.
	(estimate_ipcp_clone_size_and_time): Same.
	* ipa-prop.c (ipa_get_value_range): Use in-place new for
	value_range.
	* ipa-prop.h (struct GTY): Remove class keyword for m_vr.
	* range-op.cc (empty_range_check): Rename to...
	(empty_range_varying): ...this and adjust for varying.
	(undefined_shift_range_check): Adjust for irange.
	(range_operator::wi_fold): Same.
	(range_operator::fold_range): Adjust for irange.  Special case
	single pairs for performance.
	(range_operator::op1_range): Adjust for irange.
	(range_operator::op2_range): Same.
	(value_range_from_overflowed_bounds): Same.
	(value_range_with_overflow): Same.
	(create_possibly_reversed_range): Same.
	(range_true): Same.
	(range_false): Same.
	(range_true_and_false): Same.
	(get_bool_state):  Adjust for irange and tweak for performance.
	(operator_equal::fold_range): Adjust for irange.
	(operator_equal::op1_range): Same.
	(operator_equal::op2_range): Same.
	(operator_not_equal::fold_range): Same.
	(operator_not_equal::op1_range): Same.
	(operator_not_equal::op2_range): Same.
	(build_lt): Same.
	(build_le): Same.
	(build_gt): Same.
	(build_ge): Same.
	(operator_lt::fold_range): Same.
	(operator_lt::op1_range): Same.
	(operator_lt::op2_range): Same.
	(operator_le::fold_range): Same.
	(operator_le::op1_range): Same.
	(operator_le::op2_range): Same.
	(operator_gt::fold_range): Same.
	(operator_gt::op1_range): Same.
	(operator_gt::op2_range): Same.
	(operator_ge::fold_range): Same.
	(operator_ge::op1_range): Same.
	(operator_ge::op2_range): Same.
	(operator_plus::wi_fold): Same.
	(operator_plus::op1_range): Same.
	(operator_plus::op2_range): Same.
	(operator_minus::wi_fold): Same.
	(operator_minus::op1_range): Same.
	(operator_minus::op2_range): Same.
	(operator_min::wi_fold): Same.
	(operator_max::wi_fold): Same.
	(cross_product_operator::wi_cross_product): Same.
	(operator_mult::op1_range): New.
	(operator_mult::op2_range): New.
	(operator_mult::wi_fold): Adjust for irange.
	(operator_div::wi_fold): Same.
	(operator_exact_divide::op1_range): Same.
	(operator_lshift::fold_range): Same.
	(operator_lshift::wi_fold): Same.
	(operator_lshift::op1_range): New.
	(operator_rshift::op1_range): New.
	(operator_rshift::fold_range): Adjust for irange.
	(operator_rshift::wi_fold): Same.
	(operator_cast::truncating_cast_p): Abstract out from
	operator_cast::fold_range.
	(operator_cast::fold_range): Adjust for irange and tweak for
	performance.
	(operator_cast::inside_domain_p): Abstract out from fold_range.
	(operator_cast::fold_pair): Same.
	(operator_cast::op1_range): Use abstracted methods above.  Adjust
	for irange and tweak for performance.
	(operator_logical_and::fold_range): Adjust for irange.
	(operator_logical_and::op1_range): Same.
	(operator_logical_and::op2_range): Same.
	(unsigned_singleton_p): New.
	(operator_bitwise_and::remove_impossible_ranges): New.
	(operator_bitwise_and::fold_range): New.
	(wi_optimize_and_or):  Adjust for irange.
	(operator_bitwise_and::wi_fold): Same.
	(set_nonzero_range_from_mask): New.
	(operator_bitwise_and::simple_op1_range_solver): New.
	(operator_bitwise_and::op1_range): Adjust for irange.
	(operator_bitwise_and::op2_range): Same.
	(operator_logical_or::fold_range): Same.
	(operator_logical_or::op1_range): Same.
	(operator_logical_or::op2_range): Same.
	(operator_bitwise_or::wi_fold): Same.
	(operator_bitwise_or::op1_range): Same.
	(operator_bitwise_or::op2_range): Same.
	(operator_bitwise_xor::wi_fold): Same.
	(operator_bitwise_xor::op1_range): New.
	(operator_bitwise_xor::op2_range): New.
	(operator_trunc_mod::wi_fold):  Adjust for irange.
	(operator_logical_not::fold_range): Same.
	(operator_logical_not::op1_range): Same.
	(operator_bitwise_not::fold_range): Same.
	(operator_bitwise_not::op1_range): Same.
	(operator_cst::fold_range): Same.
	(operator_identity::fold_range): Same.
	(operator_identity::op1_range): Same.
	(class operator_unknown): New.
	(operator_unknown::fold_range): New.
	(class operator_abs): Adjust for irange.
	(operator_abs::wi_fold): Same.
	(operator_abs::op1_range): Same.
	(operator_absu::wi_fold): Same.
	(class operator_negate): Same.
	(operator_negate::fold_range): Same.
	(operator_negate::op1_range): Same.
	(operator_addr_expr::fold_range): Same.
	(operator_addr_expr::op1_range): Same.
	(pointer_plus_operator::wi_fold): Same.
	(pointer_min_max_operator::wi_fold): Same.
	(pointer_and_operator::wi_fold): Same.
	(pointer_or_operator::op1_range): New.
	(pointer_or_operator::op2_range): New.
	(pointer_or_operator::wi_fold):  Adjust for irange.
	(integral_table::integral_table): Add entries for IMAGPART_EXPR
	and POINTER_DIFF_EXPR.
	(range_cast):  Adjust for irange.
	(build_range3): New.
	(range3_tests): New.
	(widest_irange_tests): New.
	(multi_precision_range_tests): New.
	(operator_tests): New.
	(range_tests): New.
	* range-op.h (class range_operator): Adjust for irange.
	(range_cast): Same.
	* tree-vrp.c (range_fold_binary_symbolics_p): Adjust for irange and
	tweak for performance.
	(range_fold_binary_expr): Same.
	(masked_increment): Change to extern.
	* tree-vrp.h (masked_increment): New.
	* tree.c (cache_wide_int_in_type_cache): New function abstracted
	out from wide_int_to_tree_1.
	(wide_int_to_tree_1): Cache 0, 1, and MAX for pointers.
	* value-range-equiv.cc (value_range_equiv::deep_copy): Use kind
	method.
	(value_range_equiv::move): Same.
	(value_range_equiv::check): Adjust for irange.
	(value_range_equiv::intersect): Same.
	(value_range_equiv::union_): Same.
	(value_range_equiv::dump): Same.
	* value-range.cc (irange::operator=): Same.
	(irange::maybe_anti_range): New.
	(irange::copy_legacy_range): New.
	(irange::set_undefined): Adjust for irange.
	(irange::swap_out_of_order_endpoints): Abstract out from set().
	(irange::set_varying): Adjust for irange.
	(irange::irange_set): New.
	(irange::irange_set_anti_range): New.
	(irange::set): Adjust for irange.
	(value_range::set_nonzero): Move to header file.
	(value_range::set_zero): Move to header file.
	(value_range::check): Rename to...
	(irange::verify_range): ...this.
	(value_range::num_pairs): Rename to...
	(irange::legacy_num_pairs): ...this, and adjust for irange.
	(value_range::lower_bound): Rename to...
	(irange::legacy_lower_bound): ...this, and adjust for irange.
	(value_range::upper_bound): Rename to...
	(irange::legacy_upper_bound): ...this, and adjust for irange.
	(value_range::equal_p): Rename to...
	(irange::legacy_equal_p): ...this.
	(value_range::operator==): Move to header file.
	(irange::equal_p): New.
	(irange::symbolic_p): Adjust for irange.
	(irange::constant_p): Same.
	(irange::singleton_p): Same.
	(irange::value_inside_range): Same.
	(irange::may_contain_p): Same.
	(irange::contains_p): Same.
	(irange::normalize_addresses): Same.
	(irange::normalize_symbolics): Same.
	(irange::legacy_intersect): Same.
	(irange::legacy_union): Same.
	(irange::union_): Same.
	(irange::intersect): Same.
	(irange::irange_union): New.
	(irange::irange_intersect): New.
	(subtract_one): New.
	(irange::invert): Adjust for irange.
	(dump_bound_with_infinite_markers): New.
	(irange::dump): Adjust for irange.
	(debug): Add irange versions.
	(range_has_numeric_bounds_p): Adjust for irange.
	(vrp_val_max): Move to header file.
	(vrp_val_min): Move to header file.
	(DEFINE_INT_RANGE_GC_STUBS): New.
	(DEFINE_INT_RANGE_INSTANCE): New.
	* value-range.h (class irange): New.
	(class int_range): New.
	(class value_range): Rename to a instantiation of int_range.
	(irange::legacy_mode_p): New.
	(value_range::value_range): Remove.
	(irange::kind): New.
	(irange::num_pairs): Adjust for irange.
	(irange::type): Adjust for irange.
	(irange::tree_lower_bound): New.
	(irange::tree_upper_bound): New.
	(irange::type): Adjust for irange.
	(irange::min): Same.
	(irange::max): Same.
	(irange::varying_p): Same.
	(irange::undefined_p): Same.
	(irange::zero_p): Same.
	(irange::nonzero_p): Same.
	(irange::supports_type_p): Same.
	(range_includes_zero_p): Same.
	(gt_ggc_mx): New.
	(gt_pch_nx): New.
	(irange::irange): New.
	(int_range::int_range): New.
	(int_range::operator=): New.
	(irange::set): Moved from value-range.cc and adjusted for irange.
	(irange::set_undefined): Same.
	(irange::set_varying): Same.
	(irange::operator==): Same.
	(irange::lower_bound): Same.
	(irange::upper_bound): Same.
	(irange::union_): Same.
	(irange::intersect): Same.
	(irange::set_nonzero): Same.
	(irange::set_zero): Same.
	(irange::normalize_min_max): New.
	(vrp_val_max): Move from value-range.cc.
	(vrp_val_min): Same.
	* vr-values.c (vr_values::get_lattice_entry): Call value_range
	constructor.

1 files changed, 13 insertions, 7 deletions

diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
index 55a0b272a96..49bab04524b 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,