Hi,
this patch started as experiment moving hash_table_mod1 inline because it shows
high in streaming profiles and it represents a branch-less code that is good
to schedule to surrounding instructions.
While looking at hash-tab.h I however noticed that it was not updated very
well while it was moved from libiberty.h. It still assumes lack of 64bit
integers to be possible and also it uses abort() calls instead of gcc_asserts.
Fixed thus.
Bootstrapped/regtested x86_64-linux, also checked that cc1plus binary
shirnks by about 15kb despite the extra inlining. Will commit it shortly.
Honza
* hash-table.h (struct pointer_hash): Fix formating.
(hash_table_higher_prime_index): Declare pure.
(hash_table_mod2, hash_table_mod1, mul_mod): Move inline;
assume that uint64_t always exists.
(hash_table<Descriptor, Allocator, false>): Use gcc_checking_assert.
(hash_table<Descriptor, Allocator, false>::expand ()): Fix formating.
(hash_table<Descriptor, Allocator, false>::clear_slot (value_type
**slot)):
Use checking assert.
* hash-table.c: Remvoe #if 0 code.
(hash_table_higher_prime_index): Use gcc_assert.
(mul_mod, hash-table_mod1, hash_table_mod2): move to hash-table.h
Index: hash-table.h
===================================================================
--- hash-table.h (revision 218795)
+++ hash-table.h (working copy)
@@ -282,7 +282,8 @@ struct pointer_hash : typed_noop_remove
static inline hashval_t hash (const value_type &);
- static inline bool equal (const value_type &existing, const compare_type
&candidate);
+ static inline bool equal (const value_type &existing,
+ const compare_type &candidate);
};
template <typename Type>
@@ -388,9 +389,54 @@ extern struct prime_ent const prime_tab[
/* Functions for computing hash table indexes. */
-extern unsigned int hash_table_higher_prime_index (unsigned long n);
-extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
-extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
+extern unsigned int hash_table_higher_prime_index (unsigned long n)
+ ATTRIBUTE_PURE;
+
+/* Return X % Y using multiplicative inverse values INV and SHIFT.
+
+ The multiplicative inverses computed above are for 32-bit types,
+ and requires that we be able to compute a highpart multiply.
+
+ FIX: I am not at all convinced that
+ 3 loads, 2 multiplications, 3 shifts, and 3 additions
+ will be faster than
+ 1 load and 1 modulus
+ on modern systems running a compiler. */
+
+inline hashval_t
+mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
+{
+ hashval_t t1, t2, t3, t4, q, r;
+
+ t1 = ((uint64_t)x * inv) >> 32;
+ t2 = x - t1;
+ t3 = t2 >> 1;
+ t4 = t1 + t3;
+ q = t4 >> shift;
+ r = x - (q * y);
+
+ return r;
+}
+
+/* Compute the primary table index for HASH given current prime index. */
+
+inline hashval_t
+hash_table_mod1 (hashval_t hash, unsigned int index)
+{
+ const struct prime_ent *p = &prime_tab[index];
+ gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
+ return mul_mod (hash, p->prime, p->inv, p->shift);
+}
+
+/* Compute the secondary table index for HASH given current prime index. */
+
+inline hashval_t
+hash_table_mod2 (hashval_t hash, unsigned int index)
+{
+ const struct prime_ent *p = &prime_tab[index];
+ gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32);
+ return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
+}
/* The below is some template meta programming to decide if we should use the
hash table partial specialization that directly stores value_type instead of
@@ -748,8 +794,7 @@ hash_table<Descriptor, Allocator, false>
if (*slot == HTAB_EMPTY_ENTRY)
return slot;
- else if (*slot == HTAB_DELETED_ENTRY)
- abort ();
+ gcc_checking_assert (*slot != HTAB_DELETED_ENTRY);
hash2 = hash_table_mod2 (hash, m_size_prime_index);
for (;;)
@@ -761,8 +806,7 @@ hash_table<Descriptor, Allocator, false>
slot = m_entries + index;
if (*slot == HTAB_EMPTY_ENTRY)
return slot;
- else if (*slot == HTAB_DELETED_ENTRY)
- abort ();
+ gcc_checking_assert (*slot != HTAB_DELETED_ENTRY);
}
}
@@ -773,7 +817,7 @@ hash_table<Descriptor, Allocator, false>
table entries is changed. If memory allocation fails, this function
will abort. */
- template<typename Descriptor, template<typename Type> class Allocator>
+template<typename Descriptor, template<typename Type> class Allocator>
void
hash_table<Descriptor, Allocator, false>::expand ()
{
@@ -862,9 +906,9 @@ template<typename Descriptor, template<t
void
hash_table<Descriptor, Allocator, false>::clear_slot (value_type **slot)
{
- if (slot < m_entries || slot >= m_entries + size ()
- || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
- abort ();
+ gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
+ || *slot == HTAB_EMPTY_ENTRY
+ || *slot == HTAB_DELETED_ENTRY));
Descriptor::remove (*slot);
@@ -1317,8 +1361,9 @@ hash_table<Descriptor, Allocator, true>
if (is_empty (*slot))
return slot;
- else if (is_deleted (*slot))
- abort ();
+#ifdef ENABLE_CHECKING
+ gcc_checking_assert (!is_deleted (*slot));
+#endif
hash2 = hash_table_mod2 (hash, m_size_prime_index);
for (;;)
@@ -1330,8 +1375,9 @@ hash_table<Descriptor, Allocator, true>
slot = m_entries + index;
if (is_empty (*slot))
return slot;
- else if (is_deleted (*slot))
- abort ();
+#ifdef ENABLE_CHECKING
+ gcc_checking_assert (!is_deleted (*slot));
+#endif
}
}
@@ -1437,9 +1483,8 @@ template<typename Descriptor, template<t
void
hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot)
{
- if (slot < m_entries || slot >= m_entries + size ()
- || is_empty (*slot) || is_deleted (*slot))
- abort ();
+ gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size ()
+ || is_empty (*slot) || is_deleted (*slot)));
Descriptor::remove (*slot);
Index: hash-table.c
===================================================================
--- hash-table.c (revision 218795)
+++ hash-table.c (working copy)
@@ -41,39 +41,6 @@ along with GCC; see the file COPYING3.
For the record, here's the function that computed the table; it's a
vastly simplified version of the function of the same name from gcc. */
-#if 0
-unsigned int
-ceil_log2 (unsigned int x)
-{
- int i;
- for (i = 31; i >= 0 ; --i)
- if (x > (1u << i))
- return i+1;
- abort ();
-}
-
-unsigned int
-choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp)
-{
- unsigned long long mhigh;
- double nx;
- int lgup, post_shift;
- int pow, pow2;
- int n = 32, precision = 32;
-
- lgup = ceil_log2 (d);
- pow = n + lgup;
- pow2 = n + lgup - precision;
-
- nx = ldexp (1.0, pow) + ldexp (1.0, pow2);
- mhigh = nx / d;
-
- *shiftp = lgup - 1;
- *mlp = mhigh;
- return mhigh >> 32;
-}
-#endif
-
struct prime_ent const prime_tab[] = {
{ 7, 0x24924925, 0x9999999b, 2 },
{ 13, 0x3b13b13c, 0x745d1747, 3 },
@@ -127,67 +94,8 @@ hash_table_higher_prime_index (unsigned
}
/* If we've run out of primes, abort. */
- if (n > prime_tab[low].prime)
- {
- fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
- abort ();
- }
+ gcc_assert (n <= prime_tab[low].prime);
return low;
}
-/* Return X % Y using multiplicative inverse values INV and SHIFT.
-
- The multiplicative inverses computed above are for 32-bit types,
- and requires that we be able to compute a highpart multiply.
-
- FIX: I am not at all convinced that
- 3 loads, 2 multiplications, 3 shifts, and 3 additions
- will be faster than
- 1 load and 1 modulus
- on modern systems running a compiler. */
-
-#ifdef UNSIGNED_64BIT_TYPE
-static inline hashval_t
-mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
-{
- __extension__ typedef UNSIGNED_64BIT_TYPE ull;
- hashval_t t1, t2, t3, t4, q, r;
-
- t1 = ((ull)x * inv) >> 32;
- t2 = x - t1;
- t3 = t2 >> 1;
- t4 = t1 + t3;
- q = t4 >> shift;
- r = x - (q * y);
-
- return r;
-}
-#endif
-
-/* Compute the primary table index for HASH given current prime index. */
-
-hashval_t
-hash_table_mod1 (hashval_t hash, unsigned int index)
-{
- const struct prime_ent *p = &prime_tab[index];
-#ifdef UNSIGNED_64BIT_TYPE
- if (sizeof (hashval_t) * CHAR_BIT <= 32)
- return mul_mod (hash, p->prime, p->inv, p->shift);
-#endif
- return hash % p->prime;
-}
-
-
-/* Compute the secondary table index for HASH given current prime index. */
-
-hashval_t
-hash_table_mod2 (hashval_t hash, unsigned int index)
-{
- const struct prime_ent *p = &prime_tab[index];
-#ifdef UNSIGNED_64BIT_TYPE
- if (sizeof (hashval_t) * CHAR_BIT <= 32)
- return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
-#endif
- return 1 + hash % (p->prime - 2);
-}
