LLVM  14.0.0git
RegionInfo.cpp
Go to the documentation of this file.
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 
12 #include "llvm/ADT/Statistic.h"
13 #include "llvm/InitializePasses.h"
14 #ifndef NDEBUG
16 #endif
18 #include "llvm/Config/llvm-config.h"
19 #include "llvm/IR/Function.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>>;
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>
42  "verify-region-info",
44  cl::desc("Verify region info (time consuming)"));
45 
46 static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style",
48  cl::Hidden,
49  cl::desc("style of printing regions"),
50  cl::values(
51  clEnumValN(Region::PrintNone, "none", "print no details"),
53  "print regions in detail with block_iterator"),
55  "print regions in detail with element_iterator")));
56 
57 //===----------------------------------------------------------------------===//
58 // Region implementation
59 //
60 
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 
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 
88  ++numRegions;
89 
90  // TODO: Slow. Should only be enabled if -stats is used.
91  if (R->isSimple())
92  ++numSimpleRegions;
93 }
94 
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
108 void RegionInfo::view() { viewRegion(this); }
109 
111 #endif
112 
113 //===----------------------------------------------------------------------===//
114 // RegionInfoPass implementation
115 //
116 
119 }
120 
122 
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 
135  RI.releaseMemory();
136 }
137 
139  RI.verifyAnalysis();
140 }
141 
143  AU.setPreservesAll();
147 }
148 
149 void RegionInfoPass::print(raw_ostream &OS, const Module *) const {
150  RI.print(OS);
151 }
152 
153 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
155  RI.dump();
156 }
157 #endif
158 
159 char RegionInfoPass::ID = 0;
160 
162  "Detect single entry single exit regions", true, true)
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 
176  return new RegionInfoPass();
177  }
178 
179 } // end namespace llvm
180 
181 //===----------------------------------------------------------------------===//
182 // RegionInfoAnalysis implementation
183 //
184 
185 AnalysisKey RegionInfoAnalysis::Key;
186 
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 
198  : OS(OS) {}
199 
202  OS << "Region Tree for function: " << F.getName() << "\n";
204 
205  return PreservedAnalyses::all();
206 }
207 
210  AM.getResult<RegionInfoAnalysis>(F).verifyAnalysis();
211 
212  return PreservedAnalyses::all();
213 }
llvm::RegionInfoPass::ID
static char ID
Definition: RegionInfo.h:946
RegionInfo.h
llvm::RegionInfo::viewOnly
void viewOnly()
Opens a viewer to show the GraphViz visualization of this region without instructions in the BasicBlo...
Definition: RegionInfo.cpp:110
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::RegionInfo::updateStatistics
void updateStatistics(Region *R) final
Definition: RegionInfo.cpp:87
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:506
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:783
llvm::RegionInfoPrinterPass::RegionInfoPrinterPass
RegionInfoPrinterPass(raw_ostream &OS)
Definition: RegionInfo.cpp:197
llvm::RegionInfo::recalculate
void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, DominanceFrontier *DF)
Definition: RegionInfo.cpp:95
llvm::Function
Definition: Function.h:62
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:457
llvm::RegionBase
A single entry single exit Region.
Definition: RegionInfo.h:66
llvm::RegionInfoPass::releaseMemory
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:134
Statistic.h
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:93
llvm::RegionInfoPass::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: RegionInfo.cpp:138
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::RegionInfoPass::dump
void dump() const
Definition: RegionInfo.cpp:154
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::RegionInfoPass::runOnFunction
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: RegionInfo.cpp:123
RegionPrinter.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
CommandLine.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
regions
regions
Definition: RegionInfo.cpp:166
llvm::RegionInfoAnalysis
Analysis pass that exposes the RegionInfo for a function.
Definition: RegionInfo.h:967
llvm::RegionInfoBase::dump
void dump() const
Definition: RegionInfoImpl.h:792
llvm::PostDominatorTreeWrapperPass
Definition: PostDominators.h:73
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::RegionInfoPass::print
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
Definition: RegionInfo.cpp:149
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:670
llvm::initializeRegionInfoPassPass
void initializeRegionInfoPassPass(PassRegistry &)
llvm::RegionInfoBase
Analysis that detects all canonical Regions.
Definition: RegionInfo.h:68
llvm::RegionBase< RegionTraits< Function > >::PrintNone
@ PrintNone
Definition: RegionInfo.h:429
DF
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
llvm::RegionInfoPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:200
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions", "Detect single entry single exit regions", true, true) INITIALIZE_PASS_END(RegionInfoPass
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::RegionInfoBase< RegionTraits< Function > >::printStyle
static RegionT::PrintStyle printStyle
Definition: RegionInfo.h:803
llvm::cl::opt
Definition: CommandLine.h:1432
llvm::cl::values
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:697
true
Detect single entry single exit true
Definition: RegionInfo.cpp:167
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::RegionBase< RegionTraits< Function > >::PrintRN
@ PrintRN
Definition: RegionInfo.h:429
printStyleX
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")))
VerifyRegionInfoX
static cl::opt< bool, true > VerifyRegionInfoX("verify-region-info", cl::location(RegionInfoBase< RegionTraits< Function >>::VerifyRegionInfo), cl::desc("Verify region info (time consuming)"))
llvm::RegionInfoAnalysis::run
RegionInfo run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:187
RegionInfoImpl.h
llvm::RegionInfoBase::print
void print(raw_ostream &OS) const
Definition: RegionInfoImpl.h:784
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::RegionInfoPass
Definition: RegionInfo.h:942
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
Compiler.h
clEnumValN
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:672
llvm::RegionInfo
Definition: RegionInfo.h:900
llvm::DominanceFrontierAnalysis
Analysis pass which computes a DominanceFrontier.
Definition: DominanceFrontier.h:182
llvm::RegionInfo::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: RegionInfo.cpp:78
llvm::RegionInfo::view
void view()
Opens a viewer to show the GraphViz visualization of the regions.
Definition: RegionInfo.cpp:108
llvm::RegionInfo::RegionInfo
RegionInfo()
llvm::RegionTraits< Function >
Definition: RegionInfo.h:85
llvm::RegionInfoBase::verifyAnalysis
void verifyAnalysis() const
Definition: RegionInfoImpl.h:804
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::RegionBase< RegionTraits< Function > >::PrintBB
@ PrintBB
Definition: RegionInfo.h:429
llvm::RegionTraits
Definition: RegionInfo.h:75
Function.h
llvm::RegionInfo::~RegionInfo
~RegionInfo() override
llvm::createRegionInfoPass
FunctionPass * createRegionInfoPass()
Definition: RegionInfo.cpp:175
llvm::Region::Region
Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, Region *Parent=nullptr)
Definition: RegionInfo.cpp:61
llvm::viewRegion
void viewRegion(llvm::RegionInfo *RI)
Open a viewer to display the GraphViz vizualization of the analysis result.
Definition: RegionPrinter.cpp:256
llvm::RegionInfoPass::~RegionInfoPass
~RegionInfoPass() override
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
llvm::RegionInfoBase::releaseMemory
void releaseMemory()
Definition: RegionInfoImpl.h:796
llvm::DominanceFrontier
Definition: DominanceFrontier.h:141
exit
declare void exit(i32) noreturn nounwind This compiles into
Definition: README.txt:1072
llvm::RegionNodeBase
A RegionNode represents a subregion or a BasicBlock that is part of a Region.
Definition: RegionInfo.h:117
llvm::RegionInfoPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: RegionInfo.cpp:142
llvm::AnalysisUsage::addRequiredTransitive
AnalysisUsage & addRequiredTransitive()
Definition: PassAnalysisSupport.h:81
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:313
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::PostDominatorTreeAnalysis
Analysis pass which computes a PostDominatorTree.
Definition: PostDominators.h:47
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DominanceFrontierWrapperPass
Definition: DominanceFrontier.h:155
llvm::cl::desc
Definition: CommandLine.h:412
llvm::Region
Definition: RegionInfo.h:889
llvm::RegionInfoVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:208
llvm::Region::~Region
~Region()
InitializePasses.h
llvm::viewRegionOnly
void viewRegionOnly(llvm::RegionInfo *RI)
Open a viewer to display the GraphViz vizualization of the analysis result.
Definition: RegionPrinter.cpp:262
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:339
llvm::RegionInfoPass::RegionInfoPass
RegionInfoPass()
Definition: RegionInfo.cpp:117
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38