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/Constants.h" 12 #include "llvm/Instructions.h" 13 #include "llvm/LLVMContext.h" 14 #include "llvm/ADT/OwningPtr.h" 15 #include "llvm/Config/config.h" 16 17 #include "gtest/gtest.h" 18 19 using namespace llvm; 20 21 namespace { 22 23 // Test fixture 24 template<typename T> 25 class ValueMapTest : public testing::Test { 26 protected: 27 Constant *ConstantV; 28 OwningPtr<BitCastInst> BitcastV; 29 OwningPtr<BinaryOperator> AddV; 30 31 ValueMapTest() : 32 ConstantV(ConstantInt::get(Type::getInt32Ty(getGlobalContext()), 0)), 33 BitcastV(new BitCastInst(ConstantV, Type::getInt32Ty(getGlobalContext()))), 34 AddV(BinaryOperator::CreateAdd(ConstantV, ConstantV)) { 35 } 36 }; 37 38 // Run everything on Value*, a subtype to make sure that casting works as 39 // expected, and a const subtype to make sure we cast const correctly. 40 typedef ::testing::Types<Value, Instruction, const Instruction> KeyTypes; 41 TYPED_TEST_CASE(ValueMapTest, KeyTypes); 42 43 TYPED_TEST(ValueMapTest, Null) { 44 ValueMap<TypeParam*, int> VM1; 45 VM1[NULL] = 7; 46 EXPECT_EQ(7, VM1.lookup(NULL)); 47 } 48 49 TYPED_TEST(ValueMapTest, FollowsValue) { 50 ValueMap<TypeParam*, int> VM; 51 VM[this->BitcastV.get()] = 7; 52 EXPECT_EQ(7, VM.lookup(this->BitcastV.get())); 53 EXPECT_EQ(0, VM.count(this->AddV.get())); 54 this->BitcastV->replaceAllUsesWith(this->AddV.get()); 55 EXPECT_EQ(7, VM.lookup(this->AddV.get())); 56 EXPECT_EQ(0, VM.count(this->BitcastV.get())); 57 this->AddV.reset(); 58 EXPECT_EQ(0, VM.count(this->AddV.get())); 59 EXPECT_EQ(0, VM.count(this->BitcastV.get())); 60 EXPECT_EQ(0U, VM.size()); 61 } 62 63 TYPED_TEST(ValueMapTest, OperationsWork) { 64 ValueMap<TypeParam*, int> VM; 65 ValueMap<TypeParam*, int> VM2(16); (void)VM2; 66 typename ValueMapConfig<TypeParam*>::ExtraData Data; 67 ValueMap<TypeParam*, int> VM3(Data, 16); (void)VM3; 68 EXPECT_TRUE(VM.empty()); 69 70 VM[this->BitcastV.get()] = 7; 71 72 // Find: 73 typename ValueMap<TypeParam*, int>::iterator I = 74 VM.find(this->BitcastV.get()); 75 ASSERT_TRUE(I != VM.end()); 76 EXPECT_EQ(this->BitcastV.get(), I->first); 77 EXPECT_EQ(7, I->second); 78 EXPECT_TRUE(VM.find(this->AddV.get()) == VM.end()); 79 80 // Const find: 81 const ValueMap<TypeParam*, int> &CVM = VM; 82 typename ValueMap<TypeParam*, int>::const_iterator CI = 83 CVM.find(this->BitcastV.get()); 84 ASSERT_TRUE(CI != CVM.end()); 85 EXPECT_EQ(this->BitcastV.get(), CI->first); 86 EXPECT_EQ(7, CI->second); 87 EXPECT_TRUE(CVM.find(this->AddV.get()) == CVM.end()); 88 89 // Insert: 90 std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult1 = 91 VM.insert(std::make_pair(this->AddV.get(), 3)); 92 EXPECT_EQ(this->AddV.get(), InsertResult1.first->first); 93 EXPECT_EQ(3, InsertResult1.first->second); 94 EXPECT_TRUE(InsertResult1.second); 95 EXPECT_EQ(true, VM.count(this->AddV.get())); 96 std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult2 = 97 VM.insert(std::make_pair(this->AddV.get(), 5)); 98 EXPECT_EQ(this->AddV.get(), InsertResult2.first->first); 99 EXPECT_EQ(3, InsertResult2.first->second); 100 EXPECT_FALSE(InsertResult2.second); 101 102 // Erase: 103 VM.erase(InsertResult2.first); 104 EXPECT_EQ(0U, VM.count(this->AddV.get())); 105 EXPECT_EQ(1U, VM.count(this->BitcastV.get())); 106 VM.erase(this->BitcastV.get()); 107 EXPECT_EQ(0U, VM.count(this->BitcastV.get())); 108 EXPECT_EQ(0U, VM.size()); 109 110 // Range insert: 111 SmallVector<std::pair<Instruction*, int>, 2> Elems; 112 Elems.push_back(std::make_pair(this->AddV.get(), 1)); 113 Elems.push_back(std::make_pair(this->BitcastV.get(), 2)); 114 VM.insert(Elems.begin(), Elems.end()); 115 EXPECT_EQ(1, VM.lookup(this->AddV.get())); 116 EXPECT_EQ(2, VM.lookup(this->BitcastV.get())); 117 } 118 119 template<typename ExpectedType, typename VarType> 120 void CompileAssertHasType(VarType) { 121 typedef char assert[is_same<ExpectedType, VarType>::value ? 1 : -1]; 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 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
