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 
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 
42 TYPED_TEST(ValueMapTest, Null) {
43   ValueMap<TypeParam*, int> VM1;
44   VM1[NULL] = 7;
45   EXPECT_EQ(7, VM1.lookup(NULL));
46 }
47 
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 
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>
119 void CompileAssertHasType(VarType) {
120   LLVM_STATIC_ASSERT((is_same<ExpectedType, VarType>::value),
121                      "Not the same type");
122 }
123 
124 TYPED_TEST(ValueMapTest, Iteration) {
125   ValueMap<TypeParam*, int> VM;
126   VM[this->BitcastV.get()] = 2;
127   VM[this->AddV.get()] = 3;
128   size_t size = 0;
129   for (typename ValueMap<TypeParam*, int>::iterator I = VM.begin(), E = VM.end();
130        I != E; ++I) {
131     ++size;
132     std::pair<TypeParam*, int> value = *I; (void)value;
133     CompileAssertHasType<TypeParam*>(I->first);
134     if (I->second == 2) {
135       EXPECT_EQ(this->BitcastV.get(), I->first);
136       I->second = 5;
137     } else if (I->second == 3) {
138       EXPECT_EQ(this->AddV.get(), I->first);
139       I->second = 6;
140     } else {
141       ADD_FAILURE() << "Iterated through an extra value.";
142     }
143   }
144   EXPECT_EQ(2U, size);
145   EXPECT_EQ(5, VM[this->BitcastV.get()]);
146   EXPECT_EQ(6, VM[this->AddV.get()]);
147 
148   size = 0;
149   // Cast to const ValueMap to avoid a bug in DenseMap's iterators.
150   const ValueMap<TypeParam*, int>& CVM = VM;
151   for (typename ValueMap<TypeParam*, int>::const_iterator I = CVM.begin(),
152          E = CVM.end(); I != E; ++I) {
153     ++size;
154     std::pair<TypeParam*, int> value = *I;  (void)value;
155     CompileAssertHasType<TypeParam*>(I->first);
156     if (I->second == 5) {
157       EXPECT_EQ(this->BitcastV.get(), I->first);
158     } else if (I->second == 6) {
159       EXPECT_EQ(this->AddV.get(), I->first);
160     } else {
161       ADD_FAILURE() << "Iterated through an extra value.";
162     }
163   }
164   EXPECT_EQ(2U, size);
165 }
166 
167 TYPED_TEST(ValueMapTest, DefaultCollisionBehavior) {
168   // By default, we overwrite the old value with the replaced value.
169   ValueMap<TypeParam*, int> VM;
170   VM[this->BitcastV.get()] = 7;
171   VM[this->AddV.get()] = 9;
172   this->BitcastV->replaceAllUsesWith(this->AddV.get());
173   EXPECT_EQ(0, VM.count(this->BitcastV.get()));
174   EXPECT_EQ(9, VM.lookup(this->AddV.get()));
175 }
176 
177 TYPED_TEST(ValueMapTest, ConfiguredCollisionBehavior) {
178   // TODO: Implement this when someone needs it.
179 }
180 
181 template<typename KeyT>
182 struct LockMutex : ValueMapConfig<KeyT> {
183   struct ExtraData {
184     sys::Mutex *M;
185     bool *CalledRAUW;
186     bool *CalledDeleted;
187   };
188   static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) {
189     *Data.CalledRAUW = true;
190     EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked.";
191   }
192   static void onDelete(const ExtraData &Data, KeyT Old) {
193     *Data.CalledDeleted = true;
194     EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked.";
195   }
196   static sys::Mutex *getMutex(const ExtraData &Data) { return Data.M; }
197 };
198 #if LLVM_ENABLE_THREADS
199 TYPED_TEST(ValueMapTest, LocksMutex) {
200   sys::Mutex M(false);  // Not recursive.
201   bool CalledRAUW = false, CalledDeleted = false;
202   typename LockMutex<TypeParam*>::ExtraData Data =
203     {&M, &CalledRAUW, &CalledDeleted};
204   ValueMap<TypeParam*, int, LockMutex<TypeParam*> > VM(Data);
205   VM[this->BitcastV.get()] = 7;
206   this->BitcastV->replaceAllUsesWith(this->AddV.get());
207   this->AddV.reset();
208   EXPECT_TRUE(CalledRAUW);
209   EXPECT_TRUE(CalledDeleted);
210 }
211 #endif
212 
213 template<typename KeyT>
214 struct NoFollow : ValueMapConfig<KeyT> {
215   enum { FollowRAUW = false };
216 };
217 
218 TYPED_TEST(ValueMapTest, NoFollowRAUW) {
219   ValueMap<TypeParam*, int, NoFollow<TypeParam*> > VM;
220   VM[this->BitcastV.get()] = 7;
221   EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
222   EXPECT_EQ(0, VM.count(this->AddV.get()));
223   this->BitcastV->replaceAllUsesWith(this->AddV.get());
224   EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
225   EXPECT_EQ(0, VM.lookup(this->AddV.get()));
226   this->AddV.reset();
227   EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
228   EXPECT_EQ(0, VM.lookup(this->AddV.get()));
229   this->BitcastV.reset();
230   EXPECT_EQ(0, VM.lookup(this->BitcastV.get()));
231   EXPECT_EQ(0, VM.lookup(this->AddV.get()));
232   EXPECT_EQ(0U, VM.size());
233 }
234 
235 template<typename KeyT>
236 struct CountOps : ValueMapConfig<KeyT> {
237   struct ExtraData {
238     int *Deletions;
239     int *RAUWs;
240   };
241 
242   static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) {
243     ++*Data.RAUWs;
244   }
245   static void onDelete(const ExtraData &Data, KeyT Old) {
246     ++*Data.Deletions;
247   }
248 };
249 
250 TYPED_TEST(ValueMapTest, CallsConfig) {
251   int Deletions = 0, RAUWs = 0;
252   typename CountOps<TypeParam*>::ExtraData Data = {&Deletions, &RAUWs};
253   ValueMap<TypeParam*, int, CountOps<TypeParam*> > VM(Data);
254   VM[this->BitcastV.get()] = 7;
255   this->BitcastV->replaceAllUsesWith(this->AddV.get());
256   EXPECT_EQ(0, Deletions);
257   EXPECT_EQ(1, RAUWs);
258   this->AddV.reset();
259   EXPECT_EQ(1, Deletions);
260   EXPECT_EQ(1, RAUWs);
261   this->BitcastV.reset();
262   EXPECT_EQ(1, Deletions);
263   EXPECT_EQ(1, RAUWs);
264 }
265 
266 template<typename KeyT>
267 struct ModifyingConfig : ValueMapConfig<KeyT> {
268   // We'll put a pointer here back to the ValueMap this key is in, so
269   // that we can modify it (and clobber *this) before the ValueMap
270   // tries to do the same modification.  In previous versions of
271   // ValueMap, that exploded.
272   typedef ValueMap<KeyT, int, ModifyingConfig<KeyT> > **ExtraData;
273 
274   static void onRAUW(ExtraData Map, KeyT Old, KeyT New) {
275     (*Map)->erase(Old);
276   }
277   static void onDelete(ExtraData Map, KeyT Old) {
278     (*Map)->erase(Old);
279   }
280 };
281 TYPED_TEST(ValueMapTest, SurvivesModificationByConfig) {
282   ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > *MapAddress;
283   ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > VM(&MapAddress);
284   MapAddress = &VM;
285   // Now the ModifyingConfig can modify the Map inside a callback.
286   VM[this->BitcastV.get()] = 7;
287   this->BitcastV->replaceAllUsesWith(this->AddV.get());
288   EXPECT_FALSE(VM.count(this->BitcastV.get()));
289   EXPECT_FALSE(VM.count(this->AddV.get()));
290   VM[this->AddV.get()] = 7;
291   this->AddV.reset();
292   EXPECT_FALSE(VM.count(this->AddV.get()));
293 }
294 
295 }
296