llvm/lib/Analysis/BlockFrequencyInfo.cpp

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