diff --git a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h b/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h --- a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h +++ b/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h @@ -52,6 +52,7 @@ #include "llvm/IR/PassManager.h" #include "llvm/Transforms/Utils/LCSSA.h" #include "llvm/Transforms/Utils/LoopSimplify.h" +#include "llvm/Transforms/Utils/LoopUtils.h" namespace llvm { @@ -101,40 +102,6 @@ RequireAnalysisPass; -namespace internal { -/// Helper to implement appending of loops onto a worklist. -/// -/// We want to process loops in postorder, but the worklist is a LIFO data -/// structure, so we append to it in *reverse* postorder. -/// -/// For trees, a preorder traversal is a viable reverse postorder, so we -/// actually append using a preorder walk algorithm. -template -inline void appendLoopsToWorklist(RangeT &&Loops, - SmallPriorityWorklist &Worklist) { - // We use an internal worklist to build up the preorder traversal without - // recursion. - SmallVector PreOrderLoops, PreOrderWorklist; - - // We walk the initial sequence of loops in reverse because we generally want - // to visit defs before uses and the worklist is LIFO. - for (Loop *RootL : reverse(Loops)) { - assert(PreOrderLoops.empty() && "Must start with an empty preorder walk."); - assert(PreOrderWorklist.empty() && - "Must start with an empty preorder walk worklist."); - PreOrderWorklist.push_back(RootL); - do { - Loop *L = PreOrderWorklist.pop_back_val(); - PreOrderWorklist.append(L->begin(), L->end()); - PreOrderLoops.push_back(L); - } while (!PreOrderWorklist.empty()); - - Worklist.insert(std::move(PreOrderLoops)); - PreOrderLoops.clear(); - } -} -} - template class FunctionToLoopPassAdaptor; /// This class provides an interface for updating the loop pass manager based @@ -190,7 +157,7 @@ "the current loop!"); #endif - internal::appendLoopsToWorklist(NewChildLoops, Worklist); + appendLoopsToWorklist(NewChildLoops, Worklist); // Also skip further processing of the current loop--it will be revisited // after all of its newly added children are accounted for. @@ -210,7 +177,7 @@ "All of the new loops must be siblings of the current loop!"); #endif - internal::appendLoopsToWorklist(NewSibLoops, Worklist); + appendLoopsToWorklist(NewSibLoops, Worklist); // No need to skip the current loop or revisit it, as sibling loops // shouldn't impact anything. @@ -324,13 +291,9 @@ // update them when they mutate the loop nest structure. LPMUpdater Updater(Worklist, LAM); - // Add the loop nests in the reverse order of LoopInfo. For some reason, - // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For - // the purpose of unrolling, loop deletion, and LICM, we largely want to - // work forward across the CFG so that we visit defs before uses and can - // propagate simplifications from one loop nest into the next. - // FIXME: Consider changing the order in LoopInfo. - internal::appendLoopsToWorklist(reverse(LI), Worklist); + // Add the loop nests in the reverse order of LoopInfo. See method + // declaration. + appendLoopsToWorklist(LI, Worklist); do { Loop *L = Worklist.pop_back_val(); diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -15,6 +15,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Optional.h" +#include "llvm/ADT/PriorityWorklist.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" @@ -400,6 +401,30 @@ void setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, Loop *RemainderLoop, uint64_t UF); +/// Utility that implements appending of loops onto a worklist given a range. +/// We want to process loops in postorder, but the worklist is a LIFO data +/// structure, so we append to it in *reverse* postorder. +/// For trees, a preorder traversal is a viable reverse postorder, so we +/// actually append using a preorder walk algorithm. +template +void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist &); +/// Utility that implements appending of loops onto a worklist given a range. +/// It has the same behavior as appendLoopsToWorklist, but assumes the range of +/// loops has already been reversed, so it processes loops in the given order. +template +void appendReversedLoopsToWorklist(RangeT &&, + SmallPriorityWorklist &); + +/// Utility that implements appending of loops onto a worklist given LoopInfo. +/// Calls the templated utility taking a Range of loops, handing it the Loops +/// in LoopInfo, iterated in reverse. This is because the loops are stored in +/// RPO w.r.t. the control flow graph in LoopInfo. For the purpose of unrolling, +/// loop deletion, and LICM, we largely want to work forward across the CFG so +/// that we visit defs before uses and can propagate simplifications from one +/// loop nest into the next. Calls appendReversedLoopsToWorklist with the +/// already reversed loops in LI. +/// FIXME: Consider changing the order in LoopInfo. +void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist &); } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_LOOPUTILS_H diff --git a/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp b/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp --- a/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp +++ b/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp @@ -446,8 +446,10 @@ DidSomething |= formLCSSARecursively(*L, DT, &LI, &SE); } + // Add the loop nests in the reverse order of LoopInfo. See method + // declaration. SmallPriorityWorklist Worklist; - internal::appendLoopsToWorklist(reverse(LI), Worklist); + appendLoopsToWorklist(LI, Worklist); while (!Worklist.empty()) { Loop *L = Worklist.pop_back_val(); LoopUnrollResult Result = diff --git a/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp b/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp --- a/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -1395,30 +1395,6 @@ return getLoopPassPreservedAnalyses(); } -template -static SmallVector appendLoopsToWorklist(RangeT &&Loops) { - SmallVector Worklist; - // We use an internal worklist to build up the preorder traversal without - // recursion. - SmallVector PreOrderLoops, PreOrderWorklist; - - for (Loop *RootL : Loops) { - assert(PreOrderLoops.empty() && "Must start with an empty preorder walk."); - assert(PreOrderWorklist.empty() && - "Must start with an empty preorder walk worklist."); - PreOrderWorklist.push_back(RootL); - do { - Loop *L = PreOrderWorklist.pop_back_val(); - PreOrderWorklist.append(L->begin(), L->end()); - PreOrderLoops.push_back(L); - } while (!PreOrderWorklist.empty()); - - Worklist.append(PreOrderLoops.begin(), PreOrderLoops.end()); - PreOrderLoops.clear(); - } - return Worklist; -} - PreservedAnalyses LoopUnrollPass::run(Function &F, FunctionAnalysisManager &AM) { auto &SE = AM.getResult(F); @@ -1452,7 +1428,10 @@ Changed |= formLCSSARecursively(*L, DT, &LI, &SE); } - SmallVector Worklist = appendLoopsToWorklist(LI); + // Add the loop nests in the reverse order of LoopInfo. See method + // declaration. + SmallPriorityWorklist Worklist; + appendLoopsToWorklist(LI, Worklist); while (!Worklist.empty()) { // Because the LoopInfo stores the loops in RPO, we walk the worklist diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -1450,3 +1450,45 @@ setLoopEstimatedTripCount(RemainderLoop, RemainderAverageTripCount, OrigLoopInvocationWeight); } + +/// Utility that implements appending of loops onto a worklist. +/// Loops are added in preorder (analogous for reverse postorder for trees), +/// and the worklist is processed LIFO. +template +void llvm::appendReversedLoopsToWorklist( + RangeT &&Loops, SmallPriorityWorklist &Worklist) { + // We use an internal worklist to build up the preorder traversal without + // recursion. + SmallVector PreOrderLoops, PreOrderWorklist; + + // We walk the initial sequence of loops in reverse because we generally want + // to visit defs before uses and the worklist is LIFO. + for (Loop *RootL : Loops) { + assert(PreOrderLoops.empty() && "Must start with an empty preorder walk."); + assert(PreOrderWorklist.empty() && + "Must start with an empty preorder walk worklist."); + PreOrderWorklist.push_back(RootL); + do { + Loop *L = PreOrderWorklist.pop_back_val(); + PreOrderWorklist.append(L->begin(), L->end()); + PreOrderLoops.push_back(L); + } while (!PreOrderWorklist.empty()); + + Worklist.insert(std::move(PreOrderLoops)); + PreOrderLoops.clear(); + } +} + +template +void llvm::appendLoopsToWorklist(RangeT &&Loops, + SmallPriorityWorklist &Worklist) { + appendReversedLoopsToWorklist(reverse(Loops), Worklist); +} + +template void llvm::appendLoopsToWorklist &>( + ArrayRef &Loops, SmallPriorityWorklist &Worklist); + +void llvm::appendLoopsToWorklist(LoopInfo &LI, + SmallPriorityWorklist &Worklist) { + appendReversedLoopsToWorklist(LI, Worklist); +}