From 6ad5fde5d01e0c8c23b928583d2fb9489b1b5a36 Mon Sep 17 00:00:00 2001
From: Owen Anderson <resistor@mac.com>
Date: Fri, 20 Jul 2007 16:15:24 +0000
Subject: [PATCH] Have DenseMap auto-shrink itself on clear().  This improves
 the time to optimize 403.gcc from 15.2s to 14.3s.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40100 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/DenseMap.h | 37 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 36 insertions(+), 1 deletion(-)

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 83edd640e33..082fc35afa2 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -90,6 +90,11 @@ public:
   unsigned size() const { return NumEntries; }
   
   void clear() {
+    if (NumEntries * 4 < NumBuckets && NumBuckets > 64) {
+      shrink_and_clear();
+      return;
+    }
+    
     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
     for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
       if (P->first != EmptyKey && P->first != TombstoneKey) {
@@ -101,7 +106,7 @@ public:
     assert(NumEntries == 0 && "Node count imbalance!");
     NumTombstones = 0;
   }
-  
+
   /// count - Return true if the specified key is in the map.
   bool count(const KeyT &Val) const {
     BucketT *TheBucket;
@@ -290,6 +295,36 @@ private:
     // Free the old table.
     delete[] (char*)OldBuckets;
   }
+  
+  void shrink_and_clear() {
+    unsigned OldNumBuckets = NumBuckets;
+    BucketT *OldBuckets = Buckets;
+    
+    // Halve the number of buckets.
+    NumBuckets >>= 1;
+    NumTombstones = 0;
+    Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets];
+
+    // Initialize all the keys to EmptyKey.
+    const KeyT EmptyKey = getEmptyKey();
+    for (unsigned i = 0, e = NumBuckets; i != e; ++i)
+      new (&Buckets[i].first) KeyT(EmptyKey);
+
+    // Free the old buckets.
+    const KeyT TombstoneKey = getTombstoneKey();
+    for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
+      if (B->first != EmptyKey && B->first != TombstoneKey) {
+        // Free the value.
+        B->second.~ValueT();
+      }
+      B->first.~KeyT();
+    }
+    
+    // Free the old table.
+    delete[] (char*)OldBuckets;
+    
+    NumEntries = 0;
+  }
 };
 
 template<typename KeyT, typename ValueT, typename KeyInfoT>
-- 
2.34.1