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(Type::getInt32Ty(Context), 0)), 31 BitcastV(new BitCastInst(ConstantV, Type::getInt32Ty(Context))), 32 AddV(BinaryOperator::CreateAdd(ConstantV, 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(std::make_pair(this->AddV.get(), 1)); 110 Elems.push_back(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 ExtraData { 181 MutexT *M; 182 bool *CalledRAUW; 183 bool *CalledDeleted; 184 }; 185 static void onRAUW(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 onDelete(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 *getMutex(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 ExtraData { 236 int *Deletions; 237 int *RAUWs; 238 }; 239 240 static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) { 241 ++*Data.RAUWs; 242 } 243 static void onDelete(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> > **ExtraData; 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