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