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