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/iterator.h" 16 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 17 #include "llvm/CodeGen/MachineBasicBlock.h" 18 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 19 #include "llvm/CodeGen/MachineFunction.h" 20 #include "llvm/CodeGen/MachineLoopInfo.h" 21 #include "llvm/InitializePasses.h" 22 #include "llvm/Pass.h" 23 #include "llvm/Support/CommandLine.h" 24 #include "llvm/Support/GraphWriter.h" 25 #include <optional> 26 #include <string> 27 28 using namespace llvm; 29 30 #define DEBUG_TYPE "machine-block-freq" 31 32 namespace llvm { 33 static cl::opt<GVDAGType> ViewMachineBlockFreqPropagationDAG( 34 "view-machine-block-freq-propagation-dags", cl::Hidden, 35 cl::desc("Pop up a window to show a dag displaying how machine block " 36 "frequencies propagate through the CFG."), 37 cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."), 38 clEnumValN(GVDT_Fraction, "fraction", 39 "display a graph using the " 40 "fractional block frequency representation."), 41 clEnumValN(GVDT_Integer, "integer", 42 "display a graph using the raw " 43 "integer fractional block frequency representation."), 44 clEnumValN(GVDT_Count, "count", "display a graph using the real " 45 "profile count if available."))); 46 47 // Similar option above, but used to control BFI display only after MBP pass 48 cl::opt<GVDAGType> ViewBlockLayoutWithBFI( 49 "view-block-layout-with-bfi", cl::Hidden, 50 cl::desc( 51 "Pop up a window to show a dag displaying MBP layout and associated " 52 "block frequencies of the CFG."), 53 cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."), 54 clEnumValN(GVDT_Fraction, "fraction", 55 "display a graph using the " 56 "fractional block frequency representation."), 57 clEnumValN(GVDT_Integer, "integer", 58 "display a graph using the raw " 59 "integer fractional block frequency representation."), 60 clEnumValN(GVDT_Count, "count", 61 "display a graph using the real " 62 "profile count if available."))); 63 64 // Command line option to specify the name of the function for CFG dump 65 // Defined in Analysis/BlockFrequencyInfo.cpp: -view-bfi-func-name= 66 extern cl::opt<std::string> ViewBlockFreqFuncName; 67 68 // Command line option to specify hot frequency threshold. 69 // Defined in Analysis/BlockFrequencyInfo.cpp: -view-hot-freq-perc= 70 extern cl::opt<unsigned> ViewHotFreqPercent; 71 72 static cl::opt<bool> PrintMachineBlockFreq( 73 "print-machine-bfi", cl::init(false), cl::Hidden, 74 cl::desc("Print the machine block frequency info.")); 75 76 // Command line option to specify the name of the function for block frequency 77 // dump. Defined in Analysis/BlockFrequencyInfo.cpp. 78 extern cl::opt<std::string> PrintBFIFuncName; 79 } // namespace llvm 80 81 static GVDAGType getGVDT() { 82 if (ViewBlockLayoutWithBFI != GVDT_None) 83 return ViewBlockLayoutWithBFI; 84 85 return ViewMachineBlockFreqPropagationDAG; 86 } 87 88 namespace llvm { 89 90 template <> struct GraphTraits<MachineBlockFrequencyInfo *> { 91 using NodeRef = const MachineBasicBlock *; 92 using ChildIteratorType = MachineBasicBlock::const_succ_iterator; 93 using nodes_iterator = pointer_iterator<MachineFunction::const_iterator>; 94 95 static NodeRef getEntryNode(const MachineBlockFrequencyInfo *G) { 96 return &G->getFunction()->front(); 97 } 98 99 static ChildIteratorType child_begin(const NodeRef N) { 100 return N->succ_begin(); 101 } 102 103 static ChildIteratorType child_end(const NodeRef N) { return N->succ_end(); } 104 105 static nodes_iterator nodes_begin(const MachineBlockFrequencyInfo *G) { 106 return nodes_iterator(G->getFunction()->begin()); 107 } 108 109 static nodes_iterator nodes_end(const MachineBlockFrequencyInfo *G) { 110 return nodes_iterator(G->getFunction()->end()); 111 } 112 }; 113 114 using MBFIDOTGraphTraitsBase = 115 BFIDOTGraphTraitsBase<MachineBlockFrequencyInfo, 116 MachineBranchProbabilityInfo>; 117 118 template <> 119 struct DOTGraphTraits<MachineBlockFrequencyInfo *> 120 : public MBFIDOTGraphTraitsBase { 121 const MachineFunction *CurFunc = nullptr; 122 DenseMap<const MachineBasicBlock *, int> LayoutOrderMap; 123 124 explicit DOTGraphTraits(bool isSimple = false) 125 : MBFIDOTGraphTraitsBase(isSimple) {} 126 127 std::string getNodeLabel(const MachineBasicBlock *Node, 128 const MachineBlockFrequencyInfo *Graph) { 129 int layout_order = -1; 130 // Attach additional ordering information if 'isSimple' is false. 131 if (!isSimple()) { 132 const MachineFunction *F = Node->getParent(); 133 if (!CurFunc || F != CurFunc) { 134 if (CurFunc) 135 LayoutOrderMap.clear(); 136 137 CurFunc = F; 138 int O = 0; 139 for (auto MBI = F->begin(); MBI != F->end(); ++MBI, ++O) { 140 LayoutOrderMap[&*MBI] = O; 141 } 142 } 143 layout_order = LayoutOrderMap[Node]; 144 } 145 return MBFIDOTGraphTraitsBase::getNodeLabel(Node, Graph, getGVDT(), 146 layout_order); 147 } 148 149 std::string getNodeAttributes(const MachineBasicBlock *Node, 150 const MachineBlockFrequencyInfo *Graph) { 151 return MBFIDOTGraphTraitsBase::getNodeAttributes(Node, Graph, 152 ViewHotFreqPercent); 153 } 154 155 std::string getEdgeAttributes(const MachineBasicBlock *Node, EdgeIter EI, 156 const MachineBlockFrequencyInfo *MBFI) { 157 return MBFIDOTGraphTraitsBase::getEdgeAttributes( 158 Node, EI, MBFI, MBFI->getMBPI(), ViewHotFreqPercent); 159 } 160 }; 161 162 } // end namespace llvm 163 164 AnalysisKey MachineBlockFrequencyAnalysis::Key; 165 166 MachineBlockFrequencyAnalysis::Result 167 MachineBlockFrequencyAnalysis::run(MachineFunction &MF, 168 MachineFunctionAnalysisManager &MFAM) { 169 auto &MBPI = MFAM.getResult<MachineBranchProbabilityAnalysis>(MF); 170 auto &MLI = MFAM.getResult<MachineLoopAnalysis>(MF); 171 return Result(MF, MBPI, MLI); 172 } 173 174 PreservedAnalyses 175 MachineBlockFrequencyPrinterPass::run(MachineFunction &MF, 176 MachineFunctionAnalysisManager &MFAM) { 177 auto &MBFI = MFAM.getResult<MachineBlockFrequencyAnalysis>(MF); 178 OS << "Machine block frequency for machine function: " << MF.getName() 179 << '\n'; 180 MBFI.print(OS); 181 return PreservedAnalyses::all(); 182 } 183 184 INITIALIZE_PASS_BEGIN(MachineBlockFrequencyInfoWrapperPass, DEBUG_TYPE, 185 "Machine Block Frequency Analysis", true, true) 186 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass) 187 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass) 188 INITIALIZE_PASS_END(MachineBlockFrequencyInfoWrapperPass, DEBUG_TYPE, 189 "Machine Block Frequency Analysis", true, true) 190 191 char MachineBlockFrequencyInfoWrapperPass::ID = 0; 192 193 MachineBlockFrequencyInfoWrapperPass::MachineBlockFrequencyInfoWrapperPass() 194 : MachineFunctionPass(ID) { 195 initializeMachineBlockFrequencyInfoWrapperPassPass( 196 *PassRegistry::getPassRegistry()); 197 } 198 199 MachineBlockFrequencyInfo::MachineBlockFrequencyInfo() = default; 200 201 MachineBlockFrequencyInfo::MachineBlockFrequencyInfo( 202 MachineBlockFrequencyInfo &&) = default; 203 204 MachineBlockFrequencyInfo::MachineBlockFrequencyInfo( 205 MachineFunction &F, MachineBranchProbabilityInfo &MBPI, 206 MachineLoopInfo &MLI) { 207 calculate(F, MBPI, MLI); 208 } 209 210 MachineBlockFrequencyInfo::~MachineBlockFrequencyInfo() = default; 211 212 bool MachineBlockFrequencyInfo::invalidate( 213 MachineFunction &MF, const PreservedAnalyses &PA, 214 MachineFunctionAnalysisManager::Invalidator &) { 215 // Check whether the analysis, all analyses on machine functions, or the 216 // machine function's CFG have been preserved. 217 auto PAC = PA.getChecker<MachineBlockFrequencyAnalysis>(); 218 return !PAC.preserved() && 219 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() && 220 !PAC.preservedSet<CFGAnalyses>(); 221 } 222 223 void MachineBlockFrequencyInfoWrapperPass::getAnalysisUsage( 224 AnalysisUsage &AU) const { 225 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>(); 226 AU.addRequired<MachineLoopInfoWrapperPass>(); 227 AU.setPreservesAll(); 228 MachineFunctionPass::getAnalysisUsage(AU); 229 } 230 231 void MachineBlockFrequencyInfo::calculate( 232 const MachineFunction &F, const MachineBranchProbabilityInfo &MBPI, 233 const MachineLoopInfo &MLI) { 234 if (!MBFI) 235 MBFI.reset(new ImplType); 236 MBFI->calculate(F, MBPI, MLI); 237 if (ViewMachineBlockFreqPropagationDAG != GVDT_None && 238 (ViewBlockFreqFuncName.empty() || F.getName() == ViewBlockFreqFuncName)) { 239 view("MachineBlockFrequencyDAGS." + F.getName()); 240 } 241 if (PrintMachineBlockFreq && 242 (PrintBFIFuncName.empty() || F.getName() == PrintBFIFuncName)) { 243 MBFI->print(dbgs()); 244 } 245 } 246 247 bool MachineBlockFrequencyInfoWrapperPass::runOnMachineFunction( 248 MachineFunction &F) { 249 MachineBranchProbabilityInfo &MBPI = 250 getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI(); 251 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI(); 252 MBFI.calculate(F, MBPI, MLI); 253 return false; 254 } 255 256 void MachineBlockFrequencyInfo::print(raw_ostream &OS) { MBFI->print(OS); } 257 258 void MachineBlockFrequencyInfo::releaseMemory() { MBFI.reset(); } 259 260 /// Pop up a ghostview window with the current block frequency propagation 261 /// rendered using dot. 262 void MachineBlockFrequencyInfo::view(const Twine &Name, bool isSimple) const { 263 // This code is only for debugging. 264 ViewGraph(const_cast<MachineBlockFrequencyInfo *>(this), Name, isSimple); 265 } 266 267 BlockFrequency 268 MachineBlockFrequencyInfo::getBlockFreq(const MachineBasicBlock *MBB) const { 269 return MBFI ? MBFI->getBlockFreq(MBB) : BlockFrequency(0); 270 } 271 272 std::optional<uint64_t> MachineBlockFrequencyInfo::getBlockProfileCount( 273 const MachineBasicBlock *MBB) const { 274 if (!MBFI) 275 return std::nullopt; 276 277 const Function &F = MBFI->getFunction()->getFunction(); 278 return MBFI->getBlockProfileCount(F, MBB); 279 } 280 281 std::optional<uint64_t> 282 MachineBlockFrequencyInfo::getProfileCountFromFreq(BlockFrequency Freq) const { 283 if (!MBFI) 284 return std::nullopt; 285 286 const Function &F = MBFI->getFunction()->getFunction(); 287 return MBFI->getProfileCountFromFreq(F, Freq); 288 } 289 290 bool MachineBlockFrequencyInfo::isIrrLoopHeader( 291 const MachineBasicBlock *MBB) const { 292 assert(MBFI && "Expected analysis to be available"); 293 return MBFI->isIrrLoopHeader(MBB); 294 } 295 296 void MachineBlockFrequencyInfo::onEdgeSplit( 297 const MachineBasicBlock &NewPredecessor, 298 const MachineBasicBlock &NewSuccessor, 299 const MachineBranchProbabilityInfo &MBPI) { 300 assert(MBFI && "Expected analysis to be available"); 301 auto NewSuccFreq = MBFI->getBlockFreq(&NewPredecessor) * 302 MBPI.getEdgeProbability(&NewPredecessor, &NewSuccessor); 303 304 MBFI->setBlockFreq(&NewSuccessor, NewSuccFreq); 305 } 306 307 const MachineFunction *MachineBlockFrequencyInfo::getFunction() const { 308 return MBFI ? MBFI->getFunction() : nullptr; 309 } 310 311 const MachineBranchProbabilityInfo *MachineBlockFrequencyInfo::getMBPI() const { 312 return MBFI ? &MBFI->getBPI() : nullptr; 313 } 314 315 BlockFrequency MachineBlockFrequencyInfo::getEntryFreq() const { 316 return MBFI ? MBFI->getEntryFreq() : BlockFrequency(0); 317 } 318 319 Printable llvm::printBlockFreq(const MachineBlockFrequencyInfo &MBFI, 320 BlockFrequency Freq) { 321 return Printable([&MBFI, Freq](raw_ostream &OS) { 322 printRelativeBlockFreq(OS, MBFI.getEntryFreq(), Freq); 323 }); 324 } 325 326 Printable llvm::printBlockFreq(const MachineBlockFrequencyInfo &MBFI, 327 const MachineBasicBlock &MBB) { 328 return printBlockFreq(MBFI, MBFI.getBlockFreq(&MBB)); 329 } 330