Add a new insert_as() method to DenseMap and use it for ConstantUniqueMap

Summary:
Just like the existing find_as() method, the new insert_as() accepts
an extra parameter which is used as a key to find the bucket in the
map.
When creating a Constant, we want to check the map before actually
creating the object. In this case we have to perform two queries to
the map, and this extra parameter can save recomputing the hash value
for the second query.

Reviewers: dexonsmith, chandlerc

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D16268

From: Mehdi Amini <mehdi.amini@apple.com>

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@260458 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 23 insertions, 17 deletions

diff --git a/lib/IR/ConstantsContext.h b/lib/IR/ConstantsContext.h
index a03279554c5..e87e23128fc 100644
--- a/lib/IR/ConstantsContext.h
+++ b/lib/IR/ConstantsContext.h
@@ -546,6 +546,9 @@ public:
   typedef typename ConstantInfo<ConstantClass>::TypeClass TypeClass;
   typedef std::pair<TypeClass *, ValType> LookupKey;
 
+  /// Key and hash together, so that we compute the hash only once and reuse it.
+  typedef std::pair<unsigned, LookupKey> LookupKeyHashed;
+
 private:
   struct MapInfo {
     typedef DenseMapInfo<ConstantClass *> ConstantClassInfo;
@@ -565,6 +568,9 @@ private:
     static unsigned getHashValue(const LookupKey &Val) {
       return hash_combine(Val.first, Val.second.getHash());
     }
+    static unsigned getHashValue(const LookupKeyHashed &Val) {
+      return Val.first;
+    }
     static bool isEqual(const LookupKey &LHS, const ConstantClass *RHS) {
       if (RHS == getEmptyKey() || RHS == getTombstoneKey())
         return false;
@@ -572,6 +578,9 @@ private:
         return false;
       return LHS.second == RHS;
     }
+    static bool isEqual(const LookupKeyHashed &LHS, const ConstantClass *RHS) {
+      return isEqual(LHS.second, RHS);
+    }
   };
 
 public:
@@ -589,13 +598,12 @@ public:
       // Asserts that use_empty().
       delete I.first;
   }
-
 private:
-  ConstantClass *create(TypeClass *Ty, ValType V) {
+  ConstantClass *create(TypeClass *Ty, ValType V, LookupKeyHashed &HashKey) {
     ConstantClass *Result = V.create(Ty);
 
     assert(Result->getType() == Ty && "Type specified is not correct!");
-    insert(Result);
+    Map.insert_as(std::make_pair(Result, '\0'), HashKey);
 
     return Result;
   }
@@ -603,12 +611,15 @@ private:
 public:
   /// Return the specified constant from the map, creating it if necessary.
   ConstantClass *getOrCreate(TypeClass *Ty, ValType V) {
-    LookupKey Lookup(Ty, V);
+    LookupKey Key(Ty, V);
+    /// Hash once, and reuse it for the lookup and the insertion if needed.
+    LookupKeyHashed Lookup(MapInfo::getHashValue(Key), Key);
+
     ConstantClass *Result = nullptr;
 
-    auto I = find(Lookup);
+    auto I = Map.find_as(Lookup);
     if (I == Map.end())
-      Result = create(Ty, V);
+      Result = create(Ty, V, Lookup);
     else
       Result = I->first;
     assert(Result && "Unexpected nullptr");
@@ -616,14 +627,6 @@ public:
     return Result;
   }
 
-  /// Find the constant by lookup key.
-  typename MapTy::iterator find(LookupKey Lookup) {
-    return Map.find_as(Lookup);
-  }
-
-  /// Insert the constant into its proper slot.
-  void insert(ConstantClass *CP) { Map[CP] = '\0'; }
-
   /// Remove this constant from the map
   void remove(ConstantClass *CP) {
     typename MapTy::iterator I = Map.find(CP);
@@ -636,8 +639,11 @@ public:
                                         ConstantClass *CP, Value *From,
                                         Constant *To, unsigned NumUpdated = 0,
                                         unsigned OperandNo = ~0u) {
-    LookupKey Lookup(CP->getType(), ValType(Operands, CP));
-    auto I = find(Lookup);
+    LookupKey Key(CP->getType(), ValType(Operands, CP));
+    /// Hash once, and reuse it for the lookup and the insertion if needed.
+    LookupKeyHashed Lookup(MapInfo::getHashValue(Key), Key);
+
+    auto I = Map.find_as(Lookup);
     if (I != Map.end())
       return I->first;
 
@@ -653,7 +659,7 @@ public:
         if (CP->getOperand(I) == From)
           CP->setOperand(I, To);
     }
-    insert(CP);
+    Map.insert_as(std::make_pair(CP, '\0'), Lookup);
     return nullptr;
   }