Re: [PATCH] Implement ipa_vr hashing.
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
> /* Hash table for avoid repeated allocations of equal ipa_bits. */
> static GTY ((cache)) hash_table
> *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
> +struct ipa_vr_ggc_hash_traits : public ggc_cache_remove
> {
> - 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 *)
> + mark_empty (ipa_vr *)
> {
>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 (1);
> + return p == reinterpret_cast (1);
> }
>static void
> - mark_deleted (value_range *)
> + mark_deleted (ipa_vr *)
> {
> - p = reinterpret_cast (1);
> + p = reinterpret_cast (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_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 *)
> +{
> + return gt_pch_nx ((ipa_vr *) x);
> +}
> +
> +void
> +gt_ggc_mx (ipa_vr *)
> +{
> + return gt_ggc_mx ((ipa_vr *) x);
> +}
> +
> +
[...]
Re: [PATCH] Implement ipa_vr hashing.
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 wrote: > > PING*3 > > On Thu, Jun 22, 2023 at 7:49 AM Aldy Hernandez wrote: > > > > Ping*2 > > > > On Wed, Jun 14, 2023, 14:11 Aldy Hernandez wrote: > >> > >> PING > >> > >> On Sat, Jun 10, 2023 at 10:30 PM Aldy Hernandez 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.
PING*3 On Thu, Jun 22, 2023 at 7:49 AM Aldy Hernandez wrote: > > Ping*2 > > On Wed, Jun 14, 2023, 14:11 Aldy Hernandez wrote: >> >> PING >> >> On Sat, Jun 10, 2023 at 10:30 PM Aldy Hernandez 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.
Ping*2 On Wed, Jun 14, 2023, 14:11 Aldy Hernandez wrote: > PING > > On Sat, Jun 10, 2023 at 10:30 PM Aldy Hernandez 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.
PING On Sat, Jun 10, 2023 at 10:30 PM Aldy Hernandez 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.
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.
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.
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
> /* Hash table for avoid repeated allocations of equal ipa_bits. */
> static GTY ((cache)) hash_table
> *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
> +struct ipa_vr_ggc_hash_traits : public ggc_cache_remove
> {
> - 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 *)
> + mark_empty (ipa_vr *)
> {
>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 (1);
> + return p == reinterpret_cast (1);
> }
>static void
> - mark_deleted (value_range *)
> + mark_deleted (ipa_vr *)
> {
> - p = reinterpret_cast (1);
> + p = reinterpret_cast (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_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 *)
> +{
> + return gt_pch_nx ((ipa_vr *) x);
> +}
> +
> +void
> +gt_ggc_mx (ipa_vr *)
> +{
> + 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 ,
>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
