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/StructuralHash.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  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  Out << Banner;
191  for (const auto *BB : R->blocks()) {
192  if (BB)
193  BB->print(Out);
194  else
195  Out << "Printing <null> Block";
196  }
197 
198  return false;
199  }
200 
201  StringRef getPassName() const override { return "Print Region IR"; }
202 };
203 
204 char PrintRegionPass::ID = 0;
205 } //end anonymous namespace
206 
207 //===----------------------------------------------------------------------===//
208 // RegionPass
209 
210 // Check if this pass is suitable for the current RGPassManager, if
211 // available. This pass P is not suitable for a RGPassManager if P
212 // is not preserving higher level analysis info used by other
213 // RGPassManager passes. In such case, pop RGPassManager from the
214 // stack. This will force assignPassManager() to create new
215 // LPPassManger as expected.
217 
218  // Find RGPassManager
219  while (!PMS.empty() &&
221  PMS.pop();
222 
223 
224  // If this pass is destroying high level information that is used
225  // by other passes that are managed by LPM then do not insert
226  // this pass in current LPM. Use new RGPassManager.
227  if (PMS.top()->getPassManagerType() == PMT_RegionPassManager &&
228  !PMS.top()->preserveHigherLevelAnalysis(this))
229  PMS.pop();
230 }
231 
232 /// Assign pass manager to manage this pass.
234  PassManagerType PreferredType) {
235  // Find RGPassManager
236  while (!PMS.empty() &&
238  PMS.pop();
239 
240  RGPassManager *RGPM;
241 
242  // Create new Region Pass Manager if it does not exist.
244  RGPM = (RGPassManager*)PMS.top();
245  else {
246 
247  assert (!PMS.empty() && "Unable to create Region Pass Manager");
248  PMDataManager *PMD = PMS.top();
249 
250  // [1] Create new Region Pass Manager
251  RGPM = new RGPassManager();
252  RGPM->populateInheritedAnalysis(PMS);
253 
254  // [2] Set up new manager's top level manager
256  TPM->addIndirectPassManager(RGPM);
257 
258  // [3] Assign manager to manage this new manager. This may create
259  // and push new managers into PMS
260  TPM->schedulePass(RGPM);
261 
262  // [4] Push new manager into PMS
263  PMS.push(RGPM);
264  }
265 
266  RGPM->add(this);
267 }
268 
269 /// Get the printer pass
271  const std::string &Banner) const {
272  return new PrintRegionPass(Banner, O);
273 }
274 
275 static std::string getDescription(const Region &R) {
276  return "region";
277 }
278 
280  Function &F = *R.getEntry()->getParent();
281  OptPassGate &Gate = F.getContext().getOptPassGate();
282  if (Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(R)))
283  return true;
284 
285  if (F.hasOptNone()) {
286  // Report this only once per function.
287  if (R.getEntry() == &F.getEntryBlock())
288  LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName()
289  << "' on function " << F.getName() << "\n");
290  return true;
291  }
292  return false;
293 }
llvm::PMDataManager::recordAvailableAnalysis
void recordAvailableAnalysis(Pass *P)
Augment AvailableAnalysis by adding analysis made available by pass P.
Definition: LegacyPassManager.cpp:878
llvm::RGPassManager::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &Info) const override
Pass Manager itself does not invalidate any analysis info.
Definition: RegionPass.cpp:46
llvm
This file implements support for optimizing divisions by a constant.
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:279
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:233
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:664
llvm::PMDataManager::dumpPassInfo
void dumpPassInfo(Pass *P, enum PassDebuggingString S1, enum PassDebuggingString S2, StringRef Msg)
Definition: LegacyPassManager.cpp:1187
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:81
llvm::PMStack::push
void push(PMDataManager *PM)
Definition: LegacyPassManager.cpp:1700
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:103
llvm::PassManagerPrettyStackEntry
PassManagerPrettyStackEntry - This is used to print informative information about what pass is runnin...
Definition: LegacyPassManagers.h:110
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:207
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:296
llvm::PMDataManager::dumpLastUses
void dumpLastUses(Pass *P, unsigned Offset) const
Definition: LegacyPassManager.cpp:1157
llvm::PMDataManager::getNumContainedPasses
unsigned getNumContainedPasses() const
Definition: LegacyPassManagers.h:379
llvm::TimeRegion
The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...
Definition: Timer.h:146
llvm::AArch64::RP
@ RP
Definition: AArch64ISelLowering.h:475
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::PMTopLevelManager::activeStack
PMStack activeStack
Definition: LegacyPassManagers.h:220
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:1237
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:1124
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:53
llvm::MODIFICATION_MSG
@ MODIFICATION_MSG
Definition: LegacyPassManagers.h:99
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
llvm::PMStack::top
PMDataManager * top() const
Definition: LegacyPassManagers.h:144
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::PMStack::empty
bool empty() const
Definition: LegacyPassManagers.h:146
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:216
Timer.h
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:206
llvm::RGPassManager::ID
static char ID
Definition: RegionPass.h:92
llvm::PMDataManager::getTopLevelManager
PMTopLevelManager * getTopLevelManager()
Definition: LegacyPassManagers.h:364
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
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:976
llvm::PMDataManager::preserveHigherLevelAnalysis
bool preserveHigherLevelAnalysis(Pass *P)
Definition: LegacyPassManager.cpp:896
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PMDataManager::dumpRequiredSet
void dumpRequiredSet(const Pass *P) const
Definition: LegacyPassManager.cpp:1228
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:98
llvm::PMDataManager::getPassManagerType
virtual PassManagerType getPassManagerType() const
Definition: LegacyPassManagers.h:383
llvm::PMStack::pop
void pop()
Definition: LegacyPassManager.cpp:1691
llvm::PMDataManager::verifyPreservedAnalysis
void verifyPreservedAnalysis(Pass *P)
verifyPreservedAnalysis – Verify analysis presreved by pass P.
Definition: LegacyPassManager.cpp:912
llvm::PMDataManager::removeNotPreservedAnalysis
void removeNotPreservedAnalysis(Pass *P)
Remove Analysis that is not preserved by the pass.
Definition: LegacyPassManager.cpp:930
llvm::PMStack
PMStack - This class implements a stack data structure of PMDataManager pointers.
Definition: LegacyPassManagers.h:137
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:270
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:1028
llvm::PMDataManager::TPM
PMTopLevelManager * TPM
Definition: LegacyPassManagers.h:422
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:211
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:497
llvm::PMTopLevelManager
PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers.
Definition: LegacyPassManagers.h:159
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:32
getDescription
static std::string getDescription(const Region &R)
Definition: RegionPass.cpp:275
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:393
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:37