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