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