summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/ADT/DenseMap.h44
-rw-r--r--llvm/lib/IR/ConstantsContext.h40
2 files changed, 61 insertions, 23 deletions
diff --git a/llvm/include/llvm/ADT/DenseMap.h b/llvm/include/llvm/ADT/DenseMap.h
index 6ee1960b5c8..4cf0d6d328b 100644
--- a/llvm/include/llvm/ADT/DenseMap.h
+++ b/llvm/include/llvm/ADT/DenseMap.h
@@ -195,6 +195,26 @@ public:
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) {
@@ -399,7 +419,7 @@ private:
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 @@ private:
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 @@ private:
}
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 <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;
}
- BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *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
@@ -439,12 +471,12 @@ private:
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);
diff --git a/llvm/lib/IR/ConstantsContext.h b/llvm/lib/IR/ConstantsContext.h
index a03279554c5..e87e23128fc 100644
--- a/llvm/lib/IR/ConstantsContext.h
+++ b/llvm/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;
}
OpenPOWER on IntegriCloud