LCOV - code coverage report
Current view: top level - lib/Analysis - BlockFrequencyInfo.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 98 120 81.7 %
Date: 2018-07-13 00:08:38 Functions: 25 31 80.6 %
Legend: Lines: hit not hit

          Line data    Source code
       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/ADT/APInt.h"
      16             : #include "llvm/ADT/None.h"
      17             : #include "llvm/ADT/iterator.h"
      18             : #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
      19             : #include "llvm/Analysis/BranchProbabilityInfo.h"
      20             : #include "llvm/Analysis/LoopInfo.h"
      21             : #include "llvm/IR/CFG.h"
      22             : #include "llvm/IR/Function.h"
      23             : #include "llvm/IR/PassManager.h"
      24             : #include "llvm/Pass.h"
      25             : #include "llvm/Support/CommandLine.h"
      26             : #include "llvm/Support/GraphWriter.h"
      27             : #include "llvm/Support/raw_ostream.h"
      28             : #include <algorithm>
      29             : #include <cassert>
      30             : #include <string>
      31             : 
      32             : using namespace llvm;
      33             : 
      34             : #define DEBUG_TYPE "block-freq"
      35             : 
      36       99743 : static cl::opt<GVDAGType> ViewBlockFreqPropagationDAG(
      37             :     "view-block-freq-propagation-dags", cl::Hidden,
      38       99743 :     cl::desc("Pop up a window to show a dag displaying how block "
      39             :              "frequencies propagation through the CFG."),
      40      598458 :     cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
      41             :                clEnumValN(GVDT_Fraction, "fraction",
      42             :                           "display a graph using the "
      43             :                           "fractional block frequency representation."),
      44             :                clEnumValN(GVDT_Integer, "integer",
      45             :                           "display a graph using the raw "
      46             :                           "integer fractional block frequency representation."),
      47             :                clEnumValN(GVDT_Count, "count", "display a graph using the real "
      48       99743 :                                                "profile count if available.")));
      49             : 
      50             : cl::opt<std::string>
      51       99743 :     ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,
      52       99743 :                           cl::desc("The option to specify "
      53             :                                    "the name of the function "
      54       99743 :                                    "whose CFG will be displayed."));
      55             : 
      56             : cl::opt<unsigned>
      57      299229 :     ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
      58       99743 :                        cl::desc("An integer in percent used to specify "
      59             :                                 "the hot blocks/edges to be displayed "
      60             :                                 "in red: a block or edge whose frequency "
      61             :                                 "is no less than the max frequency of the "
      62      299229 :                                 "function multiplied by this percent."));
      63             : 
      64             : // Command line option to turn on CFG dot or text dump after profile annotation.
      65       99743 : cl::opt<PGOViewCountsType> PGOViewCounts(
      66             :     "pgo-view-counts", cl::Hidden,
      67       99743 :     cl::desc("A boolean option to show CFG dag or text with "
      68             :              "block profile counts and branch probabilities "
      69             :              "right after PGO profile annotation step. The "
      70             :              "profile counts are computed using branch "
      71             :              "probabilities from the runtime profile data and "
      72             :              "block frequency propagation algorithm. To view "
      73             :              "the raw counts from the profile, use option "
      74             :              "-pgo-view-raw-counts instead. To limit graph "
      75             :              "display to only one function, use filtering option "
      76             :              "-view-bfi-func-name."),
      77      498715 :     cl::values(clEnumValN(PGOVCT_None, "none", "do not show."),
      78             :                clEnumValN(PGOVCT_Graph, "graph", "show a graph."),
      79       99743 :                clEnumValN(PGOVCT_Text, "text", "show in text.")));
      80             : 
      81       99743 : static cl::opt<bool> PrintBlockFreq(
      82      199486 :     "print-bfi", cl::init(false), cl::Hidden,
      83      299229 :     cl::desc("Print the block frequency info."));
      84             : 
      85       99743 : cl::opt<std::string> PrintBlockFreqFuncName(
      86             :     "print-bfi-func-name", cl::Hidden,
      87       99743 :     cl::desc("The option to specify the name of the function "
      88       99743 :              "whose block frequency info is printed."));
      89             : 
      90             : namespace llvm {
      91             : 
      92             : static GVDAGType getGVDT() {
      93           0 :   if (PGOViewCounts == PGOVCT_Graph)
      94             :     return GVDT_Count;
      95             :   return ViewBlockFreqPropagationDAG;
      96             : }
      97             : 
      98             : template <>
      99             : struct GraphTraits<BlockFrequencyInfo *> {
     100             :   using NodeRef = const BasicBlock *;
     101             :   using ChildIteratorType = succ_const_iterator;
     102             :   using nodes_iterator = pointer_iterator<Function::const_iterator>;
     103             : 
     104             :   static NodeRef getEntryNode(const BlockFrequencyInfo *G) {
     105             :     return &G->getFunction()->front();
     106             :   }
     107             : 
     108             :   static ChildIteratorType child_begin(const NodeRef N) {
     109             :     return succ_begin(N);
     110             :   }
     111             : 
     112           0 :   static ChildIteratorType child_end(const NodeRef N) { return succ_end(N); }
     113             : 
     114             :   static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
     115           0 :     return nodes_iterator(G->getFunction()->begin());
     116             :   }
     117             : 
     118             :   static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
     119           0 :     return nodes_iterator(G->getFunction()->end());
     120             :   }
     121             : };
     122             : 
     123             : using BFIDOTGTraitsBase =
     124             :     BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>;
     125             : 
     126             : template <>
     127             : struct DOTGraphTraits<BlockFrequencyInfo *> : public BFIDOTGTraitsBase {
     128             :   explicit DOTGraphTraits(bool isSimple = false)
     129             :       : BFIDOTGTraitsBase(isSimple) {}
     130             : 
     131             :   std::string getNodeLabel(const BasicBlock *Node,
     132             :                            const BlockFrequencyInfo *Graph) {
     133             : 
     134           0 :     return BFIDOTGTraitsBase::getNodeLabel(Node, Graph, getGVDT());
     135             :   }
     136             : 
     137             :   std::string getNodeAttributes(const BasicBlock *Node,
     138             :                                 const BlockFrequencyInfo *Graph) {
     139             :     return BFIDOTGTraitsBase::getNodeAttributes(Node, Graph,
     140           0 :                                                 ViewHotFreqPercent);
     141             :   }
     142             : 
     143           0 :   std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
     144             :                                 const BlockFrequencyInfo *BFI) {
     145             :     return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),
     146           0 :                                                 ViewHotFreqPercent);
     147             :   }
     148             : };
     149             : 
     150             : } // end namespace llvm
     151             : 
     152             : BlockFrequencyInfo::BlockFrequencyInfo() = default;
     153             : 
     154      185308 : BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
     155             :                                        const BranchProbabilityInfo &BPI,
     156             :                                        const LoopInfo &LI) {
     157      185308 :   calculate(F, BPI, LI);
     158      185308 : }
     159             : 
     160        1742 : BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
     161        1742 :     : BFI(std::move(Arg.BFI)) {}
     162             : 
     163           0 : BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
     164           0 :   releaseMemory();
     165             :   BFI = std::move(RHS.BFI);
     166           0 :   return *this;
     167             : }
     168             : 
     169             : // Explicitly define the default constructor otherwise it would be implicitly
     170             : // defined at the first ODR-use which is the BFI member in the
     171             : // LazyBlockFrequencyInfo header.  The dtor needs the BlockFrequencyInfoImpl
     172             : // template instantiated which is not available in the header.
     173             : BlockFrequencyInfo::~BlockFrequencyInfo() = default;
     174             : 
     175         524 : bool BlockFrequencyInfo::invalidate(Function &F, const PreservedAnalyses &PA,
     176             :                                     FunctionAnalysisManager::Invalidator &) {
     177             :   // Check whether the analysis, all analyses on functions, or the function's
     178             :   // CFG have been preserved.
     179             :   auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
     180        1048 :   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
     181        1048 :            PAC.preservedSet<CFGAnalyses>());
     182             : }
     183             : 
     184      443823 : void BlockFrequencyInfo::calculate(const Function &F,
     185             :                                    const BranchProbabilityInfo &BPI,
     186             :                                    const LoopInfo &LI) {
     187      443823 :   if (!BFI)
     188      443823 :     BFI.reset(new ImplType);
     189      443823 :   BFI->calculate(F, BPI, LI);
     190      443823 :   if (ViewBlockFreqPropagationDAG != GVDT_None &&
     191             :       (ViewBlockFreqFuncName.empty() ||
     192      443823 :        F.getName().equals(ViewBlockFreqFuncName))) {
     193           0 :     view();
     194             :   }
     195      443823 :   if (PrintBlockFreq &&
     196             :       (PrintBlockFreqFuncName.empty() ||
     197      443823 :        F.getName().equals(PrintBlockFreqFuncName))) {
     198           0 :     print(dbgs());
     199             :   }
     200      443823 : }
     201             : 
     202       13467 : BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
     203       26934 :   return BFI ? BFI->getBlockFreq(BB) : 0;
     204             : }
     205             : 
     206             : Optional<uint64_t>
     207         736 : BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
     208         736 :   if (!BFI)
     209             :     return None;
     210             : 
     211         736 :   return BFI->getBlockProfileCount(*getFunction(), BB);
     212             : }
     213             : 
     214             : Optional<uint64_t>
     215          91 : BlockFrequencyInfo::getProfileCountFromFreq(uint64_t Freq) const {
     216          91 :   if (!BFI)
     217             :     return None;
     218          91 :   return BFI->getProfileCountFromFreq(*getFunction(), Freq);
     219             : }
     220             : 
     221         265 : bool BlockFrequencyInfo::isIrrLoopHeader(const BasicBlock *BB) {
     222             :   assert(BFI && "Expected analysis to be available");
     223         265 :   return BFI->isIrrLoopHeader(BB);
     224             : }
     225             : 
     226        1029 : void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
     227             :   assert(BFI && "Expected analysis to be available");
     228        1029 :   BFI->setBlockFreq(BB, Freq);
     229        1029 : }
     230             : 
     231         357 : void BlockFrequencyInfo::setBlockFreqAndScale(
     232             :     const BasicBlock *ReferenceBB, uint64_t Freq,
     233             :     SmallPtrSetImpl<BasicBlock *> &BlocksToScale) {
     234             :   assert(BFI && "Expected analysis to be available");
     235             :   // Use 128 bits APInt to avoid overflow.
     236             :   APInt NewFreq(128, Freq);
     237         714 :   APInt OldFreq(128, BFI->getBlockFreq(ReferenceBB).getFrequency());
     238             :   APInt BBFreq(128, 0);
     239         357 :   for (auto *BB : BlocksToScale) {
     240        1462 :     BBFreq = BFI->getBlockFreq(BB).getFrequency();
     241             :     // Multiply first by NewFreq and then divide by OldFreq
     242             :     // to minimize loss of precision.
     243         731 :     BBFreq *= NewFreq;
     244             :     // udiv is an expensive operation in the general case. If this ends up being
     245             :     // a hot spot, one of the options proposed in
     246             :     // https://reviews.llvm.org/D28535#650071 could be used to avoid this.
     247        1462 :     BBFreq = BBFreq.udiv(OldFreq);
     248         731 :     BFI->setBlockFreq(BB, BBFreq.getLimitedValue());
     249             :   }
     250         357 :   BFI->setBlockFreq(ReferenceBB, Freq);
     251         357 : }
     252             : 
     253             : /// Pop up a ghostview window with the current block frequency propagation
     254             : /// rendered using dot.
     255           0 : void BlockFrequencyInfo::view() const {
     256           0 :   ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
     257           0 : }
     258             : 
     259         827 : const Function *BlockFrequencyInfo::getFunction() const {
     260         827 :   return BFI ? BFI->getFunction() : nullptr;
     261             : }
     262             : 
     263           0 : const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {
     264           0 :   return BFI ? &BFI->getBPI() : nullptr;
     265             : }
     266             : 
     267           0 : raw_ostream &BlockFrequencyInfo::
     268             : printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
     269           0 :   return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
     270             : }
     271             : 
     272             : raw_ostream &
     273           0 : BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
     274             :                                    const BasicBlock *BB) const {
     275           0 :   return BFI ? BFI->printBlockFreq(OS, BB) : OS;
     276             : }
     277             : 
     278         440 : uint64_t BlockFrequencyInfo::getEntryFreq() const {
     279         880 :   return BFI ? BFI->getEntryFreq() : 0;
     280             : }
     281             : 
     282     1285516 : void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
     283             : 
     284          63 : void BlockFrequencyInfo::print(raw_ostream &OS) const {
     285          63 :   if (BFI)
     286          63 :     BFI->print(OS);
     287          63 : }
     288             : 
     289       32355 : INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
     290             :                       "Block Frequency Analysis", true, true)
     291       32355 : INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
     292       32355 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
     293      445836 : INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
     294             :                     "Block Frequency Analysis", true, true)
     295             : 
     296             : char BlockFrequencyInfoWrapperPass::ID = 0;
     297             : 
     298       31225 : BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
     299       31225 :     : FunctionPass(ID) {
     300       31225 :   initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
     301       31225 : }
     302             : 
     303             : BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() = default;
     304             : 
     305          29 : void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
     306             :                                           const Module *) const {
     307          29 :   BFI.print(OS);
     308          29 : }
     309             : 
     310       27547 : void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     311             :   AU.addRequired<BranchProbabilityInfoWrapperPass>();
     312             :   AU.addRequired<LoopInfoWrapperPass>();
     313             :   AU.setPreservesAll();
     314       27547 : }
     315             : 
     316      257435 : void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
     317             : 
     318      257435 : bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
     319             :   BranchProbabilityInfo &BPI =
     320      257435 :       getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
     321      257435 :   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     322      257435 :   BFI.calculate(F, BPI, LI);
     323      257435 :   return false;
     324             : }
     325             : 
     326             : AnalysisKey BlockFrequencyAnalysis::Key;
     327         871 : BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
     328             :                                                FunctionAnalysisManager &AM) {
     329         871 :   BlockFrequencyInfo BFI;
     330         871 :   BFI.calculate(F, AM.getResult<BranchProbabilityAnalysis>(F),
     331             :                 AM.getResult<LoopAnalysis>(F));
     332         871 :   return BFI;
     333             : }
     334             : 
     335             : PreservedAnalyses
     336          29 : BlockFrequencyPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
     337          29 :   OS << "Printing analysis results of BFI for function "
     338          29 :      << "'" << F.getName() << "':"
     339          29 :      << "\n";
     340          29 :   AM.getResult<BlockFrequencyAnalysis>(F).print(OS);
     341          29 :   return PreservedAnalyses::all();
     342      299229 : }

Generated by: LCOV version 1.13