LLVM  6.0.0svn
RegionPass.cpp
Go to the documentation of this file.
1 //===- RegionPass.cpp - Region Pass and Region 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 RegionPass and RGPassManager. All region optimization
11 // and transformation passes are derived from RegionPass. RGPassManager is
12 // responsible for managing RegionPasses.
13 // Most of this code has been COPIED from LoopPass.cpp
14 //
15 //===----------------------------------------------------------------------===//
18 #include "llvm/IR/OptBisect.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/Timer.h"
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "regionpassmgr"
25 
26 //===----------------------------------------------------------------------===//
27 // RGPassManager
28 //
29 
30 char RGPassManager::ID = 0;
31 
34  skipThisRegion = false;
35  redoThisRegion = false;
36  RI = nullptr;
37  CurrentRegion = nullptr;
38 }
39 
40 // Recurse through all subregions and all regions into RQ.
41 static void addRegionIntoQueue(Region &R, std::deque<Region *> &RQ) {
42  RQ.push_back(&R);
43  for (const auto &E : R)
44  addRegionIntoQueue(*E, RQ);
45 }
46 
47 /// Pass Manager itself does not invalidate any analysis info.
50  Info.setPreservesAll();
51 }
52 
53 /// run - Execute all of the passes scheduled for execution. Keep track of
54 /// whether any of the passes modifies the function, and if so, return true.
56  RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
57  bool Changed = false;
58 
59  // Collect inherited analysis from Module level pass manager.
61 
63 
64  if (RQ.empty()) // No regions, skip calling finalizers
65  return false;
66 
67  // Initialization
68  for (Region *R : RQ) {
69  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
71  Changed |= RP->doInitialization(R, *this);
72  }
73  }
74 
75  // Walk Regions
76  while (!RQ.empty()) {
77 
78  CurrentRegion = RQ.back();
79  skipThisRegion = false;
80  redoThisRegion = false;
81 
82  // Run all passes on the current Region.
83  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
85 
88  CurrentRegion->getNameStr());
89  dumpRequiredSet(P);
90  }
91 
93 
94  {
95  PassManagerPrettyStackEntry X(P, *CurrentRegion->getEntry());
96 
97  TimeRegion PassTimer(getPassTimer(P));
98  Changed |= P->runOnRegion(CurrentRegion, *this);
99  }
100 
102  if (Changed)
104  skipThisRegion ? "<deleted>" :
105  CurrentRegion->getNameStr());
106  dumpPreservedSet(P);
107  }
108 
109  if (!skipThisRegion) {
110  // Manually check that this region is still healthy. This is done
111  // instead of relying on RegionInfo::verifyRegion since RegionInfo
112  // is a function pass and it's really expensive to verify every
113  // Region in the function every time. That level of checking can be
114  // enabled with the -verify-region-info option.
115  {
116  TimeRegion PassTimer(getPassTimer(P));
117  CurrentRegion->verifyRegion();
118  }
119 
120  // Then call the regular verifyAnalysis functions.
122  }
123 
127  (!isPassDebuggingExecutionsOrMore() || skipThisRegion) ?
128  "<deleted>" : CurrentRegion->getNameStr(),
129  ON_REGION_MSG);
130 
131  if (skipThisRegion)
132  // Do not run other passes on this region.
133  break;
134  }
135 
136  // If the region was deleted, release all the region passes. This frees up
137  // some memory, and avoids trouble with the pass manager trying to call
138  // verifyAnalysis on them.
139  if (skipThisRegion)
140  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
141  Pass *P = getContainedPass(Index);
142  freePass(P, "<deleted>", ON_REGION_MSG);
143  }
144 
145  // Pop the region from queue after running all passes.
146  RQ.pop_back();
147 
148  if (redoThisRegion)
149  RQ.push_back(CurrentRegion);
150 
151  // Free all region nodes created in region passes.
152  RI->clearNodeCache();
153  }
154 
155  // Finalization
156  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
158  Changed |= P->doFinalization();
159  }
160 
161  // Print the region tree after all pass.
162  DEBUG(
163  dbgs() << "\nRegion tree of function " << F.getName()
164  << " after all region Pass:\n";
165  RI->dump();
166  dbgs() << "\n";
167  );
168 
169  return Changed;
170 }
171 
172 /// Print passes managed by this manager
174  errs().indent(Offset*2) << "Region Pass Manager\n";
175  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
176  Pass *P = getContainedPass(Index);
177  P->dumpPassStructure(Offset + 1);
178  dumpLastUses(P, Offset+1);
179  }
180 }
181 
182 namespace {
183 //===----------------------------------------------------------------------===//
184 // PrintRegionPass
185 class PrintRegionPass : public RegionPass {
186 private:
187  std::string Banner;
188  raw_ostream &Out; // raw_ostream to print on.
189 
190 public:
191  static char ID;
192  PrintRegionPass(const std::string &B, raw_ostream &o)
193  : RegionPass(ID), Banner(B), Out(o) {}
194 
195  void getAnalysisUsage(AnalysisUsage &AU) const override {
196  AU.setPreservesAll();
197  }
198 
199  bool runOnRegion(Region *R, RGPassManager &RGM) override {
200  Out << Banner;
201  for (const auto *BB : R->blocks()) {
202  if (BB)
203  BB->print(Out);
204  else
205  Out << "Printing <null> Block";
206  }
207 
208  return false;
209  }
210 
211  StringRef getPassName() const override { return "Print Region IR"; }
212 };
213 
214 char PrintRegionPass::ID = 0;
215 } //end anonymous namespace
216 
217 //===----------------------------------------------------------------------===//
218 // RegionPass
219 
220 // Check if this pass is suitable for the current RGPassManager, if
221 // available. This pass P is not suitable for a RGPassManager if P
222 // is not preserving higher level analysis info used by other
223 // RGPassManager passes. In such case, pop RGPassManager from the
224 // stack. This will force assignPassManager() to create new
225 // LPPassManger as expected.
227 
228  // Find RGPassManager
229  while (!PMS.empty() &&
231  PMS.pop();
232 
233 
234  // If this pass is destroying high level information that is used
235  // by other passes that are managed by LPM then do not insert
236  // this pass in current LPM. Use new RGPassManager.
237  if (PMS.top()->getPassManagerType() == PMT_RegionPassManager &&
238  !PMS.top()->preserveHigherLevelAnalysis(this))
239  PMS.pop();
240 }
241 
242 /// Assign pass manager to manage this pass.
244  PassManagerType PreferredType) {
245  // Find RGPassManager
246  while (!PMS.empty() &&
248  PMS.pop();
249 
250  RGPassManager *RGPM;
251 
252  // Create new Region Pass Manager if it does not exist.
254  RGPM = (RGPassManager*)PMS.top();
255  else {
256 
257  assert (!PMS.empty() && "Unable to create Region Pass Manager");
258  PMDataManager *PMD = PMS.top();
259 
260  // [1] Create new Region Pass Manager
261  RGPM = new RGPassManager();
262  RGPM->populateInheritedAnalysis(PMS);
263 
264  // [2] Set up new manager's top level manager
265  PMTopLevelManager *TPM = PMD->getTopLevelManager();
266  TPM->addIndirectPassManager(RGPM);
267 
268  // [3] Assign manager to manage this new manager. This may create
269  // and push new managers into PMS
270  TPM->schedulePass(RGPM);
271 
272  // [4] Push new manager into PMS
273  PMS.push(RGPM);
274  }
275 
276  RGPM->add(this);
277 }
278 
279 /// Get the printer pass
281  const std::string &Banner) const {
282  return new PrintRegionPass(Banner, O);
283 }
284 
286  Function &F = *R.getEntry()->getParent();
287  if (!F.getContext().getOptBisect().shouldRunPass(this, R))
288  return true;
289 
290  if (F.hasFnAttribute(Attribute::OptimizeNone)) {
291  // Report this only once per function.
292  if (R.getEntry() == &F.getEntryBlock())
293  DEBUG(dbgs() << "Skipping pass '" << getPassName()
294  << "' on function " << F.getName() << "\n");
295  return true;
296  }
297  return false;
298 }
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
bool shouldRunPass(const Pass *P, const UnitT &U)
Checks the bisect limit to determine if the specified pass should run.
Definition: OptBisect.cpp:97
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
virtual void dumpPassStructure(unsigned Offset=0)
Definition: Pass.cpp:59
void dumpLastUses(Pass *P, unsigned Offset) const
Pass * createPrinterPass(raw_ostream &O, const std::string &Banner) const override
Get a pass to print the LLVM IR in the region.
Definition: RegionPass.cpp:280
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
bool skipRegion(Region &R) const
Optional passes call this function to check whether the pass should be skipped.
Definition: RegionPass.cpp:285
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:254
void dumpPassInfo(Pass *P, enum PassDebuggingString S1, enum PassDebuggingString S2, StringRef Msg)
The pass manager to schedule RegionPasses.
Definition: RegionPass.h:89
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.
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.
AnalysisUsage & addRequired()
void freePass(Pass *P, StringRef Msg, enum PassDebuggingString)
Remove P.
virtual bool doInitialization(Region *R, RGPassManager &RGM)
Definition: RegionPass.h:64
void verifyPreservedAnalysis(Pass *P)
verifyPreservedAnalysis – Verify analysis presreved by pass P.
void populateInheritedAnalysis(PMStack &PMS)
static char ID
Definition: RegionPass.h:97
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...
RegionT * getTopLevelRegion() const
Definition: RegionInfo.h:863
bool isPassDebuggingExecutionsOrMore() const
isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions or higher is specified...
block_range blocks()
Returns a range view of the basic blocks in the region.
Definition: RegionInfo.h:619
#define F(x, y, z)
Definition: MD5.cpp:55
void add(Pass *P, bool ProcessAnalysis=true)
Add pass P into the PassVector.
virtual bool doFinalization()
Definition: RegionPass.h:65
const BasicBlock & getEntryBlock() const
Definition: Function.h:564
void dumpPassStructure(unsigned Offset) override
Print passes managed by this manager.
Definition: RegionPass.cpp:173
#define P(N)
void assignPassManager(PMStack &PMS, PassManagerType PMT=PMT_RegionPassManager) override
Assign pass manager to manage this pass.
Definition: RegionPass.cpp:243
void preparePassManager(PMStack &PMS) override
Check if available pass managers are suitable for this pass or not.
Definition: RegionPass.cpp:226
static void addRegionIntoQueue(Region &R, std::deque< Region *> &RQ)
Definition: RegionPass.cpp:41
A pass that runs on each Region in a function.
Definition: RegionPass.h:34
void addIndirectPassManager(PMDataManager *Manager)
virtual PassManagerType getPassManagerType() const
Represent the analysis usage information of a pass.
bool runOnFunction(Function &F) override
Execute all of the passes scheduled for execution.
Definition: RegionPass.cpp:55
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
Pass * getContainedPass(unsigned N)
Get passes contained by this manager.
Definition: RegionPass.h:118
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
#define E
Definition: LargeTest.cpp:27
void recordAvailableAnalysis(Pass *P)
Augment AvailableAnalysis by adding analysis made available by pass P.
#define B
Definition: LargeTest.cpp:24
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:323
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.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void setPreservesAll()
Set by analyses that do not transform their input at all.
std::string getNameStr() const
Returns the name of the Region.
void verifyRegion() const
Verify if the region is a correct region.
OptBisect & getOptBisect()
Access the object which manages optimization bisection for failure analysis.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
RGPassManager.
Definition: Pass.h:60
virtual bool runOnRegion(Region *R, RGPassManager &RGM)=0
Run the pass on a specific Region.
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())
PMDataManager * top() const
void clearNodeCache()
Clear the Node Cache for all Regions.
Definition: RegionInfo.h:868
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:44
#define DEBUG(X)
Definition: Debug.h:118
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
void getAnalysisUsage(AnalysisUsage &Info) const override
Pass Manager itself does not invalidate any analysis info.
Definition: RegionPass.cpp:48
void dumpPreservedSet(const Pass *P) const
StringRef getPassName() const override
getPassName - Return a nice clean name for a pass.
Definition: RegionPass.h:109