From 388de9dfcdf6d96ab5e32c91be49745b1892a483 Mon Sep 17 00:00:00 2001 From: Alina Sbirlea Date: Mon, 27 Jan 2020 13:36:41 -0800 Subject: [PATCH] [LoopUtils] Make duplicate method a utility. [NFCI] Summary: Method appendLoopsToWorklist is duplicate in LoopUnroll and in the LoopPassManager as an internal method. Make it an utility. Reviewers: dmgreen, chandlerc, fedor.sergeev, yamauchi Subscribers: mehdi_amini, hiraditya, zzheng, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D73569 --- .../llvm/Transforms/Scalar/LoopPassManager.h | 49 +++------------------- llvm/include/llvm/Transforms/Utils/LoopUtils.h | 25 +++++++++++ .../lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp | 4 +- llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp | 29 ++----------- llvm/lib/Transforms/Utils/LoopUtils.cpp | 42 +++++++++++++++++++ 5 files changed, 80 insertions(+), 69 deletions(-) diff --git a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h b/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h index aed7648..9bbf39c 100644 --- 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 @@ using RequireAnalysisLoopPass = 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 @@ public: "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 @@ public: "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 @@ public: // 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 index ab71a05..31d17eb 100644 --- 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 @@ int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, 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 index 88f1948..5fb9c3f 100644 --- a/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp +++ b/llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp @@ -446,8 +446,10 @@ static bool tryToUnrollAndJamLoop(Function &F, DominatorTree &DT, LoopInfo &LI, 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 index da1a818..46498a2 100644 --- a/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp +++ b/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -1395,30 +1395,6 @@ PreservedAnalyses LoopFullUnrollPass::run(Loop &L, LoopAnalysisManager &AM, 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 @@ PreservedAnalyses LoopUnrollPass::run(Function &F, 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 index 472be10..431d0c6 100644 --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -1450,3 +1450,45 @@ void llvm::setProfileInfoAfterUnrolling(Loop *OrigLoop, Loop *UnrolledLoop, 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); +} -- 2.7.4