1 //===- llvm/unittest/ADT/ValueMapTest.cpp - ValueMap unit tests -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/ADT/ValueMap.h"
11 #include "llvm/Instructions.h"
12 #include "llvm/LLVMContext.h"
13 #include "llvm/ADT/OwningPtr.h"
14 #include "llvm/Config/config.h"
16 #include "gtest/gtest.h"
24 class ValueMapTest : public testing::Test {
27 OwningPtr<BitCastInst> BitcastV;
28 OwningPtr<BinaryOperator> AddV;
31 ConstantV(ConstantInt::get(Type::getInt32Ty(getGlobalContext()), 0)),
32 BitcastV(new BitCastInst(ConstantV, Type::getInt32Ty(getGlobalContext()))),
33 AddV(BinaryOperator::CreateAdd(ConstantV, ConstantV)) {
37 // Run everything on Value*, a subtype to make sure that casting works as
38 // expected, and a const subtype to make sure we cast const correctly.
39 typedef ::testing::Types<Value, Instruction, const Instruction> KeyTypes;
40 TYPED_TEST_CASE(ValueMapTest, KeyTypes);
42 TYPED_TEST(ValueMapTest, CopyConstructor) {
43 ValueMap<TypeParam*, int> VM1;
44 VM1[this->AddV.get()] = 7;
45 ValueMap<TypeParam*, int> VM2(VM1);
47 EXPECT_TRUE(VM1.empty());
48 EXPECT_TRUE(VM2.empty());
51 TYPED_TEST(ValueMapTest, Null) {
52 ValueMap<TypeParam*, int> VM1;
54 EXPECT_EQ(7, VM1.lookup(NULL));
57 TYPED_TEST(ValueMapTest, FollowsValue) {
58 ValueMap<TypeParam*, int> VM;
59 VM[this->BitcastV.get()] = 7;
60 EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
61 EXPECT_EQ(0, VM.count(this->AddV.get()));
62 this->BitcastV->replaceAllUsesWith(this->AddV.get());
63 EXPECT_EQ(7, VM.lookup(this->AddV.get()));
64 EXPECT_EQ(0, VM.count(this->BitcastV.get()));
66 EXPECT_EQ(0, VM.count(this->AddV.get()));
67 EXPECT_EQ(0, VM.count(this->BitcastV.get()));
68 EXPECT_EQ(0U, VM.size());
71 TYPED_TEST(ValueMapTest, OperationsWork) {
72 ValueMap<TypeParam*, int> VM;
73 ValueMap<TypeParam*, int> VM2(16); (void)VM2;
74 typename ValueMapConfig<TypeParam*>::ExtraData Data;
75 ValueMap<TypeParam*, int> VM3(Data, 16); (void)VM3;
76 EXPECT_TRUE(VM.empty());
78 VM[this->BitcastV.get()] = 7;
81 typename ValueMap<TypeParam*, int>::iterator I =
82 VM.find(this->BitcastV.get());
83 ASSERT_TRUE(I != VM.end());
84 EXPECT_EQ(this->BitcastV.get(), I->first);
85 EXPECT_EQ(7, I->second);
86 EXPECT_TRUE(VM.find(this->AddV.get()) == VM.end());
89 const ValueMap<TypeParam*, int> &CVM = VM;
90 typename ValueMap<TypeParam*, int>::const_iterator CI =
91 CVM.find(this->BitcastV.get());
92 ASSERT_TRUE(CI != CVM.end());
93 EXPECT_EQ(this->BitcastV.get(), CI->first);
94 EXPECT_EQ(7, CI->second);
95 EXPECT_TRUE(CVM.find(this->AddV.get()) == CVM.end());
98 std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult1 =
99 VM.insert(std::make_pair(this->AddV.get(), 3));
100 EXPECT_EQ(this->AddV.get(), InsertResult1.first->first);
101 EXPECT_EQ(3, InsertResult1.first->second);
102 EXPECT_TRUE(InsertResult1.second);
103 EXPECT_EQ(true, VM.count(this->AddV.get()));
104 std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult2 =
105 VM.insert(std::make_pair(this->AddV.get(), 5));
106 EXPECT_EQ(this->AddV.get(), InsertResult2.first->first);
107 EXPECT_EQ(3, InsertResult2.first->second);
108 EXPECT_FALSE(InsertResult2.second);
111 VM.erase(InsertResult2.first);
112 EXPECT_EQ(0U, VM.count(this->AddV.get()));
113 EXPECT_EQ(1U, VM.count(this->BitcastV.get()));
114 VM.erase(this->BitcastV.get());
115 EXPECT_EQ(0U, VM.count(this->BitcastV.get()));
116 EXPECT_EQ(0U, VM.size());
119 SmallVector<std::pair<Instruction*, int>, 2> Elems;
120 Elems.push_back(std::make_pair(this->AddV.get(), 1));
121 Elems.push_back(std::make_pair(this->BitcastV.get(), 2));
122 VM.insert(Elems.begin(), Elems.end());
123 EXPECT_EQ(1, VM.lookup(this->AddV.get()));
124 EXPECT_EQ(2, VM.lookup(this->BitcastV.get()));
127 template<typename ExpectedType, typename VarType>
128 void CompileAssertHasType(VarType) {
129 typedef char assert[is_same<ExpectedType, VarType>::value ? 1 : -1];
132 TYPED_TEST(ValueMapTest, Iteration) {
133 ValueMap<TypeParam*, int> VM;
134 VM[this->BitcastV.get()] = 2;
135 VM[this->AddV.get()] = 3;
137 for (typename ValueMap<TypeParam*, int>::iterator I = VM.begin(), E = VM.end();
140 std::pair<TypeParam*, int> value = *I; (void)value;
141 CompileAssertHasType<TypeParam*>(I->first);
142 if (I->second == 2) {
143 EXPECT_EQ(this->BitcastV.get(), I->first);
145 } else if (I->second == 3) {
146 EXPECT_EQ(this->AddV.get(), I->first);
149 ADD_FAILURE() << "Iterated through an extra value.";
153 EXPECT_EQ(5, VM[this->BitcastV.get()]);
154 EXPECT_EQ(6, VM[this->AddV.get()]);
157 // Cast to const ValueMap to avoid a bug in DenseMap's iterators.
158 const ValueMap<TypeParam*, int>& CVM = VM;
159 for (typename ValueMap<TypeParam*, int>::const_iterator I = CVM.begin(),
160 E = CVM.end(); I != E; ++I) {
162 std::pair<TypeParam*, int> value = *I; (void)value;
163 CompileAssertHasType<TypeParam*>(I->first);
164 if (I->second == 5) {
165 EXPECT_EQ(this->BitcastV.get(), I->first);
166 } else if (I->second == 6) {
167 EXPECT_EQ(this->AddV.get(), I->first);
169 ADD_FAILURE() << "Iterated through an extra value.";
175 TYPED_TEST(ValueMapTest, DefaultCollisionBehavior) {
176 // By default, we overwrite the old value with the replaced value.
177 ValueMap<TypeParam*, int> VM;
178 VM[this->BitcastV.get()] = 7;
179 VM[this->AddV.get()] = 9;
180 this->BitcastV->replaceAllUsesWith(this->AddV.get());
181 EXPECT_EQ(0, VM.count(this->BitcastV.get()));
182 EXPECT_EQ(9, VM.lookup(this->AddV.get()));
185 TYPED_TEST(ValueMapTest, ConfiguredCollisionBehavior) {
186 // TODO: Implement this when someone needs it.
189 template<typename KeyT>
190 struct LockMutex : ValueMapConfig<KeyT> {
196 static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) {
197 *Data.CalledRAUW = true;
198 EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked.";
200 static void onDelete(const ExtraData &Data, KeyT Old) {
201 *Data.CalledDeleted = true;
202 EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked.";
204 static sys::Mutex *getMutex(const ExtraData &Data) { return Data.M; }
207 TYPED_TEST(ValueMapTest, LocksMutex) {
208 sys::Mutex M(false); // Not recursive.
209 bool CalledRAUW = false, CalledDeleted = false;
210 typename LockMutex<TypeParam*>::ExtraData Data =
211 {&M, &CalledRAUW, &CalledDeleted};
212 ValueMap<TypeParam*, int, LockMutex<TypeParam*> > VM(Data);
213 VM[this->BitcastV.get()] = 7;
214 this->BitcastV->replaceAllUsesWith(this->AddV.get());
216 EXPECT_TRUE(CalledRAUW);
217 EXPECT_TRUE(CalledDeleted);
221 template<typename KeyT>
222 struct NoFollow : ValueMapConfig<KeyT> {
223 enum { FollowRAUW = false };
226 TYPED_TEST(ValueMapTest, NoFollowRAUW) {
227 ValueMap<TypeParam*, int, NoFollow<TypeParam*> > VM;
228 VM[this->BitcastV.get()] = 7;
229 EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
230 EXPECT_EQ(0, VM.count(this->AddV.get()));
231 this->BitcastV->replaceAllUsesWith(this->AddV.get());
232 EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
233 EXPECT_EQ(0, VM.lookup(this->AddV.get()));
235 EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
236 EXPECT_EQ(0, VM.lookup(this->AddV.get()));
237 this->BitcastV.reset();
238 EXPECT_EQ(0, VM.lookup(this->BitcastV.get()));
239 EXPECT_EQ(0, VM.lookup(this->AddV.get()));
240 EXPECT_EQ(0U, VM.size());
243 template<typename KeyT>
244 struct CountOps : ValueMapConfig<KeyT> {
250 static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) {
253 static void onDelete(const ExtraData &Data, KeyT Old) {
258 TYPED_TEST(ValueMapTest, CallsConfig) {
259 int Deletions = 0, RAUWs = 0;
260 typename CountOps<TypeParam*>::ExtraData Data = {&Deletions, &RAUWs};
261 ValueMap<TypeParam*, int, CountOps<TypeParam*> > VM(Data);
262 VM[this->BitcastV.get()] = 7;
263 this->BitcastV->replaceAllUsesWith(this->AddV.get());
264 EXPECT_EQ(0, Deletions);
267 EXPECT_EQ(1, Deletions);
269 this->BitcastV.reset();
270 EXPECT_EQ(1, Deletions);
274 template<typename KeyT>
275 struct ModifyingConfig : ValueMapConfig<KeyT> {
276 // We'll put a pointer here back to the ValueMap this key is in, so
277 // that we can modify it (and clobber *this) before the ValueMap
278 // tries to do the same modification. In previous versions of
279 // ValueMap, that exploded.
280 typedef ValueMap<KeyT, int, ModifyingConfig<KeyT> > **ExtraData;
282 static void onRAUW(ExtraData Map, KeyT Old, KeyT New) {
285 static void onDelete(ExtraData Map, KeyT Old) {
289 TYPED_TEST(ValueMapTest, SurvivesModificationByConfig) {
290 ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > *MapAddress;
291 ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > VM(&MapAddress);
293 // Now the ModifyingConfig can modify the Map inside a callback.
294 VM[this->BitcastV.get()] = 7;
295 this->BitcastV->replaceAllUsesWith(this->AddV.get());
296 EXPECT_FALSE(VM.count(this->BitcastV.get()));
297 EXPECT_FALSE(VM.count(this->AddV.get()));
298 VM[this->AddV.get()] = 7;
300 EXPECT_FALSE(VM.count(this->AddV.get()));