diff --git a/llvm/include/llvm/Transforms/Scalar/LoopRotation.h b/llvm/include/llvm/Transforms/Scalar/LoopRotation.h --- a/llvm/include/llvm/Transforms/Scalar/LoopRotation.h +++ b/llvm/include/llvm/Transforms/Scalar/LoopRotation.h @@ -19,16 +19,18 @@ namespace llvm { +class AAResults; /// A simple loop rotation transformation. class LoopRotatePass : public PassInfoMixin { public: LoopRotatePass(bool EnableHeaderDuplication = true); PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, - LoopStandardAnalysisResults &AR, LPMUpdater &U); + LoopStandardAnalysisResults &AR, LPMUpdater &U, + AAResults *AA = nullptr); private: const bool EnableHeaderDuplication; }; -} +} // namespace llvm #endif // LLVM_TRANSFORMS_SCALAR_LOOPROTATION_H diff --git a/llvm/include/llvm/Transforms/Utils/LoopRotationUtils.h b/llvm/include/llvm/Transforms/Utils/LoopRotationUtils.h --- a/llvm/include/llvm/Transforms/Utils/LoopRotationUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopRotationUtils.h @@ -15,6 +15,7 @@ namespace llvm { +class AAResults; class AssumptionCache; class DominatorTree; class Loop; @@ -33,7 +34,8 @@ bool LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI, AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ, - bool RotationOnly, unsigned Threshold, bool IsUtilMode); + bool RotationOnly, unsigned Threshold, bool IsUtilMode, + AAResults *AA = nullptr); } // namespace llvm diff --git a/llvm/lib/Transforms/Scalar/LoopRotation.cpp b/llvm/lib/Transforms/Scalar/LoopRotation.cpp --- a/llvm/lib/Transforms/Scalar/LoopRotation.cpp +++ b/llvm/lib/Transforms/Scalar/LoopRotation.cpp @@ -12,6 +12,7 @@ #include "llvm/Transforms/Scalar/LoopRotation.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/MemorySSA.h" @@ -38,7 +39,7 @@ PreservedAnalyses LoopRotatePass::run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, - LPMUpdater &) { + LPMUpdater &, AAResults *AA) { int Threshold = EnableHeaderDuplication ? DefaultRotationThreshold : 0; const DataLayout &DL = L.getHeader()->getModule()->getDataLayout(); const SimplifyQuery SQ = getBestSimplifyQuery(AR, DL); @@ -48,7 +49,7 @@ MSSAU = MemorySSAUpdater(AR.MSSA); bool Changed = LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, - SQ, false, Threshold, false); + SQ, false, Threshold, false, &AR.AA); if (!Changed) return PreservedAnalyses::all(); @@ -79,10 +80,12 @@ // LCSSA form makes instruction renaming easier. void getAnalysisUsage(AnalysisUsage &AU) const override { + LoopPass::getAnalysisUsage(AU); AU.addRequired(); AU.addRequired(); if (EnableMSSALoopDependency) - AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); getLoopAnalysisUsage(AU); } @@ -91,6 +94,7 @@ return false; Function &F = *L->getHeader()->getParent(); + auto *AA = &getAnalysis().getAAResults(); auto *LI = &getAnalysis().getLoopInfo(); const auto *TTI = &getAnalysis().getTTI(F); auto *AC = &getAnalysis().getAssumptionCache(F); @@ -107,7 +111,7 @@ } return LoopRotation(L, LI, TTI, AC, &DT, &SE, MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, SQ, - false, MaxHeaderSize, false); + false, MaxHeaderSize, false, AA); } }; } // end namespace @@ -115,6 +119,7 @@ char LoopRotateLegacyPass::ID = 0; INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false, false) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(LoopPass) INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 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 @@ -19,6 +19,7 @@ #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Dominators.h" +#include "llvm/IR/IntrinsicInst.h" using namespace llvm; @@ -31,6 +32,9 @@ "Instructions are not control flow equivalent"); STATISTIC(NotMovedPHINode, "Movement of PHINodes are not supported"); STATISTIC(NotMovedTerminator, "Movement of Terminator are not supported"); +STATISTIC(NotAllocaInst, "Movement of AllocaInst are not supported"); +STATISTIC(NotDbgInfoIntrinsic, + "Movement of DbgInfoIntrinsic are not supported"); namespace { /// Represent a control condition. A control condition is a condition of a @@ -400,7 +404,7 @@ DominatorTree &DT, const PostDominatorTree *PDT, DependenceInfo *DI, AAResults *AA) { // Skip tests when we don't have PDT or either one of DI or AA. - if (!PDT || !(DI || AA)) + if (PDT && !(DI || AA)) return false; // Cannot move itself before itself. @@ -417,8 +421,14 @@ if (I.isTerminator()) return reportInvalidCandidate(I, NotMovedTerminator); + if (isa(&I)) + return reportInvalidCandidate(I, NotDbgInfoIntrinsic); + + if (isa(&I)) + return reportInvalidCandidate(I, NotAllocaInst); + // TODO remove this limitation. - if (!isControlFlowEquivalent(I, InsertPoint, DT, *PDT)) + if (PDT && !isControlFlowEquivalent(I, InsertPoint, DT, *PDT)) return reportInvalidCandidate(I, NotControlFlowEquivalent); if (!DT.dominates(&InsertPoint, &I)) diff --git a/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp b/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp --- a/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp @@ -36,6 +36,7 @@ #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/CodeMoverUtils.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/Transforms/Utils/SSAUpdater.h" @@ -66,19 +67,21 @@ const SimplifyQuery &SQ; bool RotationOnly; bool IsUtilMode; + AAResults *AA; public: LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI, const TargetTransformInfo *TTI, AssumptionCache *AC, DominatorTree *DT, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, - const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode) + const SimplifyQuery &SQ, bool RotationOnly, bool IsUtilMode, + AAResults *AA) : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE), MSSAU(MSSAU), SQ(SQ), RotationOnly(RotationOnly), - IsUtilMode(IsUtilMode) {} - bool processLoop(Loop *L); + IsUtilMode(IsUtilMode), AA(AA) {} + bool processLoop(Loop *L, AAResults *AA); private: - bool rotateLoop(Loop *L, bool SimplifiedLatch); + bool rotateLoop(Loop *L, bool SimplifiedLatch, AAResults *AA); bool simplifyLoopLatch(Loop *L); }; } // end anonymous namespace @@ -263,7 +266,7 @@ /// /// If -loop-rotate-multi is enabled we can do multiple rotations in one go /// so to reach a suitable (non-deoptimizing) exit. -bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) { +bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch, AAResults *AA) { // If the loop has only one block then there is not much to rotate. if (L->getBlocks().size() == 1) return false; @@ -403,9 +406,9 @@ // executing in each iteration of the loop. This means it is safe to hoist // something that might trap, but isn't safe to hoist something that reads // memory (without proving that the loop doesn't write). - if (L->hasLoopInvariantOperands(Inst) && !Inst->mayReadFromMemory() && - !Inst->mayWriteToMemory() && !Inst->isTerminator() && - !isa(Inst) && !isa(Inst)) { + if (L->hasLoopInvariantOperands(Inst) && + isSafeToMoveBefore(*Inst, *LoopEntryBranch, *DT, nullptr, nullptr, + AA)) { Inst->moveBefore(LoopEntryBranch); continue; } @@ -711,7 +714,7 @@ } /// Rotate \c L, and return true if any modification was made. -bool LoopRotate::processLoop(Loop *L) { +bool LoopRotate::processLoop(Loop *L, AAResults *AA) { // Save the loop metadata. MDNode *LoopMD = L->getLoopID(); @@ -723,7 +726,7 @@ if (!RotationOnly) SimplifiedLatch = simplifyLoopLatch(L); - bool MadeChange = rotateLoop(L, SimplifiedLatch); + bool MadeChange = rotateLoop(L, SimplifiedLatch, AA); assert((!MadeChange || L->isLoopExiting(L->getLoopLatch())) && "Loop latch should be exiting after loop-rotate."); @@ -742,8 +745,8 @@ ScalarEvolution *SE, MemorySSAUpdater *MSSAU, const SimplifyQuery &SQ, bool RotationOnly = true, unsigned Threshold = unsigned(-1), - bool IsUtilMode = true) { + bool IsUtilMode = true, AAResults *AA) { LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly, - IsUtilMode); - return LR.processLoop(L); + IsUtilMode, AA); + return LR.processLoop(L, AA); } diff --git a/llvm/unittests/Transforms/Utils/LoopRotationUtilsTest.cpp b/llvm/unittests/Transforms/Utils/LoopRotationUtilsTest.cpp --- a/llvm/unittests/Transforms/Utils/LoopRotationUtilsTest.cpp +++ b/llvm/unittests/Transforms/Utils/LoopRotationUtilsTest.cpp @@ -7,7 +7,9 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/Utils/LoopRotationUtils.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolution.h" @@ -80,6 +82,10 @@ TargetTransformInfo TTI(M->getDataLayout()); TargetLibraryInfoImpl TLII; TargetLibraryInfo TLI(TLII); + AAResults AA(TLI); + DataLayout DL(""); + BasicAAResult BAA(DL, *F, TLI, AC, &DT); + AA.addAAResult(BAA); ScalarEvolution SE(*F, TLI, AC, DT, LI); SimplifyQuery SQ(M->getDataLayout()); @@ -88,7 +94,7 @@ bool ret = LoopRotation(L, &LI, &TTI, &AC, &DT, &SE, nullptr, - SQ, true, -1, false); + SQ, true, -1, false, &AA); EXPECT_TRUE(ret); } @@ -151,6 +157,10 @@ TargetTransformInfo TTI(M->getDataLayout()); TargetLibraryInfoImpl TLII; TargetLibraryInfo TLI(TLII); + AAResults AA(TLI); + DataLayout DL(""); + BasicAAResult BAA(DL, *F, TLI, AC, &DT); + AA.addAAResult(BAA); ScalarEvolution SE(*F, TLI, AC, DT, LI); SimplifyQuery SQ(M->getDataLayout()); @@ -159,7 +169,7 @@ bool ret = LoopRotation(L, &LI, &TTI, &AC, &DT, &SE, nullptr, - SQ, true, -1, false); + SQ, true, -1, false, &AA); /// LoopRotation should properly report "true" as we still perform the first rotation /// so we do change the IR. EXPECT_TRUE(ret);