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