LLVM  8.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/Config/llvm-config.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/IR/PassManager.h"
21 #include "llvm/Pass.h"
23 #include "llvm/Support/Compiler.h"
25 
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "region"
29 
30 namespace llvm {
31 
32 template class RegionBase<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>
45  "verify-region-info",
47  cl::desc("Verify region info (time consuming)"));
48 
49 static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style",
51  cl::Hidden,
52  cl::desc("style of printing regions"),
53  cl::values(
54  clEnumValN(Region::PrintNone, "none", "print no details"),
56  "print regions in detail with block_iterator"),
58  "print regions in detail with element_iterator")));
59 
60 //===----------------------------------------------------------------------===//
61 // Region implementation
62 //
63 
65  RegionInfo* RI,
66  DominatorTree *DT, Region *Parent) :
67  RegionBase<RegionTraits<Function>>(Entry, Exit, RI, DT, Parent) {
68 
69 }
70 
71 Region::~Region() = default;
72 
73 //===----------------------------------------------------------------------===//
74 // RegionInfo implementation
75 //
76 
77 RegionInfo::RegionInfo() = default;
78 
79 RegionInfo::~RegionInfo() = default;
80 
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  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
87  PAC.preservedSet<CFGAnalyses>());
88 }
89 
91  ++numRegions;
92 
93  // TODO: Slow. Should only be enabled if -stats is used.
94  if (R->isSimple())
95  ++numSimpleRegions;
96 }
97 
100  DT = DT_;
101  PDT = PDT_;
102  DF = DF_;
103 
104  TopLevelRegion = new Region(&F.getEntryBlock(), nullptr,
105  this, DT, nullptr);
106  updateStatistics(TopLevelRegion);
107  calculate(F);
108 }
109 
110 #ifndef NDEBUG
111 void RegionInfo::view() { viewRegion(this); }
112 
114 #endif
115 
116 //===----------------------------------------------------------------------===//
117 // RegionInfoPass implementation
118 //
119 
122 }
123 
125 
127  releaseMemory();
128 
129  auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
130  auto PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
131  auto DF = &getAnalysis<DominanceFrontierWrapperPass>().getDominanceFrontier();
132 
133  RI.recalculate(F, DT, PDT, DF);
134  return false;
135 }
136 
138  RI.releaseMemory();
139 }
140 
142  RI.verifyAnalysis();
143 }
144 
146  AU.setPreservesAll();
150 }
151 
152 void RegionInfoPass::print(raw_ostream &OS, const Module *) const {
153  RI.print(OS);
154 }
155 
156 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
158  RI.dump();
159 }
160 #endif
161 
162 char RegionInfoPass::ID = 0;
163 
165  "Detect single entry single exit regions", true, true)
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 
179  return new RegionInfoPass();
180  }
181 
182 } // end namespace llvm
183 
184 //===----------------------------------------------------------------------===//
185 // RegionInfoAnalysis implementation
186 //
187 
188 AnalysisKey RegionInfoAnalysis::Key;
189 
191  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  RI.recalculate(F, DT, PDT, DF);
197  return RI;
198 }
199 
201  : OS(OS) {}
202 
205  OS << "Region Tree for function: " << F.getName() << "\n";
207 
208  return PreservedAnalyses::all();
209 }
210 
213  AM.getResult<RegionInfoAnalysis>(F).verifyAnalysis();
214 
215  return PreservedAnalyses::all();
216 }
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:211
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:770
regions
Definition: RegionInfo.cpp:169
This class represents lattice values for constants.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
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:152
FunctionPass * createRegionInfoPass()
Definition: RegionInfo.cpp:178
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, DominanceFrontier *DF)
Definition: RegionInfo.cpp:98
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: RegionInfo.cpp:145
void initializeRegionInfoPassPass(PassRegistry &)
Analysis that detects all canonical Regions.
Definition: RegionInfo.h:70
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:81
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:305
void view()
Opens a viewer to show the GraphViz visualization of the regions.
Definition: RegionInfo.cpp:111
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Detect single entry single exit true
Definition: RegionInfo.cpp:169
Analysis pass which computes a DominanceFrontier.
A RegionNode represents a subregion or a BasicBlock that is part of a Region.
Definition: RegionInfo.h:119
RegionInfoPrinterPass(raw_ostream &OS)
Definition: RegionInfo.cpp:200
void verifyAnalysis() const
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, Region *Parent=nullptr)
Definition: RegionInfo.cpp:64
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: RegionInfo.cpp:141
~RegionInfo() override
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:203
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
bool isSimple() const
Is this a simple region?
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:639
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
RegionInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:190
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
void viewOnly()
Opens a viewer to show the GraphViz visualization of this region without instructions in the BasicBlo...
Definition: RegionInfo.cpp:113
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
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:137
A single entry single exit Region.
Definition: RegionInfo.h:68
Analysis pass that exposes the RegionInfo for a function.
Definition: RegionInfo.h:972
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:115
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:614
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:215
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:642
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:92
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
Definition: RegionInfo.cpp:126
void updateStatistics(Region *R) final
Definition: RegionInfo.cpp:90
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
print Instructions which execute on loop entry
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
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:71
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:435