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 MemorySSAUpdater; 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, + MemorySSAUpdater *MSSAU = 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, + MemorySSAUpdater *MSSAU = 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,8 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/DependenceAnalysis.h" +#include "llvm/Analysis/MemorySSA.h" +#include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/OrderedInstructions.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ValueTracking.h" @@ -215,6 +217,69 @@ return false; } +bool isDependenceSafe(Instruction &I, DependenceInfo &DI, + SmallPtrSet InstsToCheck) { + return !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; + }); +} + +bool isDependenceSafe(Instruction &I, MemorySSAUpdater &MSSAU, + SmallPtrSet InstsToCheck) { + MemoryUseOrDef *MemUseOrDef = MSSAU.getMemorySSA()->getMemoryAccess(&I); + if (!MemUseOrDef) + return true; + return !std::any_of( + InstsToCheck.begin(), InstsToCheck.end(), + [&MSSAU, &MemUseOrDef, &I](Instruction *CurInst) { + MemoryUseOrDef *DestMemUseOrDef = + MSSAU.getMemorySSA()->getMemoryAccess(CurInst); + if (!DestMemUseOrDef) + return false; + bool IsFlowOrOutput = false; + bool IsAnti = false; + MemoryAccess *MemAccess = MemUseOrDef->getDefiningAccess(); + MemoryAccess *DestMemAccess = DestMemUseOrDef->getDefiningAccess(); + if (isa(MemUseOrDef)) { + if (isa(DestMemUseOrDef) || + isa(DestMemUseOrDef)) { + if (MemoryDef *DestMemDef = dyn_cast(DestMemAccess)) { + if (DestMemDef == MemUseOrDef) { + IsFlowOrOutput = true; + } + } + } + } else if (isa(MemUseOrDef)) { + if (isa(DestMemUseOrDef)) { + MemoryDef *MemDef = dyn_cast(MemAccess); + MemoryDef *DestMemDef = dyn_cast(DestMemAccess); + if (MemDef == DestMemDef) { + IsAnti = true; + } + } + } + if (IsFlowOrOutput || IsAnti) + return true; + return false; + }); +} + +bool isDependenceSafe(Instruction &I, DependenceInfo *DI, + MemorySSAUpdater *MSSAU, + SmallPtrSet InstsToCheck) { + if (DI) + return isDependenceSafe(I, *DI, InstsToCheck); + else if (MSSAU) + return isDependenceSafe(I, *MSSAU, InstsToCheck); + return false; +} + bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT) { @@ -298,9 +363,9 @@ bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT, - DependenceInfo *DI) { + DependenceInfo *DI, MemorySSAUpdater *MSSAU) { // Skip tests when we don't have PDT or DI - if (!PDT || !DI) + if (!PDT || !(DI || MSSAU)) return false; // Cannot move itself before itself. @@ -365,15 +430,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, MSSAU, InstsToCheck)) return reportInvalidCandidate(I, HasDependences); return true; @@ -381,12 +438,12 @@ bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT, - DependenceInfo *DI) { + DependenceInfo *DI, MemorySSAUpdater *MSSAU) { 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, MSSAU); }); } 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 @@ -11,6 +11,7 @@ #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/AsmParser/Parser.h" #include "llvm/IR/Dominators.h" @@ -29,10 +30,11 @@ 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); @@ -43,7 +45,9 @@ 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); + MemorySSAUpdater MSSAU(&MSSA); + Test(*F, DT, PDT, DI, MSSAU); } static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) { @@ -94,7 +98,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); EXPECT_TRUE( isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT)); @@ -185,7 +189,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); @@ -245,7 +249,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first"); BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first"); BasicBlock *SecondOuterIfBody = @@ -315,7 +319,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first"); BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second"); EXPECT_FALSE( @@ -369,7 +373,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { 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 +423,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { BasicBlock &Idom = F.front(); assert(Idom.getName() == "idom" && "Expecting BasicBlock idom"); BasicBlock &BB = F.back(); @@ -483,7 +487,7 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { BasicBlock *Entry = getBasicBlockByName(F, "entry"); Instruction *CI_safecall = Entry->front().getNextNode(); assert(isa(CI_safecall) && @@ -506,49 +510,76 @@ // must return. EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), *CI_safecall->getNextNode(), DT, &PDT, - &DI)); + &DI, &MSSAU)); + EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), + *CI_safecall->getNextNode(), DT, &PDT, + nullptr, &MSSAU)); // Cannot move CI_unsafecall, as it may throw. EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), - *CI_unsafecall, DT, &PDT, &DI)); + *CI_unsafecall, DT, &PDT, &DI, &MSSAU)); + EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), + *CI_unsafecall, DT, &PDT, nullptr, + &MSSAU)); // Moving instruction to non control flow equivalent places are not // supported. EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, - &PDT, &DI)); + &PDT, &DI, &MSSAU)); + EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, + &PDT, nullptr, &MSSAU)); // Moving PHINode is not supported. EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(), - DT, &PDT, &DI)); + DT, &PDT, &DI, &MSSAU)); + EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(), + DT, &PDT, nullptr, &MSSAU)); // Cannot move non-PHINode before PHINode. - EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, &DI, &MSSAU)); + EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, &PDT, + nullptr, &MSSAU)); // Moving Terminator is not supported. + EXPECT_FALSE(isSafeToMoveBefore( + *Entry->getTerminator(), *PN.getNextNode(), DT, &PDT, &DI, &MSSAU)); EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), - *PN.getNextNode(), DT, &PDT, &DI)); + *PN.getNextNode(), DT, &PDT, nullptr, + &MSSAU)); // Cannot move %arrayidx_A after SI, as SI is its user. EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), - DT, &PDT, &DI)); + DT, &PDT, &DI, &MSSAU)); + EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), + DT, &PDT, nullptr, &MSSAU)); // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand. EXPECT_FALSE( - isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI)); + isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI, &MSSAU)); + EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, + nullptr, &MSSAU)); // 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, &MSSAU)); + EXPECT_FALSE(isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, &PDT, + nullptr, &MSSAU)); // 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, + &MSSAU)); + EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, + nullptr, &MSSAU)); // 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, &MSSAU)); + EXPECT_FALSE( + isSafeToMoveBefore(*SI_A5, *LI1, DT, &PDT, nullptr, &MSSAU)); // 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, &MSSAU)); + EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, nullptr, &MSSAU)); }); } @@ -575,16 +606,22 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { 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, &MSSAU)); + EXPECT_FALSE( + isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, nullptr, &MSSAU)); // 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, &MSSAU)); + EXPECT_FALSE( + isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, nullptr, &MSSAU)); }); } @@ -607,13 +644,16 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { 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, &MSSAU)); + EXPECT_TRUE( + isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, nullptr, &MSSAU)); }); } @@ -640,15 +680,21 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, MemorySSAUpdater &MSSAU) { 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, &MSSAU)); + EXPECT_FALSE( + isSafeToMoveBefore(*AddInst, *SubInst, DT, &PDT, nullptr, &MSSAU)); // 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, &MSSAU)); + EXPECT_FALSE( + isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, nullptr, &MSSAU)); }); }