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 17 using namespace llvm; 18 19 namespace { 20 21 // Test fixture 22 template<typename T> 23 class ValueMapTest : public testing::Test { 24 protected: 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. 38 typedef ::testing::Types<Value, Instruction, const Instruction> KeyTypes; 39 TYPED_TEST_CASE(ValueMapTest, KeyTypes); 40 41 TYPED_TEST(ValueMapTest, Null) { 42 ValueMap<TypeParam*, int> VM1; 43 VM1[nullptr] = 7; 44 EXPECT_EQ(7, VM1.lookup(nullptr)); 45 } 46 47 TYPED_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 61 TYPED_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 117 template<typename ExpectedType, typename VarType> 118 void CompileAssertHasType(VarType) { 119 static_assert(std::is_same<ExpectedType, VarType>::value, 120 "Not the same type"); 121 } 122 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 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(0u, VM.count(this->BitcastV.get())); 173 EXPECT_EQ(9, VM.lookup(this->AddV.get())); 174 } 175 176 TYPED_TEST(ValueMapTest, ConfiguredCollisionBehavior) { 177 // TODO: Implement this when someone needs it. 178 } 179 180 template<typename KeyT, typename MutexT> 181 struct 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 198 TYPED_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 212 template<typename KeyT> 213 struct NoFollow : ValueMapConfig<KeyT> { 214 enum { FollowRAUW = false }; 215 }; 216 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(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 234 template<typename KeyT> 235 struct 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 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 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 }; 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_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