[RFC PATCH 1/1] dwarf_loader: have all CUs use a single hash table

[Bill Wendling <morbo@google.com>]

In some instances, e.g. with clang's LTO, a DWARF compilation units may
reference tags in other CUs. This presents us with a "chicken and egg"
problem, where in order to properly process on CU we need access to the
tags in all CUs.

This increases the runtime by ~28% (from 11.11s to 14.27s).

Signed-off-by: Bill Wendling <morbo@google.com>
---
 dwarf_loader.c | 45 +++++++++++++++++++++++++++++++++------------
 1 file changed, 33 insertions(+), 12 deletions(-)

diff --git a/dwarf_loader.c b/dwarf_loader.c
index b73d786..2b0d619 100644
--- a/dwarf_loader.c
+++ b/dwarf_loader.c
@@ -102,7 +102,7 @@ static void dwarf_tag__set_spec(struct dwarf_tag *dtag, dwarf_off_ref spec)
 	*(dwarf_off_ref *)(dtag + 1) = spec;
 }
 
-#define HASHTAGS__BITS 15
+#define HASHTAGS__BITS 16
 #define HASHTAGS__SIZE (1UL << HASHTAGS__BITS)
 
 #define obstack_chunk_alloc malloc
@@ -117,21 +117,42 @@ static void *obstack_zalloc(struct obstack *obstack, size_t size)
 	return o;
 }
 
+/* The tags and types hashes used by all "dwarf_cu" objects. */
+struct dwarf_cu_hash {
+	struct hlist_head tags[HASHTAGS__SIZE];
+	struct hlist_head types[HASHTAGS__SIZE];
+};
+
 struct dwarf_cu {
-	struct hlist_head hash_tags[HASHTAGS__SIZE];
-	struct hlist_head hash_types[HASHTAGS__SIZE];
+	struct dwarf_cu_hash *hashes;
 	struct obstack obstack;
 	struct cu *cu;
 	struct dwarf_cu *type_unit;
 };
 
+static struct dwarf_cu_hash *dwarf_cu__init_hashes(void)
+{
+	static struct dwarf_cu_hash *hashes = NULL;
+
+	if (!hashes) {
+		unsigned int i;
+
+		hashes = malloc(sizeof(struct dwarf_cu_hash));
+		if (!hashes)
+			return NULL;
+
+		for (i = 0; i < HASHTAGS__SIZE; ++i) {
+			INIT_HLIST_HEAD(&hashes->tags[i]);
+			INIT_HLIST_HEAD(&hashes->types[i]);
+		}
+	}
+
+	return hashes;
+}
+
 static void dwarf_cu__init(struct dwarf_cu *dcu)
 {
-	unsigned int i;
-	for (i = 0; i < HASHTAGS__SIZE; ++i) {
-		INIT_HLIST_HEAD(&dcu->hash_tags[i]);
-		INIT_HLIST_HEAD(&dcu->hash_types[i]);
-	}
+	dcu->hashes = dwarf_cu__init_hashes();
 	obstack_init(&dcu->obstack);
 	dcu->type_unit = NULL;
 }
@@ -166,8 +187,8 @@ static void cu__hash(struct cu *cu, struct tag *tag)
 {
 	struct dwarf_cu *dcu = cu->priv;
 	struct hlist_head *hashtable = tag__is_tag_type(tag) ?
-							dcu->hash_types :
-							dcu->hash_tags;
+							dcu->hashes->types :
+							dcu->hashes->tags;
 	hashtags__hash(hashtable, tag->priv);
 }
 
@@ -179,7 +200,7 @@ static struct dwarf_tag *dwarf_cu__find_tag_by_ref(const struct dwarf_cu *cu,
 	if (ref->from_types) {
 		return NULL;
 	}
-	return hashtags__find(cu->hash_tags, ref->off);
+	return hashtags__find(cu->hashes->tags, ref->off);
 }
 
 static struct dwarf_tag *dwarf_cu__find_type_by_ref(const struct dwarf_cu *dcu,
@@ -193,7 +214,7 @@ static struct dwarf_tag *dwarf_cu__find_type_by_ref(const struct dwarf_cu *dcu,
 			return NULL;
 		}
 	}
-	return hashtags__find(dcu->hash_types, ref->off);
+	return hashtags__find(dcu->hashes->types, ref->off);
 }
 
 extern struct strings *strings;
-- 
2.30.0.478.g8a0d178c01-goog