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 @@ -16,6 +16,7 @@ namespace llvm { +class AAResults; class BasicBlock; class DependenceInfo; class DominatorTree; @@ -40,14 +41,14 @@ bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT = nullptr, - DependenceInfo *DI = nullptr); + DependenceInfo *DI = nullptr, AAResults *AA = 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, AAResults *AA = 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 @@ -14,6 +14,7 @@ #include "llvm/Transforms/Utils/CodeMoverUtils.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ValueTracking.h" @@ -226,6 +227,75 @@ return false; } +/// Checks data dependency between /p I and instructions in /p InstsToCheck +/// using dependence info. +static bool isDependenceSafe(Instruction &I, DependenceInfo &DI, + SmallPtrSetImpl &InstsToCheck) { + return llvm::none_of(InstsToCheck, [&DI, &I](Instruction *CurInst) { + auto DepResult = DI.depends(&I, CurInst, true); + return (DepResult && (DepResult->isOutput() || DepResult->isFlow() || + DepResult->isAnti())); + }); +} + +/// Checks data dependency between /p I and instructions in /p InstsToCheck +/// using alias analysis. +static bool isDependenceSafe(Instruction &I, AAResults &AA, + SmallPtrSetImpl &InstsToCheck) { + if (!I.mayReadOrWriteMemory()) + return true; + + SmallVector MemLocs; + if (CallInst *CI = dyn_cast(&I)) { + for (Value *Op : CI->arg_operands()) + if (Op->getType()->isPointerTy()) { + MemLocs.push_back( + MemoryLocation(Op, LocationSize::unknown(), AAMDNodes())); + } + } else { + MemLocs.push_back(MemoryLocation::get(&I)); + } + for (MemoryLocation MemLoc : MemLocs) { + return llvm::none_of(InstsToCheck, [&AA, &I, &MemLoc](Instruction *Inst) { + if (!Inst->mayReadOrWriteMemory()) + return false; + /// Get memory location for CallInst can be none and it won't be used for + /// CallInst. + auto DestMemLoc = MemoryLocation::get(Inst); + if (MemLoc.Size.hasValue() && DestMemLoc.Size.hasValue() && + AA.isNoAlias(MemLoc, DestMemLoc)) + return false; + + ModRefInfo Result = AA.getModRefInfo(Inst, MemLoc); + ModRefInfo DestResult = AA.getModRefInfo(&I, DestMemLoc); + if (CallBase *CBDest = dyn_cast(Inst)) { + if (!MemLoc.Size.hasValue()) + Result = DestResult = AA.getModRefInfo(&I, CBDest); + if (CallBase *CBSrc = dyn_cast(&I)) + if (!DestMemLoc.Size.hasValue()) + DestResult = AA.getModRefInfo(Inst, CBSrc); + } + // RAR dependency is safe + if (isRefSet(Result) && isRefSet(DestResult) && !isModSet(Result) && + !isModSet(DestResult)) + return false; + return true; + }); + } + return true; +} + +/// Checks data dependency between /p I and instructions in /p InstsToCheck +/// using dependence info or alias analysis. +static bool isDependenceSafe(Instruction &I, DependenceInfo *DI, AAResults *AA, + SmallPtrSetImpl &InstsToCheck) { + if (DI) + return isDependenceSafe(I, *DI, InstsToCheck); + else if (AA) + return isDependenceSafe(I, *AA, InstsToCheck); + return false; +} + bool llvm::isControlFlowEquivalent(const Instruction &I0, const Instruction &I1, const DominatorTree &DT, const PostDominatorTree &PDT) { @@ -309,9 +379,9 @@ bool llvm::isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT, - DependenceInfo *DI) { - // Skip tests when we don't have PDT or DI - if (!PDT || !DI) + DependenceInfo *DI, AAResults *AA) { + // Skip tests when we don't have PDT or either one of DI or AA. + if (!PDT || !(DI || AA)) return false; // Cannot move itself before itself. @@ -359,7 +429,6 @@ [](Instruction *I) { if (I->mayThrow()) return true; - const CallBase *CB = dyn_cast(I); if (!CB) return false; @@ -367,7 +436,6 @@ return true; if (!CB->hasFnAttr(Attribute::NoSync)) return true; - return false; })) { return reportInvalidCandidate(I, MayThrowException); @@ -375,15 +443,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, AA, InstsToCheck)) return reportInvalidCandidate(I, HasDependences); return true; @@ -391,12 +451,12 @@ bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint, DominatorTree &DT, const PostDominatorTree *PDT, - DependenceInfo *DI) { + DependenceInfo *DI, AAResults *AA) { 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, AA); }); } 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,12 @@ #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/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 +31,25 @@ 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(""); + 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); + Test(*F, DT, PDT, DI, AA); } static BasicBlock *getBasicBlockByName(Function &F, StringRef Name) { @@ -94,7 +100,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); EXPECT_TRUE( isControlFlowEquivalent(*FirstIfBody, *FirstIfBody, DT, PDT)); @@ -185,7 +191,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.first"); BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.second"); BasicBlock *ThirdIfBody = getBasicBlockByName(F, "if.third"); @@ -245,7 +251,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { BasicBlock *FirstOuterIfBody = getBasicBlockByName(F, "if.outer.first"); BasicBlock *FirstInnerIfBody = getBasicBlockByName(F, "if.inner.first"); BasicBlock *SecondOuterIfBody = @@ -315,7 +321,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { BasicBlock *FirstIfBody = getBasicBlockByName(F, "if.inner.first"); BasicBlock *SecondIfBody = getBasicBlockByName(F, "if.inner.second"); EXPECT_FALSE( @@ -369,7 +375,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { 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 +425,7 @@ })"); run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { BasicBlock &Idom = F.front(); assert(Idom.getName() == "idom" && "Expecting BasicBlock idom"); BasicBlock &BB = F.back(); @@ -483,7 +489,7 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { BasicBlock *Entry = getBasicBlockByName(F, "entry"); Instruction *CI_safecall = Entry->front().getNextNode(); assert(isa(CI_safecall) && @@ -506,49 +512,76 @@ // 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, &AA)); // 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, + &AA)); // Moving instruction to non control flow equivalent places are not // supported. - EXPECT_FALSE( - isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, &PDT, &DI)); - + EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, + &PDT, &DI, nullptr)); + EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, + &PDT, nullptr, &AA)); // 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, &AA)); // 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, &AA)); // 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, + &AA)); // 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, &AA)); // 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, &AA)); // 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, &AA)); // 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, &AA)); // 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, &AA)); // 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, &AA)); }); } @@ -575,16 +608,22 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { 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, &AA)); // 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, &AA)); }); } @@ -607,13 +646,16 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { 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, &AA)); }); } @@ -640,16 +682,22 @@ run(*M, "foo", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { 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, &AA)); // 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, &AA)); }); } @@ -675,7 +723,7 @@ run(*M, "dependence", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { Instruction *LoadA0 = getInstructionByName(F, "tmp0"); Instruction *LoadA1 = getInstructionByName(F, "tmp1"); Instruction *LoadA2 = getInstructionByName(F, "tmp2"); @@ -689,44 +737,92 @@ Instruction *StoreA2 = StoreB1->getPrevNode(); // Input forward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, nullptr, &AA)); // Input backward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, nullptr, &AA)); // Output forward dependency - EXPECT_FALSE(isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA0, *LoadA0, DT, &PDT, nullptr, &AA)); // Output backward dependency - EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA1, *StoreA0, DT, &PDT, nullptr, &AA)); // Flow forward dependency - EXPECT_FALSE(isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA1, *StoreB0, DT, &PDT, nullptr, &AA)); // Flow backward dependency - EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA0, *StoreA1, DT, &PDT, nullptr, &AA)); // Anti forward dependency - EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA1, *StoreB1, DT, &PDT, nullptr, &AA)); // Anti backward dependency - EXPECT_FALSE(isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA2, *LoadA1, DT, &PDT, nullptr, &AA)); // No input backward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, nullptr, &AA)); // No input forward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, nullptr, &AA)); // No Output forward dependency - EXPECT_TRUE(isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreA2, *LoadA2, DT, &PDT, nullptr, &AA)); // No Output backward dependency - EXPECT_TRUE(isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB1, *StoreA2, DT, &PDT, nullptr, &AA)); // No flow forward dependency - EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB0, *StoreA2, DT, &PDT, nullptr, &AA)); // No flow backward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA1, *StoreB0, DT, &PDT, nullptr, &AA)); // No anti backward dependency - EXPECT_TRUE(isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB0, *LoadA0, DT, &PDT, nullptr, &AA)); // No anti forward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, nullptr, &AA)); }); } @@ -795,7 +891,7 @@ })"); run(*M, "dependence", [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, - DependenceInfo &DI) { + DependenceInfo &DI, AAResults &AA) { BasicBlock *BB1 = getBasicBlockByName(F, "bb1"); BasicBlock *BB3 = getBasicBlockByName(F, "bb3"); BasicBlock *BB7 = getBasicBlockByName(F, "bb7"); @@ -814,43 +910,224 @@ Instruction &StoreA2 = BB11->front(); // Input forward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA2, *LoadB2, DT, &PDT, nullptr, &AA)); // Input backward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadA2, DT, &PDT, nullptr, &AA)); // Output forward dependency - EXPECT_FALSE(isSafeToMoveBefore(StoreA0, *LoadA0, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(StoreA0, *LoadA0, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(StoreA0, *LoadA0, DT, &PDT, nullptr, &AA)); // Output backward dependency - EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreA0, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(StoreA1, StoreA0, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(StoreA1, StoreA0, DT, &PDT, nullptr, &AA)); // Flow forward dependency - EXPECT_FALSE(isSafeToMoveBefore(StoreA1, StoreB0, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(StoreA1, StoreB0, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(StoreA1, StoreB0, DT, &PDT, nullptr, &AA)); // Flow backward dependency - EXPECT_FALSE(isSafeToMoveBefore(*LoadA0, StoreA1, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA0, StoreA1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA0, StoreA1, DT, &PDT, nullptr, &AA)); // Anti forward dependency - EXPECT_FALSE(isSafeToMoveBefore(*LoadA1, StoreB1, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA1, StoreB1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA1, StoreB1, DT, &PDT, nullptr, &AA)); // Anti backward dependency - EXPECT_FALSE(isSafeToMoveBefore(StoreA2, *LoadA1, DT, &PDT, &DI)); + EXPECT_FALSE( + isSafeToMoveBefore(StoreA2, *LoadA1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(StoreA2, *LoadA1, DT, &PDT, nullptr, &AA)); // No input backward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadB2, *LoadA3, DT, &PDT, nullptr, &AA)); // No input forward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadB3, DT, &PDT, nullptr, &AA)); // No Output forward dependency - EXPECT_TRUE(isSafeToMoveBefore(StoreA2, *LoadA2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(StoreA2, *LoadA2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(StoreA2, *LoadA2, DT, &PDT, nullptr, &AA)); // No Output backward dependency - EXPECT_TRUE(isSafeToMoveBefore(StoreB1, StoreA2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(StoreB1, StoreA2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(StoreB1, StoreA2, DT, &PDT, nullptr, &AA)); // No flow forward dependency - EXPECT_TRUE(isSafeToMoveBefore(StoreB0, StoreA2, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(StoreB0, StoreA2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(StoreB0, StoreA2, DT, &PDT, nullptr, &AA)); // No flow backward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA1, StoreB0, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA1, StoreB0, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA1, StoreB0, DT, &PDT, nullptr, &AA)); // No anti backward dependency - EXPECT_TRUE(isSafeToMoveBefore(StoreB0, *LoadA0, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(StoreB0, *LoadA0, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(StoreB0, *LoadA0, DT, &PDT, nullptr, &AA)); // No anti forward dependency - EXPECT_TRUE(isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA0, *LoadA1, DT, &PDT, nullptr, &AA)); + }); +} + +TEST(CodeMoverUtils, IsSafeToMoveTest7) { + LLVMContext C; + + std::unique_ptr M = + parseIR(C, R"(define i32 @dependence(i32* noalias %A, i32* noalias %B) { +entry: + store i32 0, i32* %A, align 4 ; storeA0 + %tmp0 = load i32, i32* %A, align 4 ; LoadA0 + store i32 8, i32* %B, align 4 ; storeB0 + call void @function1(i32* %B) + %tmp1 = load i32, i32* %A, align 4 ; LoadA1 + br label %header + +header: + %b = phi i32 [ 0, %entry ], [ %c, %latch ] + %c = add i32 %b, 1 + %z = icmp eq i32 %c, 0 + %tmp2 = load i32, i32* %B, align 4 ; LoadB0 + store i32 2, i32* %A, align 4 ; storeA1 + %tmp3 = load i32, i32* %A, align 4 ; LoadA2 + %tmp4 = icmp slt i32 %tmp2, %tmp2 + br i1 %tmp4, label %bb1, label %bb5 + +bb1: + store i32 7, i32* %B, align 4 ; StoreB1 + %tmp5 = icmp sgt i32 %tmp2, 10 + br i1 %tmp5, label %bb2, label %bb3 + +bb2: + store i32 9, i32* %B, align 4 ; StoreB2 + br label %bb3 + +bb3: + call void @function(i32 %tmp1) + %tmp6 = load i32, i32* %B, align 4 ; LoadB1 + store i32 5, i32* %A, align 4 ; StoreA2 + %tmp7 = load i32, i32* %A, align 4 ; LoadA3 + br label %latch + +latch: + store i32 8, i32* %B, align 4 ; StoreB3 + %tmp8 = load i32, i32* %B, align 4 ; LoadB2 + store i32 2, i32* %A, align 4 ; StoreA3 + %tmp9 = add nsw i32 %tmp8, 1 + br label %header + +bb5: + %tmp10 = load i32, i32* %B, align 4 ; LoadB3 + store i32 1, i32* %B, align 4 ; StoreB4 + store i32 2, i32* %A, align 4 ; StoreA4 + ret i32 0 +} +declare void @function(i32) willreturn nosync nounwind +declare void @function1(i32*) willreturn nosync nounwind +)"); + run(*M, "dependence", + [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, + DependenceInfo &DI, AAResults &AA) { + Instruction *LoadA0 = getInstructionByName(F, "tmp0"); + Instruction *LoadA1 = getInstructionByName(F, "tmp1"); + Instruction *LoadB0 = getInstructionByName(F, "tmp2"); + Instruction *LoadA2 = getInstructionByName(F, "tmp3"); + Instruction *LoadB1 = getInstructionByName(F, "tmp6"); + Instruction *LoadB2 = getInstructionByName(F, "tmp8"); + Instruction *LoadA3 = getInstructionByName(F, "tmp7"); + Instruction *StoreA0 = LoadA0->getPrevNode(); + Instruction *StoreA1 = LoadB0->getNextNode(); + Instruction *StoreA2 = LoadB1->getNextNode(); + Instruction *StoreA3 = LoadB2->getNextNode(); + Instruction *StoreB3 = LoadB2->getPrevNode(); + + // sink instruction from entry to header + EXPECT_FALSE( + isSafeToMoveBefore(*LoadB1, *LoadA0, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadB1, *LoadA0, DT, &PDT, nullptr, &AA)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA0, *LoadB1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA0, *LoadB1, DT, &PDT, nullptr, &AA)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA1, *LoadB0, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA1, *LoadB0, DT, &PDT, nullptr, &AA)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA1, *StoreA1, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA1, *StoreA1, DT, &PDT, nullptr, &AA)); + + // hoist instrcution from header to entry + EXPECT_TRUE( + isSafeToMoveBefore(*LoadB0, *LoadA1, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadB0, *LoadA1, DT, &PDT, nullptr, &AA)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA1, *LoadA1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA1, *LoadA1, DT, &PDT, nullptr, &AA)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA2, *LoadA1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*LoadA2, *LoadA1, DT, &PDT, nullptr, &AA)); + + // sink instrcutions from bb3 to latch + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *StoreB3, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *StoreB3, DT, &PDT, nullptr, &AA)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadB2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*LoadA3, *LoadB2, DT, &PDT, nullptr, &AA)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB3, *LoadA3, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB3, *LoadA3, DT, &PDT, nullptr, &AA)); + + // hoist instructions from latch to bb3 + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB3, *StoreA2, DT, &PDT, &DI, nullptr)); + EXPECT_TRUE( + isSafeToMoveBefore(*StoreB3, *StoreA2, DT, &PDT, nullptr, &AA)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA3, *LoadA2, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreA3, *LoadA2, DT, &PDT, nullptr, &AA)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreB3, *LoadB1, DT, &PDT, &DI, nullptr)); + EXPECT_FALSE( + isSafeToMoveBefore(*StoreB3, *LoadB1, DT, &PDT, nullptr, &AA)); }); }