1 //===- MachineBlockFrequencyInfo.cpp - MBB Frequency Analysis -------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Loops should be simplified before this analysis. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 14 #include "llvm/ADT/DenseMap.h" 15 #include "llvm/ADT/None.h" 16 #include "llvm/ADT/iterator.h" 17 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 18 #include "llvm/CodeGen/MachineBasicBlock.h" 19 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 20 #include "llvm/CodeGen/MachineFunction.h" 21 #include "llvm/CodeGen/MachineLoopInfo.h" 22 #include "llvm/Pass.h" 23 #include "llvm/Support/CommandLine.h" 24 #include "llvm/Support/GraphWriter.h" 25 #include <string> 26 27 using namespace llvm; 28 29 #define DEBUG_TYPE "machine-block-freq" 30 31 static cl::opt<GVDAGType> ViewMachineBlockFreqPropagationDAG( 32 "view-machine-block-freq-propagation-dags", cl::Hidden, 33 cl::desc("Pop up a window to show a dag displaying how machine block " 34 "frequencies propagate through the CFG."), 35 cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."), 36 clEnumValN(GVDT_Fraction, "fraction", 37 "display a graph using the " 38 "fractional block frequency representation."), 39 clEnumValN(GVDT_Integer, "integer", 40 "display a graph using the raw " 41 "integer fractional block frequency representation."), 42 clEnumValN(GVDT_Count, "count", "display a graph using the real " 43 "profile count if available."))); 44 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 // Command line option to specify the name of the function for CFG dump 63 // Defined in Analysis/BlockFrequencyInfo.cpp: -view-bfi-func-name= 64 extern cl::opt<std::string> ViewBlockFreqFuncName; 65 66 // Command line option to specify hot frequency threshold. 67 // Defined in Analysis/BlockFrequencyInfo.cpp: -view-hot-freq-perc= 68 extern cl::opt<unsigned> ViewHotFreqPercent; 69 70 static cl::opt<bool> PrintMachineBlockFreq( 71 "print-machine-bfi", cl::init(false), cl::Hidden, 72 cl::desc("Print the machine block frequency info.")); 73 74 // Command line option to specify the name of the function for block frequency 75 // dump. Defined in Analysis/BlockFrequencyInfo.cpp. 76 extern cl::opt<std::string> PrintBlockFreqFuncName; 77 78 static GVDAGType getGVDT() { 79 if (ViewBlockLayoutWithBFI != GVDT_None) 80 return ViewBlockLayoutWithBFI; 81 82 return ViewMachineBlockFreqPropagationDAG; 83 } 84 85 namespace llvm { 86 87 template <> struct GraphTraits<MachineBlockFrequencyInfo *> { 88 using NodeRef = const MachineBasicBlock *; 89 using ChildIteratorType = MachineBasicBlock::const_succ_iterator; 90 using nodes_iterator = pointer_iterator<MachineFunction::const_iterator>; 91 92 static NodeRef getEntryNode(const MachineBlockFrequencyInfo *G) { 93 return &G->getFunction()->front(); 94 } 95 96 static ChildIteratorType child_begin(const NodeRef N) { 97 return N->succ_begin(); 98 } 99 100 static ChildIteratorType child_end(const NodeRef N) { return N->succ_end(); } 101 102 static nodes_iterator nodes_begin(const MachineBlockFrequencyInfo *G) { 103 return nodes_iterator(G->getFunction()->begin()); 104 } 105 106 static nodes_iterator nodes_end(const MachineBlockFrequencyInfo *G) { 107 return nodes_iterator(G->getFunction()->end()); 108 } 109 }; 110 111 using MBFIDOTGraphTraitsBase = 112 BFIDOTGraphTraitsBase<MachineBlockFrequencyInfo, 113 MachineBranchProbabilityInfo>; 114 115 template <> 116 struct DOTGraphTraits<MachineBlockFrequencyInfo *> 117 : public MBFIDOTGraphTraitsBase { 118 const MachineFunction *CurFunc = nullptr; 119 DenseMap<const MachineBasicBlock *, int> LayoutOrderMap; 120 121 explicit DOTGraphTraits(bool isSimple = false) 122 : MBFIDOTGraphTraitsBase(isSimple) {} 123 124 std::string getNodeLabel(const MachineBasicBlock *Node, 125 const MachineBlockFrequencyInfo *Graph) { 126 int layout_order = -1; 127 // Attach additional ordering information if 'isSimple' is false. 128 if (!isSimple()) { 129 const MachineFunction *F = Node->getParent(); 130 if (!CurFunc || F != CurFunc) { 131 if (CurFunc) 132 LayoutOrderMap.clear(); 133 134 CurFunc = F; 135 int O = 0; 136 for (auto MBI = F->begin(); MBI != F->end(); ++MBI, ++O) { 137 LayoutOrderMap[&*MBI] = O; 138 } 139 } 140 layout_order = LayoutOrderMap[Node]; 141 } 142 return MBFIDOTGraphTraitsBase::getNodeLabel(Node, Graph, getGVDT(), 143 layout_order); 144 } 145 146 std::string getNodeAttributes(const MachineBasicBlock *Node, 147 const MachineBlockFrequencyInfo *Graph) { 148 return MBFIDOTGraphTraitsBase::getNodeAttributes(Node, Graph, 149 ViewHotFreqPercent); 150 } 151 152 std::string getEdgeAttributes(const MachineBasicBlock *Node, EdgeIter EI, 153 const MachineBlockFrequencyInfo *MBFI) { 154 return MBFIDOTGraphTraitsBase::getEdgeAttributes( 155 Node, EI, MBFI, MBFI->getMBPI(), ViewHotFreqPercent); 156 } 157 }; 158 159 } // end namespace llvm 160 161 INITIALIZE_PASS_BEGIN(MachineBlockFrequencyInfo, DEBUG_TYPE, 162 "Machine Block Frequency Analysis", true, true) 163 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 164 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 165 INITIALIZE_PASS_END(MachineBlockFrequencyInfo, DEBUG_TYPE, 166 "Machine Block Frequency Analysis", true, true) 167 168 char MachineBlockFrequencyInfo::ID = 0; 169 170 MachineBlockFrequencyInfo::MachineBlockFrequencyInfo() 171 : MachineFunctionPass(ID) { 172 initializeMachineBlockFrequencyInfoPass(*PassRegistry::getPassRegistry()); 173 } 174 175 MachineBlockFrequencyInfo::MachineBlockFrequencyInfo( 176 MachineFunction &F, 177 MachineBranchProbabilityInfo &MBPI, 178 MachineLoopInfo &MLI) : MachineFunctionPass(ID) { 179 calculate(F, MBPI, MLI); 180 } 181 182 MachineBlockFrequencyInfo::~MachineBlockFrequencyInfo() = default; 183 184 void MachineBlockFrequencyInfo::getAnalysisUsage(AnalysisUsage &AU) const { 185 AU.addRequired<MachineBranchProbabilityInfo>(); 186 AU.addRequired<MachineLoopInfo>(); 187 AU.setPreservesAll(); 188 MachineFunctionPass::getAnalysisUsage(AU); 189 } 190 191 void MachineBlockFrequencyInfo::calculate( 192 const MachineFunction &F, const MachineBranchProbabilityInfo &MBPI, 193 const MachineLoopInfo &MLI) { 194 if (!MBFI) 195 MBFI.reset(new ImplType); 196 MBFI->calculate(F, MBPI, MLI); 197 if (ViewMachineBlockFreqPropagationDAG != GVDT_None && 198 (ViewBlockFreqFuncName.empty() || 199 F.getName().equals(ViewBlockFreqFuncName))) { 200 view("MachineBlockFrequencyDAGS." + F.getName()); 201 } 202 if (PrintMachineBlockFreq && 203 (PrintBlockFreqFuncName.empty() || 204 F.getName().equals(PrintBlockFreqFuncName))) { 205 MBFI->print(dbgs()); 206 } 207 } 208 209 bool MachineBlockFrequencyInfo::runOnMachineFunction(MachineFunction &F) { 210 MachineBranchProbabilityInfo &MBPI = 211 getAnalysis<MachineBranchProbabilityInfo>(); 212 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 213 calculate(F, MBPI, MLI); 214 return false; 215 } 216 217 void MachineBlockFrequencyInfo::releaseMemory() { MBFI.reset(); } 218 219 /// Pop up a ghostview window with the current block frequency propagation 220 /// rendered using dot. 221 void MachineBlockFrequencyInfo::view(const Twine &Name, bool isSimple) const { 222 // This code is only for debugging. 223 ViewGraph(const_cast<MachineBlockFrequencyInfo *>(this), Name, isSimple); 224 } 225 226 BlockFrequency 227 MachineBlockFrequencyInfo::getBlockFreq(const MachineBasicBlock *MBB) const { 228 return MBFI ? MBFI->getBlockFreq(MBB) : 0; 229 } 230 231 Optional<uint64_t> MachineBlockFrequencyInfo::getBlockProfileCount( 232 const MachineBasicBlock *MBB) const { 233 const Function &F = MBFI->getFunction()->getFunction(); 234 return MBFI ? MBFI->getBlockProfileCount(F, MBB) : None; 235 } 236 237 Optional<uint64_t> 238 MachineBlockFrequencyInfo::getProfileCountFromFreq(uint64_t Freq) const { 239 const Function &F = MBFI->getFunction()->getFunction(); 240 return MBFI ? MBFI->getProfileCountFromFreq(F, Freq) : None; 241 } 242 243 bool 244 MachineBlockFrequencyInfo::isIrrLoopHeader(const MachineBasicBlock *MBB) { 245 assert(MBFI && "Expected analysis to be available"); 246 return MBFI->isIrrLoopHeader(MBB); 247 } 248 249 const MachineFunction *MachineBlockFrequencyInfo::getFunction() const { 250 return MBFI ? MBFI->getFunction() : nullptr; 251 } 252 253 const MachineBranchProbabilityInfo *MachineBlockFrequencyInfo::getMBPI() const { 254 return MBFI ? &MBFI->getBPI() : nullptr; 255 } 256 257 raw_ostream & 258 MachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS, 259 const BlockFrequency Freq) const { 260 return MBFI ? MBFI->printBlockFreq(OS, Freq) : OS; 261 } 262 263 raw_ostream & 264 MachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS, 265 const MachineBasicBlock *MBB) const { 266 return MBFI ? MBFI->printBlockFreq(OS, MBB) : OS; 267 } 268 269 uint64_t MachineBlockFrequencyInfo::getEntryFreq() const { 270 return MBFI ? MBFI->getEntryFreq() : 0; 271 } 272