[NFC][llvm][StringMap]Extract createTable and getHashTable functions and add the inline attribute to the getMinBucketToReserveForEntries function.

[yihanaa]

Summary

1. Extract createTable and getHashTable functions.
2. Add the inline attribute to the getMinBucketToReserveForEntries function.
3. Remove unnecessary local variable HTSize.

Statements in the following order appear in llvm::StringMapImpl::init and llvm::StringMapImpl::RehashTable, so I extracted this code into a function. getHashTable is for the same reason, it appears in llvm::StringMapImpl::FindKey, llvm::StringMapImpl::LookupBucketFor and llvm::StringMapImpl::RehashTable.

auto **Table = static_cast<StringMapEntryBase **>(safe_calloc(
      NewNumBuckets + 1, sizeof(StringMapEntryBase **) + sizeof(unsigned)));

  // Allocate one extra bucket, set it to look filled so the iterators stop at
  // end.
  Table[NewNumBuckets] = (StringMapEntryBase *)2;

unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);

[SixWeining]

Thanks for adding me. I Just add some little comments since I'm not an expert about this. Maybe others could have a look.

llvm/lib/Support/StringMap.cpp

86–87

The { and } are unnecessary since there is only a single line in if.

220–221

I'm not sure this comment is necessary since the function createTable already has an internal comment.

[yihanaa]

In D121934#3391184, @SixWeining wrote:

Thanks for adding me. I Just add some little comments since I'm not an expert about this. Maybe others could have a look.

Thanks for your suggestion, i will remove these useless comments and re-upload the patch.

[skan]

it's a NFC patch?

[skan]

llvm/lib/Support/StringMap.cpp

21

This change is not reflected in the commit message...

57–65

I am not an expert here, Is it always safe to change the order of the three statements?

[yihanaa]

1. Reflected all the changes in the commit message.
2. Added some more detailed descriptions.

[yihanaa]

In D121934#3391204, @skan wrote:

it's a NFC patch?

it is an NFC patch

[yihanaa]

llvm/lib/Support/StringMap.cpp

57–65

I have updated the summary.

[yihanaa]

Reformat code.

[skan]

LGTM. The change is straightforward so far.

[skan]

Please wait for 2 days to see if there is any objection before landing it.

[yihanaa]

In D121934#3398822, @skan wrote:

Please wait for 2 days to see if there is any objection before landing it.

Thanks @skan. I don’t have commit access, can you land this patch for me? (if there are no objections after a few days) Please use “wangyihan [e-mail]” to commit the change.

[skan]

In D121934#3399083, @yihanaa wrote:

In D121934#3398822, @skan wrote:

Please wait for 2 days to see if there is any objection before landing it.

Thanks @skan. I don’t have commit access, can you land this patch for me? (if there are no objections after a few days) Please use “wangyihan [e-mail]” to commit the change.

Okay, I will do that.

[sepavloff]

LGTM too.

Thanks!

llvm/lib/Support/StringMap.cpp

 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/DJB.h"
 #include "llvm/Support/MathExtras.h"
 
 using namespace llvm;
 
 /// Returns the number of buckets to allocate to ensure that the DenseMap can
 /// accommodate \p NumEntries without need to grow().
-static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
+static inline unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
   // Ensure that "NumEntries * 4 < NumBuckets * 3"
   if (NumEntries == 0)
     return 0;
   // +1 is required because of the strict equality.
   // For example if NumEntries is 48, we need to return 401.
   return NextPowerOf2(NumEntries * 4 / 3 + 1);
 }
 
+static inline StringMapEntryBase **createTable(unsigned NewNumBuckets) {
+  auto **Table = static_cast<StringMapEntryBase **>(safe_calloc(
+      NewNumBuckets + 1, sizeof(StringMapEntryBase **) + sizeof(unsigned)));
+
+  // Allocate one extra bucket, set it to look filled so the iterators stop at
+  // end.
+  Table[NewNumBuckets] = (StringMapEntryBase *)2;
+  return Table;
+}
+
+static inline unsigned *getHashTable(StringMapEntryBase **TheTable,
+                                     unsigned NumBuckets) {
+  return reinterpret_cast<unsigned *>(TheTable + NumBuckets + 1);
+}
+
 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
   ItemSize = itemSize;
 
   // If a size is specified, initialize the table with that many buckets.
   if (InitSize) {
     // The table will grow when the number of entries reach 3/4 of the number of
     // buckets. To guarantee that "InitSize" number of entries can be inserted
     // in the table without growing, we allocate just what is needed here.

 void StringMapImpl::init(unsigned InitSize) {
   assert((InitSize & (InitSize - 1)) == 0 &&
          "Init Size must be a power of 2 or zero!");
 
   unsigned NewNumBuckets = InitSize ? InitSize : 16;
   NumItems = 0;
   NumTombstones = 0;
 
-  TheTable = static_cast<StringMapEntryBase **>(safe_calloc(
-      NewNumBuckets + 1, sizeof(StringMapEntryBase **) + sizeof(unsigned)));
+  TheTable = createTable(NewNumBuckets);
 
   // Set the member only if TheTable was successfully allocated
   NumBuckets = NewNumBuckets;
-
-  // Allocate one extra bucket, set it to look filled so the iterators stop at
-  // end.
-  TheTable[NumBuckets] = (StringMapEntryBase *)2;
 }
 
 /// LookupBucketFor - Look up the bucket that the specified string should end
 /// up in.  If it already exists as a key in the map, the Item pointer for the
 /// specified bucket will be non-null.  Otherwise, it will be null.  In either
 /// case, the FullHashValue field of the bucket will be set to the hash value
 /// of the string.
 unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
-  unsigned HTSize = NumBuckets;
-  if (HTSize == 0) { // Hash table unallocated so far?
+  // Hash table unallocated so far?
+  if (NumBuckets == 0)
     init(16);
-    HTSize = NumBuckets;
-  }
   unsigned FullHashValue = djbHash(Name, 0);
-  unsigned BucketNo = FullHashValue & (HTSize - 1);
-  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
+  unsigned BucketNo = FullHashValue & (NumBuckets - 1);
+  unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   int FirstTombstone = -1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return it.
     if (LLVM_LIKELY(!BucketItem)) {
       // If we found a tombstone, we want to reuse the tombstone instead of an
if (BucketItem == getTombstoneVal()) {
       char *ItemStr = (char *)BucketItem + ItemSize;
       if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
         // We found a match!
         return BucketNo;
       }
     }
 
     // Okay, we didn't find the item.  Probe to the next bucket.
-    BucketNo = (BucketNo + ProbeAmt) & (HTSize - 1);
+    BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);
 
     // Use quadratic probing, it has fewer clumping artifacts than linear
     // probing and has good cache behavior in the common case.
     ++ProbeAmt;
   }
 }
 
 /// FindKey - Look up the bucket that contains the specified key. If it exists
 /// in the map, return the bucket number of the key.  Otherwise return -1.
 /// This does not modify the map.
 int StringMapImpl::FindKey(StringRef Key) const {
-  unsigned HTSize = NumBuckets;
-  if (HTSize == 0)
+  if (NumBuckets == 0)
     return -1; // Really empty table?
   unsigned FullHashValue = djbHash(Key, 0);
-  unsigned BucketNo = FullHashValue & (HTSize - 1);
-  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
+  unsigned BucketNo = FullHashValue & (NumBuckets - 1);
+  unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   unsigned ProbeAmt = 1;
   while (true) {
     StringMapEntryBase *BucketItem = TheTable[BucketNo];
     // If we found an empty bucket, this key isn't in the table yet, return.
     if (LLVM_LIKELY(!BucketItem))
       return -1;
 
if (BucketItem == getTombstoneVal()) {
       char *ItemStr = (char *)BucketItem + ItemSize;
       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
         // We found a match!
         return BucketNo;
       }
     }
 
     // Okay, we didn't find the item.  Probe to the next bucket.
-    BucketNo = (BucketNo + ProbeAmt) & (HTSize - 1);
+    BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);
 
     // Use quadratic probing, it has fewer clumping artifacts than linear
     // probing and has good cache behavior in the common case.
     ++ProbeAmt;
   }
 }
 
 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
 
   return Result;
 }
 
 /// RehashTable - Grow the table, redistributing values into the buckets with
 /// the appropriate mod-of-hashtable-size.
 unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
   unsigned NewSize;
-  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
-
   // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
   // the buckets are empty (meaning that many are filled with tombstones),
   // grow/rehash the table.
   if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
     NewSize = NumBuckets * 2;
   } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=
                            NumBuckets / 8)) {
     NewSize = NumBuckets;
   } else {
     return BucketNo;
   }
 
   unsigned NewBucketNo = BucketNo;
-  // Allocate one extra bucket which will always be non-empty.  This allows the
-  // iterators to stop at end.
-  auto NewTableArray = static_cast<StringMapEntryBase **>(safe_calloc(
-      NewSize + 1, sizeof(StringMapEntryBase *) + sizeof(unsigned)));
-
-  unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
-  NewTableArray[NewSize] = (StringMapEntryBase *)2;
+  auto **NewTableArray = createTable(NewSize);
+  unsigned *NewHashArray = getHashTable(NewTableArray, NewSize);
+  unsigned *HashTable = getHashTable(TheTable, NumBuckets);
 
   // Rehash all the items into their new buckets.  Luckily :) we already have
   // the hash values available, so we don't have to rehash any strings.
   for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
     StringMapEntryBase *Bucket = TheTable[I];
     if (Bucket && Bucket != getTombstoneVal()) {
       // If the bucket is not available, probe for a spot.
       unsigned FullHash = HashTable[I];