unittests/VMCore/ValueMapTest.cpp

   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 }