llvm/lib/Analysis/RegionInfo.cpp

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