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 static cl::opt<GVDAGType> ViewBlockFreqPropagationDAG(
30     "view-block-freq-propagation-dags", cl::Hidden,
31     cl::desc("Pop up a window to show a dag displaying how block "
32              "frequencies propagation through the CFG."),
33     cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
34                clEnumValN(GVDT_Fraction, "fraction",
35                           "display a graph using the "
36                           "fractional block frequency representation."),
37                clEnumValN(GVDT_Integer, "integer",
38                           "display a graph using the raw "
39                           "integer fractional block frequency representation."),
40                clEnumValN(GVDT_Count, "count", "display a graph using the real "
41                                                "profile count if available.")));
42 
43 cl::opt<std::string>
44     ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,
45                           cl::desc("The option to specify "
46                                    "the name of the function "
47                                    "whose CFG will be displayed."));
48 
49 cl::opt<unsigned>
50     ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
51                        cl::desc("An integer in percent used to specify "
52                                 "the hot blocks/edges to be displayed "
53                                 "in red: a block or edge whose frequency "
54                                 "is no less than the max frequency of the "
55                                 "function multiplied by this percent."));
56 
57 // Command line option to turn on CFG dot dump after profile annotation.
58 cl::opt<bool>
59     PGOViewCounts("pgo-view-counts", cl::init(false), cl::Hidden,
60                   cl::desc("A boolean option to show CFG dag with "
61                            "block profile counts and branch probabilities "
62                            "right after PGO profile annotation step. The "
63                            "profile counts are computed using branch "
64                            "probabilities from the runtime profile data and "
65                            "block frequency propagation algorithm. To view "
66                            "the raw counts from the profile, use option "
67                            "-pgo-view-raw-counts instead. To limit graph "
68                            "display to only one function, use filtering option "
69                            "-view-bfi-func-name."));
70 
71 namespace llvm {
72 
73 static GVDAGType getGVDT() {
74 
75   if (PGOViewCounts)
76     return GVDT_Count;
77   return ViewBlockFreqPropagationDAG;
78 }
79 
80 template <>
81 struct GraphTraits<BlockFrequencyInfo *> {
82   typedef const BasicBlock *NodeRef;
83   typedef succ_const_iterator ChildIteratorType;
84   typedef pointer_iterator<Function::const_iterator> nodes_iterator;
85 
86   static NodeRef getEntryNode(const BlockFrequencyInfo *G) {
87     return &G->getFunction()->front();
88   }
89   static ChildIteratorType child_begin(const NodeRef N) {
90     return succ_begin(N);
91   }
92   static ChildIteratorType child_end(const NodeRef N) { return succ_end(N); }
93   static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
94     return nodes_iterator(G->getFunction()->begin());
95   }
96   static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
97     return nodes_iterator(G->getFunction()->end());
98   }
99 };
100 
101 typedef BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>
102     BFIDOTGTraitsBase;
103 
104 template <>
105 struct DOTGraphTraits<BlockFrequencyInfo *> : public BFIDOTGTraitsBase {
106   explicit DOTGraphTraits(bool isSimple = false)
107       : BFIDOTGTraitsBase(isSimple) {}
108 
109   std::string getNodeLabel(const BasicBlock *Node,
110                            const BlockFrequencyInfo *Graph) {
111 
112     return BFIDOTGTraitsBase::getNodeLabel(Node, Graph, getGVDT());
113   }
114 
115   std::string getNodeAttributes(const BasicBlock *Node,
116                                 const BlockFrequencyInfo *Graph) {
117     return BFIDOTGTraitsBase::getNodeAttributes(Node, Graph,
118                                                 ViewHotFreqPercent);
119   }
120 
121   std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
122                                 const BlockFrequencyInfo *BFI) {
123     return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),
124                                                 ViewHotFreqPercent);
125   }
126 };
127 
128 } // end namespace llvm
129 
130 BlockFrequencyInfo::BlockFrequencyInfo() {}
131 
132 BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
133                                        const BranchProbabilityInfo &BPI,
134                                        const LoopInfo &LI) {
135   calculate(F, BPI, LI);
136 }
137 
138 BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
139     : BFI(std::move(Arg.BFI)) {}
140 
141 BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
142   releaseMemory();
143   BFI = std::move(RHS.BFI);
144   return *this;
145 }
146 
147 // Explicitly define the default constructor otherwise it would be implicitly
148 // defined at the first ODR-use which is the BFI member in the
149 // LazyBlockFrequencyInfo header.  The dtor needs the BlockFrequencyInfoImpl
150 // template instantiated which is not available in the header.
151 BlockFrequencyInfo::~BlockFrequencyInfo() {}
152 
153 bool BlockFrequencyInfo::invalidate(Function &F, const PreservedAnalyses &PA,
154                                     FunctionAnalysisManager::Invalidator &) {
155   // Check whether the analysis, all analyses on functions, or the function's
156   // CFG have been preserved.
157   auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
158   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
159            PAC.preservedSet<CFGAnalyses>());
160 }
161 
162 void BlockFrequencyInfo::calculate(const Function &F,
163                                    const BranchProbabilityInfo &BPI,
164                                    const LoopInfo &LI) {
165   if (!BFI)
166     BFI.reset(new ImplType);
167   BFI->calculate(F, BPI, LI);
168   if (ViewBlockFreqPropagationDAG != GVDT_None &&
169       (ViewBlockFreqFuncName.empty() ||
170        F.getName().equals(ViewBlockFreqFuncName))) {
171     view();
172   }
173 }
174 
175 BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
176   return BFI ? BFI->getBlockFreq(BB) : 0;
177 }
178 
179 Optional<uint64_t>
180 BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
181   if (!BFI)
182     return None;
183 
184   return BFI->getBlockProfileCount(*getFunction(), BB);
185 }
186 
187 Optional<uint64_t>
188 BlockFrequencyInfo::getProfileCountFromFreq(uint64_t Freq) const {
189   if (!BFI)
190     return None;
191   return BFI->getProfileCountFromFreq(*getFunction(), Freq);
192 }
193 
194 void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
195   assert(BFI && "Expected analysis to be available");
196   BFI->setBlockFreq(BB, Freq);
197 }
198 
199 void BlockFrequencyInfo::setBlockFreqAndScale(
200     const BasicBlock *ReferenceBB, uint64_t Freq,
201     SmallPtrSetImpl<BasicBlock *> &BlocksToScale) {
202   assert(BFI && "Expected analysis to be available");
203   // Use 128 bits APInt to avoid overflow.
204   APInt NewFreq(128, Freq);
205   APInt OldFreq(128, BFI->getBlockFreq(ReferenceBB).getFrequency());
206   APInt BBFreq(128, 0);
207   for (auto *BB : BlocksToScale) {
208     BBFreq = BFI->getBlockFreq(BB).getFrequency();
209     // Multiply first by NewFreq and then divide by OldFreq
210     // to minimize loss of precision.
211     BBFreq *= NewFreq;
212     // udiv is an expensive operation in the general case. If this ends up being
213     // a hot spot, one of the options proposed in
214     // https://reviews.llvm.org/D28535#650071 could be used to avoid this.
215     BBFreq = BBFreq.udiv(OldFreq);
216     BFI->setBlockFreq(BB, BBFreq.getLimitedValue());
217   }
218   BFI->setBlockFreq(ReferenceBB, Freq);
219 }
220 
221 /// Pop up a ghostview window with the current block frequency propagation
222 /// rendered using dot.
223 void BlockFrequencyInfo::view() const {
224   ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
225 }
226 
227 const Function *BlockFrequencyInfo::getFunction() const {
228   return BFI ? BFI->getFunction() : nullptr;
229 }
230 
231 const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {
232   return BFI ? &BFI->getBPI() : nullptr;
233 }
234 
235 raw_ostream &BlockFrequencyInfo::
236 printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
237   return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
238 }
239 
240 raw_ostream &
241 BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
242                                    const BasicBlock *BB) const {
243   return BFI ? BFI->printBlockFreq(OS, BB) : OS;
244 }
245 
246 uint64_t BlockFrequencyInfo::getEntryFreq() const {
247   return BFI ? BFI->getEntryFreq() : 0;
248 }
249 
250 void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
251 
252 void BlockFrequencyInfo::print(raw_ostream &OS) const {
253   if (BFI)
254     BFI->print(OS);
255 }
256 
257 
258 INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
259                       "Block Frequency Analysis", true, true)
260 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
261 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
262 INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
263                     "Block Frequency Analysis", true, true)
264 
265 char BlockFrequencyInfoWrapperPass::ID = 0;
266 
267 
268 BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
269     : FunctionPass(ID) {
270   initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
271 }
272 
273 BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {}
274 
275 void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
276                                           const Module *) const {
277   BFI.print(OS);
278 }
279 
280 void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
281   AU.addRequired<BranchProbabilityInfoWrapperPass>();
282   AU.addRequired<LoopInfoWrapperPass>();
283   AU.setPreservesAll();
284 }
285 
286 void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
287 
288 bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
289   BranchProbabilityInfo &BPI =
290       getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
291   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
292   BFI.calculate(F, BPI, LI);
293   return false;
294 }
295 
296 AnalysisKey BlockFrequencyAnalysis::Key;
297 BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
298                                                FunctionAnalysisManager &AM) {
299   BlockFrequencyInfo BFI;
300   BFI.calculate(F, AM.getResult<BranchProbabilityAnalysis>(F),
301                 AM.getResult<LoopAnalysis>(F));
302   return BFI;
303 }
304 
305 PreservedAnalyses
306 BlockFrequencyPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
307   OS << "Printing analysis results of BFI for function "
308      << "'" << F.getName() << "':"
309      << "\n";
310   AM.getResult<BlockFrequencyAnalysis>(F).print(OS);
311   return PreservedAnalyses::all();
312 }
313