LLVM  7.0.0svn
LoopPass.cpp
Go to the documentation of this file.
1 //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements LoopPass and LPPassManager. All loop optimization
11 // and transformation passes are derived from LoopPass. LPPassManager is
12 // responsible for managing LoopPasses.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Analysis/LoopPass.h"
18 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/LLVMContext.h"
21 #include "llvm/IR/OptBisect.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/Timer.h"
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "loop-pass-manager"
29 
30 namespace {
31 
32 /// PrintLoopPass - Print a Function corresponding to a Loop.
33 ///
34 class PrintLoopPassWrapper : public LoopPass {
35  raw_ostream &OS;
36  std::string Banner;
37 
38 public:
39  static char ID;
40  PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {}
41  PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)
42  : LoopPass(ID), OS(OS), Banner(Banner) {}
43 
44  void getAnalysisUsage(AnalysisUsage &AU) const override {
45  AU.setPreservesAll();
46  }
47 
48  bool runOnLoop(Loop *L, LPPassManager &) override {
49  auto BBI = llvm::find_if(L->blocks(), [](BasicBlock *BB) { return BB; });
50  if (BBI != L->blocks().end() &&
51  isFunctionInPrintList((*BBI)->getParent()->getName())) {
52  printLoop(*L, OS, Banner);
53  }
54  return false;
55  }
56 
57  StringRef getPassName() const override { return "Print Loop IR"; }
58 };
59 
61 }
62 
63 //===----------------------------------------------------------------------===//
64 // LPPassManager
65 //
66 
67 char LPPassManager::ID = 0;
68 
71  LI = nullptr;
72  CurrentLoop = nullptr;
73 }
74 
75 // Insert loop into loop nest (LoopInfo) and loop queue (LQ).
77  if (!L.getParentLoop()) {
78  // This is the top level loop.
79  LQ.push_front(&L);
80  return;
81  }
82 
83  // Insert L into the loop queue after the parent loop.
84  for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
85  if (*I == L.getParentLoop()) {
86  // deque does not support insert after.
87  ++I;
88  LQ.insert(I, 1, &L);
89  return;
90  }
91  }
92 }
93 
94 /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
95 /// all loop passes.
97  BasicBlock *To, Loop *L) {
98  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
100  LP->cloneBasicBlockAnalysis(From, To, L);
101  }
102 }
103 
104 /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
106  if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
107  for (Instruction &I : *BB) {
109  }
110  }
111  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
113  LP->deleteAnalysisValue(V, L);
114  }
115 }
116 
117 /// Invoke deleteAnalysisLoop hook for all passes.
119  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
121  LP->deleteAnalysisLoop(L);
122  }
123 }
124 
125 
126 // Recurse through all subloops and all loops into LQ.
127 static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
128  LQ.push_back(L);
129  for (Loop *I : reverse(*L))
130  addLoopIntoQueue(I, LQ);
131 }
132 
133 /// Pass Manager itself does not invalidate any analysis info.
135  // LPPassManager needs LoopInfo. In the long term LoopInfo class will
136  // become part of LPPassManager.
139  Info.setPreservesAll();
140 }
141 
143  assert((&L == CurrentLoop || CurrentLoop->contains(&L)) &&
144  "Must not delete loop outside the current loop tree!");
145  // If this loop appears elsewhere within the queue, we also need to remove it
146  // there. However, we have to be careful to not remove the back of the queue
147  // as that is assumed to match the current loop.
148  assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!");
149  LQ.erase(std::remove(LQ.begin(), LQ.end(), &L), LQ.end());
150 
151  if (&L == CurrentLoop) {
152  CurrentLoopDeleted = true;
153  // Add this loop back onto the back of the queue to preserve our invariants.
154  LQ.push_back(&L);
155  }
156 }
157 
158 /// run - Execute all of the passes scheduled for execution. Keep track of
159 /// whether any of the passes modifies the function, and if so, return true.
161  auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
162  LI = &LIWP.getLoopInfo();
163  Module &M = *F.getParent();
164 #if 0
165  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
166 #endif
167  bool Changed = false;
168 
169  // Collect inherited analysis from Module level pass manager.
171 
172  // Populate the loop queue in reverse program order. There is no clear need to
173  // process sibling loops in either forward or reverse order. There may be some
174  // advantage in deleting uses in a later loop before optimizing the
175  // definitions in an earlier loop. If we find a clear reason to process in
176  // forward order, then a forward variant of LoopPassManager should be created.
177  //
178  // Note that LoopInfo::iterator visits loops in reverse program
179  // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
180  // reverses the order a third time by popping from the back.
181  for (Loop *L : reverse(*LI))
182  addLoopIntoQueue(L, LQ);
183 
184  if (LQ.empty()) // No loops, skip calling finalizers
185  return false;
186 
187  // Initialization
188  for (Loop *L : LQ) {
189  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
191  Changed |= P->doInitialization(L, *this);
192  }
193  }
194 
195  // Walk Loops
196  while (!LQ.empty()) {
197  CurrentLoopDeleted = false;
198  CurrentLoop = LQ.back();
199 
200  // Run all passes on the current Loop.
201  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
203 
205  CurrentLoop->getHeader()->getName());
206  dumpRequiredSet(P);
207 
209 
210  {
211  PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
212  TimeRegion PassTimer(getPassTimer(P));
213  unsigned InstrCount = initSizeRemarkInfo(M);
214  Changed |= P->runOnLoop(CurrentLoop, *this);
215  emitInstrCountChangedRemark(P, M, InstrCount);
216  }
217 
218  if (Changed)
220  CurrentLoopDeleted ? "<deleted loop>"
221  : CurrentLoop->getName());
222  dumpPreservedSet(P);
223 
224  if (CurrentLoopDeleted) {
225  // Notify passes that the loop is being deleted.
226  deleteSimpleAnalysisLoop(CurrentLoop);
227  } else {
228  // Manually check that this loop is still healthy. This is done
229  // instead of relying on LoopInfo::verifyLoop since LoopInfo
230  // is a function pass and it's really expensive to verify every
231  // loop in the function every time. That level of checking can be
232  // enabled with the -verify-loop-info option.
233  {
234  TimeRegion PassTimer(getPassTimer(&LIWP));
235  CurrentLoop->verifyLoop();
236  }
237  // Here we apply same reasoning as in the above case. Only difference
238  // is that LPPassManager might run passes which do not require LCSSA
239  // form (LoopPassPrinter for example). We should skip verification for
240  // such passes.
241  // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the
242  // verification!
243 #if 0
245  assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI));
246 #endif
247 
248  // Then call the regular verifyAnalysis functions.
250 
251  F.getContext().yield();
252  }
253 
257  CurrentLoopDeleted ? "<deleted>"
258  : CurrentLoop->getHeader()->getName(),
259  ON_LOOP_MSG);
260 
261  if (CurrentLoopDeleted)
262  // Do not run other passes on this loop.
263  break;
264  }
265 
266  // If the loop was deleted, release all the loop passes. This frees up
267  // some memory, and avoids trouble with the pass manager trying to call
268  // verifyAnalysis on them.
269  if (CurrentLoopDeleted) {
270  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
272  freePass(P, "<deleted>", ON_LOOP_MSG);
273  }
274  }
275 
276  // Pop the loop from queue after running all passes.
277  LQ.pop_back();
278  }
279 
280  // Finalization
281  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
283  Changed |= P->doFinalization();
284  }
285 
286  return Changed;
287 }
288 
289 /// Print passes managed by this manager
291  errs().indent(Offset*2) << "Loop Pass Manager\n";
292  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
294  P->dumpPassStructure(Offset + 1);
295  dumpLastUses(P, Offset+1);
296  }
297 }
298 
299 
300 //===----------------------------------------------------------------------===//
301 // LoopPass
302 
304  const std::string &Banner) const {
305  return new PrintLoopPassWrapper(O, Banner);
306 }
307 
308 // Check if this pass is suitable for the current LPPassManager, if
309 // available. This pass P is not suitable for a LPPassManager if P
310 // is not preserving higher level analysis info used by other
311 // LPPassManager passes. In such case, pop LPPassManager from the
312 // stack. This will force assignPassManager() to create new
313 // LPPassManger as expected.
315 
316  // Find LPPassManager
317  while (!PMS.empty() &&
319  PMS.pop();
320 
321  // If this pass is destroying high level information that is used
322  // by other passes that are managed by LPM then do not insert
323  // this pass in current LPM. Use new LPPassManager.
324  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
325  !PMS.top()->preserveHigherLevelAnalysis(this))
326  PMS.pop();
327 }
328 
329 /// Assign pass manager to manage this pass.
331  PassManagerType PreferredType) {
332  // Find LPPassManager
333  while (!PMS.empty() &&
335  PMS.pop();
336 
337  LPPassManager *LPPM;
339  LPPM = (LPPassManager*)PMS.top();
340  else {
341  // Create new Loop Pass Manager if it does not exist.
342  assert (!PMS.empty() && "Unable to create Loop Pass Manager");
343  PMDataManager *PMD = PMS.top();
344 
345  // [1] Create new Loop Pass Manager
346  LPPM = new LPPassManager();
347  LPPM->populateInheritedAnalysis(PMS);
348 
349  // [2] Set up new manager's top level manager
350  PMTopLevelManager *TPM = PMD->getTopLevelManager();
351  TPM->addIndirectPassManager(LPPM);
352 
353  // [3] Assign manager to manage this new manager. This may create
354  // and push new managers into PMS
355  Pass *P = LPPM->getAsPass();
356  TPM->schedulePass(P);
357 
358  // [4] Push new manager into PMS
359  PMS.push(LPPM);
360  }
361 
362  LPPM->add(this);
363 }
364 
365 bool LoopPass::skipLoop(const Loop *L) const {
366  const Function *F = L->getHeader()->getParent();
367  if (!F)
368  return false;
369  // Check the opt bisect limit.
371  if (!Context.getOptPassGate().shouldRunPass(this, *L))
372  return true;
373  // Check for the OptimizeNone attribute.
374  if (F->hasFnAttribute(Attribute::OptimizeNone)) {
375  // FIXME: Report this to dbgs() only once per function.
376  LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function "
377  << F->getName() << "\n");
378  // FIXME: Delete loop from pass manager's queue?
379  return true;
380  }
381  return false;
382 }
383 
385 INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
386  false, false)
PMTopLevelManager * TPM
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
bool preserveHigherLevelAnalysis(Pass *P)
PassManagerType
Different types of internal pass managers.
Definition: Pass.h:54
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
LLVMContext & Context
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
virtual void dumpPassStructure(unsigned Offset=0)
Definition: Pass.cpp:68
void dumpLastUses(Pass *P, unsigned Offset) const
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:183
virtual void deleteAnalysisLoop(Loop *L)
Delete analysis info associated with Loop L.
Definition: LoopPass.h:88
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
StringRef getPassName() const override
getPassName - Return a nice clean name for a pass.
Definition: LoopPass.h:110
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:307
void assignPassManager(PMStack &PMS, PassManagerType PMT) override
Assign pass manager to manage this pass.
Definition: LoopPass.cpp:330
F(f)
void yield()
Calls the yield callback (if applicable).
static unsigned InstrCount
void emitInstrCountChangedRemark(Pass *P, Module &M, unsigned CountBefore)
Emit a remark signifying that the number of IR instructions in the module changed.
void dumpPassInfo(Pass *P, enum PassDebuggingString S1, enum PassDebuggingString S2, StringRef Msg)
bool mustPreserveAnalysisID(char &AID) const
mustPreserveAnalysisID - This method serves the same function as getAnalysisIfAvailable, but works if you just have an AnalysisID.
Definition: Pass.cpp:63
PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers...
Timer * getPassTimer(Pass *)
If TimingInfo is enabled then start pass timer.
static void addLoopIntoQueue(Loop *L, std::deque< Loop *> &LQ)
Definition: LoopPass.cpp:127
The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...
Definition: Timer.h:141
virtual bool shouldRunPass(const Pass *P, const Module &U)
Definition: OptBisect.h:36
void schedulePass(Pass *P)
Schedule pass P for execution.
AnalysisUsage & addRequired()
void freePass(Pass *P, StringRef Msg, enum PassDebuggingString)
Remove P.
void deleteSimpleAnalysisLoop(Loop *L)
Invoke deleteAnalysisLoop hook for all passes that implement simple analysis interface.
Definition: LoopPass.cpp:118
void verifyPreservedAnalysis(Pass *P)
verifyPreservedAnalysis – Verify analysis presreved by pass P.
void populateInheritedAnalysis(PMStack &PMS)
PMStack - This class implements a stack data structure of PMDataManager pointers. ...
void initializeAnalysisImpl(Pass *P)
All Required analyses should be available to the pass as it runs! Here we fill in the AnalysisImpls m...
PassManagerPrettyStackEntry - This is used to print informative information about what pass is runnin...
BlockT * getHeader() const
Definition: LoopInfo.h:100
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:237
OptPassGate & getOptPassGate() const
Access the object which can disable optional passes and individual optimizations at compile time...
Pass * createPrinterPass(raw_ostream &O, const std::string &Banner) const override
getPrinterPass - Get a pass to print the function corresponding to a Loop.
Definition: LoopPass.cpp:303
void add(Pass *P, bool ProcessAnalysis=true)
Add pass P into the PassVector.
This header provides classes for managing per-loop analyses.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
virtual bool doInitialization(Loop *L, LPPassManager &LPM)
Definition: LoopPass.h:46
#define P(N)
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
virtual bool doFinalization()
Definition: LoopPass.h:52
void addIndirectPassManager(PMDataManager *Manager)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
virtual PassManagerType getPassManagerType() const
void getAnalysisUsage(AnalysisUsage &Info) const override
Pass Manager itself does not invalidate any analysis info.
Definition: LoopPass.cpp:134
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:936
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:193
static char ID
Definition: LoopPass.h:99
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:34
bool skipLoop(const Loop *L) const
Optional passes call this function to check whether the pass should be skipped.
Definition: LoopPass.cpp:365
void deleteSimpleAnalysisValue(Value *V, Loop *L)
deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes that implement simple anal...
Definition: LoopPass.cpp:105
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:110
LPPassManager.
Definition: Pass.h:59
void recordAvailableAnalysis(Pass *P)
Augment AvailableAnalysis by adding analysis made available by pass P.
void dumpRequiredSet(const Pass *P) const
void removeNotPreservedAnalysis(Pass *P)
Remove Analysis that is not preserved by the pass.
void removeDeadPasses(Pass *P, StringRef Msg, enum PassDebuggingString)
Remove dead passes used by P.
This file declares the interface for bisecting optimizations.
void markLoopAsDeleted(Loop &L)
Definition: LoopPass.cpp:142
bool isFunctionInPrintList(StringRef FunctionName)
isFunctionInPrintList - returns true if a function should be printed via
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
void setPreservesAll()
Set by analyses that do not transform their input at all.
void dumpPassStructure(unsigned Offset) override
Print passes managed by this manager.
Definition: LoopPass.cpp:290
void preparePassManager(PMStack &PMS) override
Check if available pass managers are suitable for this pass or not.
Definition: LoopPass.cpp:314
virtual bool runOnLoop(Loop *L, LPPassManager &LPM)=0
LoopT * getParentLoop() const
Definition: LoopInfo.h:101
StringRef getName() const
Definition: LoopInfo.h:583
void cloneBasicBlockSimpleAnalysis(BasicBlock *From, BasicBlock *To, Loop *L)
SimpleAnalysis - Provides simple interface to update analysis info maintained by various passes...
Definition: LoopPass.cpp:96
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:445
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
void addLoop(Loop &L)
Definition: LoopPass.cpp:76
LoopPass * getContainedPass(unsigned N)
Definition: LoopPass.h:118
void push(PMDataManager *PM)
PMDataManager provides the common place to manage the analysis data used by pass managers.
unsigned initSizeRemarkInfo(Module &M)
Set the initial size of the module if the user has specified that they want remarks for size...
This file defines passes to print out IR in various granularities.
virtual void cloneBasicBlockAnalysis(BasicBlock *F, BasicBlock *T, Loop *L)
SimpleAnalysis - Provides simple interface to update analysis info maintained by various passes...
Definition: LoopPass.h:80
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
PMDataManager * top() const
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:565
LLVM Value Representation.
Definition: Value.h:73
virtual void deleteAnalysisValue(Value *V, Loop *L)
deleteAnalysisValue - Delete analysis info associated with value V.
Definition: LoopPass.h:83
bool runOnFunction(Function &F) override
run - Execute all of the passes scheduled for execution.
Definition: LoopPass.cpp:160
unsigned getNumContainedPasses() const
bool empty() const
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
The legacy pass manager&#39;s analysis pass to compute loop information.
Definition: LoopInfo.h:964
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:227
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
Pass * getAsPass() override
Definition: LoopPass.h:113
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:254
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:119
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:156
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop&#39;s contents as LLVM&#39;s text IR assembly.
Definition: LoopInfo.cpp:734
void dumpPreservedSet(const Pass *P) const