blob: ac7f6e28b3d0a16faed360f526e892cde37294a8 [file] [log] [blame]
Duncan P. N. Exon Smith689a5072014-04-11 23:20:58 +00001//===- BlockFrequencyInfo.cpp - Block Frequency Analysis ------------------===//
Jakub Staszak668c6fa2011-06-23 21:56:59 +00002//
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
Jakub Staszak875ebd52011-07-25 19:25:40 +000014#include "llvm/Analysis/BlockFrequencyInfo.h"
Duncan P. N. Exon Smith689a5072014-04-11 23:20:58 +000015#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000016#include "llvm/Analysis/BranchProbabilityInfo.h"
Jakub Staszak668c6fa2011-06-23 21:56:59 +000017#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/Analysis/Passes.h"
Chandler Carruth1305dc32014-03-04 11:45:46 +000019#include "llvm/IR/CFG.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000020#include "llvm/InitializePasses.h"
Michael Gottesmanfd8aee72013-11-14 02:27:46 +000021#include "llvm/Support/CommandLine.h"
22#include "llvm/Support/Debug.h"
23#include "llvm/Support/GraphWriter.h"
Jakub Staszak668c6fa2011-06-23 21:56:59 +000024
25using namespace llvm;
26
Chandler Carruthf1221bd2014-04-22 02:48:03 +000027#define DEBUG_TYPE "block-freq"
28
Michael Gottesmanfd8aee72013-11-14 02:27:46 +000029#ifndef NDEBUG
30enum GVDAGType {
31 GVDT_None,
32 GVDT_Fraction,
33 GVDT_Integer
34};
35
36static cl::opt<GVDAGType>
37ViewBlockFreqPropagationDAG("view-block-freq-propagation-dags", cl::Hidden,
38 cl::desc("Pop up a window to show a dag displaying how block "
39 "frequencies propagation through the CFG."),
40 cl::values(
41 clEnumValN(GVDT_None, "none",
42 "do not display graphs."),
43 clEnumValN(GVDT_Fraction, "fraction", "display a graph using the "
44 "fractional block frequency representation."),
45 clEnumValN(GVDT_Integer, "integer", "display a graph using the raw "
46 "integer fractional block frequency representation."),
47 clEnumValEnd));
48
49namespace llvm {
50
51template <>
52struct GraphTraits<BlockFrequencyInfo *> {
53 typedef const BasicBlock NodeType;
54 typedef succ_const_iterator ChildIteratorType;
55 typedef Function::const_iterator nodes_iterator;
56
57 static inline const NodeType *getEntryNode(const BlockFrequencyInfo *G) {
Duncan P. N. Exon Smith5a82c912015-10-10 00:53:03 +000058 return &G->getFunction()->front();
Michael Gottesmanfd8aee72013-11-14 02:27:46 +000059 }
60 static ChildIteratorType child_begin(const NodeType *N) {
61 return succ_begin(N);
62 }
63 static ChildIteratorType child_end(const NodeType *N) {
64 return succ_end(N);
65 }
66 static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
67 return G->getFunction()->begin();
68 }
69 static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
70 return G->getFunction()->end();
71 }
72};
73
74template<>
75struct DOTGraphTraits<BlockFrequencyInfo*> : public DefaultDOTGraphTraits {
76 explicit DOTGraphTraits(bool isSimple=false) :
77 DefaultDOTGraphTraits(isSimple) {}
78
79 static std::string getGraphName(const BlockFrequencyInfo *G) {
80 return G->getFunction()->getName();
81 }
82
83 std::string getNodeLabel(const BasicBlock *Node,
84 const BlockFrequencyInfo *Graph) {
Alp Tokere69170a2014-06-26 22:52:05 +000085 std::string Result;
86 raw_string_ostream OS(Result);
Michael Gottesmanfd8aee72013-11-14 02:27:46 +000087
Yaron Keren75e0c4b2015-03-27 17:51:30 +000088 OS << Node->getName() << ":";
Michael Gottesmanfd8aee72013-11-14 02:27:46 +000089 switch (ViewBlockFreqPropagationDAG) {
90 case GVDT_Fraction:
Michael Gottesmanb0c1ed82013-12-14 00:25:42 +000091 Graph->printBlockFreq(OS, Node);
Michael Gottesmanfd8aee72013-11-14 02:27:46 +000092 break;
93 case GVDT_Integer:
94 OS << Graph->getBlockFreq(Node).getFrequency();
95 break;
96 case GVDT_None:
97 llvm_unreachable("If we are not supposed to render a graph we should "
98 "never reach this point.");
99 }
100
Alp Tokere69170a2014-06-26 22:52:05 +0000101 return Result;
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000102 }
103};
104
105} // end namespace llvm
106#endif
107
Cong Hou9b4f6b22015-07-16 23:23:35 +0000108BlockFrequencyInfo::BlockFrequencyInfo() {}
109
110BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
111 const BranchProbabilityInfo &BPI,
112 const LoopInfo &LI) {
113 calculate(F, BPI, LI);
114}
115
Xinliang David Li28a93272016-05-05 21:13:27 +0000116BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
117 : BFI(std::move(Arg.BFI)) {}
118
119BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
120 releaseMemory();
121 BFI = std::move(RHS.BFI);
122 return *this;
123}
124
Wei Mideee61e2015-07-14 23:40:50 +0000125void BlockFrequencyInfo::calculate(const Function &F,
126 const BranchProbabilityInfo &BPI,
127 const LoopInfo &LI) {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000128 if (!BFI)
129 BFI.reset(new ImplType);
Cong Hou5e67b662015-07-15 19:58:26 +0000130 BFI->calculate(F, BPI, LI);
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000131#ifndef NDEBUG
132 if (ViewBlockFreqPropagationDAG != GVDT_None)
133 view();
134#endif
Chandler Carruth343fad42011-10-19 10:12:41 +0000135}
136
Jakub Staszak96f8c552011-12-20 20:03:10 +0000137BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000138 return BFI ? BFI->getBlockFreq(BB) : 0;
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000139}
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000140
Easwaran Raman12b79aa2016-03-23 18:18:26 +0000141Optional<uint64_t>
142BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
Xinliang David Lib12b3532016-06-22 17:12:12 +0000143 if (!BFI)
Easwaran Raman12b79aa2016-03-23 18:18:26 +0000144 return None;
Xinliang David Lib12b3532016-06-22 17:12:12 +0000145
146 return BFI->getBlockProfileCount(*getFunction(), BB);
Easwaran Raman12b79aa2016-03-23 18:18:26 +0000147}
148
Xinliang David Lib12b3532016-06-22 17:12:12 +0000149void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
Manman Ren72d44b12015-10-15 14:59:40 +0000150 assert(BFI && "Expected analysis to be available");
151 BFI->setBlockFreq(BB, Freq);
152}
153
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000154/// Pop up a ghostview window with the current block frequency propagation
155/// rendered using dot.
156void BlockFrequencyInfo::view() const {
157// This code is only for debugging.
158#ifndef NDEBUG
159 ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
160#else
161 errs() << "BlockFrequencyInfo::view is only available in debug builds on "
162 "systems with Graphviz or gv!\n";
163#endif // NDEBUG
164}
165
166const Function *BlockFrequencyInfo::getFunction() const {
Duncan P. N. Exon Smith10be9a82014-04-21 17:57:07 +0000167 return BFI ? BFI->getFunction() : nullptr;
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000168}
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000169
170raw_ostream &BlockFrequencyInfo::
171printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000172 return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000173}
174
175raw_ostream &
176BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
177 const BasicBlock *BB) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000178 return BFI ? BFI->printBlockFreq(OS, BB) : OS;
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000179}
Yuchen Wu5947c8f2013-12-20 22:11:11 +0000180
181uint64_t BlockFrequencyInfo::getEntryFreq() const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000182 return BFI ? BFI->getEntryFreq() : 0;
Yuchen Wu5947c8f2013-12-20 22:11:11 +0000183}
Wei Mideee61e2015-07-14 23:40:50 +0000184
185void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
186
187void BlockFrequencyInfo::print(raw_ostream &OS) const {
188 if (BFI)
189 BFI->print(OS);
190}
191
192
193INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
194 "Block Frequency Analysis", true, true)
Cong Houab23bfb2015-07-15 22:48:29 +0000195INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
Wei Mideee61e2015-07-14 23:40:50 +0000196INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
197INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
198 "Block Frequency Analysis", true, true)
199
200char BlockFrequencyInfoWrapperPass::ID = 0;
201
202
203BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
204 : FunctionPass(ID) {
205 initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
206}
207
208BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {}
209
210void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
211 const Module *) const {
212 BFI.print(OS);
213}
214
215void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
Cong Houab23bfb2015-07-15 22:48:29 +0000216 AU.addRequired<BranchProbabilityInfoWrapperPass>();
Wei Mideee61e2015-07-14 23:40:50 +0000217 AU.addRequired<LoopInfoWrapperPass>();
218 AU.setPreservesAll();
219}
220
221void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
222
223bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
Cong Houab23bfb2015-07-15 22:48:29 +0000224 BranchProbabilityInfo &BPI =
225 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
Wei Mideee61e2015-07-14 23:40:50 +0000226 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
227 BFI.calculate(F, BPI, LI);
228 return false;
229}
Xinliang David Li28a93272016-05-05 21:13:27 +0000230
231char BlockFrequencyAnalysis::PassID;
232BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
233 AnalysisManager<Function> &AM) {
234 BlockFrequencyInfo BFI;
235 BFI.calculate(F, AM.getResult<BranchProbabilityAnalysis>(F),
236 AM.getResult<LoopAnalysis>(F));
237 return BFI;
238}
239
240PreservedAnalyses
241BlockFrequencyPrinterPass::run(Function &F, AnalysisManager<Function> &AM) {
242 OS << "Printing analysis results of BFI for function "
243 << "'" << F.getName() << "':"
244 << "\n";
245 AM.getResult<BlockFrequencyAnalysis>(F).print(OS);
246 return PreservedAnalyses::all();
247}