LLVM  6.0.0svn
RegionInfo.cpp
Go to the documentation of this file.
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 
13 #include "llvm/ADT/Statistic.h"
14 #ifndef NDEBUG
16 #endif
18 #include "llvm/IR/Function.h"
19 #include "llvm/IR/PassManager.h"
20 #include "llvm/Pass.h"
22 #include "llvm/Support/Compiler.h"
24 
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "region"
28 
29 namespace llvm {
30 
31 template class RegionBase<RegionTraits<Function>>;
34 
35 } // end namespace llvm
36 
37 STATISTIC(numRegions, "The # of regions");
38 STATISTIC(numSimpleRegions, "The # of simple regions");
39 
40 // Always verify if expensive checking is enabled.
41 
42 static cl::opt<bool,true>
44  "verify-region-info",
46  cl::desc("Verify region info (time consuming)"));
47 
48 static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style",
50  cl::Hidden,
51  cl::desc("style of printing regions"),
52  cl::values(
53  clEnumValN(Region::PrintNone, "none", "print no details"),
55  "print regions in detail with block_iterator"),
57  "print regions in detail with element_iterator")));
58 
59 //===----------------------------------------------------------------------===//
60 // Region implementation
61 //
62 
64  RegionInfo* RI,
65  DominatorTree *DT, Region *Parent) :
66  RegionBase<RegionTraits<Function>>(Entry, Exit, RI, DT, Parent) {
67 
68 }
69 
70 Region::~Region() = default;
71 
72 //===----------------------------------------------------------------------===//
73 // RegionInfo implementation
74 //
75 
76 RegionInfo::RegionInfo() = default;
77 
78 RegionInfo::~RegionInfo() = default;
79 
82  // Check whether the analysis, all analyses on functions, or the function's
83  // CFG have been preserved.
84  auto PAC = PA.getChecker<RegionInfoAnalysis>();
85  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
86  PAC.preservedSet<CFGAnalyses>());
87 }
88 
90  ++numRegions;
91 
92  // TODO: Slow. Should only be enabled if -stats is used.
93  if (R->isSimple())
94  ++numSimpleRegions;
95 }
96 
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 
113 #endif
114 
115 //===----------------------------------------------------------------------===//
116 // RegionInfoPass implementation
117 //
118 
121 }
122 
124 
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 
137  RI.releaseMemory();
138 }
139 
141  RI.verifyAnalysis();
142 }
143 
145  AU.setPreservesAll();
149 }
150 
151 void RegionInfoPass::print(raw_ostream &OS, const Module *) const {
152  RI.print(OS);
153 }
154 
155 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
157  RI.dump();
158 }
159 #endif
160 
161 char RegionInfoPass::ID = 0;
162 
164  "Detect single entry single exit regions", true, true)
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 
175 namespace llvm {
176 
178  return new RegionInfoPass();
179  }
180 
181 } // end namespace llvm
182 
183 //===----------------------------------------------------------------------===//
184 // RegionInfoAnalysis implementation
185 //
186 
187 AnalysisKey RegionInfoAnalysis::Key;
188 
190  RegionInfo RI;
191  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
192  auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);
193  auto *DF = &AM.getResult<DominanceFrontierAnalysis>(F);
194 
195  RI.recalculate(F, DT, PDT, DF);
196  return RI;
197 }
198 
200  : OS(OS) {}
201 
204  OS << "Region Tree for function: " << F.getName() << "\n";
205  AM.getResult<RegionInfoAnalysis>(F).print(OS);
206 
207  return PreservedAnalyses::all();
208 }
209 
212  AM.getResult<RegionInfoAnalysis>(F).verifyAnalysis();
213 
214  return PreservedAnalyses::all();
215 }
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:210
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void viewRegion(llvm::RegionInfo *RI)
Open a viewer to display the GraphViz vizualization of the analysis result.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
regions
Definition: RegionInfo.cpp:168
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions", "Detect single entry single exit regions", true, true) INITIALIZE_PASS_END(RegionInfoPass
void print(raw_ostream &OS) const
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
Definition: RegionInfo.cpp:151
FunctionPass * createRegionInfoPass()
Definition: RegionInfo.cpp:177
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:232
void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, DominanceFrontier *DF)
Definition: RegionInfo.cpp:97
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: RegionInfo.cpp:144
void initializeRegionInfoPassPass(PassRegistry &)
Analysis that detects all canonical Regions.
Definition: RegionInfo.h:69
void viewRegionOnly(llvm::RegionInfo *RI)
Open a viewer to display the GraphViz vizualization of the analysis result.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: RegionInfo.cpp:80
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
void view()
Opens a viewer to show the GraphViz visualization of the regions.
Definition: RegionInfo.cpp:110
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Detect single entry single exit true
Definition: RegionInfo.cpp:168
Analysis pass which computes a DominanceFrontier.
A RegionNode represents a subregion or a BasicBlock that is part of a Region.
Definition: RegionInfo.h:118
RegionInfoPrinterPass(raw_ostream &OS)
Definition: RegionInfo.cpp:199
void verifyAnalysis() const
#define F(x, y, z)
Definition: MD5.cpp:55
Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, Region *Parent=nullptr)
Definition: RegionInfo.cpp:63
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: RegionInfo.cpp:140
~RegionInfo() override
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:202
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:134
bool isSimple() const
Is this a simple region?
const BasicBlock & getEntryBlock() const
Definition: Function.h:564
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:624
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
RegionInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:189
void viewOnly()
Opens a viewer to show the GraphViz visualization of this region without instructions in the BasicBlo...
Definition: RegionInfo.cpp:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
~RegionInfoPass() override
Analysis pass which computes a PostDominatorTree.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: RegionInfo.cpp:136
A single entry single exit Region.
Definition: RegionInfo.h:67
Analysis pass that exposes the RegionInfo for a function.
Definition: RegionInfo.h:966
void setPreservesAll()
Set by analyses that do not transform their input at all.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:599
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
static cl::opt< Region::PrintStyle, true > printStyleX("print-region-style", cl::location(RegionInfo::printStyle), cl::Hidden, cl::desc("style of printing regions"), cl::values(clEnumValN(Region::PrintNone, "none", "print no details"), clEnumValN(Region::PrintBB, "bb", "print regions in detail with block_iterator"), clEnumValN(Region::PrintRN, "rn", "print regions in detail with element_iterator")))
AnalysisUsage & addRequiredTransitive()
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
Definition: RegionInfo.cpp:125
void updateStatistics(Region *R) final
Definition: RegionInfo.cpp:89
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:261
This header defines various interfaces for pass management in LLVM.
static cl::opt< bool, true > VerifyRegionInfoX("verify-region-info", cl::location(RegionInfoBase< RegionTraits< Function >>::VerifyRegionInfo), cl::desc("Verify region info (time consuming)"))
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:420