From: Trevor Saunders <tsaund...@mozilla.com>
Hi,
The only user of this is splay_tree. We only have a couple splay trees in ggc
memory, and it wasn't clear to me any of them were tree based instead of hash
based for performance reasons, so I chose to just convert them to hash_map
rather than writing a templated splay tree.
bootstrapped + regtested x86_64-unknown-linux-gnu, ok?
trev
gcc/
* hash-map.h (hash_map::iterator): New class.
(hash_map::begin): New method.
(hash_map::end): Likewise.
* alias.c, config/alpha/alpha.c, dwarf2asm.c, omp-low.c, tree.h:
replace splay_tree with hash_map.
diff --git a/gcc/alias.c b/gcc/alias.c
index aa6ae41..fe27ce8 100644
--- a/gcc/alias.c
+++ b/gcc/alias.c
@@ -41,6 +41,7 @@ along with GCC; see the file COPYING3. If not see
#include "diagnostic-core.h"
#include "cselib.h"
#include "splay-tree.h"
+#include "hash-map.h"
#include "langhooks.h"
#include "timevar.h"
#include "dumpfile.h"
@@ -139,6 +140,32 @@ along with GCC; see the file COPYING3. If not see
However, this is no actual entry for alias set zero. It is an
error to attempt to explicitly construct a subset of zero. */
+struct alias_set_traits : default_hashmap_traits
+{
+ template<typename T>
+ static bool
+ is_empty (T &e)
+ {
+ return e.m_key == INT_MIN;
+ }
+
+ template<typename T>
+ static bool
+ is_deleted (T &e)
+ {
+ return e.m_key == (INT_MIN + 1);
+ }
+
+ template<typename T> static void mark_empty (T &e) { e.m_key = INT_MIN; }
+
+ template<typename T>
+ static void
+ mark_deleted (T &e)
+ {
+ e.m_key = INT_MIN + 1;
+ }
+};
+
struct GTY(()) alias_set_entry_d {
/* The alias set number, as stored in MEM_ALIAS_SET. */
alias_set_type alias_set;
@@ -154,7 +181,7 @@ struct GTY(()) alias_set_entry_d {
continuing our example above, the children here will be all of
`int', `double', `float', and `struct S'. */
- splay_tree GTY((param1_is (int), param2_is (int))) children;
+ hash_map<int, int, alias_set_traits> *children;
};
typedef struct alias_set_entry_d *alias_set_entry;
@@ -165,7 +192,6 @@ static int base_alias_check (rtx, rtx, rtx, rtx,
machine_mode,
machine_mode);
static rtx find_base_value (rtx);
static int mems_in_disjoint_alias_sets_p (const_rtx, const_rtx);
-static int insert_subset_children (splay_tree_node, void*);
static alias_set_entry get_alias_set_entry (alias_set_type);
static tree decl_for_component_ref (tree);
static int write_dependence_p (const_rtx,
@@ -405,17 +431,6 @@ mems_in_disjoint_alias_sets_p (const_rtx mem1, const_rtx
mem2)
return ! alias_sets_conflict_p (MEM_ALIAS_SET (mem1), MEM_ALIAS_SET (mem2));
}
-/* Insert the NODE into the splay tree given by DATA. Used by
- record_alias_subset via splay_tree_foreach. */
-
-static int
-insert_subset_children (splay_tree_node node, void *data)
-{
- splay_tree_insert ((splay_tree) data, node->key, node->value);
-
- return 0;
-}
-
/* Return true if the first alias set is a subset of the second. */
bool
@@ -431,8 +446,7 @@ alias_set_subset_of (alias_set_type set1, alias_set_type
set2)
ase = get_alias_set_entry (set2);
if (ase != 0
&& (ase->has_zero_child
- || splay_tree_lookup (ase->children,
- (splay_tree_key) set1)))
+ || ase->children->get (set1)))
return true;
return false;
}
@@ -452,16 +466,14 @@ alias_sets_conflict_p (alias_set_type set1,
alias_set_type set2)
ase = get_alias_set_entry (set1);
if (ase != 0
&& (ase->has_zero_child
- || splay_tree_lookup (ase->children,
- (splay_tree_key) set2)))
+ || ase->children->get (set2)))
return 1;
/* Now do the same, but with the alias sets reversed. */
ase = get_alias_set_entry (set2);
if (ase != 0
&& (ase->has_zero_child
- || splay_tree_lookup (ase->children,
- (splay_tree_key) set1)))
+ || ase->children->get (set1)))
return 1;
/* The two alias sets are distinct and neither one is the
@@ -956,9 +968,7 @@ record_alias_subset (alias_set_type superset,
alias_set_type subset)
superset_entry = ggc_cleared_alloc<alias_set_entry_d> ();
superset_entry->alias_set = superset;
superset_entry->children
- = splay_tree_new_ggc (splay_tree_compare_ints,
- ggc_alloc_splay_tree_scalar_scalar_splay_tree_s,
-
ggc_alloc_splay_tree_scalar_scalar_splay_tree_node_s);
+ = hash_map<int, int, alias_set_traits>::create_ggc (64);
superset_entry->has_zero_child = 0;
(*alias_sets)[superset] = superset_entry;
}
@@ -975,13 +985,14 @@ record_alias_subset (alias_set_type superset,
alias_set_type subset)
if (subset_entry->has_zero_child)
superset_entry->has_zero_child = 1;
- splay_tree_foreach (subset_entry->children, insert_subset_children,
- superset_entry->children);
+ hash_map<int, int, alias_set_traits>::iterator iter
+ = subset_entry->children->begin ();
+ for (; iter != subset_entry->children->end (); ++iter)
+ superset_entry->children->put ((*iter).first, (*iter).second);
}
/* Enter the SUBSET itself as a child of the SUPERSET. */
- splay_tree_insert (superset_entry->children,
- (splay_tree_key) subset, 0);
+ superset_entry->children->put (subset, 0);
}
}
diff --git a/gcc/config/alpha/alpha.c b/gcc/config/alpha/alpha.c
index 05db3dc..33ff717 100644
--- a/gcc/config/alpha/alpha.c
+++ b/gcc/config/alpha/alpha.c
@@ -57,6 +57,7 @@ along with GCC; see the file COPYING3. If not see
#include "debug.h"
#include "langhooks.h"
#include "splay-tree.h"
+#include "hash-map.h"
#include "hash-table.h"
#include "predict.h"
#include "dominance.h"
@@ -4860,6 +4861,14 @@ alpha_multipass_dfa_lookahead (void)
struct GTY(()) alpha_links;
+struct string_traits : default_hashmap_traits
+{
+ static bool equal_keys (const char *const &a, const char *const &b)
+ {
+ return strcmp (a, b) == 0;
+ }
+};
+
struct GTY(()) machine_function
{
/* For flag_reorder_blocks_and_partition. */
@@ -4869,8 +4878,7 @@ struct GTY(()) machine_function
bool uses_condition_handler;
/* Linkage entries. */
- splay_tree GTY ((param1_is (char *), param2_is (struct alpha_links *)))
- links;
+ hash_map<const char *, alpha_links *, string_traits> *links;
};
/* How to allocate a 'struct machine_function'. */
@@ -9642,18 +9650,14 @@ alpha_use_linkage (rtx func, bool lflag, bool rflag)
if (cfun->machine->links)
{
- splay_tree_node lnode;
-
/* Is this name already defined? */
- lnode = splay_tree_lookup (cfun->machine->links, (splay_tree_key) name);
- if (lnode)
- al = (struct alpha_links *) lnode->value;
+ alpha_links *slot = cfun->machine->links->get (name);
+ if (slot)
+ al = *slot;
}
else
- cfun->machine->links = splay_tree_new_ggc
- ((splay_tree_compare_fn) strcmp,
- ggc_alloc_splay_tree_str_alpha_links_splay_tree_s,
- ggc_alloc_splay_tree_str_alpha_links_splay_tree_node_s);
+ cfun->machine->links
+ = hash_map<const char *, alpha_links *, string_traits>::create_ggc (64);
if (al == NULL)
{
@@ -9681,9 +9685,7 @@ alpha_use_linkage (rtx func, bool lflag, bool rflag)
al->func = func;
al->linkage = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (linksym));
- splay_tree_insert (cfun->machine->links,
- (splay_tree_key) ggc_strdup (name),
- (splay_tree_value) al);
+ cfun->machine->links->put (ggc_strdup (name), al);
}
al->rkind = rflag ? KIND_CODEADDR : KIND_LINKAGE;
@@ -9695,12 +9697,8 @@ alpha_use_linkage (rtx func, bool lflag, bool rflag)
}
static int
-alpha_write_one_linkage (splay_tree_node node, void *data)
+alpha_write_one_linkage (const char *name, alpha_links *link, FILE *steam)
{
- const char *const name = (const char *) node->key;
- struct alpha_links *link = (struct alpha_links *) node->value;
- FILE *stream = (FILE *) data;
-
ASM_OUTPUT_INTERNAL_LABEL (stream, XSTR (link->linkage, 0));
if (link->rkind == KIND_CODEADDR)
{
@@ -9750,8 +9748,10 @@ alpha_write_linkage (FILE *stream, const char *funname)
if (cfun->machine->links)
{
- splay_tree_foreach (cfun->machine->links, alpha_write_one_linkage,
stream);
- /* splay_tree_delete (func->links); */
+ hash_map<const char *, alpha_links *, string_traits>::iterator iter
+ = cfun->machine->links->begin ();
+ for (; iter != cfun->machine->links->end (); ++iter)
+ alpha_write_one_linkage ((*iter).first, (*iter).second, stream);
}
}
diff --git a/gcc/dwarf2asm.c b/gcc/dwarf2asm.c
index b437005..3eba5ca 100644
--- a/gcc/dwarf2asm.c
+++ b/gcc/dwarf2asm.c
@@ -32,6 +32,7 @@ along with GCC; see the file COPYING3. If not see
#include "dwarf2asm.h"
#include "dwarf2.h"
#include "splay-tree.h"
+#include "hash-map.h"
#include "ggc.h"
#include "tm_p.h"
@@ -790,9 +791,7 @@ dw2_asm_output_delta_sleb128 (const char *lab1
ATTRIBUTE_UNUSED,
}
#endif /* 0 */
-static int dw2_output_indirect_constant_1 (splay_tree_node, void *);
-
-static GTY((param1_is (char *), param2_is (tree))) splay_tree indirect_pool;
+static GTY(()) hash_map<const char *, tree> *indirect_pool;
static GTY(()) int dw2_const_labelno;
@@ -808,10 +807,10 @@ static GTY(()) int dw2_const_labelno;
K2, respectively. */
static int
-splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2)
+compare_strings (const void *a, const void *b)
{
- const char *s1 = (const char *)k1;
- const char *s2 = (const char *)k2;
+ const char *s1 = ((const std::pair<const char *, tree> *) a)->first;
+ const char *s2 = ((const std::pair<const char *, tree> *) b)->first;
int ret;
if (s1 == s2)
@@ -836,23 +835,18 @@ splay_tree_compare_strings (splay_tree_key k1,
splay_tree_key k2)
rtx
dw2_force_const_mem (rtx x, bool is_public)
{
- splay_tree_node node;
const char *key;
tree decl_id;
if (! indirect_pool)
- /* We use strcmp, rather than just comparing pointers, so that the
- sort order will not depend on the host system. */
- indirect_pool = splay_tree_new_ggc (splay_tree_compare_strings,
-
ggc_alloc_splay_tree_str_tree_node_splay_tree_s,
-
ggc_alloc_splay_tree_str_tree_node_splay_tree_node_s);
+ indirect_pool = hash_map<const char *, tree>::create_ggc (64);
gcc_assert (GET_CODE (x) == SYMBOL_REF);
key = XSTR (x, 0);
- node = splay_tree_lookup (indirect_pool, (splay_tree_key) key);
- if (node)
- decl_id = (tree) node->value;
+ tree *slot = indirect_pool->get (key);
+ if (slot)
+ decl_id = *slot;
else
{
tree id;
@@ -881,8 +875,7 @@ dw2_force_const_mem (rtx x, bool is_public)
if (id)
TREE_SYMBOL_REFERENCED (id) = 1;
- splay_tree_insert (indirect_pool, (splay_tree_key) key,
- (splay_tree_value) decl_id);
+ indirect_pool->put (key, decl_id);
}
return gen_rtx_SYMBOL_REF (Pmode, IDENTIFIER_POINTER (decl_id));
@@ -892,15 +885,10 @@ dw2_force_const_mem (rtx x, bool is_public)
splay_tree_foreach. Emit one queued constant to memory. */
static int
-dw2_output_indirect_constant_1 (splay_tree_node node,
- void *data ATTRIBUTE_UNUSED)
+dw2_output_indirect_constant_1 (const char *sym, tree id)
{
- const char *sym;
rtx sym_ref;
- tree id, decl;
-
- sym = (const char *) node->key;
- id = (tree) node->value;
+ tree decl;
decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, id, ptr_type_node);
SET_DECL_ASSEMBLER_NAME (decl, id);
@@ -930,8 +918,18 @@ dw2_output_indirect_constant_1 (splay_tree_node node,
void
dw2_output_indirect_constants (void)
{
- if (indirect_pool)
- splay_tree_foreach (indirect_pool, dw2_output_indirect_constant_1, NULL);
+ if (!indirect_pool)
+ return;
+
+ auto_vec<std::pair<const char *, tree> > temp (indirect_pool->elements ());
+ for (hash_map<const char *, tree>::iterator iter = indirect_pool->begin ();
+ iter != indirect_pool->end (); ++iter)
+ temp.quick_push (*iter);
+
+ temp.qsort (compare_strings);
+
+ for (unsigned int i = 0; i < temp.length (); i++)
+ dw2_output_indirect_constant_1 (temp[i].first, temp[i].second);
}
/* Like dw2_asm_output_addr_rtx, but encode the pointer as directed.
diff --git a/gcc/hash-map.h b/gcc/hash-map.h
index a5816dc..f6fdc1c 100644
--- a/gcc/hash-map.h
+++ b/gcc/hash-map.h
@@ -22,6 +22,7 @@ along with GCC; see the file COPYING3. If not see
#define hash_map_h
#include <new>
+#include <utility>
#include "hash-table.h"
/* implement default behavior for traits when types allow it. */
@@ -266,6 +267,39 @@ public:
size_t elements () const { return m_table.elements (); }
+ class iterator
+ {
+ public:
+ explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
+ m_iter (iter) {}
+
+ iterator &operator++ ()
+ {
+ ++m_iter;
+ return *this;
+ }
+
+ std::pair<Key, Value> operator* ()
+ {
+ hash_entry &e = *m_iter;
+ return std::pair<Key, Value> (e.m_key, e.m_value);
+ }
+
+ bool
+ operator != (const iterator &other) const
+ {
+ return m_iter != other.m_iter;
+ }
+
+ private:
+ typename hash_table<hash_entry>::iterator m_iter;
+ };
+
+ /* Standard iterator retrieval methods. */
+
+ iterator begin () const { return iterator (m_table.begin ()); }
+ iterator end () const { return iterator (m_table.end ()); }
+
private:
template<typename T, typename U, typename V> friend void gt_ggc_mx
(hash_map<T, U, V> *);
diff --git a/gcc/omp-low.c b/gcc/omp-low.c
index b59d069..b151430 100644
--- a/gcc/omp-low.c
+++ b/gcc/omp-low.c
@@ -9243,8 +9243,7 @@ lower_omp_ordered (gimple_stmt_iterator *gsi_p,
omp_context *ctx)
requires that languages coordinate a symbol name. It is therefore
best put here in common code. */
-static GTY((param1_is (tree), param2_is (tree)))
- splay_tree critical_name_mutexes;
+static GTY(()) hash_map<tree, tree> *critical_name_mutexes;
static void
lower_omp_critical (gimple_stmt_iterator *gsi_p, omp_context *ctx)
@@ -9259,15 +9258,11 @@ lower_omp_critical (gimple_stmt_iterator *gsi_p,
omp_context *ctx)
if (name)
{
tree decl;
- splay_tree_node n;
if (!critical_name_mutexes)
- critical_name_mutexes
- = splay_tree_new_ggc (splay_tree_compare_pointers,
-
ggc_alloc_splay_tree_tree_node_tree_node_splay_tree_s,
-
ggc_alloc_splay_tree_tree_node_tree_node_splay_tree_node_s);
+ critical_name_mutexes = hash_map<tree, tree>::create_ggc (10);
- n = splay_tree_lookup (critical_name_mutexes, (splay_tree_key) name);
+ tree *n = critical_name_mutexes->get (name);
if (n == NULL)
{
char *new_str;
@@ -9284,11 +9279,10 @@ lower_omp_critical (gimple_stmt_iterator *gsi_p,
omp_context *ctx)
DECL_IGNORED_P (decl) = 1;
varpool_node::finalize_decl (decl);
- splay_tree_insert (critical_name_mutexes, (splay_tree_key) name,
- (splay_tree_value) decl);
+ critical_name_mutexes->put (name, decl);
}
else
- decl = (tree) n->value;
+ decl = *n;
lock = builtin_decl_explicit (BUILT_IN_GOMP_CRITICAL_NAME_START);
lock = build_call_expr_loc (loc, lock, 1, build_fold_addr_expr_loc (loc,
decl));
diff --git a/gcc/tree.h b/gcc/tree.h
index 9875a50..7bff405 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -4862,4 +4862,9 @@ int_bit_position (const_tree field)
return (wi::lshift (wi::to_offset (DECL_FIELD_OFFSET (field)),
BITS_PER_UNIT_LOG)
+ wi::to_offset (DECL_FIELD_BIT_OFFSET (field))).to_shwi ();
}
+
+extern void gt_ggc_mx (tree &);
+extern void gt_pch_nx (tree &);
+extern void gt_pch_nx (tree &, gt_pointer_operator, void *);
+
#endif /* GCC_TREE_H */
--
2.1.3
