LLVM  12.0.0git
LoopPass.cpp
Go to the documentation of this file.
1 //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
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 LoopPass and LPPassManager. All loop optimization
10 // and transformation passes are derived from LoopPass. LPPassManager is
11 // responsible for managing LoopPasses.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/Analysis/LoopPass.h"
17 #include "llvm/IR/Dominators.h"
18 #include "llvm/IR/LLVMContext.h"
19 #include "llvm/IR/OptBisect.h"
20 #include "llvm/IR/PassManager.h"
21 #include "llvm/IR/PassTimingInfo.h"
22 #include "llvm/IR/PrintPasses.h"
23 #include "llvm/IR/StructuralHash.h"
24 #include "llvm/InitializePasses.h"
25 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/Timer.h"
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "loop-pass-manager"
32 
33 namespace {
34 
35 /// PrintLoopPass - Print a Function corresponding to a Loop.
36 ///
37 class PrintLoopPassWrapper : public LoopPass {
38  raw_ostream &OS;
39  std::string Banner;
40 
41 public:
42  static char ID;
43  PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {}
44  PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)
45  : LoopPass(ID), OS(OS), Banner(Banner) {}
46 
47  void getAnalysisUsage(AnalysisUsage &AU) const override {
48  AU.setPreservesAll();
49  }
50 
51  bool runOnLoop(Loop *L, LPPassManager &) override {
52  auto BBI = llvm::find_if(L->blocks(), [](BasicBlock *BB) { return BB; });
53  if (BBI != L->blocks().end() &&
54  isFunctionInPrintList((*BBI)->getParent()->getName())) {
55  printLoop(*L, OS, Banner);
56  }
57  return false;
58  }
59 
60  StringRef getPassName() const override { return "Print Loop IR"; }
61 };
62 
64 }
65 
66 //===----------------------------------------------------------------------===//
67 // LPPassManager
68 //
69 
70 char LPPassManager::ID = 0;
71 
74  LI = nullptr;
75  CurrentLoop = nullptr;
76 }
77 
78 // Insert loop into loop nest (LoopInfo) and loop queue (LQ).
80  if (L.isOutermost()) {
81  // This is the top level loop.
82  LQ.push_front(&L);
83  return;
84  }
85 
86  // Insert L into the loop queue after the parent loop.
87  for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
88  if (*I == L.getParentLoop()) {
89  // deque does not support insert after.
90  ++I;
91  LQ.insert(I, 1, &L);
92  return;
93  }
94  }
95 }
96 
97 // Recurse through all subloops and all loops into LQ.
98 static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
99  LQ.push_back(L);
100  for (Loop *I : reverse(*L))
101  addLoopIntoQueue(I, LQ);
102 }
103 
104 /// Pass Manager itself does not invalidate any analysis info.
106  // LPPassManager needs LoopInfo. In the long term LoopInfo class will
107  // become part of LPPassManager.
108  Info.addRequired<LoopInfoWrapperPass>();
109  Info.addRequired<DominatorTreeWrapperPass>();
110  Info.setPreservesAll();
111 }
112 
114  assert((&L == CurrentLoop || CurrentLoop->contains(&L)) &&
115  "Must not delete loop outside the current loop tree!");
116  // If this loop appears elsewhere within the queue, we also need to remove it
117  // there. However, we have to be careful to not remove the back of the queue
118  // as that is assumed to match the current loop.
119  assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!");
120  llvm::erase_value(LQ, &L);
121 
122  if (&L == CurrentLoop) {
123  CurrentLoopDeleted = true;
124  // Add this loop back onto the back of the queue to preserve our invariants.
125  LQ.push_back(&L);
126  }
127 }
128 
129 /// run - Execute all of the passes scheduled for execution. Keep track of
130 /// whether any of the passes modifies the function, and if so, return true.
132  auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
133  LI = &LIWP.getLoopInfo();
134  Module &M = *F.getParent();
135 #if 0
136  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
137 #endif
138  bool Changed = false;
139 
140  // Collect inherited analysis from Module level pass manager.
142 
143  // Populate the loop queue in reverse program order. There is no clear need to
144  // process sibling loops in either forward or reverse order. There may be some
145  // advantage in deleting uses in a later loop before optimizing the
146  // definitions in an earlier loop. If we find a clear reason to process in
147  // forward order, then a forward variant of LoopPassManager should be created.
148  //
149  // Note that LoopInfo::iterator visits loops in reverse program
150  // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
151  // reverses the order a third time by popping from the back.
152  for (Loop *L : reverse(*LI))
153  addLoopIntoQueue(L, LQ);
154 
155  if (LQ.empty()) // No loops, skip calling finalizers
156  return false;
157 
158  // Initialization
159  for (Loop *L : LQ) {
160  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
162  Changed |= P->doInitialization(L, *this);
163  }
164  }
165 
166  // Walk Loops
167  unsigned InstrCount, FunctionSize = 0;
168  StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
169  bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
170  // Collect the initial size of the module and the function we're looking at.
171  if (EmitICRemark) {
172  InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
173  FunctionSize = F.getInstructionCount();
174  }
175  while (!LQ.empty()) {
176  CurrentLoopDeleted = false;
177  CurrentLoop = LQ.back();
178 
179  // Run all passes on the current Loop.
180  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
182 
183  llvm::TimeTraceScope LoopPassScope("RunLoopPass", P->getPassName());
184 
186  CurrentLoop->getHeader()->getName());
188 
190 
191  bool LocalChanged = false;
192  {
193  PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
194  TimeRegion PassTimer(getPassTimer(P));
195 #ifdef EXPENSIVE_CHECKS
196  uint64_t RefHash = StructuralHash(F);
197 #endif
198  LocalChanged = P->runOnLoop(CurrentLoop, *this);
199 
200 #ifdef EXPENSIVE_CHECKS
201  if (!LocalChanged && (RefHash != StructuralHash(F))) {
202  llvm::errs() << "Pass modifies its input and doesn't report it: "
203  << P->getPassName() << "\n";
204  llvm_unreachable("Pass modifies its input and doesn't report it");
205  }
206 #endif
207 
208  Changed |= LocalChanged;
209  if (EmitICRemark) {
210  unsigned NewSize = F.getInstructionCount();
211  // Update the size of the function, emit a remark, and update the
212  // size of the module.
213  if (NewSize != FunctionSize) {
214  int64_t Delta = static_cast<int64_t>(NewSize) -
215  static_cast<int64_t>(FunctionSize);
217  FunctionToInstrCount, &F);
218  InstrCount = static_cast<int64_t>(InstrCount) + Delta;
219  FunctionSize = NewSize;
220  }
221  }
222  }
223 
224  if (LocalChanged)
226  CurrentLoopDeleted ? "<deleted loop>"
227  : CurrentLoop->getName());
229 
230  if (!CurrentLoopDeleted) {
231  // Manually check that this loop is still healthy. This is done
232  // instead of relying on LoopInfo::verifyLoop since LoopInfo
233  // is a function pass and it's really expensive to verify every
234  // loop in the function every time. That level of checking can be
235  // enabled with the -verify-loop-info option.
236  {
237  TimeRegion PassTimer(getPassTimer(&LIWP));
238  CurrentLoop->verifyLoop();
239  }
240  // Here we apply same reasoning as in the above case. Only difference
241  // is that LPPassManager might run passes which do not require LCSSA
242  // form (LoopPassPrinter for example). We should skip verification for
243  // such passes.
244  // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the
245  // verification!
246 #if 0
248  assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI));
249 #endif
250 
251  // Then call the regular verifyAnalysis functions.
253 
254  F.getContext().yield();
255  }
256 
257  if (LocalChanged)
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 static std::string getDescription(const Loop &L) {
370  return "loop";
371 }
372 
373 bool LoopPass::skipLoop(const Loop *L) const {
374  const Function *F = L->getHeader()->getParent();
375  if (!F)
376  return false;
377  // Check the opt bisect limit.
378  OptPassGate &Gate = F->getContext().getOptPassGate();
379  if (Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(*L)))
380  return true;
381  // Check for the OptimizeNone attribute.
382  if (F->hasOptNone()) {
383  // FIXME: Report this to dbgs() only once per function.
384  LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function "
385  << F->getName() << "\n");
386  // FIXME: Delete loop from pass manager's queue?
387  return true;
388  }
389  return false;
390 }
391 
394 }
395 
397 INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
398  false, false)
PMTopLevelManager * TPM
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
bool preserveHigherLevelAnalysis(Pass *P)
PassManagerType
Different types of internal pass managers.
Definition: Pass.h:52
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:67
Extensions to this class implement mechanisms to disable passes and individual optimizations at compi...
Definition: OptBisect.h:26
The TimeTraceScope is a helper class to call the begin and end functions of the time trace profiler.
Definition: TimeProfiler.h:65
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
void assignPassManager(PMStack &PMS, PassManagerType PMT) override
Assign pass manager to manage this pass.
Definition: LoopPass.cpp:334
F(f)
static unsigned InstrCount
void dumpPassInfo(Pass *P, enum PassDebuggingString S1, enum PassDebuggingString S2, StringRef Msg)
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:76
bool mustPreserveAnalysisID(char &AID) const
mustPreserveAnalysisID - This method serves the same function as getAnalysisIfAvailable,...
Definition: Pass.cpp:64
virtual bool shouldRunPass(const Pass *P, StringRef IRDescription)
IRDescription is a textual description of the IR unit the pass is running over.
Definition: OptBisect.h:32
PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers.
Timer * getPassTimer(Pass *)
Request the timer for this legacy-pass-manager's pass instance.
The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...
Definition: Timer.h:140
void schedulePass(Pass *P)
Schedule pass P for execution.
void freePass(Pass *P, StringRef Msg, enum PassDebuggingString)
Remove P.
bool isOutermost() const
Return true if the loop does not have a parent (natural) loop.
Definition: LoopInfo.h:168
void verifyPreservedAnalysis(Pass *P)
verifyPreservedAnalysis – Verify analysis presreved by pass P.
void populateInheritedAnalysis(PMStack &PMS)
This header defines classes/functions to handle pass execution timing information with interfaces for...
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...
virtual bool isEnabled() const
isEnabled() should return true before calling shouldRunPass().
Definition: OptBisect.h:37
PassManagerPrettyStackEntry - This is used to print informative information about what pass is runnin...
BlockT * getHeader() const
Definition: LoopInfo.h:104
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:151
Analysis containing CSE Info
Definition: CSEInfo.cpp:25
#define P(N)
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
static std::string getDescription(const Loop &L)
Definition: LoopPass.cpp:369
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:105
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static char ID
Definition: LoopPass.h:77
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
bool skipLoop(const Loop *L) const
Optional passes call this function to check whether the pass should be skipped.
Definition: LoopPass.cpp:373
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
uint64_t Offset
LPPassManager.
Definition: Pass.h:57
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.
uint32_t Index
unsigned initSizeRemarkInfo(Module &M, StringMap< std::pair< unsigned, unsigned >> &FunctionToInstrCount)
Set the initial size of the module if the user has specified that they want remarks for size.
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:113
bool isFunctionInPrintList(StringRef FunctionName)
Definition: PrintPasses.cpp:83
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:108
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
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
Definition: LoopInfo.h:113
StringRef getName() const
Definition: LoopInfo.h:862
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:295
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:59
void addLoop(Loop &L)
Definition: LoopPass.cpp:79
LoopPass * getContainedPass(unsigned N)
Definition: LoopPass.h:96
void push(PMDataManager *PM)
PMDataManager provides the common place to manage the analysis data used by pass managers.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:1675
PMDataManager * top() const
bool runOnFunction(Function &F) override
run - Execute all of the passes scheduled for execution.
Definition: LoopPass.cpp:131
static void addLoopIntoQueue(Loop *L, std::deque< Loop * > &LQ)
Definition: LoopPass.cpp:98
unsigned getNumContainedPasses() const
bool empty() const
bool isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:461
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1249
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:285
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
Pass * getAsPass() override
Definition: LoopPass.h:91
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:278
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:338
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1525
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:178
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop's contents as LLVM's text IR assembly.
Definition: LoopInfo.cpp:959
void dumpPreservedSet(const Pass *P) const
void initializeLCSSAVerificationPassPass(PassRegistry &)
void emitInstrCountChangedRemark(Pass *P, Module &M, int64_t Delta, unsigned CountBefore, StringMap< std::pair< unsigned, unsigned >> &FunctionToInstrCount, Function *F=nullptr)
Emit a remark signifying that the number of IR instructions in the module changed.