blob: ac4ee8f11e0a0e5189fb921716ba13b61d99a81c [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
Wei Mideee61e2015-07-14 23:40:50 +0000116void BlockFrequencyInfo::calculate(const Function &F,
117 const BranchProbabilityInfo &BPI,
118 const LoopInfo &LI) {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000119 if (!BFI)
120 BFI.reset(new ImplType);
Cong Hou5e67b662015-07-15 19:58:26 +0000121 BFI->calculate(F, BPI, LI);
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000122#ifndef NDEBUG
123 if (ViewBlockFreqPropagationDAG != GVDT_None)
124 view();
125#endif
Chandler Carruth343fad42011-10-19 10:12:41 +0000126}
127
Jakub Staszak96f8c552011-12-20 20:03:10 +0000128BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000129 return BFI ? BFI->getBlockFreq(BB) : 0;
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000130}
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000131
132/// Pop up a ghostview window with the current block frequency propagation
133/// rendered using dot.
134void BlockFrequencyInfo::view() const {
135// This code is only for debugging.
136#ifndef NDEBUG
137 ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
138#else
139 errs() << "BlockFrequencyInfo::view is only available in debug builds on "
140 "systems with Graphviz or gv!\n";
141#endif // NDEBUG
142}
143
144const Function *BlockFrequencyInfo::getFunction() const {
Duncan P. N. Exon Smith10be9a82014-04-21 17:57:07 +0000145 return BFI ? BFI->getFunction() : nullptr;
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000146}
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000147
148raw_ostream &BlockFrequencyInfo::
149printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000150 return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000151}
152
153raw_ostream &
154BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
155 const BasicBlock *BB) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000156 return BFI ? BFI->printBlockFreq(OS, BB) : OS;
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000157}
Yuchen Wu5947c8f2013-12-20 22:11:11 +0000158
159uint64_t BlockFrequencyInfo::getEntryFreq() const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000160 return BFI ? BFI->getEntryFreq() : 0;
Yuchen Wu5947c8f2013-12-20 22:11:11 +0000161}
Wei Mideee61e2015-07-14 23:40:50 +0000162
163void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
164
165void BlockFrequencyInfo::print(raw_ostream &OS) const {
166 if (BFI)
167 BFI->print(OS);
168}
169
170
171INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
172 "Block Frequency Analysis", true, true)
Cong Houab23bfb2015-07-15 22:48:29 +0000173INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
Wei Mideee61e2015-07-14 23:40:50 +0000174INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
175INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
176 "Block Frequency Analysis", true, true)
177
178char BlockFrequencyInfoWrapperPass::ID = 0;
179
180
181BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
182 : FunctionPass(ID) {
183 initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
184}
185
186BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {}
187
188void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
189 const Module *) const {
190 BFI.print(OS);
191}
192
193void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
Cong Houab23bfb2015-07-15 22:48:29 +0000194 AU.addRequired<BranchProbabilityInfoWrapperPass>();
Wei Mideee61e2015-07-14 23:40:50 +0000195 AU.addRequired<LoopInfoWrapperPass>();
196 AU.setPreservesAll();
197}
198
199void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
200
201bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
Cong Houab23bfb2015-07-15 22:48:29 +0000202 BranchProbabilityInfo &BPI =
203 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
Wei Mideee61e2015-07-14 23:40:50 +0000204 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
205 BFI.calculate(F, BPI, LI);
206 return false;
207}