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
16#include "llvm/Analysis/RegionPass.h"
17#include "llvm/Analysis/RegionInfo.h"
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"
23#include "llvm/Support/raw_ostream.h"
24
25using namespace llvm;
26
27#define DEBUG_TYPE "regionpassmgr"
28
29//===----------------------------------------------------------------------===//
30// RGPassManager
31//
32
33char RGPassManager::ID = 0;
34
35RGPassManager::RGPassManager() : FunctionPass(ID) {
36 RI = nullptr;
37 CurrentRegion = nullptr;
38}
39
40// Recurse through all subregions and all regions into RQ.
41static void addRegionIntoQueue(Region &R, std::deque<Region *> &RQ) {
42 RQ.push_back(x: &R);
43 for (const auto &E : R)
44 addRegionIntoQueue(R&: *E, RQ);
45}
46
47/// Pass Manager itself does not invalidate any analysis info.
48void RGPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
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.
55bool RGPassManager::runOnFunction(Function &F) {
56 RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
57 bool Changed = false;
58
59 // Collect inherited analysis from Module level pass manager.
60 populateInheritedAnalysis(PMS&: TPM->activeStack);
61
62 addRegionIntoQueue(R&: *RI->getTopLevelRegion(), RQ);
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) {
70 RegionPass *RP = (RegionPass *)getContainedPass(N: Index);
71 Changed |= RP->doInitialization(R, RGM&: *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) {
82 RegionPass *P = (RegionPass*)getContainedPass(N: Index);
83
84 if (isPassDebuggingExecutionsOrMore()) {
85 dumpPassInfo(P, S1: EXECUTION_MSG, S2: ON_REGION_MSG,
86 Msg: CurrentRegion->getNameStr());
87 dumpRequiredSet(P);
88 }
89
90 initializeAnalysisImpl(P);
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(R: CurrentRegion, RGM&: *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
113 if (isPassDebuggingExecutionsOrMore()) {
114 if (LocalChanged)
115 dumpPassInfo(P, S1: MODIFICATION_MSG, S2: ON_REGION_MSG,
116 Msg: CurrentRegion->getNameStr());
117 dumpPreservedSet(P);
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.
131 verifyPreservedAnalysis(P);
132
133 if (LocalChanged)
134 removeNotPreservedAnalysis(P);
135 recordAvailableAnalysis(P);
136 removeDeadPasses(P,
137 Msg: (!isPassDebuggingExecutionsOrMore())
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) {
152 RegionPass *P = (RegionPass*)getContainedPass(N: 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
165void RGPassManager::dumpPassStructure(unsigned Offset) {
166 errs().indent(NumSpaces: Offset*2) << "Region Pass Manager\n";
167 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
168 Pass *P = getContainedPass(N: Index);
169 P->dumpPassStructure(Offset: Offset + 1);
170 dumpLastUses(P, Offset: Offset+1);
171 }
172}
173
174namespace {
175bool shouldPrintRegion(const Region &R) {
176 bool SourceLocFilterEmpty = isSourceLocFilterEmpty();
177 if (!isFunctionInPrintList(FunctionName: R.getEntry()->getParent()->getName()))
178 return false;
179
180 if (SourceLocFilterEmpty)
181 return true;
182
183 for (const BasicBlock *BB : R.blocks())
184 if (BB)
185 for (const Instruction &I : *BB)
186 if (isSourceLocInPrintList(Loc: I.getDebugLoc()))
187 return true;
188 return false;
189}
190
191//===----------------------------------------------------------------------===//
192// PrintRegionPass
193class PrintRegionPass : public RegionPass {
194private:
195 std::string Banner;
196 raw_ostream &Out; // raw_ostream to print on.
197
198public:
199 static char ID;
200 PrintRegionPass(const std::string &B, raw_ostream &o)
201 : RegionPass(ID), Banner(B), Out(o) {}
202
203 void getAnalysisUsage(AnalysisUsage &AU) const override {
204 AU.setPreservesAll();
205 }
206
207 bool runOnRegion(Region *R, RGPassManager &RGM) override {
208 if (!shouldPrintRegion(R: *R))
209 return false;
210 Out << Banner;
211 for (const auto *BB : R->blocks()) {
212 if (BB)
213 BB->print(OS&: Out);
214 else
215 Out << "Printing <null> Block";
216 }
217
218 return false;
219 }
220
221 StringRef getPassName() const override { return "Print Region IR"; }
222};
223
224char PrintRegionPass::ID = 0;
225} //end anonymous namespace
226
227//===----------------------------------------------------------------------===//
228// RegionPass
229
230// Check if this pass is suitable for the current RGPassManager, if
231// available. This pass P is not suitable for a RGPassManager if P
232// is not preserving higher level analysis info used by other
233// RGPassManager passes. In such case, pop RGPassManager from the
234// stack. This will force assignPassManager() to create new
235// LPPassManger as expected.
236void RegionPass::preparePassManager(PMStack &PMS) {
237
238 // Find RGPassManager
239 while (!PMS.empty() &&
240 PMS.top()->getPassManagerType() > PMT_RegionPassManager)
241 PMS.pop();
242
243
244 // If this pass is destroying high level information that is used
245 // by other passes that are managed by LPM then do not insert
246 // this pass in current LPM. Use new RGPassManager.
247 if (PMS.top()->getPassManagerType() == PMT_RegionPassManager &&
248 !PMS.top()->preserveHigherLevelAnalysis(P: this))
249 PMS.pop();
250}
251
252/// Assign pass manager to manage this pass.
253void RegionPass::assignPassManager(PMStack &PMS,
254 PassManagerType PreferredType) {
255 // Find RGPassManager
256 while (!PMS.empty() &&
257 PMS.top()->getPassManagerType() > PMT_RegionPassManager)
258 PMS.pop();
259
260 RGPassManager *RGPM;
261
262 // Create new Region Pass Manager if it does not exist.
263 if (PMS.top()->getPassManagerType() == PMT_RegionPassManager)
264 RGPM = (RGPassManager*)PMS.top();
265 else {
266
267 assert (!PMS.empty() && "Unable to create Region Pass Manager");
268 PMDataManager *PMD = PMS.top();
269
270 // [1] Create new Region Pass Manager
271 RGPM = new RGPassManager();
272 RGPM->populateInheritedAnalysis(PMS);
273
274 // [2] Set up new manager's top level manager
275 PMTopLevelManager *TPM = PMD->getTopLevelManager();
276 TPM->addIndirectPassManager(Manager: RGPM);
277
278 // [3] Assign manager to manage this new manager. This may create
279 // and push new managers into PMS
280 TPM->schedulePass(P: RGPM);
281
282 // [4] Push new manager into PMS
283 PMS.push(PM: RGPM);
284 }
285
286 RGPM->add(P: this);
287}
288
289/// Get the printer pass
290Pass *RegionPass::createPrinterPass(raw_ostream &O,
291 const std::string &Banner) const {
292 return new PrintRegionPass(Banner, O);
293}
294
295static std::string getDescription(const Region &R) {
296 return "region";
297}
298
299bool RegionPass::skipRegion(Region &R) const {
300 Function &F = *R.getEntry()->getParent();
301 const OptPassGate &Gate = F.getContext().getOptPassGate();
302 if (Gate.isEnabled() &&
303 !Gate.shouldRunPass(PassName: this->getPassName(), IRDescription: getDescription(R)))
304 return true;
305
306 if (F.hasOptNone()) {
307 // Report this only once per function.
308 if (R.getEntry() == &F.getEntryBlock())
309 LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName()
310 << "' on function " << F.getName() << "\n");
311 return true;
312 }
313 return false;
314}
315