LCOV - code coverage report
Current view: top level - lib/Analysis - BlockFrequencyInfo.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 104 132 78.8 %
Date: 2017-09-14 15:23:50 Functions: 24 30 80.0 %
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       72306 : static cl::opt<GVDAGType> ViewBlockFreqPropagationDAG(
      37             :     "view-block-freq-propagation-dags", cl::Hidden,
      38      216918 :     cl::desc("Pop up a window to show a dag displaying how block "
      39             :              "frequencies propagation through the CFG."),
      40      650754 :     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       72306 :                                                "profile count if available.")));
      49             : 
      50             : cl::opt<std::string>
      51       72306 :     ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,
      52      216918 :                           cl::desc("The option to specify "
      53             :                                    "the name of the function "
      54       72306 :                                    "whose CFG will be displayed."));
      55             : 
      56             : cl::opt<unsigned>
      57      289224 :     ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
      58      216918 :                        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      216918 :                                 "function multiplied by this percent."));
      63             : 
      64             : // Command line option to turn on CFG dot or text dump after profile annotation.
      65       72306 : cl::opt<PGOViewCountsType> PGOViewCounts(
      66             :     "pgo-view-counts", cl::Hidden,
      67      216918 :     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      506142 :     cl::values(clEnumValN(PGOVCT_None, "none", "do not show."),
      78             :                clEnumValN(PGOVCT_Graph, "graph", "show a graph."),
      79       72306 :                clEnumValN(PGOVCT_Text, "text", "show in text.")));
      80             : 
      81       72306 : static cl::opt<bool> PrintBlockFreq(
      82      216918 :     "print-bfi", cl::init(false), cl::Hidden,
      83      289224 :     cl::desc("Print the block frequency info."));
      84             : 
      85       72306 : cl::opt<std::string> PrintBlockFreqFuncName(
      86             :     "print-bfi-func-name", cl::Hidden,
      87      216918 :     cl::desc("The option to specify the name of the function "
      88       72306 :              "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           0 :   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           0 :     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           0 :       : 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         287 : BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
     155             :                                        const BranchProbabilityInfo &BPI,
     156         574 :                                        const LoopInfo &LI) {
     157         287 :   calculate(F, BPI, LI);
     158         287 : }
     159             : 
     160        1504 : BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
     161        3008 :     : BFI(std::move(Arg.BFI)) {}
     162             : 
     163           0 : BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
     164           0 :   releaseMemory();
     165           0 :   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         465 : 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         465 :   auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
     180         930 :   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
     181         930 :            PAC.preservedSet<CFGAnalyses>());
     182             : }
     183             : 
     184      205125 : void BlockFrequencyInfo::calculate(const Function &F,
     185             :                                    const BranchProbabilityInfo &BPI,
     186             :                                    const LoopInfo &LI) {
     187      410250 :   if (!BFI)
     188      205125 :     BFI.reset(new ImplType);
     189      410250 :   BFI->calculate(F, BPI, LI);
     190      205125 :   if (ViewBlockFreqPropagationDAG != GVDT_None &&
     191           0 :       (ViewBlockFreqFuncName.empty() ||
     192      205125 :        F.getName().equals(ViewBlockFreqFuncName))) {
     193           0 :     view();
     194             :   }
     195      205125 :   if (PrintBlockFreq &&
     196           0 :       (PrintBlockFreqFuncName.empty() ||
     197      410250 :        F.getName().equals(PrintBlockFreqFuncName))) {
     198           0 :     print(dbgs());
     199             :   }
     200      205125 : }
     201             : 
     202        4561 : BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
     203       18244 :   return BFI ? BFI->getBlockFreq(BB) : 0;
     204             : }
     205             : 
     206             : Optional<uint64_t>
     207         435 : BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
     208         870 :   if (!BFI)
     209             :     return None;
     210             : 
     211         870 :   return BFI->getBlockProfileCount(*getFunction(), BB);
     212             : }
     213             : 
     214             : Optional<uint64_t>
     215          70 : BlockFrequencyInfo::getProfileCountFromFreq(uint64_t Freq) const {
     216         140 :   if (!BFI)
     217             :     return None;
     218         140 :   return BFI->getProfileCountFromFreq(*getFunction(), Freq);
     219             : }
     220             : 
     221         931 : void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
     222             :   assert(BFI && "Expected analysis to be available");
     223        1862 :   BFI->setBlockFreq(BB, Freq);
     224         931 : }
     225             : 
     226         307 : void BlockFrequencyInfo::setBlockFreqAndScale(
     227             :     const BasicBlock *ReferenceBB, uint64_t Freq,
     228             :     SmallPtrSetImpl<BasicBlock *> &BlocksToScale) {
     229             :   assert(BFI && "Expected analysis to be available");
     230             :   // Use 128 bits APInt to avoid overflow.
     231         614 :   APInt NewFreq(128, Freq);
     232        1535 :   APInt OldFreq(128, BFI->getBlockFreq(ReferenceBB).getFrequency());
     233         614 :   APInt BBFreq(128, 0);
     234         985 :   for (auto *BB : BlocksToScale) {
     235        2034 :     BBFreq = BFI->getBlockFreq(BB).getFrequency();
     236             :     // Multiply first by NewFreq and then divide by OldFreq
     237             :     // to minimize loss of precision.
     238         678 :     BBFreq *= NewFreq;
     239             :     // udiv is an expensive operation in the general case. If this ends up being
     240             :     // a hot spot, one of the options proposed in
     241             :     // https://reviews.llvm.org/D28535#650071 could be used to avoid this.
     242        2034 :     BBFreq = BBFreq.udiv(OldFreq);
     243        2034 :     BFI->setBlockFreq(BB, BBFreq.getLimitedValue());
     244             :   }
     245         614 :   BFI->setBlockFreq(ReferenceBB, Freq);
     246         307 : }
     247             : 
     248             : /// Pop up a ghostview window with the current block frequency propagation
     249             : /// rendered using dot.
     250           0 : void BlockFrequencyInfo::view() const {
     251           0 :   ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
     252           0 : }
     253             : 
     254         505 : const Function *BlockFrequencyInfo::getFunction() const {
     255        1515 :   return BFI ? BFI->getFunction() : nullptr;
     256             : }
     257             : 
     258           0 : const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {
     259           0 :   return BFI ? &BFI->getBPI() : nullptr;
     260             : }
     261             : 
     262           0 : raw_ostream &BlockFrequencyInfo::
     263             : printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
     264           0 :   return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
     265             : }
     266             : 
     267             : raw_ostream &
     268           0 : BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
     269             :                                    const BasicBlock *BB) const {
     270           0 :   return BFI ? BFI->printBlockFreq(OS, BB) : OS;
     271             : }
     272             : 
     273         150 : uint64_t BlockFrequencyInfo::getEntryFreq() const {
     274         600 :   return BFI ? BFI->getEntryFreq() : 0;
     275             : }
     276             : 
     277     1142106 : void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
     278             : 
     279          52 : void BlockFrequencyInfo::print(raw_ostream &OS) const {
     280         104 :   if (BFI)
     281         104 :     BFI->print(OS);
     282          52 : }
     283             : 
     284       26866 : INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
     285             :                       "Block Frequency Analysis", true, true)
     286       26866 : INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
     287       26866 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
     288      491438 : INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
     289             :                     "Block Frequency Analysis", true, true)
     290             : 
     291             : char BlockFrequencyInfoWrapperPass::ID = 0;
     292             : 
     293       20136 : BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
     294       40272 :     : FunctionPass(ID) {
     295       20136 :   initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
     296       20136 : }
     297             : 
     298             : BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() = default;
     299             : 
     300          24 : void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
     301             :                                           const Module *) const {
     302          24 :   BFI.print(OS);
     303          24 : }
     304             : 
     305       19823 : void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     306       19823 :   AU.addRequired<BranchProbabilityInfoWrapperPass>();
     307       19823 :   AU.addRequired<LoopInfoWrapperPass>();
     308       19823 :   AU.setPreservesAll();
     309       19823 : }
     310             : 
     311      203955 : void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
     312             : 
     313      203955 : bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
     314             :   BranchProbabilityInfo &BPI =
     315      407910 :       getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
     316      407910 :   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     317      203955 :   BFI.calculate(F, BPI, LI);
     318      203955 :   return false;
     319             : }
     320             : 
     321             : AnalysisKey BlockFrequencyAnalysis::Key;
     322         752 : BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
     323             :                                                FunctionAnalysisManager &AM) {
     324         752 :   BlockFrequencyInfo BFI;
     325         752 :   BFI.calculate(F, AM.getResult<BranchProbabilityAnalysis>(F),
     326         752 :                 AM.getResult<LoopAnalysis>(F));
     327         752 :   return BFI;
     328             : }
     329             : 
     330             : PreservedAnalyses
     331          24 : BlockFrequencyPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
     332          24 :   OS << "Printing analysis results of BFI for function "
     333          24 :      << "'" << F.getName() << "':"
     334          24 :      << "\n";
     335          24 :   AM.getResult<BlockFrequencyAnalysis>(F).print(OS);
     336          24 :   return PreservedAnalyses::all();
     337      216918 : }

Generated by: LCOV version 1.13