unittests/ADT/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
  12 #include "llvm/Instructions.h"
  13 #include "llvm/ADT/OwningPtr.h"
  14
  15 #include "gtest/gtest.h"
  16
  17 using namespace llvm;
  18
  19 namespace {
  20
  21 // Test fixture
  22 template<typename T>
  23 class ValueMapTest : public testing::Test {
  24 protected:
  25   Constant *ConstantV;
  26   OwningPtr<BitCastInst> BitcastV;
  27   OwningPtr<BinaryOperator> AddV;
  28
  29   ValueMapTest() :
  30     ConstantV(ConstantInt::get(Type::getInt32Ty(getGlobalContext()), 0)),
  31     BitcastV(new BitCastInst(ConstantV, Type::getInt32Ty(getGlobalContext()))),
  32     AddV(BinaryOperator::CreateAdd(ConstantV, ConstantV)) {
  33   }
  34 };
  35
  36 // Run everything on Value*, a subtype to make sure that casting works as
  37 // expected, and a const subtype to make sure we cast const correctly.
  38 typedef ::testing::Types<Value, Instruction, const Instruction> KeyTypes;
  39 TYPED_TEST_CASE(ValueMapTest, KeyTypes);
  40
  41 TYPED_TEST(ValueMapTest, Null) {
  42   ValueMap<TypeParam*, int> VM1;
  43   VM1[NULL] = 7;
  44   EXPECT_EQ(7, VM1.lookup(NULL));
  45 }
  46
  47 TYPED_TEST(ValueMapTest, FollowsValue) {
  48   ValueMap<TypeParam*, int> VM;
  49   VM[this->BitcastV.get()] = 7;
  50   EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
  51   EXPECT_EQ(0, VM.count(this->AddV.get()));
  52   this->BitcastV->replaceAllUsesWith(this->AddV.get());
  53   EXPECT_EQ(7, VM.lookup(this->AddV.get()));
  54   EXPECT_EQ(0, VM.count(this->BitcastV.get()));
  55   this->AddV.reset();
  56   EXPECT_EQ(0, VM.count(this->AddV.get()));
  57   EXPECT_EQ(0, VM.count(this->BitcastV.get()));
  58   EXPECT_EQ(0U, VM.size());
  59 }
  60
  61 TYPED_TEST(ValueMapTest, OperationsWork) {
  62   ValueMap<TypeParam*, int> VM;
  63   ValueMap<TypeParam*, int> VM2(16);
  64   typename ValueMapConfig<TypeParam*>::ExtraData Data;
  65   ValueMap<TypeParam*, int> VM3(Data, 16);
  66   EXPECT_TRUE(VM.empty());
  67
  68   VM[this->BitcastV.get()] = 7;
  69
  70   // Find:
  71   typename ValueMap<TypeParam*, int>::iterator I =
  72     VM.find(this->BitcastV.get());
  73   ASSERT_TRUE(I != VM.end());
  74   EXPECT_EQ(this->BitcastV.get(), I->first);
  75   EXPECT_EQ(7, I->second);
  76   EXPECT_TRUE(VM.find(this->AddV.get()) == VM.end());
  77
  78   // Const find:
  79   const ValueMap<TypeParam*, int> &CVM = VM;
  80   typename ValueMap<TypeParam*, int>::const_iterator CI =
  81     CVM.find(this->BitcastV.get());
  82   ASSERT_TRUE(CI != CVM.end());
  83   EXPECT_EQ(this->BitcastV.get(), CI->first);
  84   EXPECT_EQ(7, CI->second);
  85   EXPECT_TRUE(CVM.find(this->AddV.get()) == CVM.end());
  86
  87   // Insert:
  88   std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult1 =
  89     VM.insert(std::make_pair(this->AddV.get(), 3));
  90   EXPECT_EQ(this->AddV.get(), InsertResult1.first->first);
  91   EXPECT_EQ(3, InsertResult1.first->second);
  92   EXPECT_TRUE(InsertResult1.second);
  93   EXPECT_EQ(true, VM.count(this->AddV.get()));
  94   std::pair<typename ValueMap<TypeParam*, int>::iterator, bool> InsertResult2 =
  95     VM.insert(std::make_pair(this->AddV.get(), 5));
  96   EXPECT_EQ(this->AddV.get(), InsertResult2.first->first);
  97   EXPECT_EQ(3, InsertResult2.first->second);
  98   EXPECT_FALSE(InsertResult2.second);
  99
 100   // Erase:
 101   VM.erase(InsertResult2.first);
 102   EXPECT_EQ(false, VM.count(this->AddV.get()));
 103   EXPECT_EQ(true, VM.count(this->BitcastV.get()));
 104   VM.erase(this->BitcastV.get());
 105   EXPECT_EQ(false, VM.count(this->BitcastV.get()));
 106   EXPECT_EQ(0U, VM.size());
 107
 108   // Range insert:
 109   SmallVector<std::pair<Instruction*, int>, 2> Elems;
 110   Elems.push_back(std::make_pair(this->AddV.get(), 1));
 111   Elems.push_back(std::make_pair(this->BitcastV.get(), 2));
 112   VM.insert(Elems.begin(), Elems.end());
 113   EXPECT_EQ(1, VM.lookup(this->AddV.get()));
 114   EXPECT_EQ(2, VM.lookup(this->BitcastV.get()));
 115 }
 116
 117 template<typename ExpectedType, typename VarType>
 118 void CompileAssertHasType(VarType) {
 119   typedef char assert[is_same<ExpectedType, VarType>::value ? 1 : -1];
 120 }
 121
 122 TYPED_TEST(ValueMapTest, Iteration) {
 123   ValueMap<TypeParam*, int> VM;
 124   VM[this->BitcastV.get()] = 2;
 125   VM[this->AddV.get()] = 3;
 126   size_t size = 0;
 127   for (typename ValueMap<TypeParam*, int>::iterator I = VM.begin(), E = VM.end();
 128        I != E; ++I) {
 129     ++size;
 130     std::pair<TypeParam*, int> value = *I;
 131     CompileAssertHasType<TypeParam*>(I->first);
 132     if (I->second == 2) {
 133       EXPECT_EQ(this->BitcastV.get(), I->first);
 134       I->second = 5;
 135     } else if (I->second == 3) {
 136       EXPECT_EQ(this->AddV.get(), I->first);
 137       I->second = 6;
 138     } else {
 139       ADD_FAILURE() << "Iterated through an extra value.";
 140     }
 141   }
 142   EXPECT_EQ(2U, size);
 143   EXPECT_EQ(5, VM[this->BitcastV.get()]);
 144   EXPECT_EQ(6, VM[this->AddV.get()]);
 145
 146   size = 0;
 147   // Cast to const ValueMap to avoid a bug in DenseMap's iterators.
 148   const ValueMap<TypeParam*, int>& CVM = VM;
 149   for (typename ValueMap<TypeParam*, int>::const_iterator I = CVM.begin(),
 150          E = CVM.end(); I != E; ++I) {
 151     ++size;
 152     std::pair<TypeParam*, int> value = *I;
 153     CompileAssertHasType<TypeParam*>(I->first);
 154     if (I->second == 5) {
 155       EXPECT_EQ(this->BitcastV.get(), I->first);
 156     } else if (I->second == 6) {
 157       EXPECT_EQ(this->AddV.get(), I->first);
 158     } else {
 159       ADD_FAILURE() << "Iterated through an extra value.";
 160     }
 161   }
 162   EXPECT_EQ(2U, size);
 163 }
 164
 165 TYPED_TEST(ValueMapTest, DefaultCollisionBehavior) {
 166   // By default, we overwrite the old value with the replaced value.
 167   ValueMap<TypeParam*, int> VM;
 168   VM[this->BitcastV.get()] = 7;
 169   VM[this->AddV.get()] = 9;
 170   this->BitcastV->replaceAllUsesWith(this->AddV.get());
 171   EXPECT_EQ(0, VM.count(this->BitcastV.get()));
 172   EXPECT_EQ(9, VM.lookup(this->AddV.get()));
 173 }
 174
 175 TYPED_TEST(ValueMapTest, ConfiguredCollisionBehavior) {
 176   // TODO: Implement this when someone needs it.
 177 }
 178
 179 template<typename KeyT>
 180 struct LockMutex : ValueMapConfig<KeyT> {
 181   struct ExtraData {
 182     sys::Mutex *M;
 183     bool *CalledRAUW;
 184     bool *CalledDeleted;
 185   };
 186   static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) {
 187     *Data.CalledRAUW = true;
 188     EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked.";
 189   }
 190   static void onDeleted(const ExtraData &Data, KeyT Old) {
 191     *Data.CalledDeleted = true;
 192     EXPECT_FALSE(Data.M->tryacquire()) << "Mutex should already be locked.";
 193   }
 194   static sys::Mutex *getMutex(const ExtraData &Data) { return Data.M; }
 195 };
 196 TYPED_TEST(ValueMapTest, LocksMutex) {
 197   sys::Mutex M(false);  // Not recursive.
 198   bool CalledRAUW = false, CalledDeleted = false;
 199   typename LockMutex<TypeParam*>::ExtraData Data =
 200     {&M, &CalledRAUW, &CalledDeleted};
 201   ValueMap<TypeParam*, int, LockMutex<TypeParam*> > VM(Data);
 202   VM[this->BitcastV.get()] = 7;
 203   this->BitcastV->replaceAllUsesWith(this->AddV.get());
 204   this->AddV.reset();
 205   EXPECT_TRUE(CalledRAUW);
 206   EXPECT_TRUE(CalledDeleted);
 207 }
 208
 209 template<typename KeyT>
 210 struct NoFollow : ValueMapConfig<KeyT> {
 211   enum { FollowRAUW = false };
 212 };
 213
 214 TYPED_TEST(ValueMapTest, NoFollowRAUW) {
 215   ValueMap<TypeParam*, int, NoFollow<TypeParam*> > VM;
 216   VM[this->BitcastV.get()] = 7;
 217   EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
 218   EXPECT_EQ(0, VM.count(this->AddV.get()));
 219   this->BitcastV->replaceAllUsesWith(this->AddV.get());
 220   EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
 221   EXPECT_EQ(0, VM.lookup(this->AddV.get()));
 222   this->AddV.reset();
 223   EXPECT_EQ(7, VM.lookup(this->BitcastV.get()));
 224   EXPECT_EQ(0, VM.lookup(this->AddV.get()));
 225   this->BitcastV.reset();
 226   EXPECT_EQ(0, VM.lookup(this->BitcastV.get()));
 227   EXPECT_EQ(0, VM.lookup(this->AddV.get()));
 228   EXPECT_EQ(0U, VM.size());
 229 }
 230
 231 template<typename KeyT>
 232 struct CountOps : ValueMapConfig<KeyT> {
 233   struct ExtraData {
 234     int *Deletions;
 235     int *RAUWs;
 236   };
 237
 238   static void onRAUW(const ExtraData &Data, KeyT Old, KeyT New) {
 239     ++*Data.RAUWs;
 240   }
 241   static void onDeleted(const ExtraData &Data, KeyT Old) {
 242     ++*Data.Deletions;
 243   }
 244 };
 245
 246 TYPED_TEST(ValueMapTest, CallsConfig) {
 247   int Deletions = 0, RAUWs = 0;
 248   typename CountOps<TypeParam*>::ExtraData Data = {&Deletions, &RAUWs};
 249   ValueMap<TypeParam*, int, CountOps<TypeParam*> > VM(Data);
 250   VM[this->BitcastV.get()] = 7;
 251   this->BitcastV->replaceAllUsesWith(this->AddV.get());
 252   EXPECT_EQ(0, Deletions);
 253   EXPECT_EQ(1, RAUWs);
 254   this->AddV.reset();
 255   EXPECT_EQ(1, Deletions);
 256   EXPECT_EQ(1, RAUWs);
 257   this->BitcastV.reset();
 258   EXPECT_EQ(1, Deletions);
 259   EXPECT_EQ(1, RAUWs);
 260 }
 261
 262 template<typename KeyT>
 263 struct ModifyingConfig : ValueMapConfig<KeyT> {
 264   // We'll put a pointer here back to the ValueMap this key is in, so
 265   // that we can modify it (and clobber *this) before the ValueMap
 266   // tries to do the same modification.  In previous versions of
 267   // ValueMap, that exploded.
 268   typedef ValueMap<KeyT, int, ModifyingConfig<KeyT> > **ExtraData;
 269
 270   static void onRAUW(ExtraData Map, KeyT Old, KeyT New) {
 271     (*Map)->erase(Old);
 272   }
 273   static void onDeleted(ExtraData Map, KeyT Old) {
 274     (*Map)->erase(Old);
 275   }
 276 };
 277 TYPED_TEST(ValueMapTest, SurvivesModificationByConfig) {
 278   ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > *MapAddress;
 279   ValueMap<TypeParam*, int, ModifyingConfig<TypeParam*> > VM(&MapAddress);
 280   MapAddress = &VM;
 281   // Now the ModifyingConfig can modify the Map inside a callback.
 282   VM[this->BitcastV.get()] = 7;
 283   this->BitcastV->replaceAllUsesWith(this->AddV.get());
 284   EXPECT_FALSE(VM.count(this->BitcastV.get()));
 285   EXPECT_FALSE(VM.count(this->AddV.get()));
 286   VM[this->AddV.get()] = 7;
 287   this->AddV.reset();
 288   EXPECT_FALSE(VM.count(this->AddV.get()));
 289 }
 290
 291 }