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, 57 insertions, 28 deletions

diff --git a/gcc/tree.c b/gcc/tree.c
index 6522a08..01a342c 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -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
 	{