LLVM  16.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 //===----------------------------------------------------------------------===//
15 
18 #include "llvm/IR/OptBisect.h"
19 #include "llvm/IR/PassTimingInfo.h"
20 #include "llvm/IR/PrintPasses.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/Timer.h"
24 
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "regionpassmgr"
28 
29 //===----------------------------------------------------------------------===//
30 // RGPassManager
31 //
32 
33 char RGPassManager::ID = 0;
34 
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.
49  Info.addRequired<RegionInfoPass>();
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 
80  // Run all passes on the current Region.
81  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
83 
86  CurrentRegion->getNameStr());
88  }
89 
91 
92  bool LocalChanged = false;
93  {
94  PassManagerPrettyStackEntry X(P, *CurrentRegion->getEntry());
95 
96  TimeRegion PassTimer(getPassTimer(P));
97 #ifdef EXPENSIVE_CHECKS
98  uint64_t RefHash = P->structuralHash(F);
99 #endif
100  LocalChanged = P->runOnRegion(CurrentRegion, *this);
101 
102 #ifdef EXPENSIVE_CHECKS
103  if (!LocalChanged && (RefHash != P->structuralHash(F))) {
104  llvm::errs() << "Pass modifies its input and doesn't report it: "
105  << P->getPassName() << "\n";
106  llvm_unreachable("Pass modifies its input and doesn't report it");
107  }
108 #endif
109 
110  Changed |= LocalChanged;
111  }
112 
114  if (LocalChanged)
116  CurrentRegion->getNameStr());
118  }
119 
120  // Manually check that this region is still healthy. This is done
121  // instead of relying on RegionInfo::verifyRegion since RegionInfo
122  // is a function pass and it's really expensive to verify every
123  // Region in the function every time. That level of checking can be
124  // enabled with the -verify-region-info option.
125  {
126  TimeRegion PassTimer(getPassTimer(P));
127  CurrentRegion->verifyRegion();
128  }
129 
130  // Then call the regular verifyAnalysis functions.
132 
133  if (LocalChanged)
138  ? "<deleted>"
139  : CurrentRegion->getNameStr(),
140  ON_REGION_MSG);
141  }
142 
143  // Pop the region from queue after running all passes.
144  RQ.pop_back();
145 
146  // Free all region nodes created in region passes.
147  RI->clearNodeCache();
148  }
149 
150  // Finalization
151  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
153  Changed |= P->doFinalization();
154  }
155 
156  // Print the region tree after all pass.
157  LLVM_DEBUG(dbgs() << "\nRegion tree of function " << F.getName()
158  << " after all region Pass:\n";
159  RI->dump(); dbgs() << "\n";);
160 
161  return Changed;
162 }
163 
164 /// Print passes managed by this manager
165 void RGPassManager::dumpPassStructure(unsigned Offset) {
166  errs().indent(Offset*2) << "Region Pass Manager\n";
167  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
169  P->dumpPassStructure(Offset + 1);
170  dumpLastUses(P, Offset+1);
171  }
172 }
173 
174 namespace {
175 //===----------------------------------------------------------------------===//
176 // PrintRegionPass
177 class PrintRegionPass : public RegionPass {
178 private:
179  std::string Banner;
180  raw_ostream &Out; // raw_ostream to print on.
181 
182 public:
183  static char ID;
184  PrintRegionPass(const std::string &B, raw_ostream &o)
185  : RegionPass(ID), Banner(B), Out(o) {}
186 
187  void getAnalysisUsage(AnalysisUsage &AU) const override {
188  AU.setPreservesAll();
189  }
190 
191  bool runOnRegion(Region *R, RGPassManager &RGM) override {
192  if (!isFunctionInPrintList(R->getEntry()->getParent()->getName()))
193  return false;
194  Out << Banner;
195  for (const auto *BB : R->blocks()) {
196  if (BB)
197  BB->print(Out);
198  else
199  Out << "Printing <null> Block";
200  }
201 
202  return false;
203  }
204 
205  StringRef getPassName() const override { return "Print Region IR"; }
206 };
207 
208 char PrintRegionPass::ID = 0;
209 } //end anonymous namespace
210 
211 //===----------------------------------------------------------------------===//
212 // RegionPass
213 
214 // Check if this pass is suitable for the current RGPassManager, if
215 // available. This pass P is not suitable for a RGPassManager if P
216 // is not preserving higher level analysis info used by other
217 // RGPassManager passes. In such case, pop RGPassManager from the
218 // stack. This will force assignPassManager() to create new
219 // LPPassManger as expected.
221 
222  // Find RGPassManager
223  while (!PMS.empty() &&
225  PMS.pop();
226 
227 
228  // If this pass is destroying high level information that is used
229  // by other passes that are managed by LPM then do not insert
230  // this pass in current LPM. Use new RGPassManager.
231  if (PMS.top()->getPassManagerType() == PMT_RegionPassManager &&
232  !PMS.top()->preserveHigherLevelAnalysis(this))
233  PMS.pop();
234 }
235 
236 /// Assign pass manager to manage this pass.
238  PassManagerType PreferredType) {
239  // Find RGPassManager
240  while (!PMS.empty() &&
242  PMS.pop();
243 
244  RGPassManager *RGPM;
245 
246  // Create new Region Pass Manager if it does not exist.
248  RGPM = (RGPassManager*)PMS.top();
249  else {
250 
251  assert (!PMS.empty() && "Unable to create Region Pass Manager");
252  PMDataManager *PMD = PMS.top();
253 
254  // [1] Create new Region Pass Manager
255  RGPM = new RGPassManager();
256  RGPM->populateInheritedAnalysis(PMS);
257 
258  // [2] Set up new manager's top level manager
260  TPM->addIndirectPassManager(RGPM);
261 
262  // [3] Assign manager to manage this new manager. This may create
263  // and push new managers into PMS
264  TPM->schedulePass(RGPM);
265 
266  // [4] Push new manager into PMS
267  PMS.push(RGPM);
268  }
269 
270  RGPM->add(this);
271 }
272 
273 /// Get the printer pass
275  const std::string &Banner) const {
276  return new PrintRegionPass(Banner, O);
277 }
278 
279 static std::string getDescription(const Region &R) {
280  return "region";
281 }
282 
284  Function &F = *R.getEntry()->getParent();
285  OptPassGate &Gate = F.getContext().getOptPassGate();
286  if (Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(R)))
287  return true;
288 
289  if (F.hasOptNone()) {
290  // Report this only once per function.
291  if (R.getEntry() == &F.getEntryBlock())
292  LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName()
293  << "' on function " << F.getName() << "\n");
294  return true;
295  }
296  return false;
297 }
RegionInfo.h
llvm::PMDataManager::recordAvailableAnalysis
void recordAvailableAnalysis(Pass *P)
Augment AvailableAnalysis by adding analysis made available by pass P.
Definition: LegacyPassManager.cpp:871
llvm::RGPassManager::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &Info) const override
Pass Manager itself does not invalidate any analysis info.
Definition: RegionPass.cpp:48
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::RegionPass::skipRegion
bool skipRegion(Region &R) const
Optional passes call this function to check whether the pass should be skipped.
Definition: RegionPass.cpp:283
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:237
RegionPass.h
llvm::Function
Definition: Function.h:60
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:657
llvm::PMDataManager::dumpPassInfo
void dumpPassInfo(Pass *P, enum PassDebuggingString S1, enum PassDebuggingString S2, StringRef Msg)
Definition: LegacyPassManager.cpp:1178
llvm::OptPassGate::isEnabled
virtual bool isEnabled() const
isEnabled() should return true before calling shouldRunPass().
Definition: OptBisect.h:37
llvm::PassManagerType
PassManagerType
Different types of internal pass managers.
Definition: Pass.h:52
OptBisect.h
llvm::PMStack::push
void push(PMDataManager *PM)
Definition: LegacyPassManager.cpp:1691
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:891
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:265
llvm::RGPassManager::dumpPassStructure
void dumpPassStructure(unsigned Offset) override
Print passes managed by this manager.
Definition: RegionPass.cpp:165
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:1148
llvm::PMDataManager::getNumContainedPasses
unsigned getNumContainedPasses() const
Definition: LegacyPassManagers.h:376
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:485
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:790
llvm::OptPassGate
Extensions to this class implement mechanisms to disable passes and individual optimizations at compi...
Definition: OptBisect.h:26
llvm::PMDataManager::dumpPreservedSet
void dumpPreservedSet(const Pass *P) const
Definition: LegacyPassManager.cpp:1228
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:1115
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
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:292
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
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
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::PMStack::empty
bool empty() const
Definition: LegacyPassManagers.h:145
llvm::RegionPass::preparePassManager
void preparePassManager(PMStack &PMS) override
Check if available pass managers are suitable for this pass or not.
Definition: RegionPass.cpp:220
Timer.h
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:264
llvm::RGPassManager::ID
static char ID
Definition: RegionPass.h:93
llvm::PMDataManager::getTopLevelManager
PMTopLevelManager * getTopLevelManager()
Definition: LegacyPassManagers.h:361
Index
uint32_t Index
Definition: ELFObjHandler.cpp:82
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:968
llvm::isFunctionInPrintList
bool isFunctionInPrintList(StringRef FunctionName)
Definition: PrintPasses.cpp:151
llvm::PMDataManager::preserveHigherLevelAnalysis
bool preserveHigherLevelAnalysis(Pass *P)
Definition: LegacyPassManager.cpp:888
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PMDataManager::dumpRequiredSet
void dumpRequiredSet(const Pass *P) const
Definition: LegacyPassManager.cpp:1219
llvm::RGPassManager
The pass manager to schedule RegionPasses.
Definition: RegionPass.h:87
llvm::RegionPass
A pass that runs on each Region in a function.
Definition: RegionPass.h:32
llvm::RegionInfoPass
Definition: RegionInfo.h:942
addRegionIntoQueue
static void addRegionIntoQueue(Region &R, std::deque< Region * > &RQ)
Definition: RegionPass.cpp:41
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::Pass::getPassName
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:80
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::EXECUTION_MSG
@ EXECUTION_MSG
Definition: LegacyPassManagers.h:97
llvm::PMDataManager::getPassManagerType
virtual PassManagerType getPassManagerType() const
Definition: LegacyPassManagers.h:380
llvm::PMStack::pop
void pop()
Definition: LegacyPassManager.cpp:1682
llvm::PMDataManager::verifyPreservedAnalysis
void verifyPreservedAnalysis(Pass *P)
verifyPreservedAnalysis – Verify analysis presreved by pass P.
Definition: LegacyPassManager.cpp:904
llvm::PMDataManager::removeNotPreservedAnalysis
void removeNotPreservedAnalysis(Pass *P)
Remove Analysis that is not preserved by the pass.
Definition: LegacyPassManager.cpp:922
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:274
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:1019
llvm::PMDataManager::TPM
PMTopLevelManager * TPM
Definition: LegacyPassManagers.h:419
llvm::RegionBase::getNameStr
std::string getNameStr() const
Returns the name of the Region.
Definition: RegionInfoImpl.h:228
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:494
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:308
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:35
getDescription
static std::string getDescription(const Region &R)
Definition: RegionPass.cpp:279
llvm::RGPassManager::runOnFunction
bool runOnFunction(Function &F) override
Execute all of the passes scheduled for execution.
Definition: RegionPass.cpp:55
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:61
raw_ostream.h
llvm::PMDataManager::populateInheritedAnalysis
void populateInheritedAnalysis(PMStack &PMS)
Definition: LegacyPassManagers.h:390
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:32
llvm::RGPassManager::getContainedPass
Pass * getContainedPass(unsigned N)
Get passes contained by this manager.
Definition: RegionPass.h:114
Debug.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38