[PATCH] Fix up ipa_vr_ggc_hash_traits::hash

[Jakub Jelinek]

Hi!

ipa_vr_ggc_hash_traits::equal does
  return a->type == b->type && a->min == b->min && a->max == b->max;
so it requires pointer identical type (5 value enum) and min/max,
hopefully only INTEGER_CSTs.  Honza complained on IRC that during
firefox a lot of time is spent in this hash table, probably because
the hash function was poor, it hashes any ranges with the same
min/max values but different TREE_TYPE (p->min) the same.

The following patch adjusts the hash method to match the equal
method, bootstrapped/regtested on x86_64-linux and i686-linux,
ok for trunk?

In theory we could get bigger savings by e.g. using operand_equal_p
on p->min and p->max instead of pointer comparison, but not really sure
if the VRP code is prepared for that.  E.g. VRP cares whether min
or max are the minimum or maximum of the corresponding type, but if we
ignore the type completely, it could be any other integral type.
We'd use the same value_range memory struct for unsigned char [5, 255]
range, where it is [5, +INF] and for int, where it is just [5, 255].
Does LTO canonicalize INTEGER_TYPEs using type_hash_canon?  In any case,
I think further optimizations should be postponed for GCC9.

2018-02-23  Jakub Jelinek  

* ipa-prop.c (ipa_vr_ggc_hash_traits::hash): Hash p->min and
p->max as pointers rather than using iterative_hash_expr.

--- gcc/ipa-prop.c.jj   2018-01-03 10:19:54.617533871 +0100
+++ gcc/ipa-prop.c  2018-02-23 14:43:08.983733102 +0100
@@ -111,12 +111,13 @@ struct ipa_vr_ggc_hash_traits : public g
   typedef value_range *compare_type;
   static hashval_t
   hash (const value_range *p)
-  {
-gcc_checking_assert (!p->equiv);
-hashval_t t = (hashval_t) p->type;
-t = iterative_hash_expr (p->min, t);
-return iterative_hash_expr (p->max, t);
-  }
+{
+  gcc_checking_assert (!p->equiv);
+  inchash::hash hstate (p->type);
+  hstate.add_ptr (p->min);
+  hstate.add_ptr (p->max);
+  return hstate.end ();
+}
   static bool
   equal (const value_range *a, const value_range *b)
 {

Jakub

Re: [PATCH] Fix up ipa_vr_ggc_hash_traits::hash

[Richard Biener]

On February 23, 2018 6:06:51 PM GMT+01:00, Jakub Jelinek  
wrote:
>Hi!
>
>ipa_vr_ggc_hash_traits::equal does
>  return a->type == b->type && a->min == b->min && a->max == b->max;
>so it requires pointer identical type (5 value enum) and min/max,
>hopefully only INTEGER_CSTs.  Honza complained on IRC that during
>firefox a lot of time is spent in this hash table, probably because
>the hash function was poor, it hashes any ranges with the same
>min/max values but different TREE_TYPE (p->min) the same.
>
>The following patch adjusts the hash method to match the equal
>method, bootstrapped/regtested on x86_64-linux and i686-linux,
>ok for trunk?
>
>In theory we could get bigger savings by e.g. using operand_equal_p
>on p->min and p->max instead of pointer comparison, but not really sure
>if the VRP code is prepared for that.  E.g. VRP cares whether min
>or max are the minimum or maximum of the corresponding type, but if we
>ignore the type completely, it could be any other integral type.

That would certainly lead to issues.

>We'd use the same value_range memory struct for unsigned char [5, 255]
>range, where it is [5, +INF] and for int, where it is just [5, 255].
>Does LTO canonicalize INTEGER_TYPEs using type_hash_canon? 

No.  It unifies with its own logic and types are not registered with the canon 
hash. 

 In any
>case,
>I think further optimizations should be postponed for GCC9.

OK. 

Thanks, 
Richard. 

>2018-02-23  Jakub Jelinek  
>
>   * ipa-prop.c (ipa_vr_ggc_hash_traits::hash): Hash p->min and
>   p->max as pointers rather than using iterative_hash_expr.
>
>--- gcc/ipa-prop.c.jj  2018-01-03 10:19:54.617533871 +0100
>+++ gcc/ipa-prop.c 2018-02-23 14:43:08.983733102 +0100
>@@ -111,12 +111,13 @@ struct ipa_vr_ggc_hash_traits : public g
>   typedef value_range *compare_type;
>   static hashval_t
>   hash (const value_range *p)
>-  {
>-gcc_checking_assert (!p->equiv);
>-hashval_t t = (hashval_t) p->type;
>-t = iterative_hash_expr (p->min, t);
>-return iterative_hash_expr (p->max, t);
>-  }
>+{
>+  gcc_checking_assert (!p->equiv);
>+  inchash::hash hstate (p->type);
>+  hstate.add_ptr (p->min);
>+  hstate.add_ptr (p->max);
>+  return hstate.end ();
>+}
>   static bool
>   equal (const value_range *a, const value_range *b)
> {
>
>   Jakub