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
25using namespace llvm;
26
27#define DEBUG_TYPE "block-freq"
28
29#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) {
85    std::string Result;
86    raw_string_ostream OS(Result);
87
88    OS << Node->getName().str() << ":";
89    switch (ViewBlockFreqPropagationDAG) {
90    case GVDT_Fraction:
91      Graph->printBlockFreq(OS, Node);
92      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
101    return Result;
102  }
103};
104
105} // end namespace llvm
106#endif
107
108INITIALIZE_PASS_BEGIN(BlockFrequencyInfo, "block-freq",
109                      "Block Frequency Analysis", true, true)
110INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfo)
111INITIALIZE_PASS_DEPENDENCY(LoopInfo)
112INITIALIZE_PASS_END(BlockFrequencyInfo, "block-freq",
113                    "Block Frequency Analysis", true, true)
114
115char BlockFrequencyInfo::ID = 0;
116
117
118BlockFrequencyInfo::BlockFrequencyInfo() : FunctionPass(ID) {
119  initializeBlockFrequencyInfoPass(*PassRegistry::getPassRegistry());
120}
121
122BlockFrequencyInfo::~BlockFrequencyInfo() {}
123
124void BlockFrequencyInfo::getAnalysisUsage(AnalysisUsage &AU) const {
125  AU.addRequired<BranchProbabilityInfo>();
126  AU.addRequired<LoopInfo>();
127  AU.setPreservesAll();
128}
129
130bool BlockFrequencyInfo::runOnFunction(Function &F) {
131  BranchProbabilityInfo &BPI = getAnalysis<BranchProbabilityInfo>();
132  LoopInfo &LI = getAnalysis<LoopInfo>();
133  if (!BFI)
134    BFI.reset(new ImplType);
135  BFI->doFunction(&F, &BPI, &LI);
136#ifndef NDEBUG
137  if (ViewBlockFreqPropagationDAG != GVDT_None)
138    view();
139#endif
140  return false;
141}
142
143void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
144
145void BlockFrequencyInfo::print(raw_ostream &O, const Module *) const {
146  if (BFI) BFI->print(O);
147}
148
149BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
150  return BFI ? BFI->getBlockFreq(BB) : 0;
151}
152
153/// Pop up a ghostview window with the current block frequency propagation
154/// rendered using dot.
155void BlockFrequencyInfo::view() const {
156// This code is only for debugging.
157#ifndef NDEBUG
158  ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
159#else
160  errs() << "BlockFrequencyInfo::view is only available in debug builds on "
161            "systems with Graphviz or gv!\n";
162#endif // NDEBUG
163}
164
165const Function *BlockFrequencyInfo::getFunction() const {
166  return BFI ? BFI->getFunction() : nullptr;
167}
168
169raw_ostream &BlockFrequencyInfo::
170printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
171  return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
172}
173
174raw_ostream &
175BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
176                                   const BasicBlock *BB) const {
177  return BFI ? BFI->printBlockFreq(OS, BB) : OS;
178}
179
180uint64_t BlockFrequencyInfo::getEntryFreq() const {
181  return BFI ? BFI->getEntryFreq() : 0;
182}
183