blob: 63049a56019846c5246b3ca0d74b2f64b09af953 [file] [log] [blame]
Michael Gottesman857d6e32013-11-14 00:05:07 +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"
Chandler Carruthed0881b2012-12-03 16:50:05 +000015#include "llvm/Analysis/BlockFrequencyImpl.h"
16#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
Michael Gottesmanfd8aee72013-11-14 02:27:46 +000027#ifndef NDEBUG
28enum GVDAGType {
29 GVDT_None,
30 GVDT_Fraction,
31 GVDT_Integer
32};
33
34static cl::opt<GVDAGType>
35ViewBlockFreqPropagationDAG("view-block-freq-propagation-dags", cl::Hidden,
36 cl::desc("Pop up a window to show a dag displaying how block "
37 "frequencies propagation through the CFG."),
38 cl::values(
39 clEnumValN(GVDT_None, "none",
40 "do not display graphs."),
41 clEnumValN(GVDT_Fraction, "fraction", "display a graph using the "
42 "fractional block frequency representation."),
43 clEnumValN(GVDT_Integer, "integer", "display a graph using the raw "
44 "integer fractional block frequency representation."),
45 clEnumValEnd));
46
47namespace llvm {
48
49template <>
50struct GraphTraits<BlockFrequencyInfo *> {
51 typedef const BasicBlock NodeType;
52 typedef succ_const_iterator ChildIteratorType;
53 typedef Function::const_iterator nodes_iterator;
54
55 static inline const NodeType *getEntryNode(const BlockFrequencyInfo *G) {
56 return G->getFunction()->begin();
57 }
58 static ChildIteratorType child_begin(const NodeType *N) {
59 return succ_begin(N);
60 }
61 static ChildIteratorType child_end(const NodeType *N) {
62 return succ_end(N);
63 }
64 static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
65 return G->getFunction()->begin();
66 }
67 static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
68 return G->getFunction()->end();
69 }
70};
71
72template<>
73struct DOTGraphTraits<BlockFrequencyInfo*> : public DefaultDOTGraphTraits {
74 explicit DOTGraphTraits(bool isSimple=false) :
75 DefaultDOTGraphTraits(isSimple) {}
76
77 static std::string getGraphName(const BlockFrequencyInfo *G) {
78 return G->getFunction()->getName();
79 }
80
81 std::string getNodeLabel(const BasicBlock *Node,
82 const BlockFrequencyInfo *Graph) {
83 std::string Result;
84 raw_string_ostream OS(Result);
85
86 OS << Node->getName().str() << ":";
87 switch (ViewBlockFreqPropagationDAG) {
88 case GVDT_Fraction:
Michael Gottesmanb0c1ed82013-12-14 00:25:42 +000089 Graph->printBlockFreq(OS, Node);
Michael Gottesmanfd8aee72013-11-14 02:27:46 +000090 break;
91 case GVDT_Integer:
92 OS << Graph->getBlockFreq(Node).getFrequency();
93 break;
94 case GVDT_None:
95 llvm_unreachable("If we are not supposed to render a graph we should "
96 "never reach this point.");
97 }
98
99 return Result;
100 }
101};
102
103} // end namespace llvm
104#endif
105
Michael Gottesman857d6e32013-11-14 00:05:07 +0000106INITIALIZE_PASS_BEGIN(BlockFrequencyInfo, "block-freq",
107 "Block Frequency Analysis", true, true)
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000108INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfo)
Michael Gottesman857d6e32013-11-14 00:05:07 +0000109INITIALIZE_PASS_END(BlockFrequencyInfo, "block-freq",
110 "Block Frequency Analysis", true, true)
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000111
Jakub Staszak875ebd52011-07-25 19:25:40 +0000112char BlockFrequencyInfo::ID = 0;
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000113
114
Jakub Staszak875ebd52011-07-25 19:25:40 +0000115BlockFrequencyInfo::BlockFrequencyInfo() : FunctionPass(ID) {
116 initializeBlockFrequencyInfoPass(*PassRegistry::getPassRegistry());
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000117}
118
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000119BlockFrequencyInfo::~BlockFrequencyInfo() {}
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000120
Jakub Staszak875ebd52011-07-25 19:25:40 +0000121void BlockFrequencyInfo::getAnalysisUsage(AnalysisUsage &AU) const {
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000122 AU.addRequired<BranchProbabilityInfo>();
123 AU.setPreservesAll();
124}
125
Jakub Staszak875ebd52011-07-25 19:25:40 +0000126bool BlockFrequencyInfo::runOnFunction(Function &F) {
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000127 BranchProbabilityInfo &BPI = getAnalysis<BranchProbabilityInfo>();
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000128 if (!BFI)
129 BFI.reset(new ImplType);
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000130 BFI->doFunction(&F, &BPI);
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000131#ifndef NDEBUG
132 if (ViewBlockFreqPropagationDAG != GVDT_None)
133 view();
134#endif
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000135 return false;
136}
137
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000138void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
139
Chandler Carruth343fad42011-10-19 10:12:41 +0000140void BlockFrequencyInfo::print(raw_ostream &O, const Module *) const {
141 if (BFI) BFI->print(O);
142}
143
Jakub Staszak96f8c552011-12-20 20:03:10 +0000144BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000145 return BFI ? BFI->getBlockFreq(BB) : 0;
Jakub Staszak668c6fa2011-06-23 21:56:59 +0000146}
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000147
148/// Pop up a ghostview window with the current block frequency propagation
149/// rendered using dot.
150void BlockFrequencyInfo::view() const {
151// This code is only for debugging.
152#ifndef NDEBUG
153 ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
154#else
155 errs() << "BlockFrequencyInfo::view is only available in debug builds on "
156 "systems with Graphviz or gv!\n";
157#endif // NDEBUG
158}
159
160const Function *BlockFrequencyInfo::getFunction() const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000161 return BFI ? BFI->Fn : nullptr;
Michael Gottesmanfd8aee72013-11-14 02:27:46 +0000162}
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000163
164raw_ostream &BlockFrequencyInfo::
165printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000166 return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000167}
168
169raw_ostream &
170BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
171 const BasicBlock *BB) const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000172 return BFI ? BFI->printBlockFreq(OS, BB) : OS;
Michael Gottesmanfd5c4b22013-12-14 00:06:03 +0000173}
Yuchen Wu5947c8f2013-12-20 22:11:11 +0000174
175uint64_t BlockFrequencyInfo::getEntryFreq() const {
Duncan P. N. Exon Smith3dbe1052014-03-25 18:01:38 +0000176 return BFI ? BFI->getEntryFreq() : 0;
Yuchen Wu5947c8f2013-12-20 22:11:11 +0000177}