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,60 @@ return false; } +bool isDependenceSafe(Instruction &I, DependenceInfo &DI, + SmallPtrSet InstsToCheck) { + for (Instruction *CurInst : InstsToCheck) { + auto DepResult = DI.depends(&I, CurInst, true); + if (DepResult && + (DepResult->isOutput() || DepResult->isFlow() || DepResult->isAnti())) + return false; + } + return true; +} + +bool isDependenceSafe(Instruction &I, MemorySSA &MSSA, + SmallPtrSet InstsToCheck) { + MemoryUseOrDef *MemUseOrDef = MSSA.getMemoryAccess(&I); + if (!MemUseOrDef) + return true; + for (Instruction *CurInst : InstsToCheck) { + MemoryUseOrDef *DestMemUseOrDef = MSSA.getMemoryAccess(CurInst); + if (!DestMemUseOrDef) + continue; + bool IsFlowOrOutput = false; + bool IsAnti = false; + MemoryAccess *MemAccess = MemUseOrDef->getDefiningAccess(); + MemoryAccess *DestMemAccess = DestMemUseOrDef->getDefiningAccess(); + if (isa(MemUseOrDef)) { + 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 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 +353,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 +420,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 +428,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 @@ -11,6 +11,7 @@ #include "llvm/Analysis/AssumptionCache.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/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,8 @@ 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 +97,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 +188,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 +248,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 +318,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 +372,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 +422,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 +486,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 +509,76 @@ // must return. EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), *CI_safecall->getNextNode(), DT, &PDT, - &DI)); + &DI, &MSSA)); + 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, &MSSA)); + 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, &MSSA)); + 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, &MSSA)); + 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, &MSSA)); + 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, &MSSA)); EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), - *PN.getNextNode(), DT, &PDT, &DI)); + *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, &MSSA)); + 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)); + isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, &PDT, &DI, &MSSA)); + 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, &MSSA)); + 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)); + isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, &PDT, &DI, &MSSA)); + 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, &MSSA)); + 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, &MSSA)); + EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, &PDT, nullptr, &MSSA)); }); } @@ -575,16 +605,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, &MSSA)); + 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, &MSSA)); + EXPECT_FALSE( + isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, nullptr, &MSSA)); }); } @@ -607,13 +643,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, &MSSA)); + EXPECT_TRUE( + isSafeToMoveBefore(*IncInst, *CmpInst, DT, &PDT, nullptr, &MSSA)); }); } @@ -640,15 +679,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, &MSSA)); + 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, &MSSA)); + EXPECT_FALSE( + isSafeToMoveBefore(*SubInst, *AddInst, DT, &PDT, nullptr, &MSSA)); }); }