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