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 | |
29 | ValueMapTest() |
30 | : ConstantV(ConstantInt::get(Ty: Type::getInt32Ty(C&: Context), V: 0)), |
31 | BitcastV(new BitCastInst(ConstantV, Type::getInt32Ty(C&: Context))), |
32 | AddV(BinaryOperator::CreateAdd(V1: ConstantV, V2: 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 | |
40 | TYPED_TEST(ValueMapTest, Null) { |
41 | ValueMap<TypeParam*, int> VM1; |
42 | VM1[nullptr] = 7; |
43 | EXPECT_EQ(7, VM1.lookup(nullptr)); |
44 | } |
45 | |
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 | |
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(Elt: std::make_pair(this->AddV.get(), 1)); |
110 | Elems.push_back(Elt: 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> |
117 | void CompileAssertHasType(VarType) { |
118 | static_assert(std::is_same_v<ExpectedType, VarType>, "Not the same type" ); |
119 | } |
120 | |
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 | |
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 | |
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 { |
181 | MutexT *; |
182 | bool *; |
183 | bool *; |
184 | }; |
185 | static void (const ExtraData &Data, KeyT Old, KeyT New) { |
186 | *Data.CalledRAUW = true; |
187 | EXPECT_FALSE(Data.M->try_lock()) << "Mutex should already be locked." ; |
188 | } |
189 | static void (const ExtraData &Data, KeyT Old) { |
190 | *Data.CalledDeleted = true; |
191 | EXPECT_FALSE(Data.M->try_lock()) << "Mutex should already be locked." ; |
192 | } |
193 | static MutexT *(const ExtraData &Data) { return Data.M; } |
194 | }; |
195 | // FIXME: These tests started failing on Windows. |
196 | #if LLVM_ENABLE_THREADS && !defined(_WIN32) |
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 | |
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 { |
236 | int *; |
237 | int *; |
238 | }; |
239 | |
240 | static void (const ExtraData &Data, KeyT Old, KeyT New) { |
241 | ++*Data.RAUWs; |
242 | } |
243 | static void (const ExtraData &Data, KeyT Old) { |
244 | ++*Data.Deletions; |
245 | } |
246 | }; |
247 | |
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> > **; |
271 | |
272 | static void onRAUW(ExtraData Map, KeyT Old, KeyT New) { |
273 | (*Map)->erase(Old); |
274 | } |
275 | static void onDelete(ExtraData Map, KeyT Old) { |
276 | (*Map)->erase(Old); |
277 | } |
278 | }; |
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 | |