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 #ifndef NDEBUG
32 enum GVDAGType { GVDT_None, GVDT_Fraction, GVDT_Integer, GVDT_Count };
33 
34 static cl::opt<GVDAGType> ViewMachineBlockFreqPropagationDAG(
35     "view-machine-block-freq-propagation-dags", cl::Hidden,
36     cl::desc("Pop up a window to show a dag displaying how machine block "
37              "frequencies propagate through the CFG."),
38     cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
39                clEnumValN(GVDT_Fraction, "fraction",
40                           "display a graph using the "
41                           "fractional block frequency representation."),
42                clEnumValN(GVDT_Integer, "integer",
43                           "display a graph using the raw "
44                           "integer fractional block frequency representation."),
45                clEnumValN(GVDT_Count, "count", "display a graph using the real "
46                                                "profile count if available."),
47 
48                clEnumValEnd));
49 
50 static cl::opt<std::string> ViewMachineBlockFreqFuncName("view-mbfi-func-name",
51                                                          cl::Hidden);
52 
53 namespace llvm {
54 
55 template <> struct GraphTraits<MachineBlockFrequencyInfo *> {
56   typedef const MachineBasicBlock NodeType;
57   typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
58   typedef MachineFunction::const_iterator nodes_iterator;
59 
60   static inline const NodeType *
61   getEntryNode(const MachineBlockFrequencyInfo *G) {
62     return &G->getFunction()->front();
63   }
64 
65   static ChildIteratorType child_begin(const NodeType *N) {
66     return N->succ_begin();
67   }
68 
69   static ChildIteratorType child_end(const NodeType *N) {
70     return N->succ_end();
71   }
72 
73   static nodes_iterator nodes_begin(const MachineBlockFrequencyInfo *G) {
74     return G->getFunction()->begin();
75   }
76 
77   static nodes_iterator nodes_end(const MachineBlockFrequencyInfo *G) {
78     return G->getFunction()->end();
79   }
80 };
81 
82 template <>
83 struct DOTGraphTraits<MachineBlockFrequencyInfo *>
84     : public DefaultDOTGraphTraits {
85   explicit DOTGraphTraits(bool isSimple = false)
86       : DefaultDOTGraphTraits(isSimple) {}
87 
88   typedef MachineBasicBlock::const_succ_iterator EdgeIter;
89   static std::string getGraphName(const MachineBlockFrequencyInfo *G) {
90     return G->getFunction()->getName();
91   }
92 
93   std::string getNodeLabel(const MachineBasicBlock *Node,
94                            const MachineBlockFrequencyInfo *Graph) {
95     std::string Result;
96     raw_string_ostream OS(Result);
97 
98     OS << Node->getName().str() << " : ";
99     switch (ViewMachineBlockFreqPropagationDAG) {
100     case GVDT_Fraction:
101       Graph->printBlockFreq(OS, Node);
102       break;
103     case GVDT_Integer:
104       OS << Graph->getBlockFreq(Node).getFrequency();
105       break;
106     case GVDT_Count: {
107       auto Count = Graph->getBlockProfileCount(Node);
108       if (Count)
109         OS << Count.getValue();
110       else
111         OS << "Unknown";
112       break;
113     }
114     case GVDT_None:
115       llvm_unreachable("If we are not supposed to render a graph we should "
116                        "never reach this point.");
117     }
118     return Result;
119   }
120   static std::string getEdgeAttributes(const MachineBasicBlock *Node,
121                                        EdgeIter EI,
122                                        const MachineBlockFrequencyInfo *MBFI) {
123     MachineBranchProbabilityInfo &MBPI =
124         MBFI->getAnalysis<MachineBranchProbabilityInfo>();
125     BranchProbability BP = MBPI.getEdgeProbability(Node, EI);
126     uint32_t N = BP.getNumerator();
127     uint32_t D = BP.getDenominator();
128     double Percent = 100.0 * N / D;
129     std::string Str;
130     raw_string_ostream OS(Str);
131     OS << format("label=\"%.1f%%\"", Percent);
132     OS.flush();
133     return Str;
134   }
135 };
136 
137 } // end namespace llvm
138 #endif
139 
140 INITIALIZE_PASS_BEGIN(MachineBlockFrequencyInfo, "machine-block-freq",
141                       "Machine Block Frequency Analysis", true, true)
142 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
143 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
144 INITIALIZE_PASS_END(MachineBlockFrequencyInfo, "machine-block-freq",
145                     "Machine Block Frequency Analysis", true, true)
146 
147 char MachineBlockFrequencyInfo::ID = 0;
148 
149 MachineBlockFrequencyInfo::MachineBlockFrequencyInfo()
150     : MachineFunctionPass(ID) {
151   initializeMachineBlockFrequencyInfoPass(*PassRegistry::getPassRegistry());
152 }
153 
154 MachineBlockFrequencyInfo::~MachineBlockFrequencyInfo() {}
155 
156 void MachineBlockFrequencyInfo::getAnalysisUsage(AnalysisUsage &AU) const {
157   AU.addRequired<MachineBranchProbabilityInfo>();
158   AU.addRequired<MachineLoopInfo>();
159   AU.setPreservesAll();
160   MachineFunctionPass::getAnalysisUsage(AU);
161 }
162 
163 bool MachineBlockFrequencyInfo::runOnMachineFunction(MachineFunction &F) {
164   MachineBranchProbabilityInfo &MBPI =
165       getAnalysis<MachineBranchProbabilityInfo>();
166   MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
167   if (!MBFI)
168     MBFI.reset(new ImplType);
169   MBFI->calculate(F, MBPI, MLI);
170 #ifndef NDEBUG
171   if (ViewMachineBlockFreqPropagationDAG != GVDT_None &&
172       (ViewMachineBlockFreqFuncName.empty() ||
173        F.getName().equals(ViewMachineBlockFreqFuncName))) {
174     view();
175   }
176 #endif
177   return false;
178 }
179 
180 void MachineBlockFrequencyInfo::releaseMemory() { MBFI.reset(); }
181 
182 /// Pop up a ghostview window with the current block frequency propagation
183 /// rendered using dot.
184 void MachineBlockFrequencyInfo::view() const {
185 // This code is only for debugging.
186 #ifndef NDEBUG
187   ViewGraph(const_cast<MachineBlockFrequencyInfo *>(this),
188             "MachineBlockFrequencyDAGs");
189 #else
190   errs() << "MachineBlockFrequencyInfo::view is only available in debug builds "
191             "on systems with Graphviz or gv!\n";
192 #endif // NDEBUG
193 }
194 
195 BlockFrequency
196 MachineBlockFrequencyInfo::getBlockFreq(const MachineBasicBlock *MBB) const {
197   return MBFI ? MBFI->getBlockFreq(MBB) : 0;
198 }
199 
200 Optional<uint64_t> MachineBlockFrequencyInfo::getBlockProfileCount(
201     const MachineBasicBlock *MBB) const {
202   const Function *F = MBFI->getFunction()->getFunction();
203   return MBFI ? MBFI->getBlockProfileCount(*F, MBB) : None;
204 }
205 
206 const MachineFunction *MachineBlockFrequencyInfo::getFunction() const {
207   return MBFI ? MBFI->getFunction() : nullptr;
208 }
209 
210 raw_ostream &
211 MachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
212                                           const BlockFrequency Freq) const {
213   return MBFI ? MBFI->printBlockFreq(OS, Freq) : OS;
214 }
215 
216 raw_ostream &
217 MachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
218                                           const MachineBasicBlock *MBB) const {
219   return MBFI ? MBFI->printBlockFreq(OS, MBB) : OS;
220 }
221 
222 uint64_t MachineBlockFrequencyInfo::getEntryFreq() const {
223   return MBFI ? MBFI->getEntryFreq() : 0;
224 }
225