LLVM  mainline
RegionInfo.cpp
Go to the documentation of this file.
00001 //===- RegionInfo.cpp - SESE region detection analysis --------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 // Detects single entry single exit regions in the control flow graph.
00010 //===----------------------------------------------------------------------===//
00011 
00012 #include "llvm/Analysis/RegionInfo.h"
00013 #include "llvm/ADT/PostOrderIterator.h"
00014 #include "llvm/ADT/Statistic.h"
00015 #include "llvm/Analysis/LoopInfo.h"
00016 #include "llvm/Analysis/RegionInfoImpl.h"
00017 #include "llvm/Analysis/RegionIterator.h"
00018 #include "llvm/Support/CommandLine.h"
00019 #include "llvm/Support/Debug.h"
00020 #include "llvm/Support/ErrorHandling.h"
00021 #include <algorithm>
00022 #include <iterator>
00023 #include <set>
00024 
00025 using namespace llvm;
00026 
00027 #define DEBUG_TYPE "region"
00028 
00029 namespace llvm {
00030 template class RegionBase<RegionTraits<Function>>;
00031 template class RegionNodeBase<RegionTraits<Function>>;
00032 template class RegionInfoBase<RegionTraits<Function>>;
00033 }
00034 
00035 STATISTIC(numRegions,       "The # of regions");
00036 STATISTIC(numSimpleRegions, "The # of simple regions");
00037 
00038 // Always verify if expensive checking is enabled.
00039 
00040 static cl::opt<bool,true>
00041 VerifyRegionInfoX(
00042   "verify-region-info",
00043   cl::location(RegionInfoBase<RegionTraits<Function>>::VerifyRegionInfo),
00044   cl::desc("Verify region info (time consuming)"));
00045 
00046 
00047 static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style",
00048   cl::location(RegionInfo::printStyle),
00049   cl::Hidden,
00050   cl::desc("style of printing regions"),
00051   cl::values(
00052     clEnumValN(Region::PrintNone, "none",  "print no details"),
00053     clEnumValN(Region::PrintBB, "bb",
00054                "print regions in detail with block_iterator"),
00055     clEnumValN(Region::PrintRN, "rn",
00056                "print regions in detail with element_iterator"),
00057     clEnumValEnd));
00058 
00059 
00060 //===----------------------------------------------------------------------===//
00061 // Region implementation
00062 //
00063 
00064 Region::Region(BasicBlock *Entry, BasicBlock *Exit,
00065                RegionInfo* RI,
00066                DominatorTree *DT, Region *Parent) :
00067   RegionBase<RegionTraits<Function>>(Entry, Exit, RI, DT, Parent) {
00068 
00069 }
00070 
00071 Region::~Region() { }
00072 
00073 //===----------------------------------------------------------------------===//
00074 // RegionInfo implementation
00075 //
00076 
00077 RegionInfo::RegionInfo() :
00078   RegionInfoBase<RegionTraits<Function>>() {
00079 
00080 }
00081 
00082 RegionInfo::~RegionInfo() {
00083 
00084 }
00085 
00086 void RegionInfo::updateStatistics(Region *R) {
00087   ++numRegions;
00088 
00089   // TODO: Slow. Should only be enabled if -stats is used.
00090   if (R->isSimple())
00091     ++numSimpleRegions;
00092 }
00093 
00094 void RegionInfo::recalculate(Function &F, DominatorTree *DT_,
00095                              PostDominatorTree *PDT_, DominanceFrontier *DF_) {
00096   DT = DT_;
00097   PDT = PDT_;
00098   DF = DF_;
00099 
00100   TopLevelRegion = new Region(&F.getEntryBlock(), nullptr,
00101                               this, DT, nullptr);
00102   updateStatistics(TopLevelRegion);
00103   calculate(F);
00104 }
00105 
00106 //===----------------------------------------------------------------------===//
00107 // RegionInfoPass implementation
00108 //
00109 
00110 RegionInfoPass::RegionInfoPass() : FunctionPass(ID) {
00111   initializeRegionInfoPassPass(*PassRegistry::getPassRegistry());
00112 }
00113 
00114 RegionInfoPass::~RegionInfoPass() {
00115 
00116 }
00117 
00118 bool RegionInfoPass::runOnFunction(Function &F) {
00119   releaseMemory();
00120 
00121   auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
00122   auto PDT = &getAnalysis<PostDominatorTree>();
00123   auto DF = &getAnalysis<DominanceFrontier>();
00124 
00125   RI.recalculate(F, DT, PDT, DF);
00126   return false;
00127 }
00128 
00129 void RegionInfoPass::releaseMemory() {
00130   RI.releaseMemory();
00131 }
00132 
00133 void RegionInfoPass::verifyAnalysis() const {
00134     RI.verifyAnalysis();
00135 }
00136 
00137 void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
00138   AU.setPreservesAll();
00139   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
00140   AU.addRequired<PostDominatorTree>();
00141   AU.addRequired<DominanceFrontier>();
00142 }
00143 
00144 void RegionInfoPass::print(raw_ostream &OS, const Module *) const {
00145   RI.print(OS);
00146 }
00147 
00148 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
00149 void RegionInfoPass::dump() const {
00150   RI.dump();
00151 }
00152 #endif
00153 
00154 char RegionInfoPass::ID = 0;
00155 
00156 INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions",
00157                 "Detect single entry single exit regions", true, true)
00158 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
00159 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
00160 INITIALIZE_PASS_DEPENDENCY(DominanceFrontier)
00161 INITIALIZE_PASS_END(RegionInfoPass, "regions",
00162                 "Detect single entry single exit regions", true, true)
00163 
00164 // Create methods available outside of this file, to use them
00165 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
00166 // the link time optimization.
00167 
00168 namespace llvm {
00169   FunctionPass *createRegionInfoPass() {
00170     return new RegionInfoPass();
00171   }
00172 }
00173