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