lib/CodeGen/MachineBlockFrequencyInfo.cpp

   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() = default;
 176
 177 void MachineBlockFrequencyInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 178   AU.addRequired<MachineBranchProbabilityInfo>();
 179   AU.addRequired<MachineLoopInfo>();
 180   AU.setPreservesAll();
 181   MachineFunctionPass::getAnalysisUsage(AU);
 182 }
 183
 184 void MachineBlockFrequencyInfo::calculate(
 185     const MachineFunction &F, const MachineBranchProbabilityInfo &MBPI,
 186     const MachineLoopInfo &MLI) {
 187   if (!MBFI)
 188     MBFI.reset(new ImplType);
 189   MBFI->calculate(F, MBPI, MLI);
 190   if (ViewMachineBlockFreqPropagationDAG != GVDT_None &&
 191       (ViewBlockFreqFuncName.empty() ||
 192        F.getName().equals(ViewBlockFreqFuncName))) {
 193     view("MachineBlockFrequencyDAGS." + F.getName());
 194   }
 195   if (PrintMachineBlockFreq &&
 196       (PrintBlockFreqFuncName.empty() ||
 197        F.getName().equals(PrintBlockFreqFuncName))) {
 198     MBFI->print(dbgs());
 199   }
 200 }
 201
 202 bool MachineBlockFrequencyInfo::runOnMachineFunction(MachineFunction &F) {
 203   MachineBranchProbabilityInfo &MBPI =
 204       getAnalysis<MachineBranchProbabilityInfo>();
 205   MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
 206   calculate(F, MBPI, MLI);
 207   return false;
 208 }
 209
 210 void MachineBlockFrequencyInfo::releaseMemory() { MBFI.reset(); }
 211
 212 /// Pop up a ghostview window with the current block frequency propagation
 213 /// rendered using dot.
 214 void MachineBlockFrequencyInfo::view(const Twine &Name, bool isSimple) const {
 215   // This code is only for debugging.
 216   ViewGraph(const_cast<MachineBlockFrequencyInfo *>(this), Name, isSimple);
 217 }
 218
 219 BlockFrequency
 220 MachineBlockFrequencyInfo::getBlockFreq(const MachineBasicBlock *MBB) const {
 221   return MBFI ? MBFI->getBlockFreq(MBB) : 0;
 222 }
 223
 224 Optional<uint64_t> MachineBlockFrequencyInfo::getBlockProfileCount(
 225     const MachineBasicBlock *MBB) const {
 226   const Function &F = MBFI->getFunction()->getFunction();
 227   return MBFI ? MBFI->getBlockProfileCount(F, MBB) : None;
 228 }
 229
 230 Optional<uint64_t>
 231 MachineBlockFrequencyInfo::getProfileCountFromFreq(uint64_t Freq) const {
 232   const Function &F = MBFI->getFunction()->getFunction();
 233   return MBFI ? MBFI->getProfileCountFromFreq(F, Freq) : None;
 234 }
 235
 236 bool
 237 MachineBlockFrequencyInfo::isIrrLoopHeader(const MachineBasicBlock *MBB) {
 238   assert(MBFI && "Expected analysis to be available");
 239   return MBFI->isIrrLoopHeader(MBB);
 240 }
 241
 242 const MachineFunction *MachineBlockFrequencyInfo::getFunction() const {
 243   return MBFI ? MBFI->getFunction() : nullptr;
 244 }
 245
 246 const MachineBranchProbabilityInfo *MachineBlockFrequencyInfo::getMBPI() const {
 247   return MBFI ? &MBFI->getBPI() : nullptr;
 248 }
 249
 250 raw_ostream &
 251 MachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
 252                                           const BlockFrequency Freq) const {
 253   return MBFI ? MBFI->printBlockFreq(OS, Freq) : OS;
 254 }
 255
 256 raw_ostream &
 257 MachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
 258                                           const MachineBasicBlock *MBB) const {
 259   return MBFI ? MBFI->printBlockFreq(OS, MBB) : OS;
 260 }
 261
 262 uint64_t MachineBlockFrequencyInfo::getEntryFreq() const {
 263   return MBFI ? MBFI->getEntryFreq() : 0;
 264 }