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/IR/StructuralHash.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/Timer.h"
24 #include "llvm/Support/raw_ostream.h"
25 
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "regionpassmgr"
29 
30 //===----------------------------------------------------------------------===//
31 // RGPassManager
32 //
33 
34 char RGPassManager::ID = 0;
35 
36 RGPassManager::RGPassManager() : FunctionPass(ID) {
37   RI = nullptr;
38   CurrentRegion = nullptr;
39 }
40 
41 // Recurse through all subregions and all regions  into RQ.
42 static void addRegionIntoQueue(Region &R, std::deque<Region *> &RQ) {
43   RQ.push_back(&R);
44   for (const auto &E : R)
45     addRegionIntoQueue(*E, RQ);
46 }
47 
48 /// Pass Manager itself does not invalidate any analysis info.
49 void RGPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
50   Info.addRequired<RegionInfoPass>();
51   Info.setPreservesAll();
52 }
53 
54 /// run - Execute all of the passes scheduled for execution.  Keep track of
55 /// whether any of the passes modifies the function, and if so, return true.
56 bool RGPassManager::runOnFunction(Function &F) {
57   RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
58   bool Changed = false;
59 
60   // Collect inherited analysis from Module level pass manager.
61   populateInheritedAnalysis(TPM->activeStack);
62 
63   addRegionIntoQueue(*RI->getTopLevelRegion(), RQ);
64 
65   if (RQ.empty()) // No regions, skip calling finalizers
66     return false;
67 
68   // Initialization
69   for (Region *R : RQ) {
70     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
71       RegionPass *RP = (RegionPass *)getContainedPass(Index);
72       Changed |= RP->doInitialization(R, *this);
73     }
74   }
75 
76   // Walk Regions
77   while (!RQ.empty()) {
78 
79     CurrentRegion  = RQ.back();
80 
81     // Run all passes on the current Region.
82     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
83       RegionPass *P = (RegionPass*)getContainedPass(Index);
84 
85       if (isPassDebuggingExecutionsOrMore()) {
86         dumpPassInfo(P, EXECUTION_MSG, ON_REGION_MSG,
87                      CurrentRegion->getNameStr());
88         dumpRequiredSet(P);
89       }
90 
91       initializeAnalysisImpl(P);
92 
93       bool LocalChanged = false;
94       {
95         PassManagerPrettyStackEntry X(P, *CurrentRegion->getEntry());
96 
97         TimeRegion PassTimer(getPassTimer(P));
98 #ifdef EXPENSIVE_CHECKS
99         uint64_t RefHash = StructuralHash(F);
100 #endif
101         LocalChanged = P->runOnRegion(CurrentRegion, *this);
102 
103 #ifdef EXPENSIVE_CHECKS
104         if (!LocalChanged && (RefHash != StructuralHash(F))) {
105           llvm::errs() << "Pass modifies its input and doesn't report it: "
106                        << P->getPassName() << "\n";
107           llvm_unreachable("Pass modifies its input and doesn't report it");
108         }
109 #endif
110 
111         Changed |= LocalChanged;
112       }
113 
114       if (isPassDebuggingExecutionsOrMore()) {
115         if (LocalChanged)
116           dumpPassInfo(P, MODIFICATION_MSG, ON_REGION_MSG,
117                                       CurrentRegion->getNameStr());
118         dumpPreservedSet(P);
119       }
120 
121       // Manually check that this region is still healthy. This is done
122       // instead of relying on RegionInfo::verifyRegion since RegionInfo
123       // is a function pass and it's really expensive to verify every
124       // Region in the function every time. That level of checking can be
125       // enabled with the -verify-region-info option.
126       {
127         TimeRegion PassTimer(getPassTimer(P));
128         CurrentRegion->verifyRegion();
129       }
130 
131       // Then call the regular verifyAnalysis functions.
132       verifyPreservedAnalysis(P);
133 
134       if (LocalChanged)
135         removeNotPreservedAnalysis(P);
136       recordAvailableAnalysis(P);
137       removeDeadPasses(P,
138                        (!isPassDebuggingExecutionsOrMore())
139                            ? "<deleted>"
140                            : CurrentRegion->getNameStr(),
141                        ON_REGION_MSG);
142     }
143 
144     // Pop the region from queue after running all passes.
145     RQ.pop_back();
146 
147     // Free all region nodes created in region passes.
148     RI->clearNodeCache();
149   }
150 
151   // Finalization
152   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
153     RegionPass *P = (RegionPass*)getContainedPass(Index);
154     Changed |= P->doFinalization();
155   }
156 
157   // Print the region tree after all pass.
158   LLVM_DEBUG(dbgs() << "\nRegion tree of function " << F.getName()
159                     << " after all region Pass:\n";
160              RI->dump(); dbgs() << "\n";);
161 
162   return Changed;
163 }
164 
165 /// Print passes managed by this manager
166 void RGPassManager::dumpPassStructure(unsigned Offset) {
167   errs().indent(Offset*2) << "Region Pass Manager\n";
168   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
169     Pass *P = getContainedPass(Index);
170     P->dumpPassStructure(Offset + 1);
171     dumpLastUses(P, Offset+1);
172   }
173 }
174 
175 namespace {
176 //===----------------------------------------------------------------------===//
177 // PrintRegionPass
178 class PrintRegionPass : public RegionPass {
179 private:
180   std::string Banner;
181   raw_ostream &Out;       // raw_ostream to print on.
182 
183 public:
184   static char ID;
185   PrintRegionPass(const std::string &B, raw_ostream &o)
186       : RegionPass(ID), Banner(B), Out(o) {}
187 
188   void getAnalysisUsage(AnalysisUsage &AU) const override {
189     AU.setPreservesAll();
190   }
191 
192   bool runOnRegion(Region *R, RGPassManager &RGM) override {
193     if (!isFunctionInPrintList(R->getEntry()->getParent()->getName()))
194       return false;
195     Out << Banner;
196     for (const auto *BB : R->blocks()) {
197       if (BB)
198         BB->print(Out);
199       else
200         Out << "Printing <null> Block";
201     }
202 
203     return false;
204   }
205 
206   StringRef getPassName() const override { return "Print Region IR"; }
207 };
208 
209 char PrintRegionPass::ID = 0;
210 }  //end anonymous namespace
211 
212 //===----------------------------------------------------------------------===//
213 // RegionPass
214 
215 // Check if this pass is suitable for the current RGPassManager, if
216 // available. This pass P is not suitable for a RGPassManager if P
217 // is not preserving higher level analysis info used by other
218 // RGPassManager passes. In such case, pop RGPassManager from the
219 // stack. This will force assignPassManager() to create new
220 // LPPassManger as expected.
221 void RegionPass::preparePassManager(PMStack &PMS) {
222 
223   // Find RGPassManager
224   while (!PMS.empty() &&
225          PMS.top()->getPassManagerType() > PMT_RegionPassManager)
226     PMS.pop();
227 
228 
229   // If this pass is destroying high level information that is used
230   // by other passes that are managed by LPM then do not insert
231   // this pass in current LPM. Use new RGPassManager.
232   if (PMS.top()->getPassManagerType() == PMT_RegionPassManager &&
233     !PMS.top()->preserveHigherLevelAnalysis(this))
234     PMS.pop();
235 }
236 
237 /// Assign pass manager to manage this pass.
238 void RegionPass::assignPassManager(PMStack &PMS,
239                                  PassManagerType PreferredType) {
240   // Find RGPassManager
241   while (!PMS.empty() &&
242          PMS.top()->getPassManagerType() > PMT_RegionPassManager)
243     PMS.pop();
244 
245   RGPassManager *RGPM;
246 
247   // Create new Region Pass Manager if it does not exist.
248   if (PMS.top()->getPassManagerType() == PMT_RegionPassManager)
249     RGPM = (RGPassManager*)PMS.top();
250   else {
251 
252     assert (!PMS.empty() && "Unable to create Region Pass Manager");
253     PMDataManager *PMD = PMS.top();
254 
255     // [1] Create new Region Pass Manager
256     RGPM = new RGPassManager();
257     RGPM->populateInheritedAnalysis(PMS);
258 
259     // [2] Set up new manager's top level manager
260     PMTopLevelManager *TPM = PMD->getTopLevelManager();
261     TPM->addIndirectPassManager(RGPM);
262 
263     // [3] Assign manager to manage this new manager. This may create
264     // and push new managers into PMS
265     TPM->schedulePass(RGPM);
266 
267     // [4] Push new manager into PMS
268     PMS.push(RGPM);
269   }
270 
271   RGPM->add(this);
272 }
273 
274 /// Get the printer pass
275 Pass *RegionPass::createPrinterPass(raw_ostream &O,
276                                   const std::string &Banner) const {
277   return new PrintRegionPass(Banner, O);
278 }
279 
280 static std::string getDescription(const Region &R) {
281   return "region";
282 }
283 
284 bool RegionPass::skipRegion(Region &R) const {
285   Function &F = *R.getEntry()->getParent();
286   OptPassGate &Gate = F.getContext().getOptPassGate();
287   if (Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(R)))
288     return true;
289 
290   if (F.hasOptNone()) {
291     // Report this only once per function.
292     if (R.getEntry() == &F.getEntryBlock())
293       LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName()
294                         << "' on function " << F.getName() << "\n");
295     return true;
296   }
297   return false;
298 }
299