RegionPass.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f 
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#include "llvm/Support/Debug.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<RegionInfo>();
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<RegionInfo>();
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      dumpPassInfo(P, EXECUTION_MSG, ON_REGION_MSG,
88                   CurrentRegion->getNameStr());
89      dumpRequiredSet(P);
90
91      initializeAnalysisImpl(P);
92
93      {
94        PassManagerPrettyStackEntry X(P, *CurrentRegion->getEntry());
95
96        TimeRegion PassTimer(getPassTimer(P));
97        Changed |= P->runOnRegion(CurrentRegion, *this);
98      }
99
100      if (Changed)
101        dumpPassInfo(P, MODIFICATION_MSG, ON_REGION_MSG,
102                     skipThisRegion ? "<deleted>" :
103                                    CurrentRegion->getNameStr());
104      dumpPreservedSet(P);
105
106      if (!skipThisRegion) {
107        // Manually check that this region is still healthy. This is done
108        // instead of relying on RegionInfo::verifyRegion since RegionInfo
109        // is a function pass and it's really expensive to verify every
110        // Region in the function every time. That level of checking can be
111        // enabled with the -verify-region-info option.
112        {
113          TimeRegion PassTimer(getPassTimer(P));
114          CurrentRegion->verifyRegion();
115        }
116
117        // Then call the regular verifyAnalysis functions.
118        verifyPreservedAnalysis(P);
119      }
120
121      removeNotPreservedAnalysis(P);
122      recordAvailableAnalysis(P);
123      removeDeadPasses(P,
124                       skipThisRegion ? "<deleted>" :
125                                      CurrentRegion->getNameStr(),
126                       ON_REGION_MSG);
127
128      if (skipThisRegion)
129        // Do not run other passes on this region.
130        break;
131    }
132
133    // If the region was deleted, release all the region passes. This frees up
134    // some memory, and avoids trouble with the pass manager trying to call
135    // verifyAnalysis on them.
136    if (skipThisRegion)
137      for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
138        Pass *P = getContainedPass(Index);
139        freePass(P, "<deleted>", ON_REGION_MSG);
140      }
141
142    // Pop the region from queue after running all passes.
143    RQ.pop_back();
144
145    if (redoThisRegion)
146      RQ.push_back(CurrentRegion);
147
148    // Free all region nodes created in region passes.
149    RI->clearNodeCache();
150  }
151
152  // Finalization
153  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
154    RegionPass *P = (RegionPass*)getContainedPass(Index);
155    Changed |= P->doFinalization();
156  }
157
158  // Print the region tree after all pass.
159  DEBUG(
160    dbgs() << "\nRegion tree of function " << F.getName()
161           << " after all region Pass:\n";
162    RI->dump();
163    dbgs() << "\n";
164    );
165
166  return Changed;
167}
168
169/// Print passes managed by this manager
170void RGPassManager::dumpPassStructure(unsigned Offset) {
171  errs().indent(Offset*2) << "Region Pass Manager\n";
172  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
173    Pass *P = getContainedPass(Index);
174    P->dumpPassStructure(Offset + 1);
175    dumpLastUses(P, Offset+1);
176  }
177}
178
179namespace {
180//===----------------------------------------------------------------------===//
181// PrintRegionPass
182class PrintRegionPass : public RegionPass {
183private:
184  std::string Banner;
185  raw_ostream &Out;       // raw_ostream to print on.
186
187public:
188  static char ID;
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