llvm/unittests/IR/ValueMapTest.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-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