unittests/Analysis/MemorySSA.cpp

   1 //===- MemorySSA.cpp - Unit tests for MemorySSA ---------------------------===//
   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 #include "llvm/Analysis/MemorySSA.h"
  10 #include "llvm/Analysis/AliasAnalysis.h"
  11 #include "llvm/Analysis/BasicAliasAnalysis.h"
  12 #include "llvm/Analysis/MemorySSAUpdater.h"
  13 #include "llvm/IR/BasicBlock.h"
  14 #include "llvm/IR/DataLayout.h"
  15 #include "llvm/IR/Dominators.h"
  16 #include "llvm/IR/IRBuilder.h"
  17 #include "llvm/IR/Instructions.h"
  18 #include "llvm/IR/LLVMContext.h"
  19 #include "gtest/gtest.h"
  20
  21 using namespace llvm;
  22
  23 const static char DLString[] = "e-i64:64-f80:128-n8:16:32:64-S128";
  24
  25 /// There's a lot of common setup between these tests. This fixture helps reduce
  26 /// that. Tests should mock up a function, store it in F, and then call
  27 /// setupAnalyses().
  28 class MemorySSATest : public testing::Test {
  29 protected:
  30   // N.B. Many of these members depend on each other (e.g. the Module depends on
  31   // the Context, etc.). So, order matters here (and in TestAnalyses).
  32   LLVMContext C;
  33   Module M;
  34   IRBuilder<> B;
  35   DataLayout DL;
  36   TargetLibraryInfoImpl TLII;
  37   TargetLibraryInfo TLI;
  38   Function *F;
  39
  40   // Things that we need to build after the function is created.
  41   struct TestAnalyses {
  42     DominatorTree DT;
  43     AssumptionCache AC;
  44     AAResults AA;
  45     BasicAAResult BAA;
  46     // We need to defer MSSA construction until AA is *entirely* set up, which
  47     // requires calling addAAResult. Hence, we just use a pointer here.
  48     std::unique_ptr<MemorySSA> MSSA;
  49     MemorySSAWalker *Walker;
  50
  51     TestAnalyses(MemorySSATest &Test)
  52         : DT(*Test.F), AC(*Test.F), AA(Test.TLI),
  53           BAA(Test.DL, Test.TLI, AC, &DT) {
  54       AA.addAAResult(BAA);
  55       MSSA = make_unique<MemorySSA>(*Test.F, &AA, &DT);
  56       Walker = MSSA->getWalker();
  57     }
  58   };
  59
  60   std::unique_ptr<TestAnalyses> Analyses;
  61
  62   void setupAnalyses() {
  63     assert(F);
  64     Analyses.reset(new TestAnalyses(*this));
  65   }
  66
  67 public:
  68   MemorySSATest()
  69       : M("MemorySSATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {}
  70 };
  71
  72 TEST_F(MemorySSATest, CreateALoad) {
  73   // We create a diamond where there is a store on one side, and then after
  74   // building MemorySSA, create a load after the merge point, and use it to test
  75   // updating by creating an access for the load.
  76   F = Function::Create(
  77       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
  78       GlobalValue::ExternalLinkage, "F", &M);
  79   BasicBlock *Entry(BasicBlock::Create(C, "", F));
  80   BasicBlock *Left(BasicBlock::Create(C, "", F));
  81   BasicBlock *Right(BasicBlock::Create(C, "", F));
  82   BasicBlock *Merge(BasicBlock::Create(C, "", F));
  83   B.SetInsertPoint(Entry);
  84   B.CreateCondBr(B.getTrue(), Left, Right);
  85   B.SetInsertPoint(Left);
  86   Argument *PointerArg = &*F->arg_begin();
  87   B.CreateStore(B.getInt8(16), PointerArg);
  88   BranchInst::Create(Merge, Left);
  89   BranchInst::Create(Merge, Right);
  90
  91   setupAnalyses();
  92   MemorySSA &MSSA = *Analyses->MSSA;
  93   MemorySSAUpdater Updater(&MSSA);
  94   // Add the load
  95   B.SetInsertPoint(Merge);
  96   LoadInst *LoadInst = B.CreateLoad(PointerArg);
  97
  98   // MemoryPHI should already exist.
  99   MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
 100   EXPECT_NE(MP, nullptr);
 101
 102   // Create the load memory acccess
 103   MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
 104       LoadInst, MP, Merge, MemorySSA::Beginning));
 105   MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
 106   EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
 107   MSSA.verifyMemorySSA();
 108 }
 109 TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
 110   // We create a diamond, then build memoryssa with no memory accesses, and
 111   // incrementally update it by inserting a store in the, entry, a load in the
 112   // merge point, then a store in the branch, another load in the merge point,
 113   // and then a store in the entry.
 114   F = Function::Create(
 115       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 116       GlobalValue::ExternalLinkage, "F", &M);
 117   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 118   BasicBlock *Left(BasicBlock::Create(C, "", F));
 119   BasicBlock *Right(BasicBlock::Create(C, "", F));
 120   BasicBlock *Merge(BasicBlock::Create(C, "", F));
 121   B.SetInsertPoint(Entry);
 122   B.CreateCondBr(B.getTrue(), Left, Right);
 123   B.SetInsertPoint(Left, Left->begin());
 124   Argument *PointerArg = &*F->arg_begin();
 125   B.SetInsertPoint(Left);
 126   B.CreateBr(Merge);
 127   B.SetInsertPoint(Right);
 128   B.CreateBr(Merge);
 129
 130   setupAnalyses();
 131   MemorySSA &MSSA = *Analyses->MSSA;
 132   MemorySSAUpdater Updater(&MSSA);
 133   // Add the store
 134   B.SetInsertPoint(Entry, Entry->begin());
 135   StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
 136   MemoryAccess *EntryStoreAccess = Updater.createMemoryAccessInBB(
 137       EntryStore, nullptr, Entry, MemorySSA::Beginning);
 138   Updater.insertDef(cast<MemoryDef>(EntryStoreAccess));
 139
 140   // Add the load
 141   B.SetInsertPoint(Merge, Merge->begin());
 142   LoadInst *FirstLoad = B.CreateLoad(PointerArg);
 143
 144   // MemoryPHI should not already exist.
 145   MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
 146   EXPECT_EQ(MP, nullptr);
 147
 148   // Create the load memory access
 149   MemoryUse *FirstLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
 150       FirstLoad, nullptr, Merge, MemorySSA::Beginning));
 151   Updater.insertUse(FirstLoadAccess);
 152   // Should just have a load using the entry access, because it should discover
 153   // the phi is trivial
 154   EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), EntryStoreAccess);
 155
 156   // Create a store on the left
 157   // Add the store
 158   B.SetInsertPoint(Left, Left->begin());
 159   StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg);
 160   MemoryAccess *LeftStoreAccess = Updater.createMemoryAccessInBB(
 161       LeftStore, nullptr, Left, MemorySSA::Beginning);
 162   Updater.insertDef(cast<MemoryDef>(LeftStoreAccess), false);
 163   // We don't touch existing loads, so we need to create a new one to get a phi
 164   // Add the second load
 165   B.SetInsertPoint(Merge, Merge->begin());
 166   LoadInst *SecondLoad = B.CreateLoad(PointerArg);
 167
 168   // MemoryPHI should not already exist.
 169   MP = MSSA.getMemoryAccess(Merge);
 170   EXPECT_EQ(MP, nullptr);
 171
 172   // Create the load memory access
 173   MemoryUse *SecondLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
 174       SecondLoad, nullptr, Merge, MemorySSA::Beginning));
 175   Updater.insertUse(SecondLoadAccess);
 176   // Now the load should be a phi of the entry store and the left store
 177   MemoryPhi *MergePhi =
 178       dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
 179   EXPECT_NE(MergePhi, nullptr);
 180   EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
 181   EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
 182   // Now create a store below the existing one in the entry
 183   B.SetInsertPoint(Entry, --Entry->end());
 184   StoreInst *SecondEntryStore = B.CreateStore(B.getInt8(16), PointerArg);
 185   MemoryAccess *SecondEntryStoreAccess = Updater.createMemoryAccessInBB(
 186       SecondEntryStore, nullptr, Entry, MemorySSA::End);
 187   // Insert it twice just to test renaming
 188   Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess), false);
 189   EXPECT_NE(FirstLoadAccess->getDefiningAccess(), MergePhi);
 190   Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess), true);
 191   EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), MergePhi);
 192   // and make sure the phi below it got updated, despite being blocks away
 193   MergePhi = dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
 194   EXPECT_NE(MergePhi, nullptr);
 195   EXPECT_EQ(MergePhi->getIncomingValue(0), SecondEntryStoreAccess);
 196   EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);
 197   MSSA.verifyMemorySSA();
 198 }
 199
 200 TEST_F(MemorySSATest, CreateALoadUpdater) {
 201   // We create a diamond, then build memoryssa with no memory accesses, and
 202   // incrementally update it by inserting a store in one of the branches, and a
 203   // load in the merge point
 204   F = Function::Create(
 205       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 206       GlobalValue::ExternalLinkage, "F", &M);
 207   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 208   BasicBlock *Left(BasicBlock::Create(C, "", F));
 209   BasicBlock *Right(BasicBlock::Create(C, "", F));
 210   BasicBlock *Merge(BasicBlock::Create(C, "", F));
 211   B.SetInsertPoint(Entry);
 212   B.CreateCondBr(B.getTrue(), Left, Right);
 213   B.SetInsertPoint(Left, Left->begin());
 214   Argument *PointerArg = &*F->arg_begin();
 215   B.SetInsertPoint(Left);
 216   B.CreateBr(Merge);
 217   B.SetInsertPoint(Right);
 218   B.CreateBr(Merge);
 219
 220   setupAnalyses();
 221   MemorySSA &MSSA = *Analyses->MSSA;
 222   MemorySSAUpdater Updater(&MSSA);
 223   B.SetInsertPoint(Left, Left->begin());
 224   // Add the store
 225   StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg);
 226   MemoryAccess *StoreAccess =
 227       Updater.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning);
 228   Updater.insertDef(cast<MemoryDef>(StoreAccess));
 229
 230   // Add the load
 231   B.SetInsertPoint(Merge, Merge->begin());
 232   LoadInst *LoadInst = B.CreateLoad(PointerArg);
 233
 234   // MemoryPHI should not already exist.
 235   MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
 236   EXPECT_EQ(MP, nullptr);
 237
 238   // Create the load memory acccess
 239   MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
 240       LoadInst, nullptr, Merge, MemorySSA::Beginning));
 241   Updater.insertUse(LoadAccess);
 242   MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
 243   EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
 244   MSSA.verifyMemorySSA();
 245 }
 246
 247 TEST_F(MemorySSATest, SinkLoad) {
 248   F = Function::Create(
 249       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 250       GlobalValue::ExternalLinkage, "F", &M);
 251   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 252   BasicBlock *Left(BasicBlock::Create(C, "", F));
 253   BasicBlock *Right(BasicBlock::Create(C, "", F));
 254   BasicBlock *Merge(BasicBlock::Create(C, "", F));
 255   B.SetInsertPoint(Entry);
 256   B.CreateCondBr(B.getTrue(), Left, Right);
 257   B.SetInsertPoint(Left, Left->begin());
 258   Argument *PointerArg = &*F->arg_begin();
 259   B.SetInsertPoint(Left);
 260   B.CreateBr(Merge);
 261   B.SetInsertPoint(Right);
 262   B.CreateBr(Merge);
 263
 264   // Load in left block
 265   B.SetInsertPoint(Left, Left->begin());
 266   LoadInst *LoadInst1 = B.CreateLoad(PointerArg);
 267   // Store in merge block
 268   B.SetInsertPoint(Merge, Merge->begin());
 269   B.CreateStore(B.getInt8(16), PointerArg);
 270
 271   setupAnalyses();
 272   MemorySSA &MSSA = *Analyses->MSSA;
 273   MemorySSAUpdater Updater(&MSSA);
 274
 275   // Mimic sinking of a load:
 276   // - clone load
 277   // - insert in "exit" block
 278   // - insert in mssa
 279   // - remove from original block
 280
 281   LoadInst *LoadInstClone = cast<LoadInst>(LoadInst1->clone());
 282   Merge->getInstList().insert(Merge->begin(), LoadInstClone);
 283   MemoryAccess * NewLoadAccess =
 284       Updater.createMemoryAccessInBB(LoadInstClone, nullptr,
 285                                      LoadInstClone->getParent(),
 286                                      MemorySSA::Beginning);
 287   Updater.insertUse(cast<MemoryUse>(NewLoadAccess));
 288   MSSA.verifyMemorySSA();
 289   Updater.removeMemoryAccess(MSSA.getMemoryAccess(LoadInst1));
 290   MSSA.verifyMemorySSA();
 291 }
 292
 293 TEST_F(MemorySSATest, MoveAStore) {
 294   // We create a diamond where there is a in the entry, a store on one side, and
 295   // a load at the end.  After building MemorySSA, we test updating by moving
 296   // the store from the side block to the entry block. This destroys the old
 297   // access.
 298   F = Function::Create(
 299       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 300       GlobalValue::ExternalLinkage, "F", &M);
 301   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 302   BasicBlock *Left(BasicBlock::Create(C, "", F));
 303   BasicBlock *Right(BasicBlock::Create(C, "", F));
 304   BasicBlock *Merge(BasicBlock::Create(C, "", F));
 305   B.SetInsertPoint(Entry);
 306   Argument *PointerArg = &*F->arg_begin();
 307   StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
 308   B.CreateCondBr(B.getTrue(), Left, Right);
 309   B.SetInsertPoint(Left);
 310   StoreInst *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
 311   BranchInst::Create(Merge, Left);
 312   BranchInst::Create(Merge, Right);
 313   B.SetInsertPoint(Merge);
 314   B.CreateLoad(PointerArg);
 315   setupAnalyses();
 316   MemorySSA &MSSA = *Analyses->MSSA;
 317   MemorySSAUpdater Updater(&MSSA);
 318   // Move the store
 319   SideStore->moveBefore(Entry->getTerminator());
 320   MemoryAccess *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
 321   MemoryAccess *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
 322   MemoryAccess *NewStoreAccess = Updater.createMemoryAccessAfter(
 323       SideStore, EntryStoreAccess, EntryStoreAccess);
 324   EntryStoreAccess->replaceAllUsesWith(NewStoreAccess);
 325   Updater.removeMemoryAccess(SideStoreAccess);
 326   MSSA.verifyMemorySSA();
 327 }
 328
 329 TEST_F(MemorySSATest, MoveAStoreUpdater) {
 330   // We create a diamond where there is a in the entry, a store on one side, and
 331   // a load at the end.  After building MemorySSA, we test updating by moving
 332   // the store from the side block to the entry block.  This destroys the old
 333   // access.
 334   F = Function::Create(
 335       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 336       GlobalValue::ExternalLinkage, "F", &M);
 337   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 338   BasicBlock *Left(BasicBlock::Create(C, "", F));
 339   BasicBlock *Right(BasicBlock::Create(C, "", F));
 340   BasicBlock *Merge(BasicBlock::Create(C, "", F));
 341   B.SetInsertPoint(Entry);
 342   Argument *PointerArg = &*F->arg_begin();
 343   StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
 344   B.CreateCondBr(B.getTrue(), Left, Right);
 345   B.SetInsertPoint(Left);
 346   auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
 347   BranchInst::Create(Merge, Left);
 348   BranchInst::Create(Merge, Right);
 349   B.SetInsertPoint(Merge);
 350   auto *MergeLoad = B.CreateLoad(PointerArg);
 351   setupAnalyses();
 352   MemorySSA &MSSA = *Analyses->MSSA;
 353   MemorySSAUpdater Updater(&MSSA);
 354
 355   // Move the store
 356   SideStore->moveBefore(Entry->getTerminator());
 357   auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
 358   auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
 359   auto *NewStoreAccess = Updater.createMemoryAccessAfter(
 360       SideStore, EntryStoreAccess, EntryStoreAccess);
 361   // Before, the load will point to a phi of the EntryStore and SideStore.
 362   auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
 363   EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
 364   MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
 365   EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
 366   EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
 367   Updater.removeMemoryAccess(SideStoreAccess);
 368   Updater.insertDef(cast<MemoryDef>(NewStoreAccess));
 369   // After it's a phi of the new side store access.
 370   EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess);
 371   EXPECT_EQ(MergePhi->getIncomingValue(1), NewStoreAccess);
 372   MSSA.verifyMemorySSA();
 373 }
 374
 375 TEST_F(MemorySSATest, MoveAStoreUpdaterMove) {
 376   // We create a diamond where there is a in the entry, a store on one side, and
 377   // a load at the end.  After building MemorySSA, we test updating by moving
 378   // the store from the side block to the entry block.  This does not destroy
 379   // the old access.
 380   F = Function::Create(
 381       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 382       GlobalValue::ExternalLinkage, "F", &M);
 383   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 384   BasicBlock *Left(BasicBlock::Create(C, "", F));
 385   BasicBlock *Right(BasicBlock::Create(C, "", F));
 386   BasicBlock *Merge(BasicBlock::Create(C, "", F));
 387   B.SetInsertPoint(Entry);
 388   Argument *PointerArg = &*F->arg_begin();
 389   StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
 390   B.CreateCondBr(B.getTrue(), Left, Right);
 391   B.SetInsertPoint(Left);
 392   auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
 393   BranchInst::Create(Merge, Left);
 394   BranchInst::Create(Merge, Right);
 395   B.SetInsertPoint(Merge);
 396   auto *MergeLoad = B.CreateLoad(PointerArg);
 397   setupAnalyses();
 398   MemorySSA &MSSA = *Analyses->MSSA;
 399   MemorySSAUpdater Updater(&MSSA);
 400
 401   // Move the store
 402   auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
 403   auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
 404   // Before, the load will point to a phi of the EntryStore and SideStore.
 405   auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
 406   EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
 407   MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
 408   EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
 409   EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
 410   SideStore->moveBefore(*EntryStore->getParent(), ++EntryStore->getIterator());
 411   Updater.moveAfter(SideStoreAccess, EntryStoreAccess);
 412   // After, it's a phi of the side store.
 413   EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
 414   EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess);
 415
 416   MSSA.verifyMemorySSA();
 417 }
 418
 419 TEST_F(MemorySSATest, MoveAStoreAllAround) {
 420   // We create a diamond where there is a in the entry, a store on one side, and
 421   // a load at the end.  After building MemorySSA, we test updating by moving
 422   // the store from the side block to the entry block, then to the other side
 423   // block, then to before the load.  This does not destroy the old access.
 424   F = Function::Create(
 425       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 426       GlobalValue::ExternalLinkage, "F", &M);
 427   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 428   BasicBlock *Left(BasicBlock::Create(C, "", F));
 429   BasicBlock *Right(BasicBlock::Create(C, "", F));
 430   BasicBlock *Merge(BasicBlock::Create(C, "", F));
 431   B.SetInsertPoint(Entry);
 432   Argument *PointerArg = &*F->arg_begin();
 433   StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);
 434   B.CreateCondBr(B.getTrue(), Left, Right);
 435   B.SetInsertPoint(Left);
 436   auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);
 437   BranchInst::Create(Merge, Left);
 438   BranchInst::Create(Merge, Right);
 439   B.SetInsertPoint(Merge);
 440   auto *MergeLoad = B.CreateLoad(PointerArg);
 441   setupAnalyses();
 442   MemorySSA &MSSA = *Analyses->MSSA;
 443   MemorySSAUpdater Updater(&MSSA);
 444
 445   // Move the store
 446   auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);
 447   auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);
 448   // Before, the load will point to a phi of the EntryStore and SideStore.
 449   auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));
 450   EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));
 451   MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());
 452   EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
 453   EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);
 454   // Move the store before the entry store
 455   SideStore->moveBefore(*EntryStore->getParent(), EntryStore->getIterator());
 456   Updater.moveBefore(SideStoreAccess, EntryStoreAccess);
 457   // After, it's a phi of the entry store.
 458   EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
 459   EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
 460   MSSA.verifyMemorySSA();
 461   // Now move the store to the right branch
 462   SideStore->moveBefore(*Right, Right->begin());
 463   Updater.moveToPlace(SideStoreAccess, Right, MemorySSA::Beginning);
 464   MSSA.verifyMemorySSA();
 465   EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
 466   EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess);
 467   // Now move it before the load
 468   SideStore->moveBefore(MergeLoad);
 469   Updater.moveBefore(SideStoreAccess, LoadAccess);
 470   EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);
 471   EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);
 472   MSSA.verifyMemorySSA();
 473 }
 474
 475 TEST_F(MemorySSATest, RemoveAPhi) {
 476   // We create a diamond where there is a store on one side, and then a load
 477   // after the merge point.  This enables us to test a bunch of different
 478   // removal cases.
 479   F = Function::Create(
 480       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 481       GlobalValue::ExternalLinkage, "F", &M);
 482   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 483   BasicBlock *Left(BasicBlock::Create(C, "", F));
 484   BasicBlock *Right(BasicBlock::Create(C, "", F));
 485   BasicBlock *Merge(BasicBlock::Create(C, "", F));
 486   B.SetInsertPoint(Entry);
 487   B.CreateCondBr(B.getTrue(), Left, Right);
 488   B.SetInsertPoint(Left);
 489   Argument *PointerArg = &*F->arg_begin();
 490   StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);
 491   BranchInst::Create(Merge, Left);
 492   BranchInst::Create(Merge, Right);
 493   B.SetInsertPoint(Merge);
 494   LoadInst *LoadInst = B.CreateLoad(PointerArg);
 495
 496   setupAnalyses();
 497   MemorySSA &MSSA = *Analyses->MSSA;
 498   MemorySSAUpdater Updater(&MSSA);
 499
 500   // Before, the load will be a use of a phi<store, liveonentry>.
 501   MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));
 502   MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
 503   MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
 504   EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
 505   // Kill the store
 506   Updater.removeMemoryAccess(StoreAccess);
 507   MemoryPhi *MP = cast<MemoryPhi>(DefiningAccess);
 508   // Verify the phi ended up as liveonentry, liveonentry
 509   for (auto &Op : MP->incoming_values())
 510     EXPECT_TRUE(MSSA.isLiveOnEntryDef(cast<MemoryAccess>(Op.get())));
 511   // Replace the phi uses with the live on entry def
 512   MP->replaceAllUsesWith(MSSA.getLiveOnEntryDef());
 513   // Verify the load is now defined by liveOnEntryDef
 514   EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
 515   // Remove the PHI
 516   Updater.removeMemoryAccess(MP);
 517   MSSA.verifyMemorySSA();
 518 }
 519
 520 TEST_F(MemorySSATest, RemoveMemoryAccess) {
 521   // We create a diamond where there is a store on one side, and then a load
 522   // after the merge point.  This enables us to test a bunch of different
 523   // removal cases.
 524   F = Function::Create(
 525       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 526       GlobalValue::ExternalLinkage, "F", &M);
 527   BasicBlock *Entry(BasicBlock::Create(C, "", F));
 528   BasicBlock *Left(BasicBlock::Create(C, "", F));
 529   BasicBlock *Right(BasicBlock::Create(C, "", F));
 530   BasicBlock *Merge(BasicBlock::Create(C, "", F));
 531   B.SetInsertPoint(Entry);
 532   B.CreateCondBr(B.getTrue(), Left, Right);
 533   B.SetInsertPoint(Left);
 534   Argument *PointerArg = &*F->arg_begin();
 535   StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);
 536   BranchInst::Create(Merge, Left);
 537   BranchInst::Create(Merge, Right);
 538   B.SetInsertPoint(Merge);
 539   LoadInst *LoadInst = B.CreateLoad(PointerArg);
 540
 541   setupAnalyses();
 542   MemorySSA &MSSA = *Analyses->MSSA;
 543   MemorySSAWalker *Walker = Analyses->Walker;
 544   MemorySSAUpdater Updater(&MSSA);
 545
 546   // Before, the load will be a use of a phi<store, liveonentry>. It should be
 547   // the same after.
 548   MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));
 549   MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));
 550   MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
 551   EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
 552   // The load is currently clobbered by one of the phi arguments, so the walker
 553   // should determine the clobbering access as the phi.
 554   EXPECT_EQ(DefiningAccess, Walker->getClobberingMemoryAccess(LoadInst));
 555   Updater.removeMemoryAccess(StoreAccess);
 556   MSSA.verifyMemorySSA();
 557   // After the removeaccess, let's see if we got the right accesses
 558   // The load should still point to the phi ...
 559   EXPECT_EQ(DefiningAccess, LoadAccess->getDefiningAccess());
 560   // but we should now get live on entry for the clobbering definition of the
 561   // load, since it will walk past the phi node since every argument is the
 562   // same.
 563   // XXX: This currently requires either removing the phi or resetting optimized
 564   // on the load
 565
 566   EXPECT_FALSE(
 567       MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst)));
 568   // If we reset optimized, we get live on entry.
 569   LoadAccess->resetOptimized();
 570   EXPECT_TRUE(
 571       MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst)));
 572   // The phi should now be a two entry phi with two live on entry defs.
 573   for (const auto &Op : DefiningAccess->operands()) {
 574     MemoryAccess *Operand = cast<MemoryAccess>(&*Op);
 575     EXPECT_TRUE(MSSA.isLiveOnEntryDef(Operand));
 576   }
 577
 578   // Now we try to remove the single valued phi
 579   Updater.removeMemoryAccess(DefiningAccess);
 580   MSSA.verifyMemorySSA();
 581   // Now the load should be a load of live on entry.
 582   EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));
 583 }
 584
 585 // We had a bug with caching where the walker would report MemoryDef#3's clobber
 586 // (below) was MemoryDef#1.
 587 //
 588 // define void @F(i8*) {
 589 //   %A = alloca i8, i8 1
 590 // ; 1 = MemoryDef(liveOnEntry)
 591 //   store i8 0, i8* %A
 592 // ; 2 = MemoryDef(1)
 593 //   store i8 1, i8* %A
 594 // ; 3 = MemoryDef(2)
 595 //   store i8 2, i8* %A
 596 // }
 597 TEST_F(MemorySSATest, TestTripleStore) {
 598   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
 599                        GlobalValue::ExternalLinkage, "F", &M);
 600   B.SetInsertPoint(BasicBlock::Create(C, "", F));
 601   Type *Int8 = Type::getInt8Ty(C);
 602   Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
 603   StoreInst *S1 = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
 604   StoreInst *S2 = B.CreateStore(ConstantInt::get(Int8, 1), Alloca);
 605   StoreInst *S3 = B.CreateStore(ConstantInt::get(Int8, 2), Alloca);
 606
 607   setupAnalyses();
 608   MemorySSA &MSSA = *Analyses->MSSA;
 609   MemorySSAWalker *Walker = Analyses->Walker;
 610
 611   unsigned I = 0;
 612   for (StoreInst *V : {S1, S2, S3}) {
 613     // Everything should be clobbered by its defining access
 614     MemoryAccess *DefiningAccess = MSSA.getMemoryAccess(V)->getDefiningAccess();
 615     MemoryAccess *WalkerClobber = Walker->getClobberingMemoryAccess(V);
 616     EXPECT_EQ(DefiningAccess, WalkerClobber)
 617         << "Store " << I << " doesn't have the correct clobbering access";
 618     // EXPECT_EQ expands such that if we increment I above, it won't get
 619     // incremented except when we try to print the error message.
 620     ++I;
 621   }
 622 }
 623
 624 // ...And fixing the above bug made it obvious that, when walking, MemorySSA's
 625 // walker was caching the initial node it walked. This was fine (albeit
 626 // mostly redundant) unless the initial node being walked is a clobber for the
 627 // query. In that case, we'd cache that the node clobbered itself.
 628 TEST_F(MemorySSATest, TestStoreAndLoad) {
 629   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
 630                        GlobalValue::ExternalLinkage, "F", &M);
 631   B.SetInsertPoint(BasicBlock::Create(C, "", F));
 632   Type *Int8 = Type::getInt8Ty(C);
 633   Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
 634   Instruction *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
 635   Instruction *LI = B.CreateLoad(Alloca);
 636
 637   setupAnalyses();
 638   MemorySSA &MSSA = *Analyses->MSSA;
 639   MemorySSAWalker *Walker = Analyses->Walker;
 640
 641   MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LI);
 642   EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SI));
 643   EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SI)));
 644 }
 645
 646 // Another bug (related to the above two fixes): It was noted that, given the
 647 // following code:
 648 // ; 1 = MemoryDef(liveOnEntry)
 649 // store i8 0, i8* %1
 650 //
 651 // ...A query to getClobberingMemoryAccess(MemoryAccess*, MemoryLocation) would
 652 // hand back the store (correctly). A later call to
 653 // getClobberingMemoryAccess(const Instruction*) would also hand back the store
 654 // (incorrectly; it should return liveOnEntry).
 655 //
 656 // This test checks that repeated calls to either function returns what they're
 657 // meant to.
 658 TEST_F(MemorySSATest, TestStoreDoubleQuery) {
 659   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
 660                        GlobalValue::ExternalLinkage, "F", &M);
 661   B.SetInsertPoint(BasicBlock::Create(C, "", F));
 662   Type *Int8 = Type::getInt8Ty(C);
 663   Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
 664   StoreInst *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
 665
 666   setupAnalyses();
 667   MemorySSA &MSSA = *Analyses->MSSA;
 668   MemorySSAWalker *Walker = Analyses->Walker;
 669
 670   MemoryAccess *StoreAccess = MSSA.getMemoryAccess(SI);
 671   MemoryLocation StoreLoc = MemoryLocation::get(SI);
 672   MemoryAccess *Clobber =
 673       Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);
 674   MemoryAccess *LiveOnEntry = Walker->getClobberingMemoryAccess(SI);
 675
 676   EXPECT_EQ(Clobber, StoreAccess);
 677   EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));
 678
 679   // Try again (with entries in the cache already) for good measure...
 680   Clobber = Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);
 681   LiveOnEntry = Walker->getClobberingMemoryAccess(SI);
 682   EXPECT_EQ(Clobber, StoreAccess);
 683   EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));
 684 }
 685
 686 // Bug: During phi optimization, the walker wouldn't cache to the proper result
 687 // in the farthest-walked BB.
 688 //
 689 // Specifically, it would assume that whatever we walked to was a clobber.
 690 // "Whatever we walked to" isn't a clobber if we hit a cache entry.
 691 //
 692 // ...So, we need a test case that looks like:
 693 //    A
 694 //   / \
 695 //  B   |
 696 //   \ /
 697 //    C
 698 //
 699 // Where, when we try to optimize a thing in 'C', a blocker is found in 'B'.
 700 // The walk must determine that the blocker exists by using cache entries *while
 701 // walking* 'B'.
 702 TEST_F(MemorySSATest, PartialWalkerCacheWithPhis) {
 703   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
 704                        GlobalValue::ExternalLinkage, "F", &M);
 705   B.SetInsertPoint(BasicBlock::Create(C, "A", F));
 706   Type *Int8 = Type::getInt8Ty(C);
 707   Constant *One = ConstantInt::get(Int8, 1);
 708   Constant *Zero = ConstantInt::get(Int8, 0);
 709   Value *AllocA = B.CreateAlloca(Int8, One, "a");
 710   Value *AllocB = B.CreateAlloca(Int8, One, "b");
 711   BasicBlock *IfThen = BasicBlock::Create(C, "B", F);
 712   BasicBlock *IfEnd = BasicBlock::Create(C, "C", F);
 713
 714   B.CreateCondBr(UndefValue::get(Type::getInt1Ty(C)), IfThen, IfEnd);
 715
 716   B.SetInsertPoint(IfThen);
 717   Instruction *FirstStore = B.CreateStore(Zero, AllocA);
 718   B.CreateStore(Zero, AllocB);
 719   Instruction *ALoad0 = B.CreateLoad(AllocA, "");
 720   Instruction *BStore = B.CreateStore(Zero, AllocB);
 721   // Due to use optimization/etc. we make a store to A, which is removed after
 722   // we build MSSA. This helps keep the test case simple-ish.
 723   Instruction *KillStore = B.CreateStore(Zero, AllocA);
 724   Instruction *ALoad = B.CreateLoad(AllocA, "");
 725   B.CreateBr(IfEnd);
 726
 727   B.SetInsertPoint(IfEnd);
 728   Instruction *BelowPhi = B.CreateStore(Zero, AllocA);
 729
 730   setupAnalyses();
 731   MemorySSA &MSSA = *Analyses->MSSA;
 732   MemorySSAWalker *Walker = Analyses->Walker;
 733   MemorySSAUpdater Updater(&MSSA);
 734
 735   // Kill `KillStore`; it exists solely so that the load after it won't be
 736   // optimized to FirstStore.
 737   Updater.removeMemoryAccess(MSSA.getMemoryAccess(KillStore));
 738   KillStore->eraseFromParent();
 739   auto *ALoadMA = cast<MemoryUse>(MSSA.getMemoryAccess(ALoad));
 740   EXPECT_EQ(ALoadMA->getDefiningAccess(), MSSA.getMemoryAccess(BStore));
 741
 742   // Populate the cache for the store to AllocB directly after FirstStore. It
 743   // should point to something in block B (so something in D can't be optimized
 744   // to it).
 745   MemoryAccess *Load0Clobber = Walker->getClobberingMemoryAccess(ALoad0);
 746   EXPECT_EQ(MSSA.getMemoryAccess(FirstStore), Load0Clobber);
 747
 748   // If the bug exists, this will introduce a bad cache entry for %a on BStore.
 749   // It will point to the store to %b after FirstStore. This only happens during
 750   // phi optimization.
 751   MemoryAccess *BottomClobber = Walker->getClobberingMemoryAccess(BelowPhi);
 752   MemoryAccess *Phi = MSSA.getMemoryAccess(IfEnd);
 753   EXPECT_EQ(BottomClobber, Phi);
 754
 755   // This query will first check the cache for {%a, BStore}. It should point to
 756   // FirstStore, not to the store after FirstStore.
 757   MemoryAccess *UseClobber = Walker->getClobberingMemoryAccess(ALoad);
 758   EXPECT_EQ(UseClobber, MSSA.getMemoryAccess(FirstStore));
 759 }
 760
 761 // Test that our walker properly handles loads with the invariant group
 762 // attribute. It's a bit hacky, since we add the invariant attribute *after*
 763 // building MSSA. Otherwise, the use optimizer will optimize it for us, which
 764 // isn't what we want.
 765 // FIXME: It may be easier/cleaner to just add an 'optimize uses?' flag to MSSA.
 766 TEST_F(MemorySSATest, WalkerInvariantLoadOpt) {
 767   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
 768                        GlobalValue::ExternalLinkage, "F", &M);
 769   B.SetInsertPoint(BasicBlock::Create(C, "", F));
 770   Type *Int8 = Type::getInt8Ty(C);
 771   Constant *One = ConstantInt::get(Int8, 1);
 772   Value *AllocA = B.CreateAlloca(Int8, One, "");
 773
 774   Instruction *Store = B.CreateStore(One, AllocA);
 775   Instruction *Load = B.CreateLoad(AllocA);
 776
 777   setupAnalyses();
 778   MemorySSA &MSSA = *Analyses->MSSA;
 779   MemorySSAWalker *Walker = Analyses->Walker;
 780
 781   auto *LoadMA = cast<MemoryUse>(MSSA.getMemoryAccess(Load));
 782   auto *StoreMA = cast<MemoryDef>(MSSA.getMemoryAccess(Store));
 783   EXPECT_EQ(LoadMA->getDefiningAccess(), StoreMA);
 784
 785   // ...At the time of writing, no cache should exist for LoadMA. Be a bit
 786   // flexible to future changes.
 787   Walker->invalidateInfo(LoadMA);
 788   Load->setMetadata(LLVMContext::MD_invariant_load, MDNode::get(C, {}));
 789
 790   MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LoadMA);
 791   EXPECT_EQ(LoadClobber, MSSA.getLiveOnEntryDef());
 792 }
 793
 794 // Test loads get reoptimized properly by the walker.
 795 TEST_F(MemorySSATest, WalkerReopt) {
 796   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
 797                        GlobalValue::ExternalLinkage, "F", &M);
 798   B.SetInsertPoint(BasicBlock::Create(C, "", F));
 799   Type *Int8 = Type::getInt8Ty(C);
 800   Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
 801   Instruction *SIA = B.CreateStore(ConstantInt::get(Int8, 0), AllocaA);
 802   Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
 803   Instruction *SIB = B.CreateStore(ConstantInt::get(Int8, 0), AllocaB);
 804   Instruction *LIA = B.CreateLoad(AllocaA);
 805
 806   setupAnalyses();
 807   MemorySSA &MSSA = *Analyses->MSSA;
 808   MemorySSAWalker *Walker = Analyses->Walker;
 809   MemorySSAUpdater Updater(&MSSA);
 810
 811   MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LIA);
 812   MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LIA));
 813   EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SIA));
 814   EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SIA)));
 815   Updater.removeMemoryAccess(LoadAccess);
 816
 817   // Create the load memory access pointing to an unoptimized place.
 818   MemoryUse *NewLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
 819       LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End));
 820   // This should it cause it to be optimized
 821   EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber);
 822   EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber);
 823 }
 824
 825 // Test out MemorySSAUpdater::moveBefore
 826 TEST_F(MemorySSATest, MoveAboveMemoryDef) {
 827   F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),
 828                        GlobalValue::ExternalLinkage, "F", &M);
 829   B.SetInsertPoint(BasicBlock::Create(C, "", F));
 830
 831   Type *Int8 = Type::getInt8Ty(C);
 832   Value *A = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
 833   Value *B_ = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");
 834   Value *C = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");
 835
 836   StoreInst *StoreA0 = B.CreateStore(ConstantInt::get(Int8, 0), A);
 837   StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 0), B_);
 838   LoadInst *LoadB = B.CreateLoad(B_);
 839   StoreInst *StoreA1 = B.CreateStore(ConstantInt::get(Int8, 4), A);
 840   StoreInst *StoreC = B.CreateStore(ConstantInt::get(Int8, 4), C);
 841   StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 4), A);
 842   LoadInst *LoadC = B.CreateLoad(C);
 843
 844   setupAnalyses();
 845   MemorySSA &MSSA = *Analyses->MSSA;
 846   MemorySSAWalker &Walker = *Analyses->Walker;
 847
 848   MemorySSAUpdater Updater(&MSSA);
 849   StoreC->moveBefore(StoreB);
 850   Updater.moveBefore(cast<MemoryDef>(MSSA.getMemoryAccess(StoreC)),
 851                      cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)));
 852
 853   MSSA.verifyMemorySSA();
 854
 855   EXPECT_EQ(MSSA.getMemoryAccess(StoreB)->getDefiningAccess(),
 856             MSSA.getMemoryAccess(StoreC));
 857   EXPECT_EQ(MSSA.getMemoryAccess(StoreC)->getDefiningAccess(),
 858             MSSA.getMemoryAccess(StoreA0));
 859   EXPECT_EQ(MSSA.getMemoryAccess(StoreA2)->getDefiningAccess(),
 860             MSSA.getMemoryAccess(StoreA1));
 861   EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadB),
 862             MSSA.getMemoryAccess(StoreB));
 863   EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadC),
 864             MSSA.getMemoryAccess(StoreC));
 865
 866   // exercise block numbering
 867   EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreC),
 868                                     MSSA.getMemoryAccess(StoreB)));
 869   EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1),
 870                                     MSSA.getMemoryAccess(StoreA2)));
 871 }
 872
 873 TEST_F(MemorySSATest, Irreducible) {
 874   // Create the equivalent of
 875   // x = something
 876   // if (...)
 877   //    goto second_loop_entry
 878   // while (...) {
 879   // second_loop_entry:
 880   // }
 881   // use(x)
 882
 883   SmallVector<PHINode *, 8> Inserted;
 884   IRBuilder<> B(C);
 885   F = Function::Create(
 886       FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
 887       GlobalValue::ExternalLinkage, "F", &M);
 888
 889   // Make blocks
 890   BasicBlock *IfBB = BasicBlock::Create(C, "if", F);
 891   BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F);
 892   BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F);
 893   BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F);
 894   B.SetInsertPoint(IfBB);
 895   B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB);
 896   B.SetInsertPoint(LoopStartBB);
 897   B.CreateBr(LoopMainBB);
 898   B.SetInsertPoint(LoopMainBB);
 899   B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB);
 900   B.SetInsertPoint(AfterLoopBB);
 901   Argument *FirstArg = &*F->arg_begin();
 902   setupAnalyses();
 903   MemorySSA &MSSA = *Analyses->MSSA;
 904   MemorySSAUpdater Updater(&MSSA);
 905   // Create the load memory acccess
 906   LoadInst *LoadInst = B.CreateLoad(FirstArg);
 907   MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
 908       LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning));
 909   Updater.insertUse(LoadAccess);
 910   MSSA.verifyMemorySSA();
 911 }