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  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
193    AU.setPreservesAll();
194  }
195
196  virtual bool runOnRegion(Region *R, RGPassManager &RGM) {
197    Out << Banner;
198    for (Region::block_iterator I = R->block_begin(), E = R->block_end();
199         I != E; ++I)
200      (*I)->print(Out);
201
202    return false;
203  }
204};
205
206char PrintRegionPass::ID = 0;
207}  //end anonymous namespace
208
209//===----------------------------------------------------------------------===//
210// RegionPass
211
212// Check if this pass is suitable for the current RGPassManager, if
213// available. This pass P is not suitable for a RGPassManager if P
214// is not preserving higher level analysis info used by other
215// RGPassManager passes. In such case, pop RGPassManager from the
216// stack. This will force assignPassManager() to create new
217// LPPassManger as expected.
218void RegionPass::preparePassManager(PMStack &PMS) {
219
220  // Find RGPassManager
221  while (!PMS.empty() &&
222         PMS.top()->getPassManagerType() > PMT_RegionPassManager)
223    PMS.pop();
224
225
226  // If this pass is destroying high level information that is used
227  // by other passes that are managed by LPM then do not insert
228  // this pass in current LPM. Use new RGPassManager.
229  if (PMS.top()->getPassManagerType() == PMT_RegionPassManager &&
230    !PMS.top()->preserveHigherLevelAnalysis(this))
231    PMS.pop();
232}
233
234/// Assign pass manager to manage this pass.
235void RegionPass::assignPassManager(PMStack &PMS,
236                                 PassManagerType PreferredType) {
237  // Find RGPassManager
238  while (!PMS.empty() &&
239         PMS.top()->getPassManagerType() > PMT_RegionPassManager)
240    PMS.pop();
241
242  RGPassManager *RGPM;
243
244  // Create new Region Pass Manager if it does not exist.
245  if (PMS.top()->getPassManagerType() == PMT_RegionPassManager)
246    RGPM = (RGPassManager*)PMS.top();
247  else {
248
249    assert (!PMS.empty() && "Unable to create Region Pass Manager");
250    PMDataManager *PMD = PMS.top();
251
252    // [1] Create new Region Pass Manager
253    RGPM = new RGPassManager();
254    RGPM->populateInheritedAnalysis(PMS);
255
256    // [2] Set up new manager's top level manager
257    PMTopLevelManager *TPM = PMD->getTopLevelManager();
258    TPM->addIndirectPassManager(RGPM);
259
260    // [3] Assign manager to manage this new manager. This may create
261    // and push new managers into PMS
262    TPM->schedulePass(RGPM);
263
264    // [4] Push new manager into PMS
265    PMS.push(RGPM);
266  }
267
268  RGPM->add(this);
269}
270
271/// Get the printer pass
272Pass *RegionPass::createPrinterPass(raw_ostream &O,
273                                  const std::string &Banner) const {
274  return new PrintRegionPass(Banner, O);
275}
276