1 //===- llvm/unittest/ADT/ValueMapTest.cpp - ValueMap unit tests -*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/ADT/ValueMap.h"
11 #include "llvm/ADT/OwningPtr.h"
12 #include "llvm/Config/llvm-config.h"
13 #include "llvm/IR/Constants.h"
14 #include "llvm/IR/Instructions.h"
15 #include "llvm/IR/LLVMContext.h"
16 #include "gtest/gtest.h"
17
18 using namespace llvm;
19
20 namespace {
21
22 // Test fixture
23 template<typename T>
24 class ValueMapTest : public testing::Test {
25 protected:
26 Constant *ConstantV;
27 OwningPtr<BitCastInst> BitcastV;
28 OwningPtr<BinaryOperator> AddV;
29
ValueMapTest()30 ValueMapTest() :
31 ConstantV(ConstantInt::get(Type::getInt32Ty(getGlobalContext()), 0)),
32 BitcastV(new BitCastInst(ConstantV, Type::getInt32Ty(getGlobalContext()))),
33 AddV(BinaryOperator::CreateAdd(ConstantV, ConstantV)) {
34 }
35 };
36
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);
41
TYPED_TEST(ValueMapTest,Null)42 TYPED_TEST(ValueMapTest, Null) {
43 ValueMap<TypeParam*, int> VM1;
44 VM1[NULL] = 7;
45 EXPECT_EQ(7, VM1.lookup(NULL));
46 }
47
TYPED_TEST(ValueMapTest,FollowsValue)48 TYPED_TEST(ValueMapTest, FollowsValue) {
49 ValueMap<TypeParam*, int> VM;
50 VM[this->BitcastV.get()] = 7;
51 EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
52 EXPECT_EQ(0, VM.count(this->AddV.get()));
53 this->BitcastV->replaceAllUsesWith(this->AddV.get());
54 EXPECT_EQ(7, VM.lookup(this->AddV.get()));
55 EXPECT_EQ(0, VM.count(this->BitcastV.get()));
56 this->AddV.reset();
57 EXPECT_EQ(0, VM.count(this->AddV.get()));
58 EXPECT_EQ(0, VM.count(this->BitcastV.get()));
59 EXPECT_EQ(0U, VM.size());
60 }
61
TYPED_TEST(ValueMapTest,OperationsWork)62 TYPED_TEST(ValueMapTest, OperationsWork) {
63 ValueMap<TypeParam*, int> VM;
64 ValueMap<TypeParam*, int> VM2(16); (void)VM2;
65 typename ValueMapConfig<TypeParam*>::ExtraData Data;
66 ValueMap<TypeParam*, int> VM3(Data, 16); (void)VM3;
67 EXPECT_TRUE(VM.empty());
68
69 VM[this->BitcastV.get()] = 7;
70
71 // Find:
72 typename ValueMap<TypeParam*, int>::iterator I =
73 VM.find(this->BitcastV.get());
74 ASSERT_TRUE(I != VM.end());
75 EXPECT_EQ(this->BitcastV.get(), I->first);
76 EXPECT_EQ(7, I->second);
77 EXPECT_TRUE(VM.find(this->AddV.get()) == VM.end());
78
79 // Const find:
80 const ValueMap<TypeParam*, int> &CVM = VM;
81 typename ValueMap<TypeParam*, int>::const_iterator CI =
82 CVM.find(this->BitcastV.get());
83 ASSERT_TRUE(CI != CVM.end());
84 EXPECT_EQ(this->BitcastV.get(), CI->first);
85 EXPECT_EQ(7, CI->second);
86 EXPECT_TRUE(CVM.find(this->AddV.get()) == CVM.end());
87
88 // Insert:
89 std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult1 =
90 VM.insert(std::make_pair(this->AddV.get(), 3));
91 EXPECT_EQ(this->AddV.get(), InsertResult1.first->first);
92 EXPECT_EQ(3, InsertResult1.first->second);
93 EXPECT_TRUE(InsertResult1.second);
94 EXPECT_EQ(true, VM.count(this->AddV.get()));
95 std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult2 =
96 VM.insert(std::make_pair(this->AddV.get(), 5));
97 EXPECT_EQ(this->AddV.get(), InsertResult2.first->first);
98 EXPECT_EQ(3, InsertResult2.first->second);
99 EXPECT_FALSE(InsertResult2.second);
100
101 // Erase:
102 VM.erase(InsertResult2.first);
103 EXPECT_EQ(0U, VM.count(this->AddV.get()));
104 EXPECT_EQ(1U, VM.count(this->BitcastV.get()));
105 VM.erase(this->BitcastV.get());
106 EXPECT_EQ(0U, VM.count(this->BitcastV.get()));
107 EXPECT_EQ(0U, VM.size());
108
109 // Range insert:
110 SmallVector<std::pair<Instruction*, int>, 2> Elems;
111 Elems.push_back(std::make_pair(this->AddV.get(), 1));
112 Elems.push_back(std::make_pair(this->BitcastV.get(), 2));
113 VM.insert(Elems.begin(), Elems.end());
114 EXPECT_EQ(1, VM.lookup(this->AddV.get()));
115 EXPECT_EQ(2, VM.lookup(this->BitcastV.get()));
116 }
117
118 template<typename ExpectedType, typename VarType>
CompileAssertHasType(VarType)119 void CompileAssertHasType(VarType) {
120 typedef char assert[is_same<ExpectedType, VarType>::value ? 1 : -1];
121 }
122
TYPED_TEST(ValueMapTest,Iteration)123 TYPED_TEST(ValueMapTest, Iteration) {
124 ValueMap<TypeParam*, int> VM;
125 VM[this->BitcastV.get()] = 2;
126 VM[this->AddV.get()] = 3;
127 size_t size = 0;
128 for (typename ValueMap<TypeParam*, int>::iterator I = VM.begin(), E = VM.end();
129 I != E; ++I) {
130 ++size;
131 std::pair<TypeParam*, int> value = *I; (void)value;
132 CompileAssertHasType<TypeParam*>(I->first);
133 if (I->second == 2) {
134 EXPECT_EQ(this->BitcastV.get(), I->first);
135 I->second = 5;
136 } else if (I->second == 3) {
137 EXPECT_EQ(this->AddV.get(), I->first);
138 I->second = 6;
139 } else {
140 ADD_FAILURE() << "Iterated through an extra value.";
141 }
142 }
143 EXPECT_EQ(2U, size);
144 EXPECT_EQ(5, VM[this->BitcastV.get()]);
145 EXPECT_EQ(6, VM[this->AddV.get()]);
146
147 size = 0;
148 // Cast to const ValueMap to avoid a bug in DenseMap's iterators.
149 const ValueMap<TypeParam*, int>& CVM = VM;
150 for (typename ValueMap<TypeParam*, int>::const_iterator I = CVM.begin(),
151 E = CVM.end(); I != E; ++I) {
152 ++size;
153 std::pair<TypeParam*, int> value = *I; (void)value;
154 CompileAssertHasType<TypeParam*>(I->first);
155 if (I->second == 5) {
156 EXPECT_EQ(this->BitcastV.get(), I->first);
157 } else if (I->second == 6) {
158 EXPECT_EQ(this->AddV.get(), I->first);
159 } else {
160 ADD_FAILURE() << "Iterated through an extra value.";
161 }
162 }
163 EXPECT_EQ(2U, size);
164 }
165
TYPED_TEST(ValueMapTest,DefaultCollisionBehavior)166 TYPED_TEST(ValueMapTest, DefaultCollisionBehavior) {
167 // By default, we overwrite the old value with the replaced value.
168 ValueMap<TypeParam*, int> VM;
169 VM[this->BitcastV.get()] = 7;
170 VM[this->AddV.get()] = 9;
171 this->BitcastV->replaceAllUsesWith(this->AddV.get());
172 EXPECT_EQ(0, VM.count(this->BitcastV.get()));
173 EXPECT_EQ(9, VM.lookup(this->AddV.get()));
174 }
175
TYPED_TEST(ValueMapTest,ConfiguredCollisionBehavior)176 TYPED_TEST(ValueMapTest, ConfiguredCollisionBehavior) {
177 // TODO: Implement this when someone needs it.
178 }
179
180 template<typename KeyT>
181 struct LockMutex : ValueMapConfig<KeyT> {
182 struct ExtraData {
183 sys::Mutex *M;
184 bool *CalledRAUW;
185 bool *CalledDeleted;
186 };
onRAUW__anonc548d39d0111::LockMutex187 static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) {
188 *Data.CalledRAUW = true;
189 EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked.";
190 }
onDelete__anonc548d39d0111::LockMutex191 static void onDelete(const ExtraData &Data, KeyT Old) {
192 *Data.CalledDeleted = true;
193 EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked.";
194 }
getMutex__anonc548d39d0111::LockMutex195 static sys::Mutex *getMutex(const ExtraData &Data) { return Data.M; }
196 };
197 #if LLVM_ENABLE_THREADS
TYPED_TEST(ValueMapTest,LocksMutex)198 TYPED_TEST(ValueMapTest, LocksMutex) {
199 sys::Mutex M(false); // Not recursive.
200 bool CalledRAUW = false, CalledDeleted = false;
201 typename LockMutex<TypeParam*>::ExtraData Data =
202 {&M, &CalledRAUW, &CalledDeleted};
203 ValueMap<TypeParam*, int, LockMutex<TypeParam*> > VM(Data);
204 VM[this->BitcastV.get()] = 7;
205 this->BitcastV->replaceAllUsesWith(this->AddV.get());
206 this->AddV.reset();
207 EXPECT_TRUE(CalledRAUW);
208 EXPECT_TRUE(CalledDeleted);
209 }
210 #endif
211
212 template<typename KeyT>
213 struct NoFollow : ValueMapConfig<KeyT> {
214 enum { FollowRAUW = false };
215 };
216
TYPED_TEST(ValueMapTest,NoFollowRAUW)217 TYPED_TEST(ValueMapTest, NoFollowRAUW) {
218 ValueMap<TypeParam*, int, NoFollow<TypeParam*> > VM;
219 VM[this->BitcastV.get()] = 7;
220 EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
221 EXPECT_EQ(0, VM.count(this->AddV.get()));
222 this->BitcastV->replaceAllUsesWith(this->AddV.get());
223 EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
224 EXPECT_EQ(0, VM.lookup(this->AddV.get()));
225 this->AddV.reset();
226 EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
227 EXPECT_EQ(0, VM.lookup(this->AddV.get()));
228 this->BitcastV.reset();
229 EXPECT_EQ(0, VM.lookup(this->BitcastV.get()));
230 EXPECT_EQ(0, VM.lookup(this->AddV.get()));
231 EXPECT_EQ(0U, VM.size());
232 }
233
234 template<typename KeyT>
235 struct CountOps : ValueMapConfig<KeyT> {
236 struct ExtraData {
237 int *Deletions;
238 int *RAUWs;
239 };
240
onRAUW__anonc548d39d0111::CountOps241 static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) {
242 ++*Data.RAUWs;
243 }
onDelete__anonc548d39d0111::CountOps244 static void onDelete(const ExtraData &Data, KeyT Old) {
245 ++*Data.Deletions;
246 }
247 };
248
TYPED_TEST(ValueMapTest,CallsConfig)249 TYPED_TEST(ValueMapTest, CallsConfig) {
250 int Deletions = 0, RAUWs = 0;
251 typename CountOps<TypeParam*>::ExtraData Data = {&Deletions, &RAUWs};
252 ValueMap<TypeParam*, int, CountOps<TypeParam*> > VM(Data);
253 VM[this->BitcastV.get()] = 7;
254 this->BitcastV->replaceAllUsesWith(this->AddV.get());
255 EXPECT_EQ(0, Deletions);
256 EXPECT_EQ(1, RAUWs);
257 this->AddV.reset();
258 EXPECT_EQ(1, Deletions);
259 EXPECT_EQ(1, RAUWs);
260 this->BitcastV.reset();
261 EXPECT_EQ(1, Deletions);
262 EXPECT_EQ(1, RAUWs);
263 }
264
265 template<typename KeyT>
266 struct ModifyingConfig : ValueMapConfig<KeyT> {
267 // We'll put a pointer here back to the ValueMap this key is in, so
268 // that we can modify it (and clobber *this) before the ValueMap
269 // tries to do the same modification. In previous versions of
270 // ValueMap, that exploded.
271 typedef ValueMap<KeyT, int, ModifyingConfig<KeyT> > **ExtraData;
272
onRAUW__anonc548d39d0111::ModifyingConfig273 static void onRAUW(ExtraData Map, KeyT Old, KeyT New) {
274 (*Map)->erase(Old);
275 }
onDelete__anonc548d39d0111::ModifyingConfig276 static void onDelete(ExtraData Map, KeyT Old) {
277 (*Map)->erase(Old);
278 }
279 };
TYPED_TEST(ValueMapTest,SurvivesModificationByConfig)280 TYPED_TEST(ValueMapTest, SurvivesModificationByConfig) {
281 ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > *MapAddress;
282 ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > VM(&MapAddress);
283 MapAddress = &VM;
284 // Now the ModifyingConfig can modify the Map inside a callback.
285 VM[this->BitcastV.get()] = 7;
286 this->BitcastV->replaceAllUsesWith(this->AddV.get());
287 EXPECT_FALSE(VM.count(this->BitcastV.get()));
288 EXPECT_FALSE(VM.count(this->AddV.get()));
289 VM[this->AddV.get()] = 7;
290 this->AddV.reset();
291 EXPECT_FALSE(VM.count(this->AddV.get()));
292 }
293
294 }
295