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 
25 using namespace llvm;
26 
27 #define DEBUG_TYPE "block-freq"
28 
29 #ifndef NDEBUG
30 static cl::opt<GVDAGType> ViewBlockFreqPropagationDAG(
31     "view-block-freq-propagation-dags", cl::Hidden,
32     cl::desc("Pop up a window to show a dag displaying how block "
33              "frequencies propagation through the CFG."),
34     cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
35                clEnumValN(GVDT_Fraction, "fraction",
36                           "display a graph using the "
37                           "fractional block frequency representation."),
38                clEnumValN(GVDT_Integer, "integer",
39                           "display a graph using the raw "
40                           "integer fractional block frequency representation."),
41                clEnumValN(GVDT_Count, "count", "display a graph using the real "
42                                                "profile count if available."),
43                clEnumValEnd));
44 
45 cl::opt<std::string>
46     ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,
47                           cl::desc("The option to specify "
48                                    "the name of the function "
49                                    "whose CFG will be displayed."));
50 
51 cl::opt<unsigned>
52     ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
53                        cl::desc("An integer in percent used to specify "
54                                 "the hot blocks/edges to be displayed "
55                                 "in red: a block or edge whose frequency "
56                                 "is no less than the max frequency of the "
57                                 "function multiplied by this percent."));
58 
59 namespace llvm {
60 
61 template <>
62 struct GraphTraits<BlockFrequencyInfo *> {
63   typedef const BasicBlock NodeType;
64   typedef const BasicBlock *NodeRef;
65   typedef succ_const_iterator ChildIteratorType;
66   typedef Function::const_iterator nodes_iterator;
67 
68   static inline const NodeType *getEntryNode(const BlockFrequencyInfo *G) {
69     return &G->getFunction()->front();
70   }
71   static ChildIteratorType child_begin(const NodeType *N) {
72     return succ_begin(N);
73   }
74   static ChildIteratorType child_end(const NodeType *N) {
75     return succ_end(N);
76   }
77   static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
78     return G->getFunction()->begin();
79   }
80   static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
81     return G->getFunction()->end();
82   }
83 };
84 
85 typedef BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>
86     BFIDOTGTraitsBase;
87 
88 template <>
89 struct DOTGraphTraits<BlockFrequencyInfo *> : public BFIDOTGTraitsBase {
90   explicit DOTGraphTraits(bool isSimple = false)
91       : BFIDOTGTraitsBase(isSimple) {}
92 
93   std::string getNodeLabel(const BasicBlock *Node,
94                            const BlockFrequencyInfo *Graph) {
95 
96     return BFIDOTGTraitsBase::getNodeLabel(Node, Graph,
97                                            ViewBlockFreqPropagationDAG);
98   }
99 
100   std::string getNodeAttributes(const BasicBlock *Node,
101                                 const BlockFrequencyInfo *Graph) {
102     return BFIDOTGTraitsBase::getNodeAttributes(Node, Graph,
103                                                 ViewHotFreqPercent);
104   }
105 
106   std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
107                                 const BlockFrequencyInfo *BFI) {
108     return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),
109                                                 ViewHotFreqPercent);
110   }
111 };
112 
113 } // end namespace llvm
114 #endif
115 
116 BlockFrequencyInfo::BlockFrequencyInfo() {}
117 
118 BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
119                                        const BranchProbabilityInfo &BPI,
120                                        const LoopInfo &LI) {
121   calculate(F, BPI, LI);
122 }
123 
124 BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
125     : BFI(std::move(Arg.BFI)) {}
126 
127 BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
128   releaseMemory();
129   BFI = std::move(RHS.BFI);
130   return *this;
131 }
132 
133 // Explicitly define the default constructor otherwise it would be implicitly
134 // defined at the first ODR-use which is the BFI member in the
135 // LazyBlockFrequencyInfo header.  The dtor needs the BlockFrequencyInfoImpl
136 // template instantiated which is not available in the header.
137 BlockFrequencyInfo::~BlockFrequencyInfo() {}
138 
139 void BlockFrequencyInfo::calculate(const Function &F,
140                                    const BranchProbabilityInfo &BPI,
141                                    const LoopInfo &LI) {
142   if (!BFI)
143     BFI.reset(new ImplType);
144   BFI->calculate(F, BPI, LI);
145 #ifndef NDEBUG
146   if (ViewBlockFreqPropagationDAG != GVDT_None &&
147       (ViewBlockFreqFuncName.empty() ||
148        F.getName().equals(ViewBlockFreqFuncName))) {
149     view();
150   }
151 #endif
152 }
153 
154 BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
155   return BFI ? BFI->getBlockFreq(BB) : 0;
156 }
157 
158 Optional<uint64_t>
159 BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
160   if (!BFI)
161     return None;
162 
163   return BFI->getBlockProfileCount(*getFunction(), BB);
164 }
165 
166 Optional<uint64_t>
167 BlockFrequencyInfo::getProfileCountFromFreq(uint64_t Freq) const {
168   if (!BFI)
169     return None;
170   return BFI->getProfileCountFromFreq(*getFunction(), Freq);
171 }
172 
173 void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
174   assert(BFI && "Expected analysis to be available");
175   BFI->setBlockFreq(BB, Freq);
176 }
177 
178 /// Pop up a ghostview window with the current block frequency propagation
179 /// rendered using dot.
180 void BlockFrequencyInfo::view() const {
181 // This code is only for debugging.
182 #ifndef NDEBUG
183   ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
184 #else
185   errs() << "BlockFrequencyInfo::view is only available in debug builds on "
186             "systems with Graphviz or gv!\n";
187 #endif // NDEBUG
188 }
189 
190 const Function *BlockFrequencyInfo::getFunction() const {
191   return BFI ? BFI->getFunction() : nullptr;
192 }
193 
194 const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {
195   return BFI ? &BFI->getBPI() : nullptr;
196 }
197 
198 raw_ostream &BlockFrequencyInfo::
199 printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
200   return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
201 }
202 
203 raw_ostream &
204 BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
205                                    const BasicBlock *BB) const {
206   return BFI ? BFI->printBlockFreq(OS, BB) : OS;
207 }
208 
209 uint64_t BlockFrequencyInfo::getEntryFreq() const {
210   return BFI ? BFI->getEntryFreq() : 0;
211 }
212 
213 void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
214 
215 void BlockFrequencyInfo::print(raw_ostream &OS) const {
216   if (BFI)
217     BFI->print(OS);
218 }
219 
220 
221 INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
222                       "Block Frequency Analysis", true, true)
223 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
224 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
225 INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
226                     "Block Frequency Analysis", true, true)
227 
228 char BlockFrequencyInfoWrapperPass::ID = 0;
229 
230 
231 BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
232     : FunctionPass(ID) {
233   initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
234 }
235 
236 BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {}
237 
238 void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
239                                           const Module *) const {
240   BFI.print(OS);
241 }
242 
243 void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
244   AU.addRequired<BranchProbabilityInfoWrapperPass>();
245   AU.addRequired<LoopInfoWrapperPass>();
246   AU.setPreservesAll();
247 }
248 
249 void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
250 
251 bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
252   BranchProbabilityInfo &BPI =
253       getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
254   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
255   BFI.calculate(F, BPI, LI);
256   return false;
257 }
258 
259 char BlockFrequencyAnalysis::PassID;
260 BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
261                                                FunctionAnalysisManager &AM) {
262   BlockFrequencyInfo BFI;
263   BFI.calculate(F, AM.getResult<BranchProbabilityAnalysis>(F),
264                 AM.getResult<LoopAnalysis>(F));
265   return BFI;
266 }
267 
268 PreservedAnalyses
269 BlockFrequencyPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
270   OS << "Printing analysis results of BFI for function "
271      << "'" << F.getName() << "':"
272      << "\n";
273   AM.getResult<BlockFrequencyAnalysis>(F).print(OS);
274   return PreservedAnalyses::all();
275 }
276