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 
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "regionpassmgr"
28 
29 //===----------------------------------------------------------------------===//
30 // RGPassManager
31 //
32 
33 char RGPassManager::ID = 0;
34 
35 RGPassManager::RGPassManager() : FunctionPass(ID) {
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.
48 void 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.
55 bool 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(TPM->activeStack);
61 
62   addRegionIntoQueue(*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(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) {
82       RegionPass *P = (RegionPass*)getContainedPass(Index);
83 
84       if (isPassDebuggingExecutionsOrMore()) {
85         dumpPassInfo(P, EXECUTION_MSG, ON_REGION_MSG,
86                      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(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 
113       if (isPassDebuggingExecutionsOrMore()) {
114         if (LocalChanged)
115           dumpPassInfo(P, MODIFICATION_MSG, ON_REGION_MSG,
116                                       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                        (!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(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) {
168     Pass *P = getContainedPass(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.
220 void RegionPass::preparePassManager(PMStack &PMS) {
221 
222   // Find RGPassManager
223   while (!PMS.empty() &&
224          PMS.top()->getPassManagerType() > PMT_RegionPassManager)
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.
237 void RegionPass::assignPassManager(PMStack &PMS,
238                                  PassManagerType PreferredType) {
239   // Find RGPassManager
240   while (!PMS.empty() &&
241          PMS.top()->getPassManagerType() > PMT_RegionPassManager)
242     PMS.pop();
243 
244   RGPassManager *RGPM;
245 
246   // Create new Region Pass Manager if it does not exist.
247   if (PMS.top()->getPassManagerType() == PMT_RegionPassManager)
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
259     PMTopLevelManager *TPM = PMD->getTopLevelManager();
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
274 Pass *RegionPass::createPrinterPass(raw_ostream &O,
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 
283 bool RegionPass::skipRegion(Region &R) const {
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 }
298