1 //===- BlockFrequencyInfo.cpp - Block Frequency 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 //
10 // Loops should be simplified before this analysis.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Analysis/BlockFrequencyInfo.h"
15 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
16 #include "llvm/Analysis/BranchProbabilityInfo.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/Analysis/Passes.h"
19 #include "llvm/IR/CFG.h"
20 #include "llvm/InitializePasses.h"
21 #include "llvm/Support/CommandLine.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/GraphWriter.h"
24
25 using namespace llvm;
26
27 #define DEBUG_TYPE "block-freq"
28
29 #ifndef NDEBUG
30 static cl::opt<GVDAGType> ViewBlockFreqPropagationDAG(
31 "view-block-freq-propagation-dags", cl::Hidden,
32 cl::desc("Pop up a window to show a dag displaying how block "
33 "frequencies propagation through the CFG."),
34 cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
35 clEnumValN(GVDT_Fraction, "fraction",
36 "display a graph using the "
37 "fractional block frequency representation."),
38 clEnumValN(GVDT_Integer, "integer",
39 "display a graph using the raw "
40 "integer fractional block frequency representation."),
41 clEnumValN(GVDT_Count, "count", "display a graph using the real "
42 "profile count if available."),
43 clEnumValEnd));
44
45 cl::opt<std::string>
46 ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,
47 cl::desc("The option to specify "
48 "the name of the function "
49 "whose CFG will be displayed."));
50
51 cl::opt<unsigned>
52 ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
53 cl::desc("An integer in percent used to specify "
54 "the hot blocks/edges to be displayed "
55 "in red: a block or edge whose frequency "
56 "is no less than the max frequency of the "
57 "function multiplied by this percent."));
58
59 namespace llvm {
60
61 template <>
62 struct GraphTraits<BlockFrequencyInfo *> {
63 typedef const BasicBlock NodeType;
64 typedef succ_const_iterator ChildIteratorType;
65 typedef Function::const_iterator nodes_iterator;
66
getEntryNodellvm::GraphTraits67 static inline const NodeType *getEntryNode(const BlockFrequencyInfo *G) {
68 return &G->getFunction()->front();
69 }
child_beginllvm::GraphTraits70 static ChildIteratorType child_begin(const NodeType *N) {
71 return succ_begin(N);
72 }
child_endllvm::GraphTraits73 static ChildIteratorType child_end(const NodeType *N) {
74 return succ_end(N);
75 }
nodes_beginllvm::GraphTraits76 static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
77 return G->getFunction()->begin();
78 }
nodes_endllvm::GraphTraits79 static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
80 return G->getFunction()->end();
81 }
82 };
83
84 typedef BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>
85 BFIDOTGTraitsBase;
86
87 template <>
88 struct DOTGraphTraits<BlockFrequencyInfo *> : public BFIDOTGTraitsBase {
DOTGraphTraitsllvm::DOTGraphTraits89 explicit DOTGraphTraits(bool isSimple = false)
90 : BFIDOTGTraitsBase(isSimple) {}
91
getNodeLabelllvm::DOTGraphTraits92 std::string getNodeLabel(const BasicBlock *Node,
93 const BlockFrequencyInfo *Graph) {
94
95 return BFIDOTGTraitsBase::getNodeLabel(Node, Graph,
96 ViewBlockFreqPropagationDAG);
97 }
98
getNodeAttributesllvm::DOTGraphTraits99 std::string getNodeAttributes(const BasicBlock *Node,
100 const BlockFrequencyInfo *Graph) {
101 return BFIDOTGTraitsBase::getNodeAttributes(Node, Graph,
102 ViewHotFreqPercent);
103 }
104
getEdgeAttributesllvm::DOTGraphTraits105 std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
106 const BlockFrequencyInfo *BFI) {
107 return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),
108 ViewHotFreqPercent);
109 }
110 };
111
112 } // end namespace llvm
113 #endif
114
BlockFrequencyInfo()115 BlockFrequencyInfo::BlockFrequencyInfo() {}
116
BlockFrequencyInfo(const Function & F,const BranchProbabilityInfo & BPI,const LoopInfo & LI)117 BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
118 const BranchProbabilityInfo &BPI,
119 const LoopInfo &LI) {
120 calculate(F, BPI, LI);
121 }
122
BlockFrequencyInfo(BlockFrequencyInfo && Arg)123 BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
124 : BFI(std::move(Arg.BFI)) {}
125
operator =(BlockFrequencyInfo && RHS)126 BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
127 releaseMemory();
128 BFI = std::move(RHS.BFI);
129 return *this;
130 }
131
132 // Explicitly define the default constructor otherwise it would be implicitly
133 // defined at the first ODR-use which is the BFI member in the
134 // LazyBlockFrequencyInfo header. The dtor needs the BlockFrequencyInfoImpl
135 // template instantiated which is not available in the header.
~BlockFrequencyInfo()136 BlockFrequencyInfo::~BlockFrequencyInfo() {}
137
calculate(const Function & F,const BranchProbabilityInfo & BPI,const LoopInfo & LI)138 void BlockFrequencyInfo::calculate(const Function &F,
139 const BranchProbabilityInfo &BPI,
140 const LoopInfo &LI) {
141 if (!BFI)
142 BFI.reset(new ImplType);
143 BFI->calculate(F, BPI, LI);
144 #ifndef NDEBUG
145 if (ViewBlockFreqPropagationDAG != GVDT_None &&
146 (ViewBlockFreqFuncName.empty() ||
147 F.getName().equals(ViewBlockFreqFuncName))) {
148 view();
149 }
150 #endif
151 }
152
getBlockFreq(const BasicBlock * BB) const153 BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
154 return BFI ? BFI->getBlockFreq(BB) : 0;
155 }
156
157 Optional<uint64_t>
getBlockProfileCount(const BasicBlock * BB) const158 BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
159 if (!BFI)
160 return None;
161
162 return BFI->getBlockProfileCount(*getFunction(), BB);
163 }
164
setBlockFreq(const BasicBlock * BB,uint64_t Freq)165 void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
166 assert(BFI && "Expected analysis to be available");
167 BFI->setBlockFreq(BB, Freq);
168 }
169
170 /// Pop up a ghostview window with the current block frequency propagation
171 /// rendered using dot.
view() const172 void BlockFrequencyInfo::view() const {
173 // This code is only for debugging.
174 #ifndef NDEBUG
175 ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
176 #else
177 errs() << "BlockFrequencyInfo::view is only available in debug builds on "
178 "systems with Graphviz or gv!\n";
179 #endif // NDEBUG
180 }
181
getFunction() const182 const Function *BlockFrequencyInfo::getFunction() const {
183 return BFI ? BFI->getFunction() : nullptr;
184 }
185
getBPI() const186 const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {
187 return BFI ? &BFI->getBPI() : nullptr;
188 }
189
190 raw_ostream &BlockFrequencyInfo::
printBlockFreq(raw_ostream & OS,const BlockFrequency Freq) const191 printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
192 return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
193 }
194
195 raw_ostream &
printBlockFreq(raw_ostream & OS,const BasicBlock * BB) const196 BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
197 const BasicBlock *BB) const {
198 return BFI ? BFI->printBlockFreq(OS, BB) : OS;
199 }
200
getEntryFreq() const201 uint64_t BlockFrequencyInfo::getEntryFreq() const {
202 return BFI ? BFI->getEntryFreq() : 0;
203 }
204
releaseMemory()205 void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
206
print(raw_ostream & OS) const207 void BlockFrequencyInfo::print(raw_ostream &OS) const {
208 if (BFI)
209 BFI->print(OS);
210 }
211
212
213 INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
214 "Block Frequency Analysis", true, true)
215 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
216 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
217 INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
218 "Block Frequency Analysis", true, true)
219
220 char BlockFrequencyInfoWrapperPass::ID = 0;
221
222
BlockFrequencyInfoWrapperPass()223 BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
224 : FunctionPass(ID) {
225 initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
226 }
227
~BlockFrequencyInfoWrapperPass()228 BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {}
229
print(raw_ostream & OS,const Module *) const230 void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
231 const Module *) const {
232 BFI.print(OS);
233 }
234
getAnalysisUsage(AnalysisUsage & AU) const235 void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
236 AU.addRequired<BranchProbabilityInfoWrapperPass>();
237 AU.addRequired<LoopInfoWrapperPass>();
238 AU.setPreservesAll();
239 }
240
releaseMemory()241 void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
242
runOnFunction(Function & F)243 bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
244 BranchProbabilityInfo &BPI =
245 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
246 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
247 BFI.calculate(F, BPI, LI);
248 return false;
249 }
250
251 char BlockFrequencyAnalysis::PassID;
run(Function & F,AnalysisManager<Function> & AM)252 BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
253 AnalysisManager<Function> &AM) {
254 BlockFrequencyInfo BFI;
255 BFI.calculate(F, AM.getResult<BranchProbabilityAnalysis>(F),
256 AM.getResult<LoopAnalysis>(F));
257 return BFI;
258 }
259
260 PreservedAnalyses
run(Function & F,AnalysisManager<Function> & AM)261 BlockFrequencyPrinterPass::run(Function &F, AnalysisManager<Function> &AM) {
262 OS << "Printing analysis results of BFI for function "
263 << "'" << F.getName() << "':"
264 << "\n";
265 AM.getResult<BlockFrequencyAnalysis>(F).print(OS);
266 return PreservedAnalyses::all();
267 }
268