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