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