294 lines · cpp
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-exception6//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 16using namespace llvm;17 18namespace {19 20// Test fixture21template<typename T>22class ValueMapTest : public testing::Test {23protected: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 as36// expected, and a const subtype to make sure we cast const correctly.37typedef ::testing::Types<Value, Instruction, const Instruction> KeyTypes;38TYPED_TEST_SUITE(ValueMapTest, KeyTypes, );39 40TYPED_TEST(ValueMapTest, Null) {41 ValueMap<TypeParam*, int> VM1;42 VM1[nullptr] = 7;43 EXPECT_EQ(7, VM1.lookup(nullptr));44}45 46TYPED_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 60TYPED_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 116template<typename ExpectedType, typename VarType>117void CompileAssertHasType(VarType) {118 static_assert(std::is_same_v<ExpectedType, VarType>, "Not the same type");119}120 121TYPED_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 164TYPED_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 174TYPED_TEST(ValueMapTest, ConfiguredCollisionBehavior) {175 // TODO: Implement this when someone needs it.176}177 178template<typename KeyT, typename MutexT>179struct 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)197TYPED_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#endif210 211template<typename KeyT>212struct NoFollow : ValueMapConfig<KeyT> {213 enum { FollowRAUW = false };214};215 216TYPED_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 233template<typename KeyT>234struct 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 248TYPED_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 264template<typename KeyT>265struct ModifyingConfig : ValueMapConfig<KeyT> {266 // We'll put a pointer here back to the ValueMap this key is in, so267 // that we can modify it (and clobber *this) before the ValueMap268 // tries to do the same modification. In previous versions of269 // 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};279TYPED_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 namespace294