1774 lines · cpp
1//===- MemorySSA.cpp - Unit tests for MemorySSA ---------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8#include "llvm/Analysis/MemorySSA.h"9#include "llvm/Analysis/AliasAnalysis.h"10#include "llvm/Analysis/AssumptionCache.h"11#include "llvm/Analysis/BasicAliasAnalysis.h"12#include "llvm/Analysis/MemorySSAUpdater.h"13#include "llvm/Analysis/TargetLibraryInfo.h"14#include "llvm/AsmParser/Parser.h"15#include "llvm/IR/BasicBlock.h"16#include "llvm/IR/DataLayout.h"17#include "llvm/IR/Dominators.h"18#include "llvm/IR/IRBuilder.h"19#include "llvm/IR/Instructions.h"20#include "llvm/IR/LLVMContext.h"21#include "llvm/IR/Module.h"22#include "llvm/Support/SourceMgr.h"23#include "gtest/gtest.h"24 25using namespace llvm;26 27const static char DLString[] = "e-i64:64-f80:128-n8:16:32:64-S128";28 29/// There's a lot of common setup between these tests. This fixture helps reduce30/// that. Tests should mock up a function, store it in F, and then call31/// setupAnalyses().32class MemorySSATest : public testing::Test {33protected:34 // N.B. Many of these members depend on each other (e.g. the Module depends on35 // the Context, etc.). So, order matters here (and in TestAnalyses).36 LLVMContext C;37 Module M;38 IRBuilder<> B;39 DataLayout DL;40 TargetLibraryInfoImpl TLII;41 TargetLibraryInfo TLI;42 Function *F;43 44 // Things that we need to build after the function is created.45 struct TestAnalyses {46 DominatorTree DT;47 AssumptionCache AC;48 AAResults AA;49 BasicAAResult BAA;50 // We need to defer MSSA construction until AA is *entirely* set up, which51 // requires calling addAAResult. Hence, we just use a pointer here.52 std::unique_ptr<MemorySSA> MSSA;53 MemorySSAWalker *Walker;54 55 TestAnalyses(MemorySSATest &Test)56 : DT(*Test.F), AC(*Test.F), AA(Test.TLI),57 BAA(Test.DL, *Test.F, Test.TLI, AC, &DT) {58 AA.addAAResult(BAA);59 MSSA = std::make_unique<MemorySSA>(*Test.F, &AA, &DT);60 Walker = MSSA->getWalker();61 }62 };63 64 std::unique_ptr<TestAnalyses> Analyses;65 66 void setupAnalyses() {67 assert(F);68 Analyses.reset(new TestAnalyses(*this));69 }70 71public:72 MemorySSATest()73 : M("MemorySSATest", C), B(C), DL(DLString), TLII(M.getTargetTriple()),74 TLI(TLII), F(nullptr) {}75};76 77TEST_F(MemorySSATest, CreateALoad) {78 // We create a diamond where there is a store on one side, and then after79 // building MemorySSA, create a load after the merge point, and use it to test80 // updating by creating an access for the load.81 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),82 GlobalValue::ExternalLinkage, "F", &M);83 BasicBlock *Entry(BasicBlock::Create(C, "", F));84 BasicBlock *Left(BasicBlock::Create(C, "", F));85 BasicBlock *Right(BasicBlock::Create(C, "", F));86 BasicBlock *Merge(BasicBlock::Create(C, "", F));87 B.SetInsertPoint(Entry);88 B.CreateCondBr(B.getTrue(), Left, Right);89 B.SetInsertPoint(Left);90 Argument *PointerArg = &*F->arg_begin();91 B.CreateStore(B.getInt8(16), PointerArg);92 BranchInst::Create(Merge, Left);93 BranchInst::Create(Merge, Right);94 95 setupAnalyses();96 MemorySSA &MSSA = *Analyses->MSSA;97 MemorySSAUpdater Updater(&MSSA);98 // Add the load99 B.SetInsertPoint(Merge);100 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), PointerArg);101 102 // MemoryPHI should already exist.103 MemoryPhi *MP = MSSA.getMemoryAccess(Merge);104 EXPECT_NE(MP, nullptr);105 106 // Create the load memory acccess107 MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(108 LoadInst, MP, Merge, MemorySSA::Beginning));109 MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();110 EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));111 MSSA.verifyMemorySSA();112}113TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {114 // We create a diamond, then build memoryssa with no memory accesses, and115 // incrementally update it by inserting a store in the, entry, a load in the116 // merge point, then a store in the branch, another load in the merge point,117 // and then a store in the entry.118 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),119 GlobalValue::ExternalLinkage, "F", &M);120 BasicBlock *Entry(BasicBlock::Create(C, "", F));121 BasicBlock *Left(BasicBlock::Create(C, "", F));122 BasicBlock *Right(BasicBlock::Create(C, "", F));123 BasicBlock *Merge(BasicBlock::Create(C, "", F));124 B.SetInsertPoint(Entry);125 B.CreateCondBr(B.getTrue(), Left, Right);126 B.SetInsertPoint(Left, Left->begin());127 Argument *PointerArg = &*F->arg_begin();128 B.SetInsertPoint(Left);129 B.CreateBr(Merge);130 B.SetInsertPoint(Right);131 B.CreateBr(Merge);132 133 setupAnalyses();134 MemorySSA &MSSA = *Analyses->MSSA;135 MemorySSAUpdater Updater(&MSSA);136 // Add the store137 B.SetInsertPoint(Entry, Entry->begin());138 StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);139 MemoryAccess *EntryStoreAccess = Updater.createMemoryAccessInBB(140 EntryStore, nullptr, Entry, MemorySSA::Beginning);141 Updater.insertDef(cast<MemoryDef>(EntryStoreAccess));142 143 // Add the load144 B.SetInsertPoint(Merge, Merge->begin());145 LoadInst *FirstLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);146 147 // MemoryPHI should not already exist.148 MemoryPhi *MP = MSSA.getMemoryAccess(Merge);149 EXPECT_EQ(MP, nullptr);150 151 // Create the load memory access152 MemoryUse *FirstLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(153 FirstLoad, nullptr, Merge, MemorySSA::Beginning));154 Updater.insertUse(FirstLoadAccess);155 // Should just have a load using the entry access, because it should discover156 // the phi is trivial157 EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), EntryStoreAccess);158 159 // Create a store on the left160 // Add the store161 B.SetInsertPoint(Left, Left->begin());162 StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg);163 MemoryAccess *LeftStoreAccess = Updater.createMemoryAccessInBB(164 LeftStore, nullptr, Left, MemorySSA::Beginning);165 Updater.insertDef(cast<MemoryDef>(LeftStoreAccess), false);166 167 // MemoryPHI should exist after adding LeftStore.168 MP = MSSA.getMemoryAccess(Merge);169 EXPECT_NE(MP, nullptr);170 171 // Add the second load172 B.SetInsertPoint(Merge, Merge->begin());173 LoadInst *SecondLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);174 175 // Create the load memory access176 MemoryUse *SecondLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(177 SecondLoad, nullptr, Merge, MemorySSA::Beginning));178 Updater.insertUse(SecondLoadAccess);179 // Now the load should be a phi of the entry store and the left store180 MemoryPhi *MergePhi =181 dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());182 EXPECT_NE(MergePhi, nullptr);183 EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);184 EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);185 // Now create a store below the existing one in the entry186 B.SetInsertPoint(Entry, --Entry->end());187 StoreInst *SecondEntryStore = B.CreateStore(B.getInt8(16), PointerArg);188 MemoryAccess *SecondEntryStoreAccess = Updater.createMemoryAccessInBB(189 SecondEntryStore, nullptr, Entry, MemorySSA::End);190 // Insert it twice just to test renaming191 Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess), false);192 EXPECT_NE(FirstLoadAccess->getDefiningAccess(), MergePhi);193 Updater.insertDef(cast<MemoryDef>(SecondEntryStoreAccess), true);194 EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), MergePhi);195 // and make sure the phi below it got updated, despite being blocks away196 MergePhi = dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());197 EXPECT_NE(MergePhi, nullptr);198 EXPECT_EQ(MergePhi->getIncomingValue(0), SecondEntryStoreAccess);199 EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess);200 MSSA.verifyMemorySSA();201}202 203TEST_F(MemorySSATest, CreateALoadUpdater) {204 // We create a diamond, then build memoryssa with no memory accesses, and205 // incrementally update it by inserting a store in one of the branches, and a206 // load in the merge point207 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),208 GlobalValue::ExternalLinkage, "F", &M);209 BasicBlock *Entry(BasicBlock::Create(C, "", F));210 BasicBlock *Left(BasicBlock::Create(C, "", F));211 BasicBlock *Right(BasicBlock::Create(C, "", F));212 BasicBlock *Merge(BasicBlock::Create(C, "", F));213 B.SetInsertPoint(Entry);214 B.CreateCondBr(B.getTrue(), Left, Right);215 B.SetInsertPoint(Left, Left->begin());216 Argument *PointerArg = &*F->arg_begin();217 B.SetInsertPoint(Left);218 B.CreateBr(Merge);219 B.SetInsertPoint(Right);220 B.CreateBr(Merge);221 222 setupAnalyses();223 MemorySSA &MSSA = *Analyses->MSSA;224 MemorySSAUpdater Updater(&MSSA);225 B.SetInsertPoint(Left, Left->begin());226 // Add the store227 StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg);228 MemoryAccess *StoreAccess =229 Updater.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning);230 Updater.insertDef(cast<MemoryDef>(StoreAccess));231 232 // MemoryPHI should be created when inserting the def233 MemoryPhi *MP = MSSA.getMemoryAccess(Merge);234 EXPECT_NE(MP, nullptr);235 236 // Add the load237 B.SetInsertPoint(Merge, Merge->begin());238 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), PointerArg);239 240 // Create the load memory acccess241 MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(242 LoadInst, nullptr, Merge, MemorySSA::Beginning));243 Updater.insertUse(LoadAccess);244 MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();245 EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));246 MSSA.verifyMemorySSA();247}248 249TEST_F(MemorySSATest, SinkLoad) {250 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),251 GlobalValue::ExternalLinkage, "F", &M);252 BasicBlock *Entry(BasicBlock::Create(C, "", F));253 BasicBlock *Left(BasicBlock::Create(C, "", F));254 BasicBlock *Right(BasicBlock::Create(C, "", F));255 BasicBlock *Merge(BasicBlock::Create(C, "", F));256 B.SetInsertPoint(Entry);257 B.CreateCondBr(B.getTrue(), Left, Right);258 B.SetInsertPoint(Left, Left->begin());259 Argument *PointerArg = &*F->arg_begin();260 B.SetInsertPoint(Left);261 B.CreateBr(Merge);262 B.SetInsertPoint(Right);263 B.CreateBr(Merge);264 265 // Load in left block266 B.SetInsertPoint(Left, Left->begin());267 LoadInst *LoadInst1 = B.CreateLoad(B.getInt8Ty(), PointerArg);268 // Store in merge block269 B.SetInsertPoint(Merge, Merge->begin());270 B.CreateStore(B.getInt8(16), PointerArg);271 272 setupAnalyses();273 MemorySSA &MSSA = *Analyses->MSSA;274 MemorySSAUpdater Updater(&MSSA);275 276 // Mimic sinking of a load:277 // - clone load278 // - insert in "exit" block279 // - insert in mssa280 // - remove from original block281 282 LoadInst *LoadInstClone = cast<LoadInst>(LoadInst1->clone());283 LoadInstClone->insertInto(Merge, Merge->begin());284 MemoryAccess * NewLoadAccess =285 Updater.createMemoryAccessInBB(LoadInstClone, nullptr,286 LoadInstClone->getParent(),287 MemorySSA::Beginning);288 Updater.insertUse(cast<MemoryUse>(NewLoadAccess));289 MSSA.verifyMemorySSA();290 Updater.removeMemoryAccess(MSSA.getMemoryAccess(LoadInst1));291 MSSA.verifyMemorySSA();292}293 294TEST_F(MemorySSATest, MoveAStore) {295 // We create a diamond where there is a in the entry, a store on one side, and296 // a load at the end. After building MemorySSA, we test updating by moving297 // the store from the side block to the entry block. This destroys the old298 // access.299 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, 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(B.getInt8Ty(), PointerArg);315 setupAnalyses();316 MemorySSA &MSSA = *Analyses->MSSA;317 MemorySSAUpdater Updater(&MSSA);318 // Move the store319 SideStore->moveBefore(Entry->getTerminator()->getIterator());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 329TEST_F(MemorySSATest, MoveAStoreUpdater) {330 // We create a diamond where there is a in the entry, a store on one side, and331 // a load at the end. After building MemorySSA, we test updating by moving332 // the store from the side block to the entry block. This destroys the old333 // access.334 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),335 GlobalValue::ExternalLinkage, "F", &M);336 BasicBlock *Entry(BasicBlock::Create(C, "", F));337 BasicBlock *Left(BasicBlock::Create(C, "", F));338 BasicBlock *Right(BasicBlock::Create(C, "", F));339 BasicBlock *Merge(BasicBlock::Create(C, "", F));340 B.SetInsertPoint(Entry);341 Argument *PointerArg = &*F->arg_begin();342 StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);343 B.CreateCondBr(B.getTrue(), Left, Right);344 B.SetInsertPoint(Left);345 auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);346 BranchInst::Create(Merge, Left);347 BranchInst::Create(Merge, Right);348 B.SetInsertPoint(Merge);349 auto *MergeLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);350 setupAnalyses();351 MemorySSA &MSSA = *Analyses->MSSA;352 MemorySSAUpdater Updater(&MSSA);353 354 // Move the store355 SideStore->moveBefore(Entry->getTerminator()->getIterator());356 auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);357 auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);358 auto *NewStoreAccess = Updater.createMemoryAccessAfter(359 SideStore, EntryStoreAccess, EntryStoreAccess);360 // Before, the load will point to a phi of the EntryStore and SideStore.361 auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));362 EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));363 MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());364 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);365 EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);366 Updater.removeMemoryAccess(SideStoreAccess);367 Updater.insertDef(cast<MemoryDef>(NewStoreAccess));368 // After it's a phi of the new side store access.369 EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess);370 EXPECT_EQ(MergePhi->getIncomingValue(1), NewStoreAccess);371 MSSA.verifyMemorySSA();372}373 374TEST_F(MemorySSATest, MoveAStoreUpdaterMove) {375 // We create a diamond where there is a in the entry, a store on one side, and376 // a load at the end. After building MemorySSA, we test updating by moving377 // the store from the side block to the entry block. This does not destroy378 // the old access.379 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),380 GlobalValue::ExternalLinkage, "F", &M);381 BasicBlock *Entry(BasicBlock::Create(C, "", F));382 BasicBlock *Left(BasicBlock::Create(C, "", F));383 BasicBlock *Right(BasicBlock::Create(C, "", F));384 BasicBlock *Merge(BasicBlock::Create(C, "", F));385 B.SetInsertPoint(Entry);386 Argument *PointerArg = &*F->arg_begin();387 StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);388 B.CreateCondBr(B.getTrue(), Left, Right);389 B.SetInsertPoint(Left);390 auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);391 BranchInst::Create(Merge, Left);392 BranchInst::Create(Merge, Right);393 B.SetInsertPoint(Merge);394 auto *MergeLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);395 setupAnalyses();396 MemorySSA &MSSA = *Analyses->MSSA;397 MemorySSAUpdater Updater(&MSSA);398 399 // Move the store400 auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);401 auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);402 // Before, the load will point to a phi of the EntryStore and SideStore.403 auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));404 EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));405 MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());406 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);407 EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);408 SideStore->moveBefore(*EntryStore->getParent(), ++EntryStore->getIterator());409 Updater.moveAfter(SideStoreAccess, EntryStoreAccess);410 // After, it's a phi of the side store.411 EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);412 EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess);413 414 MSSA.verifyMemorySSA();415}416 417TEST_F(MemorySSATest, MoveAStoreAllAround) {418 // We create a diamond where there is a in the entry, a store on one side, and419 // a load at the end. After building MemorySSA, we test updating by moving420 // the store from the side block to the entry block, then to the other side421 // block, then to before the load. This does not destroy the old access.422 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),423 GlobalValue::ExternalLinkage, "F", &M);424 BasicBlock *Entry(BasicBlock::Create(C, "", F));425 BasicBlock *Left(BasicBlock::Create(C, "", F));426 BasicBlock *Right(BasicBlock::Create(C, "", F));427 BasicBlock *Merge(BasicBlock::Create(C, "", F));428 B.SetInsertPoint(Entry);429 Argument *PointerArg = &*F->arg_begin();430 StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg);431 B.CreateCondBr(B.getTrue(), Left, Right);432 B.SetInsertPoint(Left);433 auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg);434 BranchInst::Create(Merge, Left);435 BranchInst::Create(Merge, Right);436 B.SetInsertPoint(Merge);437 auto *MergeLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);438 setupAnalyses();439 MemorySSA &MSSA = *Analyses->MSSA;440 MemorySSAUpdater Updater(&MSSA);441 442 // Move the store443 auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore);444 auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore);445 // Before, the load will point to a phi of the EntryStore and SideStore.446 auto *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(MergeLoad));447 EXPECT_TRUE(isa<MemoryPhi>(LoadAccess->getDefiningAccess()));448 MemoryPhi *MergePhi = cast<MemoryPhi>(LoadAccess->getDefiningAccess());449 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);450 EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess);451 // Move the store before the entry store452 SideStore->moveBefore(*EntryStore->getParent(), EntryStore->getIterator());453 Updater.moveBefore(SideStoreAccess, EntryStoreAccess);454 // After, it's a phi of the entry store.455 EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);456 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);457 MSSA.verifyMemorySSA();458 // Now move the store to the right branch459 SideStore->moveBefore(*Right, Right->begin());460 Updater.moveToPlace(SideStoreAccess, Right, MemorySSA::Beginning);461 MSSA.verifyMemorySSA();462 EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);463 EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess);464 // Now move it before the load465 SideStore->moveBefore(MergeLoad->getIterator());466 Updater.moveBefore(SideStoreAccess, LoadAccess);467 EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess);468 EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess);469 MSSA.verifyMemorySSA();470}471 472TEST_F(MemorySSATest, RemoveAPhi) {473 // We create a diamond where there is a store on one side, and then a load474 // after the merge point. This enables us to test a bunch of different475 // removal cases.476 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),477 GlobalValue::ExternalLinkage, "F", &M);478 BasicBlock *Entry(BasicBlock::Create(C, "", F));479 BasicBlock *Left(BasicBlock::Create(C, "", F));480 BasicBlock *Right(BasicBlock::Create(C, "", F));481 BasicBlock *Merge(BasicBlock::Create(C, "", F));482 B.SetInsertPoint(Entry);483 B.CreateCondBr(B.getTrue(), Left, Right);484 B.SetInsertPoint(Left);485 Argument *PointerArg = &*F->arg_begin();486 StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);487 BranchInst::Create(Merge, Left);488 BranchInst::Create(Merge, Right);489 B.SetInsertPoint(Merge);490 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), PointerArg);491 492 setupAnalyses();493 MemorySSA &MSSA = *Analyses->MSSA;494 MemorySSAUpdater Updater(&MSSA);495 496 // Before, the load will be a use of a phi<store, liveonentry>.497 MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));498 MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));499 MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();500 EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));501 // Kill the store502 Updater.removeMemoryAccess(StoreAccess);503 MemoryPhi *MP = cast<MemoryPhi>(DefiningAccess);504 // Verify the phi ended up as liveonentry, liveonentry505 for (auto &Op : MP->incoming_values())506 EXPECT_TRUE(MSSA.isLiveOnEntryDef(cast<MemoryAccess>(Op.get())));507 // Replace the phi uses with the live on entry def508 MP->replaceAllUsesWith(MSSA.getLiveOnEntryDef());509 // Verify the load is now defined by liveOnEntryDef510 EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));511 // Remove the PHI512 Updater.removeMemoryAccess(MP);513 MSSA.verifyMemorySSA();514}515 516TEST_F(MemorySSATest, RemoveMemoryAccess) {517 // We create a diamond where there is a store on one side, and then a load518 // after the merge point. This enables us to test a bunch of different519 // removal cases.520 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),521 GlobalValue::ExternalLinkage, "F", &M);522 BasicBlock *Entry(BasicBlock::Create(C, "", F));523 BasicBlock *Left(BasicBlock::Create(C, "", F));524 BasicBlock *Right(BasicBlock::Create(C, "", F));525 BasicBlock *Merge(BasicBlock::Create(C, "", F));526 B.SetInsertPoint(Entry);527 B.CreateCondBr(B.getTrue(), Left, Right);528 B.SetInsertPoint(Left);529 Argument *PointerArg = &*F->arg_begin();530 StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg);531 BranchInst::Create(Merge, Left);532 BranchInst::Create(Merge, Right);533 B.SetInsertPoint(Merge);534 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), PointerArg);535 536 setupAnalyses();537 MemorySSA &MSSA = *Analyses->MSSA;538 MemorySSAWalker *Walker = Analyses->Walker;539 MemorySSAUpdater Updater(&MSSA);540 541 // Before, the load will be a use of a phi<store, liveonentry>. It should be542 // the same after.543 MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LoadInst));544 MemoryDef *StoreAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreInst));545 MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();546 EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));547 // The load is currently clobbered by one of the phi arguments, so the walker548 // should determine the clobbering access as the phi.549 EXPECT_EQ(DefiningAccess, Walker->getClobberingMemoryAccess(LoadInst));550 Updater.removeMemoryAccess(StoreAccess);551 MSSA.verifyMemorySSA();552 // After the removeaccess, let's see if we got the right accesses553 // The load should still point to the phi ...554 EXPECT_EQ(DefiningAccess, LoadAccess->getDefiningAccess());555 // but we should now get live on entry for the clobbering definition of the556 // load, since it will walk past the phi node since every argument is the557 // same.558 // XXX: This currently requires either removing the phi or resetting optimized559 // on the load560 561 EXPECT_FALSE(562 MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst)));563 // If we reset optimized, we get live on entry.564 LoadAccess->resetOptimized();565 EXPECT_TRUE(566 MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst)));567 // The phi should now be a two entry phi with two live on entry defs.568 for (const auto &Op : DefiningAccess->operands()) {569 MemoryAccess *Operand = cast<MemoryAccess>(&*Op);570 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Operand));571 }572 573 // Now we try to remove the single valued phi574 Updater.removeMemoryAccess(DefiningAccess);575 MSSA.verifyMemorySSA();576 // Now the load should be a load of live on entry.577 EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess()));578}579 580// We had a bug with caching where the walker would report MemoryDef#3's clobber581// (below) was MemoryDef#1.582//583// define void @F(i8*) {584// %A = alloca i8, i8 1585// ; 1 = MemoryDef(liveOnEntry)586// store i8 0, i8* %A587// ; 2 = MemoryDef(1)588// store i8 1, i8* %A589// ; 3 = MemoryDef(2)590// store i8 2, i8* %A591// }592TEST_F(MemorySSATest, TestTripleStore) {593 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),594 GlobalValue::ExternalLinkage, "F", &M);595 B.SetInsertPoint(BasicBlock::Create(C, "", F));596 Type *Int8 = Type::getInt8Ty(C);597 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");598 StoreInst *S1 = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);599 StoreInst *S2 = B.CreateStore(ConstantInt::get(Int8, 1), Alloca);600 StoreInst *S3 = B.CreateStore(ConstantInt::get(Int8, 2), Alloca);601 602 setupAnalyses();603 MemorySSA &MSSA = *Analyses->MSSA;604 MemorySSAWalker *Walker = Analyses->Walker;605 606 unsigned I = 0;607 for (StoreInst *V : {S1, S2, S3}) {608 // Everything should be clobbered by its defining access609 MemoryAccess *DefiningAccess = MSSA.getMemoryAccess(V)->getDefiningAccess();610 MemoryAccess *WalkerClobber = Walker->getClobberingMemoryAccess(V);611 EXPECT_EQ(DefiningAccess, WalkerClobber)612 << "Store " << I << " doesn't have the correct clobbering access";613 // EXPECT_EQ expands such that if we increment I above, it won't get614 // incremented except when we try to print the error message.615 ++I;616 }617}618 619// ...And fixing the above bug made it obvious that, when walking, MemorySSA's620// walker was caching the initial node it walked. This was fine (albeit621// mostly redundant) unless the initial node being walked is a clobber for the622// query. In that case, we'd cache that the node clobbered itself.623TEST_F(MemorySSATest, TestStoreAndLoad) {624 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),625 GlobalValue::ExternalLinkage, "F", &M);626 B.SetInsertPoint(BasicBlock::Create(C, "", F));627 Type *Int8 = Type::getInt8Ty(C);628 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");629 Instruction *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);630 Instruction *LI = B.CreateLoad(Int8, Alloca);631 632 setupAnalyses();633 MemorySSA &MSSA = *Analyses->MSSA;634 MemorySSAWalker *Walker = Analyses->Walker;635 636 MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LI);637 EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SI));638 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SI)));639}640 641// Another bug (related to the above two fixes): It was noted that, given the642// following code:643// ; 1 = MemoryDef(liveOnEntry)644// store i8 0, i8* %1645//646// ...A query to getClobberingMemoryAccess(MemoryAccess*, MemoryLocation) would647// hand back the store (correctly). A later call to648// getClobberingMemoryAccess(const Instruction*) would also hand back the store649// (incorrectly; it should return liveOnEntry).650//651// This test checks that repeated calls to either function returns what they're652// meant to.653TEST_F(MemorySSATest, TestStoreDoubleQuery) {654 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),655 GlobalValue::ExternalLinkage, "F", &M);656 B.SetInsertPoint(BasicBlock::Create(C, "", F));657 Type *Int8 = Type::getInt8Ty(C);658 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");659 StoreInst *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca);660 661 setupAnalyses();662 MemorySSA &MSSA = *Analyses->MSSA;663 MemorySSAWalker *Walker = Analyses->Walker;664 665 MemoryAccess *StoreAccess = MSSA.getMemoryAccess(SI);666 MemoryLocation StoreLoc = MemoryLocation::get(SI);667 MemoryAccess *Clobber =668 Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);669 MemoryAccess *LiveOnEntry = Walker->getClobberingMemoryAccess(SI);670 671 EXPECT_EQ(Clobber, StoreAccess);672 EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));673 674 // Try again (with entries in the cache already) for good measure...675 Clobber = Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc);676 LiveOnEntry = Walker->getClobberingMemoryAccess(SI);677 EXPECT_EQ(Clobber, StoreAccess);678 EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry));679}680 681// Bug: During phi optimization, the walker wouldn't cache to the proper result682// in the farthest-walked BB.683//684// Specifically, it would assume that whatever we walked to was a clobber.685// "Whatever we walked to" isn't a clobber if we hit a cache entry.686//687// ...So, we need a test case that looks like:688// A689// / \690// B |691// \ /692// C693//694// Where, when we try to optimize a thing in 'C', a blocker is found in 'B'.695// The walk must determine that the blocker exists by using cache entries *while696// walking* 'B'.697TEST_F(MemorySSATest, PartialWalkerCacheWithPhis) {698 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),699 GlobalValue::ExternalLinkage, "F", &M);700 B.SetInsertPoint(BasicBlock::Create(C, "A", F));701 Type *Int8 = Type::getInt8Ty(C);702 Constant *One = ConstantInt::get(Int8, 1);703 Constant *Zero = ConstantInt::get(Int8, 0);704 Value *AllocA = B.CreateAlloca(Int8, One, "a");705 Value *AllocB = B.CreateAlloca(Int8, One, "b");706 BasicBlock *IfThen = BasicBlock::Create(C, "B", F);707 BasicBlock *IfEnd = BasicBlock::Create(C, "C", F);708 709 B.CreateCondBr(PoisonValue::get(Type::getInt1Ty(C)), IfThen, IfEnd);710 711 B.SetInsertPoint(IfThen);712 Instruction *FirstStore = B.CreateStore(Zero, AllocA);713 B.CreateStore(Zero, AllocB);714 Instruction *ALoad0 = B.CreateLoad(Int8, AllocA, "");715 Instruction *BStore = B.CreateStore(Zero, AllocB);716 // Due to use optimization/etc. we make a store to A, which is removed after717 // we build MSSA. This helps keep the test case simple-ish.718 Instruction *KillStore = B.CreateStore(Zero, AllocA);719 Instruction *ALoad = B.CreateLoad(Int8, AllocA, "");720 B.CreateBr(IfEnd);721 722 B.SetInsertPoint(IfEnd);723 Instruction *BelowPhi = B.CreateStore(Zero, AllocA);724 725 setupAnalyses();726 MemorySSA &MSSA = *Analyses->MSSA;727 MemorySSAWalker *Walker = Analyses->Walker;728 MemorySSAUpdater Updater(&MSSA);729 730 // Kill `KillStore`; it exists solely so that the load after it won't be731 // optimized to FirstStore.732 Updater.removeMemoryAccess(MSSA.getMemoryAccess(KillStore));733 KillStore->eraseFromParent();734 auto *ALoadMA = cast<MemoryUse>(MSSA.getMemoryAccess(ALoad));735 EXPECT_EQ(ALoadMA->getDefiningAccess(), MSSA.getMemoryAccess(BStore));736 737 // Populate the cache for the store to AllocB directly after FirstStore. It738 // should point to something in block B (so something in D can't be optimized739 // to it).740 MemoryAccess *Load0Clobber = Walker->getClobberingMemoryAccess(ALoad0);741 EXPECT_EQ(MSSA.getMemoryAccess(FirstStore), Load0Clobber);742 743 // If the bug exists, this will introduce a bad cache entry for %a on BStore.744 // It will point to the store to %b after FirstStore. This only happens during745 // phi optimization.746 MemoryAccess *BottomClobber = Walker->getClobberingMemoryAccess(BelowPhi);747 MemoryAccess *Phi = MSSA.getMemoryAccess(IfEnd);748 EXPECT_EQ(BottomClobber, Phi);749 750 // This query will first check the cache for {%a, BStore}. It should point to751 // FirstStore, not to the store after FirstStore.752 MemoryAccess *UseClobber = Walker->getClobberingMemoryAccess(ALoad);753 EXPECT_EQ(UseClobber, MSSA.getMemoryAccess(FirstStore));754}755 756// Test that our walker properly handles loads with the invariant group757// attribute. It's a bit hacky, since we add the invariant attribute *after*758// building MSSA. Otherwise, the use optimizer will optimize it for us, which759// isn't what we want.760// FIXME: It may be easier/cleaner to just add an 'optimize uses?' flag to MSSA.761TEST_F(MemorySSATest, WalkerInvariantLoadOpt) {762 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),763 GlobalValue::ExternalLinkage, "F", &M);764 B.SetInsertPoint(BasicBlock::Create(C, "", F));765 Type *Int8 = Type::getInt8Ty(C);766 Constant *One = ConstantInt::get(Int8, 1);767 Value *AllocA = B.CreateAlloca(Int8, One, "");768 769 Instruction *Store = B.CreateStore(One, AllocA);770 Instruction *Load = B.CreateLoad(Int8, AllocA);771 772 setupAnalyses();773 MemorySSA &MSSA = *Analyses->MSSA;774 MemorySSAWalker *Walker = Analyses->Walker;775 776 auto *LoadMA = cast<MemoryUse>(MSSA.getMemoryAccess(Load));777 auto *StoreMA = cast<MemoryDef>(MSSA.getMemoryAccess(Store));778 EXPECT_EQ(LoadMA->getDefiningAccess(), StoreMA);779 780 // ...At the time of writing, no cache should exist for LoadMA. Be a bit781 // flexible to future changes.782 Walker->invalidateInfo(LoadMA);783 Load->setMetadata(LLVMContext::MD_invariant_load, MDNode::get(C, {}));784 785 MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LoadMA);786 EXPECT_EQ(LoadClobber, MSSA.getLiveOnEntryDef());787}788 789// Test loads get reoptimized properly by the walker.790TEST_F(MemorySSATest, WalkerReopt) {791 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),792 GlobalValue::ExternalLinkage, "F", &M);793 B.SetInsertPoint(BasicBlock::Create(C, "", F));794 Type *Int8 = Type::getInt8Ty(C);795 Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");796 Instruction *SIA = B.CreateStore(ConstantInt::get(Int8, 0), AllocaA);797 Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");798 Instruction *SIB = B.CreateStore(ConstantInt::get(Int8, 0), AllocaB);799 Instruction *LIA = B.CreateLoad(Int8, AllocaA);800 801 setupAnalyses();802 MemorySSA &MSSA = *Analyses->MSSA;803 MemorySSAWalker *Walker = Analyses->Walker;804 MemorySSAUpdater Updater(&MSSA);805 806 MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LIA);807 MemoryUse *LoadAccess = cast<MemoryUse>(MSSA.getMemoryAccess(LIA));808 EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SIA));809 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SIA)));810 Updater.removeMemoryAccess(LoadAccess);811 812 // Create the load memory access pointing to an unoptimized place.813 MemoryUse *NewLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(814 LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End));815 // This should it cause it to be optimized816 EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber);817 EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber);818}819 820// Test out MemorySSAUpdater::moveBefore821TEST_F(MemorySSATest, MoveAboveMemoryDef) {822 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),823 GlobalValue::ExternalLinkage, "F", &M);824 B.SetInsertPoint(BasicBlock::Create(C, "", F));825 826 Type *Int8 = Type::getInt8Ty(C);827 Value *A = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");828 Value *B_ = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");829 Value *C = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");830 831 StoreInst *StoreA0 = B.CreateStore(ConstantInt::get(Int8, 0), A);832 StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 0), B_);833 LoadInst *LoadB = B.CreateLoad(Int8, B_);834 StoreInst *StoreA1 = B.CreateStore(ConstantInt::get(Int8, 4), A);835 StoreInst *StoreC = B.CreateStore(ConstantInt::get(Int8, 4), C);836 StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 4), A);837 LoadInst *LoadC = B.CreateLoad(Int8, C);838 839 setupAnalyses();840 MemorySSA &MSSA = *Analyses->MSSA;841 MemorySSAWalker &Walker = *Analyses->Walker;842 843 MemorySSAUpdater Updater(&MSSA);844 StoreC->moveBefore(StoreB->getIterator());845 Updater.moveBefore(cast<MemoryDef>(MSSA.getMemoryAccess(StoreC)),846 cast<MemoryDef>(MSSA.getMemoryAccess(StoreB)));847 848 MSSA.verifyMemorySSA();849 850 EXPECT_EQ(MSSA.getMemoryAccess(StoreB)->getDefiningAccess(),851 MSSA.getMemoryAccess(StoreC));852 EXPECT_EQ(MSSA.getMemoryAccess(StoreC)->getDefiningAccess(),853 MSSA.getMemoryAccess(StoreA0));854 EXPECT_EQ(MSSA.getMemoryAccess(StoreA2)->getDefiningAccess(),855 MSSA.getMemoryAccess(StoreA1));856 EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadB),857 MSSA.getMemoryAccess(StoreB));858 EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadC),859 MSSA.getMemoryAccess(StoreC));860 861 // exercise block numbering862 EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreC),863 MSSA.getMemoryAccess(StoreB)));864 EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1),865 MSSA.getMemoryAccess(StoreA2)));866}867 868TEST_F(MemorySSATest, Irreducible) {869 // Create the equivalent of870 // x = something871 // if (...)872 // goto second_loop_entry873 // while (...) {874 // second_loop_entry:875 // }876 // use(x)877 878 IRBuilder<> B(C);879 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),880 GlobalValue::ExternalLinkage, "F", &M);881 882 // Make blocks883 BasicBlock *IfBB = BasicBlock::Create(C, "if", F);884 BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F);885 BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F);886 BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F);887 B.SetInsertPoint(IfBB);888 B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB);889 B.SetInsertPoint(LoopStartBB);890 B.CreateBr(LoopMainBB);891 B.SetInsertPoint(LoopMainBB);892 B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB);893 B.SetInsertPoint(AfterLoopBB);894 Argument *FirstArg = &*F->arg_begin();895 setupAnalyses();896 MemorySSA &MSSA = *Analyses->MSSA;897 MemorySSAUpdater Updater(&MSSA);898 // Create the load memory acccess899 LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), FirstArg);900 MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(901 LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning));902 Updater.insertUse(LoadAccess);903 MSSA.verifyMemorySSA();904}905 906TEST_F(MemorySSATest, MoveToBeforeLiveOnEntryInvalidatesCache) {907 // Create:908 // %1 = alloca i8909 // ; 1 = MemoryDef(liveOnEntry)910 // store i8 0, i8* %1911 // ; 2 = MemoryDef(1)912 // store i8 0, i8* %1913 //914 // ...And be sure that MSSA's caching doesn't give us `1` for the clobber of915 // `2` after `1` is removed.916 IRBuilder<> B(C);917 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),918 GlobalValue::ExternalLinkage, "F", &M);919 920 BasicBlock *Entry = BasicBlock::Create(C, "if", F);921 B.SetInsertPoint(Entry);922 923 Value *A = B.CreateAlloca(B.getInt8Ty());924 StoreInst *StoreA = B.CreateStore(B.getInt8(0), A);925 StoreInst *StoreB = B.CreateStore(B.getInt8(0), A);926 927 setupAnalyses();928 929 MemorySSA &MSSA = *Analyses->MSSA;930 931 auto *DefA = cast<MemoryDef>(MSSA.getMemoryAccess(StoreA));932 auto *DefB = cast<MemoryDef>(MSSA.getMemoryAccess(StoreB));933 934 MemoryAccess *BClobber = MSSA.getWalker()->getClobberingMemoryAccess(DefB);935 ASSERT_EQ(DefA, BClobber);936 937 MemorySSAUpdater(&MSSA).removeMemoryAccess(DefA);938 StoreA->eraseFromParent();939 940 EXPECT_EQ(DefB->getDefiningAccess(), MSSA.getLiveOnEntryDef());941 942 EXPECT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(DefB),943 MSSA.getLiveOnEntryDef())944 << "(DefA = " << DefA << ")";945}946 947TEST_F(MemorySSATest, RemovingDefInvalidatesCache) {948 // Create:949 // %x = alloca i8950 // %y = alloca i8951 // ; 1 = MemoryDef(liveOnEntry)952 // store i8 0, i8* %x953 // ; 2 = MemoryDef(1)954 // store i8 0, i8* %y955 // ; 3 = MemoryDef(2)956 // store i8 0, i8* %x957 //958 // And be sure that MSSA's caching handles the removal of def `1`959 // appropriately.960 IRBuilder<> B(C);961 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),962 GlobalValue::ExternalLinkage, "F", &M);963 964 BasicBlock *Entry = BasicBlock::Create(C, "if", F);965 B.SetInsertPoint(Entry);966 967 Value *X = B.CreateAlloca(B.getInt8Ty());968 Value *Y = B.CreateAlloca(B.getInt8Ty());969 StoreInst *StoreX1 = B.CreateStore(B.getInt8(0), X);970 StoreInst *StoreY = B.CreateStore(B.getInt8(0), Y);971 StoreInst *StoreX2 = B.CreateStore(B.getInt8(0), X);972 973 setupAnalyses();974 975 MemorySSA &MSSA = *Analyses->MSSA;976 977 auto *DefX1 = cast<MemoryDef>(MSSA.getMemoryAccess(StoreX1));978 auto *DefY = cast<MemoryDef>(MSSA.getMemoryAccess(StoreY));979 auto *DefX2 = cast<MemoryDef>(MSSA.getMemoryAccess(StoreX2));980 981 EXPECT_EQ(DefX2->getDefiningAccess(), DefY);982 MemoryAccess *X2Clobber = MSSA.getWalker()->getClobberingMemoryAccess(DefX2);983 ASSERT_EQ(DefX1, X2Clobber);984 985 MemorySSAUpdater(&MSSA).removeMemoryAccess(DefX1);986 StoreX1->eraseFromParent();987 988 EXPECT_EQ(DefX2->getDefiningAccess(), DefY);989 EXPECT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(DefX2),990 MSSA.getLiveOnEntryDef())991 << "(DefX1 = " << DefX1 << ")";992}993 994// Test Must alias for optimized defs.995TEST_F(MemorySSATest, TestStoreMustAlias) {996 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),997 GlobalValue::ExternalLinkage, "F", &M);998 B.SetInsertPoint(BasicBlock::Create(C, "", F));999 Type *Int8 = Type::getInt8Ty(C);1000 Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");1001 Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");1002 StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaA);1003 StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaB);1004 StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaA);1005 StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaB);1006 StoreInst *SA3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaA);1007 StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaB);1008 1009 setupAnalyses();1010 MemorySSA &MSSA = *Analyses->MSSA;1011 MemorySSAWalker *Walker = Analyses->Walker;1012 1013 unsigned I = 0;1014 for (StoreInst *V : {SA1, SB1, SA2, SB2, SA3, SB3}) {1015 MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));1016 EXPECT_EQ(MemDef->isOptimized(), false)1017 << "Store " << I << " is optimized from the start?";1018 if (V == SA1)1019 Walker->getClobberingMemoryAccess(V);1020 else {1021 MemoryAccess *Def = MemDef->getDefiningAccess();1022 MemoryAccess *Clob = Walker->getClobberingMemoryAccess(V);1023 EXPECT_NE(Def, Clob) << "Store " << I1024 << " has Defining Access equal to Clobbering Access";1025 }1026 EXPECT_EQ(MemDef->isOptimized(), true)1027 << "Store " << I << " was not optimized";1028 // EXPECT_EQ expands such that if we increment I above, it won't get1029 // incremented except when we try to print the error message.1030 ++I;1031 }1032}1033 1034// Test May alias for optimized defs.1035TEST_F(MemorySSATest, TestStoreMayAlias) {1036 F = Function::Create(1037 FunctionType::get(B.getVoidTy(), {B.getPtrTy(), B.getPtrTy()}, false),1038 GlobalValue::ExternalLinkage, "F", &M);1039 B.SetInsertPoint(BasicBlock::Create(C, "", F));1040 Type *Int8 = Type::getInt8Ty(C);1041 auto *ArgIt = F->arg_begin();1042 Argument *PointerA = &*ArgIt;1043 Argument *PointerB = &*(++ArgIt);1044 Value *AllocaC = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C");1045 // Store into arg1, must alias because it's LOE => must1046 StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 0), PointerA);1047 // Store into arg2, may alias store to arg1 => may1048 StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), PointerB);1049 // Store into aloca, no alias with args, so must alias LOE => must1050 StoreInst *SC1 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaC);1051 // Store into arg1, may alias store to arg2 => may1052 StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 3), PointerA);1053 // Store into arg2, may alias store to arg1 => may1054 StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 4), PointerB);1055 // Store into aloca, no alias with args, so must alias SC1 => must1056 StoreInst *SC2 = B.CreateStore(ConstantInt::get(Int8, 5), AllocaC);1057 // Store into arg2, must alias store to arg2 => must1058 StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 6), PointerB);1059 std::initializer_list<StoreInst *> Sts = {SA1, SB1, SC1, SA2, SB2, SC2, SB3};1060 1061 setupAnalyses();1062 MemorySSA &MSSA = *Analyses->MSSA;1063 MemorySSAWalker *Walker = Analyses->Walker;1064 1065 unsigned I = 0;1066 for (StoreInst *V : Sts) {1067 MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));1068 EXPECT_EQ(MemDef->isOptimized(), false)1069 << "Store " << I << " is optimized from the start?";1070 ++I;1071 }1072 1073 for (StoreInst *V : Sts)1074 Walker->getClobberingMemoryAccess(V);1075 1076 I = 0;1077 for (StoreInst *V : Sts) {1078 MemoryDef *MemDef = dyn_cast_or_null<MemoryDef>(MSSA.getMemoryAccess(V));1079 EXPECT_EQ(MemDef->isOptimized(), true)1080 << "Store " << I << " was not optimized";1081 // EXPECT_EQ expands such that if we increment I above, it won't get1082 // incremented except when we try to print the error message.1083 ++I;1084 }1085}1086 1087TEST_F(MemorySSATest, LifetimeMarkersAreClobbers) {1088 // Example code:1089 // define void @a() {1090 // %foo = alloca i321091 // %bar = getelementptr i8, ptr %foo, i64 11092 // %baz = getelementptr i8, ptr %foo, i64 21093 // store i8 0, ptr %foo1094 // store i8 0, ptr %bar1095 // call void @llvm.lifetime.end.p0(ptr %foo)1096 // call void @llvm.lifetime.start.p0(ptr %foo)1097 // store i8 0, ptr %foo1098 // store i8 0, ptr %bar1099 // call void @llvm.memset.p0i8(ptr %baz, i8 0, i64 1)1100 // ret void1101 // }1102 //1103 // Patterns like this are possible after inlining; the stores to %foo and %bar1104 // should both be clobbered by the lifetime.start call if they're dominated by1105 // it.1106 1107 IRBuilder<> B(C);1108 F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false),1109 GlobalValue::ExternalLinkage, "F", &M);1110 1111 // Make blocks1112 BasicBlock *Entry = BasicBlock::Create(C, "entry", F);1113 1114 B.SetInsertPoint(Entry);1115 Value *Foo = B.CreateAlloca(B.getInt32Ty());1116 1117 Value *Bar = B.CreatePtrAdd(Foo, B.getInt64(1), "bar");1118 Value *Baz = B.CreatePtrAdd(Foo, B.getInt64(2), "baz");1119 1120 B.CreateStore(B.getInt8(0), Foo);1121 B.CreateStore(B.getInt8(0), Bar);1122 1123 B.CreateLifetimeEnd(Foo);1124 Instruction *LifetimeStart = B.CreateLifetimeStart(Foo);1125 1126 Instruction *FooStore = B.CreateStore(B.getInt8(0), Foo);1127 Instruction *BarStore = B.CreateStore(B.getInt8(0), Bar);1128 Instruction *BazMemSet = B.CreateMemSet(Baz, B.getInt8(0), 1, Align(1));1129 1130 setupAnalyses();1131 MemorySSA &MSSA = *Analyses->MSSA;1132 1133 MemoryAccess *LifetimeStartAccess = MSSA.getMemoryAccess(LifetimeStart);1134 ASSERT_NE(LifetimeStartAccess, nullptr);1135 1136 MemoryAccess *FooAccess = MSSA.getMemoryAccess(FooStore);1137 ASSERT_NE(FooAccess, nullptr);1138 1139 MemoryAccess *BarAccess = MSSA.getMemoryAccess(BarStore);1140 ASSERT_NE(BarAccess, nullptr);1141 1142 MemoryAccess *BazAccess = MSSA.getMemoryAccess(BazMemSet);1143 ASSERT_NE(BazAccess, nullptr);1144 1145 MemoryAccess *FooClobber =1146 MSSA.getWalker()->getClobberingMemoryAccess(FooAccess);1147 EXPECT_EQ(FooClobber, LifetimeStartAccess);1148 1149 MemoryAccess *BarClobber =1150 MSSA.getWalker()->getClobberingMemoryAccess(BarAccess);1151 EXPECT_EQ(BarClobber, LifetimeStartAccess);1152 1153 MemoryAccess *BazClobber =1154 MSSA.getWalker()->getClobberingMemoryAccess(BazAccess);1155 EXPECT_EQ(BazClobber, LifetimeStartAccess);1156 1157 MemoryAccess *LifetimeStartClobber =1158 MSSA.getWalker()->getClobberingMemoryAccess(1159 LifetimeStartAccess, MemoryLocation::getAfter(Foo));1160 EXPECT_EQ(LifetimeStartClobber, LifetimeStartAccess);1161}1162 1163TEST_F(MemorySSATest, DefOptimizationsAreInvalidatedOnMoving) {1164 IRBuilder<> B(C);1165 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getInt1Ty()}, false),1166 GlobalValue::ExternalLinkage, "F", &M);1167 1168 // Make a CFG like1169 // entry1170 // / \1171 // a b1172 // \ /1173 // c1174 //1175 // Put a def in A and a def in B, move the def from A -> B, observe as the1176 // optimization is invalidated.1177 BasicBlock *Entry = BasicBlock::Create(C, "entry", F);1178 BasicBlock *BlockA = BasicBlock::Create(C, "a", F);1179 BasicBlock *BlockB = BasicBlock::Create(C, "b", F);1180 BasicBlock *BlockC = BasicBlock::Create(C, "c", F);1181 1182 B.SetInsertPoint(Entry);1183 Type *Int8 = Type::getInt8Ty(C);1184 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "alloc");1185 StoreInst *StoreEntry = B.CreateStore(B.getInt8(0), Alloca);1186 B.CreateCondBr(B.getTrue(), BlockA, BlockB);1187 1188 B.SetInsertPoint(BlockA);1189 StoreInst *StoreA = B.CreateStore(B.getInt8(1), Alloca);1190 B.CreateBr(BlockC);1191 1192 B.SetInsertPoint(BlockB);1193 StoreInst *StoreB = B.CreateStore(B.getInt8(2), Alloca);1194 B.CreateBr(BlockC);1195 1196 B.SetInsertPoint(BlockC);1197 B.CreateUnreachable();1198 1199 setupAnalyses();1200 MemorySSA &MSSA = *Analyses->MSSA;1201 1202 auto *AccessEntry = cast<MemoryDef>(MSSA.getMemoryAccess(StoreEntry));1203 auto *StoreAEntry = cast<MemoryDef>(MSSA.getMemoryAccess(StoreA));1204 auto *StoreBEntry = cast<MemoryDef>(MSSA.getMemoryAccess(StoreB));1205 1206 ASSERT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(StoreAEntry),1207 AccessEntry);1208 ASSERT_TRUE(StoreAEntry->isOptimized());1209 1210 ASSERT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(StoreBEntry),1211 AccessEntry);1212 ASSERT_TRUE(StoreBEntry->isOptimized());1213 1214 // Note that if we did InsertionPlace::Beginning, we don't go out of our way1215 // to invalidate the cache for StoreBEntry. If the user wants to actually do1216 // moves like these, it's up to them to ensure that nearby cache entries are1217 // correctly invalidated (which, in general, requires walking all instructions1218 // that the moved instruction dominates. So we probably shouldn't be doing1219 // moves like this in general. Still, works as a test-case. ;) )1220 MemorySSAUpdater(&MSSA).moveToPlace(StoreAEntry, BlockB,1221 MemorySSA::InsertionPlace::End);1222 ASSERT_FALSE(StoreAEntry->isOptimized());1223 ASSERT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(StoreAEntry),1224 StoreBEntry);1225}1226 1227TEST_F(MemorySSATest, TestOptimizedDefsAreProperUses) {1228 F = Function::Create(1229 FunctionType::get(B.getVoidTy(), {B.getPtrTy(), B.getPtrTy()}, false),1230 GlobalValue::ExternalLinkage, "F", &M);1231 B.SetInsertPoint(BasicBlock::Create(C, "", F));1232 Type *Int8 = Type::getInt8Ty(C);1233 Value *AllocA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");1234 Value *AllocB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B");1235 1236 StoreInst *StoreA = B.CreateStore(ConstantInt::get(Int8, 0), AllocA);1237 StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 1), AllocB);1238 StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocA);1239 1240 setupAnalyses();1241 MemorySSA &MSSA = *Analyses->MSSA;1242 MemorySSAWalker *Walker = Analyses->Walker;1243 1244 // If these don't hold, there's no chance of the test result being useful.1245 ASSERT_EQ(Walker->getClobberingMemoryAccess(StoreA),1246 MSSA.getLiveOnEntryDef());1247 ASSERT_EQ(Walker->getClobberingMemoryAccess(StoreB),1248 MSSA.getLiveOnEntryDef());1249 auto *StoreAAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreA));1250 auto *StoreA2Access = cast<MemoryDef>(MSSA.getMemoryAccess(StoreA2));1251 ASSERT_EQ(Walker->getClobberingMemoryAccess(StoreA2), StoreAAccess);1252 ASSERT_EQ(StoreA2Access->getOptimized(), StoreAAccess);1253 1254 auto *StoreBAccess = cast<MemoryDef>(MSSA.getMemoryAccess(StoreB));1255 ASSERT_LT(StoreAAccess->getID(), StoreBAccess->getID());1256 ASSERT_LT(StoreBAccess->getID(), StoreA2Access->getID());1257 1258 auto SortVecByID = [](std::vector<const MemoryDef *> &Defs) {1259 llvm::sort(Defs, [](const MemoryDef *LHS, const MemoryDef *RHS) {1260 return LHS->getID() < RHS->getID();1261 });1262 };1263 1264 auto SortedUserList = [&](const MemoryDef *MD) {1265 std::vector<const MemoryDef *> Result;1266 transform(MD->users(), std::back_inserter(Result),1267 [](const User *U) { return cast<MemoryDef>(U); });1268 SortVecByID(Result);1269 return Result;1270 };1271 1272 // Use std::vectors, since they have nice pretty-printing if the test fails.1273 // Parens are necessary because EXPECT_EQ is a macro, and we have commas in1274 // our init lists...1275 EXPECT_EQ(SortedUserList(StoreAAccess),1276 (std::vector<const MemoryDef *>{StoreBAccess, StoreA2Access}));1277 1278 EXPECT_EQ(SortedUserList(StoreBAccess),1279 std::vector<const MemoryDef *>{StoreA2Access});1280 1281 // StoreAAccess should be present twice, since it uses liveOnEntry for both1282 // its defining and optimized accesses. This is a bit awkward, and is not1283 // relied upon anywhere at the moment. If this is painful, we can fix it.1284 EXPECT_EQ(SortedUserList(cast<MemoryDef>(MSSA.getLiveOnEntryDef())),1285 (std::vector<const MemoryDef *>{StoreAAccess, StoreAAccess,1286 StoreBAccess}));1287}1288 1289// entry1290// |1291// header1292// / \1293// body |1294// \ /1295// exit1296// header:1297// ; 1 = MemoryDef(liveOnEntry)1298// body:1299// ; 2 = MemoryDef(1)1300// exit:1301// ; 3 = MemoryPhi({body, 2}, {header, 1})1302// ; 4 = MemoryDef(3); optimized to 3, cannot optimize thorugh phi.1303// Insert edge: entry -> exit, check mssa Update is correct.1304TEST_F(MemorySSATest, TestAddedEdgeToBlockWithPhiNotOpt) {1305 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),1306 GlobalValue::ExternalLinkage, "F", &M);1307 Argument *PointerArg = &*F->arg_begin();1308 BasicBlock *Entry(BasicBlock::Create(C, "entry", F));1309 BasicBlock *Header(BasicBlock::Create(C, "header", F));1310 BasicBlock *Body(BasicBlock::Create(C, "body", F));1311 BasicBlock *Exit(BasicBlock::Create(C, "exit", F));1312 B.SetInsertPoint(Entry);1313 BranchInst::Create(Header, Entry);1314 B.SetInsertPoint(Header);1315 B.CreateStore(B.getInt8(16), PointerArg);1316 B.CreateCondBr(B.getTrue(), Exit, Body);1317 B.SetInsertPoint(Body);1318 B.CreateStore(B.getInt8(16), PointerArg);1319 BranchInst::Create(Exit, Body);1320 B.SetInsertPoint(Exit);1321 StoreInst *S1 = B.CreateStore(B.getInt8(16), PointerArg);1322 1323 setupAnalyses();1324 MemorySSA &MSSA = *Analyses->MSSA;1325 MemorySSAWalker *Walker = Analyses->Walker;1326 std::unique_ptr<MemorySSAUpdater> MSSAU =1327 std::make_unique<MemorySSAUpdater>(&MSSA);1328 1329 MemoryPhi *Phi = MSSA.getMemoryAccess(Exit);1330 EXPECT_EQ(Phi, Walker->getClobberingMemoryAccess(S1));1331 1332 // Alter CFG, add edge: entry -> exit1333 Entry->getTerminator()->eraseFromParent();1334 B.SetInsertPoint(Entry);1335 B.CreateCondBr(B.getTrue(), Header, Exit);1336 SmallVector<CFGUpdate, 1> Updates;1337 Updates.push_back({cfg::UpdateKind::Insert, Entry, Exit});1338 Analyses->DT.applyUpdates(Updates);1339 MSSAU->applyInsertUpdates(Updates, Analyses->DT);1340 EXPECT_EQ(Phi, Walker->getClobberingMemoryAccess(S1));1341}1342 1343// entry1344// |1345// header1346// / \1347// body |1348// \ /1349// exit1350// header:1351// ; 1 = MemoryDef(liveOnEntry)1352// body:1353// ; 2 = MemoryDef(1)1354// exit:1355// ; 3 = MemoryPhi({body, 2}, {header, 1})1356// ; 4 = MemoryDef(3); optimize this to 1 now, added edge should invalidate1357// the optimized access.1358// Insert edge: entry -> exit, check mssa Update is correct.1359TEST_F(MemorySSATest, TestAddedEdgeToBlockWithPhiOpt) {1360 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),1361 GlobalValue::ExternalLinkage, "F", &M);1362 Argument *PointerArg = &*F->arg_begin();1363 Type *Int8 = Type::getInt8Ty(C);1364 BasicBlock *Entry(BasicBlock::Create(C, "entry", F));1365 BasicBlock *Header(BasicBlock::Create(C, "header", F));1366 BasicBlock *Body(BasicBlock::Create(C, "body", F));1367 BasicBlock *Exit(BasicBlock::Create(C, "exit", F));1368 1369 B.SetInsertPoint(Entry);1370 Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");1371 BranchInst::Create(Header, Entry);1372 1373 B.SetInsertPoint(Header);1374 StoreInst *S1 = B.CreateStore(B.getInt8(16), PointerArg);1375 B.CreateCondBr(B.getTrue(), Exit, Body);1376 1377 B.SetInsertPoint(Body);1378 B.CreateStore(ConstantInt::get(Int8, 0), Alloca);1379 BranchInst::Create(Exit, Body);1380 1381 B.SetInsertPoint(Exit);1382 StoreInst *S2 = B.CreateStore(B.getInt8(16), PointerArg);1383 1384 setupAnalyses();1385 MemorySSA &MSSA = *Analyses->MSSA;1386 MemorySSAWalker *Walker = Analyses->Walker;1387 std::unique_ptr<MemorySSAUpdater> MSSAU =1388 std::make_unique<MemorySSAUpdater>(&MSSA);1389 1390 MemoryDef *DefS1 = cast<MemoryDef>(MSSA.getMemoryAccess(S1));1391 EXPECT_EQ(DefS1, Walker->getClobberingMemoryAccess(S2));1392 1393 // Alter CFG, add edge: entry -> exit1394 Entry->getTerminator()->eraseFromParent();1395 B.SetInsertPoint(Entry);1396 B.CreateCondBr(B.getTrue(), Header, Exit);1397 SmallVector<CFGUpdate, 1> Updates;1398 Updates.push_back({cfg::UpdateKind::Insert, Entry, Exit});1399 Analyses->DT.applyUpdates(Updates);1400 MSSAU->applyInsertUpdates(Updates, Analyses->DT);1401 1402 MemoryPhi *Phi = MSSA.getMemoryAccess(Exit);1403 EXPECT_EQ(Phi, Walker->getClobberingMemoryAccess(S2));1404}1405 1406// entry1407// / |1408// a |1409// / \ |1410// b c f1411// \ / |1412// d |1413// \ /1414// e1415// f:1416// ; 1 = MemoryDef(liveOnEntry)1417// e:1418// ; 2 = MemoryPhi({d, liveOnEntry}, {f, 1})1419//1420// Insert edge: f -> c, check update is correct.1421// After update:1422// f:1423// ; 1 = MemoryDef(liveOnEntry)1424// c:1425// ; 3 = MemoryPhi({a, liveOnEntry}, {f, 1})1426// d:1427// ; 4 = MemoryPhi({b, liveOnEntry}, {c, 3})1428// e:1429// ; 2 = MemoryPhi({d, 4}, {f, 1})1430TEST_F(MemorySSATest, TestAddedEdgeToBlockWithNoPhiAddNewPhis) {1431 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),1432 GlobalValue::ExternalLinkage, "F", &M);1433 Argument *PointerArg = &*F->arg_begin();1434 BasicBlock *Entry(BasicBlock::Create(C, "entry", F));1435 BasicBlock *ABlock(BasicBlock::Create(C, "a", F));1436 BasicBlock *BBlock(BasicBlock::Create(C, "b", F));1437 BasicBlock *CBlock(BasicBlock::Create(C, "c", F));1438 BasicBlock *DBlock(BasicBlock::Create(C, "d", F));1439 BasicBlock *EBlock(BasicBlock::Create(C, "e", F));1440 BasicBlock *FBlock(BasicBlock::Create(C, "f", F));1441 1442 B.SetInsertPoint(Entry);1443 B.CreateCondBr(B.getTrue(), ABlock, FBlock);1444 B.SetInsertPoint(ABlock);1445 B.CreateCondBr(B.getTrue(), BBlock, CBlock);1446 B.SetInsertPoint(BBlock);1447 BranchInst::Create(DBlock, BBlock);1448 B.SetInsertPoint(CBlock);1449 BranchInst::Create(DBlock, CBlock);1450 B.SetInsertPoint(DBlock);1451 BranchInst::Create(EBlock, DBlock);1452 B.SetInsertPoint(FBlock);1453 B.CreateStore(B.getInt8(16), PointerArg);1454 BranchInst::Create(EBlock, FBlock);1455 1456 setupAnalyses();1457 MemorySSA &MSSA = *Analyses->MSSA;1458 std::unique_ptr<MemorySSAUpdater> MSSAU =1459 std::make_unique<MemorySSAUpdater>(&MSSA);1460 1461 // Alter CFG, add edge: f -> c1462 FBlock->getTerminator()->eraseFromParent();1463 B.SetInsertPoint(FBlock);1464 B.CreateCondBr(B.getTrue(), CBlock, EBlock);1465 SmallVector<CFGUpdate, 1> Updates;1466 Updates.push_back({cfg::UpdateKind::Insert, FBlock, CBlock});1467 Analyses->DT.applyUpdates(Updates);1468 MSSAU->applyInsertUpdates(Updates, Analyses->DT);1469 1470 MemoryPhi *MPC = MSSA.getMemoryAccess(CBlock);1471 EXPECT_NE(MPC, nullptr);1472 MemoryPhi *MPD = MSSA.getMemoryAccess(DBlock);1473 EXPECT_NE(MPD, nullptr);1474 MemoryPhi *MPE = MSSA.getMemoryAccess(EBlock);1475 EXPECT_EQ(MPD, MPE->getIncomingValueForBlock(DBlock));1476}1477 1478TEST_F(MemorySSATest, TestCallClobber) {1479 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),1480 GlobalValue::ExternalLinkage, "F", &M);1481 1482 Value *Pointer1 = &*F->arg_begin();1483 BasicBlock *Entry(BasicBlock::Create(C, "", F));1484 B.SetInsertPoint(Entry);1485 Value *Pointer2 = B.CreatePtrAdd(Pointer1, B.getInt64(1));1486 Instruction *StorePointer1 = B.CreateStore(B.getInt8(0), Pointer1);1487 Instruction *StorePointer2 = B.CreateStore(B.getInt8(0), Pointer2);1488 Instruction *MemSet = B.CreateMemSet(Pointer2, B.getInt8(0), 1, Align(1));1489 1490 setupAnalyses();1491 MemorySSA &MSSA = *Analyses->MSSA;1492 MemorySSAWalker *Walker = Analyses->Walker;1493 1494 MemoryUseOrDef *Store1Access = MSSA.getMemoryAccess(StorePointer1);1495 MemoryUseOrDef *Store2Access = MSSA.getMemoryAccess(StorePointer2);1496 MemoryUseOrDef *MemSetAccess = MSSA.getMemoryAccess(MemSet);1497 1498 MemoryAccess *Pointer1Clobber = Walker->getClobberingMemoryAccess(1499 MemSetAccess, MemoryLocation(Pointer1, LocationSize::precise(1)));1500 EXPECT_EQ(Pointer1Clobber, Store1Access);1501 1502 MemoryAccess *Pointer2Clobber = Walker->getClobberingMemoryAccess(1503 MemSetAccess, MemoryLocation(Pointer2, LocationSize::precise(1)));1504 EXPECT_EQ(Pointer2Clobber, MemSetAccess);1505 1506 MemoryAccess *MemSetClobber = Walker->getClobberingMemoryAccess(MemSetAccess);1507 EXPECT_EQ(MemSetClobber, Store2Access);1508}1509 1510TEST_F(MemorySSATest, TestLoadClobber) {1511 F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getPtrTy()}, false),1512 GlobalValue::ExternalLinkage, "F", &M);1513 1514 Value *Pointer1 = &*F->arg_begin();1515 BasicBlock *Entry(BasicBlock::Create(C, "", F));1516 B.SetInsertPoint(Entry);1517 Value *Pointer2 = B.CreatePtrAdd(Pointer1, B.getInt64(1));1518 Instruction *LoadPointer1 =1519 B.CreateLoad(B.getInt8Ty(), Pointer1, /* Volatile */ true);1520 Instruction *LoadPointer2 =1521 B.CreateLoad(B.getInt8Ty(), Pointer2, /* Volatile */ true);1522 1523 setupAnalyses();1524 MemorySSA &MSSA = *Analyses->MSSA;1525 MemorySSAWalker *Walker = Analyses->Walker;1526 1527 MemoryUseOrDef *Load1Access = MSSA.getMemoryAccess(LoadPointer1);1528 MemoryUseOrDef *Load2Access = MSSA.getMemoryAccess(LoadPointer2);1529 1530 // When providing a memory location, we should never return a load as the1531 // clobber.1532 MemoryAccess *Pointer1Clobber = Walker->getClobberingMemoryAccess(1533 Load2Access, MemoryLocation(Pointer1, LocationSize::precise(1)));1534 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Pointer1Clobber));1535 1536 MemoryAccess *Pointer2Clobber = Walker->getClobberingMemoryAccess(1537 Load2Access, MemoryLocation(Pointer2, LocationSize::precise(1)));1538 EXPECT_TRUE(MSSA.isLiveOnEntryDef(Pointer2Clobber));1539 1540 MemoryAccess *Load2Clobber = Walker->getClobberingMemoryAccess(Load2Access);1541 EXPECT_EQ(Load2Clobber, Load1Access);1542}1543 1544// We want to test if the location information are retained1545// when the IsGuaranteedLoopInvariant function handles a1546// memory access referring to a pointer defined in the entry1547// block, hence automatically guaranteed to be loop invariant.1548TEST_F(MemorySSATest, TestLoopInvariantEntryBlockPointer) {1549 SMDiagnostic E;1550 auto LocalM =1551 parseAssemblyString("define void @test(i64 %a0, i8* %a1, i1* %a2) {\n"1552 "entry:\n"1553 "%v0 = getelementptr i8, i8* %a1, i64 %a0\n"1554 "%v1 = bitcast i8* %v0 to i64*\n"1555 "%v2 = bitcast i8* %v0 to i32*\n"1556 "%v3 = load i1, i1* %a2\n"1557 "br i1 %v3, label %body, label %exit\n"1558 "body:\n"1559 "store i32 1, i32* %v2\n"1560 "br label %exit\n"1561 "exit:\n"1562 "store i64 0, i64* %v1\n"1563 "ret void\n"1564 "}",1565 E, C);1566 ASSERT_TRUE(LocalM);1567 F = LocalM->getFunction("test");1568 ASSERT_TRUE(F);1569 // Setup the analysis1570 setupAnalyses();1571 MemorySSA &MSSA = *Analyses->MSSA;1572 // Find the exit block1573 for (auto &BB : *F) {1574 if (BB.getName() == "exit") {1575 // Get the store instruction1576 auto *SI = &*BB.getFirstNonPHIIt();1577 // Get the memory access and location1578 MemoryAccess *MA = MSSA.getMemoryAccess(SI);1579 MemoryLocation ML = MemoryLocation::get(SI);1580 // Use the 'upward_defs_iterator' which internally calls1581 // IsGuaranteedLoopInvariant1582 auto ItA = upward_defs_begin({MA, ML}, MSSA.getDomTree());1583 auto ItB =1584 upward_defs_begin({ItA->first, ItA->second}, MSSA.getDomTree());1585 // Check if the location information have been retained1586 EXPECT_TRUE(ItB->second.Size.isPrecise());1587 EXPECT_TRUE(ItB->second.Size.hasValue());1588 EXPECT_TRUE(ItB->second.Size.getValue() == 8);1589 }1590 }1591}1592 1593TEST_F(MemorySSATest, TestInvariantGroup) {1594 SMDiagnostic E;1595 auto M = parseAssemblyString("declare void @f(i8*)\n"1596 "define i8 @test(i8* %p) {\n"1597 "entry:\n"1598 " store i8 42, i8* %p, !invariant.group !0\n"1599 " call void @f(i8* %p)\n"1600 " %v = load i8, i8* %p, !invariant.group !0\n"1601 " ret i8 %v\n"1602 "}\n"1603 "!0 = !{}",1604 E, C);1605 ASSERT_TRUE(M);1606 F = M->getFunction("test");1607 ASSERT_TRUE(F);1608 setupAnalyses();1609 MemorySSA &MSSA = *Analyses->MSSA;1610 MemorySSAWalker *Walker = Analyses->Walker;1611 1612 auto &BB = F->getEntryBlock();1613 auto &SI = cast<StoreInst>(*BB.begin());1614 auto &Call = cast<CallBase>(*std::next(BB.begin()));1615 auto &LI = cast<LoadInst>(*std::next(std::next(BB.begin())));1616 1617 {1618 MemoryAccess *SAccess = MSSA.getMemoryAccess(&SI);1619 MemoryAccess *LAccess = MSSA.getMemoryAccess(&LI);1620 MemoryAccess *SClobber = Walker->getClobberingMemoryAccess(SAccess);1621 EXPECT_TRUE(MSSA.isLiveOnEntryDef(SClobber));1622 MemoryAccess *LClobber = Walker->getClobberingMemoryAccess(LAccess);1623 EXPECT_EQ(SAccess, LClobber);1624 }1625 1626 // remove store and verify that the memory accesses still make sense1627 MemorySSAUpdater Updater(&MSSA);1628 Updater.removeMemoryAccess(&SI);1629 SI.eraseFromParent();1630 1631 {1632 MemoryAccess *CallAccess = MSSA.getMemoryAccess(&Call);1633 MemoryAccess *LAccess = MSSA.getMemoryAccess(&LI);1634 MemoryAccess *LClobber = Walker->getClobberingMemoryAccess(LAccess);1635 EXPECT_EQ(CallAccess, LClobber);1636 }1637}1638 1639static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) {1640 for (BasicBlock &BB : F)1641 if (BB.getName() == Name)1642 return &BB;1643 llvm_unreachable("Expected to find basic block!");1644}1645 1646static Instruction *getInstructionByName(Function &F, StringRef Name) {1647 for (BasicBlock &BB : F)1648 for (Instruction &I : BB)1649 if (I.getName() == Name)1650 return &I;1651 llvm_unreachable("Expected to find instruction!");1652}1653 1654TEST_F(MemorySSATest, TestVisitedBlocks) {1655 SMDiagnostic E;1656 auto M = parseAssemblyString(1657 "define void @test(i64* noalias %P, i64 %N) {\n"1658 "preheader.n:\n"1659 " br label %header.n\n"1660 "header.n:\n"1661 " %n = phi i64 [ 0, %preheader.n ], [ %inc.n, %latch.n ]\n"1662 " %guard.cond.i = icmp slt i64 0, %N\n"1663 " br i1 %guard.cond.i, label %header.i.check, label %other.i\n"1664 "header.i.check:\n"1665 " br label %preheader.i\n"1666 "preheader.i:\n"1667 " br label %header.i\n"1668 "header.i:\n"1669 " %i = phi i64 [ 0, %preheader.i ], [ %inc.i, %header.i ]\n"1670 " %v1 = load i64, i64* %P, align 8\n"1671 " %v2 = load i64, i64* %P, align 8\n"1672 " %inc.i = add nsw i64 %i, 1\n"1673 " %cmp.i = icmp slt i64 %inc.i, %N\n"1674 " br i1 %cmp.i, label %header.i, label %exit.i\n"1675 "exit.i:\n"1676 " br label %commonexit\n"1677 "other.i:\n"1678 " br label %commonexit\n"1679 "commonexit:\n"1680 " br label %latch.n\n"1681 "latch.n:\n"1682 " %inc.n = add nsw i64 %n, 1\n"1683 " %cmp.n = icmp slt i64 %inc.n, %N\n"1684 " br i1 %cmp.n, label %header.n, label %exit.n\n"1685 "exit.n:\n"1686 " ret void\n"1687 "}\n",1688 E, C);1689 ASSERT_TRUE(M);1690 F = M->getFunction("test");1691 ASSERT_TRUE(F);1692 setupAnalyses();1693 MemorySSA &MSSA = *Analyses->MSSA;1694 MemorySSAUpdater Updater(&MSSA);1695 1696 {1697 // Move %v1 before the terminator of %header.i.check1698 BasicBlock *BB = getBasicBlockByName(*F, "header.i.check");1699 Instruction *LI = getInstructionByName(*F, "v1");1700 LI->moveBefore(BB->getTerminator()->getIterator());1701 if (MemoryUseOrDef *MUD = MSSA.getMemoryAccess(LI))1702 Updater.moveToPlace(MUD, BB, MemorySSA::BeforeTerminator);1703 1704 // Change the termiantor of %header.i.check to `br label true, label1705 // %preheader.i, label %other.i`1706 BB->getTerminator()->eraseFromParent();1707 ConstantInt *BoolTrue = ConstantInt::getTrue(F->getContext());1708 BranchInst::Create(getBasicBlockByName(*F, "preheader.i"),1709 getBasicBlockByName(*F, "other.i"), BoolTrue, BB);1710 SmallVector<DominatorTree::UpdateType, 4> DTUpdates;1711 DTUpdates.push_back(DominatorTree::UpdateType(1712 DominatorTree::Insert, BB, getBasicBlockByName(*F, "other.i")));1713 Updater.applyUpdates(DTUpdates, Analyses->DT, true);1714 }1715 1716 // After the first moveToPlace(), %other.i is in VisitedBlocks, even after1717 // there is a new edge to %other.i, which makes the second moveToPlace()1718 // traverse incorrectly.1719 {1720 // Move %v2 before the terminator of %preheader.i1721 BasicBlock *BB = getBasicBlockByName(*F, "preheader.i");1722 Instruction *LI = getInstructionByName(*F, "v2");1723 LI->moveBefore(BB->getTerminator()->getIterator());1724 // Check that there is no assertion of "Incomplete phi during partial1725 // rename"1726 if (MemoryUseOrDef *MUD = MSSA.getMemoryAccess(LI))1727 Updater.moveToPlace(MUD, BB, MemorySSA::BeforeTerminator);1728 }1729}1730 1731TEST_F(MemorySSATest, TestNoDbgInsts) {1732 SMDiagnostic E;1733 auto M = parseAssemblyString(R"(1734 define void @test() presplitcoroutine {1735 entry:1736 %i = alloca i321737 call void @llvm.dbg.declare(metadata ptr %i, metadata !6, metadata !DIExpression()), !dbg !101738 call void @llvm.dbg.value(metadata ptr %i, metadata !6, metadata !DIExpression()), !dbg !101739 ret void1740 }1741 1742 declare void @llvm.dbg.declare(metadata, metadata, metadata) nocallback nofree nosync nounwind readnone speculatable willreturn1743 declare void @llvm.dbg.value(metadata, metadata, metadata) nocallback nofree nosync nounwind readnone speculatable willreturn1744 1745 !llvm.dbg.cu = !{!0}1746 1747 !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 15.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, retainedTypes: !2, splitDebugInlining: false, nameTableKind: None)1748 !1 = !DIFile(filename: "repro.cpp", directory: ".")1749 !2 = !{}1750 !3 = !{i32 7, !"Dwarf Version", i32 4}1751 !4 = !{i32 2, !"Debug Info Version", i32 3}1752 !5 = !{!"clang version 15.0.0"}1753 !6 = !DILocalVariable(name: "i", scope: !7, file: !1, line: 24, type: !10)1754 !7 = distinct !DILexicalBlock(scope: !8, file: !1, line: 23, column: 12)1755 !8 = distinct !DISubprogram(name: "foo", linkageName: "_Z3foov", scope: !1, file: !1, line: 23, type: !9, scopeLine: 23, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)1756 !9 = !DISubroutineType(types: !2)1757 !10 = !DILocation(line: 24, column: 7, scope: !7)1758 )",1759 E, C);1760 ASSERT_TRUE(M);1761 F = M->getFunction("test");1762 ASSERT_TRUE(F);1763 setupAnalyses();1764 MemorySSA &MSSA = *Analyses->MSSA;1765 MemorySSAUpdater Updater(&MSSA);1766 1767 BasicBlock &Entry = F->front();1768 auto I = Entry.begin();1769 Instruction *DbgDeclare = cast<Instruction>(I++);1770 Instruction *DbgValue = cast<Instruction>(I++);1771 ASSERT_EQ(MSSA.getMemoryAccess(DbgDeclare), nullptr);1772 ASSERT_EQ(MSSA.getMemoryAccess(DbgValue), nullptr);1773}1774