contrib/llvm/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 static cl::opt<GVDAGType> ViewBlockFreqPropagationDAG(
  31     "view-block-freq-propagation-dags", cl::Hidden,
  32     cl::desc("Pop up a window to show a dag displaying how block "
  33              "frequencies propagation through the CFG."),
  34     cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
  35                clEnumValN(GVDT_Fraction, "fraction",
  36                           "display a graph using the "
  37                           "fractional block frequency representation."),
  38                clEnumValN(GVDT_Integer, "integer",
  39                           "display a graph using the raw "
  40                           "integer fractional block frequency representation."),
  41                clEnumValN(GVDT_Count, "count", "display a graph using the real "
  42                                                "profile count if available."),
  43                clEnumValEnd));
  44
  45 cl::opt<std::string>
  46     ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,
  47                           cl::desc("The option to specify "
  48                                    "the name of the function "
  49                                    "whose CFG will be displayed."));
  50
  51 cl::opt<unsigned>
  52     ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
  53                        cl::desc("An integer in percent used to specify "
  54                                 "the hot blocks/edges to be displayed "
  55                                 "in red: a block or edge whose frequency "
  56                                 "is no less than the max frequency of the "
  57                                 "function multiplied by this percent."));
  58
  59 namespace llvm {
  60
  61 template <>
  62 struct GraphTraits<BlockFrequencyInfo *> {
  63   typedef const BasicBlock NodeType;
  64   typedef succ_const_iterator ChildIteratorType;
  65   typedef Function::const_iterator nodes_iterator;
  66
  67   static inline const NodeType *getEntryNode(const BlockFrequencyInfo *G) {
  68     return &G->getFunction()->front();
  69   }
  70   static ChildIteratorType child_begin(const NodeType *N) {
  71     return succ_begin(N);
  72   }
  73   static ChildIteratorType child_end(const NodeType *N) {
  74     return succ_end(N);
  75   }
  76   static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
  77     return G->getFunction()->begin();
  78   }
  79   static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
  80     return G->getFunction()->end();
  81   }
  82 };
  83
  84 typedef BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>
  85     BFIDOTGTraitsBase;
  86
  87 template <>
  88 struct DOTGraphTraits<BlockFrequencyInfo *> : public BFIDOTGTraitsBase {
  89   explicit DOTGraphTraits(bool isSimple = false)
  90       : BFIDOTGTraitsBase(isSimple) {}
  91
  92   std::string getNodeLabel(const BasicBlock *Node,
  93                            const BlockFrequencyInfo *Graph) {
  94
  95     return BFIDOTGTraitsBase::getNodeLabel(Node, Graph,
  96                                            ViewBlockFreqPropagationDAG);
  97   }
  98
  99   std::string getNodeAttributes(const BasicBlock *Node,
 100                                 const BlockFrequencyInfo *Graph) {
 101     return BFIDOTGTraitsBase::getNodeAttributes(Node, Graph,
 102                                                 ViewHotFreqPercent);
 103   }
 104
 105   std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
 106                                 const BlockFrequencyInfo *BFI) {
 107     return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),
 108                                                 ViewHotFreqPercent);
 109   }
 110 };
 111
 112 } // end namespace llvm
 113 #endif
 114
 115 BlockFrequencyInfo::BlockFrequencyInfo() {}
 116
 117 BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
 118                                        const BranchProbabilityInfo &BPI,
 119                                        const LoopInfo &LI) {
 120   calculate(F, BPI, LI);
 121 }
 122
 123 BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
 124     : BFI(std::move(Arg.BFI)) {}
 125
 126 BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
 127   releaseMemory();
 128   BFI = std::move(RHS.BFI);
 129   return *this;
 130 }
 131
 132 // Explicitly define the default constructor otherwise it would be implicitly
 133 // defined at the first ODR-use which is the BFI member in the
 134 // LazyBlockFrequencyInfo header.  The dtor needs the BlockFrequencyInfoImpl
 135 // template instantiated which is not available in the header.
 136 BlockFrequencyInfo::~BlockFrequencyInfo() {}
 137
 138 void BlockFrequencyInfo::calculate(const Function &F,
 139                                    const BranchProbabilityInfo &BPI,
 140                                    const LoopInfo &LI) {
 141   if (!BFI)
 142     BFI.reset(new ImplType);
 143   BFI->calculate(F, BPI, LI);
 144 #ifndef NDEBUG
 145   if (ViewBlockFreqPropagationDAG != GVDT_None &&
 146       (ViewBlockFreqFuncName.empty() ||
 147        F.getName().equals(ViewBlockFreqFuncName))) {
 148     view();
 149   }
 150 #endif
 151 }
 152
 153 BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
 154   return BFI ? BFI->getBlockFreq(BB) : 0;
 155 }
 156
 157 Optional<uint64_t>
 158 BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
 159   if (!BFI)
 160     return None;
 161
 162   return BFI->getBlockProfileCount(*getFunction(), BB);
 163 }
 164
 165 void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
 166   assert(BFI && "Expected analysis to be available");
 167   BFI->setBlockFreq(BB, Freq);
 168 }
 169
 170 /// Pop up a ghostview window with the current block frequency propagation
 171 /// rendered using dot.
 172 void BlockFrequencyInfo::view() const {
 173 // This code is only for debugging.
 174 #ifndef NDEBUG
 175   ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
 176 #else
 177   errs() << "BlockFrequencyInfo::view is only available in debug builds on "
 178             "systems with Graphviz or gv!\n";
 179 #endif // NDEBUG
 180 }
 181
 182 const Function *BlockFrequencyInfo::getFunction() const {
 183   return BFI ? BFI->getFunction() : nullptr;
 184 }
 185
 186 const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {
 187   return BFI ? &BFI->getBPI() : nullptr;
 188 }
 189
 190 raw_ostream &BlockFrequencyInfo::
 191 printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
 192   return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
 193 }
 194
 195 raw_ostream &
 196 BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
 197                                    const BasicBlock *BB) const {
 198   return BFI ? BFI->printBlockFreq(OS, BB) : OS;
 199 }
 200
 201 uint64_t BlockFrequencyInfo::getEntryFreq() const {
 202   return BFI ? BFI->getEntryFreq() : 0;
 203 }
 204
 205 void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
 206
 207 void BlockFrequencyInfo::print(raw_ostream &OS) const {
 208   if (BFI)
 209     BFI->print(OS);
 210 }
 211
 212
 213 INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
 214                       "Block Frequency Analysis", true, true)
 215 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
 216 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 217 INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
 218                     "Block Frequency Analysis", true, true)
 219
 220 char BlockFrequencyInfoWrapperPass::ID = 0;
 221
 222
 223 BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
 224     : FunctionPass(ID) {
 225   initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
 226 }
 227
 228 BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {}
 229
 230 void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
 231                                           const Module *) const {
 232   BFI.print(OS);
 233 }
 234
 235 void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 236   AU.addRequired<BranchProbabilityInfoWrapperPass>();
 237   AU.addRequired<LoopInfoWrapperPass>();
 238   AU.setPreservesAll();
 239 }
 240
 241 void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
 242
 243 bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
 244   BranchProbabilityInfo &BPI =
 245       getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
 246   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 247   BFI.calculate(F, BPI, LI);
 248   return false;
 249 }
 250
 251 char BlockFrequencyAnalysis::PassID;
 252 BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
 253                                                AnalysisManager<Function> &AM) {
 254   BlockFrequencyInfo BFI;
 255   BFI.calculate(F, AM.getResult<BranchProbabilityAnalysis>(F),
 256                 AM.getResult<LoopAnalysis>(F));
 257   return BFI;
 258 }
 259
 260 PreservedAnalyses
 261 BlockFrequencyPrinterPass::run(Function &F, AnalysisManager<Function> &AM) {
 262   OS << "Printing analysis results of BFI for function "
 263      << "'" << F.getName() << "':"
 264      << "\n";
 265   AM.getResult<BlockFrequencyAnalysis>(F).print(OS);
 266   return PreservedAnalyses::all();
 267 }