tree-optimization/113910 - huge compile time during PTA
Checks
Commit Message
For the testcase in PR113910 we spend a lot of time in PTA comparing
bitmaps for looking up equivalence class members. This points to
the very weak bitmap_hash function which effectively hashes set
and a subset of not set bits. The following improves it by mixing
that weak result with the population count of the bitmap, reducing
the number of collisions significantly. It's still by no means
a good hash function.
One major problem with it was that it simply truncated the
BITMAP_WORD sized intermediate hash to hashval_t which is
unsigned int, effectively not hashing half of the bits. That solves
most of the slowness. Mixing in the population count improves
compile-time by another 30% though.
This reduces the compile-time for the testcase from tens of minutes
to 30 seconds and PTA time from 99% to 25%. bitmap_equal_p is gone
from the profile.
Bootstrap and regtest running on x86_64-unknown-linux-gnu, will
push to trunk and branches.
PR tree-optimization/113910
* bitmap.cc (bitmap_hash): Mix the full element "hash" with
the bitmap population count.
---
gcc/bitmap.cc | 8 ++++++--
1 file changed, 6 insertions(+), 2 deletions(-)
@@ -2696,6 +2696,7 @@ bitmap_hash (const_bitmap head)
{
const bitmap_element *ptr;
BITMAP_WORD hash = 0;
+ unsigned long count = 0;
int ix;
gcc_checking_assert (!head->tree_form);
@@ -2704,9 +2705,12 @@ bitmap_hash (const_bitmap head)
{
hash ^= ptr->indx;
for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
- hash ^= ptr->bits[ix];
+ {
+ hash ^= ptr->bits[ix];
+ count += bitmap_count_bits_in_word (&ptr->bits[ix]);
+ }
}
- return (hashval_t)hash;
+ return iterative_hash (&hash, sizeof (hash), count);
}