blob: 7be33658518af86f4b6ff7aa43eee5cd3c1979ae [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) {
58 return G->getFunction()->begin();
59 }
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
Wei Mideee61e2015-07-14 23:40:50 +0000108void BlockFrequencyInfo::calculate(const Function &F,
109 const BranchProbabilityInfo &BPI,
110 const LoopInfo &LI) {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000111 if (!BFI)
112 BFI.reset(new ImplType);
Duncan P. N. Exon Smith10be9a82014-04-21 17:57:07 +0000113 BFI->doFunction(&F, &BPI, &LI);
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000114#ifndef NDEBUG
115 if (ViewBlockFreqPropagationDAG != GVDT_None)
116 view();
117#endif
Chandler Carruth343fad42011-10-19 10:12:41 +0000118}
119
Jakub Staszak96f8c552011-12-20 20:03:10 +0000120BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000121 return BFI ? BFI->getBlockFreq(BB) : 0;
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000122}
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000123
124/// Pop up a ghostview window with the current block frequency propagation
125/// rendered using dot.
126void BlockFrequencyInfo::view() const {
127// This code is only for debugging.
128#ifndef NDEBUG
129 ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
130#else
131 errs() << "BlockFrequencyInfo::view is only available in debug builds on "
132 "systems with Graphviz or gv!\n";
133#endif // NDEBUG
134}
135
136const Function *BlockFrequencyInfo::getFunction() const {
Duncan P. N. Exon Smith10be9a82014-04-21 17:57:07 +0000137 return BFI ? BFI->getFunction() : nullptr;
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000138}
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000139
140raw_ostream &BlockFrequencyInfo::
141printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000142 return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000143}
144
145raw_ostream &
146BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
147 const BasicBlock *BB) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000148 return BFI ? BFI->printBlockFreq(OS, BB) : OS;
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000149}
Yuchen Wu5947c8f2013-12-20 22:11:11 +0000150
151uint64_t BlockFrequencyInfo::getEntryFreq() const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000152 return BFI ? BFI->getEntryFreq() : 0;
Yuchen Wu5947c8f2013-12-20 22:11:11 +0000153}
Wei Mideee61e2015-07-14 23:40:50 +0000154
155void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
156
157void BlockFrequencyInfo::print(raw_ostream &OS) const {
158 if (BFI)
159 BFI->print(OS);
160}
161
162
163INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
164 "Block Frequency Analysis", true, true)
165INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfo)
166INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
167INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
168 "Block Frequency Analysis", true, true)
169
170char BlockFrequencyInfoWrapperPass::ID = 0;
171
172
173BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
174 : FunctionPass(ID) {
175 initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
176}
177
178BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {}
179
180void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
181 const Module *) const {
182 BFI.print(OS);
183}
184
185void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
186 AU.addRequired<BranchProbabilityInfo>();
187 AU.addRequired<LoopInfoWrapperPass>();
188 AU.setPreservesAll();
189}
190
191void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
192
193bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
194 BranchProbabilityInfo &BPI = getAnalysis<BranchProbabilityInfo>();
195 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
196 BFI.calculate(F, BPI, LI);
197 return false;
198}