Home | History | Annotate | Download | only in Analysis 
      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 }
    268