From 6db4bc6e2553169f6bf1214d7cbb95e2d0060402 Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Fri, 19 Dec 2014 21:27:53 +0100 Subject: [PATCH] hash-table.h (struct pointer_hash): Fix formating. * 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): Use gcc_checking_assert. (hash_table::expand ()): Fix formating. (hash_table::clear_slot (value_type **slot)): Use checking assert. * hash-table.c: Remove #if 0 code. (hash_table_higher_prime_index): Use gcc_assert. (mul_mod, hash-table_mod1, hash_table_mod2): move to hash-table.h From-SVN: r218976 --- gcc/ChangeLog | 14 ++++++++ gcc/hash-table.c | 94 +----------------------------------------------- gcc/hash-table.h | 83 ++++++++++++++++++++++++++++++++---------- 3 files changed, 79 insertions(+), 112 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 05374e1cbf9..9c5841f91c8 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2014-12-19 Jan Hubicka + + * 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): Use gcc_checking_assert. + (hash_table::expand ()): Fix formating. + (hash_table::clear_slot (value_type **slot)): + Use checking assert. + * hash-table.c: Remove #if 0 code. + (hash_table_higher_prime_index): Use gcc_assert. + (mul_mod, hash-table_mod1, hash_table_mod2): move to hash-table.h + 2014-12-19 Matthew Fortune * config.gcc: Support mips*-img-linux* and mips*-img-elf*. diff --git a/gcc/hash-table.c b/gcc/hash-table.c index 3dfde6d2170..4c9ef0abf72 100644 --- a/gcc/hash-table.c +++ b/gcc/hash-table.c @@ -41,39 +41,6 @@ along with GCC; see the file COPYING3. If not see 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 long n) } /* 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); -} diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 5485d06f5bd..bfbe36db7e5 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -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 @@ -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 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 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 table entries is changed. If memory allocation fails, this function will abort. */ - template class Allocator> +template class Allocator> void hash_table::expand () { @@ -862,9 +906,9 @@ template class Allocator> void hash_table::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 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 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 class Allocator> void hash_table::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); -- 2.30.2