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