[PATCH] Convert ipa_jump_func to use ipa_vr instead of a value_range.

[PATCH] Convert ipa_jump_func to use ipa_vr instead of a value_range.

[Aldy Hernandez]

This patch converts the ipa_jump_func code to use the type agnostic
ipa_vr suitable for GC instead of value_range which is integer specific.

I've disabled the range cacheing to simplify the patch for review, but
it is handled in the next patch in the series.

OK?

gcc/ChangeLog:

	* ipa-cp.cc (ipa_vr_operation_and_type_effects): New.
	* ipa-prop.cc (ipa_get_value_range): Adjust for ipa_vr.
	(ipa_set_jfunc_vr): Take a range.
	(ipa_compute_jump_functions_for_edge): Pass range to
	ipa_set_jfunc_vr.
	(ipa_write_jump_function): Call streamer write helper.
	(ipa_read_jump_function): Call streamer read helper.
	* ipa-prop.h (class ipa_vr): Change m_vr to an ipa_vr.
---
 gcc/ipa-cp.cc   | 15 +++++++++++
 gcc/ipa-prop.cc | 70 ++++++++++++++++++-------------------------------
 gcc/ipa-prop.h  |  5 +++-
 3 files changed, 44 insertions(+), 46 deletions(-)

diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
index bdbc2184b5f..03273666ea2 100644
--- a/gcc/ipa-cp.cc
+++ b/gcc/ipa-cp.cc
@@ -1928,6 +1928,21 @@ ipa_vr_operation_and_type_effects (vrange &dst_vr,
 	  && !dst_vr.undefined_p ());
 }
 
+/* Same as above, but the SRC_VR argument is an IPA_VR which must
+   first be extracted onto a vrange.  */
+
+static bool
+ipa_vr_operation_and_type_effects (vrange &dst_vr,
+				   const ipa_vr &src_vr,
+				   enum tree_code operation,
+				   tree dst_type, tree src_type)
+{
+  Value_Range tmp;
+  src_vr.get_vrange (tmp);
+  return ipa_vr_operation_and_type_effects (dst_vr, tmp, operation,
+					    dst_type, src_type);
+}
+
 /* Determine range of JFUNC given that INFO describes the caller node or
    the one it is inlined to, CS is the call graph edge corresponding to JFUNC
    and PARM_TYPE of the parameter.  */
diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
index bbfe0f8aa45..c46a89f1b49 100644
--- a/gcc/ipa-prop.cc
+++ b/gcc/ipa-prop.cc
@@ -2287,9 +2287,10 @@ ipa_set_jfunc_bits (ipa_jump_func *jf, const widest_int &value,
 /* Return a pointer to a value_range just like *TMP, but either find it in
    ipa_vr_hash_table or allocate it in GC memory.  TMP->equiv must be NULL.  */
 
-static value_range *
-ipa_get_value_range (value_range *tmp)
+static ipa_vr *
+ipa_get_value_range (const vrange &tmp)
 {
+  /* FIXME: Add hashing support.
   value_range **slot = ipa_vr_hash_table->find_slot (tmp, INSERT);
   if (*slot)
     return *slot;
@@ -2297,40 +2298,27 @@ ipa_get_value_range (value_range *tmp)
   value_range *vr = new (ggc_alloc<value_range> ()) value_range;
   *vr = *tmp;
   *slot = vr;
+  */
+  ipa_vr *vr = new (ggc_alloc<ipa_vr> ()) ipa_vr (tmp);
 
   return vr;
 }
 
-/* Return a pointer to a value range consisting of TYPE, MIN, MAX and an empty
-   equiv set. Use hash table in order to avoid creating multiple same copies of
-   value_ranges.  */
-
-static value_range *
-ipa_get_value_range (enum value_range_kind kind, tree min, tree max)
-{
-  value_range tmp (TREE_TYPE (min),
-		   wi::to_wide (min), wi::to_wide (max), kind);
-  return ipa_get_value_range (&tmp);
-}
-
-/* Assign to JF a pointer to a value_range structure with TYPE, MIN and MAX and
-   a NULL equiv bitmap.  Use hash table in order to avoid creating multiple
-   same value_range structures.  */
+/* Assign to JF a pointer to a value_range just like TMP but either fetch a
+   copy from ipa_vr_hash_table or allocate a new on in GC memory.  */
 
 static void
-ipa_set_jfunc_vr (ipa_jump_func *jf, enum value_range_kind type,
-		  tree min, tree max)
+ipa_set_jfunc_vr (ipa_jump_func *jf, const vrange &tmp)
 {
-  jf->m_vr = ipa_get_value_range (type, min, max);
+  jf->m_vr = ipa_get_value_range (tmp);
 }
 
-/* Assign to JF a pointer to a value_range just like TMP but either fetch a
-   copy from ipa_vr_hash_table or allocate a new on in GC memory.  */
-
 static void
-ipa_set_jfunc_vr (ipa_jump_func *jf, value_range *tmp)
+ipa_set_jfunc_vr (ipa_jump_func *jf, const ipa_vr &vr)
 {
-  jf->m_vr = ipa_get_value_range (tmp);
+  Value_Range tmp;
+  vr.get_vrange (tmp);
+  ipa_set_jfunc_vr (jf, tmp);
 }
 
 /* Compute jump function for all arguments of callsite CS and insert the
@@ -2392,8 +2380,8 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 
 	  if (addr_nonzero)
 	    {
-	      tree z = build_int_cst (TREE_TYPE (arg), 0);
-	      ipa_set_jfunc_vr (jfunc, VR_ANTI_RANGE, z, z);
+	      vr.set_nonzero (TREE_TYPE (arg));
+	      ipa_set_jfunc_vr (jfunc, vr);
 	    }
 	  else
 	    gcc_assert (!jfunc->m_vr);
@@ -2412,7 +2400,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 	      value_range resvr = vr;
 	      range_cast (resvr, param_type);
 	      if (!resvr.undefined_p () && !resvr.varying_p ())
-		ipa_set_jfunc_vr (jfunc, &resvr);
+		ipa_set_jfunc_vr (jfunc, resvr);
 	      else
 		gcc_assert (!jfunc->m_vr);
 	    }
@@ -4864,16 +4852,12 @@ ipa_write_jump_function (struct output_block *ob,
       streamer_write_widest_int (ob, jump_func->bits->value);
       streamer_write_widest_int (ob, jump_func->bits->mask);
     }
-  bp_pack_value (&bp, !!jump_func->m_vr, 1);
-  streamer_write_bitpack (&bp);
   if (jump_func->m_vr)
+    jump_func->m_vr->streamer_write (ob);
+  else
     {
-      tree min, max;
-      value_range_kind kind = get_legacy_range (*jump_func->m_vr, min, max);
-      streamer_write_enum (ob->main_stream, value_rang_type,
-			   VR_LAST, kind);
-      stream_write_tree (ob, min, true);
-      stream_write_tree (ob, max, true);
+      bp_pack_value (&bp, false, 1);
+      streamer_write_bitpack (&bp);
     }
 }
 
@@ -5001,21 +4985,17 @@ ipa_read_jump_function (class lto_input_block *ib,
       widest_int value = streamer_read_widest_int (ib);
       widest_int mask = streamer_read_widest_int (ib);
       if (prevails)
-        ipa_set_jfunc_bits (jump_func, value, mask);
+	ipa_set_jfunc_bits (jump_func, value, mask);
     }
   else
     jump_func->bits = NULL;
 
-  struct bitpack_d vr_bp = streamer_read_bitpack (ib);
-  bool vr_known = bp_unpack_value (&vr_bp, 1);
-  if (vr_known)
+  ipa_vr vr;
+  vr.streamer_read (ib, data_in);
+  if (vr.known_p ())
     {
-      enum value_range_kind type = streamer_read_enum (ib, value_range_kind,
-						       VR_LAST);
-      tree min = stream_read_tree (ib, data_in);
-      tree max = stream_read_tree (ib, data_in);
       if (prevails)
-        ipa_set_jfunc_vr (jump_func, type, min, max);
+	ipa_set_jfunc_vr (jump_func, vr);
     }
   else
     jump_func->m_vr = NULL;
diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
index f87e8a596c1..33fad228913 100644
--- a/gcc/ipa-prop.h
+++ b/gcc/ipa-prop.h
@@ -325,6 +325,9 @@ private:
   friend void gt_pch_nx (struct ipa_vr &);
   friend void gt_ggc_mx (struct ipa_vr &);
   friend void gt_pch_nx (struct ipa_vr *, gt_pointer_operator, void *);
+  friend void gt_ggc_mx_ipa_vr (void *);
+  friend void gt_pch_nx_ipa_vr (void*);
+  friend void gt_pch_p_6ipa_vr(void*, void*, gt_pointer_operator, void*);
 
   vrange_storage *m_storage;
   // vrange_storage is typeless, but we need to know what type of
@@ -351,7 +354,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.  */
-  value_range *m_vr;
+  ipa_vr *m_vr;
 
   enum jump_func_type type;
   /* Represents a value of a jump function.  pass_through is used only in jump
-- 
2.40.1

[PATCH] Implement ipa_vr hashing.

[Aldy Hernandez]

Implement hashing for ipa_vr.  When all is said and done, all these
patches incurr a 7.64% slowdown for ipa-cp, with is entirely covered by
the similar 7% increase in this area last week.  So we get type agnostic
ranges with "infinite" range precision close to free.

There is no change in overall compilation.

OK?

gcc/ChangeLog:

	* ipa-prop.cc (struct ipa_vr_ggc_hash_traits): Adjust for use with
	ipa_vr instead of value_range.
	(gt_pch_nx): Same.
	(gt_ggc_mx): Same.
	(ipa_get_value_range): Same.
	* value-range.cc (gt_pch_nx): Move to ipa-prop.cc and adjust for
	ipa_vr.
	(gt_ggc_mx): Same.
---
 gcc/ipa-prop.cc    | 76 +++++++++++++++++++++++++++-------------------
 gcc/value-range.cc | 15 ---------
 2 files changed, 45 insertions(+), 46 deletions(-)

diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
index c46a89f1b49..6383bc11e0a 100644
--- a/gcc/ipa-prop.cc
+++ b/gcc/ipa-prop.cc
@@ -109,53 +109,53 @@ struct ipa_bit_ggc_hash_traits : public ggc_cache_remove <ipa_bits *>
 /* Hash table for avoid repeated allocations of equal ipa_bits.  */
 static GTY ((cache)) hash_table<ipa_bit_ggc_hash_traits> *ipa_bits_hash_table;
 
-/* Traits for a hash table for reusing value_ranges used for IPA.  Note that
-   the equiv bitmap is not hashed and is expected to be NULL.  */
+/* Traits for a hash table for reusing ranges.  */
 
-struct ipa_vr_ggc_hash_traits : public ggc_cache_remove <value_range *>
+struct ipa_vr_ggc_hash_traits : public ggc_cache_remove <ipa_vr *>
 {
-  typedef value_range *value_type;
-  typedef value_range *compare_type;
+  typedef ipa_vr *value_type;
+  typedef const vrange *compare_type;
   static hashval_t
-  hash (const value_range *p)
+  hash (const ipa_vr *p)
     {
-      tree min, max;
-      value_range_kind kind = get_legacy_range (*p, min, max);
-      inchash::hash hstate (kind);
-      inchash::add_expr (min, hstate);
-      inchash::add_expr (max, hstate);
+      // This never get called, except in the verification code, as
+      // ipa_get_value_range() calculates the hash itself.  This
+      // function is mostly here for completness' sake.
+      Value_Range vr;
+      p->get_vrange (vr);
+      inchash::hash hstate;
+      add_vrange (vr, hstate);
       return hstate.end ();
     }
   static bool
-  equal (const value_range *a, const value_range *b)
+  equal (const ipa_vr *a, const vrange *b)
     {
-      return (types_compatible_p (a->type (), b->type ())
-	      && *a == *b);
+      return a->equal_p (*b);
     }
   static const bool empty_zero_p = true;
   static void
-  mark_empty (value_range *&p)
+  mark_empty (ipa_vr *&p)
     {
       p = NULL;
     }
   static bool
-  is_empty (const value_range *p)
+  is_empty (const ipa_vr *p)
     {
       return p == NULL;
     }
   static bool
-  is_deleted (const value_range *p)
+  is_deleted (const ipa_vr *p)
     {
-      return p == reinterpret_cast<const value_range *> (1);
+      return p == reinterpret_cast<const ipa_vr *> (1);
     }
   static void
-  mark_deleted (value_range *&p)
+  mark_deleted (ipa_vr *&p)
     {
-      p = reinterpret_cast<value_range *> (1);
+      p = reinterpret_cast<ipa_vr *> (1);
     }
 };
 
-/* Hash table for avoid repeated allocations of equal value_ranges.  */
+/* Hash table for avoid repeated allocations of equal ranges.  */
 static GTY ((cache)) hash_table<ipa_vr_ggc_hash_traits> *ipa_vr_hash_table;
 
 /* Holders of ipa cgraph hooks: */
@@ -265,6 +265,22 @@ ipa_vr::dump (FILE *out) const
     fprintf (out, "NO RANGE");
 }
 
+// ?? These stubs are because we use an ipa_vr in a hash_traits and
+// hash-traits.h defines an extern of gt_ggc_mx (T &) instead of
+// picking up the gt_ggc_mx (T *) version.
+void
+gt_pch_nx (ipa_vr *&x)
+{
+  return gt_pch_nx ((ipa_vr *) x);
+}
+
+void
+gt_ggc_mx (ipa_vr *&x)
+{
+  return gt_ggc_mx ((ipa_vr *) x);
+}
+
+
 /* Return true if DECL_FUNCTION_SPECIFIC_OPTIMIZATION of the decl associated
    with NODE should prevent us from analyzing it for the purposes of IPA-CP.  */
 
@@ -2284,27 +2300,25 @@ ipa_set_jfunc_bits (ipa_jump_func *jf, const widest_int &value,
   jf->bits = ipa_get_ipa_bits_for_value (value, mask);
 }
 
-/* Return a pointer to a value_range just like *TMP, but either find it in
-   ipa_vr_hash_table or allocate it in GC memory.  TMP->equiv must be NULL.  */
+/* Return a pointer to an ipa_vr just like TMP, but either find it in
+   ipa_vr_hash_table or allocate it in GC memory.  */
 
 static ipa_vr *
 ipa_get_value_range (const vrange &tmp)
 {
-  /* FIXME: Add hashing support.
-  value_range **slot = ipa_vr_hash_table->find_slot (tmp, INSERT);
+  inchash::hash hstate;
+  inchash::add_vrange (tmp, hstate);
+  hashval_t hash = hstate.end ();
+  ipa_vr **slot = ipa_vr_hash_table->find_slot_with_hash (&tmp, hash, INSERT);
   if (*slot)
     return *slot;
 
-  value_range *vr = new (ggc_alloc<value_range> ()) value_range;
-  *vr = *tmp;
-  *slot = vr;
-  */
   ipa_vr *vr = new (ggc_alloc<ipa_vr> ()) ipa_vr (tmp);
-
+  *slot = vr;
   return vr;
 }
 
-/* Assign to JF a pointer to a value_range just like TMP but either fetch a
+/* Assign to JF a pointer to a range just like TMP but either fetch a
    copy from ipa_vr_hash_table or allocate a new on in GC memory.  */
 
 static void
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 45b1e655967..7b81025357b 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -2008,21 +2008,6 @@ gt_pch_nx (vrange *x, gt_pointer_operator op, void *cookie)
     gcc_unreachable ();
 }
 
-// ?? These stubs are for ipa-prop.cc which use a value_range in a
-// hash_traits.  hash-traits.h defines an extern of gt_ggc_mx (T &)
-// instead of picking up the gt_ggc_mx (T *) version.
-void
-gt_pch_nx (int_range<2> *&x)
-{
-  return gt_pch_nx ((irange *) x);
-}
-
-void
-gt_ggc_mx (int_range<2> *&x)
-{
-  return gt_ggc_mx ((irange *) x);
-}
-
 #define DEFINE_INT_RANGE_INSTANCE(N)					\
   template int_range<N>::int_range(tree_node *,				\
 				   const wide_int &,			\
-- 
2.40.1

[PATCH] Convert remaining uses of value_range in ipa-*.cc to Value_Range.

[Aldy Hernandez]

Minor cleanups to get rid of value_range in IPA.  There's only one left,
but it's in the switch code which is integer specific.

OK?

gcc/ChangeLog:

	* ipa-cp.cc (decide_whether_version_node): Adjust comment.
	* ipa-fnsummary.cc (evaluate_conditions_for_known_args): Adjust
	for Value_Range.
	(set_switch_stmt_execution_predicate): Same.
	* ipa-prop.cc (ipa_compute_jump_functions_for_edge): Same.
---
 gcc/ipa-cp.cc        |  3 +--
 gcc/ipa-fnsummary.cc | 22 ++++++++++++++--------
 gcc/ipa-prop.cc      |  9 +++------
 3 files changed, 18 insertions(+), 16 deletions(-)

diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
index 03273666ea2..2e64415096e 100644
--- a/gcc/ipa-cp.cc
+++ b/gcc/ipa-cp.cc
@@ -6287,8 +6287,7 @@ decide_whether_version_node (struct cgraph_node *node)
 	    {
 	      /* If some values generated for self-recursive calls with
 		 arithmetic jump functions fall outside of the known
-		 value_range for the parameter, we can skip them.  VR interface
-		 supports this only for integers now.  */
+		 range for the parameter, we can skip them.  */
 	      if (TREE_CODE (val->value) == INTEGER_CST
 		  && !plats->m_value_range.bottom_p ()
 		  && !ipa_range_contains_p (plats->m_value_range.m_vr,
diff --git a/gcc/ipa-fnsummary.cc b/gcc/ipa-fnsummary.cc
index 0474af8991e..1ce8501fe85 100644
--- a/gcc/ipa-fnsummary.cc
+++ b/gcc/ipa-fnsummary.cc
@@ -488,19 +488,20 @@ evaluate_conditions_for_known_args (struct cgraph_node *node,
 		  if (vr.varying_p () || vr.undefined_p ())
 		    break;
 
-		  value_range res;
+		  Value_Range res (op->type);
 		  if (!op->val[0])
 		    {
+		      Value_Range varying (op->type);
+		      varying.set_varying (op->type);
 		      range_op_handler handler (op->code, op->type);
 		      if (!handler
 			  || !res.supports_type_p (op->type)
-			  || !handler.fold_range (res, op->type, vr,
-						  value_range (op->type)))
+			  || !handler.fold_range (res, op->type, vr, varying))
 			res.set_varying (op->type);
 		    }
 		  else if (!op->val[1])
 		    {
-		      value_range op0;
+		      Value_Range op0 (op->type);
 		      range_op_handler handler (op->code, op->type);
 
 		      ipa_range_set_and_normalize (op0, op->val[0]);
@@ -518,14 +519,14 @@ evaluate_conditions_for_known_args (struct cgraph_node *node,
 		}
 	      if (!vr.varying_p () && !vr.undefined_p ())
 		{
-		  value_range res;
-		  value_range val_vr;
+		  int_range<2> res;
+		  Value_Range val_vr (TREE_TYPE (c->val));
 		  range_op_handler handler (c->code, boolean_type_node);
 
 		  ipa_range_set_and_normalize (val_vr, c->val);
 
 		  if (!handler
-		      || !res.supports_type_p (boolean_type_node)
+		      || !val_vr.supports_type_p (TREE_TYPE (c->val))
 		      || !handler.fold_range (res, boolean_type_node, vr, val_vr))
 		    res.set_varying (boolean_type_node);
 
@@ -1687,12 +1688,17 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi,
   int bound_limit = opt_for_fn (fbi->node->decl,
 				param_ipa_max_switch_predicate_bounds);
   int bound_count = 0;
-  value_range vr;
+  // This can safely be an integer range, as switches can only hold
+  // integers.
+  int_range<2> vr;
 
   get_range_query (cfun)->range_of_expr (vr, op);
   if (vr.undefined_p ())
     vr.set_varying (TREE_TYPE (op));
   tree vr_min, vr_max;
+  // ?? This entire function could use a rewrite to use the irange
+  // API, instead of trying to recreate its intersection/union logic.
+  // Any use of get_legacy_range() is a serious code smell.
   value_range_kind vr_type = get_legacy_range (vr, vr_min, vr_max);
   wide_int vr_wmin = wi::to_wide (vr_min);
   wide_int vr_wmax = wi::to_wide (vr_max);
diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
index 6383bc11e0a..5f9e6dbbff2 100644
--- a/gcc/ipa-prop.cc
+++ b/gcc/ipa-prop.cc
@@ -2348,7 +2348,6 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
   gcall *call = cs->call_stmt;
   int n, arg_num = gimple_call_num_args (call);
   bool useful_context = false;
-  value_range vr;
 
   if (arg_num == 0 || args->jump_functions)
     return;
@@ -2379,6 +2378,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 	    useful_context = true;
 	}
 
+      Value_Range vr (TREE_TYPE (arg));
       if (POINTER_TYPE_P (TREE_TYPE (arg)))
 	{
 	  bool addr_nonzero = false;
@@ -2404,14 +2404,11 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
 	{
 	  if (TREE_CODE (arg) == SSA_NAME
 	      && param_type
-	      /* Limit the ranger query to integral types as the rest
-		 of this file uses value_range's, which only hold
-		 integers and pointers.  */
-	      && irange::supports_p (TREE_TYPE (arg))
+	      && Value_Range::supports_type_p (TREE_TYPE (arg))
 	      && get_range_query (cfun)->range_of_expr (vr, arg)
 	      && !vr.undefined_p ())
 	    {
-	      value_range resvr = vr;
+	      Value_Range resvr (vr);
 	      range_cast (resvr, param_type);
 	      if (!resvr.undefined_p () && !resvr.varying_p ())
 		ipa_set_jfunc_vr (jfunc, resvr);
-- 
2.40.1

Re: [PATCH] Implement ipa_vr hashing.

[Martin Jambor]

Hi,

On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
> Implement hashing for ipa_vr.  When all is said and done, all these
> patches incurr a 7.64% slowdown for ipa-cp, with is entirely covered by
> the similar 7% increase in this area last week.  So we get type agnostic
> ranges with "infinite" range precision close to free.

Do you know why/where this slow-down happens?  Do we perhaps want to
limit the "infiniteness" a little somehow?

Also, jump functions live for a long time, have you looked at how memory
hungry they become?  I hope that the hashing would be good at preventing
any issues.

Generally, I think I OK with the patches if the impact on memory is not
too bad, though I guess they depend on the one I looked at last week, so
we may focus on that one first.

Thanks,

Martin

>
> There is no change in overall compilation.
>
> OK?
>
> gcc/ChangeLog:
>
> 	* ipa-prop.cc (struct ipa_vr_ggc_hash_traits): Adjust for use with
> 	ipa_vr instead of value_range.
> 	(gt_pch_nx): Same.
> 	(gt_ggc_mx): Same.
> 	(ipa_get_value_range): Same.
> 	* value-range.cc (gt_pch_nx): Move to ipa-prop.cc and adjust for
> 	ipa_vr.
> 	(gt_ggc_mx): Same.
> ---
>  gcc/ipa-prop.cc    | 76 +++++++++++++++++++++++++++-------------------
>  gcc/value-range.cc | 15 ---------
>  2 files changed, 45 insertions(+), 46 deletions(-)
>
> diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
> index c46a89f1b49..6383bc11e0a 100644
> --- a/gcc/ipa-prop.cc
> +++ b/gcc/ipa-prop.cc
> @@ -109,53 +109,53 @@ struct ipa_bit_ggc_hash_traits : public ggc_cache_remove <ipa_bits *>
>  /* Hash table for avoid repeated allocations of equal ipa_bits.  */
>  static GTY ((cache)) hash_table<ipa_bit_ggc_hash_traits> *ipa_bits_hash_table;
>  
> -/* Traits for a hash table for reusing value_ranges used for IPA.  Note that
> -   the equiv bitmap is not hashed and is expected to be NULL.  */
> +/* Traits for a hash table for reusing ranges.  */
>  
> -struct ipa_vr_ggc_hash_traits : public ggc_cache_remove <value_range *>
> +struct ipa_vr_ggc_hash_traits : public ggc_cache_remove <ipa_vr *>
>  {
> -  typedef value_range *value_type;
> -  typedef value_range *compare_type;
> +  typedef ipa_vr *value_type;
> +  typedef const vrange *compare_type;
>    static hashval_t
> -  hash (const value_range *p)
> +  hash (const ipa_vr *p)
>      {
> -      tree min, max;
> -      value_range_kind kind = get_legacy_range (*p, min, max);
> -      inchash::hash hstate (kind);
> -      inchash::add_expr (min, hstate);
> -      inchash::add_expr (max, hstate);
> +      // This never get called, except in the verification code, as
> +      // ipa_get_value_range() calculates the hash itself.  This
> +      // function is mostly here for completness' sake.
> +      Value_Range vr;
> +      p->get_vrange (vr);
> +      inchash::hash hstate;
> +      add_vrange (vr, hstate);
>        return hstate.end ();
>      }
>    static bool
> -  equal (const value_range *a, const value_range *b)
> +  equal (const ipa_vr *a, const vrange *b)
>      {
> -      return (types_compatible_p (a->type (), b->type ())
> -	      && *a == *b);
> +      return a->equal_p (*b);
>      }
>    static const bool empty_zero_p = true;
>    static void
> -  mark_empty (value_range *&p)
> +  mark_empty (ipa_vr *&p)
>      {
>        p = NULL;
>      }
>    static bool
> -  is_empty (const value_range *p)
> +  is_empty (const ipa_vr *p)
>      {
>        return p == NULL;
>      }
>    static bool
> -  is_deleted (const value_range *p)
> +  is_deleted (const ipa_vr *p)
>      {
> -      return p == reinterpret_cast<const value_range *> (1);
> +      return p == reinterpret_cast<const ipa_vr *> (1);
>      }
>    static void
> -  mark_deleted (value_range *&p)
> +  mark_deleted (ipa_vr *&p)
>      {
> -      p = reinterpret_cast<value_range *> (1);
> +      p = reinterpret_cast<ipa_vr *> (1);
>      }
>  };
>  
> -/* Hash table for avoid repeated allocations of equal value_ranges.  */
> +/* Hash table for avoid repeated allocations of equal ranges.  */
>  static GTY ((cache)) hash_table<ipa_vr_ggc_hash_traits> *ipa_vr_hash_table;
>  
>  /* Holders of ipa cgraph hooks: */
> @@ -265,6 +265,22 @@ ipa_vr::dump (FILE *out) const
>      fprintf (out, "NO RANGE");
>  }
>  
> +// ?? These stubs are because we use an ipa_vr in a hash_traits and
> +// hash-traits.h defines an extern of gt_ggc_mx (T &) instead of
> +// picking up the gt_ggc_mx (T *) version.
> +void
> +gt_pch_nx (ipa_vr *&x)
> +{
> +  return gt_pch_nx ((ipa_vr *) x);
> +}
> +
> +void
> +gt_ggc_mx (ipa_vr *&x)
> +{
> +  return gt_ggc_mx ((ipa_vr *) x);
> +}
> +
> +
>  /* Return true if DECL_FUNCTION_SPECIFIC_OPTIMIZATION of the decl associated
>     with NODE should prevent us from analyzing it for the purposes of IPA-CP.  */
>  
> @@ -2284,27 +2300,25 @@ ipa_set_jfunc_bits (ipa_jump_func *jf, const widest_int &value,
>    jf->bits = ipa_get_ipa_bits_for_value (value, mask);
>  }
>  
> -/* Return a pointer to a value_range just like *TMP, but either find it in
> -   ipa_vr_hash_table or allocate it in GC memory.  TMP->equiv must be NULL.  */
> +/* Return a pointer to an ipa_vr just like TMP, but either find it in
> +   ipa_vr_hash_table or allocate it in GC memory.  */
>  
>  static ipa_vr *
>  ipa_get_value_range (const vrange &tmp)
>  {
> -  /* FIXME: Add hashing support.
> -  value_range **slot = ipa_vr_hash_table->find_slot (tmp, INSERT);
> +  inchash::hash hstate;
> +  inchash::add_vrange (tmp, hstate);
> +  hashval_t hash = hstate.end ();
> +  ipa_vr **slot = ipa_vr_hash_table->find_slot_with_hash (&tmp, hash, INSERT);
>    if (*slot)
>      return *slot;
>  
> -  value_range *vr = new (ggc_alloc<value_range> ()) value_range;
> -  *vr = *tmp;
> -  *slot = vr;
> -  */
>    ipa_vr *vr = new (ggc_alloc<ipa_vr> ()) ipa_vr (tmp);
> -
> +  *slot = vr;
>    return vr;
>  }
>  
> -/* Assign to JF a pointer to a value_range just like TMP but either fetch a
> +/* Assign to JF a pointer to a range just like TMP but either fetch a
>     copy from ipa_vr_hash_table or allocate a new on in GC memory.  */
>  
>  static void
> diff --git a/gcc/value-range.cc b/gcc/value-range.cc
> index 45b1e655967..7b81025357b 100644
> --- a/gcc/value-range.cc
> +++ b/gcc/value-range.cc
> @@ -2008,21 +2008,6 @@ gt_pch_nx (vrange *x, gt_pointer_operator op, void *cookie)
>      gcc_unreachable ();
>  }
>  
> -// ?? These stubs are for ipa-prop.cc which use a value_range in a
> -// hash_traits.  hash-traits.h defines an extern of gt_ggc_mx (T &)
> -// instead of picking up the gt_ggc_mx (T *) version.
> -void
> -gt_pch_nx (int_range<2> *&x)
> -{
> -  return gt_pch_nx ((irange *) x);
> -}
> -
> -void
> -gt_ggc_mx (int_range<2> *&x)
> -{
> -  return gt_ggc_mx ((irange *) x);
> -}
> -
>  #define DEFINE_INT_RANGE_INSTANCE(N)					\
>    template int_range<N>::int_range(tree_node *,				\
>  				   const wide_int &,			\
> -- 
> 2.40.1

Re: [PATCH] Implement ipa_vr hashing.

[Aldy Hernandez]

On 5/29/23 16:51, Martin Jambor wrote:
> Hi,
> 
> On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
>> Implement hashing for ipa_vr.  When all is said and done, all these
>> patches incurr a 7.64% slowdown for ipa-cp, with is entirely covered by
>> the similar 7% increase in this area last week.  So we get type agnostic
>> ranges with "infinite" range precision close to free.
> 
> Do you know why/where this slow-down happens?  Do we perhaps want to
> limit the "infiniteness" a little somehow?

It happens in ipcp_vr_lattice::meet_with_1, because we have a lot more 
sub-ranges to union.  The latest numbers are 6.6%, and as I said I've 
already improved ipa-cp by the an equal amount, so we're good :).

The infiniteness is already capped.  We start at 3 sub-ranges, and grow 
up to 255.  I suppose if this is a problem, we could write a custom 
Value_Range temporary for IPA to fit specific needs, but I'd really like 
to avoid such special casing.

> 
> Also, jump functions live for a long time, have you looked at how memory
> hungry they become?  I hope that the hashing would be good at preventing
> any issues.

See my previous mail on memory usage.

Aldy

Re: [PATCH] Implement ipa_vr hashing.

[Aldy Hernandez]

On 5/29/23 16:51, Martin Jambor wrote:
> Hi,
> 
> On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
>> Implement hashing for ipa_vr.  When all is said and done, all these
>> patches incurr a 7.64% slowdown for ipa-cp, with is entirely covered by
>> the similar 7% increase in this area last week.  So we get type agnostic
>> ranges with "infinite" range precision close to free.
> 
> Do you know why/where this slow-down happens?  Do we perhaps want to
> limit the "infiniteness" a little somehow?

I addressed the slow down in another mail.

> 
> Also, jump functions live for a long time, have you looked at how memory
> hungry they become?  I hope that the hashing would be good at preventing
> any issues.

On a side-note, the caching does help.  On a (mistaken) hunch, I had
played around with removing caching for everything but UNDEFINED/VARYING 
and zero/nonzero to simplify things, but the cache hit ratio was still 
surprisingly high (+80%).  So good job there :-).

> 
> Generally, I think I OK with the patches if the impact on memory is not
> too bad, though I guess they depend on the one I looked at last week, so
> we may focus on that one first.

I'm not sure whether this was an OK for the other patches, given you 
approved the first patch, so I'll hold off until you give the go-ahead.

Thanks.
Aldy

Re: [PATCH] Convert ipa_jump_func to use ipa_vr instead of a value_range.

[Aldy Hernandez]

PING

On Mon, May 22, 2023 at 8:56 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> This patch converts the ipa_jump_func code to use the type agnostic
> ipa_vr suitable for GC instead of value_range which is integer specific.
>
> I've disabled the range cacheing to simplify the patch for review, but
> it is handled in the next patch in the series.
>
> OK?
>
> gcc/ChangeLog:
>
>         * ipa-cp.cc (ipa_vr_operation_and_type_effects): New.
>         * ipa-prop.cc (ipa_get_value_range): Adjust for ipa_vr.
>         (ipa_set_jfunc_vr): Take a range.
>         (ipa_compute_jump_functions_for_edge): Pass range to
>         ipa_set_jfunc_vr.
>         (ipa_write_jump_function): Call streamer write helper.
>         (ipa_read_jump_function): Call streamer read helper.
>         * ipa-prop.h (class ipa_vr): Change m_vr to an ipa_vr.
> ---
>  gcc/ipa-cp.cc   | 15 +++++++++++
>  gcc/ipa-prop.cc | 70 ++++++++++++++++++-------------------------------
>  gcc/ipa-prop.h  |  5 +++-
>  3 files changed, 44 insertions(+), 46 deletions(-)
>
> diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
> index bdbc2184b5f..03273666ea2 100644
> --- a/gcc/ipa-cp.cc
> +++ b/gcc/ipa-cp.cc
> @@ -1928,6 +1928,21 @@ ipa_vr_operation_and_type_effects (vrange &dst_vr,
>           && !dst_vr.undefined_p ());
>  }
>
> +/* Same as above, but the SRC_VR argument is an IPA_VR which must
> +   first be extracted onto a vrange.  */
> +
> +static bool
> +ipa_vr_operation_and_type_effects (vrange &dst_vr,
> +                                  const ipa_vr &src_vr,
> +                                  enum tree_code operation,
> +                                  tree dst_type, tree src_type)
> +{
> +  Value_Range tmp;
> +  src_vr.get_vrange (tmp);
> +  return ipa_vr_operation_and_type_effects (dst_vr, tmp, operation,
> +                                           dst_type, src_type);
> +}
> +
>  /* Determine range of JFUNC given that INFO describes the caller node or
>     the one it is inlined to, CS is the call graph edge corresponding to JFUNC
>     and PARM_TYPE of the parameter.  */
> diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
> index bbfe0f8aa45..c46a89f1b49 100644
> --- a/gcc/ipa-prop.cc
> +++ b/gcc/ipa-prop.cc
> @@ -2287,9 +2287,10 @@ ipa_set_jfunc_bits (ipa_jump_func *jf, const widest_int &value,
>  /* Return a pointer to a value_range just like *TMP, but either find it in
>     ipa_vr_hash_table or allocate it in GC memory.  TMP->equiv must be NULL.  */
>
> -static value_range *
> -ipa_get_value_range (value_range *tmp)
> +static ipa_vr *
> +ipa_get_value_range (const vrange &tmp)
>  {
> +  /* FIXME: Add hashing support.
>    value_range **slot = ipa_vr_hash_table->find_slot (tmp, INSERT);
>    if (*slot)
>      return *slot;
> @@ -2297,40 +2298,27 @@ ipa_get_value_range (value_range *tmp)
>    value_range *vr = new (ggc_alloc<value_range> ()) value_range;
>    *vr = *tmp;
>    *slot = vr;
> +  */
> +  ipa_vr *vr = new (ggc_alloc<ipa_vr> ()) ipa_vr (tmp);
>
>    return vr;
>  }
>
> -/* Return a pointer to a value range consisting of TYPE, MIN, MAX and an empty
> -   equiv set. Use hash table in order to avoid creating multiple same copies of
> -   value_ranges.  */
> -
> -static value_range *
> -ipa_get_value_range (enum value_range_kind kind, tree min, tree max)
> -{
> -  value_range tmp (TREE_TYPE (min),
> -                  wi::to_wide (min), wi::to_wide (max), kind);
> -  return ipa_get_value_range (&tmp);
> -}
> -
> -/* Assign to JF a pointer to a value_range structure with TYPE, MIN and MAX and
> -   a NULL equiv bitmap.  Use hash table in order to avoid creating multiple
> -   same value_range structures.  */
> +/* Assign to JF a pointer to a value_range just like TMP but either fetch a
> +   copy from ipa_vr_hash_table or allocate a new on in GC memory.  */
>
>  static void
> -ipa_set_jfunc_vr (ipa_jump_func *jf, enum value_range_kind type,
> -                 tree min, tree max)
> +ipa_set_jfunc_vr (ipa_jump_func *jf, const vrange &tmp)
>  {
> -  jf->m_vr = ipa_get_value_range (type, min, max);
> +  jf->m_vr = ipa_get_value_range (tmp);
>  }
>
> -/* Assign to JF a pointer to a value_range just like TMP but either fetch a
> -   copy from ipa_vr_hash_table or allocate a new on in GC memory.  */
> -
>  static void
> -ipa_set_jfunc_vr (ipa_jump_func *jf, value_range *tmp)
> +ipa_set_jfunc_vr (ipa_jump_func *jf, const ipa_vr &vr)
>  {
> -  jf->m_vr = ipa_get_value_range (tmp);
> +  Value_Range tmp;
> +  vr.get_vrange (tmp);
> +  ipa_set_jfunc_vr (jf, tmp);
>  }
>
>  /* Compute jump function for all arguments of callsite CS and insert the
> @@ -2392,8 +2380,8 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>
>           if (addr_nonzero)
>             {
> -             tree z = build_int_cst (TREE_TYPE (arg), 0);
> -             ipa_set_jfunc_vr (jfunc, VR_ANTI_RANGE, z, z);
> +             vr.set_nonzero (TREE_TYPE (arg));
> +             ipa_set_jfunc_vr (jfunc, vr);
>             }
>           else
>             gcc_assert (!jfunc->m_vr);
> @@ -2412,7 +2400,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>               value_range resvr = vr;
>               range_cast (resvr, param_type);
>               if (!resvr.undefined_p () && !resvr.varying_p ())
> -               ipa_set_jfunc_vr (jfunc, &resvr);
> +               ipa_set_jfunc_vr (jfunc, resvr);
>               else
>                 gcc_assert (!jfunc->m_vr);
>             }
> @@ -4864,16 +4852,12 @@ ipa_write_jump_function (struct output_block *ob,
>        streamer_write_widest_int (ob, jump_func->bits->value);
>        streamer_write_widest_int (ob, jump_func->bits->mask);
>      }
> -  bp_pack_value (&bp, !!jump_func->m_vr, 1);
> -  streamer_write_bitpack (&bp);
>    if (jump_func->m_vr)
> +    jump_func->m_vr->streamer_write (ob);
> +  else
>      {
> -      tree min, max;
> -      value_range_kind kind = get_legacy_range (*jump_func->m_vr, min, max);
> -      streamer_write_enum (ob->main_stream, value_rang_type,
> -                          VR_LAST, kind);
> -      stream_write_tree (ob, min, true);
> -      stream_write_tree (ob, max, true);
> +      bp_pack_value (&bp, false, 1);
> +      streamer_write_bitpack (&bp);
>      }
>  }
>
> @@ -5001,21 +4985,17 @@ ipa_read_jump_function (class lto_input_block *ib,
>        widest_int value = streamer_read_widest_int (ib);
>        widest_int mask = streamer_read_widest_int (ib);
>        if (prevails)
> -        ipa_set_jfunc_bits (jump_func, value, mask);
> +       ipa_set_jfunc_bits (jump_func, value, mask);
>      }
>    else
>      jump_func->bits = NULL;
>
> -  struct bitpack_d vr_bp = streamer_read_bitpack (ib);
> -  bool vr_known = bp_unpack_value (&vr_bp, 1);
> -  if (vr_known)
> +  ipa_vr vr;
> +  vr.streamer_read (ib, data_in);
> +  if (vr.known_p ())
>      {
> -      enum value_range_kind type = streamer_read_enum (ib, value_range_kind,
> -                                                      VR_LAST);
> -      tree min = stream_read_tree (ib, data_in);
> -      tree max = stream_read_tree (ib, data_in);
>        if (prevails)
> -        ipa_set_jfunc_vr (jump_func, type, min, max);
> +       ipa_set_jfunc_vr (jump_func, vr);
>      }
>    else
>      jump_func->m_vr = NULL;
> diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
> index f87e8a596c1..33fad228913 100644
> --- a/gcc/ipa-prop.h
> +++ b/gcc/ipa-prop.h
> @@ -325,6 +325,9 @@ private:
>    friend void gt_pch_nx (struct ipa_vr &);
>    friend void gt_ggc_mx (struct ipa_vr &);
>    friend void gt_pch_nx (struct ipa_vr *, gt_pointer_operator, void *);
> +  friend void gt_ggc_mx_ipa_vr (void *);
> +  friend void gt_pch_nx_ipa_vr (void*);
> +  friend void gt_pch_p_6ipa_vr(void*, void*, gt_pointer_operator, void*);
>
>    vrange_storage *m_storage;
>    // vrange_storage is typeless, but we need to know what type of
> @@ -351,7 +354,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.  */
> -  value_range *m_vr;
> +  ipa_vr *m_vr;
>
>    enum jump_func_type type;
>    /* Represents a value of a jump function.  pass_through is used only in jump
> --
> 2.40.1
>

Re: [PATCH] Convert remaining uses of value_range in ipa-*.cc to Value_Range.

[Aldy Hernandez]

PING

On Mon, May 22, 2023 at 8:56 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> Minor cleanups to get rid of value_range in IPA.  There's only one left,
> but it's in the switch code which is integer specific.
>
> OK?
>
> gcc/ChangeLog:
>
>         * ipa-cp.cc (decide_whether_version_node): Adjust comment.
>         * ipa-fnsummary.cc (evaluate_conditions_for_known_args): Adjust
>         for Value_Range.
>         (set_switch_stmt_execution_predicate): Same.
>         * ipa-prop.cc (ipa_compute_jump_functions_for_edge): Same.
> ---
>  gcc/ipa-cp.cc        |  3 +--
>  gcc/ipa-fnsummary.cc | 22 ++++++++++++++--------
>  gcc/ipa-prop.cc      |  9 +++------
>  3 files changed, 18 insertions(+), 16 deletions(-)
>
> diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
> index 03273666ea2..2e64415096e 100644
> --- a/gcc/ipa-cp.cc
> +++ b/gcc/ipa-cp.cc
> @@ -6287,8 +6287,7 @@ decide_whether_version_node (struct cgraph_node *node)
>             {
>               /* If some values generated for self-recursive calls with
>                  arithmetic jump functions fall outside of the known
> -                value_range for the parameter, we can skip them.  VR interface
> -                supports this only for integers now.  */
> +                range for the parameter, we can skip them.  */
>               if (TREE_CODE (val->value) == INTEGER_CST
>                   && !plats->m_value_range.bottom_p ()
>                   && !ipa_range_contains_p (plats->m_value_range.m_vr,
> diff --git a/gcc/ipa-fnsummary.cc b/gcc/ipa-fnsummary.cc
> index 0474af8991e..1ce8501fe85 100644
> --- a/gcc/ipa-fnsummary.cc
> +++ b/gcc/ipa-fnsummary.cc
> @@ -488,19 +488,20 @@ evaluate_conditions_for_known_args (struct cgraph_node *node,
>                   if (vr.varying_p () || vr.undefined_p ())
>                     break;
>
> -                 value_range res;
> +                 Value_Range res (op->type);
>                   if (!op->val[0])
>                     {
> +                     Value_Range varying (op->type);
> +                     varying.set_varying (op->type);
>                       range_op_handler handler (op->code, op->type);
>                       if (!handler
>                           || !res.supports_type_p (op->type)
> -                         || !handler.fold_range (res, op->type, vr,
> -                                                 value_range (op->type)))
> +                         || !handler.fold_range (res, op->type, vr, varying))
>                         res.set_varying (op->type);
>                     }
>                   else if (!op->val[1])
>                     {
> -                     value_range op0;
> +                     Value_Range op0 (op->type);
>                       range_op_handler handler (op->code, op->type);
>
>                       ipa_range_set_and_normalize (op0, op->val[0]);
> @@ -518,14 +519,14 @@ evaluate_conditions_for_known_args (struct cgraph_node *node,
>                 }
>               if (!vr.varying_p () && !vr.undefined_p ())
>                 {
> -                 value_range res;
> -                 value_range val_vr;
> +                 int_range<2> res;
> +                 Value_Range val_vr (TREE_TYPE (c->val));
>                   range_op_handler handler (c->code, boolean_type_node);
>
>                   ipa_range_set_and_normalize (val_vr, c->val);
>
>                   if (!handler
> -                     || !res.supports_type_p (boolean_type_node)
> +                     || !val_vr.supports_type_p (TREE_TYPE (c->val))
>                       || !handler.fold_range (res, boolean_type_node, vr, val_vr))
>                     res.set_varying (boolean_type_node);
>
> @@ -1687,12 +1688,17 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi,
>    int bound_limit = opt_for_fn (fbi->node->decl,
>                                 param_ipa_max_switch_predicate_bounds);
>    int bound_count = 0;
> -  value_range vr;
> +  // This can safely be an integer range, as switches can only hold
> +  // integers.
> +  int_range<2> vr;
>
>    get_range_query (cfun)->range_of_expr (vr, op);
>    if (vr.undefined_p ())
>      vr.set_varying (TREE_TYPE (op));
>    tree vr_min, vr_max;
> +  // ?? This entire function could use a rewrite to use the irange
> +  // API, instead of trying to recreate its intersection/union logic.
> +  // Any use of get_legacy_range() is a serious code smell.
>    value_range_kind vr_type = get_legacy_range (vr, vr_min, vr_max);
>    wide_int vr_wmin = wi::to_wide (vr_min);
>    wide_int vr_wmax = wi::to_wide (vr_max);
> diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
> index 6383bc11e0a..5f9e6dbbff2 100644
> --- a/gcc/ipa-prop.cc
> +++ b/gcc/ipa-prop.cc
> @@ -2348,7 +2348,6 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>    gcall *call = cs->call_stmt;
>    int n, arg_num = gimple_call_num_args (call);
>    bool useful_context = false;
> -  value_range vr;
>
>    if (arg_num == 0 || args->jump_functions)
>      return;
> @@ -2379,6 +2378,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>             useful_context = true;
>         }
>
> +      Value_Range vr (TREE_TYPE (arg));
>        if (POINTER_TYPE_P (TREE_TYPE (arg)))
>         {
>           bool addr_nonzero = false;
> @@ -2404,14 +2404,11 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>         {
>           if (TREE_CODE (arg) == SSA_NAME
>               && param_type
> -             /* Limit the ranger query to integral types as the rest
> -                of this file uses value_range's, which only hold
> -                integers and pointers.  */
> -             && irange::supports_p (TREE_TYPE (arg))
> +             && Value_Range::supports_type_p (TREE_TYPE (arg))
>               && get_range_query (cfun)->range_of_expr (vr, arg)
>               && !vr.undefined_p ())
>             {
> -             value_range resvr = vr;
> +             Value_Range resvr (vr);
>               range_cast (resvr, param_type);
>               if (!resvr.undefined_p () && !resvr.varying_p ())
>                 ipa_set_jfunc_vr (jfunc, resvr);
> --
> 2.40.1
>

Re: [PATCH] Implement ipa_vr hashing.

[Aldy Hernandez]

PING

On Sat, Jun 10, 2023 at 10:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 5/29/23 16:51, Martin Jambor wrote:
> > Hi,
> >
> > On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
> >> Implement hashing for ipa_vr.  When all is said and done, all these
> >> patches incurr a 7.64% slowdown for ipa-cp, with is entirely covered by
> >> the similar 7% increase in this area last week.  So we get type agnostic
> >> ranges with "infinite" range precision close to free.
> >
> > Do you know why/where this slow-down happens?  Do we perhaps want to
> > limit the "infiniteness" a little somehow?
>
> I addressed the slow down in another mail.
>
> >
> > Also, jump functions live for a long time, have you looked at how memory
> > hungry they become?  I hope that the hashing would be good at preventing
> > any issues.
>
> On a side-note, the caching does help.  On a (mistaken) hunch, I had
> played around with removing caching for everything but UNDEFINED/VARYING
> and zero/nonzero to simplify things, but the cache hit ratio was still
> surprisingly high (+80%).  So good job there :-).
>
> >
> > Generally, I think I OK with the patches if the impact on memory is not
> > too bad, though I guess they depend on the one I looked at last week, so
> > we may focus on that one first.
>
> I'm not sure whether this was an OK for the other patches, given you
> approved the first patch, so I'll hold off until you give the go-ahead.
>
> Thanks.
> Aldy

Re: [PATCH] Convert remaining uses of value_range in ipa-*.cc to Value_Range.

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 6721 bytes --]

Ping*2

On Wed, Jun 14, 2023, 14:10 Aldy Hernandez <aldyh@redhat.com> wrote:

> PING
>
> On Mon, May 22, 2023 at 8:56 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > Minor cleanups to get rid of value_range in IPA.  There's only one left,
> > but it's in the switch code which is integer specific.
> >
> > OK?
> >
> > gcc/ChangeLog:
> >
> >         * ipa-cp.cc (decide_whether_version_node): Adjust comment.
> >         * ipa-fnsummary.cc (evaluate_conditions_for_known_args): Adjust
> >         for Value_Range.
> >         (set_switch_stmt_execution_predicate): Same.
> >         * ipa-prop.cc (ipa_compute_jump_functions_for_edge): Same.
> > ---
> >  gcc/ipa-cp.cc        |  3 +--
> >  gcc/ipa-fnsummary.cc | 22 ++++++++++++++--------
> >  gcc/ipa-prop.cc      |  9 +++------
> >  3 files changed, 18 insertions(+), 16 deletions(-)
> >
> > diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
> > index 03273666ea2..2e64415096e 100644
> > --- a/gcc/ipa-cp.cc
> > +++ b/gcc/ipa-cp.cc
> > @@ -6287,8 +6287,7 @@ decide_whether_version_node (struct cgraph_node
> *node)
> >             {
> >               /* If some values generated for self-recursive calls with
> >                  arithmetic jump functions fall outside of the known
> > -                value_range for the parameter, we can skip them.  VR
> interface
> > -                supports this only for integers now.  */
> > +                range for the parameter, we can skip them.  */
> >               if (TREE_CODE (val->value) == INTEGER_CST
> >                   && !plats->m_value_range.bottom_p ()
> >                   && !ipa_range_contains_p (plats->m_value_range.m_vr,
> > diff --git a/gcc/ipa-fnsummary.cc b/gcc/ipa-fnsummary.cc
> > index 0474af8991e..1ce8501fe85 100644
> > --- a/gcc/ipa-fnsummary.cc
> > +++ b/gcc/ipa-fnsummary.cc
> > @@ -488,19 +488,20 @@ evaluate_conditions_for_known_args (struct
> cgraph_node *node,
> >                   if (vr.varying_p () || vr.undefined_p ())
> >                     break;
> >
> > -                 value_range res;
> > +                 Value_Range res (op->type);
> >                   if (!op->val[0])
> >                     {
> > +                     Value_Range varying (op->type);
> > +                     varying.set_varying (op->type);
> >                       range_op_handler handler (op->code, op->type);
> >                       if (!handler
> >                           || !res.supports_type_p (op->type)
> > -                         || !handler.fold_range (res, op->type, vr,
> > -                                                 value_range
> (op->type)))
> > +                         || !handler.fold_range (res, op->type, vr,
> varying))
> >                         res.set_varying (op->type);
> >                     }
> >                   else if (!op->val[1])
> >                     {
> > -                     value_range op0;
> > +                     Value_Range op0 (op->type);
> >                       range_op_handler handler (op->code, op->type);
> >
> >                       ipa_range_set_and_normalize (op0, op->val[0]);
> > @@ -518,14 +519,14 @@ evaluate_conditions_for_known_args (struct
> cgraph_node *node,
> >                 }
> >               if (!vr.varying_p () && !vr.undefined_p ())
> >                 {
> > -                 value_range res;
> > -                 value_range val_vr;
> > +                 int_range<2> res;
> > +                 Value_Range val_vr (TREE_TYPE (c->val));
> >                   range_op_handler handler (c->code, boolean_type_node);
> >
> >                   ipa_range_set_and_normalize (val_vr, c->val);
> >
> >                   if (!handler
> > -                     || !res.supports_type_p (boolean_type_node)
> > +                     || !val_vr.supports_type_p (TREE_TYPE (c->val))
> >                       || !handler.fold_range (res, boolean_type_node,
> vr, val_vr))
> >                     res.set_varying (boolean_type_node);
> >
> > @@ -1687,12 +1688,17 @@ set_switch_stmt_execution_predicate (struct
> ipa_func_body_info *fbi,
> >    int bound_limit = opt_for_fn (fbi->node->decl,
> >                                 param_ipa_max_switch_predicate_bounds);
> >    int bound_count = 0;
> > -  value_range vr;
> > +  // This can safely be an integer range, as switches can only hold
> > +  // integers.
> > +  int_range<2> vr;
> >
> >    get_range_query (cfun)->range_of_expr (vr, op);
> >    if (vr.undefined_p ())
> >      vr.set_varying (TREE_TYPE (op));
> >    tree vr_min, vr_max;
> > +  // ?? This entire function could use a rewrite to use the irange
> > +  // API, instead of trying to recreate its intersection/union logic.
> > +  // Any use of get_legacy_range() is a serious code smell.
> >    value_range_kind vr_type = get_legacy_range (vr, vr_min, vr_max);
> >    wide_int vr_wmin = wi::to_wide (vr_min);
> >    wide_int vr_wmax = wi::to_wide (vr_max);
> > diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
> > index 6383bc11e0a..5f9e6dbbff2 100644
> > --- a/gcc/ipa-prop.cc
> > +++ b/gcc/ipa-prop.cc
> > @@ -2348,7 +2348,6 @@ ipa_compute_jump_functions_for_edge (struct
> ipa_func_body_info *fbi,
> >    gcall *call = cs->call_stmt;
> >    int n, arg_num = gimple_call_num_args (call);
> >    bool useful_context = false;
> > -  value_range vr;
> >
> >    if (arg_num == 0 || args->jump_functions)
> >      return;
> > @@ -2379,6 +2378,7 @@ ipa_compute_jump_functions_for_edge (struct
> ipa_func_body_info *fbi,
> >             useful_context = true;
> >         }
> >
> > +      Value_Range vr (TREE_TYPE (arg));
> >        if (POINTER_TYPE_P (TREE_TYPE (arg)))
> >         {
> >           bool addr_nonzero = false;
> > @@ -2404,14 +2404,11 @@ ipa_compute_jump_functions_for_edge (struct
> ipa_func_body_info *fbi,
> >         {
> >           if (TREE_CODE (arg) == SSA_NAME
> >               && param_type
> > -             /* Limit the ranger query to integral types as the rest
> > -                of this file uses value_range's, which only hold
> > -                integers and pointers.  */
> > -             && irange::supports_p (TREE_TYPE (arg))
> > +             && Value_Range::supports_type_p (TREE_TYPE (arg))
> >               && get_range_query (cfun)->range_of_expr (vr, arg)
> >               && !vr.undefined_p ())
> >             {
> > -             value_range resvr = vr;
> > +             Value_Range resvr (vr);
> >               range_cast (resvr, param_type);
> >               if (!resvr.undefined_p () && !resvr.varying_p ())
> >                 ipa_set_jfunc_vr (jfunc, resvr);
> > --
> > 2.40.1
> >
>

Re: [PATCH] Convert ipa_jump_func to use ipa_vr instead of a value_range.

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 9085 bytes --]

Ping*2

On Wed, Jun 14, 2023, 14:09 Aldy Hernandez <aldyh@redhat.com> wrote:

> PING
>
> On Mon, May 22, 2023 at 8:56 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > This patch converts the ipa_jump_func code to use the type agnostic
> > ipa_vr suitable for GC instead of value_range which is integer specific.
> >
> > I've disabled the range cacheing to simplify the patch for review, but
> > it is handled in the next patch in the series.
> >
> > OK?
> >
> > gcc/ChangeLog:
> >
> >         * ipa-cp.cc (ipa_vr_operation_and_type_effects): New.
> >         * ipa-prop.cc (ipa_get_value_range): Adjust for ipa_vr.
> >         (ipa_set_jfunc_vr): Take a range.
> >         (ipa_compute_jump_functions_for_edge): Pass range to
> >         ipa_set_jfunc_vr.
> >         (ipa_write_jump_function): Call streamer write helper.
> >         (ipa_read_jump_function): Call streamer read helper.
> >         * ipa-prop.h (class ipa_vr): Change m_vr to an ipa_vr.
> > ---
> >  gcc/ipa-cp.cc   | 15 +++++++++++
> >  gcc/ipa-prop.cc | 70 ++++++++++++++++++-------------------------------
> >  gcc/ipa-prop.h  |  5 +++-
> >  3 files changed, 44 insertions(+), 46 deletions(-)
> >
> > diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
> > index bdbc2184b5f..03273666ea2 100644
> > --- a/gcc/ipa-cp.cc
> > +++ b/gcc/ipa-cp.cc
> > @@ -1928,6 +1928,21 @@ ipa_vr_operation_and_type_effects (vrange &dst_vr,
> >           && !dst_vr.undefined_p ());
> >  }
> >
> > +/* Same as above, but the SRC_VR argument is an IPA_VR which must
> > +   first be extracted onto a vrange.  */
> > +
> > +static bool
> > +ipa_vr_operation_and_type_effects (vrange &dst_vr,
> > +                                  const ipa_vr &src_vr,
> > +                                  enum tree_code operation,
> > +                                  tree dst_type, tree src_type)
> > +{
> > +  Value_Range tmp;
> > +  src_vr.get_vrange (tmp);
> > +  return ipa_vr_operation_and_type_effects (dst_vr, tmp, operation,
> > +                                           dst_type, src_type);
> > +}
> > +
> >  /* Determine range of JFUNC given that INFO describes the caller node or
> >     the one it is inlined to, CS is the call graph edge corresponding to
> JFUNC
> >     and PARM_TYPE of the parameter.  */
> > diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
> > index bbfe0f8aa45..c46a89f1b49 100644
> > --- a/gcc/ipa-prop.cc
> > +++ b/gcc/ipa-prop.cc
> > @@ -2287,9 +2287,10 @@ ipa_set_jfunc_bits (ipa_jump_func *jf, const
> widest_int &value,
> >  /* Return a pointer to a value_range just like *TMP, but either find it
> in
> >     ipa_vr_hash_table or allocate it in GC memory.  TMP->equiv must be
> NULL.  */
> >
> > -static value_range *
> > -ipa_get_value_range (value_range *tmp)
> > +static ipa_vr *
> > +ipa_get_value_range (const vrange &tmp)
> >  {
> > +  /* FIXME: Add hashing support.
> >    value_range **slot = ipa_vr_hash_table->find_slot (tmp, INSERT);
> >    if (*slot)
> >      return *slot;
> > @@ -2297,40 +2298,27 @@ ipa_get_value_range (value_range *tmp)
> >    value_range *vr = new (ggc_alloc<value_range> ()) value_range;
> >    *vr = *tmp;
> >    *slot = vr;
> > +  */
> > +  ipa_vr *vr = new (ggc_alloc<ipa_vr> ()) ipa_vr (tmp);
> >
> >    return vr;
> >  }
> >
> > -/* Return a pointer to a value range consisting of TYPE, MIN, MAX and
> an empty
> > -   equiv set. Use hash table in order to avoid creating multiple same
> copies of
> > -   value_ranges.  */
> > -
> > -static value_range *
> > -ipa_get_value_range (enum value_range_kind kind, tree min, tree max)
> > -{
> > -  value_range tmp (TREE_TYPE (min),
> > -                  wi::to_wide (min), wi::to_wide (max), kind);
> > -  return ipa_get_value_range (&tmp);
> > -}
> > -
> > -/* Assign to JF a pointer to a value_range structure with TYPE, MIN and
> MAX and
> > -   a NULL equiv bitmap.  Use hash table in order to avoid creating
> multiple
> > -   same value_range structures.  */
> > +/* Assign to JF a pointer to a value_range just like TMP but either
> fetch a
> > +   copy from ipa_vr_hash_table or allocate a new on in GC memory.  */
> >
> >  static void
> > -ipa_set_jfunc_vr (ipa_jump_func *jf, enum value_range_kind type,
> > -                 tree min, tree max)
> > +ipa_set_jfunc_vr (ipa_jump_func *jf, const vrange &tmp)
> >  {
> > -  jf->m_vr = ipa_get_value_range (type, min, max);
> > +  jf->m_vr = ipa_get_value_range (tmp);
> >  }
> >
> > -/* Assign to JF a pointer to a value_range just like TMP but either
> fetch a
> > -   copy from ipa_vr_hash_table or allocate a new on in GC memory.  */
> > -
> >  static void
> > -ipa_set_jfunc_vr (ipa_jump_func *jf, value_range *tmp)
> > +ipa_set_jfunc_vr (ipa_jump_func *jf, const ipa_vr &vr)
> >  {
> > -  jf->m_vr = ipa_get_value_range (tmp);
> > +  Value_Range tmp;
> > +  vr.get_vrange (tmp);
> > +  ipa_set_jfunc_vr (jf, tmp);
> >  }
> >
> >  /* Compute jump function for all arguments of callsite CS and insert the
> > @@ -2392,8 +2380,8 @@ ipa_compute_jump_functions_for_edge (struct
> ipa_func_body_info *fbi,
> >
> >           if (addr_nonzero)
> >             {
> > -             tree z = build_int_cst (TREE_TYPE (arg), 0);
> > -             ipa_set_jfunc_vr (jfunc, VR_ANTI_RANGE, z, z);
> > +             vr.set_nonzero (TREE_TYPE (arg));
> > +             ipa_set_jfunc_vr (jfunc, vr);
> >             }
> >           else
> >             gcc_assert (!jfunc->m_vr);
> > @@ -2412,7 +2400,7 @@ ipa_compute_jump_functions_for_edge (struct
> ipa_func_body_info *fbi,
> >               value_range resvr = vr;
> >               range_cast (resvr, param_type);
> >               if (!resvr.undefined_p () && !resvr.varying_p ())
> > -               ipa_set_jfunc_vr (jfunc, &resvr);
> > +               ipa_set_jfunc_vr (jfunc, resvr);
> >               else
> >                 gcc_assert (!jfunc->m_vr);
> >             }
> > @@ -4864,16 +4852,12 @@ ipa_write_jump_function (struct output_block *ob,
> >        streamer_write_widest_int (ob, jump_func->bits->value);
> >        streamer_write_widest_int (ob, jump_func->bits->mask);
> >      }
> > -  bp_pack_value (&bp, !!jump_func->m_vr, 1);
> > -  streamer_write_bitpack (&bp);
> >    if (jump_func->m_vr)
> > +    jump_func->m_vr->streamer_write (ob);
> > +  else
> >      {
> > -      tree min, max;
> > -      value_range_kind kind = get_legacy_range (*jump_func->m_vr, min,
> max);
> > -      streamer_write_enum (ob->main_stream, value_rang_type,
> > -                          VR_LAST, kind);
> > -      stream_write_tree (ob, min, true);
> > -      stream_write_tree (ob, max, true);
> > +      bp_pack_value (&bp, false, 1);
> > +      streamer_write_bitpack (&bp);
> >      }
> >  }
> >
> > @@ -5001,21 +4985,17 @@ ipa_read_jump_function (class lto_input_block
> *ib,
> >        widest_int value = streamer_read_widest_int (ib);
> >        widest_int mask = streamer_read_widest_int (ib);
> >        if (prevails)
> > -        ipa_set_jfunc_bits (jump_func, value, mask);
> > +       ipa_set_jfunc_bits (jump_func, value, mask);
> >      }
> >    else
> >      jump_func->bits = NULL;
> >
> > -  struct bitpack_d vr_bp = streamer_read_bitpack (ib);
> > -  bool vr_known = bp_unpack_value (&vr_bp, 1);
> > -  if (vr_known)
> > +  ipa_vr vr;
> > +  vr.streamer_read (ib, data_in);
> > +  if (vr.known_p ())
> >      {
> > -      enum value_range_kind type = streamer_read_enum (ib,
> value_range_kind,
> > -                                                      VR_LAST);
> > -      tree min = stream_read_tree (ib, data_in);
> > -      tree max = stream_read_tree (ib, data_in);
> >        if (prevails)
> > -        ipa_set_jfunc_vr (jump_func, type, min, max);
> > +       ipa_set_jfunc_vr (jump_func, vr);
> >      }
> >    else
> >      jump_func->m_vr = NULL;
> > diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
> > index f87e8a596c1..33fad228913 100644
> > --- a/gcc/ipa-prop.h
> > +++ b/gcc/ipa-prop.h
> > @@ -325,6 +325,9 @@ private:
> >    friend void gt_pch_nx (struct ipa_vr &);
> >    friend void gt_ggc_mx (struct ipa_vr &);
> >    friend void gt_pch_nx (struct ipa_vr *, gt_pointer_operator, void *);
> > +  friend void gt_ggc_mx_ipa_vr (void *);
> > +  friend void gt_pch_nx_ipa_vr (void*);
> > +  friend void gt_pch_p_6ipa_vr(void*, void*, gt_pointer_operator,
> void*);
> >
> >    vrange_storage *m_storage;
> >    // vrange_storage is typeless, but we need to know what type of
> > @@ -351,7 +354,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.  */
> > -  value_range *m_vr;
> > +  ipa_vr *m_vr;
> >
> >    enum jump_func_type type;
> >    /* Represents a value of a jump function.  pass_through is used only
> in jump
> > --
> > 2.40.1
> >
>

Re: [PATCH] Implement ipa_vr hashing.

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 1691 bytes --]

Ping*2

On Wed, Jun 14, 2023, 14:11 Aldy Hernandez <aldyh@redhat.com> wrote:

> PING
>
> On Sat, Jun 10, 2023 at 10:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> >
> >
> > On 5/29/23 16:51, Martin Jambor wrote:
> > > Hi,
> > >
> > > On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
> > >> Implement hashing for ipa_vr.  When all is said and done, all these
> > >> patches incurr a 7.64% slowdown for ipa-cp, with is entirely covered
> by
> > >> the similar 7% increase in this area last week.  So we get type
> agnostic
> > >> ranges with "infinite" range precision close to free.
> > >
> > > Do you know why/where this slow-down happens?  Do we perhaps want to
> > > limit the "infiniteness" a little somehow?
> >
> > I addressed the slow down in another mail.
> >
> > >
> > > Also, jump functions live for a long time, have you looked at how
> memory
> > > hungry they become?  I hope that the hashing would be good at
> preventing
> > > any issues.
> >
> > On a side-note, the caching does help.  On a (mistaken) hunch, I had
> > played around with removing caching for everything but UNDEFINED/VARYING
> > and zero/nonzero to simplify things, but the cache hit ratio was still
> > surprisingly high (+80%).  So good job there :-).
> >
> > >
> > > Generally, I think I OK with the patches if the impact on memory is not
> > > too bad, though I guess they depend on the one I looked at last week,
> so
> > > we may focus on that one first.
> >
> > I'm not sure whether this was an OK for the other patches, given you
> > approved the first patch, so I'll hold off until you give the go-ahead.
> >
> > Thanks.
> > Aldy
>

Re: [PATCH] Implement ipa_vr hashing.

[Aldy Hernandez]

PING*3

On Thu, Jun 22, 2023 at 7:49 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> Ping*2
>
> On Wed, Jun 14, 2023, 14:11 Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>> PING
>>
>> On Sat, Jun 10, 2023 at 10:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>> >
>> >
>> >
>> > On 5/29/23 16:51, Martin Jambor wrote:
>> > > Hi,
>> > >
>> > > On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
>> > >> Implement hashing for ipa_vr.  When all is said and done, all these
>> > >> patches incurr a 7.64% slowdown for ipa-cp, with is entirely covered by
>> > >> the similar 7% increase in this area last week.  So we get type agnostic
>> > >> ranges with "infinite" range precision close to free.
>> > >
>> > > Do you know why/where this slow-down happens?  Do we perhaps want to
>> > > limit the "infiniteness" a little somehow?
>> >
>> > I addressed the slow down in another mail.
>> >
>> > >
>> > > Also, jump functions live for a long time, have you looked at how memory
>> > > hungry they become?  I hope that the hashing would be good at preventing
>> > > any issues.
>> >
>> > On a side-note, the caching does help.  On a (mistaken) hunch, I had
>> > played around with removing caching for everything but UNDEFINED/VARYING
>> > and zero/nonzero to simplify things, but the cache hit ratio was still
>> > surprisingly high (+80%).  So good job there :-).
>> >
>> > >
>> > > Generally, I think I OK with the patches if the impact on memory is not
>> > > too bad, though I guess they depend on the one I looked at last week, so
>> > > we may focus on that one first.
>> >
>> > I'm not sure whether this was an OK for the other patches, given you
>> > approved the first patch, so I'll hold off until you give the go-ahead.
>> >
>> > Thanks.
>> > Aldy

Re: [PATCH] Implement ipa_vr hashing.

[Aldy Hernandez]

Errr, sorry about this ping.  I was meant to re-ping my IPA patches
after 7 days, but just realized it had been only 4.  My bad.

Aldy

On Mon, Jun 26, 2023 at 11:22 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> PING*3
>
> On Thu, Jun 22, 2023 at 7:49 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > Ping*2
> >
> > On Wed, Jun 14, 2023, 14:11 Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >> PING
> >>
> >> On Sat, Jun 10, 2023 at 10:30 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >> >
> >> >
> >> >
> >> > On 5/29/23 16:51, Martin Jambor wrote:
> >> > > Hi,
> >> > >
> >> > > On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
> >> > >> Implement hashing for ipa_vr.  When all is said and done, all these
> >> > >> patches incurr a 7.64% slowdown for ipa-cp, with is entirely covered by
> >> > >> the similar 7% increase in this area last week.  So we get type agnostic
> >> > >> ranges with "infinite" range precision close to free.
> >> > >
> >> > > Do you know why/where this slow-down happens?  Do we perhaps want to
> >> > > limit the "infiniteness" a little somehow?
> >> >
> >> > I addressed the slow down in another mail.
> >> >
> >> > >
> >> > > Also, jump functions live for a long time, have you looked at how memory
> >> > > hungry they become?  I hope that the hashing would be good at preventing
> >> > > any issues.
> >> >
> >> > On a side-note, the caching does help.  On a (mistaken) hunch, I had
> >> > played around with removing caching for everything but UNDEFINED/VARYING
> >> > and zero/nonzero to simplify things, but the cache hit ratio was still
> >> > surprisingly high (+80%).  So good job there :-).
> >> >
> >> > >
> >> > > Generally, I think I OK with the patches if the impact on memory is not
> >> > > too bad, though I guess they depend on the one I looked at last week, so
> >> > > we may focus on that one first.
> >> >
> >> > I'm not sure whether this was an OK for the other patches, given you
> >> > approved the first patch, so I'll hold off until you give the go-ahead.
> >> >
> >> > Thanks.
> >> > Aldy

Re: [PATCH] Convert ipa_jump_func to use ipa_vr instead of a value_range.

[Martin Jambor]

Hi,

On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
> This patch converts the ipa_jump_func code to use the type agnostic
> ipa_vr suitable for GC instead of value_range which is integer specific.
>
> I've disabled the range cacheing to simplify the patch for review, but
> it is handled in the next patch in the series.
>
> OK?
>
> gcc/ChangeLog:
>
> 	* ipa-cp.cc (ipa_vr_operation_and_type_effects): New.
> 	* ipa-prop.cc (ipa_get_value_range): Adjust for ipa_vr.
> 	(ipa_set_jfunc_vr): Take a range.
> 	(ipa_compute_jump_functions_for_edge): Pass range to
> 	ipa_set_jfunc_vr.
> 	(ipa_write_jump_function): Call streamer write helper.
> 	(ipa_read_jump_function): Call streamer read helper.
> 	* ipa-prop.h (class ipa_vr): Change m_vr to an ipa_vr.

OK, thanks and sorry for the waiting, I've been unexpectedly traveling
last week.

Martin

> ---
>  gcc/ipa-cp.cc   | 15 +++++++++++
>  gcc/ipa-prop.cc | 70 ++++++++++++++++++-------------------------------
>  gcc/ipa-prop.h  |  5 +++-
>  3 files changed, 44 insertions(+), 46 deletions(-)
>
[...]

Re: [PATCH] Implement ipa_vr hashing.

[Martin Jambor]

Hi,

On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
> Implement hashing for ipa_vr.  When all is said and done, all these
> patches incurr a 7.64% slowdown for ipa-cp, with is entirely covered by
> the similar 7% increase in this area last week.  So we get type agnostic
> ranges with "infinite" range precision close to free.
>
> There is no change in overall compilation.
>
> OK?
>

One small request....

> gcc/ChangeLog:
>
> 	* ipa-prop.cc (struct ipa_vr_ggc_hash_traits): Adjust for use with
> 	ipa_vr instead of value_range.
> 	(gt_pch_nx): Same.
> 	(gt_ggc_mx): Same.
> 	(ipa_get_value_range): Same.
> 	* value-range.cc (gt_pch_nx): Move to ipa-prop.cc and adjust for
> 	ipa_vr.
> 	(gt_ggc_mx): Same.
> ---
>  gcc/ipa-prop.cc    | 76 +++++++++++++++++++++++++++-------------------
>  gcc/value-range.cc | 15 ---------
>  2 files changed, 45 insertions(+), 46 deletions(-)
>
> diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
> index c46a89f1b49..6383bc11e0a 100644
> --- a/gcc/ipa-prop.cc
> +++ b/gcc/ipa-prop.cc
> @@ -109,53 +109,53 @@ struct ipa_bit_ggc_hash_traits : public ggc_cache_remove <ipa_bits *>
>  /* Hash table for avoid repeated allocations of equal ipa_bits.  */
>  static GTY ((cache)) hash_table<ipa_bit_ggc_hash_traits> *ipa_bits_hash_table;
>  
> -/* Traits for a hash table for reusing value_ranges used for IPA.  Note that
> -   the equiv bitmap is not hashed and is expected to be NULL.  */
> +/* Traits for a hash table for reusing ranges.  */
>  
> -struct ipa_vr_ggc_hash_traits : public ggc_cache_remove <value_range *>
> +struct ipa_vr_ggc_hash_traits : public ggc_cache_remove <ipa_vr *>
>  {
> -  typedef value_range *value_type;
> -  typedef value_range *compare_type;
> +  typedef ipa_vr *value_type;
> +  typedef const vrange *compare_type;
>    static hashval_t
> -  hash (const value_range *p)
> +  hash (const ipa_vr *p)
>      {
> -      tree min, max;
> -      value_range_kind kind = get_legacy_range (*p, min, max);
> -      inchash::hash hstate (kind);
> -      inchash::add_expr (min, hstate);
> -      inchash::add_expr (max, hstate);
> +      // This never get called, except in the verification code, as
> +      // ipa_get_value_range() calculates the hash itself.  This
> +      // function is mostly here for completness' sake.
> +      Value_Range vr;
> +      p->get_vrange (vr);
> +      inchash::hash hstate;
> +      add_vrange (vr, hstate);
>        return hstate.end ();
>      }
>    static bool
> -  equal (const value_range *a, const value_range *b)
> +  equal (const ipa_vr *a, const vrange *b)
>      {
> -      return (types_compatible_p (a->type (), b->type ())
> -	      && *a == *b);
> +      return a->equal_p (*b);
>      }
>    static const bool empty_zero_p = true;
>    static void
> -  mark_empty (value_range *&p)
> +  mark_empty (ipa_vr *&p)
>      {
>        p = NULL;
>      }
>    static bool
> -  is_empty (const value_range *p)
> +  is_empty (const ipa_vr *p)
>      {
>        return p == NULL;
>      }
>    static bool
> -  is_deleted (const value_range *p)
> +  is_deleted (const ipa_vr *p)
>      {
> -      return p == reinterpret_cast<const value_range *> (1);
> +      return p == reinterpret_cast<const ipa_vr *> (1);
>      }
>    static void
> -  mark_deleted (value_range *&p)
> +  mark_deleted (ipa_vr *&p)
>      {
> -      p = reinterpret_cast<value_range *> (1);
> +      p = reinterpret_cast<ipa_vr *> (1);
>      }
>  };
>  
> -/* Hash table for avoid repeated allocations of equal value_ranges.  */
> +/* Hash table for avoid repeated allocations of equal ranges.  */
>  static GTY ((cache)) hash_table<ipa_vr_ggc_hash_traits> *ipa_vr_hash_table;
>  
>  /* Holders of ipa cgraph hooks: */
> @@ -265,6 +265,22 @@ ipa_vr::dump (FILE *out) const
>      fprintf (out, "NO RANGE");
>  }
>  
> +// ?? These stubs are because we use an ipa_vr in a hash_traits and
> +// hash-traits.h defines an extern of gt_ggc_mx (T &) instead of
> +// picking up the gt_ggc_mx (T *) version.

If you mean FIXME or TODO, please replace the "??" string with one of
those.  Otherwise please just remove it or specify what you mean in some
clearer way.

OK with that change.

Thanks,

Martin



> +void
> +gt_pch_nx (ipa_vr *&x)
> +{
> +  return gt_pch_nx ((ipa_vr *) x);
> +}
> +
> +void
> +gt_ggc_mx (ipa_vr *&x)
> +{
> +  return gt_ggc_mx ((ipa_vr *) x);
> +}
> +
> +

[...]

Re: [PATCH] Convert remaining uses of value_range in ipa-*.cc to Value_Range.

[Martin Jambor]

Hi,

On Mon, May 22 2023, Aldy Hernandez via Gcc-patches wrote:
> Minor cleanups to get rid of value_range in IPA.  There's only one left,
> but it's in the switch code which is integer specific.
>
> OK?

With the same request that...

>
> gcc/ChangeLog:
>
> 	* ipa-cp.cc (decide_whether_version_node): Adjust comment.
> 	* ipa-fnsummary.cc (evaluate_conditions_for_known_args): Adjust
> 	for Value_Range.
> 	(set_switch_stmt_execution_predicate): Same.
> 	* ipa-prop.cc (ipa_compute_jump_functions_for_edge): Same.
> ---
>  gcc/ipa-cp.cc        |  3 +--
>  gcc/ipa-fnsummary.cc | 22 ++++++++++++++--------
>  gcc/ipa-prop.cc      |  9 +++------
>  3 files changed, 18 insertions(+), 16 deletions(-)
>
> diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
> index 03273666ea2..2e64415096e 100644
> --- a/gcc/ipa-cp.cc
> +++ b/gcc/ipa-cp.cc
> @@ -6287,8 +6287,7 @@ decide_whether_version_node (struct cgraph_node *node)
>  	    {
>  	      /* If some values generated for self-recursive calls with
>  		 arithmetic jump functions fall outside of the known
> -		 value_range for the parameter, we can skip them.  VR interface
> -		 supports this only for integers now.  */
> +		 range for the parameter, we can skip them.  */
>  	      if (TREE_CODE (val->value) == INTEGER_CST
>  		  && !plats->m_value_range.bottom_p ()
>  		  && !ipa_range_contains_p (plats->m_value_range.m_vr,
> diff --git a/gcc/ipa-fnsummary.cc b/gcc/ipa-fnsummary.cc
> index 0474af8991e..1ce8501fe85 100644
> --- a/gcc/ipa-fnsummary.cc
> +++ b/gcc/ipa-fnsummary.cc
> @@ -488,19 +488,20 @@ evaluate_conditions_for_known_args (struct cgraph_node *node,
>  		  if (vr.varying_p () || vr.undefined_p ())
>  		    break;
>  
> -		  value_range res;
> +		  Value_Range res (op->type);
>  		  if (!op->val[0])
>  		    {
> +		      Value_Range varying (op->type);
> +		      varying.set_varying (op->type);
>  		      range_op_handler handler (op->code, op->type);
>  		      if (!handler
>  			  || !res.supports_type_p (op->type)
> -			  || !handler.fold_range (res, op->type, vr,
> -						  value_range (op->type)))
> +			  || !handler.fold_range (res, op->type, vr, varying))
>  			res.set_varying (op->type);
>  		    }
>  		  else if (!op->val[1])
>  		    {
> -		      value_range op0;
> +		      Value_Range op0 (op->type);
>  		      range_op_handler handler (op->code, op->type);
>  
>  		      ipa_range_set_and_normalize (op0, op->val[0]);
> @@ -518,14 +519,14 @@ evaluate_conditions_for_known_args (struct cgraph_node *node,
>  		}
>  	      if (!vr.varying_p () && !vr.undefined_p ())
>  		{
> -		  value_range res;
> -		  value_range val_vr;
> +		  int_range<2> res;
> +		  Value_Range val_vr (TREE_TYPE (c->val));
>  		  range_op_handler handler (c->code, boolean_type_node);
>  
>  		  ipa_range_set_and_normalize (val_vr, c->val);
>  
>  		  if (!handler
> -		      || !res.supports_type_p (boolean_type_node)
> +		      || !val_vr.supports_type_p (TREE_TYPE (c->val))
>  		      || !handler.fold_range (res, boolean_type_node, vr, val_vr))
>  		    res.set_varying (boolean_type_node);
>  
> @@ -1687,12 +1688,17 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi,
>    int bound_limit = opt_for_fn (fbi->node->decl,
>  				param_ipa_max_switch_predicate_bounds);
>    int bound_count = 0;
> -  value_range vr;
> +  // This can safely be an integer range, as switches can only hold
> +  // integers.
> +  int_range<2> vr;
>  
>    get_range_query (cfun)->range_of_expr (vr, op);
>    if (vr.undefined_p ())
>      vr.set_varying (TREE_TYPE (op));
>    tree vr_min, vr_max;
> +  // ?? This entire function could use a rewrite to use the irange
> +  // API, instead of trying to recreate its intersection/union logic.
> +  // Any use of get_legacy_range() is a serious code smell.

you replace "??" with TODO, because that is presumably what you mean.

OK with that change.

Thanks,

Martin


>    value_range_kind vr_type = get_legacy_range (vr, vr_min, vr_max);
>    wide_int vr_wmin = wi::to_wide (vr_min);
>    wide_int vr_wmax = wi::to_wide (vr_max);
> diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
> index 6383bc11e0a..5f9e6dbbff2 100644
> --- a/gcc/ipa-prop.cc
> +++ b/gcc/ipa-prop.cc
> @@ -2348,7 +2348,6 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>    gcall *call = cs->call_stmt;
>    int n, arg_num = gimple_call_num_args (call);
>    bool useful_context = false;
> -  value_range vr;
>  
>    if (arg_num == 0 || args->jump_functions)
>      return;
> @@ -2379,6 +2378,7 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>  	    useful_context = true;
>  	}
>  
> +      Value_Range vr (TREE_TYPE (arg));
>        if (POINTER_TYPE_P (TREE_TYPE (arg)))
>  	{
>  	  bool addr_nonzero = false;
> @@ -2404,14 +2404,11 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi,
>  	{
>  	  if (TREE_CODE (arg) == SSA_NAME
>  	      && param_type
> -	      /* Limit the ranger query to integral types as the rest
> -		 of this file uses value_range's, which only hold
> -		 integers and pointers.  */
> -	      && irange::supports_p (TREE_TYPE (arg))
> +	      && Value_Range::supports_type_p (TREE_TYPE (arg))
>  	      && get_range_query (cfun)->range_of_expr (vr, arg)
>  	      && !vr.undefined_p ())
>  	    {
> -	      value_range resvr = vr;
> +	      Value_Range resvr (vr);
>  	      range_cast (resvr, param_type);
>  	      if (!resvr.undefined_p () && !resvr.varying_p ())
>  		ipa_set_jfunc_vr (jfunc, resvr);
> -- 
> 2.40.1