LLVM  9.0.0svn
LoopRotation.cpp
Go to the documentation of this file.
1 //===- LoopRotation.cpp - Loop Rotation Pass ------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements Loop Rotation Pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/Statistic.h"
16 #include "llvm/Analysis/LoopPass.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Transforms/Scalar.h"
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "loop-rotate"
29 
31  "rotation-max-header-size", cl::init(16), cl::Hidden,
32  cl::desc("The default maximum header size for automatic loop rotation"));
33 
34 LoopRotatePass::LoopRotatePass(bool EnableHeaderDuplication)
35  : EnableHeaderDuplication(EnableHeaderDuplication) {}
36 
39  LPMUpdater &) {
40  int Threshold = EnableHeaderDuplication ? DefaultRotationThreshold : 0;
41  const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
42  const SimplifyQuery SQ = getBestSimplifyQuery(AR, DL);
43 
45  if (AR.MSSA)
46  MSSAU = MemorySSAUpdater(AR.MSSA);
47  bool Changed = LoopRotation(&L, &AR.LI, &AR.TTI, &AR.AC, &AR.DT, &AR.SE,
48  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
49  SQ, false, Threshold, false);
50 
51  if (!Changed)
52  return PreservedAnalyses::all();
53 
54  if (AR.MSSA && VerifyMemorySSA)
55  AR.MSSA->verifyMemorySSA();
56 
57  auto PA = getLoopPassPreservedAnalyses();
59  PA.preserve<MemorySSAAnalysis>();
60  return PA;
61 }
62 
63 namespace {
64 
65 class LoopRotateLegacyPass : public LoopPass {
66  unsigned MaxHeaderSize;
67 
68 public:
69  static char ID; // Pass ID, replacement for typeid
70  LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1) : LoopPass(ID) {
72  if (SpecifiedMaxHeaderSize == -1)
73  MaxHeaderSize = DefaultRotationThreshold;
74  else
75  MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize);
76  }
77 
78  // LCSSA form makes instruction renaming easier.
79  void getAnalysisUsage(AnalysisUsage &AU) const override {
85  }
87  }
88 
89  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
90  if (skipLoop(L))
91  return false;
92  Function &F = *L->getHeader()->getParent();
93 
94  auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
95  const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
96  auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
97  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
98  auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
99  auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
100  auto *SE = SEWP ? &SEWP->getSE() : nullptr;
101  const SimplifyQuery SQ = getBestSimplifyQuery(*this, F);
104  MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
105  MSSAU = MemorySSAUpdater(MSSA);
106  }
107  return LoopRotation(L, LI, TTI, AC, DT, SE,
108  MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, SQ,
109  false, MaxHeaderSize, false);
110  }
111 };
112 }
113 
114 char LoopRotateLegacyPass::ID = 0;
115 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
116  false, false)
121 INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
122  false)
123 
124 Pass *llvm::createLoopRotatePass(int MaxHeaderSize) {
125  return new LoopRotateLegacyPass(MaxHeaderSize);
126 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:82
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This header provides classes for managing a pipeline of passes over loops in LLVM IR...
An immutable pass that tracks lazily created AssumptionCache objects.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
F(f)
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
AnalysisUsage & addRequired()
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:133
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
Legacy analysis pass which computes MemorySSA.
Definition: MemorySSA.h:963
INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false, false) INITIALIZE_PASS_END(LoopRotateLegacyPass
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:703
BlockT * getHeader() const
Definition: LoopInfo.h:102
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
Represent the analysis usage information of a pass.
const T * getPointer() const
Definition: Optional.h:253
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)
Convert a loop into a loop with bottom test.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
void initializeLoopRotateLegacyPassPass(PassRegistry &)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
loop Rotate Loops
void verifyMemorySSA() const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1848
loop rotate
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:924
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
bool hasValue() const
Definition: Optional.h:259
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:510
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass&#39;s AnalysisUsage.
Definition: LoopUtils.cpp:136
LoopRotatePass(bool EnableHeaderDuplication=true)
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
A container for analyses that lazily runs them and caches their results.
This pass exposes codegen information to IR-level passes.
Pass * createLoopRotatePass(int MaxHeaderSize=-1)
static cl::opt< unsigned > DefaultRotationThreshold("rotation-max-header-size", cl::init(16), cl::Hidden, cl::desc("The default maximum header size for automatic loop rotation"))