From 41ef09a4b56f8dcd2a2b234a61a5fdf7388cb472 Mon Sep 17 00:00:00 2001
From: Pete Cooper <peter_cooper@apple.com>
Date: Tue, 23 Oct 2012 19:34:36 +0000
Subject: [PATCH] Change DenseMap to use a power of 2 growth if one is given
 instead of the next power of 2.  This was causing DenseMaps to grow 4x
 instead of 2x.  I'll keep an eye on the buildbots as this could impact
 performance

llvm-svn: 166493
---
 llvm/include/llvm/ADT/DenseMap.h | 11 +++++++----
 1 file changed, 7 insertions(+), 4 deletions(-)

diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h
index 0ae54f4..ce07f8e 100644
--- a/llvm/include/llvm/ADT/DenseMap.h
+++ b/llvm/include/llvm/ADT/DenseMap.h
@@ -420,7 +420,7 @@ private:
       NumBuckets = getNumBuckets();
     }
     if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) {
-      this->grow(NumBuckets);
+      this->grow(NumBuckets * 2);
       LookupBucketFor(Key, TheBucket);
     }
     assert(TheBucket);
@@ -600,7 +600,8 @@ public:
     unsigned OldNumBuckets = NumBuckets;
     BucketT *OldBuckets = Buckets;
 
-    allocateBuckets(std::max<unsigned>(64, NextPowerOf2(AtLeast)));
+    AtLeast = isPowerOf2_32(AtLeast) ? AtLeast : NextPowerOf2(AtLeast);
+    allocateBuckets(std::max<unsigned>(64, AtLeast));
     assert(Buckets);
     if (!OldBuckets) {
       this->BaseT::initEmpty();
@@ -826,8 +827,10 @@ public:
   }
 
   void grow(unsigned AtLeast) {
-    if (AtLeast >= InlineBuckets)
-      AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast));
+    if (AtLeast >= InlineBuckets) {
+      AtLeast = isPowerOf2_32(AtLeast) ? AtLeast : NextPowerOf2(AtLeast);
+      AtLeast = std::max<unsigned>(64, AtLeast);
+    }
 
     if (Small) {
       if (AtLeast < InlineBuckets)
-- 
2.7.4