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