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, 20 insertions, 12 deletions

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)
 {