Index: include/llvm/ADT/DenseMap.h =================================================================== --- include/llvm/ADT/DenseMap.h +++ include/llvm/ADT/DenseMap.h @@ -195,6 +195,26 @@ 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 + std::pair insert_as(std::pair &&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 void insert(InputIt I, InputIt E) { @@ -399,7 +419,7 @@ 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); @@ -408,7 +428,7 @@ 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)); @@ -416,14 +436,26 @@ } 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; + } + + template + 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; } - BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { + template + 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 @@ -439,12 +471,12 @@ 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); Index: lib/IR/ConstantsContext.h =================================================================== --- lib/IR/ConstantsContext.h +++ lib/IR/ConstantsContext.h @@ -552,6 +552,9 @@ typedef typename ConstantInfo::TypeClass TypeClass; typedef std::pair LookupKey; + /// Key and hash together, so that we compute the hash only once and reuse it. + typedef std::pair LookupKeyHashed; + private: struct MapInfo { typedef DenseMapInfo ConstantClassInfo; @@ -571,6 +574,9 @@ 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; @@ -578,6 +584,9 @@ return false; return LHS.second == RHS; } + static bool isEqual(const LookupKeyHashed &LHS, const ConstantClass *RHS) { + return isEqual(LHS.second, RHS); + } }; public: @@ -595,13 +604,12 @@ // 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; } @@ -609,12 +617,15 @@ 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"); @@ -622,14 +633,6 @@ 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); @@ -642,8 +645,11 @@ 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; @@ -659,7 +665,7 @@ if (CP->getOperand(I) == From) CP->setOperand(I, To); } - insert(CP); + Map.insert_as(std::make_pair(CP, '\0'), Lookup); return nullptr; }