Implement ipa_vr hashing.

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

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

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

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

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

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
>

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

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

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);
> +}
> +
> +

[...]