diff --git a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h --- a/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h +++ b/llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h @@ -20,6 +20,7 @@ class DependenceInfo; class DominatorTree; class Instruction; +class MemorySSA; class PostDominatorTree; /// Return true if \p I0 and \p I1 are control flow equivalent. @@ -40,14 +41,16 @@ bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT = nullptr, - DependenceInfo *DI = nullptr); + DependenceInfo *DI = nullptr, + MemorySSA *MSSA = nullptr); /// Return true if all instructions (except the terminator) in \p BB can be /// safely moved before \p InsertPoint. bool isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT = nullptr, - DependenceInfo *DI = nullptr); + DependenceInfo *DI = nullptr, + MemorySSA *MSSA = nullptr); /// Move instructions, in an order-preserving manner, from \p FromBB to the /// beginning of \p ToBB when proven safe. diff --git a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp --- a/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp +++ b/llvm/lib/Transforms/Utils/CodeMoverUtils.cpp @@ -15,6 +15,7 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/DependenceAnalysis.h" +#include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/OrderedInstructions.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ValueTracking.h" @@ -215,6 +216,68 @@ return false; } +bool isDependenceSafe(Instruction &I, DependenceInfo &DI, + SmallPtrSet InstsToCheck) { + return llvm::none_of(InstsToCheck, [&DI, &I](Instruction *CurInst) { + auto DepResult = DI.depends(&I, CurInst, true); + if (DepResult && + (DepResult->isOutput() || DepResult->isFlow() || DepResult->isAnti())) + return true; + return false; + }); +} + +bool isDependenceSafe(Instruction &I, MemorySSA &MSSA, + SmallPtrSet InstsToCheck) { + MemoryUseOrDef *InstMA = MSSA.getMemoryAccess(&I); + if (!InstMA) + return true; + MemoryAccess *InstDefMA = InstMA->getDefiningAccess(); + MemoryAccess *InstLastDefMA = + MSSA.getWalker()->getClobberingMemoryAccess(InstMA); + return llvm::none_of(InstsToCheck, [&MSSA, InstMA, InstDefMA, + InstLastDefMA](Instruction *CurInst) { + MemoryUseOrDef *CurInstMA = MSSA.getMemoryAccess(CurInst); + if (!CurInstMA) + return false; + MemoryAccess *CurInstDefMA = CurInstMA->getDefiningAccess(); + MemoryAccess *CurInstLastDefMA = + MSSA.getWalker()->getClobberingMemoryAccess(CurInstMA); + // potential input dependencies are safe to move + if (isa(InstMA) && isa(CurInstMA)) + return false; + if (isa(InstMA)) { + // write after write dependency on same memory location + if (InstLastDefMA == CurInstMA) + return true; + if (isa(CurInstMA)) { + // write after write dependency on same memory location + if (InstMA == CurInstLastDefMA) + return true; + } else if (isa(CurInstMA)) { + // write after read dependency on same memory location + if (InstMA == CurInstDefMA || InstLastDefMA == CurInstDefMA) + return true; + } + } else if (isa(InstMA)) { + // read after write dependency on same memory location + if (InstDefMA == CurInstLastDefMA || InstDefMA == CurInstMA) + return true; + } + return false; + }); + return true; +} + +bool isDependenceSafe(Instruction &I, DependenceInfo *DI, MemorySSA *MSSA, + SmallPtrSet InstsToCheck) { + if (DI) + return isDependenceSafe(I, *DI, InstsToCheck); + else if (MSSA) + return isDependenceSafe(I, *MSSA, InstsToCheck); + return false; +} + bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT) { @@ -298,9 +361,9 @@ bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT, - DependenceInfo *DI) { + DependenceInfo *DI, MemorySSA *MSSA) { // Skip tests when we don't have PDT or DI - if (!PDT || !DI) + if (!PDT || !(DI || MSSA)) return false; // Cannot move itself before itself. @@ -365,15 +428,7 @@ // Check if I has any output/flow/anti dependences with instructions from \p // StartInst to \p EndInst. - if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(), - [&DI, &I](Instruction *CurInst) { - auto DepResult = DI->depends(&I, CurInst, true); - if (DepResult && - (DepResult->isOutput() || DepResult->isFlow() || - DepResult->isAnti())) - return true; - return false; - })) + if (!isDependenceSafe(I, DI, MSSA, InstsToCheck)) return reportInvalidCandidate(I, HasDependences); return true; @@ -381,12 +436,12 @@ bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT, - DependenceInfo *DI) { + DependenceInfo *DI, MemorySSA *MSSA) { return llvm::all_of(BB, [&](Instruction &I) { if (BB.getTerminator() == &I) return true; - return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI); + return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI, MSSA); }); } diff --git a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp --- a/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp +++ b/llvm/unittests/Transforms/Utils/CodeMoverUtilsTest.cpp @@ -9,10 +9,13 @@ #include "llvm/Transforms/Utils/CodeMoverUtils.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/AsmParser/Parser.h" +#include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/LLVMContext.h" #include "llvm/Support/SourceMgr.h" @@ -29,21 +32,26 @@ return Mod; } -static void run(Module &M, StringRef FuncName, - function_ref - Test) { +static void +run(Module &M, StringRef FuncName, + function_ref + Test) { auto *F = M.getFunction(FuncName); DominatorTree DT(*F); PostDominatorTree PDT(*F); TargetLibraryInfoImpl TLII; TargetLibraryInfo TLI(TLII); AssumptionCache AC(*F); - AliasAnalysis AA(TLI); + AAResults AA(TLI); + DataLayout DL("e-i64:64-f80:128-n8:16:32:64-S128"); + BasicAAResult BAA(DL, *F, TLI, AC, &DT); + AA.addAAResult(BAA); LoopInfo LI(DT); ScalarEvolution SE(*F, TLI, AC, DT, LI); DependenceInfo DI(F, &AA, &SE, &LI); - Test(*F, DT, PDT, DI); + MemorySSA MSSA(*F, &AA, &DT); + Test(*F, DT, PDT, DI, MSSA); } static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) { @@ -94,7 +102,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); EXPECT_TRUE( isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT)); @@ -185,7 +193,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); @@ -245,7 +253,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first"); BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first"); BasicBlock *SecondOuterIfBody = @@ -315,7 +323,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first"); BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second"); EXPECT_FALSE( @@ -369,7 +377,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); // Limitation: if we can prove cond haven't been modify between %0 and @@ -419,7 +427,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { BasicBlock &Idom = F.front(); assert(Idom.getName() == "idom" && "Expecting BasicBlock idom"); BasicBlock &BB = F.back(); @@ -483,7 +491,7 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { BasicBlock *Entry = getBasicBlockByName(F, "entry"); Instruction *CI_safecall = Entry->front().getNextNode(); assert(isa(CI_safecall) && @@ -506,49 +514,78 @@ // must return. EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), *CI_safecall->getNextNode(), DT, &PDT, - &DI)); + &DI, nullptr)); + EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), + *CI_safecall->getNextNode(), DT, &PDT, + nullptr, &MSSA)); // Cannot move CI_unsafecall, as it may throw. EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), - *CI_unsafecall, DT, &PDT, &DI)); + *CI_unsafecall, DT, &PDT, &DI, + nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), + *CI_unsafecall, DT, &PDT, nullptr, + &MSSA)); // Moving instruction to non control flow equivalent places are not // supported. EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, - &PDT, &DI)); + &PDT, &DI, nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, + &PDT, nullptr, &MSSA)); // Moving PHINode is not supported. EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(), - DT, &PDT, &DI)); + DT, &PDT, &DI, nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(), + DT, &PDT, nullptr, &MSSA)); // Cannot move non-PHINode before PHINode. - EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, + nullptr, &MSSA)); // Moving Terminator is not supported. EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), - *PN.getNextNode(), DT, &PDT, &DI)); + *PN.getNextNode(), DT, &PDT, &DI, + nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), + *PN.getNextNode(), DT, &PDT, nullptr, + &MSSA)); // Cannot move %arrayidx_A after SI, as SI is its user. EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), - DT, &PDT, &DI)); + DT, &PDT, &DI, nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), + DT, &PDT, nullptr, &MSSA)); // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand. - EXPECT_FALSE( - isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI)); + EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI, + nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, + nullptr, &MSSA)); // Cannot move LI2 after SI_A6, as there is a flow dependence. - EXPECT_FALSE( - isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT, &DI)); + EXPECT_FALSE(isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT, + &DI, nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT, + nullptr, &MSSA)); // Cannot move SI after LI1, as there is a anti dependence. - EXPECT_FALSE( - isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, &DI)); + EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, &DI, + nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, + nullptr, &MSSA)); // Cannot move SI_A5 after SI, as there is a output dependence. - EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, &DI)); + EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, nullptr, &MSSA)); // Can move LI2 before LI1, as there is only an input dependence. - EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, &DI)); + EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, nullptr, &MSSA)); }); } @@ -575,16 +612,22 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { Instruction *AddInst = getInstructionByName(F, "add"); Instruction *SubInst = getInstructionByName(F, "sub"); // Cannot move as %user uses %add and %sub doesn't dominates %user. - EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, nullptr, &MSSA)); // Cannot move as %sub_op0 is an operand of %sub and %add doesn't // dominates %sub_op0. - EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, nullptr, &MSSA)); }); } @@ -607,13 +650,16 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { Instruction *IncInst = getInstructionByName(F, "inc"); Instruction *CmpInst = getInstructionByName(F, "cmp"); // Can move as the incoming block of %inc for %i (%for.latch) dominated // by %cmp. - EXPECT_TRUE(isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, nullptr, &MSSA)); }); } @@ -640,15 +686,21 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSA &MSSA) { Instruction *AddInst = getInstructionByName(F, "add"); Instruction *SubInst = getInstructionByName(F, "sub"); // Cannot move as %user uses %add and %sub doesn't dominates %user. - EXPECT_FALSE(isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, nullptr, &MSSA)); // Cannot move as %sub_op0 is an operand of %sub and %add doesn't // dominates %sub_op0. - EXPECT_FALSE(isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, nullptr, &MSSA)); }); }