Index: unittests/Analysis/CMakeLists.txt =================================================================== --- unittests/Analysis/CMakeLists.txt +++ unittests/Analysis/CMakeLists.txt @@ -18,15 +18,15 @@ LazyCallGraphTest.cpp LoopInfoTest.cpp MemoryBuiltinsTest.cpp - MemorySSA.cpp + MemorySSATest.cpp OrderedBasicBlockTest.cpp - OrderedInstructions.cpp + OrderedInstructionsTest.cpp PhiValuesTest.cpp ProfileSummaryInfoTest.cpp ScalarEvolutionTest.cpp SparsePropagation.cpp TargetLibraryInfoTest.cpp TBAATest.cpp - UnrollAnalyzer.cpp + UnrollAnalyzerTest.cpp ValueTrackingTest.cpp ) Index: unittests/Analysis/MemorySSA.cpp =================================================================== --- unittests/Analysis/MemorySSA.cpp +++ unittests/Analysis/MemorySSA.cpp @@ -1,1395 +0,0 @@ -//===- MemorySSA.cpp - Unit tests for MemorySSA ---------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -#include "llvm/Analysis/MemorySSA.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/BasicAliasAnalysis.h" -#include "llvm/Analysis/MemorySSAUpdater.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/DataLayout.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "gtest/gtest.h" - -using namespace llvm; - -const static char DLString[] = "e-i64:64-f80:128-n8:16:32:64-S128"; - -/// There's a lot of common setup between these tests. This fixture helps reduce -/// that. Tests should mock up a function, store it in F, and then call -/// setupAnalyses(). -class MemorySSATest : public testing::Test { -protected: - // N.B. Many of these members depend on each other (e.g. the Module depends on - // the Context, etc.). So, order matters here (and in TestAnalyses). - LLVMContext C; - Module M; - IRBuilder<> B; - DataLayout DL; - TargetLibraryInfoImpl TLII; - TargetLibraryInfo TLI; - Function *F; - - // Things that we need to build after the function is created. - struct TestAnalyses { - DominatorTree DT; - AssumptionCache AC; - AAResults AA; - BasicAAResult BAA; - // We need to defer MSSA construction until AA is *entirely* set up, which - // requires calling addAAResult. Hence, we just use a pointer here. - std::unique_ptr MSSA; - MemorySSAWalker *Walker; - - TestAnalyses(MemorySSATest &Test) - : DT(*Test.F), AC(*Test.F), AA(Test.TLI), - BAA(Test.DL, *Test.F, Test.TLI, AC, &DT) { - AA.addAAResult(BAA); - MSSA = make_unique(*Test.F, &AA, &DT); - Walker = MSSA->getWalker(); - } - }; - - std::unique_ptr Analyses; - - void setupAnalyses() { - assert(F); - Analyses.reset(new TestAnalyses(*this)); - } - -public: - MemorySSATest() - : M("MemorySSATest", C), B(C), DL(DLString), TLI(TLII), F(nullptr) {} -}; - -TEST_F(MemorySSATest, CreateALoad) { - // We create a diamond where there is a store on one side, and then after - // building MemorySSA, create a load after the merge point, and use it to test - // updating by creating an access for the load. - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left); - Argument *PointerArg = &*F->arg_begin(); - B.CreateStore(B.getInt8(16), PointerArg); - BranchInst::Create(Merge, Left); - BranchInst::Create(Merge, Right); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - // Add the load - B.SetInsertPoint(Merge); - LoadInst *LoadInst = B.CreateLoad(PointerArg); - - // MemoryPHI should already exist. - MemoryPhi *MP = MSSA.getMemoryAccess(Merge); - EXPECT_NE(MP, nullptr); - - // Create the load memory acccess - MemoryUse *LoadAccess = cast(Updater.createMemoryAccessInBB( - LoadInst, MP, Merge, MemorySSA::Beginning)); - MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess(); - EXPECT_TRUE(isa(DefiningAccess)); - MSSA.verifyMemorySSA(); -} -TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) { - // We create a diamond, then build memoryssa with no memory accesses, and - // incrementally update it by inserting a store in the, entry, a load in the - // merge point, then a store in the branch, another load in the merge point, - // and then a store in the entry. - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left, Left->begin()); - Argument *PointerArg = &*F->arg_begin(); - B.SetInsertPoint(Left); - B.CreateBr(Merge); - B.SetInsertPoint(Right); - B.CreateBr(Merge); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - // Add the store - B.SetInsertPoint(Entry, Entry->begin()); - StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg); - MemoryAccess *EntryStoreAccess = Updater.createMemoryAccessInBB( - EntryStore, nullptr, Entry, MemorySSA::Beginning); - Updater.insertDef(cast(EntryStoreAccess)); - - // Add the load - B.SetInsertPoint(Merge, Merge->begin()); - LoadInst *FirstLoad = B.CreateLoad(PointerArg); - - // MemoryPHI should not already exist. - MemoryPhi *MP = MSSA.getMemoryAccess(Merge); - EXPECT_EQ(MP, nullptr); - - // Create the load memory access - MemoryUse *FirstLoadAccess = cast(Updater.createMemoryAccessInBB( - FirstLoad, nullptr, Merge, MemorySSA::Beginning)); - Updater.insertUse(FirstLoadAccess); - // Should just have a load using the entry access, because it should discover - // the phi is trivial - EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), EntryStoreAccess); - - // Create a store on the left - // Add the store - B.SetInsertPoint(Left, Left->begin()); - StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg); - MemoryAccess *LeftStoreAccess = Updater.createMemoryAccessInBB( - LeftStore, nullptr, Left, MemorySSA::Beginning); - Updater.insertDef(cast(LeftStoreAccess), false); - // We don't touch existing loads, so we need to create a new one to get a phi - // Add the second load - B.SetInsertPoint(Merge, Merge->begin()); - LoadInst *SecondLoad = B.CreateLoad(PointerArg); - - // MemoryPHI should not already exist. - MP = MSSA.getMemoryAccess(Merge); - EXPECT_EQ(MP, nullptr); - - // Create the load memory access - MemoryUse *SecondLoadAccess = cast(Updater.createMemoryAccessInBB( - SecondLoad, nullptr, Merge, MemorySSA::Beginning)); - Updater.insertUse(SecondLoadAccess); - // Now the load should be a phi of the entry store and the left store - MemoryPhi *MergePhi = - dyn_cast(SecondLoadAccess->getDefiningAccess()); - EXPECT_NE(MergePhi, nullptr); - EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess); - // Now create a store below the existing one in the entry - B.SetInsertPoint(Entry, --Entry->end()); - StoreInst *SecondEntryStore = B.CreateStore(B.getInt8(16), PointerArg); - MemoryAccess *SecondEntryStoreAccess = Updater.createMemoryAccessInBB( - SecondEntryStore, nullptr, Entry, MemorySSA::End); - // Insert it twice just to test renaming - Updater.insertDef(cast(SecondEntryStoreAccess), false); - EXPECT_NE(FirstLoadAccess->getDefiningAccess(), MergePhi); - Updater.insertDef(cast(SecondEntryStoreAccess), true); - EXPECT_EQ(FirstLoadAccess->getDefiningAccess(), MergePhi); - // and make sure the phi below it got updated, despite being blocks away - MergePhi = dyn_cast(SecondLoadAccess->getDefiningAccess()); - EXPECT_NE(MergePhi, nullptr); - EXPECT_EQ(MergePhi->getIncomingValue(0), SecondEntryStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(1), LeftStoreAccess); - MSSA.verifyMemorySSA(); -} - -TEST_F(MemorySSATest, CreateALoadUpdater) { - // We create a diamond, then build memoryssa with no memory accesses, and - // incrementally update it by inserting a store in one of the branches, and a - // load in the merge point - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left, Left->begin()); - Argument *PointerArg = &*F->arg_begin(); - B.SetInsertPoint(Left); - B.CreateBr(Merge); - B.SetInsertPoint(Right); - B.CreateBr(Merge); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - B.SetInsertPoint(Left, Left->begin()); - // Add the store - StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg); - MemoryAccess *StoreAccess = - Updater.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning); - Updater.insertDef(cast(StoreAccess)); - - // Add the load - B.SetInsertPoint(Merge, Merge->begin()); - LoadInst *LoadInst = B.CreateLoad(PointerArg); - - // MemoryPHI should not already exist. - MemoryPhi *MP = MSSA.getMemoryAccess(Merge); - EXPECT_EQ(MP, nullptr); - - // Create the load memory acccess - MemoryUse *LoadAccess = cast(Updater.createMemoryAccessInBB( - LoadInst, nullptr, Merge, MemorySSA::Beginning)); - Updater.insertUse(LoadAccess); - MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess(); - EXPECT_TRUE(isa(DefiningAccess)); - MSSA.verifyMemorySSA(); -} - -TEST_F(MemorySSATest, SinkLoad) { - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left, Left->begin()); - Argument *PointerArg = &*F->arg_begin(); - B.SetInsertPoint(Left); - B.CreateBr(Merge); - B.SetInsertPoint(Right); - B.CreateBr(Merge); - - // Load in left block - B.SetInsertPoint(Left, Left->begin()); - LoadInst *LoadInst1 = B.CreateLoad(PointerArg); - // Store in merge block - B.SetInsertPoint(Merge, Merge->begin()); - B.CreateStore(B.getInt8(16), PointerArg); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - - // Mimic sinking of a load: - // - clone load - // - insert in "exit" block - // - insert in mssa - // - remove from original block - - LoadInst *LoadInstClone = cast(LoadInst1->clone()); - Merge->getInstList().insert(Merge->begin(), LoadInstClone); - MemoryAccess * NewLoadAccess = - Updater.createMemoryAccessInBB(LoadInstClone, nullptr, - LoadInstClone->getParent(), - MemorySSA::Beginning); - Updater.insertUse(cast(NewLoadAccess)); - MSSA.verifyMemorySSA(); - Updater.removeMemoryAccess(MSSA.getMemoryAccess(LoadInst1)); - MSSA.verifyMemorySSA(); -} - -TEST_F(MemorySSATest, MoveAStore) { - // We create a diamond where there is a in the entry, a store on one side, and - // a load at the end. After building MemorySSA, we test updating by moving - // the store from the side block to the entry block. This destroys the old - // access. - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - Argument *PointerArg = &*F->arg_begin(); - StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left); - StoreInst *SideStore = B.CreateStore(B.getInt8(16), PointerArg); - BranchInst::Create(Merge, Left); - BranchInst::Create(Merge, Right); - B.SetInsertPoint(Merge); - B.CreateLoad(PointerArg); - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - // Move the store - SideStore->moveBefore(Entry->getTerminator()); - MemoryAccess *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore); - MemoryAccess *SideStoreAccess = MSSA.getMemoryAccess(SideStore); - MemoryAccess *NewStoreAccess = Updater.createMemoryAccessAfter( - SideStore, EntryStoreAccess, EntryStoreAccess); - EntryStoreAccess->replaceAllUsesWith(NewStoreAccess); - Updater.removeMemoryAccess(SideStoreAccess); - MSSA.verifyMemorySSA(); -} - -TEST_F(MemorySSATest, MoveAStoreUpdater) { - // We create a diamond where there is a in the entry, a store on one side, and - // a load at the end. After building MemorySSA, we test updating by moving - // the store from the side block to the entry block. This destroys the old - // access. - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - Argument *PointerArg = &*F->arg_begin(); - StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left); - auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg); - BranchInst::Create(Merge, Left); - BranchInst::Create(Merge, Right); - B.SetInsertPoint(Merge); - auto *MergeLoad = B.CreateLoad(PointerArg); - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - - // Move the store - SideStore->moveBefore(Entry->getTerminator()); - auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore); - auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore); - auto *NewStoreAccess = Updater.createMemoryAccessAfter( - SideStore, EntryStoreAccess, EntryStoreAccess); - // Before, the load will point to a phi of the EntryStore and SideStore. - auto *LoadAccess = cast(MSSA.getMemoryAccess(MergeLoad)); - EXPECT_TRUE(isa(LoadAccess->getDefiningAccess())); - MemoryPhi *MergePhi = cast(LoadAccess->getDefiningAccess()); - EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess); - Updater.removeMemoryAccess(SideStoreAccess); - Updater.insertDef(cast(NewStoreAccess)); - // After it's a phi of the new side store access. - EXPECT_EQ(MergePhi->getIncomingValue(0), NewStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(1), NewStoreAccess); - MSSA.verifyMemorySSA(); -} - -TEST_F(MemorySSATest, MoveAStoreUpdaterMove) { - // We create a diamond where there is a in the entry, a store on one side, and - // a load at the end. After building MemorySSA, we test updating by moving - // the store from the side block to the entry block. This does not destroy - // the old access. - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - Argument *PointerArg = &*F->arg_begin(); - StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left); - auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg); - BranchInst::Create(Merge, Left); - BranchInst::Create(Merge, Right); - B.SetInsertPoint(Merge); - auto *MergeLoad = B.CreateLoad(PointerArg); - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - - // Move the store - auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore); - auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore); - // Before, the load will point to a phi of the EntryStore and SideStore. - auto *LoadAccess = cast(MSSA.getMemoryAccess(MergeLoad)); - EXPECT_TRUE(isa(LoadAccess->getDefiningAccess())); - MemoryPhi *MergePhi = cast(LoadAccess->getDefiningAccess()); - EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess); - SideStore->moveBefore(*EntryStore->getParent(), ++EntryStore->getIterator()); - Updater.moveAfter(SideStoreAccess, EntryStoreAccess); - // After, it's a phi of the side store. - EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess); - - MSSA.verifyMemorySSA(); -} - -TEST_F(MemorySSATest, MoveAStoreAllAround) { - // We create a diamond where there is a in the entry, a store on one side, and - // a load at the end. After building MemorySSA, we test updating by moving - // the store from the side block to the entry block, then to the other side - // block, then to before the load. This does not destroy the old access. - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - Argument *PointerArg = &*F->arg_begin(); - StoreInst *EntryStore = B.CreateStore(B.getInt8(16), PointerArg); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left); - auto *SideStore = B.CreateStore(B.getInt8(16), PointerArg); - BranchInst::Create(Merge, Left); - BranchInst::Create(Merge, Right); - B.SetInsertPoint(Merge); - auto *MergeLoad = B.CreateLoad(PointerArg); - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - - // Move the store - auto *EntryStoreAccess = MSSA.getMemoryAccess(EntryStore); - auto *SideStoreAccess = MSSA.getMemoryAccess(SideStore); - // Before, the load will point to a phi of the EntryStore and SideStore. - auto *LoadAccess = cast(MSSA.getMemoryAccess(MergeLoad)); - EXPECT_TRUE(isa(LoadAccess->getDefiningAccess())); - MemoryPhi *MergePhi = cast(LoadAccess->getDefiningAccess()); - EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(0), SideStoreAccess); - // Move the store before the entry store - SideStore->moveBefore(*EntryStore->getParent(), EntryStore->getIterator()); - Updater.moveBefore(SideStoreAccess, EntryStoreAccess); - // After, it's a phi of the entry store. - EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); - MSSA.verifyMemorySSA(); - // Now move the store to the right branch - SideStore->moveBefore(*Right, Right->begin()); - Updater.moveToPlace(SideStoreAccess, Right, MemorySSA::Beginning); - MSSA.verifyMemorySSA(); - EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(1), SideStoreAccess); - // Now move it before the load - SideStore->moveBefore(MergeLoad); - Updater.moveBefore(SideStoreAccess, LoadAccess); - EXPECT_EQ(MergePhi->getIncomingValue(0), EntryStoreAccess); - EXPECT_EQ(MergePhi->getIncomingValue(1), EntryStoreAccess); - MSSA.verifyMemorySSA(); -} - -TEST_F(MemorySSATest, RemoveAPhi) { - // We create a diamond where there is a store on one side, and then a load - // after the merge point. This enables us to test a bunch of different - // removal cases. - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left); - Argument *PointerArg = &*F->arg_begin(); - StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg); - BranchInst::Create(Merge, Left); - BranchInst::Create(Merge, Right); - B.SetInsertPoint(Merge); - LoadInst *LoadInst = B.CreateLoad(PointerArg); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - - // Before, the load will be a use of a phi. - MemoryUse *LoadAccess = cast(MSSA.getMemoryAccess(LoadInst)); - MemoryDef *StoreAccess = cast(MSSA.getMemoryAccess(StoreInst)); - MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess(); - EXPECT_TRUE(isa(DefiningAccess)); - // Kill the store - Updater.removeMemoryAccess(StoreAccess); - MemoryPhi *MP = cast(DefiningAccess); - // Verify the phi ended up as liveonentry, liveonentry - for (auto &Op : MP->incoming_values()) - EXPECT_TRUE(MSSA.isLiveOnEntryDef(cast(Op.get()))); - // Replace the phi uses with the live on entry def - MP->replaceAllUsesWith(MSSA.getLiveOnEntryDef()); - // Verify the load is now defined by liveOnEntryDef - EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess())); - // Remove the PHI - Updater.removeMemoryAccess(MP); - MSSA.verifyMemorySSA(); -} - -TEST_F(MemorySSATest, RemoveMemoryAccess) { - // We create a diamond where there is a store on one side, and then a load - // after the merge point. This enables us to test a bunch of different - // removal cases. - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BasicBlock *Entry(BasicBlock::Create(C, "", F)); - BasicBlock *Left(BasicBlock::Create(C, "", F)); - BasicBlock *Right(BasicBlock::Create(C, "", F)); - BasicBlock *Merge(BasicBlock::Create(C, "", F)); - B.SetInsertPoint(Entry); - B.CreateCondBr(B.getTrue(), Left, Right); - B.SetInsertPoint(Left); - Argument *PointerArg = &*F->arg_begin(); - StoreInst *StoreInst = B.CreateStore(B.getInt8(16), PointerArg); - BranchInst::Create(Merge, Left); - BranchInst::Create(Merge, Right); - B.SetInsertPoint(Merge); - LoadInst *LoadInst = B.CreateLoad(PointerArg); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - MemorySSAUpdater Updater(&MSSA); - - // Before, the load will be a use of a phi. It should be - // the same after. - MemoryUse *LoadAccess = cast(MSSA.getMemoryAccess(LoadInst)); - MemoryDef *StoreAccess = cast(MSSA.getMemoryAccess(StoreInst)); - MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess(); - EXPECT_TRUE(isa(DefiningAccess)); - // The load is currently clobbered by one of the phi arguments, so the walker - // should determine the clobbering access as the phi. - EXPECT_EQ(DefiningAccess, Walker->getClobberingMemoryAccess(LoadInst)); - Updater.removeMemoryAccess(StoreAccess); - MSSA.verifyMemorySSA(); - // After the removeaccess, let's see if we got the right accesses - // The load should still point to the phi ... - EXPECT_EQ(DefiningAccess, LoadAccess->getDefiningAccess()); - // but we should now get live on entry for the clobbering definition of the - // load, since it will walk past the phi node since every argument is the - // same. - // XXX: This currently requires either removing the phi or resetting optimized - // on the load - - EXPECT_FALSE( - MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst))); - // If we reset optimized, we get live on entry. - LoadAccess->resetOptimized(); - EXPECT_TRUE( - MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(LoadInst))); - // The phi should now be a two entry phi with two live on entry defs. - for (const auto &Op : DefiningAccess->operands()) { - MemoryAccess *Operand = cast(&*Op); - EXPECT_TRUE(MSSA.isLiveOnEntryDef(Operand)); - } - - // Now we try to remove the single valued phi - Updater.removeMemoryAccess(DefiningAccess); - MSSA.verifyMemorySSA(); - // Now the load should be a load of live on entry. - EXPECT_TRUE(MSSA.isLiveOnEntryDef(LoadAccess->getDefiningAccess())); -} - -// We had a bug with caching where the walker would report MemoryDef#3's clobber -// (below) was MemoryDef#1. -// -// define void @F(i8*) { -// %A = alloca i8, i8 1 -// ; 1 = MemoryDef(liveOnEntry) -// store i8 0, i8* %A -// ; 2 = MemoryDef(1) -// store i8 1, i8* %A -// ; 3 = MemoryDef(2) -// store i8 2, i8* %A -// } -TEST_F(MemorySSATest, TestTripleStore) { - F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); - StoreInst *S1 = B.CreateStore(ConstantInt::get(Int8, 0), Alloca); - StoreInst *S2 = B.CreateStore(ConstantInt::get(Int8, 1), Alloca); - StoreInst *S3 = B.CreateStore(ConstantInt::get(Int8, 2), Alloca); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - - unsigned I = 0; - for (StoreInst *V : {S1, S2, S3}) { - // Everything should be clobbered by its defining access - MemoryAccess *DefiningAccess = MSSA.getMemoryAccess(V)->getDefiningAccess(); - MemoryAccess *WalkerClobber = Walker->getClobberingMemoryAccess(V); - EXPECT_EQ(DefiningAccess, WalkerClobber) - << "Store " << I << " doesn't have the correct clobbering access"; - // EXPECT_EQ expands such that if we increment I above, it won't get - // incremented except when we try to print the error message. - ++I; - } -} - -// ...And fixing the above bug made it obvious that, when walking, MemorySSA's -// walker was caching the initial node it walked. This was fine (albeit -// mostly redundant) unless the initial node being walked is a clobber for the -// query. In that case, we'd cache that the node clobbered itself. -TEST_F(MemorySSATest, TestStoreAndLoad) { - F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); - Instruction *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca); - Instruction *LI = B.CreateLoad(Alloca); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - - MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LI); - EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SI)); - EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SI))); -} - -// Another bug (related to the above two fixes): It was noted that, given the -// following code: -// ; 1 = MemoryDef(liveOnEntry) -// store i8 0, i8* %1 -// -// ...A query to getClobberingMemoryAccess(MemoryAccess*, MemoryLocation) would -// hand back the store (correctly). A later call to -// getClobberingMemoryAccess(const Instruction*) would also hand back the store -// (incorrectly; it should return liveOnEntry). -// -// This test checks that repeated calls to either function returns what they're -// meant to. -TEST_F(MemorySSATest, TestStoreDoubleQuery) { - F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); - StoreInst *SI = B.CreateStore(ConstantInt::get(Int8, 0), Alloca); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - - MemoryAccess *StoreAccess = MSSA.getMemoryAccess(SI); - MemoryLocation StoreLoc = MemoryLocation::get(SI); - MemoryAccess *Clobber = - Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc); - MemoryAccess *LiveOnEntry = Walker->getClobberingMemoryAccess(SI); - - EXPECT_EQ(Clobber, StoreAccess); - EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry)); - - // Try again (with entries in the cache already) for good measure... - Clobber = Walker->getClobberingMemoryAccess(StoreAccess, StoreLoc); - LiveOnEntry = Walker->getClobberingMemoryAccess(SI); - EXPECT_EQ(Clobber, StoreAccess); - EXPECT_TRUE(MSSA.isLiveOnEntryDef(LiveOnEntry)); -} - -// Bug: During phi optimization, the walker wouldn't cache to the proper result -// in the farthest-walked BB. -// -// Specifically, it would assume that whatever we walked to was a clobber. -// "Whatever we walked to" isn't a clobber if we hit a cache entry. -// -// ...So, we need a test case that looks like: -// A -// / \ -// B | -// \ / -// C -// -// Where, when we try to optimize a thing in 'C', a blocker is found in 'B'. -// The walk must determine that the blocker exists by using cache entries *while -// walking* 'B'. -TEST_F(MemorySSATest, PartialWalkerCacheWithPhis) { - F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "A", F)); - Type *Int8 = Type::getInt8Ty(C); - Constant *One = ConstantInt::get(Int8, 1); - Constant *Zero = ConstantInt::get(Int8, 0); - Value *AllocA = B.CreateAlloca(Int8, One, "a"); - Value *AllocB = B.CreateAlloca(Int8, One, "b"); - BasicBlock *IfThen = BasicBlock::Create(C, "B", F); - BasicBlock *IfEnd = BasicBlock::Create(C, "C", F); - - B.CreateCondBr(UndefValue::get(Type::getInt1Ty(C)), IfThen, IfEnd); - - B.SetInsertPoint(IfThen); - Instruction *FirstStore = B.CreateStore(Zero, AllocA); - B.CreateStore(Zero, AllocB); - Instruction *ALoad0 = B.CreateLoad(AllocA, ""); - Instruction *BStore = B.CreateStore(Zero, AllocB); - // Due to use optimization/etc. we make a store to A, which is removed after - // we build MSSA. This helps keep the test case simple-ish. - Instruction *KillStore = B.CreateStore(Zero, AllocA); - Instruction *ALoad = B.CreateLoad(AllocA, ""); - B.CreateBr(IfEnd); - - B.SetInsertPoint(IfEnd); - Instruction *BelowPhi = B.CreateStore(Zero, AllocA); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - MemorySSAUpdater Updater(&MSSA); - - // Kill `KillStore`; it exists solely so that the load after it won't be - // optimized to FirstStore. - Updater.removeMemoryAccess(MSSA.getMemoryAccess(KillStore)); - KillStore->eraseFromParent(); - auto *ALoadMA = cast(MSSA.getMemoryAccess(ALoad)); - EXPECT_EQ(ALoadMA->getDefiningAccess(), MSSA.getMemoryAccess(BStore)); - - // Populate the cache for the store to AllocB directly after FirstStore. It - // should point to something in block B (so something in D can't be optimized - // to it). - MemoryAccess *Load0Clobber = Walker->getClobberingMemoryAccess(ALoad0); - EXPECT_EQ(MSSA.getMemoryAccess(FirstStore), Load0Clobber); - - // If the bug exists, this will introduce a bad cache entry for %a on BStore. - // It will point to the store to %b after FirstStore. This only happens during - // phi optimization. - MemoryAccess *BottomClobber = Walker->getClobberingMemoryAccess(BelowPhi); - MemoryAccess *Phi = MSSA.getMemoryAccess(IfEnd); - EXPECT_EQ(BottomClobber, Phi); - - // This query will first check the cache for {%a, BStore}. It should point to - // FirstStore, not to the store after FirstStore. - MemoryAccess *UseClobber = Walker->getClobberingMemoryAccess(ALoad); - EXPECT_EQ(UseClobber, MSSA.getMemoryAccess(FirstStore)); -} - -// Test that our walker properly handles loads with the invariant group -// attribute. It's a bit hacky, since we add the invariant attribute *after* -// building MSSA. Otherwise, the use optimizer will optimize it for us, which -// isn't what we want. -// FIXME: It may be easier/cleaner to just add an 'optimize uses?' flag to MSSA. -TEST_F(MemorySSATest, WalkerInvariantLoadOpt) { - F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - Constant *One = ConstantInt::get(Int8, 1); - Value *AllocA = B.CreateAlloca(Int8, One, ""); - - Instruction *Store = B.CreateStore(One, AllocA); - Instruction *Load = B.CreateLoad(AllocA); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - - auto *LoadMA = cast(MSSA.getMemoryAccess(Load)); - auto *StoreMA = cast(MSSA.getMemoryAccess(Store)); - EXPECT_EQ(LoadMA->getDefiningAccess(), StoreMA); - - // ...At the time of writing, no cache should exist for LoadMA. Be a bit - // flexible to future changes. - Walker->invalidateInfo(LoadMA); - Load->setMetadata(LLVMContext::MD_invariant_load, MDNode::get(C, {})); - - MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LoadMA); - EXPECT_EQ(LoadClobber, MSSA.getLiveOnEntryDef()); -} - -// Test loads get reoptimized properly by the walker. -TEST_F(MemorySSATest, WalkerReopt) { - F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); - Instruction *SIA = B.CreateStore(ConstantInt::get(Int8, 0), AllocaA); - Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B"); - Instruction *SIB = B.CreateStore(ConstantInt::get(Int8, 0), AllocaB); - Instruction *LIA = B.CreateLoad(AllocaA); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - MemorySSAUpdater Updater(&MSSA); - - MemoryAccess *LoadClobber = Walker->getClobberingMemoryAccess(LIA); - MemoryUse *LoadAccess = cast(MSSA.getMemoryAccess(LIA)); - EXPECT_EQ(LoadClobber, MSSA.getMemoryAccess(SIA)); - EXPECT_TRUE(MSSA.isLiveOnEntryDef(Walker->getClobberingMemoryAccess(SIA))); - Updater.removeMemoryAccess(LoadAccess); - - // Create the load memory access pointing to an unoptimized place. - MemoryUse *NewLoadAccess = cast(Updater.createMemoryAccessInBB( - LIA, MSSA.getMemoryAccess(SIB), LIA->getParent(), MemorySSA::End)); - // This should it cause it to be optimized - EXPECT_EQ(Walker->getClobberingMemoryAccess(NewLoadAccess), LoadClobber); - EXPECT_EQ(NewLoadAccess->getDefiningAccess(), LoadClobber); -} - -// Test out MemorySSAUpdater::moveBefore -TEST_F(MemorySSATest, MoveAboveMemoryDef) { - F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - - Type *Int8 = Type::getInt8Ty(C); - Value *A = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); - Value *B_ = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B"); - Value *C = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C"); - - StoreInst *StoreA0 = B.CreateStore(ConstantInt::get(Int8, 0), A); - StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 0), B_); - LoadInst *LoadB = B.CreateLoad(B_); - StoreInst *StoreA1 = B.CreateStore(ConstantInt::get(Int8, 4), A); - StoreInst *StoreC = B.CreateStore(ConstantInt::get(Int8, 4), C); - StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 4), A); - LoadInst *LoadC = B.CreateLoad(C); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker &Walker = *Analyses->Walker; - - MemorySSAUpdater Updater(&MSSA); - StoreC->moveBefore(StoreB); - Updater.moveBefore(cast(MSSA.getMemoryAccess(StoreC)), - cast(MSSA.getMemoryAccess(StoreB))); - - MSSA.verifyMemorySSA(); - - EXPECT_EQ(MSSA.getMemoryAccess(StoreB)->getDefiningAccess(), - MSSA.getMemoryAccess(StoreC)); - EXPECT_EQ(MSSA.getMemoryAccess(StoreC)->getDefiningAccess(), - MSSA.getMemoryAccess(StoreA0)); - EXPECT_EQ(MSSA.getMemoryAccess(StoreA2)->getDefiningAccess(), - MSSA.getMemoryAccess(StoreA1)); - EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadB), - MSSA.getMemoryAccess(StoreB)); - EXPECT_EQ(Walker.getClobberingMemoryAccess(LoadC), - MSSA.getMemoryAccess(StoreC)); - - // exercise block numbering - EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreC), - MSSA.getMemoryAccess(StoreB))); - EXPECT_TRUE(MSSA.locallyDominates(MSSA.getMemoryAccess(StoreA1), - MSSA.getMemoryAccess(StoreA2))); -} - -TEST_F(MemorySSATest, Irreducible) { - // Create the equivalent of - // x = something - // if (...) - // goto second_loop_entry - // while (...) { - // second_loop_entry: - // } - // use(x) - - SmallVector Inserted; - IRBuilder<> B(C); - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - - // Make blocks - BasicBlock *IfBB = BasicBlock::Create(C, "if", F); - BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F); - BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F); - BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F); - B.SetInsertPoint(IfBB); - B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB); - B.SetInsertPoint(LoopStartBB); - B.CreateBr(LoopMainBB); - B.SetInsertPoint(LoopMainBB); - B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB); - B.SetInsertPoint(AfterLoopBB); - Argument *FirstArg = &*F->arg_begin(); - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAUpdater Updater(&MSSA); - // Create the load memory acccess - LoadInst *LoadInst = B.CreateLoad(FirstArg); - MemoryUse *LoadAccess = cast(Updater.createMemoryAccessInBB( - LoadInst, nullptr, AfterLoopBB, MemorySSA::Beginning)); - Updater.insertUse(LoadAccess); - MSSA.verifyMemorySSA(); -} - -TEST_F(MemorySSATest, MoveToBeforeLiveOnEntryInvalidatesCache) { - // Create: - // %1 = alloca i8 - // ; 1 = MemoryDef(liveOnEntry) - // store i8 0, i8* %1 - // ; 2 = MemoryDef(1) - // store i8 0, i8* %1 - // - // ...And be sure that MSSA's caching doesn't give us `1` for the clobber of - // `2` after `1` is removed. - IRBuilder<> B(C); - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - - BasicBlock *Entry = BasicBlock::Create(C, "if", F); - B.SetInsertPoint(Entry); - - Value *A = B.CreateAlloca(B.getInt8Ty()); - StoreInst *StoreA = B.CreateStore(B.getInt8(0), A); - StoreInst *StoreB = B.CreateStore(B.getInt8(0), A); - - setupAnalyses(); - - MemorySSA &MSSA = *Analyses->MSSA; - - auto *DefA = cast(MSSA.getMemoryAccess(StoreA)); - auto *DefB = cast(MSSA.getMemoryAccess(StoreB)); - - MemoryAccess *BClobber = MSSA.getWalker()->getClobberingMemoryAccess(DefB); - ASSERT_EQ(DefA, BClobber); - - MemorySSAUpdater(&MSSA).removeMemoryAccess(DefA); - StoreA->eraseFromParent(); - - EXPECT_EQ(DefB->getDefiningAccess(), MSSA.getLiveOnEntryDef()); - - EXPECT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(DefB), - MSSA.getLiveOnEntryDef()) - << "(DefA = " << DefA << ")"; -} - -TEST_F(MemorySSATest, RemovingDefInvalidatesCache) { - // Create: - // %x = alloca i8 - // %y = alloca i8 - // ; 1 = MemoryDef(liveOnEntry) - // store i8 0, i8* %x - // ; 2 = MemoryDef(1) - // store i8 0, i8* %y - // ; 3 = MemoryDef(2) - // store i8 0, i8* %x - // - // And be sure that MSSA's caching handles the removal of def `1` - // appropriately. - IRBuilder<> B(C); - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - - BasicBlock *Entry = BasicBlock::Create(C, "if", F); - B.SetInsertPoint(Entry); - - Value *X = B.CreateAlloca(B.getInt8Ty()); - Value *Y = B.CreateAlloca(B.getInt8Ty()); - StoreInst *StoreX1 = B.CreateStore(B.getInt8(0), X); - StoreInst *StoreY = B.CreateStore(B.getInt8(0), Y); - StoreInst *StoreX2 = B.CreateStore(B.getInt8(0), X); - - setupAnalyses(); - - MemorySSA &MSSA = *Analyses->MSSA; - - auto *DefX1 = cast(MSSA.getMemoryAccess(StoreX1)); - auto *DefY = cast(MSSA.getMemoryAccess(StoreY)); - auto *DefX2 = cast(MSSA.getMemoryAccess(StoreX2)); - - EXPECT_EQ(DefX2->getDefiningAccess(), DefY); - MemoryAccess *X2Clobber = MSSA.getWalker()->getClobberingMemoryAccess(DefX2); - ASSERT_EQ(DefX1, X2Clobber); - - MemorySSAUpdater(&MSSA).removeMemoryAccess(DefX1); - StoreX1->eraseFromParent(); - - EXPECT_EQ(DefX2->getDefiningAccess(), DefY); - EXPECT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(DefX2), - MSSA.getLiveOnEntryDef()) - << "(DefX1 = " << DefX1 << ")"; -} - -// Test Must alias for optimized uses -TEST_F(MemorySSATest, TestLoadMustAlias) { - F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); - Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B"); - - B.CreateStore(ConstantInt::get(Int8, 1), AllocaB); - // Check load from LOE - LoadInst *LA1 = B.CreateLoad(AllocaA, ""); - // Check load alias cached for second load - LoadInst *LA2 = B.CreateLoad(AllocaA, ""); - - B.CreateStore(ConstantInt::get(Int8, 1), AllocaA); - // Check load from store/def - LoadInst *LA3 = B.CreateLoad(AllocaA, ""); - // Check load alias cached for second load - LoadInst *LA4 = B.CreateLoad(AllocaA, ""); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - - unsigned I = 0; - for (LoadInst *V : {LA1, LA2}) { - MemoryUse *MemUse = dyn_cast_or_null(MSSA.getMemoryAccess(V)); - EXPECT_EQ(MemUse->getOptimizedAccessType(), None) - << "Load " << I << " doesn't have the correct alias information"; - // EXPECT_EQ expands such that if we increment I above, it won't get - // incremented except when we try to print the error message. - ++I; - } - for (LoadInst *V : {LA3, LA4}) { - MemoryUse *MemUse = dyn_cast_or_null(MSSA.getMemoryAccess(V)); - EXPECT_EQ(MemUse->getOptimizedAccessType(), MustAlias) - << "Load " << I << " doesn't have the correct alias information"; - // EXPECT_EQ expands such that if we increment I above, it won't get - // incremented except when we try to print the error message. - ++I; - } -} - -// Test Must alias for optimized defs. -TEST_F(MemorySSATest, TestStoreMustAlias) { - F = Function::Create(FunctionType::get(B.getVoidTy(), {}, false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - Value *AllocaA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); - Value *AllocaB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B"); - StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaA); - StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), AllocaB); - StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaA); - StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaB); - StoreInst *SA3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaA); - StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 3), AllocaB); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - - unsigned I = 0; - for (StoreInst *V : {SA1, SB1, SA2, SB2, SA3, SB3}) { - MemoryDef *MemDef = dyn_cast_or_null(MSSA.getMemoryAccess(V)); - EXPECT_EQ(MemDef->isOptimized(), false) - << "Store " << I << " is optimized from the start?"; - EXPECT_EQ(MemDef->getOptimizedAccessType(), MayAlias) - << "Store " << I - << " has correct alias information before being optimized?"; - if (V == SA1) - Walker->getClobberingMemoryAccess(V); - else { - MemoryAccess *Def = MemDef->getDefiningAccess(); - MemoryAccess *Clob = Walker->getClobberingMemoryAccess(V); - EXPECT_NE(Def, Clob) << "Store " << I - << " has Defining Access equal to Clobbering Access"; - } - EXPECT_EQ(MemDef->isOptimized(), true) - << "Store " << I << " was not optimized"; - if (I == 0 || I == 1) - EXPECT_EQ(MemDef->getOptimizedAccessType(), None) - << "Store " << I << " doesn't have the correct alias information"; - else - EXPECT_EQ(MemDef->getOptimizedAccessType(), MustAlias) - << "Store " << I << " doesn't have the correct alias information"; - // EXPECT_EQ expands such that if we increment I above, it won't get - // incremented except when we try to print the error message. - ++I; - } -} - -// Test May alias for optimized uses. -TEST_F(MemorySSATest, TestLoadMayAlias) { - F = Function::Create(FunctionType::get(B.getVoidTy(), - {B.getInt8PtrTy(), B.getInt8PtrTy()}, - false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - auto *ArgIt = F->arg_begin(); - Argument *PointerA = &*ArgIt; - Argument *PointerB = &*(++ArgIt); - B.CreateStore(ConstantInt::get(Int8, 1), PointerB); - LoadInst *LA1 = B.CreateLoad(PointerA, ""); - B.CreateStore(ConstantInt::get(Int8, 0), PointerA); - LoadInst *LB1 = B.CreateLoad(PointerB, ""); - B.CreateStore(ConstantInt::get(Int8, 0), PointerA); - LoadInst *LA2 = B.CreateLoad(PointerA, ""); - B.CreateStore(ConstantInt::get(Int8, 0), PointerB); - LoadInst *LB2 = B.CreateLoad(PointerB, ""); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - - unsigned I = 0; - for (LoadInst *V : {LA1, LB1}) { - MemoryUse *MemUse = dyn_cast_or_null(MSSA.getMemoryAccess(V)); - EXPECT_EQ(MemUse->getOptimizedAccessType(), MayAlias) - << "Load " << I << " doesn't have the correct alias information"; - // EXPECT_EQ expands such that if we increment I above, it won't get - // incremented except when we try to print the error message. - ++I; - } - for (LoadInst *V : {LA2, LB2}) { - MemoryUse *MemUse = dyn_cast_or_null(MSSA.getMemoryAccess(V)); - EXPECT_EQ(MemUse->getOptimizedAccessType(), MustAlias) - << "Load " << I << " doesn't have the correct alias information"; - // EXPECT_EQ expands such that if we increment I above, it won't get - // incremented except when we try to print the error message. - ++I; - } -} - -// Test May alias for optimized defs. -TEST_F(MemorySSATest, TestStoreMayAlias) { - F = Function::Create(FunctionType::get(B.getVoidTy(), - {B.getInt8PtrTy(), B.getInt8PtrTy()}, - false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - auto *ArgIt = F->arg_begin(); - Argument *PointerA = &*ArgIt; - Argument *PointerB = &*(++ArgIt); - Value *AllocaC = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "C"); - // Store into arg1, must alias because it's LOE => must - StoreInst *SA1 = B.CreateStore(ConstantInt::get(Int8, 0), PointerA); - // Store into arg2, may alias store to arg1 => may - StoreInst *SB1 = B.CreateStore(ConstantInt::get(Int8, 1), PointerB); - // Store into aloca, no alias with args, so must alias LOE => must - StoreInst *SC1 = B.CreateStore(ConstantInt::get(Int8, 2), AllocaC); - // Store into arg1, may alias store to arg2 => may - StoreInst *SA2 = B.CreateStore(ConstantInt::get(Int8, 3), PointerA); - // Store into arg2, may alias store to arg1 => may - StoreInst *SB2 = B.CreateStore(ConstantInt::get(Int8, 4), PointerB); - // Store into aloca, no alias with args, so must alias SC1 => must - StoreInst *SC2 = B.CreateStore(ConstantInt::get(Int8, 5), AllocaC); - // Store into arg2, must alias store to arg2 => must - StoreInst *SB3 = B.CreateStore(ConstantInt::get(Int8, 6), PointerB); - std::initializer_list Sts = {SA1, SB1, SC1, SA2, SB2, SC2, SB3}; - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - - unsigned I = 0; - for (StoreInst *V : Sts) { - MemoryDef *MemDef = dyn_cast_or_null(MSSA.getMemoryAccess(V)); - EXPECT_EQ(MemDef->isOptimized(), false) - << "Store " << I << " is optimized from the start?"; - EXPECT_EQ(MemDef->getOptimizedAccessType(), MayAlias) - << "Store " << I - << " has correct alias information before being optimized?"; - ++I; - } - - for (StoreInst *V : Sts) - Walker->getClobberingMemoryAccess(V); - - I = 0; - for (StoreInst *V : Sts) { - MemoryDef *MemDef = dyn_cast_or_null(MSSA.getMemoryAccess(V)); - EXPECT_EQ(MemDef->isOptimized(), true) - << "Store " << I << " was not optimized"; - if (I == 1 || I == 3 || I == 4) - EXPECT_EQ(MemDef->getOptimizedAccessType(), MayAlias) - << "Store " << I << " doesn't have the correct alias information"; - else if (I == 0 || I == 2) - EXPECT_EQ(MemDef->getOptimizedAccessType(), None) - << "Store " << I << " doesn't have the correct alias information"; - else - EXPECT_EQ(MemDef->getOptimizedAccessType(), MustAlias) - << "Store " << I << " doesn't have the correct alias information"; - // EXPECT_EQ expands such that if we increment I above, it won't get - // incremented except when we try to print the error message. - ++I; - } -} - -TEST_F(MemorySSATest, LifetimeMarkersAreClobbers) { - // Example code: - // define void @a(i8* %foo) { - // %bar = getelementptr i8, i8* %foo, i64 1 - // store i8 0, i8* %foo - // store i8 0, i8* %bar - // call void @llvm.lifetime.end.p0i8(i64 8, i32* %p) - // call void @llvm.lifetime.start.p0i8(i64 8, i32* %p) - // store i8 0, i8* %foo - // store i8 0, i8* %bar - // ret void - // } - // - // Patterns like this are possible after inlining; the stores to %foo and %bar - // should both be clobbered by the lifetime.start call if they're dominated by - // it. - - IRBuilder<> B(C); - F = Function::Create( - FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - - // Make blocks - BasicBlock *Entry = BasicBlock::Create(C, "entry", F); - - B.SetInsertPoint(Entry); - Value *Foo = &*F->arg_begin(); - - Value *Bar = B.CreateGEP(Foo, B.getInt64(1), "bar"); - - B.CreateStore(B.getInt8(0), Foo); - B.CreateStore(B.getInt8(0), Bar); - - auto GetLifetimeIntrinsic = [&](Intrinsic::ID ID) { - return Intrinsic::getDeclaration(&M, ID, {Foo->getType()}); - }; - - B.CreateCall(GetLifetimeIntrinsic(Intrinsic::lifetime_end), - {B.getInt64(2), Foo}); - Instruction *LifetimeStart = B.CreateCall( - GetLifetimeIntrinsic(Intrinsic::lifetime_start), {B.getInt64(2), Foo}); - - Instruction *FooStore = B.CreateStore(B.getInt8(0), Foo); - Instruction *BarStore = B.CreateStore(B.getInt8(0), Bar); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - - MemoryAccess *LifetimeStartAccess = MSSA.getMemoryAccess(LifetimeStart); - ASSERT_NE(LifetimeStartAccess, nullptr); - - MemoryAccess *FooAccess = MSSA.getMemoryAccess(FooStore); - ASSERT_NE(FooAccess, nullptr); - - MemoryAccess *BarAccess = MSSA.getMemoryAccess(BarStore); - ASSERT_NE(BarAccess, nullptr); - - MemoryAccess *FooClobber = - MSSA.getWalker()->getClobberingMemoryAccess(FooAccess); - EXPECT_EQ(FooClobber, LifetimeStartAccess); - - MemoryAccess *BarClobber = - MSSA.getWalker()->getClobberingMemoryAccess(BarAccess); - EXPECT_EQ(BarClobber, LifetimeStartAccess); -} - -TEST_F(MemorySSATest, DefOptimizationsAreInvalidatedOnMoving) { - IRBuilder<> B(C); - F = Function::Create(FunctionType::get(B.getVoidTy(), {B.getInt1Ty()}, false), - GlobalValue::ExternalLinkage, "F", &M); - - // Make a CFG like - // entry - // / \ - // a b - // \ / - // c - // - // Put a def in A and a def in B, move the def from A -> B, observe as the - // optimization is invalidated. - BasicBlock *Entry = BasicBlock::Create(C, "entry", F); - BasicBlock *BlockA = BasicBlock::Create(C, "a", F); - BasicBlock *BlockB = BasicBlock::Create(C, "b", F); - BasicBlock *BlockC = BasicBlock::Create(C, "c", F); - - B.SetInsertPoint(Entry); - Type *Int8 = Type::getInt8Ty(C); - Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "alloc"); - StoreInst *StoreEntry = B.CreateStore(B.getInt8(0), Alloca); - B.CreateCondBr(B.getTrue(), BlockA, BlockB); - - B.SetInsertPoint(BlockA); - StoreInst *StoreA = B.CreateStore(B.getInt8(1), Alloca); - B.CreateBr(BlockC); - - B.SetInsertPoint(BlockB); - StoreInst *StoreB = B.CreateStore(B.getInt8(2), Alloca); - B.CreateBr(BlockC); - - B.SetInsertPoint(BlockC); - B.CreateUnreachable(); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - - auto *AccessEntry = cast(MSSA.getMemoryAccess(StoreEntry)); - auto *StoreAEntry = cast(MSSA.getMemoryAccess(StoreA)); - auto *StoreBEntry = cast(MSSA.getMemoryAccess(StoreB)); - - ASSERT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(StoreAEntry), - AccessEntry); - ASSERT_TRUE(StoreAEntry->isOptimized()); - - ASSERT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(StoreBEntry), - AccessEntry); - ASSERT_TRUE(StoreBEntry->isOptimized()); - - // Note that if we did InsertionPlace::Beginning, we don't go out of our way - // to invalidate the cache for StoreBEntry. If the user wants to actually do - // moves like these, it's up to them to ensure that nearby cache entries are - // correctly invalidated (which, in general, requires walking all instructions - // that the moved instruction dominates. So we probably shouldn't be doing - // moves like this in general. Still, works as a test-case. ;) ) - MemorySSAUpdater(&MSSA).moveToPlace(StoreAEntry, BlockB, - MemorySSA::InsertionPlace::End); - ASSERT_FALSE(StoreAEntry->isOptimized()); - ASSERT_EQ(MSSA.getWalker()->getClobberingMemoryAccess(StoreAEntry), - StoreBEntry); -} - -TEST_F(MemorySSATest, TestOptimizedDefsAreProperUses) { - F = Function::Create(FunctionType::get(B.getVoidTy(), - {B.getInt8PtrTy(), B.getInt8PtrTy()}, - false), - GlobalValue::ExternalLinkage, "F", &M); - B.SetInsertPoint(BasicBlock::Create(C, "", F)); - Type *Int8 = Type::getInt8Ty(C); - Value *AllocA = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A"); - Value *AllocB = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "B"); - - StoreInst *StoreA = B.CreateStore(ConstantInt::get(Int8, 0), AllocA); - StoreInst *StoreB = B.CreateStore(ConstantInt::get(Int8, 1), AllocB); - StoreInst *StoreA2 = B.CreateStore(ConstantInt::get(Int8, 2), AllocA); - - setupAnalyses(); - MemorySSA &MSSA = *Analyses->MSSA; - MemorySSAWalker *Walker = Analyses->Walker; - - // If these don't hold, there's no chance of the test result being useful. - ASSERT_EQ(Walker->getClobberingMemoryAccess(StoreA), - MSSA.getLiveOnEntryDef()); - ASSERT_EQ(Walker->getClobberingMemoryAccess(StoreB), - MSSA.getLiveOnEntryDef()); - auto *StoreAAccess = cast(MSSA.getMemoryAccess(StoreA)); - auto *StoreA2Access = cast(MSSA.getMemoryAccess(StoreA2)); - ASSERT_EQ(Walker->getClobberingMemoryAccess(StoreA2), StoreAAccess); - ASSERT_EQ(StoreA2Access->getOptimized(), StoreAAccess); - - auto *StoreBAccess = cast(MSSA.getMemoryAccess(StoreB)); - ASSERT_LT(StoreAAccess->getID(), StoreBAccess->getID()); - ASSERT_LT(StoreBAccess->getID(), StoreA2Access->getID()); - - auto SortVecByID = [](std::vector &Defs) { - llvm::sort(Defs.begin(), Defs.end(), - [](const MemoryDef *LHS, const MemoryDef *RHS) { - return LHS->getID() < RHS->getID(); - }); - }; - - auto SortedUserList = [&](const MemoryDef *MD) { - std::vector Result; - transform(MD->users(), std::back_inserter(Result), - [](const User *U) { return cast(U); }); - SortVecByID(Result); - return Result; - }; - - // Use std::vectors, since they have nice pretty-printing if the test fails. - // Parens are necessary because EXPECT_EQ is a macro, and we have commas in - // our init lists... - EXPECT_EQ(SortedUserList(StoreAAccess), - (std::vector{StoreBAccess, StoreA2Access})); - - EXPECT_EQ(SortedUserList(StoreBAccess), - std::vector{StoreA2Access}); - - // StoreAAccess should be present twice, since it uses liveOnEntry for both - // its defining and optimized accesses. This is a bit awkward, and is not - // relied upon anywhere at the moment. If this is painful, we can fix it. - EXPECT_EQ(SortedUserList(cast(MSSA.getLiveOnEntryDef())), - (std::vector{StoreAAccess, StoreAAccess, - StoreBAccess})); -} Index: unittests/Analysis/OrderedInstructions.cpp =================================================================== --- unittests/Analysis/OrderedInstructions.cpp +++ unittests/Analysis/OrderedInstructions.cpp @@ -1,65 +0,0 @@ -//===- OrderedInstructions.cpp - Unit tests for OrderedInstructions ------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/OrderedInstructions.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "gtest/gtest.h" - -using namespace llvm; - -/// Check intra-basicblock and inter-basicblock dominance using -/// OrderedInstruction. -TEST(OrderedInstructionsTest, DominanceTest) { - LLVMContext Ctx; - Module M("test", Ctx); - IRBuilder<> B(Ctx); - FunctionType *FTy = - FunctionType::get(Type::getVoidTy(Ctx), {B.getInt8PtrTy()}, false); - Function *F = cast(M.getOrInsertFunction("f", FTy)); - - // Create the function as follow and check for dominance relation. - // - // test(): - // bbx: - // loadx; - // loady; - // bby: - // loadz; - // return; - // - // More specifically, check for loadx -> (dominates) loady, - // loady -> loadx and loady -> loadz. - // - // Create BBX with 2 loads. - BasicBlock *BBX = BasicBlock::Create(Ctx, "bbx", F); - B.SetInsertPoint(BBX); - Argument *PointerArg = &*F->arg_begin(); - LoadInst *LoadInstX = B.CreateLoad(PointerArg); - LoadInst *LoadInstY = B.CreateLoad(PointerArg); - - // Create BBY with 1 load. - BasicBlock *BBY = BasicBlock::Create(Ctx, "bby", F); - B.SetInsertPoint(BBY); - LoadInst *LoadInstZ = B.CreateLoad(PointerArg); - B.CreateRet(LoadInstZ); - std::unique_ptr DT(new DominatorTree(*F)); - OrderedInstructions OI(&*DT); - - // Intra-BB dominance test. - EXPECT_TRUE(OI.dominates(LoadInstX, LoadInstY)); - EXPECT_FALSE(OI.dominates(LoadInstY, LoadInstX)); - - // Inter-BB dominance test. - EXPECT_TRUE(OI.dominates(LoadInstY, LoadInstZ)); -} Index: unittests/Analysis/UnrollAnalyzer.cpp =================================================================== --- unittests/Analysis/UnrollAnalyzer.cpp +++ unittests/Analysis/UnrollAnalyzer.cpp @@ -1,330 +0,0 @@ -//===- UnrollAnalyzerTest.cpp - UnrollAnalyzer unit tests -----------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/LoopUnrollAnalyzer.h" -#include "llvm/AsmParser/Parser.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/LegacyPassManager.h" -#include "llvm/Support/SourceMgr.h" -#include "gtest/gtest.h" - -using namespace llvm; -namespace llvm { -void initializeUnrollAnalyzerTestPass(PassRegistry &); - -static SmallVector, 16> SimplifiedValuesVector; -static unsigned TripCount = 0; - -namespace { -struct UnrollAnalyzerTest : public FunctionPass { - static char ID; - bool runOnFunction(Function &F) override { - LoopInfo *LI = &getAnalysis().getLoopInfo(); - ScalarEvolution *SE = &getAnalysis().getSE(); - - Function::iterator FI = F.begin(); - FI++; // First basic block is entry - skip it. - BasicBlock *Header = &*FI++; - Loop *L = LI->getLoopFor(Header); - BasicBlock *Exiting = L->getExitingBlock(); - - SimplifiedValuesVector.clear(); - TripCount = SE->getSmallConstantTripCount(L, Exiting); - for (unsigned Iteration = 0; Iteration < TripCount; Iteration++) { - DenseMap SimplifiedValues; - UnrolledInstAnalyzer Analyzer(Iteration, SimplifiedValues, *SE, L); - for (auto *BB : L->getBlocks()) - for (Instruction &I : *BB) - Analyzer.visit(I); - SimplifiedValuesVector.push_back(SimplifiedValues); - } - return false; - } - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); - AU.setPreservesAll(); - } - UnrollAnalyzerTest() : FunctionPass(ID) { - initializeUnrollAnalyzerTestPass(*PassRegistry::getPassRegistry()); - } -}; -} - -char UnrollAnalyzerTest::ID = 0; - -std::unique_ptr makeLLVMModule(LLVMContext &Context, - const char *ModuleStr) { - SMDiagnostic Err; - return parseAssemblyString(ModuleStr, Err, Context); -} - -TEST(UnrollAnalyzerTest, BasicSimplifications) { - const char *ModuleStr = - "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" - "define i64 @propagate_loop_phis() {\n" - "entry:\n" - " br label %loop\n" - "loop:\n" - " %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]\n" - " %x0 = phi i64 [ 0, %entry ], [ %x2, %loop ]\n" - " %x1 = or i64 %x0, 1\n" - " %x2 = or i64 %x1, 2\n" - " %inc = add nuw nsw i64 %iv, 1\n" - " %cond = icmp sge i64 %inc, 8\n" - " br i1 %cond, label %loop.end, label %loop\n" - "loop.end:\n" - " %x.lcssa = phi i64 [ %x2, %loop ]\n" - " ret i64 %x.lcssa\n" - "}\n"; - UnrollAnalyzerTest *P = new UnrollAnalyzerTest(); - LLVMContext Context; - std::unique_ptr M = makeLLVMModule(Context, ModuleStr); - legacy::PassManager Passes; - Passes.add(P); - Passes.run(*M); - - // Perform checks - Module::iterator MI = M->begin(); - Function *F = &*MI++; - Function::iterator FI = F->begin(); - FI++; // First basic block is entry - skip it. - BasicBlock *Header = &*FI++; - - BasicBlock::iterator BBI = Header->begin(); - std::advance(BBI, 4); - Instruction *Y1 = &*BBI++; - Instruction *Y2 = &*BBI++; - // Check simplification expected on the 1st iteration. - // Check that "%inc = add nuw nsw i64 %iv, 1" is simplified to 1 - auto I1 = SimplifiedValuesVector[0].find(Y1); - EXPECT_TRUE(I1 != SimplifiedValuesVector[0].end()); - EXPECT_EQ(cast((*I1).second)->getZExtValue(), 1U); - - // Check that "%cond = icmp sge i64 %inc, 10" is simplified to false - auto I2 = SimplifiedValuesVector[0].find(Y2); - EXPECT_TRUE(I2 != SimplifiedValuesVector[0].end()); - EXPECT_FALSE(cast((*I2).second)->getZExtValue()); - - // Check simplification expected on the last iteration. - // Check that "%inc = add nuw nsw i64 %iv, 1" is simplified to 8 - I1 = SimplifiedValuesVector[TripCount - 1].find(Y1); - EXPECT_TRUE(I1 != SimplifiedValuesVector[TripCount - 1].end()); - EXPECT_EQ(cast((*I1).second)->getZExtValue(), TripCount); - - // Check that "%cond = icmp sge i64 %inc, 10" is simplified to false - I2 = SimplifiedValuesVector[TripCount - 1].find(Y2); - EXPECT_TRUE(I2 != SimplifiedValuesVector[TripCount - 1].end()); - EXPECT_TRUE(cast((*I2).second)->getZExtValue()); -} - -TEST(UnrollAnalyzerTest, OuterLoopSimplification) { - const char *ModuleStr = - "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" - "define void @foo() {\n" - "entry:\n" - " br label %outer.loop\n" - "outer.loop:\n" - " %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %outer.loop.latch ]\n" - " %iv.outer.next = add nuw nsw i64 %iv.outer, 1\n" - " br label %inner.loop\n" - "inner.loop:\n" - " %iv.inner = phi i64 [ 0, %outer.loop ], [ %iv.inner.next, %inner.loop ]\n" - " %iv.inner.next = add nuw nsw i64 %iv.inner, 1\n" - " %exitcond.inner = icmp eq i64 %iv.inner.next, 1000\n" - " br i1 %exitcond.inner, label %outer.loop.latch, label %inner.loop\n" - "outer.loop.latch:\n" - " %exitcond.outer = icmp eq i64 %iv.outer.next, 40\n" - " br i1 %exitcond.outer, label %exit, label %outer.loop\n" - "exit:\n" - " ret void\n" - "}\n"; - - UnrollAnalyzerTest *P = new UnrollAnalyzerTest(); - LLVMContext Context; - std::unique_ptr M = makeLLVMModule(Context, ModuleStr); - legacy::PassManager Passes; - Passes.add(P); - Passes.run(*M); - - Module::iterator MI = M->begin(); - Function *F = &*MI++; - Function::iterator FI = F->begin(); - FI++; - BasicBlock *Header = &*FI++; - BasicBlock *InnerBody = &*FI++; - - BasicBlock::iterator BBI = Header->begin(); - BBI++; - Instruction *Y1 = &*BBI; - BBI = InnerBody->begin(); - BBI++; - Instruction *Y2 = &*BBI; - // Check that we can simplify IV of the outer loop, but can't simplify the IV - // of the inner loop if we only know the iteration number of the outer loop. - // - // Y1 is %iv.outer.next, Y2 is %iv.inner.next - auto I1 = SimplifiedValuesVector[0].find(Y1); - EXPECT_TRUE(I1 != SimplifiedValuesVector[0].end()); - auto I2 = SimplifiedValuesVector[0].find(Y2); - EXPECT_TRUE(I2 == SimplifiedValuesVector[0].end()); -} -TEST(UnrollAnalyzerTest, CmpSimplifications) { - const char *ModuleStr = - "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" - "define void @branch_iv_trunc() {\n" - "entry:\n" - " br label %for.body\n" - "for.body:\n" - " %indvars.iv = phi i64 [ 0, %entry ], [ %tmp3, %for.body ]\n" - " %tmp2 = trunc i64 %indvars.iv to i32\n" - " %cmp3 = icmp eq i32 %tmp2, 5\n" - " %tmp3 = add nuw nsw i64 %indvars.iv, 1\n" - " %exitcond = icmp eq i64 %tmp3, 10\n" - " br i1 %exitcond, label %for.end, label %for.body\n" - "for.end:\n" - " ret void\n" - "}\n"; - UnrollAnalyzerTest *P = new UnrollAnalyzerTest(); - LLVMContext Context; - std::unique_ptr M = makeLLVMModule(Context, ModuleStr); - legacy::PassManager Passes; - Passes.add(P); - Passes.run(*M); - - // Perform checks - Module::iterator MI = M->begin(); - Function *F = &*MI++; - Function::iterator FI = F->begin(); - FI++; // First basic block is entry - skip it. - BasicBlock *Header = &*FI++; - - BasicBlock::iterator BBI = Header->begin(); - BBI++; - Instruction *Y1 = &*BBI++; - Instruction *Y2 = &*BBI++; - // Check simplification expected on the 5th iteration. - // Check that "%tmp2 = trunc i64 %indvars.iv to i32" is simplified to 5 - // and "%cmp3 = icmp eq i32 %tmp2, 5" is simplified to 1 (i.e. true). - auto I1 = SimplifiedValuesVector[5].find(Y1); - EXPECT_TRUE(I1 != SimplifiedValuesVector[5].end()); - EXPECT_EQ(cast((*I1).second)->getZExtValue(), 5U); - auto I2 = SimplifiedValuesVector[5].find(Y2); - EXPECT_TRUE(I2 != SimplifiedValuesVector[5].end()); - EXPECT_EQ(cast((*I2).second)->getZExtValue(), 1U); -} -TEST(UnrollAnalyzerTest, PtrCmpSimplifications) { - const char *ModuleStr = - "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" - "define void @ptr_cmp(i8 *%a) {\n" - "entry:\n" - " %limit = getelementptr i8, i8* %a, i64 40\n" - " %start.iv2 = getelementptr i8, i8* %a, i64 7\n" - " br label %loop.body\n" - "loop.body:\n" - " %iv.0 = phi i8* [ %a, %entry ], [ %iv.1, %loop.body ]\n" - " %iv2.0 = phi i8* [ %start.iv2, %entry ], [ %iv2.1, %loop.body ]\n" - " %cmp = icmp eq i8* %iv2.0, %iv.0\n" - " %iv.1 = getelementptr inbounds i8, i8* %iv.0, i64 1\n" - " %iv2.1 = getelementptr inbounds i8, i8* %iv2.0, i64 1\n" - " %exitcond = icmp ne i8* %iv.1, %limit\n" - " br i1 %exitcond, label %loop.body, label %loop.exit\n" - "loop.exit:\n" - " ret void\n" - "}\n"; - UnrollAnalyzerTest *P = new UnrollAnalyzerTest(); - LLVMContext Context; - std::unique_ptr M = makeLLVMModule(Context, ModuleStr); - legacy::PassManager Passes; - Passes.add(P); - Passes.run(*M); - - // Perform checks - Module::iterator MI = M->begin(); - Function *F = &*MI++; - Function::iterator FI = F->begin(); - FI++; // First basic block is entry - skip it. - BasicBlock *Header = &*FI; - - BasicBlock::iterator BBI = Header->begin(); - std::advance(BBI, 2); - Instruction *Y1 = &*BBI; - // Check simplification expected on the 5th iteration. - // Check that "%cmp = icmp eq i8* %iv2.0, %iv.0" is simplified to 0. - auto I1 = SimplifiedValuesVector[5].find(Y1); - EXPECT_TRUE(I1 != SimplifiedValuesVector[5].end()); - EXPECT_EQ(cast((*I1).second)->getZExtValue(), 0U); -} -TEST(UnrollAnalyzerTest, CastSimplifications) { - const char *ModuleStr = - "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" - "@known_constant = internal unnamed_addr constant [10 x i32] [i32 0, i32 1, i32 0, i32 1, i32 0, i32 259, i32 0, i32 1, i32 0, i32 1], align 16\n" - "define void @const_load_cast() {\n" - "entry:\n" - " br label %loop\n" - "\n" - "loop:\n" - " %iv = phi i64 [ 0, %entry ], [ %inc, %loop ]\n" - " %array_const_idx = getelementptr inbounds [10 x i32], [10 x i32]* @known_constant, i64 0, i64 %iv\n" - " %const_array_element = load i32, i32* %array_const_idx, align 4\n" - " %se = sext i32 %const_array_element to i64\n" - " %ze = zext i32 %const_array_element to i64\n" - " %tr = trunc i32 %const_array_element to i8\n" - " %inc = add nuw nsw i64 %iv, 1\n" - " %exitcond86.i = icmp eq i64 %inc, 10\n" - " br i1 %exitcond86.i, label %loop.end, label %loop\n" - "\n" - "loop.end:\n" - " ret void\n" - "}\n"; - - UnrollAnalyzerTest *P = new UnrollAnalyzerTest(); - LLVMContext Context; - std::unique_ptr M = makeLLVMModule(Context, ModuleStr); - legacy::PassManager Passes; - Passes.add(P); - Passes.run(*M); - - // Perform checks - Module::iterator MI = M->begin(); - Function *F = &*MI++; - Function::iterator FI = F->begin(); - FI++; // First basic block is entry - skip it. - BasicBlock *Header = &*FI++; - - BasicBlock::iterator BBI = Header->begin(); - std::advance(BBI, 3); - Instruction *Y1 = &*BBI++; - Instruction *Y2 = &*BBI++; - Instruction *Y3 = &*BBI++; - // Check simplification expected on the 5th iteration. - // "%se = sext i32 %const_array_element to i64" should be simplified to 259, - // "%ze = zext i32 %const_array_element to i64" should be simplified to 259, - // "%tr = trunc i32 %const_array_element to i8" should be simplified to 3. - auto I1 = SimplifiedValuesVector[5].find(Y1); - EXPECT_TRUE(I1 != SimplifiedValuesVector[5].end()); - EXPECT_EQ(cast((*I1).second)->getZExtValue(), 259U); - auto I2 = SimplifiedValuesVector[5].find(Y2); - EXPECT_TRUE(I2 != SimplifiedValuesVector[5].end()); - EXPECT_EQ(cast((*I2).second)->getZExtValue(), 259U); - auto I3 = SimplifiedValuesVector[5].find(Y3); - EXPECT_TRUE(I3 != SimplifiedValuesVector[5].end()); - EXPECT_EQ(cast((*I3).second)->getZExtValue(), 3U); -} - -} // end namespace llvm - -INITIALIZE_PASS_BEGIN(UnrollAnalyzerTest, "unrollanalyzertestpass", - "unrollanalyzertestpass", false, false) -INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) -INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) -INITIALIZE_PASS_END(UnrollAnalyzerTest, "unrollanalyzertestpass", - "unrollanalyzertestpass", false, false) Index: unittests/Transforms/Utils/BasicBlockUtils.cpp =================================================================== --- unittests/Transforms/Utils/BasicBlockUtils.cpp +++ unittests/Transforms/Utils/BasicBlockUtils.cpp @@ -1,52 +0,0 @@ -//===- BasicBlockUtils.cpp - Unit tests for BasicBlockUtils ---------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/AsmParser/Parser.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/Support/SourceMgr.h" -#include "gtest/gtest.h" - -using namespace llvm; - -static std::unique_ptr parseIR(LLVMContext &C, const char *IR) { - SMDiagnostic Err; - std::unique_ptr Mod = parseAssemblyString(IR, Err, C); - if (!Mod) - Err.print("BasicBlockUtilsTests", errs()); - return Mod; -} - -TEST(BasicBlockUtils, SplitBlockPredecessors) { - LLVMContext C; - - std::unique_ptr M = parseIR( - C, - "define i32 @basic_func(i1 %cond) {\n" - "entry:\n" - " br i1 %cond, label %bb0, label %bb1\n" - "bb0:\n" - " br label %bb1\n" - "bb1:\n" - " %phi = phi i32 [ 0, %entry ], [ 1, %bb0 ]" - " ret i32 %phi\n" - "}\n" - "\n" - ); - - auto *F = M->getFunction("basic_func"); - DominatorTree DT(*F); - - // Make sure the dominator tree is properly updated if calling this on the - // entry block. - SplitBlockPredecessors(&F->getEntryBlock(), {}, "split.entry", &DT); - EXPECT_TRUE(DT.verify()); -} Index: unittests/Transforms/Utils/CMakeLists.txt =================================================================== --- unittests/Transforms/Utils/CMakeLists.txt +++ unittests/Transforms/Utils/CMakeLists.txt @@ -8,12 +8,12 @@ add_llvm_unittest(UtilsTests ASanStackFrameLayoutTest.cpp - BasicBlockUtils.cpp - Cloning.cpp - CodeExtractor.cpp - FunctionComparator.cpp - IntegerDivision.cpp - Local.cpp - SSAUpdaterBulk.cpp + BasicBlockUtilsTest.cpp + CloningTest.cpp + CodeExtractorTest.cpp + FunctionComparatorTest.cpp + IntegerDivisionTest.cpp + LocalTest.cpp + SSAUpdaterBulkTest.cpp ValueMapperTest.cpp ) Index: unittests/Transforms/Utils/Cloning.cpp =================================================================== --- unittests/Transforms/Utils/Cloning.cpp +++ unittests/Transforms/Utils/Cloning.cpp @@ -1,715 +0,0 @@ -//===- Cloning.cpp - Unit tests for the Cloner ----------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/Utils/Cloning.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/IR/Argument.h" -#include "llvm/IR/Constant.h" -#include "llvm/IR/DIBuilder.h" -#include "llvm/IR/DebugInfo.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/InstIterator.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/IntrinsicInst.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/Verifier.h" -#include "gtest/gtest.h" - -using namespace llvm; - -namespace { - -class CloneInstruction : public ::testing::Test { -protected: - void SetUp() override { V = nullptr; } - - template - T *clone(T *V1) { - Value *V2 = V1->clone(); - Orig.insert(V1); - Clones.insert(V2); - return cast(V2); - } - - void eraseClones() { - for (Value *V : Clones) - V->deleteValue(); - Clones.clear(); - } - - void TearDown() override { - eraseClones(); - for (Value *V : Orig) - V->deleteValue(); - Orig.clear(); - if (V) - V->deleteValue(); - } - - SmallPtrSet Orig; // Erase on exit - SmallPtrSet Clones; // Erase in eraseClones - - LLVMContext context; - Value *V; -}; - -TEST_F(CloneInstruction, OverflowBits) { - V = new Argument(Type::getInt32Ty(context)); - - BinaryOperator *Add = BinaryOperator::Create(Instruction::Add, V, V); - BinaryOperator *Sub = BinaryOperator::Create(Instruction::Sub, V, V); - BinaryOperator *Mul = BinaryOperator::Create(Instruction::Mul, V, V); - - BinaryOperator *AddClone = this->clone(Add); - BinaryOperator *SubClone = this->clone(Sub); - BinaryOperator *MulClone = this->clone(Mul); - - EXPECT_FALSE(AddClone->hasNoUnsignedWrap()); - EXPECT_FALSE(AddClone->hasNoSignedWrap()); - EXPECT_FALSE(SubClone->hasNoUnsignedWrap()); - EXPECT_FALSE(SubClone->hasNoSignedWrap()); - EXPECT_FALSE(MulClone->hasNoUnsignedWrap()); - EXPECT_FALSE(MulClone->hasNoSignedWrap()); - - eraseClones(); - - Add->setHasNoUnsignedWrap(); - Sub->setHasNoUnsignedWrap(); - Mul->setHasNoUnsignedWrap(); - - AddClone = this->clone(Add); - SubClone = this->clone(Sub); - MulClone = this->clone(Mul); - - EXPECT_TRUE(AddClone->hasNoUnsignedWrap()); - EXPECT_FALSE(AddClone->hasNoSignedWrap()); - EXPECT_TRUE(SubClone->hasNoUnsignedWrap()); - EXPECT_FALSE(SubClone->hasNoSignedWrap()); - EXPECT_TRUE(MulClone->hasNoUnsignedWrap()); - EXPECT_FALSE(MulClone->hasNoSignedWrap()); - - eraseClones(); - - Add->setHasNoSignedWrap(); - Sub->setHasNoSignedWrap(); - Mul->setHasNoSignedWrap(); - - AddClone = this->clone(Add); - SubClone = this->clone(Sub); - MulClone = this->clone(Mul); - - EXPECT_TRUE(AddClone->hasNoUnsignedWrap()); - EXPECT_TRUE(AddClone->hasNoSignedWrap()); - EXPECT_TRUE(SubClone->hasNoUnsignedWrap()); - EXPECT_TRUE(SubClone->hasNoSignedWrap()); - EXPECT_TRUE(MulClone->hasNoUnsignedWrap()); - EXPECT_TRUE(MulClone->hasNoSignedWrap()); - - eraseClones(); - - Add->setHasNoUnsignedWrap(false); - Sub->setHasNoUnsignedWrap(false); - Mul->setHasNoUnsignedWrap(false); - - AddClone = this->clone(Add); - SubClone = this->clone(Sub); - MulClone = this->clone(Mul); - - EXPECT_FALSE(AddClone->hasNoUnsignedWrap()); - EXPECT_TRUE(AddClone->hasNoSignedWrap()); - EXPECT_FALSE(SubClone->hasNoUnsignedWrap()); - EXPECT_TRUE(SubClone->hasNoSignedWrap()); - EXPECT_FALSE(MulClone->hasNoUnsignedWrap()); - EXPECT_TRUE(MulClone->hasNoSignedWrap()); -} - -TEST_F(CloneInstruction, Inbounds) { - V = new Argument(Type::getInt32PtrTy(context)); - - Constant *Z = Constant::getNullValue(Type::getInt32Ty(context)); - std::vector ops; - ops.push_back(Z); - GetElementPtrInst *GEP = - GetElementPtrInst::Create(Type::getInt32Ty(context), V, ops); - EXPECT_FALSE(this->clone(GEP)->isInBounds()); - - GEP->setIsInBounds(); - EXPECT_TRUE(this->clone(GEP)->isInBounds()); -} - -TEST_F(CloneInstruction, Exact) { - V = new Argument(Type::getInt32Ty(context)); - - BinaryOperator *SDiv = BinaryOperator::Create(Instruction::SDiv, V, V); - EXPECT_FALSE(this->clone(SDiv)->isExact()); - - SDiv->setIsExact(true); - EXPECT_TRUE(this->clone(SDiv)->isExact()); -} - -TEST_F(CloneInstruction, Attributes) { - Type *ArgTy1[] = { Type::getInt32PtrTy(context) }; - FunctionType *FT1 = FunctionType::get(Type::getVoidTy(context), ArgTy1, false); - - Function *F1 = Function::Create(FT1, Function::ExternalLinkage); - BasicBlock *BB = BasicBlock::Create(context, "", F1); - IRBuilder<> Builder(BB); - Builder.CreateRetVoid(); - - Function *F2 = Function::Create(FT1, Function::ExternalLinkage); - - Argument *A = &*F1->arg_begin(); - A->addAttr(Attribute::NoCapture); - - SmallVector Returns; - ValueToValueMapTy VMap; - VMap[A] = UndefValue::get(A->getType()); - - CloneFunctionInto(F2, F1, VMap, false, Returns); - EXPECT_FALSE(F2->arg_begin()->hasNoCaptureAttr()); - - delete F1; - delete F2; -} - -TEST_F(CloneInstruction, CallingConvention) { - Type *ArgTy1[] = { Type::getInt32PtrTy(context) }; - FunctionType *FT1 = FunctionType::get(Type::getVoidTy(context), ArgTy1, false); - - Function *F1 = Function::Create(FT1, Function::ExternalLinkage); - F1->setCallingConv(CallingConv::Cold); - BasicBlock *BB = BasicBlock::Create(context, "", F1); - IRBuilder<> Builder(BB); - Builder.CreateRetVoid(); - - Function *F2 = Function::Create(FT1, Function::ExternalLinkage); - - SmallVector Returns; - ValueToValueMapTy VMap; - VMap[&*F1->arg_begin()] = &*F2->arg_begin(); - - CloneFunctionInto(F2, F1, VMap, false, Returns); - EXPECT_EQ(CallingConv::Cold, F2->getCallingConv()); - - delete F1; - delete F2; -} - -TEST_F(CloneInstruction, DuplicateInstructionsToSplit) { - Type *ArgTy1[] = {Type::getInt32PtrTy(context)}; - FunctionType *FT = FunctionType::get(Type::getVoidTy(context), ArgTy1, false); - V = new Argument(Type::getInt32Ty(context)); - - Function *F = Function::Create(FT, Function::ExternalLinkage); - - BasicBlock *BB1 = BasicBlock::Create(context, "", F); - IRBuilder<> Builder1(BB1); - - BasicBlock *BB2 = BasicBlock::Create(context, "", F); - IRBuilder<> Builder2(BB2); - - Builder1.CreateBr(BB2); - - Instruction *AddInst = cast(Builder2.CreateAdd(V, V)); - Instruction *MulInst = cast(Builder2.CreateMul(AddInst, V)); - Instruction *SubInst = cast(Builder2.CreateSub(MulInst, V)); - Builder2.CreateRetVoid(); - - ValueToValueMapTy Mapping; - - auto Split = DuplicateInstructionsInSplitBetween(BB2, BB1, SubInst, Mapping); - - EXPECT_TRUE(Split); - EXPECT_EQ(Mapping.size(), 2u); - EXPECT_TRUE(Mapping.find(AddInst) != Mapping.end()); - EXPECT_TRUE(Mapping.find(MulInst) != Mapping.end()); - - auto AddSplit = dyn_cast(Mapping[AddInst]); - EXPECT_TRUE(AddSplit); - EXPECT_EQ(AddSplit->getOperand(0), V); - EXPECT_EQ(AddSplit->getOperand(1), V); - EXPECT_EQ(AddSplit->getParent(), Split); - - auto MulSplit = dyn_cast(Mapping[MulInst]); - EXPECT_TRUE(MulSplit); - EXPECT_EQ(MulSplit->getOperand(0), AddSplit); - EXPECT_EQ(MulSplit->getOperand(1), V); - EXPECT_EQ(MulSplit->getParent(), Split); - - EXPECT_EQ(AddSplit->getNextNode(), MulSplit); - EXPECT_EQ(MulSplit->getNextNode(), Split->getTerminator()); - - delete F; -} - -TEST_F(CloneInstruction, DuplicateInstructionsToSplitBlocksEq1) { - Type *ArgTy1[] = {Type::getInt32PtrTy(context)}; - FunctionType *FT = FunctionType::get(Type::getVoidTy(context), ArgTy1, false); - V = new Argument(Type::getInt32Ty(context)); - - Function *F = Function::Create(FT, Function::ExternalLinkage); - - BasicBlock *BB1 = BasicBlock::Create(context, "", F); - IRBuilder<> Builder1(BB1); - - BasicBlock *BB2 = BasicBlock::Create(context, "", F); - IRBuilder<> Builder2(BB2); - - Builder1.CreateBr(BB2); - - Instruction *AddInst = cast(Builder2.CreateAdd(V, V)); - Instruction *MulInst = cast(Builder2.CreateMul(AddInst, V)); - Instruction *SubInst = cast(Builder2.CreateSub(MulInst, V)); - Builder2.CreateBr(BB2); - - ValueToValueMapTy Mapping; - - auto Split = DuplicateInstructionsInSplitBetween(BB2, BB2, BB2->getTerminator(), Mapping); - - EXPECT_TRUE(Split); - EXPECT_EQ(Mapping.size(), 3u); - EXPECT_TRUE(Mapping.find(AddInst) != Mapping.end()); - EXPECT_TRUE(Mapping.find(MulInst) != Mapping.end()); - EXPECT_TRUE(Mapping.find(SubInst) != Mapping.end()); - - auto AddSplit = dyn_cast(Mapping[AddInst]); - EXPECT_TRUE(AddSplit); - EXPECT_EQ(AddSplit->getOperand(0), V); - EXPECT_EQ(AddSplit->getOperand(1), V); - EXPECT_EQ(AddSplit->getParent(), Split); - - auto MulSplit = dyn_cast(Mapping[MulInst]); - EXPECT_TRUE(MulSplit); - EXPECT_EQ(MulSplit->getOperand(0), AddSplit); - EXPECT_EQ(MulSplit->getOperand(1), V); - EXPECT_EQ(MulSplit->getParent(), Split); - - auto SubSplit = dyn_cast(Mapping[SubInst]); - EXPECT_EQ(MulSplit->getNextNode(), SubSplit); - EXPECT_EQ(SubSplit->getNextNode(), Split->getTerminator()); - EXPECT_EQ(Split->getSingleSuccessor(), BB2); - EXPECT_EQ(BB2->getSingleSuccessor(), Split); - - delete F; -} - -TEST_F(CloneInstruction, DuplicateInstructionsToSplitBlocksEq2) { - Type *ArgTy1[] = {Type::getInt32PtrTy(context)}; - FunctionType *FT = FunctionType::get(Type::getVoidTy(context), ArgTy1, false); - V = new Argument(Type::getInt32Ty(context)); - - Function *F = Function::Create(FT, Function::ExternalLinkage); - - BasicBlock *BB1 = BasicBlock::Create(context, "", F); - IRBuilder<> Builder1(BB1); - - BasicBlock *BB2 = BasicBlock::Create(context, "", F); - IRBuilder<> Builder2(BB2); - - Builder1.CreateBr(BB2); - - Instruction *AddInst = cast(Builder2.CreateAdd(V, V)); - Instruction *MulInst = cast(Builder2.CreateMul(AddInst, V)); - Instruction *SubInst = cast(Builder2.CreateSub(MulInst, V)); - Builder2.CreateBr(BB2); - - ValueToValueMapTy Mapping; - - auto Split = DuplicateInstructionsInSplitBetween(BB2, BB2, SubInst, Mapping); - - EXPECT_TRUE(Split); - EXPECT_EQ(Mapping.size(), 2u); - EXPECT_TRUE(Mapping.find(AddInst) != Mapping.end()); - EXPECT_TRUE(Mapping.find(MulInst) != Mapping.end()); - - auto AddSplit = dyn_cast(Mapping[AddInst]); - EXPECT_TRUE(AddSplit); - EXPECT_EQ(AddSplit->getOperand(0), V); - EXPECT_EQ(AddSplit->getOperand(1), V); - EXPECT_EQ(AddSplit->getParent(), Split); - - auto MulSplit = dyn_cast(Mapping[MulInst]); - EXPECT_TRUE(MulSplit); - EXPECT_EQ(MulSplit->getOperand(0), AddSplit); - EXPECT_EQ(MulSplit->getOperand(1), V); - EXPECT_EQ(MulSplit->getParent(), Split); - EXPECT_EQ(MulSplit->getNextNode(), Split->getTerminator()); - EXPECT_EQ(Split->getSingleSuccessor(), BB2); - EXPECT_EQ(BB2->getSingleSuccessor(), Split); - - delete F; -} - -class CloneFunc : public ::testing::Test { -protected: - void SetUp() override { - SetupModule(); - CreateOldFunc(); - CreateNewFunc(); - SetupFinder(); - } - - void TearDown() override { delete Finder; } - - void SetupModule() { - M = new Module("", C); - } - - void CreateOldFunc() { - FunctionType* FuncType = FunctionType::get(Type::getVoidTy(C), false); - OldFunc = Function::Create(FuncType, GlobalValue::PrivateLinkage, "f", M); - CreateOldFunctionBodyAndDI(); - } - - void CreateOldFunctionBodyAndDI() { - DIBuilder DBuilder(*M); - IRBuilder<> IBuilder(C); - - // Function DI - auto *File = DBuilder.createFile("filename.c", "/file/dir/"); - DITypeRefArray ParamTypes = DBuilder.getOrCreateTypeArray(None); - DISubroutineType *FuncType = - DBuilder.createSubroutineType(ParamTypes); - auto *CU = DBuilder.createCompileUnit(dwarf::DW_LANG_C99, - DBuilder.createFile("filename.c", - "/file/dir"), - "CloneFunc", false, "", 0); - - auto *Subprogram = - DBuilder.createFunction(CU, "f", "f", File, 4, FuncType, true, true, 3, - DINode::FlagZero, false); - OldFunc->setSubprogram(Subprogram); - - // Function body - BasicBlock* Entry = BasicBlock::Create(C, "", OldFunc); - IBuilder.SetInsertPoint(Entry); - DebugLoc Loc = DebugLoc::get(3, 2, Subprogram); - IBuilder.SetCurrentDebugLocation(Loc); - AllocaInst* Alloca = IBuilder.CreateAlloca(IntegerType::getInt32Ty(C)); - IBuilder.SetCurrentDebugLocation(DebugLoc::get(4, 2, Subprogram)); - Value* AllocaContent = IBuilder.getInt32(1); - Instruction* Store = IBuilder.CreateStore(AllocaContent, Alloca); - IBuilder.SetCurrentDebugLocation(DebugLoc::get(5, 2, Subprogram)); - - // Create a local variable around the alloca - auto *IntType = DBuilder.createBasicType("int", 32, dwarf::DW_ATE_signed); - auto *E = DBuilder.createExpression(); - auto *Variable = - DBuilder.createAutoVariable(Subprogram, "x", File, 5, IntType, true); - auto *DL = DILocation::get(Subprogram->getContext(), 5, 0, Subprogram); - DBuilder.insertDeclare(Alloca, Variable, E, DL, Store); - DBuilder.insertDbgValueIntrinsic(AllocaContent, Variable, E, DL, Entry); - // Also create an inlined variable. - // Create a distinct struct type that we should not duplicate during - // cloning). - auto *StructType = DICompositeType::getDistinct( - C, dwarf::DW_TAG_structure_type, "some_struct", nullptr, 0, nullptr, - nullptr, 32, 32, 0, DINode::FlagZero, nullptr, 0, nullptr, nullptr); - auto *InlinedSP = - DBuilder.createFunction(CU, "inlined", "inlined", File, 8, FuncType, - true, true, 9, DINode::FlagZero, false); - auto *InlinedVar = - DBuilder.createAutoVariable(InlinedSP, "inlined", File, 5, StructType, true); - auto *Scope = DBuilder.createLexicalBlock( - DBuilder.createLexicalBlockFile(InlinedSP, File), File, 1, 1); - auto InlinedDL = - DebugLoc::get(9, 4, Scope, DebugLoc::get(5, 2, Subprogram)); - IBuilder.SetCurrentDebugLocation(InlinedDL); - DBuilder.insertDeclare(Alloca, InlinedVar, E, InlinedDL, Store); - IBuilder.CreateStore(IBuilder.getInt32(2), Alloca); - // Finalize the debug info. - DBuilder.finalize(); - IBuilder.CreateRetVoid(); - - // Create another, empty, compile unit. - DIBuilder DBuilder2(*M); - DBuilder2.createCompileUnit(dwarf::DW_LANG_C99, - DBuilder.createFile("extra.c", "/file/dir"), - "CloneFunc", false, "", 0); - DBuilder2.finalize(); - } - - void CreateNewFunc() { - ValueToValueMapTy VMap; - NewFunc = CloneFunction(OldFunc, VMap, nullptr); - } - - void SetupFinder() { - Finder = new DebugInfoFinder(); - Finder->processModule(*M); - } - - LLVMContext C; - Function* OldFunc; - Function* NewFunc; - Module* M; - DebugInfoFinder* Finder; -}; - -// Test that a new, distinct function was created. -TEST_F(CloneFunc, NewFunctionCreated) { - EXPECT_NE(OldFunc, NewFunc); -} - -// Test that a new subprogram entry was added and is pointing to the new -// function, while the original subprogram still points to the old one. -TEST_F(CloneFunc, Subprogram) { - EXPECT_FALSE(verifyModule(*M, &errs())); - EXPECT_EQ(3U, Finder->subprogram_count()); - EXPECT_NE(NewFunc->getSubprogram(), OldFunc->getSubprogram()); -} - -// Test that instructions in the old function still belong to it in the -// metadata, while instruction in the new function belong to the new one. -TEST_F(CloneFunc, InstructionOwnership) { - EXPECT_FALSE(verifyModule(*M)); - - inst_iterator OldIter = inst_begin(OldFunc); - inst_iterator OldEnd = inst_end(OldFunc); - inst_iterator NewIter = inst_begin(NewFunc); - inst_iterator NewEnd = inst_end(NewFunc); - while (OldIter != OldEnd && NewIter != NewEnd) { - Instruction& OldI = *OldIter; - Instruction& NewI = *NewIter; - EXPECT_NE(&OldI, &NewI); - - EXPECT_EQ(OldI.hasMetadata(), NewI.hasMetadata()); - if (OldI.hasMetadata()) { - const DebugLoc& OldDL = OldI.getDebugLoc(); - const DebugLoc& NewDL = NewI.getDebugLoc(); - - // Verify that the debug location data is the same - EXPECT_EQ(OldDL.getLine(), NewDL.getLine()); - EXPECT_EQ(OldDL.getCol(), NewDL.getCol()); - - // But that they belong to different functions - auto *OldSubprogram = cast(OldDL.getInlinedAtScope()); - auto *NewSubprogram = cast(NewDL.getInlinedAtScope()); - EXPECT_EQ(OldFunc->getSubprogram(), OldSubprogram); - EXPECT_EQ(NewFunc->getSubprogram(), NewSubprogram); - } - - ++OldIter; - ++NewIter; - } - EXPECT_EQ(OldEnd, OldIter); - EXPECT_EQ(NewEnd, NewIter); -} - -// Test that the arguments for debug intrinsics in the new function were -// properly cloned -TEST_F(CloneFunc, DebugIntrinsics) { - EXPECT_FALSE(verifyModule(*M)); - - inst_iterator OldIter = inst_begin(OldFunc); - inst_iterator OldEnd = inst_end(OldFunc); - inst_iterator NewIter = inst_begin(NewFunc); - inst_iterator NewEnd = inst_end(NewFunc); - while (OldIter != OldEnd && NewIter != NewEnd) { - Instruction& OldI = *OldIter; - Instruction& NewI = *NewIter; - if (DbgDeclareInst* OldIntrin = dyn_cast(&OldI)) { - DbgDeclareInst* NewIntrin = dyn_cast(&NewI); - EXPECT_TRUE(NewIntrin); - - // Old address must belong to the old function - EXPECT_EQ(OldFunc, cast(OldIntrin->getAddress())-> - getParent()->getParent()); - // New address must belong to the new function - EXPECT_EQ(NewFunc, cast(NewIntrin->getAddress())-> - getParent()->getParent()); - - if (OldIntrin->getDebugLoc()->getInlinedAt()) { - // Inlined variable should refer to the same DILocalVariable as in the - // Old Function - EXPECT_EQ(OldIntrin->getVariable(), NewIntrin->getVariable()); - } else { - // Old variable must belong to the old function. - EXPECT_EQ(OldFunc->getSubprogram(), - cast(OldIntrin->getVariable()->getScope())); - // New variable must belong to the new function. - EXPECT_EQ(NewFunc->getSubprogram(), - cast(NewIntrin->getVariable()->getScope())); - } - } else if (DbgValueInst* OldIntrin = dyn_cast(&OldI)) { - DbgValueInst* NewIntrin = dyn_cast(&NewI); - EXPECT_TRUE(NewIntrin); - - if (!OldIntrin->getDebugLoc()->getInlinedAt()) { - // Old variable must belong to the old function. - EXPECT_EQ(OldFunc->getSubprogram(), - cast(OldIntrin->getVariable()->getScope())); - // New variable must belong to the new function. - EXPECT_EQ(NewFunc->getSubprogram(), - cast(NewIntrin->getVariable()->getScope())); - } - } - - ++OldIter; - ++NewIter; - } -} - -class CloneModule : public ::testing::Test { -protected: - void SetUp() override { - SetupModule(); - CreateOldModule(); - CreateNewModule(); - } - - void SetupModule() { OldM = new Module("", C); } - - void CreateOldModule() { - auto *CD = OldM->getOrInsertComdat("comdat"); - CD->setSelectionKind(Comdat::ExactMatch); - - auto GV = new GlobalVariable( - *OldM, Type::getInt32Ty(C), false, GlobalValue::ExternalLinkage, - ConstantInt::get(Type::getInt32Ty(C), 1), "gv"); - GV->addMetadata(LLVMContext::MD_type, *MDNode::get(C, {})); - GV->setComdat(CD); - - DIBuilder DBuilder(*OldM); - IRBuilder<> IBuilder(C); - - auto *FuncType = FunctionType::get(Type::getVoidTy(C), false); - auto *PersFn = Function::Create(FuncType, GlobalValue::ExternalLinkage, - "persfn", OldM); - auto *F = - Function::Create(FuncType, GlobalValue::PrivateLinkage, "f", OldM); - F->setPersonalityFn(PersFn); - F->setComdat(CD); - - // Create debug info - auto *File = DBuilder.createFile("filename.c", "/file/dir/"); - DITypeRefArray ParamTypes = DBuilder.getOrCreateTypeArray(None); - DISubroutineType *DFuncType = DBuilder.createSubroutineType(ParamTypes); - auto *CU = DBuilder.createCompileUnit(dwarf::DW_LANG_C99, - DBuilder.createFile("filename.c", - "/file/dir"), - "CloneModule", false, "", 0); - // Function DI - auto *Subprogram = - DBuilder.createFunction(CU, "f", "f", File, 4, DFuncType, true, true, 3, - DINode::FlagZero, false); - F->setSubprogram(Subprogram); - - // Create and assign DIGlobalVariableExpression to gv - auto GVExpression = DBuilder.createGlobalVariableExpression( - Subprogram, "gv", "gv", File, 1, DBuilder.createNullPtrType(), false); - GV->addDebugInfo(GVExpression); - - // DIGlobalVariableExpression not attached to any global variable - auto Expr = DBuilder.createExpression( - ArrayRef{dwarf::DW_OP_constu, 42U, dwarf::DW_OP_stack_value}); - - DBuilder.createGlobalVariableExpression( - Subprogram, "unattached", "unattached", File, 1, - DBuilder.createNullPtrType(), false, Expr); - - auto *Entry = BasicBlock::Create(C, "", F); - IBuilder.SetInsertPoint(Entry); - IBuilder.CreateRetVoid(); - - // Finalize the debug info - DBuilder.finalize(); - } - - void CreateNewModule() { NewM = llvm::CloneModule(*OldM).release(); } - - LLVMContext C; - Module *OldM; - Module *NewM; -}; - -TEST_F(CloneModule, Verify) { - EXPECT_FALSE(verifyModule(*NewM)); -} - -TEST_F(CloneModule, OldModuleUnchanged) { - DebugInfoFinder Finder; - Finder.processModule(*OldM); - EXPECT_EQ(1U, Finder.subprogram_count()); -} - -TEST_F(CloneModule, Subprogram) { - Function *NewF = NewM->getFunction("f"); - DISubprogram *SP = NewF->getSubprogram(); - EXPECT_TRUE(SP != nullptr); - EXPECT_EQ(SP->getName(), "f"); - EXPECT_EQ(SP->getFile()->getFilename(), "filename.c"); - EXPECT_EQ(SP->getLine(), (unsigned)4); -} - -TEST_F(CloneModule, GlobalMetadata) { - GlobalVariable *NewGV = NewM->getGlobalVariable("gv"); - EXPECT_NE(nullptr, NewGV->getMetadata(LLVMContext::MD_type)); -} - -TEST_F(CloneModule, GlobalDebugInfo) { - GlobalVariable *NewGV = NewM->getGlobalVariable("gv"); - EXPECT_TRUE(NewGV != nullptr); - - // Find debug info expression assigned to global - SmallVector GVs; - NewGV->getDebugInfo(GVs); - EXPECT_EQ(GVs.size(), 1U); - - DIGlobalVariableExpression *GVExpr = GVs[0]; - DIGlobalVariable *GV = GVExpr->getVariable(); - EXPECT_TRUE(GV != nullptr); - - EXPECT_EQ(GV->getName(), "gv"); - EXPECT_EQ(GV->getLine(), 1U); - - // Assert that the scope of the debug info attached to - // global variable matches the cloned function. - DISubprogram *SP = NewM->getFunction("f")->getSubprogram(); - EXPECT_TRUE(SP != nullptr); - EXPECT_EQ(GV->getScope(), SP); -} - -TEST_F(CloneModule, CompileUnit) { - // Find DICompileUnit listed in llvm.dbg.cu - auto *NMD = NewM->getNamedMetadata("llvm.dbg.cu"); - EXPECT_TRUE(NMD != nullptr); - EXPECT_EQ(NMD->getNumOperands(), 1U); - - DICompileUnit *CU = dyn_cast(NMD->getOperand(0)); - EXPECT_TRUE(CU != nullptr); - - // Assert this CU is consistent with the cloned function debug info - DISubprogram *SP = NewM->getFunction("f")->getSubprogram(); - EXPECT_TRUE(SP != nullptr); - EXPECT_EQ(SP->getUnit(), CU); - - // Check globals listed in CU have the correct scope - DIGlobalVariableExpressionArray GlobalArray = CU->getGlobalVariables(); - EXPECT_EQ(GlobalArray.size(), 2U); - for (DIGlobalVariableExpression *GVExpr : GlobalArray) { - DIGlobalVariable *GV = GVExpr->getVariable(); - EXPECT_EQ(GV->getScope(), SP); - } -} - -TEST_F(CloneModule, Comdat) { - GlobalVariable *NewGV = NewM->getGlobalVariable("gv"); - auto *CD = NewGV->getComdat(); - ASSERT_NE(nullptr, CD); - EXPECT_EQ("comdat", CD->getName()); - EXPECT_EQ(Comdat::ExactMatch, CD->getSelectionKind()); - - Function *NewF = NewM->getFunction("f"); - EXPECT_EQ(CD, NewF->getComdat()); -} -} Index: unittests/Transforms/Utils/CodeExtractor.cpp =================================================================== --- unittests/Transforms/Utils/CodeExtractor.cpp +++ unittests/Transforms/Utils/CodeExtractor.cpp @@ -1,69 +0,0 @@ -//===- CodeExtractor.cpp - Unit tests for CodeExtractor -------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/Utils/CodeExtractor.h" -#include "llvm/AsmParser/Parser.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/Verifier.h" -#include "llvm/IRReader/IRReader.h" -#include "llvm/Support/SourceMgr.h" -#include "gtest/gtest.h" - -using namespace llvm; - -namespace { -TEST(CodeExtractor, ExitStub) { - LLVMContext Ctx; - SMDiagnostic Err; - std::unique_ptr M(parseAssemblyString(R"invalid( - define i32 @foo(i32 %x, i32 %y, i32 %z) { - header: - %0 = icmp ugt i32 %x, %y - br i1 %0, label %body1, label %body2 - - body1: - %1 = add i32 %z, 2 - br label %notExtracted - - body2: - %2 = mul i32 %z, 7 - br label %notExtracted - - notExtracted: - %3 = phi i32 [ %1, %body1 ], [ %2, %body2 ] - %4 = add i32 %3, %x - ret i32 %4 - } - )invalid", - Err, Ctx)); - - Function *Func = M->getFunction("foo"); - SmallVector Candidates; - for (auto &BB : *Func) { - if (BB.getName() == "body1") - Candidates.push_back(&BB); - if (BB.getName() == "body2") - Candidates.push_back(&BB); - } - // CodeExtractor requires the first basic block - // to dominate all the other ones. - Candidates.insert(Candidates.begin(), &Func->getEntryBlock()); - - DominatorTree DT(*Func); - CodeExtractor CE(Candidates, &DT); - EXPECT_TRUE(CE.isEligible()); - - Function *Outlined = CE.extractCodeRegion(); - EXPECT_TRUE(Outlined); - EXPECT_FALSE(verifyFunction(*Outlined)); -} -} // end anonymous namespace Index: unittests/Transforms/Utils/FunctionComparator.cpp =================================================================== --- unittests/Transforms/Utils/FunctionComparator.cpp +++ unittests/Transforms/Utils/FunctionComparator.cpp @@ -1,130 +0,0 @@ -//===- FunctionComparator.cpp - Unit tests for FunctionComparator ---------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -#include "llvm/Transforms/Utils/FunctionComparator.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "gtest/gtest.h" - -using namespace llvm; - -/// Generates a simple test function. -struct TestFunction { - Function *F; - BasicBlock *BB; - Constant *C; - Instruction *I; - Type *T; - - TestFunction(LLVMContext &Ctx, Module &M, int addVal) { - IRBuilder<> B(Ctx); - T = B.getInt8Ty(); - F = Function::Create(FunctionType::get(T, {B.getInt8PtrTy()}, false), - GlobalValue::ExternalLinkage, "F", &M); - BB = BasicBlock::Create(Ctx, "", F); - B.SetInsertPoint(BB); - Argument *PointerArg = &*F->arg_begin(); - LoadInst *LoadInst = B.CreateLoad(PointerArg); - C = B.getInt8(addVal); - I = cast(B.CreateAdd(LoadInst, C)); - B.CreateRet(I); - } -}; - -/// A class for testing the FunctionComparator API. -/// -/// The main purpose is to test if the required protected functions are -/// accessible from a derived class of FunctionComparator. -class TestComparator : public FunctionComparator { -public: - TestComparator(const Function *F1, const Function *F2, - GlobalNumberState *GN) - : FunctionComparator(F1, F2, GN) { - } - - bool testFunctionAccess(const Function *F1, const Function *F2) { - // Test if FnL and FnR are accessible. - return F1 == FnL && F2 == FnR; - } - - int testCompare() { - return compare(); - } - - int testCompareSignature() { - beginCompare(); - return compareSignature(); - } - - int testCmpBasicBlocks(BasicBlock *BBL, BasicBlock *BBR) { - beginCompare(); - return cmpBasicBlocks(BBL, BBR); - } - - int testCmpConstants(const Constant *L, const Constant *R) { - beginCompare(); - return cmpConstants(L, R); - } - - int testCmpGlobalValues(GlobalValue *L, GlobalValue *R) { - beginCompare(); - return cmpGlobalValues(L, R); - } - - int testCmpValues(const Value *L, const Value *R) { - beginCompare(); - return cmpValues(L, R); - } - - int testCmpOperations(const Instruction *L, const Instruction *R, - bool &needToCmpOperands) { - beginCompare(); - return cmpOperations(L, R, needToCmpOperands); - } - - int testCmpTypes(Type *TyL, Type *TyR) { - beginCompare(); - return cmpTypes(TyL, TyR); - } - - int testCmpPrimitives() { - beginCompare(); - return - cmpNumbers(2, 3) + - cmpAPInts(APInt(32, 2), APInt(32, 3)) + - cmpAPFloats(APFloat(2.0), APFloat(3.0)) + - cmpMem("2", "3"); - } -}; - -/// A sanity check for the FunctionComparator API. -TEST(FunctionComparatorTest, TestAPI) { - LLVMContext C; - Module M("test", C); - TestFunction F1(C, M, 27); - TestFunction F2(C, M, 28); - - GlobalNumberState GN; - TestComparator Cmp(F1.F, F2.F, &GN); - - EXPECT_TRUE(Cmp.testFunctionAccess(F1.F, F2.F)); - EXPECT_EQ(Cmp.testCompare(), -1); - EXPECT_EQ(Cmp.testCompareSignature(), 0); - EXPECT_EQ(Cmp.testCmpBasicBlocks(F1.BB, F2.BB), -1); - EXPECT_EQ(Cmp.testCmpConstants(F1.C, F2.C), -1); - EXPECT_EQ(Cmp.testCmpGlobalValues(F1.F, F2.F), -1); - EXPECT_EQ(Cmp.testCmpValues(F1.I, F2.I), 0); - bool needToCmpOperands = false; - EXPECT_EQ(Cmp.testCmpOperations(F1.I, F2.I, needToCmpOperands), 0); - EXPECT_TRUE(needToCmpOperands); - EXPECT_EQ(Cmp.testCmpTypes(F1.T, F2.T), 0); - EXPECT_EQ(Cmp.testCmpPrimitives(), -4); -} Index: unittests/Transforms/Utils/IntegerDivision.cpp =================================================================== --- unittests/Transforms/Utils/IntegerDivision.cpp +++ unittests/Transforms/Utils/IntegerDivision.cpp @@ -1,264 +0,0 @@ -//===- IntegerDivision.cpp - Unit tests for the integer division code -----===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/Utils/IntegerDivision.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/GlobalValue.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Module.h" -#include "gtest/gtest.h" - -using namespace llvm; - -namespace { - - -TEST(IntegerDivision, SDiv) { - LLVMContext C; - Module M("test division", C); - IRBuilder<> Builder(C); - - SmallVector ArgTys(2, Builder.getInt32Ty()); - Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(), - ArgTys, false), - GlobalValue::ExternalLinkage, "F", &M); - assert(F->arg_size() == 2); - - BasicBlock *BB = BasicBlock::Create(C, "", F); - Builder.SetInsertPoint(BB); - - Function::arg_iterator AI = F->arg_begin(); - Value *A = &*AI++; - Value *B = &*AI++; - - Value *Div = Builder.CreateSDiv(A, B); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::SDiv); - - Value *Ret = Builder.CreateRet(Div); - - expandDivision(cast(Div)); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr); - - Instruction* Quotient = dyn_cast(cast(Ret)->getOperand(0)); - EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::Sub); -} - -TEST(IntegerDivision, UDiv) { - LLVMContext C; - Module M("test division", C); - IRBuilder<> Builder(C); - - SmallVector ArgTys(2, Builder.getInt32Ty()); - Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(), - ArgTys, false), - GlobalValue::ExternalLinkage, "F", &M); - assert(F->arg_size() == 2); - - BasicBlock *BB = BasicBlock::Create(C, "", F); - Builder.SetInsertPoint(BB); - - Function::arg_iterator AI = F->arg_begin(); - Value *A = &*AI++; - Value *B = &*AI++; - - Value *Div = Builder.CreateUDiv(A, B); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::UDiv); - - Value *Ret = Builder.CreateRet(Div); - - expandDivision(cast(Div)); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp); - - Instruction* Quotient = dyn_cast(cast(Ret)->getOperand(0)); - EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::PHI); -} - -TEST(IntegerDivision, SRem) { - LLVMContext C; - Module M("test remainder", C); - IRBuilder<> Builder(C); - - SmallVector ArgTys(2, Builder.getInt32Ty()); - Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(), - ArgTys, false), - GlobalValue::ExternalLinkage, "F", &M); - assert(F->arg_size() == 2); - - BasicBlock *BB = BasicBlock::Create(C, "", F); - Builder.SetInsertPoint(BB); - - Function::arg_iterator AI = F->arg_begin(); - Value *A = &*AI++; - Value *B = &*AI++; - - Value *Rem = Builder.CreateSRem(A, B); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::SRem); - - Value *Ret = Builder.CreateRet(Rem); - - expandRemainder(cast(Rem)); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr); - - Instruction* Remainder = dyn_cast(cast(Ret)->getOperand(0)); - EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub); -} - -TEST(IntegerDivision, URem) { - LLVMContext C; - Module M("test remainder", C); - IRBuilder<> Builder(C); - - SmallVector ArgTys(2, Builder.getInt32Ty()); - Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(), - ArgTys, false), - GlobalValue::ExternalLinkage, "F", &M); - assert(F->arg_size() == 2); - - BasicBlock *BB = BasicBlock::Create(C, "", F); - Builder.SetInsertPoint(BB); - - Function::arg_iterator AI = F->arg_begin(); - Value *A = &*AI++; - Value *B = &*AI++; - - Value *Rem = Builder.CreateURem(A, B); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::URem); - - Value *Ret = Builder.CreateRet(Rem); - - expandRemainder(cast(Rem)); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp); - - Instruction* Remainder = dyn_cast(cast(Ret)->getOperand(0)); - EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub); -} - - -TEST(IntegerDivision, SDiv64) { - LLVMContext C; - Module M("test division", C); - IRBuilder<> Builder(C); - - SmallVector ArgTys(2, Builder.getInt64Ty()); - Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(), - ArgTys, false), - GlobalValue::ExternalLinkage, "F", &M); - assert(F->arg_size() == 2); - - BasicBlock *BB = BasicBlock::Create(C, "", F); - Builder.SetInsertPoint(BB); - - Function::arg_iterator AI = F->arg_begin(); - Value *A = &*AI++; - Value *B = &*AI++; - - Value *Div = Builder.CreateSDiv(A, B); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::SDiv); - - Value *Ret = Builder.CreateRet(Div); - - expandDivision(cast(Div)); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr); - - Instruction* Quotient = dyn_cast(cast(Ret)->getOperand(0)); - EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::Sub); -} - -TEST(IntegerDivision, UDiv64) { - LLVMContext C; - Module M("test division", C); - IRBuilder<> Builder(C); - - SmallVector ArgTys(2, Builder.getInt64Ty()); - Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(), - ArgTys, false), - GlobalValue::ExternalLinkage, "F", &M); - assert(F->arg_size() == 2); - - BasicBlock *BB = BasicBlock::Create(C, "", F); - Builder.SetInsertPoint(BB); - - Function::arg_iterator AI = F->arg_begin(); - Value *A = &*AI++; - Value *B = &*AI++; - - Value *Div = Builder.CreateUDiv(A, B); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::UDiv); - - Value *Ret = Builder.CreateRet(Div); - - expandDivision(cast(Div)); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp); - - Instruction* Quotient = dyn_cast(cast(Ret)->getOperand(0)); - EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::PHI); -} - -TEST(IntegerDivision, SRem64) { - LLVMContext C; - Module M("test remainder", C); - IRBuilder<> Builder(C); - - SmallVector ArgTys(2, Builder.getInt64Ty()); - Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(), - ArgTys, false), - GlobalValue::ExternalLinkage, "F", &M); - assert(F->arg_size() == 2); - - BasicBlock *BB = BasicBlock::Create(C, "", F); - Builder.SetInsertPoint(BB); - - Function::arg_iterator AI = F->arg_begin(); - Value *A = &*AI++; - Value *B = &*AI++; - - Value *Rem = Builder.CreateSRem(A, B); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::SRem); - - Value *Ret = Builder.CreateRet(Rem); - - expandRemainder(cast(Rem)); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr); - - Instruction* Remainder = dyn_cast(cast(Ret)->getOperand(0)); - EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub); -} - -TEST(IntegerDivision, URem64) { - LLVMContext C; - Module M("test remainder", C); - IRBuilder<> Builder(C); - - SmallVector ArgTys(2, Builder.getInt64Ty()); - Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(), - ArgTys, false), - GlobalValue::ExternalLinkage, "F", &M); - assert(F->arg_size() == 2); - - BasicBlock *BB = BasicBlock::Create(C, "", F); - Builder.SetInsertPoint(BB); - - Function::arg_iterator AI = F->arg_begin(); - Value *A = &*AI++; - Value *B = &*AI++; - - Value *Rem = Builder.CreateURem(A, B); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::URem); - - Value *Ret = Builder.CreateRet(Rem); - - expandRemainder(cast(Rem)); - EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp); - - Instruction* Remainder = dyn_cast(cast(Ret)->getOperand(0)); - EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub); -} - -} Index: unittests/Transforms/Utils/Local.cpp =================================================================== --- unittests/Transforms/Utils/Local.cpp +++ unittests/Transforms/Utils/Local.cpp @@ -1,914 +0,0 @@ -//===- Local.cpp - Unit tests for Local -----------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/Utils/Local.h" -#include "llvm/Analysis/PostDominators.h" -#include "llvm/AsmParser/Parser.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/DIBuilder.h" -#include "llvm/IR/DomTreeUpdater.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/IntrinsicInst.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Verifier.h" -#include "llvm/Support/SourceMgr.h" -#include "gtest/gtest.h" - -using namespace llvm; - -TEST(Local, RecursivelyDeleteDeadPHINodes) { - LLVMContext C; - - IRBuilder<> builder(C); - - // Make blocks - BasicBlock *bb0 = BasicBlock::Create(C); - BasicBlock *bb1 = BasicBlock::Create(C); - - builder.SetInsertPoint(bb0); - PHINode *phi = builder.CreatePHI(Type::getInt32Ty(C), 2); - BranchInst *br0 = builder.CreateCondBr(builder.getTrue(), bb0, bb1); - - builder.SetInsertPoint(bb1); - BranchInst *br1 = builder.CreateBr(bb0); - - phi->addIncoming(phi, bb0); - phi->addIncoming(phi, bb1); - - // The PHI will be removed - EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi)); - - // Make sure the blocks only contain the branches - EXPECT_EQ(&bb0->front(), br0); - EXPECT_EQ(&bb1->front(), br1); - - builder.SetInsertPoint(bb0); - phi = builder.CreatePHI(Type::getInt32Ty(C), 0); - - EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi)); - - builder.SetInsertPoint(bb0); - phi = builder.CreatePHI(Type::getInt32Ty(C), 0); - builder.CreateAdd(phi, phi); - - EXPECT_TRUE(RecursivelyDeleteDeadPHINode(phi)); - - bb0->dropAllReferences(); - bb1->dropAllReferences(); - delete bb0; - delete bb1; -} - -TEST(Local, RemoveDuplicatePHINodes) { - LLVMContext C; - IRBuilder<> B(C); - - std::unique_ptr F( - Function::Create(FunctionType::get(B.getVoidTy(), false), - GlobalValue::ExternalLinkage, "F")); - BasicBlock *Entry(BasicBlock::Create(C, "", F.get())); - BasicBlock *BB(BasicBlock::Create(C, "", F.get())); - BranchInst::Create(BB, Entry); - - B.SetInsertPoint(BB); - - AssertingVH P1 = B.CreatePHI(Type::getInt32Ty(C), 2); - P1->addIncoming(B.getInt32(42), Entry); - - PHINode *P2 = B.CreatePHI(Type::getInt32Ty(C), 2); - P2->addIncoming(B.getInt32(42), Entry); - - AssertingVH P3 = B.CreatePHI(Type::getInt32Ty(C), 2); - P3->addIncoming(B.getInt32(42), Entry); - P3->addIncoming(B.getInt32(23), BB); - - PHINode *P4 = B.CreatePHI(Type::getInt32Ty(C), 2); - P4->addIncoming(B.getInt32(42), Entry); - P4->addIncoming(B.getInt32(23), BB); - - P1->addIncoming(P3, BB); - P2->addIncoming(P4, BB); - BranchInst::Create(BB, BB); - - // Verify that we can eliminate PHIs that become duplicates after chaning PHIs - // downstream. - EXPECT_TRUE(EliminateDuplicatePHINodes(BB)); - EXPECT_EQ(3U, BB->size()); -} - -static std::unique_ptr parseIR(LLVMContext &C, const char *IR) { - SMDiagnostic Err; - std::unique_ptr Mod = parseAssemblyString(IR, Err, C); - if (!Mod) - Err.print("UtilsTests", errs()); - return Mod; -} - -TEST(Local, ReplaceDbgDeclare) { - LLVMContext C; - - // Original C source to get debug info for a local variable: - // void f() { int x; } - std::unique_ptr M = parseIR(C, - R"( - define void @f() !dbg !8 { - entry: - %x = alloca i32, align 4 - call void @llvm.dbg.declare(metadata i32* %x, metadata !11, metadata !DIExpression()), !dbg !13 - call void @llvm.dbg.declare(metadata i32* %x, metadata !11, metadata !DIExpression()), !dbg !13 - ret void, !dbg !14 - } - declare void @llvm.dbg.declare(metadata, metadata, metadata) - !llvm.dbg.cu = !{!0} - !llvm.module.flags = !{!3, !4} - !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 6.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2) - !1 = !DIFile(filename: "t2.c", directory: "foo") - !2 = !{} - !3 = !{i32 2, !"Dwarf Version", i32 4} - !4 = !{i32 2, !"Debug Info Version", i32 3} - !8 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 1, type: !9, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: false, unit: !0, retainedNodes: !2) - !9 = !DISubroutineType(types: !10) - !10 = !{null} - !11 = !DILocalVariable(name: "x", scope: !8, file: !1, line: 2, type: !12) - !12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) - !13 = !DILocation(line: 2, column: 7, scope: !8) - !14 = !DILocation(line: 3, column: 1, scope: !8) - )"); - auto *GV = M->getNamedValue("f"); - ASSERT_TRUE(GV); - auto *F = dyn_cast(GV); - ASSERT_TRUE(F); - Instruction *Inst = &F->front().front(); - auto *AI = dyn_cast(Inst); - ASSERT_TRUE(AI); - Inst = Inst->getNextNode()->getNextNode(); - ASSERT_TRUE(Inst); - auto *DII = dyn_cast(Inst); - ASSERT_TRUE(DII); - Value *NewBase = Constant::getNullValue(Type::getInt32PtrTy(C)); - DIBuilder DIB(*M); - replaceDbgDeclare(AI, NewBase, DII, DIB, DIExpression::NoDeref, 0, - DIExpression::NoDeref); - - // There should be exactly two dbg.declares. - int Declares = 0; - for (const Instruction &I : F->front()) - if (isa(I)) - Declares++; - EXPECT_EQ(2, Declares); -} - -/// Build the dominator tree for the function and run the Test. -static void runWithDomTree( - Module &M, StringRef FuncName, - function_ref Test) { - auto *F = M.getFunction(FuncName); - ASSERT_NE(F, nullptr) << "Could not find " << FuncName; - // Compute the dominator tree for the function. - DominatorTree DT(*F); - Test(*F, &DT); -} - -TEST(Local, MergeBasicBlockIntoOnlyPred) { - LLVMContext C; - std::unique_ptr M; - auto resetIR = [&]() { - M = parseIR(C, - R"( - define i32 @f(i8* %str) { - entry: - br label %bb2.i - bb2.i: ; preds = %bb4.i, %entry - br i1 false, label %bb4.i, label %base2flt.exit204 - bb4.i: ; preds = %bb2.i - br i1 false, label %base2flt.exit204, label %bb2.i - bb10.i196.bb7.i197_crit_edge: ; No predecessors! - br label %bb7.i197 - bb7.i197: ; preds = %bb10.i196.bb7.i197_crit_edge - %.reg2mem.0 = phi i32 [ %.reg2mem.0, %bb10.i196.bb7.i197_crit_edge ] - br i1 undef, label %base2flt.exit204, label %base2flt.exit204 - base2flt.exit204: ; preds = %bb7.i197, %bb7.i197, %bb2.i, %bb4.i - ret i32 0 - } - )"); - }; - - auto resetIRReplaceEntry = [&]() { - M = parseIR(C, - R"( - define i32 @f() { - entry: - br label %bb2.i - bb2.i: ; preds = %entry - ret i32 0 - } - )"); - }; - - auto Test = [&](Function &F, DomTreeUpdater &DTU) { - for (Function::iterator I = F.begin(), E = F.end(); I != E;) { - BasicBlock *BB = &*I++; - BasicBlock *SinglePred = BB->getSinglePredecessor(); - if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) - continue; - BranchInst *Term = dyn_cast(SinglePred->getTerminator()); - if (Term && !Term->isConditional()) - MergeBasicBlockIntoOnlyPred(BB, &DTU); - } - if (DTU.hasDomTree()) - EXPECT_TRUE(DTU.getDomTree().verify()); - if (DTU.hasPostDomTree()) - EXPECT_TRUE(DTU.getPostDomTree().verify()); - }; - - // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with - // both DT and PDT. - resetIR(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with - // DT. - resetIR(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with - // PDT. - resetIR(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Eager); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with - // both DT and PDT. - resetIR(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with - // PDT. - resetIR(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Lazy); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with DT. - resetIR(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with - // both DT and PDT. - resetIRReplaceEntry(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with - // DT. - resetIRReplaceEntry(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Eager); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Eager UpdateStrategy with - // PDT. - resetIRReplaceEntry(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Eager); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with - // both DT and PDT. - resetIRReplaceEntry(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with - // PDT. - resetIRReplaceEntry(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(PDT, DomTreeUpdater::UpdateStrategy::Lazy); - Test(F, DTU); - }); - - // Test MergeBasicBlockIntoOnlyPred working under Lazy UpdateStrategy with DT. - resetIRReplaceEntry(); - runWithDomTree(*M, "f", [&](Function &F, DominatorTree *DT) { - DomTreeUpdater DTU(*DT, DomTreeUpdater::UpdateStrategy::Lazy); - Test(F, DTU); - }); -} - -TEST(Local, ConstantFoldTerminator) { - LLVMContext C; - - std::unique_ptr M = parseIR(C, - R"( - define void @br_same_dest() { - entry: - br i1 false, label %bb0, label %bb0 - bb0: - ret void - } - - define void @br_different_dest() { - entry: - br i1 true, label %bb0, label %bb1 - bb0: - br label %exit - bb1: - br label %exit - exit: - ret void - } - - define void @switch_2_different_dest() { - entry: - switch i32 0, label %default [ i32 0, label %bb0 ] - default: - ret void - bb0: - ret void - } - define void @switch_2_different_dest_default() { - entry: - switch i32 1, label %default [ i32 0, label %bb0 ] - default: - ret void - bb0: - ret void - } - define void @switch_3_different_dest() { - entry: - switch i32 0, label %default [ i32 0, label %bb0 - i32 1, label %bb1 ] - default: - ret void - bb0: - ret void - bb1: - ret void - } - - define void @switch_variable_2_default_dest(i32 %arg) { - entry: - switch i32 %arg, label %default [ i32 0, label %default ] - default: - ret void - } - - define void @switch_constant_2_default_dest() { - entry: - switch i32 1, label %default [ i32 0, label %default ] - default: - ret void - } - - define void @switch_constant_3_repeated_dest() { - entry: - switch i32 0, label %default [ i32 0, label %bb0 - i32 1, label %bb0 ] - bb0: - ret void - default: - ret void - } - - define void @indirectbr() { - entry: - indirectbr i8* blockaddress(@indirectbr, %bb0), [label %bb0, label %bb1] - bb0: - ret void - bb1: - ret void - } - - define void @indirectbr_repeated() { - entry: - indirectbr i8* blockaddress(@indirectbr_repeated, %bb0), [label %bb0, label %bb0] - bb0: - ret void - } - - define void @indirectbr_unreachable() { - entry: - indirectbr i8* blockaddress(@indirectbr_unreachable, %bb0), [label %bb1] - bb0: - ret void - bb1: - ret void - } - )"); - - auto CFAllTerminatorsEager = [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); - for (Function::iterator I = F.begin(), E = F.end(); I != E;) { - BasicBlock *BB = &*I++; - ConstantFoldTerminator(BB, true, nullptr, &DTU); - } - - EXPECT_TRUE(DTU.getDomTree().verify()); - EXPECT_TRUE(DTU.getPostDomTree().verify()); - }; - - auto CFAllTerminatorsLazy = [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); - for (Function::iterator I = F.begin(), E = F.end(); I != E;) { - BasicBlock *BB = &*I++; - ConstantFoldTerminator(BB, true, nullptr, &DTU); - } - - EXPECT_TRUE(DTU.getDomTree().verify()); - EXPECT_TRUE(DTU.getPostDomTree().verify()); - }; - - // Test ConstantFoldTerminator under Eager UpdateStrategy. - runWithDomTree(*M, "br_same_dest", CFAllTerminatorsEager); - runWithDomTree(*M, "br_different_dest", CFAllTerminatorsEager); - runWithDomTree(*M, "switch_2_different_dest", CFAllTerminatorsEager); - runWithDomTree(*M, "switch_2_different_dest_default", CFAllTerminatorsEager); - runWithDomTree(*M, "switch_3_different_dest", CFAllTerminatorsEager); - runWithDomTree(*M, "switch_variable_2_default_dest", CFAllTerminatorsEager); - runWithDomTree(*M, "switch_constant_2_default_dest", CFAllTerminatorsEager); - runWithDomTree(*M, "switch_constant_3_repeated_dest", CFAllTerminatorsEager); - runWithDomTree(*M, "indirectbr", CFAllTerminatorsEager); - runWithDomTree(*M, "indirectbr_repeated", CFAllTerminatorsEager); - runWithDomTree(*M, "indirectbr_unreachable", CFAllTerminatorsEager); - - // Test ConstantFoldTerminator under Lazy UpdateStrategy. - runWithDomTree(*M, "br_same_dest", CFAllTerminatorsLazy); - runWithDomTree(*M, "br_different_dest", CFAllTerminatorsLazy); - runWithDomTree(*M, "switch_2_different_dest", CFAllTerminatorsLazy); - runWithDomTree(*M, "switch_2_different_dest_default", CFAllTerminatorsLazy); - runWithDomTree(*M, "switch_3_different_dest", CFAllTerminatorsLazy); - runWithDomTree(*M, "switch_variable_2_default_dest", CFAllTerminatorsLazy); - runWithDomTree(*M, "switch_constant_2_default_dest", CFAllTerminatorsLazy); - runWithDomTree(*M, "switch_constant_3_repeated_dest", CFAllTerminatorsLazy); - runWithDomTree(*M, "indirectbr", CFAllTerminatorsLazy); - runWithDomTree(*M, "indirectbr_repeated", CFAllTerminatorsLazy); - runWithDomTree(*M, "indirectbr_unreachable", CFAllTerminatorsLazy); -} - -struct SalvageDebugInfoTest : ::testing::Test { - LLVMContext C; - std::unique_ptr M; - Function *F = nullptr; - - void SetUp() { - M = parseIR(C, - R"( - define void @f() !dbg !8 { - entry: - %x = add i32 0, 1 - %y = add i32 %x, 2 - call void @llvm.dbg.value(metadata i32 %x, metadata !11, metadata !DIExpression()), !dbg !13 - call void @llvm.dbg.value(metadata i32 %y, metadata !11, metadata !DIExpression()), !dbg !13 - ret void, !dbg !14 - } - declare void @llvm.dbg.value(metadata, metadata, metadata) - !llvm.dbg.cu = !{!0} - !llvm.module.flags = !{!3, !4} - !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 6.0.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2) - !1 = !DIFile(filename: "t2.c", directory: "foo") - !2 = !{} - !3 = !{i32 2, !"Dwarf Version", i32 4} - !4 = !{i32 2, !"Debug Info Version", i32 3} - !8 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 1, type: !9, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: false, unit: !0, retainedNodes: !2) - !9 = !DISubroutineType(types: !10) - !10 = !{null} - !11 = !DILocalVariable(name: "x", scope: !8, file: !1, line: 2, type: !12) - !12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) - !13 = !DILocation(line: 2, column: 7, scope: !8) - !14 = !DILocation(line: 3, column: 1, scope: !8) - )"); - - auto *GV = M->getNamedValue("f"); - ASSERT_TRUE(GV); - F = dyn_cast(GV); - ASSERT_TRUE(F); - } - - bool doesDebugValueDescribeX(const DbgValueInst &DI) { - const auto &CI = *cast(DI.getValue()); - if (CI.isZero()) - return DI.getExpression()->getElements().equals( - {dwarf::DW_OP_plus_uconst, 1, dwarf::DW_OP_stack_value}); - else if (CI.isOneValue()) - return DI.getExpression()->getElements().empty(); - return false; - } - - bool doesDebugValueDescribeY(const DbgValueInst &DI) { - const auto &CI = *cast(DI.getValue()); - if (CI.isZero()) - return DI.getExpression()->getElements().equals( - {dwarf::DW_OP_plus_uconst, 1, dwarf::DW_OP_plus_uconst, 2, - dwarf::DW_OP_stack_value}); - else if (CI.isOneValue()) - return DI.getExpression()->getElements().equals( - {dwarf::DW_OP_plus_uconst, 2, dwarf::DW_OP_stack_value}); - return false; - } - - void verifyDebugValuesAreSalvaged() { - // Check that the debug values for %x and %y are preserved. - bool FoundX = false; - bool FoundY = false; - for (const Instruction &I : F->front()) { - auto DI = dyn_cast(&I); - if (!DI) { - // The function should only contain debug values and a terminator. - ASSERT_TRUE(I.isTerminator()); - continue; - } - EXPECT_EQ(DI->getVariable()->getName(), "x"); - FoundX |= doesDebugValueDescribeX(*DI); - FoundY |= doesDebugValueDescribeY(*DI); - } - ASSERT_TRUE(FoundX); - ASSERT_TRUE(FoundY); - } -}; - -TEST_F(SalvageDebugInfoTest, RecursiveInstDeletion) { - Instruction *Inst = &F->front().front(); - Inst = Inst->getNextNode(); // Get %y = add ... - ASSERT_TRUE(Inst); - bool Deleted = RecursivelyDeleteTriviallyDeadInstructions(Inst); - ASSERT_TRUE(Deleted); - verifyDebugValuesAreSalvaged(); -} - -TEST_F(SalvageDebugInfoTest, RecursiveBlockSimplification) { - BasicBlock *BB = &F->front(); - ASSERT_TRUE(BB); - bool Deleted = SimplifyInstructionsInBlock(BB); - ASSERT_TRUE(Deleted); - verifyDebugValuesAreSalvaged(); -} - -TEST(Local, ChangeToUnreachable) { - LLVMContext Ctx; - - std::unique_ptr M = parseIR(Ctx, - R"( - define internal void @foo() !dbg !6 { - entry: - ret void, !dbg !8 - } - - !llvm.dbg.cu = !{!0} - !llvm.debugify = !{!3, !4} - !llvm.module.flags = !{!5} - - !0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2) - !1 = !DIFile(filename: "test.ll", directory: "/") - !2 = !{} - !3 = !{i32 1} - !4 = !{i32 0} - !5 = !{i32 2, !"Debug Info Version", i32 3} - !6 = distinct !DISubprogram(name: "foo", linkageName: "foo", scope: null, file: !1, line: 1, type: !7, isLocal: true, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !0, retainedNodes: !2) - !7 = !DISubroutineType(types: !2) - !8 = !DILocation(line: 1, column: 1, scope: !6) - )"); - - bool BrokenDebugInfo = true; - verifyModule(*M, &errs(), &BrokenDebugInfo); - ASSERT_FALSE(BrokenDebugInfo); - - Function &F = *cast(M->getNamedValue("foo")); - - BasicBlock &BB = F.front(); - Instruction &A = BB.front(); - DebugLoc DLA = A.getDebugLoc(); - - ASSERT_TRUE(isa(&A)); - // One instruction should be affected. - EXPECT_EQ(changeToUnreachable(&A, /*UseLLVMTrap*/false), 1U); - - Instruction &B = BB.front(); - - // There should be an uncreachable instruction. - ASSERT_TRUE(isa(&B)); - - DebugLoc DLB = B.getDebugLoc(); - EXPECT_EQ(DLA, DLB); -} - -TEST(Local, ReplaceAllDbgUsesWith) { - using namespace llvm::dwarf; - - LLVMContext Ctx; - - // Note: The datalayout simulates Darwin/x86_64. - std::unique_ptr M = parseIR(Ctx, - R"( - target datalayout = "e-m:o-i63:64-f80:128-n8:16:32:64-S128" - - declare i32 @escape(i32) - - define void @f() !dbg !6 { - entry: - %a = add i32 0, 1, !dbg !15 - call void @llvm.dbg.value(metadata i32 %a, metadata !9, metadata !DIExpression()), !dbg !15 - - %b = add i64 0, 1, !dbg !16 - call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression()), !dbg !16 - call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul)), !dbg !16 - call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul, DW_OP_stack_value)), !dbg !16 - call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 8)), !dbg !16 - call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul, DW_OP_LLVM_fragment, 0, 8)), !dbg !16 - call void @llvm.dbg.value(metadata i64 %b, metadata !11, metadata !DIExpression(DW_OP_lit0, DW_OP_mul, DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8)), !dbg !16 - - %c = inttoptr i64 0 to i64*, !dbg !17 - call void @llvm.dbg.declare(metadata i64* %c, metadata !13, metadata !DIExpression()), !dbg !17 - - %d = inttoptr i64 0 to i32*, !dbg !18 - call void @llvm.dbg.addr(metadata i32* %d, metadata !20, metadata !DIExpression()), !dbg !18 - - %e = add <2 x i16> zeroinitializer, zeroinitializer - call void @llvm.dbg.value(metadata <2 x i16> %e, metadata !14, metadata !DIExpression()), !dbg !18 - - %f = call i32 @escape(i32 0) - call void @llvm.dbg.value(metadata i32 %f, metadata !9, metadata !DIExpression()), !dbg !15 - - %barrier = call i32 @escape(i32 0) - - %g = call i32 @escape(i32 %f) - call void @llvm.dbg.value(metadata i32 %g, metadata !9, metadata !DIExpression()), !dbg !15 - - ret void, !dbg !19 - } - - declare void @llvm.dbg.addr(metadata, metadata, metadata) - declare void @llvm.dbg.declare(metadata, metadata, metadata) - declare void @llvm.dbg.value(metadata, metadata, metadata) - - !llvm.dbg.cu = !{!0} - !llvm.module.flags = !{!5} - - !0 = distinct !DICompileUnit(language: DW_LANG_C, file: !1, producer: "debugify", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2) - !1 = !DIFile(filename: "/Users/vsk/Desktop/foo.ll", directory: "/") - !2 = !{} - !5 = !{i32 2, !"Debug Info Version", i32 3} - !6 = distinct !DISubprogram(name: "f", linkageName: "f", scope: null, file: !1, line: 1, type: !7, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !0, retainedNodes: !8) - !7 = !DISubroutineType(types: !2) - !8 = !{!9, !11, !13, !14} - !9 = !DILocalVariable(name: "1", scope: !6, file: !1, line: 1, type: !10) - !10 = !DIBasicType(name: "ty32", size: 32, encoding: DW_ATE_signed) - !11 = !DILocalVariable(name: "2", scope: !6, file: !1, line: 2, type: !12) - !12 = !DIBasicType(name: "ty64", size: 64, encoding: DW_ATE_signed) - !13 = !DILocalVariable(name: "3", scope: !6, file: !1, line: 3, type: !12) - !14 = !DILocalVariable(name: "4", scope: !6, file: !1, line: 4, type: !10) - !15 = !DILocation(line: 1, column: 1, scope: !6) - !16 = !DILocation(line: 2, column: 1, scope: !6) - !17 = !DILocation(line: 3, column: 1, scope: !6) - !18 = !DILocation(line: 4, column: 1, scope: !6) - !19 = !DILocation(line: 5, column: 1, scope: !6) - !20 = !DILocalVariable(name: "5", scope: !6, file: !1, line: 5, type: !10) - )"); - - bool BrokenDebugInfo = true; - verifyModule(*M, &errs(), &BrokenDebugInfo); - ASSERT_FALSE(BrokenDebugInfo); - - Function &F = *cast(M->getNamedValue("f")); - DominatorTree DT{F}; - - BasicBlock &BB = F.front(); - Instruction &A = BB.front(); - Instruction &B = *A.getNextNonDebugInstruction(); - Instruction &C = *B.getNextNonDebugInstruction(); - Instruction &D = *C.getNextNonDebugInstruction(); - Instruction &E = *D.getNextNonDebugInstruction(); - Instruction &F_ = *E.getNextNonDebugInstruction(); - Instruction &Barrier = *F_.getNextNonDebugInstruction(); - Instruction &G = *Barrier.getNextNonDebugInstruction(); - - // Simulate i32 <-> i64* conversion. Expect no updates: the datalayout says - // pointers are 64 bits, so the conversion would be lossy. - EXPECT_FALSE(replaceAllDbgUsesWith(A, C, C, DT)); - EXPECT_FALSE(replaceAllDbgUsesWith(C, A, A, DT)); - - // Simulate i32 <-> <2 x i16> conversion. This is unsupported. - EXPECT_FALSE(replaceAllDbgUsesWith(E, A, A, DT)); - EXPECT_FALSE(replaceAllDbgUsesWith(A, E, E, DT)); - - // Simulate i32* <-> i64* conversion. - EXPECT_TRUE(replaceAllDbgUsesWith(D, C, C, DT)); - - SmallVector CDbgVals; - findDbgUsers(CDbgVals, &C); - EXPECT_EQ(2U, CDbgVals.size()); - EXPECT_TRUE(any_of(CDbgVals, [](DbgVariableIntrinsic *DII) { - return isa(DII); - })); - EXPECT_TRUE(any_of(CDbgVals, [](DbgVariableIntrinsic *DII) { - return isa(DII); - })); - - EXPECT_TRUE(replaceAllDbgUsesWith(C, D, D, DT)); - - SmallVector DDbgVals; - findDbgUsers(DDbgVals, &D); - EXPECT_EQ(2U, DDbgVals.size()); - EXPECT_TRUE(any_of(DDbgVals, [](DbgVariableIntrinsic *DII) { - return isa(DII); - })); - EXPECT_TRUE(any_of(DDbgVals, [](DbgVariableIntrinsic *DII) { - return isa(DII); - })); - - // Introduce a use-before-def. Check that the dbg.value for %a is salvaged. - EXPECT_TRUE(replaceAllDbgUsesWith(A, F_, F_, DT)); - - auto *ADbgVal = cast(A.getNextNode()); - EXPECT_EQ(ConstantInt::get(A.getType(), 0), ADbgVal->getVariableLocation()); - - // Introduce a use-before-def. Check that the dbg.values for %f are deleted. - EXPECT_TRUE(replaceAllDbgUsesWith(F_, G, G, DT)); - - SmallVector FDbgVals; - findDbgValues(FDbgVals, &F); - EXPECT_EQ(0U, FDbgVals.size()); - - // Simulate i32 -> i64 conversion to test sign-extension. Here are some - // interesting cases to handle: - // 1) debug user has empty DIExpression - // 2) debug user has non-empty, non-stack-value'd DIExpression - // 3) debug user has non-empty, stack-value'd DIExpression - // 4-6) like (1-3), but with a fragment - EXPECT_TRUE(replaceAllDbgUsesWith(B, A, A, DT)); - - SmallVector ADbgVals; - findDbgValues(ADbgVals, &A); - EXPECT_EQ(6U, ADbgVals.size()); - - // Check that %a has a dbg.value with a DIExpression matching \p Ops. - auto hasADbgVal = [&](ArrayRef Ops) { - return any_of(ADbgVals, [&](DbgValueInst *DVI) { - assert(DVI->getVariable()->getName() == "2"); - return DVI->getExpression()->getElements() == Ops; - }); - }; - - // Case 1: The original expr is empty, so no deref is needed. - EXPECT_TRUE(hasADbgVal({DW_OP_dup, DW_OP_constu, 31, DW_OP_shr, DW_OP_lit0, - DW_OP_not, DW_OP_mul, DW_OP_or, DW_OP_stack_value})); - - // Case 2: Perform an address calculation with the original expr, deref it, - // then sign-extend the result. - EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_deref, DW_OP_dup, - DW_OP_constu, 31, DW_OP_shr, DW_OP_lit0, DW_OP_not, - DW_OP_mul, DW_OP_or, DW_OP_stack_value})); - - // Case 3: Insert the sign-extension logic before the DW_OP_stack_value. - EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_dup, DW_OP_constu, 31, - DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_or, - DW_OP_stack_value})); - - // Cases 4-6: Just like cases 1-3, but preserve the fragment at the end. - EXPECT_TRUE(hasADbgVal({DW_OP_dup, DW_OP_constu, 31, DW_OP_shr, DW_OP_lit0, - DW_OP_not, DW_OP_mul, DW_OP_or, DW_OP_stack_value, - DW_OP_LLVM_fragment, 0, 8})); - EXPECT_TRUE( - hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_deref, DW_OP_dup, DW_OP_constu, - 31, DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_or, - DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8})); - EXPECT_TRUE(hasADbgVal({DW_OP_lit0, DW_OP_mul, DW_OP_dup, DW_OP_constu, 31, - DW_OP_shr, DW_OP_lit0, DW_OP_not, DW_OP_mul, DW_OP_or, - DW_OP_stack_value, DW_OP_LLVM_fragment, 0, 8})); - - verifyModule(*M, &errs(), &BrokenDebugInfo); - ASSERT_FALSE(BrokenDebugInfo); -} - -TEST(Local, RemoveUnreachableBlocks) { - LLVMContext C; - - std::unique_ptr M = parseIR(C, - R"( - define void @br_simple() { - entry: - br label %bb0 - bb0: - ret void - bb1: - ret void - } - - define void @br_self_loop() { - entry: - br label %bb0 - bb0: - br i1 true, label %bb1, label %bb0 - bb1: - br i1 true, label %bb0, label %bb2 - bb2: - br label %bb2 - } - - define void @br_constant() { - entry: - br label %bb0 - bb0: - br i1 true, label %bb1, label %bb2 - bb1: - br i1 true, label %bb0, label %bb2 - bb2: - br label %bb2 - } - - define void @br_loop() { - entry: - br label %bb0 - bb0: - br label %bb0 - bb1: - br label %bb2 - bb2: - br label %bb1 - } - )"); - - auto runEager = [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Eager); - removeUnreachableBlocks(F, nullptr, &DTU); - EXPECT_TRUE(DTU.getDomTree().verify()); - EXPECT_TRUE(DTU.getPostDomTree().verify()); - }; - - auto runLazy = [&](Function &F, DominatorTree *DT) { - PostDominatorTree PDT = PostDominatorTree(F); - DomTreeUpdater DTU(*DT, PDT, DomTreeUpdater::UpdateStrategy::Lazy); - removeUnreachableBlocks(F, nullptr, &DTU); - EXPECT_TRUE(DTU.getDomTree().verify()); - EXPECT_TRUE(DTU.getPostDomTree().verify()); - }; - - // Test removeUnreachableBlocks under Eager UpdateStrategy. - runWithDomTree(*M, "br_simple", runEager); - runWithDomTree(*M, "br_self_loop", runEager); - runWithDomTree(*M, "br_constant", runEager); - runWithDomTree(*M, "br_loop", runEager); - - // Test removeUnreachableBlocks under Lazy UpdateStrategy. - runWithDomTree(*M, "br_simple", runLazy); - runWithDomTree(*M, "br_self_loop", runLazy); - runWithDomTree(*M, "br_constant", runLazy); - runWithDomTree(*M, "br_loop", runLazy); - - M = parseIR(C, - R"( - define void @f() { - entry: - ret void - bb0: - ret void - } - )"); - - auto checkRUBlocksRetVal = [&](Function &F, DominatorTree *DT) { - DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); - EXPECT_TRUE(removeUnreachableBlocks(F, nullptr, &DTU)); - EXPECT_FALSE(removeUnreachableBlocks(F, nullptr, &DTU)); - EXPECT_TRUE(DTU.getDomTree().verify()); - }; - - runWithDomTree(*M, "f", checkRUBlocksRetVal); -} Index: unittests/Transforms/Utils/SSAUpdaterBulk.cpp =================================================================== --- unittests/Transforms/Utils/SSAUpdaterBulk.cpp +++ unittests/Transforms/Utils/SSAUpdaterBulk.cpp @@ -1,195 +0,0 @@ -//===- SSAUpdaterBulk.cpp - Unit tests for SSAUpdaterBulk -----------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/Utils/SSAUpdaterBulk.h" -#include "llvm/AsmParser/Parser.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Dominators.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "gtest/gtest.h" - -using namespace llvm; - -TEST(SSAUpdaterBulk, SimpleMerge) { - SSAUpdaterBulk Updater; - LLVMContext C; - Module M("SSAUpdaterTest", C); - IRBuilder<> B(C); - Type *I32Ty = B.getInt32Ty(); - auto *F = Function::Create(FunctionType::get(B.getVoidTy(), {I32Ty}, false), - GlobalValue::ExternalLinkage, "F", &M); - - // Generate a simple program: - // if: - // br i1 true, label %true, label %false - // true: - // %1 = add i32 %0, 1 - // %2 = sub i32 %0, 2 - // br label %merge - // false: - // %3 = add i32 %0, 3 - // %4 = sub i32 %0, 4 - // br label %merge - // merge: - // %5 = add i32 %1, 5 - // %6 = add i32 %3, 6 - // %7 = add i32 %2, %4 - // %8 = sub i32 %2, %4 - Argument *FirstArg = &*(F->arg_begin()); - BasicBlock *IfBB = BasicBlock::Create(C, "if", F); - BasicBlock *TrueBB = BasicBlock::Create(C, "true", F); - BasicBlock *FalseBB = BasicBlock::Create(C, "false", F); - BasicBlock *MergeBB = BasicBlock::Create(C, "merge", F); - - B.SetInsertPoint(IfBB); - B.CreateCondBr(B.getTrue(), TrueBB, FalseBB); - - B.SetInsertPoint(TrueBB); - Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1)); - Value *SubOp1 = B.CreateSub(FirstArg, ConstantInt::get(I32Ty, 2)); - B.CreateBr(MergeBB); - - B.SetInsertPoint(FalseBB); - Value *AddOp2 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 3)); - Value *SubOp2 = B.CreateSub(FirstArg, ConstantInt::get(I32Ty, 4)); - B.CreateBr(MergeBB); - - B.SetInsertPoint(MergeBB, MergeBB->begin()); - auto *I1 = cast(B.CreateAdd(AddOp1, ConstantInt::get(I32Ty, 5))); - auto *I2 = cast(B.CreateAdd(AddOp2, ConstantInt::get(I32Ty, 6))); - auto *I3 = cast(B.CreateAdd(SubOp1, SubOp2)); - auto *I4 = cast(B.CreateSub(SubOp1, SubOp2)); - - // Now rewrite uses in instructions %5, %6, %7. They need to use a phi, which - // SSAUpdater should insert into %merge. - // Intentionally don't touch %8 to see that SSAUpdater only changes - // instructions that were explicitly specified. - unsigned VarNum = Updater.AddVariable("a", I32Ty); - Updater.AddAvailableValue(VarNum, TrueBB, AddOp1); - Updater.AddAvailableValue(VarNum, FalseBB, AddOp2); - Updater.AddUse(VarNum, &I1->getOperandUse(0)); - Updater.AddUse(VarNum, &I2->getOperandUse(0)); - - VarNum = Updater.AddVariable("b", I32Ty); - Updater.AddAvailableValue(VarNum, TrueBB, SubOp1); - Updater.AddAvailableValue(VarNum, FalseBB, SubOp2); - Updater.AddUse(VarNum, &I3->getOperandUse(0)); - Updater.AddUse(VarNum, &I3->getOperandUse(1)); - - DominatorTree DT(*F); - Updater.RewriteAllUses(&DT); - - // Check how %5 and %6 were rewritten. - PHINode *UpdatePhiA = dyn_cast_or_null(I1->getOperand(0)); - EXPECT_NE(UpdatePhiA, nullptr); - EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(TrueBB), AddOp1); - EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(FalseBB), AddOp2); - EXPECT_EQ(UpdatePhiA, dyn_cast_or_null(I1->getOperand(0))); - - // Check how %7 was rewritten. - PHINode *UpdatePhiB = dyn_cast_or_null(I3->getOperand(0)); - EXPECT_EQ(UpdatePhiB->getIncomingValueForBlock(TrueBB), SubOp1); - EXPECT_EQ(UpdatePhiB->getIncomingValueForBlock(FalseBB), SubOp2); - EXPECT_EQ(UpdatePhiB, dyn_cast_or_null(I3->getOperand(1))); - - // Check that %8 was kept untouched. - EXPECT_EQ(I4->getOperand(0), SubOp1); - EXPECT_EQ(I4->getOperand(1), SubOp2); -} - -TEST(SSAUpdaterBulk, Irreducible) { - SSAUpdaterBulk Updater; - LLVMContext C; - Module M("SSAUpdaterTest", C); - IRBuilder<> B(C); - Type *I32Ty = B.getInt32Ty(); - auto *F = Function::Create(FunctionType::get(B.getVoidTy(), {I32Ty}, false), - GlobalValue::ExternalLinkage, "F", &M); - - // Generate a small program with a multi-entry loop: - // if: - // %1 = add i32 %0, 1 - // br i1 true, label %loopmain, label %loopstart - // - // loopstart: - // %2 = add i32 %0, 2 - // br label %loopmain - // - // loopmain: - // %3 = add i32 %1, 3 - // br i1 true, label %loopstart, label %afterloop - // - // afterloop: - // %4 = add i32 %2, 4 - // ret i32 %0 - Argument *FirstArg = &*F->arg_begin(); - BasicBlock *IfBB = BasicBlock::Create(C, "if", F); - BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F); - BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F); - BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F); - - B.SetInsertPoint(IfBB); - Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1)); - B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB); - - B.SetInsertPoint(LoopStartBB); - Value *AddOp2 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 2)); - B.CreateBr(LoopMainBB); - - B.SetInsertPoint(LoopMainBB); - auto *I1 = cast(B.CreateAdd(AddOp1, ConstantInt::get(I32Ty, 3))); - B.CreateCondBr(B.getTrue(), LoopStartBB, AfterLoopBB); - - B.SetInsertPoint(AfterLoopBB); - auto *I2 = cast(B.CreateAdd(AddOp2, ConstantInt::get(I32Ty, 4))); - ReturnInst *Return = B.CreateRet(FirstArg); - - // Now rewrite uses in instructions %3, %4, and 'ret i32 %0'. Only %4 needs a - // new phi, others should be able to work with existing values. - // The phi for %4 should be inserted into LoopMainBB and should look like - // this: - // %b = phi i32 [ %2, %loopstart ], [ undef, %if ] - // No other rewrites should be made. - - // Add use in %3. - unsigned VarNum = Updater.AddVariable("c", I32Ty); - Updater.AddAvailableValue(VarNum, IfBB, AddOp1); - Updater.AddUse(VarNum, &I1->getOperandUse(0)); - - // Add use in %4. - VarNum = Updater.AddVariable("b", I32Ty); - Updater.AddAvailableValue(VarNum, LoopStartBB, AddOp2); - Updater.AddUse(VarNum, &I2->getOperandUse(0)); - - // Add use in the return instruction. - VarNum = Updater.AddVariable("a", I32Ty); - Updater.AddAvailableValue(VarNum, &F->getEntryBlock(), FirstArg); - Updater.AddUse(VarNum, &Return->getOperandUse(0)); - - // Save all inserted phis into a vector. - SmallVector Inserted; - DominatorTree DT(*F); - Updater.RewriteAllUses(&DT, &Inserted); - - // Only one phi should have been inserted. - EXPECT_EQ(Inserted.size(), 1u); - - // I1 and Return should use the same values as they used before. - EXPECT_EQ(I1->getOperand(0), AddOp1); - EXPECT_EQ(Return->getOperand(0), FirstArg); - - // I2 should use the new phi. - PHINode *UpdatePhi = dyn_cast_or_null(I2->getOperand(0)); - EXPECT_NE(UpdatePhi, nullptr); - EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(LoopStartBB), AddOp2); - EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(IfBB), UndefValue::get(I32Ty)); -}