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/IR/ValueMap.h"
11#include "llvm/Config/llvm-config.h"
12#include "llvm/IR/Constants.h"
13#include "llvm/IR/Instructions.h"
14#include "llvm/IR/LLVMContext.h"
15#include "gtest/gtest.h"
16
17using namespace llvm;
18
19namespace {
20
21// Test fixture
22template<typename T>
23class ValueMapTest : public testing::Test {
24protected:
25  Constant *ConstantV;
26  std::unique_ptr<BitCastInst> BitcastV;
27  std::unique_ptr<BinaryOperator> AddV;
28
29  ValueMapTest() :
30    ConstantV(ConstantInt::get(Type::getInt32Ty(getGlobalContext()), 0)),
31    BitcastV(new BitCastInst(ConstantV, Type::getInt32Ty(getGlobalContext()))),
32    AddV(BinaryOperator::CreateAdd(ConstantV, ConstantV)) {
33  }
34};
35
36// Run everything on Value*, a subtype to make sure that casting works as
37// expected, and a const subtype to make sure we cast const correctly.
38typedef ::testing::Types<Value, Instruction, const Instruction> KeyTypes;
39TYPED_TEST_CASE(ValueMapTest, KeyTypes);
40
41TYPED_TEST(ValueMapTest, Null) {
42  ValueMap<TypeParam*, int> VM1;
43  VM1[nullptr] = 7;
44  EXPECT_EQ(7, VM1.lookup(nullptr));
45}
46
47TYPED_TEST(ValueMapTest, FollowsValue) {
48  ValueMap<TypeParam*, int> VM;
49  VM[this->BitcastV.get()] = 7;
50  EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
51  EXPECT_EQ(0u, VM.count(this->AddV.get()));
52  this->BitcastV->replaceAllUsesWith(this->AddV.get());
53  EXPECT_EQ(7, VM.lookup(this->AddV.get()));
54  EXPECT_EQ(0u, VM.count(this->BitcastV.get()));
55  this->AddV.reset();
56  EXPECT_EQ(0u, VM.count(this->AddV.get()));
57  EXPECT_EQ(0u, VM.count(this->BitcastV.get()));
58  EXPECT_EQ(0U, VM.size());
59}
60
61TYPED_TEST(ValueMapTest, OperationsWork) {
62  ValueMap<TypeParam*, int> VM;
63  ValueMap<TypeParam*, int> VM2(16);  (void)VM2;
64  typename ValueMapConfig<TypeParam*>::ExtraData Data;
65  ValueMap<TypeParam*, int> VM3(Data, 16);  (void)VM3;
66  EXPECT_TRUE(VM.empty());
67
68  VM[this->BitcastV.get()] = 7;
69
70  // Find:
71  typename ValueMap<TypeParam*, int>::iterator I =
72    VM.find(this->BitcastV.get());
73  ASSERT_TRUE(I != VM.end());
74  EXPECT_EQ(this->BitcastV.get(), I->first);
75  EXPECT_EQ(7, I->second);
76  EXPECT_TRUE(VM.find(this->AddV.get()) == VM.end());
77
78  // Const find:
79  const ValueMap<TypeParam*, int> &CVM = VM;
80  typename ValueMap<TypeParam*, int>::const_iterator CI =
81    CVM.find(this->BitcastV.get());
82  ASSERT_TRUE(CI != CVM.end());
83  EXPECT_EQ(this->BitcastV.get(), CI->first);
84  EXPECT_EQ(7, CI->second);
85  EXPECT_TRUE(CVM.find(this->AddV.get()) == CVM.end());
86
87  // Insert:
88  std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult1 =
89    VM.insert(std::make_pair(this->AddV.get(), 3));
90  EXPECT_EQ(this->AddV.get(), InsertResult1.first->first);
91  EXPECT_EQ(3, InsertResult1.first->second);
92  EXPECT_TRUE(InsertResult1.second);
93  EXPECT_EQ(1u, VM.count(this->AddV.get()));
94  std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult2 =
95    VM.insert(std::make_pair(this->AddV.get(), 5));
96  EXPECT_EQ(this->AddV.get(), InsertResult2.first->first);
97  EXPECT_EQ(3, InsertResult2.first->second);
98  EXPECT_FALSE(InsertResult2.second);
99
100  // Erase:
101  VM.erase(InsertResult2.first);
102  EXPECT_EQ(0U, VM.count(this->AddV.get()));
103  EXPECT_EQ(1U, VM.count(this->BitcastV.get()));
104  VM.erase(this->BitcastV.get());
105  EXPECT_EQ(0U, VM.count(this->BitcastV.get()));
106  EXPECT_EQ(0U, VM.size());
107
108  // Range insert:
109  SmallVector<std::pair<Instruction*, int>, 2> Elems;
110  Elems.push_back(std::make_pair(this->AddV.get(), 1));
111  Elems.push_back(std::make_pair(this->BitcastV.get(), 2));
112  VM.insert(Elems.begin(), Elems.end());
113  EXPECT_EQ(1, VM.lookup(this->AddV.get()));
114  EXPECT_EQ(2, VM.lookup(this->BitcastV.get()));
115}
116
117template<typename ExpectedType, typename VarType>
118void CompileAssertHasType(VarType) {
119  static_assert(std::is_same<ExpectedType, VarType>::value,
120                "Not the same type");
121}
122
123TYPED_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
166TYPED_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(0u, VM.count(this->BitcastV.get()));
173  EXPECT_EQ(9, VM.lookup(this->AddV.get()));
174}
175
176TYPED_TEST(ValueMapTest, ConfiguredCollisionBehavior) {
177  // TODO: Implement this when someone needs it.
178}
179
180template<typename KeyT, typename MutexT>
181struct LockMutex : ValueMapConfig<KeyT, MutexT> {
182  struct ExtraData {
183    MutexT *M;
184    bool *CalledRAUW;
185    bool *CalledDeleted;
186  };
187  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  }
191  static void onDelete(const ExtraData &Data, KeyT Old) {
192    *Data.CalledDeleted = true;
193    EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked.";
194  }
195  static MutexT *getMutex(const ExtraData &Data) { return Data.M; }
196};
197#if LLVM_ENABLE_THREADS
198TYPED_TEST(ValueMapTest, LocksMutex) {
199  sys::Mutex M(false);  // Not recursive.
200  bool CalledRAUW = false, CalledDeleted = false;
201  typedef LockMutex<TypeParam*, sys::Mutex> ConfigType;
202  typename ConfigType::ExtraData Data = {&M, &CalledRAUW, &CalledDeleted};
203  ValueMap<TypeParam*, int, ConfigType> 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
212template<typename KeyT>
213struct NoFollow : ValueMapConfig<KeyT> {
214  enum { FollowRAUW = false };
215};
216
217TYPED_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(0u, 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
234template<typename KeyT>
235struct CountOps : ValueMapConfig<KeyT> {
236  struct ExtraData {
237    int *Deletions;
238    int *RAUWs;
239  };
240
241  static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) {
242    ++*Data.RAUWs;
243  }
244  static void onDelete(const ExtraData &Data, KeyT Old) {
245    ++*Data.Deletions;
246  }
247};
248
249TYPED_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
265template<typename KeyT>
266struct 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
273  static void onRAUW(ExtraData Map, KeyT Old, KeyT New) {
274    (*Map)->erase(Old);
275  }
276  static void onDelete(ExtraData Map, KeyT Old) {
277    (*Map)->erase(Old);
278  }
279};
280TYPED_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_EQ(0u, VM.count(this->BitcastV.get()));
288  EXPECT_EQ(0u, VM.count(this->AddV.get()));
289  VM[this->AddV.get()] = 7;
290  this->AddV.reset();
291  EXPECT_EQ(0u, VM.count(this->AddV.get()));
292}
293
294}
295