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

[mehdi_amini]

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.

[dexonsmith]

LGTM. In the DenseMapInfo, it might be cleaner to store the hash
in the LookupKey as an Optional<unsigned> rather than creating a
third type that the DenseMapInfo understands, but I'm not sure.
Either way seems fine.

[hfinkel]

LGTM too.

[mehdi_amini]

r260458.

I couldn't figure an easy way to merge the two keys, but I only tried to add the hash as an optional in a "tuple" (I guess it requires to expand to a custom class).

include/llvm/ADT/DenseMap.h

std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
     // Otherwise, insert the new element.
     TheBucket = InsertIntoBucket(std::move(KV.first),
                                  std::move(KV.second),
                                  TheBucket);
     return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
                           true);
   }
 
+  /// Alternate version of insert() which allows a different, and possibly
+  /// less expensive, key type.
+  /// The DenseMapInfo is responsible for supplying methods
+  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
+  /// type used.
+  template <typename LookupKeyT>
+  std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
+                                      const LookupKeyT &Val) {
+    BucketT *TheBucket;
+    if (LookupBucketFor(Val, TheBucket))
+      return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
+                            false); // Already in map.
+
+    // Otherwise, insert the new element.
+    TheBucket = InsertIntoBucket(std::move(KV.first), std::move(KV.second), Val,
+                                 TheBucket);
+    return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
+                          true);
+  }
+
   /// insert - Range insertion of pairs.
   template<typename InputIt>
   void insert(InputIt I, InputIt E) {
     for (; I != E; ++I)
       insert(*I);
   }
 
 
private:
 
   void shrink_and_clear() {
     static_cast<DerivedT *>(this)->shrink_and_clear();
   }
 
 
   BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
                             BucketT *TheBucket) {
-    TheBucket = InsertIntoBucketImpl(Key, TheBucket);
+    TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
 
     TheBucket->getFirst() = Key;
     ::new (&TheBucket->getSecond()) ValueT(Value);
     return TheBucket;
   }
 
   BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value,
                             BucketT *TheBucket) {
-    TheBucket = InsertIntoBucketImpl(Key, TheBucket);
+    TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
 
     TheBucket->getFirst() = Key;
     ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
     return TheBucket;
   }
 
   BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) {
-    TheBucket = InsertIntoBucketImpl(Key, TheBucket);
+    TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
 
     TheBucket->getFirst() = std::move(Key);
     ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
     return TheBucket;
   }
 
-  BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) {
+  template <typename LookupKeyT>
+  BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, LookupKeyT &Lookup,
+                            BucketT *TheBucket) {
+    TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);
+
+    TheBucket->getFirst() = std::move(Key);
+    ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
+    return TheBucket;
+  }
+
+  template <typename LookupKeyT>
+  BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
+                                BucketT *TheBucket) {
     incrementEpoch();
 
     // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
     // the buckets are empty (meaning that many are filled with tombstones),
     // grow the table.
     //
     // The later case is tricky.  For example, if we had one empty bucket with
     // tons of tombstones, failing lookups (e.g. for insertion) would have to
     // probe almost the entire table until it found the empty bucket.  If the
     // table completely filled with tombstones, no lookup would ever succeed,
     // causing infinite loops in lookup.
     unsigned NewNumEntries = getNumEntries() + 1;
     unsigned NumBuckets = getNumBuckets();
     if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
       this->grow(NumBuckets * 2);
-      LookupBucketFor(Key, TheBucket);
+      LookupBucketFor(Lookup, TheBucket);
       NumBuckets = getNumBuckets();
     } else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
                              NumBuckets/8)) {
       this->grow(NumBuckets);
-      LookupBucketFor(Key, TheBucket);
+      LookupBucketFor(Lookup, TheBucket);
     }
     assert(TheBucket);
 
     // Only update the state after we've grown our bucket space appropriately
     // so that when growing buckets we have self-consistent entry count.
     incrementNumEntries();
 
     // If we are writing over a tombstone, remember this.

lib/IR/ConstantsContext.h

 };
 
 template <class ConstantClass> class ConstantUniqueMap {
 public:
   typedef typename ConstantInfo<ConstantClass>::ValType ValType;
   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;
     static inline ConstantClass *getEmptyKey() {
       return ConstantClassInfo::getEmptyKey();
     }
     static inline ConstantClass *getTombstoneKey() {
       return ConstantClassInfo::getTombstoneKey();
     }
     static unsigned getHashValue(const ConstantClass *CP) {
       SmallVector<Constant *, 8> Storage;
       return getHashValue(LookupKey(CP->getType(), ValType(CP, Storage)));
     }
     static bool isEqual(const ConstantClass *LHS, const ConstantClass *RHS) {
       return LHS == RHS;
     }
     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;
       if (LHS.first != RHS->getType())
         return false;
       return LHS.second == RHS;
     }
+    static bool isEqual(const LookupKeyHashed &LHS, const ConstantClass *RHS) {
+      return isEqual(LHS.second, RHS);
+    }
   };
 
 public:
   typedef DenseMap<ConstantClass *, char, MapInfo> MapTy;
 
 private:
   MapTy Map;
 
 public:
   typename MapTy::iterator map_begin() { return Map.begin(); }
   typename MapTy::iterator map_end() { return Map.end(); }
 
   void freeConstants() {
     for (auto &I : Map)
       // 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;
   }
 
 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");
 
     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);
     assert(I != Map.end() && "Constant not found in constant table!");
     assert(I->first == CP && "Didn't find correct element?");
     Map.erase(I);
   }
 
   ConstantClass *replaceOperandsInPlace(ArrayRef<Constant *> Operands,
                                         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;
 
     // Update to the new value.  Optimize for the case when we have a single
     // operand that we're changing, but handle bulk updates efficiently.
     remove(CP);
     if (NumUpdated == 1) {
       assert(OperandNo < CP->getNumOperands() && "Invalid index");
       assert(CP->getOperand(OperandNo) != To && "I didn't contain From!");
       CP->setOperand(OperandNo, To);
     } else {
       for (unsigned I = 0, E = CP->getNumOperands(); I != E; ++I)
         if (CP->getOperand(I) == From)
           CP->setOperand(I, To);
     }
-    insert(CP);
+    Map.insert_as(std::make_pair(CP, '\0'), Lookup);
     return nullptr;
   }
 
   void dump() const { DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n"); }
 };
 
 } // end namespace llvm
 
 #endif