LLVM  8.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  unsigned InstrCount = 0;
197  bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
198  while (!LQ.empty()) {
199  CurrentLoopDeleted = false;
200  CurrentLoop = LQ.back();
201 
202  // Run all passes on the current Loop.
203  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
205 
207  CurrentLoop->getHeader()->getName());
208  dumpRequiredSet(P);
209 
211 
212  {
213  PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
214  TimeRegion PassTimer(getPassTimer(P));
215  if (EmitICRemark)
216  InstrCount = initSizeRemarkInfo(M);
217  Changed |= P->runOnLoop(CurrentLoop, *this);
218  if (EmitICRemark)
219  emitInstrCountChangedRemark(P, M, InstrCount);
220  }
221 
222  if (Changed)
224  CurrentLoopDeleted ? "<deleted loop>"
225  : CurrentLoop->getName());
226  dumpPreservedSet(P);
227 
228  if (CurrentLoopDeleted) {
229  // Notify passes that the loop is being deleted.
230  deleteSimpleAnalysisLoop(CurrentLoop);
231  } else {
232  // Manually check that this loop is still healthy. This is done
233  // instead of relying on LoopInfo::verifyLoop since LoopInfo
234  // is a function pass and it's really expensive to verify every
235  // loop in the function every time. That level of checking can be
236  // enabled with the -verify-loop-info option.
237  {
238  TimeRegion PassTimer(getPassTimer(&LIWP));
239  CurrentLoop->verifyLoop();
240  }
241  // Here we apply same reasoning as in the above case. Only difference
242  // is that LPPassManager might run passes which do not require LCSSA
243  // form (LoopPassPrinter for example). We should skip verification for
244  // such passes.
245  // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the
246  // verification!
247 #if 0
249  assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI));
250 #endif
251 
252  // Then call the regular verifyAnalysis functions.
254 
255  F.getContext().yield();
256  }
257 
261  CurrentLoopDeleted ? "<deleted>"
262  : CurrentLoop->getHeader()->getName(),
263  ON_LOOP_MSG);
264 
265  if (CurrentLoopDeleted)
266  // Do not run other passes on this loop.
267  break;
268  }
269 
270  // If the loop was deleted, release all the loop passes. This frees up
271  // some memory, and avoids trouble with the pass manager trying to call
272  // verifyAnalysis on them.
273  if (CurrentLoopDeleted) {
274  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
276  freePass(P, "<deleted>", ON_LOOP_MSG);
277  }
278  }
279 
280  // Pop the loop from queue after running all passes.
281  LQ.pop_back();
282  }
283 
284  // Finalization
285  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
287  Changed |= P->doFinalization();
288  }
289 
290  return Changed;
291 }
292 
293 /// Print passes managed by this manager
295  errs().indent(Offset*2) << "Loop Pass Manager\n";
296  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
298  P->dumpPassStructure(Offset + 1);
299  dumpLastUses(P, Offset+1);
300  }
301 }
302 
303 
304 //===----------------------------------------------------------------------===//
305 // LoopPass
306 
308  const std::string &Banner) const {
309  return new PrintLoopPassWrapper(O, Banner);
310 }
311 
312 // Check if this pass is suitable for the current LPPassManager, if
313 // available. This pass P is not suitable for a LPPassManager if P
314 // is not preserving higher level analysis info used by other
315 // LPPassManager passes. In such case, pop LPPassManager from the
316 // stack. This will force assignPassManager() to create new
317 // LPPassManger as expected.
319 
320  // Find LPPassManager
321  while (!PMS.empty() &&
323  PMS.pop();
324 
325  // If this pass is destroying high level information that is used
326  // by other passes that are managed by LPM then do not insert
327  // this pass in current LPM. Use new LPPassManager.
328  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
329  !PMS.top()->preserveHigherLevelAnalysis(this))
330  PMS.pop();
331 }
332 
333 /// Assign pass manager to manage this pass.
335  PassManagerType PreferredType) {
336  // Find LPPassManager
337  while (!PMS.empty() &&
339  PMS.pop();
340 
341  LPPassManager *LPPM;
343  LPPM = (LPPassManager*)PMS.top();
344  else {
345  // Create new Loop Pass Manager if it does not exist.
346  assert (!PMS.empty() && "Unable to create Loop Pass Manager");
347  PMDataManager *PMD = PMS.top();
348 
349  // [1] Create new Loop Pass Manager
350  LPPM = new LPPassManager();
351  LPPM->populateInheritedAnalysis(PMS);
352 
353  // [2] Set up new manager's top level manager
354  PMTopLevelManager *TPM = PMD->getTopLevelManager();
355  TPM->addIndirectPassManager(LPPM);
356 
357  // [3] Assign manager to manage this new manager. This may create
358  // and push new managers into PMS
359  Pass *P = LPPM->getAsPass();
360  TPM->schedulePass(P);
361 
362  // [4] Push new manager into PMS
363  PMS.push(LPPM);
364  }
365 
366  LPPM->add(this);
367 }
368 
369 bool LoopPass::skipLoop(const Loop *L) const {
370  const Function *F = L->getHeader()->getParent();
371  if (!F)
372  return false;
373  // Check the opt bisect limit.
375  if (!Context.getOptPassGate().shouldRunPass(this, *L))
376  return true;
377  // Check for the OptimizeNone attribute.
378  if (F->hasFnAttribute(Attribute::OptimizeNone)) {
379  // FIXME: Report this to dbgs() only once per function.
380  LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function "
381  << F->getName() << "\n");
382  // FIXME: Delete loop from pass manager's queue?
383  return true;
384  }
385  return false;
386 }
387 
389 INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
390  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:334
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:251
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:307
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:145
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
bool shouldEmitInstrCountChangedRemark()
Return true if size-info optimization remark is enabled, false otherwise.
Definition: Module.h:261
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:1046
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
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:369
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:294
void preparePassManager(PMStack &PMS) override
Check if available pass managers are suitable for this pass or not.
Definition: LoopPass.cpp:318
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:459
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:295
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:260
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
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:671
void dumpPreservedSet(const Pass *P) const