LLVM  14.0.0git
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/IR/PrintPasses.h"
19 #include "llvm/IR/StructuralHash.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/Timer.h"
23 using namespace llvm;
24 
25 #define DEBUG_TYPE "regionpassmgr"
26 
27 //===----------------------------------------------------------------------===//
28 // RGPassManager
29 //
30 
31 char RGPassManager::ID = 0;
32 
34  RI = nullptr;
35  CurrentRegion = nullptr;
36 }
37 
38 // Recurse through all subregions and all regions into RQ.
39 static void addRegionIntoQueue(Region &R, std::deque<Region *> &RQ) {
40  RQ.push_back(&R);
41  for (const auto &E : R)
42  addRegionIntoQueue(*E, RQ);
43 }
44 
45 /// Pass Manager itself does not invalidate any analysis info.
47  Info.addRequired<RegionInfoPass>();
48  Info.setPreservesAll();
49 }
50 
51 /// run - Execute all of the passes scheduled for execution. Keep track of
52 /// whether any of the passes modifies the function, and if so, return true.
54  RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
55  bool Changed = false;
56 
57  // Collect inherited analysis from Module level pass manager.
59 
61 
62  if (RQ.empty()) // No regions, skip calling finalizers
63  return false;
64 
65  // Initialization
66  for (Region *R : RQ) {
67  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
69  Changed |= RP->doInitialization(R, *this);
70  }
71  }
72 
73  // Walk Regions
74  while (!RQ.empty()) {
75 
76  CurrentRegion = RQ.back();
77 
78  // Run all passes on the current Region.
79  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
81 
84  CurrentRegion->getNameStr());
86  }
87 
89 
90  bool LocalChanged = false;
91  {
92  PassManagerPrettyStackEntry X(P, *CurrentRegion->getEntry());
93 
94  TimeRegion PassTimer(getPassTimer(P));
95 #ifdef EXPENSIVE_CHECKS
96  uint64_t RefHash = StructuralHash(F);
97 #endif
98  LocalChanged = P->runOnRegion(CurrentRegion, *this);
99 
100 #ifdef EXPENSIVE_CHECKS
101  if (!LocalChanged && (RefHash != StructuralHash(F))) {
102  llvm::errs() << "Pass modifies its input and doesn't report it: "
103  << P->getPassName() << "\n";
104  llvm_unreachable("Pass modifies its input and doesn't report it");
105  }
106 #endif
107 
108  Changed |= LocalChanged;
109  }
110 
112  if (LocalChanged)
114  CurrentRegion->getNameStr());
116  }
117 
118  // Manually check that this region is still healthy. This is done
119  // instead of relying on RegionInfo::verifyRegion since RegionInfo
120  // is a function pass and it's really expensive to verify every
121  // Region in the function every time. That level of checking can be
122  // enabled with the -verify-region-info option.
123  {
124  TimeRegion PassTimer(getPassTimer(P));
125  CurrentRegion->verifyRegion();
126  }
127 
128  // Then call the regular verifyAnalysis functions.
130 
131  if (LocalChanged)
136  ? "<deleted>"
137  : CurrentRegion->getNameStr(),
138  ON_REGION_MSG);
139  }
140 
141  // Pop the region from queue after running all passes.
142  RQ.pop_back();
143 
144  // Free all region nodes created in region passes.
145  RI->clearNodeCache();
146  }
147 
148  // Finalization
149  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
151  Changed |= P->doFinalization();
152  }
153 
154  // Print the region tree after all pass.
155  LLVM_DEBUG(dbgs() << "\nRegion tree of function " << F.getName()
156  << " after all region Pass:\n";
157  RI->dump(); dbgs() << "\n";);
158 
159  return Changed;
160 }
161 
162 /// Print passes managed by this manager
164  errs().indent(Offset*2) << "Region Pass Manager\n";
165  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
167  P->dumpPassStructure(Offset + 1);
168  dumpLastUses(P, Offset+1);
169  }
170 }
171 
172 namespace {
173 //===----------------------------------------------------------------------===//
174 // PrintRegionPass
175 class PrintRegionPass : public RegionPass {
176 private:
177  std::string Banner;
178  raw_ostream &Out; // raw_ostream to print on.
179 
180 public:
181  static char ID;
182  PrintRegionPass(const std::string &B, raw_ostream &o)
183  : RegionPass(ID), Banner(B), Out(o) {}
184 
185  void getAnalysisUsage(AnalysisUsage &AU) const override {
186  AU.setPreservesAll();
187  }
188 
189  bool runOnRegion(Region *R, RGPassManager &RGM) override {
190  if (!isFunctionInPrintList(R->getEntry()->getParent()->getName()))
191  return false;
192  Out << Banner;
193  for (const auto *BB : R->blocks()) {
194  if (BB)
195  BB->print(Out);
196  else
197  Out << "Printing <null> Block";
198  }
199 
200  return false;
201  }
202 
203  StringRef getPassName() const override { return "Print Region IR"; }
204 };
205 
206 char PrintRegionPass::ID = 0;
207 } //end anonymous namespace
208 
209 //===----------------------------------------------------------------------===//
210 // RegionPass
211 
212 // Check if this pass is suitable for the current RGPassManager, if
213 // available. This pass P is not suitable for a RGPassManager if P
214 // is not preserving higher level analysis info used by other
215 // RGPassManager passes. In such case, pop RGPassManager from the
216 // stack. This will force assignPassManager() to create new
217 // LPPassManger as expected.
219 
220  // Find RGPassManager
221  while (!PMS.empty() &&
223  PMS.pop();
224 
225 
226  // If this pass is destroying high level information that is used
227  // by other passes that are managed by LPM then do not insert
228  // this pass in current LPM. Use new RGPassManager.
229  if (PMS.top()->getPassManagerType() == PMT_RegionPassManager &&
230  !PMS.top()->preserveHigherLevelAnalysis(this))
231  PMS.pop();
232 }
233 
234 /// Assign pass manager to manage this pass.
236  PassManagerType PreferredType) {
237  // Find RGPassManager
238  while (!PMS.empty() &&
240  PMS.pop();
241 
242  RGPassManager *RGPM;
243 
244  // Create new Region Pass Manager if it does not exist.
246  RGPM = (RGPassManager*)PMS.top();
247  else {
248 
249  assert (!PMS.empty() && "Unable to create Region Pass Manager");
250  PMDataManager *PMD = PMS.top();
251 
252  // [1] Create new Region Pass Manager
253  RGPM = new RGPassManager();
254  RGPM->populateInheritedAnalysis(PMS);
255 
256  // [2] Set up new manager's top level manager
258  TPM->addIndirectPassManager(RGPM);
259 
260  // [3] Assign manager to manage this new manager. This may create
261  // and push new managers into PMS
262  TPM->schedulePass(RGPM);
263 
264  // [4] Push new manager into PMS
265  PMS.push(RGPM);
266  }
267 
268  RGPM->add(this);
269 }
270 
271 /// Get the printer pass
273  const std::string &Banner) const {
274  return new PrintRegionPass(Banner, O);
275 }
276 
277 static std::string getDescription(const Region &R) {
278  return "region";
279 }
280 
282  Function &F = *R.getEntry()->getParent();
283  OptPassGate &Gate = F.getContext().getOptPassGate();
284  if (Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(R)))
285  return true;
286 
287  if (F.hasOptNone()) {
288  // Report this only once per function.
289  if (R.getEntry() == &F.getEntryBlock())
290  LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName()
291  << "' on function " << F.getName() << "\n");
292  return true;
293  }
294  return false;
295 }
llvm::PMDataManager::recordAvailableAnalysis
void recordAvailableAnalysis(Pass *P)
Augment AvailableAnalysis by adding analysis made available by pass P.
Definition: LegacyPassManager.cpp:876
llvm::RGPassManager::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &Info) const override
Pass Manager itself does not invalidate any analysis info.
Definition: RegionPass.cpp:46
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::RegionPass::skipRegion
bool skipRegion(Region &R) const
Optional passes call this function to check whether the pass should be skipped.
Definition: RegionPass.cpp:281
llvm::RegionInfoBase::getTopLevelRegion
RegionT * getTopLevelRegion() const
Definition: RegionInfo.h:866
llvm::RegionPass::assignPassManager
void assignPassManager(PMStack &PMS, PassManagerType PMT=PMT_RegionPassManager) override
Assign pass manager to manage this pass.
Definition: RegionPass.cpp:235
RegionPass.h
llvm::Function
Definition: Function.h:62
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::PMTopLevelManager::schedulePass
void schedulePass(Pass *P)
Schedule pass P for execution.
Definition: LegacyPassManager.cpp:662
llvm::PMDataManager::dumpPassInfo
void dumpPassInfo(Pass *P, enum PassDebuggingString S1, enum PassDebuggingString S2, StringRef Msg)
Definition: LegacyPassManager.cpp:1183
llvm::OptPassGate::isEnabled
virtual bool isEnabled() const
isEnabled() should return true before calling shouldRunPass().
Definition: OptBisect.h:38
llvm::PassManagerType
PassManagerType
Different types of internal pass managers.
Definition: Pass.h:52
OptBisect.h
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
llvm::PMStack::push
void push(PMDataManager *PM)
Definition: LegacyPassManager.cpp:1696
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
llvm::ON_REGION_MSG
@ ON_REGION_MSG
Definition: LegacyPassManagers.h:102
llvm::PassManagerPrettyStackEntry
PassManagerPrettyStackEntry - This is used to print informative information about what pass is runnin...
Definition: LegacyPassManagers.h:109
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:208
llvm::RGPassManager::dumpPassStructure
void dumpPassStructure(unsigned Offset) override
Print passes managed by this manager.
Definition: RegionPass.cpp:163
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
PassTimingInfo.h
llvm::PMDataManager
PMDataManager provides the common place to manage the analysis data used by pass managers.
Definition: LegacyPassManagers.h:295
llvm::PMDataManager::dumpLastUses
void dumpLastUses(Pass *P, unsigned Offset) const
Definition: LegacyPassManager.cpp:1153
llvm::PMDataManager::getNumContainedPasses
unsigned getNumContainedPasses() const
Definition: LegacyPassManagers.h:378
llvm::TimeRegion
The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...
Definition: Timer.h:145
llvm::AArch64::RP
@ RP
Definition: AArch64ISelLowering.h:479
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::PMTopLevelManager::activeStack
PMStack activeStack
Definition: LegacyPassManagers.h:219
llvm::RegionInfoBase::dump
void dump() const
Definition: RegionInfoImpl.h:792
llvm::OptPassGate
Extensions to this class implement mechanisms to disable passes and individual optimizations at compi...
Definition: OptBisect.h:27
llvm::PMDataManager::dumpPreservedSet
void dumpPreservedSet(const Pass *P) const
Definition: LegacyPassManager.cpp:1233
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::PMDataManager::initializeAnalysisImpl
void initializeAnalysisImpl(Pass *P)
All Required analyses should be available to the pass as it runs! Here we fill in the AnalysisImpls m...
Definition: LegacyPassManager.cpp:1120
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::RegionBase::verifyRegion
void verifyRegion() const
Verify if the region is a correct region.
Definition: RegionInfoImpl.h:294
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::MODIFICATION_MSG
@ MODIFICATION_MSG
Definition: LegacyPassManagers.h:98
llvm::RegionInfoBase::clearNodeCache
void clearNodeCache()
Clear the Node Cache for all Regions.
Definition: RegionInfo.h:871
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
PrintPasses.h
llvm::PMStack::top
PMDataManager * top() const
Definition: LegacyPassManagers.h:143
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::PMStack::empty
bool empty() const
Definition: LegacyPassManagers.h:145
StructuralHash.h
llvm::RegionPass::preparePassManager
void preparePassManager(PMStack &PMS) override
Check if available pass managers are suitable for this pass or not.
Definition: RegionPass.cpp:218
Timer.h
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:207
llvm::RGPassManager::ID
static char ID
Definition: RegionPass.h:92
llvm::PMDataManager::getTopLevelManager
PMTopLevelManager * getTopLevelManager()
Definition: LegacyPassManagers.h:363
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
uint64_t
llvm::RegionBase::getEntry
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:322
llvm::getPassTimer
Timer * getPassTimer(Pass *)
Request the timer for this legacy-pass-manager's pass instance.
Definition: PassTimingInfo.cpp:153
llvm::PMDataManager::removeDeadPasses
void removeDeadPasses(Pass *P, StringRef Msg, enum PassDebuggingString)
Remove dead passes used by P.
Definition: LegacyPassManager.cpp:973
llvm::isFunctionInPrintList
bool isFunctionInPrintList(StringRef FunctionName)
Definition: PrintPasses.cpp:83
llvm::PMDataManager::preserveHigherLevelAnalysis
bool preserveHigherLevelAnalysis(Pass *P)
Definition: LegacyPassManager.cpp:893
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PMDataManager::dumpRequiredSet
void dumpRequiredSet(const Pass *P) const
Definition: LegacyPassManager.cpp:1224
llvm::RGPassManager
The pass manager to schedule RegionPasses.
Definition: RegionPass.h:86
llvm::RegionPass
A pass that runs on each Region in a function.
Definition: RegionPass.h:31
llvm::RegionInfoPass
Definition: RegionInfo.h:942
addRegionIntoQueue
static void addRegionIntoQueue(Region &R, std::deque< Region * > &RQ)
Definition: RegionPass.cpp:39
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::Pass::getPassName
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:76
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::EXECUTION_MSG
@ EXECUTION_MSG
Definition: LegacyPassManagers.h:97
llvm::PMDataManager::getPassManagerType
virtual PassManagerType getPassManagerType() const
Definition: LegacyPassManagers.h:382
llvm::PMStack::pop
void pop()
Definition: LegacyPassManager.cpp:1687
llvm::PMDataManager::verifyPreservedAnalysis
void verifyPreservedAnalysis(Pass *P)
verifyPreservedAnalysis – Verify analysis presreved by pass P.
Definition: LegacyPassManager.cpp:909
llvm::PMDataManager::removeNotPreservedAnalysis
void removeNotPreservedAnalysis(Pass *P)
Remove Analysis that is not preserved by the pass.
Definition: LegacyPassManager.cpp:927
llvm::PMStack
PMStack - This class implements a stack data structure of PMDataManager pointers.
Definition: LegacyPassManagers.h:136
llvm::RegionPass::createPrinterPass
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:272
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::PMDataManager::add
void add(Pass *P, bool ProcessAnalysis=true)
Add pass P into the PassVector.
Definition: LegacyPassManager.cpp:1024
llvm::PMDataManager::TPM
PMTopLevelManager * TPM
Definition: LegacyPassManagers.h:421
llvm::RegionBase::getNameStr
std::string getNameStr() const
Returns the name of the Region.
Definition: RegionInfoImpl.h:230
llvm::PMT_RegionPassManager
@ PMT_RegionPassManager
RGPassManager.
Definition: Pass.h:58
llvm::PMTopLevelManager::addIndirectPassManager
void addIndirectPassManager(PMDataManager *Manager)
Definition: LegacyPassManagers.h:210
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:496
llvm::PMTopLevelManager
PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers.
Definition: LegacyPassManagers.h:158
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::RGPassManager::RGPassManager
RGPassManager()
Definition: RegionPass.cpp:33
getDescription
static std::string getDescription(const Region &R)
Definition: RegionPass.cpp:277
llvm::RGPassManager::runOnFunction
bool runOnFunction(Function &F) override
Execute all of the passes scheduled for execution.
Definition: RegionPass.cpp:53
llvm::Region
Definition: RegionInfo.h:889
llvm::PMDataManager::isPassDebuggingExecutionsOrMore
bool isPassDebuggingExecutionsOrMore() const
isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions or higher is specified.
Definition: LegacyPassManager.cpp:66
raw_ostream.h
llvm::PMDataManager::populateInheritedAnalysis
void populateInheritedAnalysis(PMStack &PMS)
Definition: LegacyPassManagers.h:392
llvm::OptPassGate::shouldRunPass
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:33
llvm::RGPassManager::getContainedPass
Pass * getContainedPass(unsigned N)
Get passes contained by this manager.
Definition: RegionPass.h:113
Debug.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38