lib/Analysis/BlockFrequencyInfo.cpp

   1 //===- BlockFrequencyInfo.cpp - Block 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/Analysis/BlockFrequencyInfo.h"
  15 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
  16 #include "llvm/Analysis/BranchProbabilityInfo.h"
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/Analysis/Passes.h"
  19 #include "llvm/IR/CFG.h"
  20 #include "llvm/InitializePasses.h"
  21 #include "llvm/Support/CommandLine.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/GraphWriter.h"
  24
  25 using namespace llvm;
  26
  27 #ifndef NDEBUG
  28 enum GVDAGType {
  29   GVDT_None,
  30   GVDT_Fraction,
  31   GVDT_Integer
  32 };
  33
  34 static cl::opt<GVDAGType>
  35 ViewBlockFreqPropagationDAG("view-block-freq-propagation-dags", cl::Hidden,
  36           cl::desc("Pop up a window to show a dag displaying how block "
  37                    "frequencies propagation through the CFG."),
  38           cl::values(
  39             clEnumValN(GVDT_None, "none",
  40                        "do not display graphs."),
  41             clEnumValN(GVDT_Fraction, "fraction", "display a graph using the "
  42                        "fractional block frequency representation."),
  43             clEnumValN(GVDT_Integer, "integer", "display a graph using the raw "
  44                        "integer fractional block frequency representation."),
  45             clEnumValEnd));
  46
  47 namespace llvm {
  48
  49 template <>
  50 struct GraphTraits<BlockFrequencyInfo *> {
  51   typedef const BasicBlock NodeType;
  52   typedef succ_const_iterator ChildIteratorType;
  53   typedef Function::const_iterator nodes_iterator;
  54
  55   static inline const NodeType *getEntryNode(const BlockFrequencyInfo *G) {
  56     return G->getFunction()->begin();
  57   }
  58   static ChildIteratorType child_begin(const NodeType *N) {
  59     return succ_begin(N);
  60   }
  61   static ChildIteratorType child_end(const NodeType *N) {
  62     return succ_end(N);
  63   }
  64   static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
  65     return G->getFunction()->begin();
  66   }
  67   static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
  68     return G->getFunction()->end();
  69   }
  70 };
  71
  72 template<>
  73 struct DOTGraphTraits<BlockFrequencyInfo*> : public DefaultDOTGraphTraits {
  74   explicit DOTGraphTraits(bool isSimple=false) :
  75     DefaultDOTGraphTraits(isSimple) {}
  76
  77   static std::string getGraphName(const BlockFrequencyInfo *G) {
  78     return G->getFunction()->getName();
  79   }
  80
  81   std::string getNodeLabel(const BasicBlock *Node,
  82                            const BlockFrequencyInfo *Graph) {
  83     std::string Result;
  84     raw_string_ostream OS(Result);
  85
  86     OS << Node->getName().str() << ":";
  87     switch (ViewBlockFreqPropagationDAG) {
  88     case GVDT_Fraction:
  89       Graph->printBlockFreq(OS, Node);
  90       break;
  91     case GVDT_Integer:
  92       OS << Graph->getBlockFreq(Node).getFrequency();
  93       break;
  94     case GVDT_None:
  95       llvm_unreachable("If we are not supposed to render a graph we should "
  96                        "never reach this point.");
  97     }
  98
  99     return Result;
 100   }
 101 };
 102
 103 } // end namespace llvm
 104 #endif
 105
 106 INITIALIZE_PASS_BEGIN(BlockFrequencyInfo, "block-freq",
 107                       "Block Frequency Analysis", true, true)
 108 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfo)
 109 INITIALIZE_PASS_END(BlockFrequencyInfo, "block-freq",
 110                     "Block Frequency Analysis", true, true)
 111
 112 char BlockFrequencyInfo::ID = 0;
 113
 114
 115 BlockFrequencyInfo::BlockFrequencyInfo() : FunctionPass(ID) {
 116   initializeBlockFrequencyInfoPass(*PassRegistry::getPassRegistry());
 117 }
 118
 119 BlockFrequencyInfo::~BlockFrequencyInfo() {}
 120
 121 void BlockFrequencyInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 122   AU.addRequired<BranchProbabilityInfo>();
 123   AU.setPreservesAll();
 124 }
 125
 126 bool BlockFrequencyInfo::runOnFunction(Function &F) {
 127   BranchProbabilityInfo &BPI = getAnalysis<BranchProbabilityInfo>();
 128   if (!BFI)
 129     BFI.reset(new ImplType);
 130   BFI->doFunction(&F, &BPI);
 131 #ifndef NDEBUG
 132   if (ViewBlockFreqPropagationDAG != GVDT_None)
 133     view();
 134 #endif
 135   return false;
 136 }
 137
 138 void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
 139
 140 void BlockFrequencyInfo::print(raw_ostream &O, const Module *) const {
 141   if (BFI) BFI->print(O);
 142 }
 143
 144 BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
 145   return BFI ? BFI->getBlockFreq(BB) : 0;
 146 }
 147
 148 /// Pop up a ghostview window with the current block frequency propagation
 149 /// rendered using dot.
 150 void BlockFrequencyInfo::view() const {
 151 // This code is only for debugging.
 152 #ifndef NDEBUG
 153   ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
 154 #else
 155   errs() << "BlockFrequencyInfo::view is only available in debug builds on "
 156             "systems with Graphviz or gv!\n";
 157 #endif // NDEBUG
 158 }
 159
 160 const Function *BlockFrequencyInfo::getFunction() const {
 161   return BFI ? BFI->Fn : nullptr;
 162 }
 163
 164 raw_ostream &BlockFrequencyInfo::
 165 printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
 166   return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
 167 }
 168
 169 raw_ostream &
 170 BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
 171                                    const BasicBlock *BB) const {
 172   return BFI ? BFI->printBlockFreq(OS, BB) : OS;
 173 }
 174
 175 uint64_t BlockFrequencyInfo::getEntryFreq() const {
 176   return BFI ? BFI->getEntryFreq() : 0;
 177 }