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