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