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/PostOrderIterator.h" 14 #include "llvm/ADT/Statistic.h" 15 #include "llvm/Analysis/LoopInfo.h" 16 #include "llvm/Analysis/RegionInfoImpl.h" 17 #include "llvm/Analysis/RegionIterator.h" 18 #include "llvm/Support/CommandLine.h" 19 #include "llvm/Support/Debug.h" 20 #include "llvm/Support/ErrorHandling.h" 21 #include <algorithm> 22 #include <iterator> 23 #include <set> 24 #ifndef NDEBUG 25 #include "llvm/Analysis/RegionPrinter.h" 26 #endif 27 28 using namespace llvm; 29 30 #define DEBUG_TYPE "region" 31 32 namespace llvm { 33 template class RegionBase<RegionTraits<Function>>; 34 template class RegionNodeBase<RegionTraits<Function>>; 35 template class RegionInfoBase<RegionTraits<Function>>; 36 } 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 50 static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style", 51 cl::location(RegionInfo::printStyle), 52 cl::Hidden, 53 cl::desc("style of printing regions"), 54 cl::values( 55 clEnumValN(Region::PrintNone, "none", "print no details"), 56 clEnumValN(Region::PrintBB, "bb", 57 "print regions in detail with block_iterator"), 58 clEnumValN(Region::PrintRN, "rn", 59 "print regions in detail with element_iterator"), 60 clEnumValEnd)); 61 62 63 //===----------------------------------------------------------------------===// 64 // Region implementation 65 // 66 67 Region::Region(BasicBlock *Entry, BasicBlock *Exit, 68 RegionInfo* RI, 69 DominatorTree *DT, Region *Parent) : 70 RegionBase<RegionTraits<Function>>(Entry, Exit, RI, DT, Parent) { 71 72 } 73 74 Region::~Region() { } 75 76 //===----------------------------------------------------------------------===// 77 // RegionInfo implementation 78 // 79 80 RegionInfo::RegionInfo() : 81 RegionInfoBase<RegionTraits<Function>>() { 82 83 } 84 85 RegionInfo::~RegionInfo() { 86 87 } 88 89 void RegionInfo::updateStatistics(Region *R) { 90 ++numRegions; 91 92 // TODO: Slow. Should only be enabled if -stats is used. 93 if (R->isSimple()) 94 ++numSimpleRegions; 95 } 96 97 void RegionInfo::recalculate(Function &F, DominatorTree *DT_, 98 PostDominatorTree *PDT_, DominanceFrontier *DF_) { 99 DT = DT_; 100 PDT = PDT_; 101 DF = DF_; 102 103 TopLevelRegion = new Region(&F.getEntryBlock(), nullptr, 104 this, DT, nullptr); 105 updateStatistics(TopLevelRegion); 106 calculate(F); 107 } 108 109 #ifndef NDEBUG 110 void RegionInfo::view() { viewRegion(this); } 111 112 void RegionInfo::viewOnly() { viewRegionOnly(this); } 113 #endif 114 115 //===----------------------------------------------------------------------===// 116 // RegionInfoPass implementation 117 // 118 119 RegionInfoPass::RegionInfoPass() : FunctionPass(ID) { 120 initializeRegionInfoPassPass(*PassRegistry::getPassRegistry()); 121 } 122 123 RegionInfoPass::~RegionInfoPass() { 124 125 } 126 127 bool RegionInfoPass::runOnFunction(Function &F) { 128 releaseMemory(); 129 130 auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 131 auto PDT = &getAnalysis<PostDominatorTree>(); 132 auto DF = &getAnalysis<DominanceFrontier>(); 133 134 RI.recalculate(F, DT, PDT, DF); 135 return false; 136 } 137 138 void RegionInfoPass::releaseMemory() { 139 RI.releaseMemory(); 140 } 141 142 void RegionInfoPass::verifyAnalysis() const { 143 RI.verifyAnalysis(); 144 } 145 146 void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const { 147 AU.setPreservesAll(); 148 AU.addRequiredTransitive<DominatorTreeWrapperPass>(); 149 AU.addRequired<PostDominatorTree>(); 150 AU.addRequired<DominanceFrontier>(); 151 } 152 153 void RegionInfoPass::print(raw_ostream &OS, const Module *) const { 154 RI.print(OS); 155 } 156 157 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 158 void RegionInfoPass::dump() const { 159 RI.dump(); 160 } 161 #endif 162 163 char RegionInfoPass::ID = 0; 164 165 INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions", 166 "Detect single entry single exit regions", true, true) 167 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 168 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) 169 INITIALIZE_PASS_DEPENDENCY(DominanceFrontier) 170 INITIALIZE_PASS_END(RegionInfoPass, "regions", 171 "Detect single entry single exit regions", true, true) 172 173 // Create methods available outside of this file, to use them 174 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by 175 // the link time optimization. 176 177 namespace llvm { 178 FunctionPass *createRegionInfoPass() { 179 return new RegionInfoPass(); 180 } 181 } 182 183
