LLVM  15.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"
14 #include "llvm/InitializePasses.h"
15 #ifndef NDEBUG
17 #endif
19 #include "llvm/Config/llvm-config.h"
20 #include "llvm/IR/Function.h"
22 #include "llvm/Support/Compiler.h"
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "region"
27 
28 namespace llvm {
29 
30 template class RegionBase<RegionTraits<Function>>;
33 
34 } // end namespace llvm
35 
36 STATISTIC(numRegions, "The # of regions");
37 STATISTIC(numSimpleRegions, "The # of simple regions");
38 
39 // Always verify if expensive checking is enabled.
40 
41 static cl::opt<bool,true>
43  "verify-region-info",
45  cl::desc("Verify region info (time consuming)"));
46 
47 static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style",
49  cl::Hidden,
50  cl::desc("style of printing regions"),
51  cl::values(
52  clEnumValN(Region::PrintNone, "none", "print no details"),
54  "print regions in detail with block_iterator"),
56  "print regions in detail with element_iterator")));
57 
58 //===----------------------------------------------------------------------===//
59 // Region implementation
60 //
61 
63  RegionInfo* RI,
64  DominatorTree *DT, Region *Parent) :
65  RegionBase<RegionTraits<Function>>(Entry, Exit, RI, DT, Parent) {
66 
67 }
68 
69 Region::~Region() = default;
70 
71 //===----------------------------------------------------------------------===//
72 // RegionInfo implementation
73 //
74 
75 RegionInfo::RegionInfo() = default;
76 
77 RegionInfo::~RegionInfo() = default;
78 
81  // Check whether the analysis, all analyses on functions, or the function's
82  // CFG has been preserved.
83  auto PAC = PA.getChecker<RegionInfoAnalysis>();
84  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
85  PAC.preservedSet<CFGAnalyses>());
86 }
87 
89  ++numRegions;
90 
91  // TODO: Slow. Should only be enabled if -stats is used.
92  if (R->isSimple())
93  ++numSimpleRegions;
94 }
95 
98  DT = DT_;
99  PDT = PDT_;
100  DF = DF_;
101 
102  TopLevelRegion = new Region(&F.getEntryBlock(), nullptr,
103  this, DT, nullptr);
104  updateStatistics(TopLevelRegion);
105  calculate(F);
106 }
107 
108 #ifndef NDEBUG
109 void RegionInfo::view() { viewRegion(this); }
110 
112 #endif
113 
114 //===----------------------------------------------------------------------===//
115 // RegionInfoPass implementation
116 //
117 
120 }
121 
123 
125  releaseMemory();
126 
127  auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
128  auto PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
129  auto DF = &getAnalysis<DominanceFrontierWrapperPass>().getDominanceFrontier();
130 
131  RI.recalculate(F, DT, PDT, DF);
132  return false;
133 }
134 
136  RI.releaseMemory();
137 }
138 
140  RI.verifyAnalysis();
141 }
142 
144  AU.setPreservesAll();
148 }
149 
150 void RegionInfoPass::print(raw_ostream &OS, const Module *) const {
151  RI.print(OS);
152 }
153 
154 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
156  RI.dump();
157 }
158 #endif
159 
160 char RegionInfoPass::ID = 0;
161 
163  "Detect single entry single exit regions", true, true)
168  "Detect single entry single exit regions", true, true)
169 
170 // Create methods available outside of this file, to use them
171 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
172 // the link time optimization.
173 
174 namespace llvm {
175 
177  return new RegionInfoPass();
178  }
179 
180 } // end namespace llvm
181 
182 //===----------------------------------------------------------------------===//
183 // RegionInfoAnalysis implementation
184 //
185 
186 AnalysisKey RegionInfoAnalysis::Key;
187 
189  RegionInfo RI;
190  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
191  auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);
192  auto *DF = &AM.getResult<DominanceFrontierAnalysis>(F);
193 
194  RI.recalculate(F, DT, PDT, DF);
195  return RI;
196 }
197 
199  : OS(OS) {}
200 
203  OS << "Region Tree for function: " << F.getName() << "\n";
205 
206  return PreservedAnalyses::all();
207 }
208 
211  AM.getResult<RegionInfoAnalysis>(F).verifyAnalysis();
212 
213  return PreservedAnalyses::all();
214 }
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:111
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::RegionInfo::updateStatistics
void updateStatistics(Region *R) final
Definition: RegionInfo.cpp:88
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:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
DominanceFrontier.h
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:152
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:780
llvm::RegionInfoPrinterPass::RegionInfoPrinterPass
RegionInfoPrinterPass(raw_ostream &OS)
Definition: RegionInfo.cpp:198
llvm::RegionInfo::recalculate
void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, DominanceFrontier *DF)
Definition: RegionInfo.cpp:96
llvm::Function
Definition: Function.h:60
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:447
llvm::RegionBase
A single entry single exit Region.
Definition: RegionInfo.h:65
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:135
Statistic.h
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
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:139
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::RegionInfoPass::dump
void dump() const
Definition: RegionInfo.cpp:155
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
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:124
RegionPrinter.h
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:167
llvm::RegionInfoAnalysis
Analysis pass that exposes the RegionInfo for a function.
Definition: RegionInfo.h:967
llvm::RegionInfoBase::dump
void dump() const
Definition: RegionInfoImpl.h:790
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:302
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:54
llvm::RegionInfoPass::print
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
Definition: RegionInfo.cpp:150
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
llvm::initializeRegionInfoPassPass
void initializeRegionInfoPassPass(PassRegistry &)
llvm::RegionInfoBase
Analysis that detects all canonical Regions.
Definition: RegionInfo.h:67
llvm::RegionBase< RegionTraits< Function > >::PrintNone
@ PrintNone
Definition: RegionInfo.h:429
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:201
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:1392
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:685
true
Detect single entry single exit true
Definition: RegionInfo.cpp:168
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:69
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:188
RegionInfoImpl.h
llvm::RegionInfoBase::print
void print(raw_ostream &OS) const
Definition: RegionInfoImpl.h:782
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
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:113
Compiler.h
clEnumValN
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:660
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:79
llvm::RegionInfo::view
void view()
Opens a viewer to show the GraphViz visualization of the regions.
Definition: RegionInfo.cpp:109
llvm::RegionInfo::RegionInfo
RegionInfo()
llvm::RegionTraits< Function >
Definition: RegionInfo.h:85
llvm::RegionInfoBase::verifyAnalysis
void verifyAnalysis() const
Definition: RegionInfoImpl.h:802
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:158
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:176
llvm::Region::Region
Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, Region *Parent=nullptr)
Definition: RegionInfo.cpp:62
llvm::viewRegion
void viewRegion(llvm::RegionInfo *RI)
Open a viewer to display the GraphViz vizualization of the analysis result.
Definition: RegionPrinter.cpp:245
llvm::RegionInfoPass::~RegionInfoPass
~RegionInfoPass() override
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::RegionInfoBase::releaseMemory
void releaseMemory()
Definition: RegionInfoImpl.h:794
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:143
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:310
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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:405
llvm::Region
Definition: RegionInfo.h:889
llvm::RegionInfoVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: RegionInfo.cpp:209
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:251
entry
print Instructions which execute on loop entry
Definition: MustExecute.cpp:336
llvm::RegionInfoPass::RegionInfoPass
RegionInfoPass()
Definition: RegionInfo.cpp:118