lib/Analysis/RegionInfo.cpp

   1 //===- RegionInfo.cpp - SESE region detection analysis --------------------===//
   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 // Detects single entry single exit regions in the control flow graph.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/Analysis/RegionInfo.h"
  13 #include "llvm/ADT/Statistic.h"
  14 #ifndef NDEBUG
  15 #include "llvm/Analysis/RegionPrinter.h"
  16 #endif
  17 #include "llvm/Analysis/RegionInfoImpl.h"
  18 #include "llvm/Config/llvm-config.h"
  19 #include "llvm/IR/Function.h"
  20 #include "llvm/IR/PassManager.h"
  21 #include "llvm/Pass.h"
  22 #include "llvm/Support/CommandLine.h"
  23 #include "llvm/Support/Compiler.h"
  24 #include "llvm/Support/raw_ostream.h"
  25
  26 using namespace llvm;
  27
  28 #define DEBUG_TYPE "region"
  29
  30 namespace llvm {
  31
  32 template class RegionBase<RegionTraits<Function>>;
  33 template class RegionNodeBase<RegionTraits<Function>>;
  34 template class RegionInfoBase<RegionTraits<Function>>;
  35
  36 } // end namespace llvm
  37
  38 STATISTIC(numRegions,       "The # of regions");
  39 STATISTIC(numSimpleRegions, "The # of simple regions");
  40
  41 // Always verify if expensive checking is enabled.
  42
  43 static cl::opt<bool,true>
  44 VerifyRegionInfoX(
  45   "verify-region-info",
  46   cl::location(RegionInfoBase<RegionTraits<Function>>::VerifyRegionInfo),
  47   cl::desc("Verify region info (time consuming)"));
  48
  49 static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style",
  50   cl::location(RegionInfo::printStyle),
  51   cl::Hidden,
  52   cl::desc("style of printing regions"),
  53   cl::values(
  54     clEnumValN(Region::PrintNone, "none",  "print no details"),
  55     clEnumValN(Region::PrintBB, "bb",
  56                "print regions in detail with block_iterator"),
  57     clEnumValN(Region::PrintRN, "rn",
  58                "print regions in detail with element_iterator")));
  59
  60 //===----------------------------------------------------------------------===//
  61 // Region implementation
  62 //
  63
  64 Region::Region(BasicBlock *Entry, BasicBlock *Exit,
  65                RegionInfo* RI,
  66                DominatorTree *DT, Region *Parent) :
  67   RegionBase<RegionTraits<Function>>(Entry, Exit, RI, DT, Parent) {
  68
  69 }
  70
  71 Region::~Region() = default;
  72
  73 //===----------------------------------------------------------------------===//
  74 // RegionInfo implementation
  75 //
  76
  77 RegionInfo::RegionInfo() = default;
  78
  79 RegionInfo::~RegionInfo() = default;
  80
  81 bool RegionInfo::invalidate(Function &F, const PreservedAnalyses &PA,
  82                             FunctionAnalysisManager::Invalidator &) {
  83   // Check whether the analysis, all analyses on functions, or the function's
  84   // CFG has been preserved.
  85   auto PAC = PA.getChecker<RegionInfoAnalysis>();
  86   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
  87            PAC.preservedSet<CFGAnalyses>());
  88 }
  89
  90 void RegionInfo::updateStatistics(Region *R) {
  91   ++numRegions;
  92
  93   // TODO: Slow. Should only be enabled if -stats is used.
  94   if (R->isSimple())
  95     ++numSimpleRegions;
  96 }
  97
  98 void RegionInfo::recalculate(Function &F, DominatorTree *DT_,
  99                              PostDominatorTree *PDT_, DominanceFrontier *DF_) {
 100   DT = DT_;
 101   PDT = PDT_;
 102   DF = DF_;
 103
 104   TopLevelRegion = new Region(&F.getEntryBlock(), nullptr,
 105                               this, DT, nullptr);
 106   updateStatistics(TopLevelRegion);
 107   calculate(F);
 108 }
 109
 110 #ifndef NDEBUG
 111 void RegionInfo::view() { viewRegion(this); }
 112
 113 void RegionInfo::viewOnly() { viewRegionOnly(this); }
 114 #endif
 115
 116 //===----------------------------------------------------------------------===//
 117 // RegionInfoPass implementation
 118 //
 119
 120 RegionInfoPass::RegionInfoPass() : FunctionPass(ID) {
 121   initializeRegionInfoPassPass(*PassRegistry::getPassRegistry());
 122 }
 123
 124 RegionInfoPass::~RegionInfoPass() = default;
 125
 126 bool RegionInfoPass::runOnFunction(Function &F) {
 127   releaseMemory();
 128
 129   auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 130   auto PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
 131   auto DF = &getAnalysis<DominanceFrontierWrapperPass>().getDominanceFrontier();
 132
 133   RI.recalculate(F, DT, PDT, DF);
 134   return false;
 135 }
 136
 137 void RegionInfoPass::releaseMemory() {
 138   RI.releaseMemory();
 139 }
 140
 141 void RegionInfoPass::verifyAnalysis() const {
 142     RI.verifyAnalysis();
 143 }
 144
 145 void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
 146   AU.setPreservesAll();
 147   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
 148   AU.addRequired<PostDominatorTreeWrapperPass>();
 149   AU.addRequired<DominanceFrontierWrapperPass>();
 150 }
 151
 152 void RegionInfoPass::print(raw_ostream &OS, const Module *) const {
 153   RI.print(OS);
 154 }
 155
 156 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 157 LLVM_DUMP_METHOD void RegionInfoPass::dump() const {
 158   RI.dump();
 159 }
 160 #endif
 161
 162 char RegionInfoPass::ID = 0;
 163
 164 INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions",
 165                 "Detect single entry single exit regions", true, true)
 166 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 167 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 168 INITIALIZE_PASS_DEPENDENCY(DominanceFrontierWrapperPass)
 169 INITIALIZE_PASS_END(RegionInfoPass, "regions",
 170                 "Detect single entry single exit regions", true, true)
 171
 172 // Create methods available outside of this file, to use them
 173 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
 174 // the link time optimization.
 175
 176 namespace llvm {
 177
 178   FunctionPass *createRegionInfoPass() {
 179     return new RegionInfoPass();
 180   }
 181
 182 } // end namespace llvm
 183
 184 //===----------------------------------------------------------------------===//
 185 // RegionInfoAnalysis implementation
 186 //
 187
 188 AnalysisKey RegionInfoAnalysis::Key;
 189
 190 RegionInfo RegionInfoAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
 191   RegionInfo RI;
 192   auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
 193   auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);
 194   auto *DF = &AM.getResult<DominanceFrontierAnalysis>(F);
 195
 196   RI.recalculate(F, DT, PDT, DF);
 197   return RI;
 198 }
 199
 200 RegionInfoPrinterPass::RegionInfoPrinterPass(raw_ostream &OS)
 201   : OS(OS) {}
 202
 203 PreservedAnalyses RegionInfoPrinterPass::run(Function &F,
 204                                              FunctionAnalysisManager &AM) {
 205   OS << "Region Tree for function: " << F.getName() << "\n";
 206   AM.getResult<RegionInfoAnalysis>(F).print(OS);
 207
 208   return PreservedAnalyses::all();
 209 }
 210
 211 PreservedAnalyses RegionInfoVerifierPass::run(Function &F,
 212                                               FunctionAnalysisManager &AM) {
 213   AM.getResult<RegionInfoAnalysis>(F).verifyAnalysis();
 214
 215   return PreservedAnalyses::all();
 216 }