1 //===- MachineBlockFrequencyInfo.cpp - MBB 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/CodeGen/MachineBlockFrequencyInfo.h"
15 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
16 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
17 #include "llvm/CodeGen/MachineFunction.h"
18 #include "llvm/CodeGen/MachineLoopInfo.h"
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/InitializePasses.h"
21 #include "llvm/Support/CommandLine.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/Format.h"
24 #include "llvm/Support/GraphWriter.h"
25 #include "llvm/Support/raw_ostream.h"
26 
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "block-freq"
30 
31 
32 static cl::opt<GVDAGType> ViewMachineBlockFreqPropagationDAG(
33     "view-machine-block-freq-propagation-dags", cl::Hidden,
34     cl::desc("Pop up a window to show a dag displaying how machine block "
35              "frequencies propagate through the CFG."),
36     cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
37                clEnumValN(GVDT_Fraction, "fraction",
38                           "display a graph using the "
39                           "fractional block frequency representation."),
40                clEnumValN(GVDT_Integer, "integer",
41                           "display a graph using the raw "
42                           "integer fractional block frequency representation."),
43                clEnumValN(GVDT_Count, "count", "display a graph using the real "
44                                                "profile count if available.")));
45 // Similar option above, but used to control BFI display only after MBP pass
46 cl::opt<GVDAGType> ViewBlockLayoutWithBFI(
47     "view-block-layout-with-bfi", cl::Hidden,
48     cl::desc(
49         "Pop up a window to show a dag displaying MBP layout and associated "
50         "block frequencies of the CFG."),
51     cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
52                clEnumValN(GVDT_Fraction, "fraction",
53                           "display a graph using the "
54                           "fractional block frequency representation."),
55                clEnumValN(GVDT_Integer, "integer",
56                           "display a graph using the raw "
57                           "integer fractional block frequency representation."),
58                clEnumValN(GVDT_Count, "count",
59                           "display a graph using the real "
60                           "profile count if available.")));
61 
62 extern cl::opt<std::string> ViewBlockFreqFuncName;
63 extern cl::opt<unsigned> ViewHotFreqPercent;
64 
65 static GVDAGType getGVDT() {
66   if (ViewBlockLayoutWithBFI != GVDT_None)
67     return ViewBlockLayoutWithBFI;
68 
69   return ViewMachineBlockFreqPropagationDAG;
70 }
71 
72 namespace llvm {
73 
74 template <> struct GraphTraits<MachineBlockFrequencyInfo *> {
75   typedef const MachineBasicBlock *NodeRef;
76   typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
77   typedef pointer_iterator<MachineFunction::const_iterator> nodes_iterator;
78 
79   static NodeRef getEntryNode(const MachineBlockFrequencyInfo *G) {
80     return &G->getFunction()->front();
81   }
82 
83   static ChildIteratorType child_begin(const NodeRef N) {
84     return N->succ_begin();
85   }
86 
87   static ChildIteratorType child_end(const NodeRef N) { return N->succ_end(); }
88 
89   static nodes_iterator nodes_begin(const MachineBlockFrequencyInfo *G) {
90     return nodes_iterator(G->getFunction()->begin());
91   }
92 
93   static nodes_iterator nodes_end(const MachineBlockFrequencyInfo *G) {
94     return nodes_iterator(G->getFunction()->end());
95   }
96 };
97 
98 typedef BFIDOTGraphTraitsBase<MachineBlockFrequencyInfo,
99                               MachineBranchProbabilityInfo>
100     MBFIDOTGraphTraitsBase;
101 template <>
102 struct DOTGraphTraits<MachineBlockFrequencyInfo *>
103     : public MBFIDOTGraphTraitsBase {
104   explicit DOTGraphTraits(bool isSimple = false)
105       : MBFIDOTGraphTraitsBase(isSimple), CurFunc(nullptr), LayoutOrderMap() {}
106 
107   const MachineFunction *CurFunc;
108   DenseMap<const MachineBasicBlock *, int> LayoutOrderMap;
109 
110   std::string getNodeLabel(const MachineBasicBlock *Node,
111                            const MachineBlockFrequencyInfo *Graph) {
112 
113     int layout_order = -1;
114     // Attach additional ordering information if 'isSimple' is false.
115     if (!isSimple()) {
116       const MachineFunction *F = Node->getParent();
117       if (!CurFunc || F != CurFunc) {
118         if (CurFunc)
119           LayoutOrderMap.clear();
120 
121         CurFunc = F;
122         int O = 0;
123         for (auto MBI = F->begin(); MBI != F->end(); ++MBI, ++O) {
124           LayoutOrderMap[&*MBI] = O;
125         }
126       }
127       layout_order = LayoutOrderMap[Node];
128     }
129     return MBFIDOTGraphTraitsBase::getNodeLabel(Node, Graph, getGVDT(),
130                                                 layout_order);
131   }
132 
133   std::string getNodeAttributes(const MachineBasicBlock *Node,
134                                 const MachineBlockFrequencyInfo *Graph) {
135     return MBFIDOTGraphTraitsBase::getNodeAttributes(Node, Graph,
136                                                      ViewHotFreqPercent);
137   }
138 
139   std::string getEdgeAttributes(const MachineBasicBlock *Node, EdgeIter EI,
140                                 const MachineBlockFrequencyInfo *MBFI) {
141     return MBFIDOTGraphTraitsBase::getEdgeAttributes(
142         Node, EI, MBFI, MBFI->getMBPI(), ViewHotFreqPercent);
143   }
144 };
145 
146 } // end namespace llvm
147 
148 INITIALIZE_PASS_BEGIN(MachineBlockFrequencyInfo, "machine-block-freq",
149                       "Machine Block Frequency Analysis", true, true)
150 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
151 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
152 INITIALIZE_PASS_END(MachineBlockFrequencyInfo, "machine-block-freq",
153                     "Machine Block Frequency Analysis", true, true)
154 
155 char MachineBlockFrequencyInfo::ID = 0;
156 
157 MachineBlockFrequencyInfo::MachineBlockFrequencyInfo()
158     : MachineFunctionPass(ID) {
159   initializeMachineBlockFrequencyInfoPass(*PassRegistry::getPassRegistry());
160 }
161 
162 MachineBlockFrequencyInfo::~MachineBlockFrequencyInfo() {}
163 
164 void MachineBlockFrequencyInfo::getAnalysisUsage(AnalysisUsage &AU) const {
165   AU.addRequired<MachineBranchProbabilityInfo>();
166   AU.addRequired<MachineLoopInfo>();
167   AU.setPreservesAll();
168   MachineFunctionPass::getAnalysisUsage(AU);
169 }
170 
171 bool MachineBlockFrequencyInfo::runOnMachineFunction(MachineFunction &F) {
172   MachineBranchProbabilityInfo &MBPI =
173       getAnalysis<MachineBranchProbabilityInfo>();
174   MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
175   if (!MBFI)
176     MBFI.reset(new ImplType);
177   MBFI->calculate(F, MBPI, MLI);
178   if (ViewMachineBlockFreqPropagationDAG != GVDT_None &&
179       (ViewBlockFreqFuncName.empty() ||
180        F.getName().equals(ViewBlockFreqFuncName))) {
181     view();
182   }
183   return false;
184 }
185 
186 void MachineBlockFrequencyInfo::releaseMemory() { MBFI.reset(); }
187 
188 /// Pop up a ghostview window with the current block frequency propagation
189 /// rendered using dot.
190 void MachineBlockFrequencyInfo::view(bool isSimple) const {
191 // This code is only for debugging.
192   ViewGraph(const_cast<MachineBlockFrequencyInfo *>(this),
193             "MachineBlockFrequencyDAGs", isSimple);
194 }
195 
196 BlockFrequency
197 MachineBlockFrequencyInfo::getBlockFreq(const MachineBasicBlock *MBB) const {
198   return MBFI ? MBFI->getBlockFreq(MBB) : 0;
199 }
200 
201 Optional<uint64_t> MachineBlockFrequencyInfo::getBlockProfileCount(
202     const MachineBasicBlock *MBB) const {
203   const Function *F = MBFI->getFunction()->getFunction();
204   return MBFI ? MBFI->getBlockProfileCount(*F, MBB) : None;
205 }
206 
207 Optional<uint64_t>
208 MachineBlockFrequencyInfo::getProfileCountFromFreq(uint64_t Freq) const {
209   const Function *F = MBFI->getFunction()->getFunction();
210   return MBFI ? MBFI->getProfileCountFromFreq(*F, Freq) : None;
211 }
212 
213 const MachineFunction *MachineBlockFrequencyInfo::getFunction() const {
214   return MBFI ? MBFI->getFunction() : nullptr;
215 }
216 
217 const MachineBranchProbabilityInfo *MachineBlockFrequencyInfo::getMBPI() const {
218   return MBFI ? &MBFI->getBPI() : nullptr;
219 }
220 
221 raw_ostream &
222 MachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
223                                           const BlockFrequency Freq) const {
224   return MBFI ? MBFI->printBlockFreq(OS, Freq) : OS;
225 }
226 
227 raw_ostream &
228 MachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
229                                           const MachineBasicBlock *MBB) const {
230   return MBFI ? MBFI->printBlockFreq(OS, MBB) : OS;
231 }
232 
233 uint64_t MachineBlockFrequencyInfo::getEntryFreq() const {
234   return MBFI ? MBFI->getEntryFreq() : 0;
235 }
236