348 lines · 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-exception6//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/iterator.h"16#include "llvm/Analysis/BlockFrequencyInfoImpl.h"17#include "llvm/Analysis/BranchProbabilityInfo.h"18#include "llvm/Analysis/LoopInfo.h"19#include "llvm/IR/CFG.h"20#include "llvm/IR/Function.h"21#include "llvm/IR/PassManager.h"22#include "llvm/InitializePasses.h"23#include "llvm/Pass.h"24#include "llvm/Support/CommandLine.h"25#include "llvm/Support/GraphWriter.h"26#include "llvm/Support/raw_ostream.h"27#include <cassert>28#include <optional>29#include <string>30 31using namespace llvm;32 33#define DEBUG_TYPE "block-freq"34 35static cl::opt<GVDAGType> ViewBlockFreqPropagationDAG(36 "view-block-freq-propagation-dags", cl::Hidden,37 cl::desc("Pop up a window to show a dag displaying how block "38 "frequencies propagation through the CFG."),39 cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),40 clEnumValN(GVDT_Fraction, "fraction",41 "display a graph using the "42 "fractional block frequency representation."),43 clEnumValN(GVDT_Integer, "integer",44 "display a graph using the raw "45 "integer fractional block frequency representation."),46 clEnumValN(GVDT_Count, "count", "display a graph using the real "47 "profile count if available.")));48 49namespace llvm {50cl::opt<std::string>51 ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,52 cl::desc("The option to specify "53 "the name of the function "54 "whose CFG will be displayed."));55 56cl::opt<unsigned>57 ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,58 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 "function multiplied by this percent."));63 64// Command line option to turn on CFG dot or text dump after profile annotation.65cl::opt<PGOViewCountsType> PGOViewCounts(66 "pgo-view-counts", cl::Hidden,67 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 cl::values(clEnumValN(PGOVCT_None, "none", "do not show."),78 clEnumValN(PGOVCT_Graph, "graph", "show a graph."),79 clEnumValN(PGOVCT_Text, "text", "show in text.")));80 81static cl::opt<bool> PrintBFI("print-bfi", cl::init(false), cl::Hidden,82 cl::desc("Print the block frequency info."));83 84cl::opt<std::string>85 PrintBFIFuncName("print-bfi-func-name", cl::Hidden,86 cl::desc("The option to specify the name of the function "87 "whose block frequency info is printed."));88} // namespace llvm89 90namespace llvm {91 92static GVDAGType getGVDT() {93 if (PGOViewCounts == PGOVCT_Graph)94 return GVDT_Count;95 return ViewBlockFreqPropagationDAG;96}97 98template <>99struct GraphTraits<BlockFrequencyInfo *> {100 using NodeRef = const BasicBlock *;101 using ChildIteratorType = const_succ_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 static ChildIteratorType child_end(const NodeRef N) { return succ_end(N); }113 114 static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {115 return nodes_iterator(G->getFunction()->begin());116 }117 118 static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {119 return nodes_iterator(G->getFunction()->end());120 }121};122 123using BFIDOTGTraitsBase =124 BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>;125 126template <>127struct 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 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 ViewHotFreqPercent);141 }142 143 std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,144 const BlockFrequencyInfo *BFI) {145 return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),146 ViewHotFreqPercent);147 }148};149 150} // end namespace llvm151 152BlockFrequencyInfo::BlockFrequencyInfo() = default;153 154BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,155 const BranchProbabilityInfo &BPI,156 const LoopInfo &LI) {157 calculate(F, BPI, LI);158}159 160BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)161 : BFI(std::move(Arg.BFI)) {}162 163BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {164 releaseMemory();165 BFI = std::move(RHS.BFI);166 return *this;167}168 169// Explicitly define the default constructor otherwise it would be implicitly170// defined at the first ODR-use which is the BFI member in the171// LazyBlockFrequencyInfo header. The dtor needs the BlockFrequencyInfoImpl172// template instantiated which is not available in the header.173BlockFrequencyInfo::~BlockFrequencyInfo() = default;174 175bool BlockFrequencyInfo::invalidate(Function &F, const PreservedAnalyses &PA,176 FunctionAnalysisManager::Invalidator &) {177 // Check whether the analysis, all analyses on functions, or the function's178 // CFG have been preserved.179 auto PAC = PA.getChecker<BlockFrequencyAnalysis>();180 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||181 PAC.preservedSet<CFGAnalyses>());182}183 184void BlockFrequencyInfo::calculate(const Function &F,185 const BranchProbabilityInfo &BPI,186 const LoopInfo &LI) {187 if (!BFI)188 BFI.reset(new ImplType);189 BFI->calculate(F, BPI, LI);190 if (ViewBlockFreqPropagationDAG != GVDT_None &&191 (ViewBlockFreqFuncName.empty() || F.getName() == ViewBlockFreqFuncName)) {192 view();193 }194 if (PrintBFI &&195 (PrintBFIFuncName.empty() || F.getName() == PrintBFIFuncName)) {196 print(dbgs());197 }198}199 200BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {201 return BFI ? BFI->getBlockFreq(BB) : BlockFrequency(0);202}203 204std::optional<uint64_t>205BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB,206 bool AllowSynthetic) const {207 if (!BFI)208 return std::nullopt;209 210 return BFI->getBlockProfileCount(*getFunction(), BB, AllowSynthetic);211}212 213std::optional<uint64_t>214BlockFrequencyInfo::getProfileCountFromFreq(BlockFrequency Freq) const {215 if (!BFI)216 return std::nullopt;217 return BFI->getProfileCountFromFreq(*getFunction(), Freq);218}219 220bool BlockFrequencyInfo::isIrrLoopHeader(const BasicBlock *BB) {221 assert(BFI && "Expected analysis to be available");222 return BFI->isIrrLoopHeader(BB);223}224 225void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB,226 BlockFrequency Freq) {227 assert(BFI && "Expected analysis to be available");228 BFI->setBlockFreq(BB, Freq);229}230 231void BlockFrequencyInfo::setBlockFreqAndScale(232 const BasicBlock *ReferenceBB, BlockFrequency 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.getFrequency());237 APInt OldFreq(128, BFI->getBlockFreq(ReferenceBB).getFrequency());238 APInt BBFreq(128, 0);239 for (auto *BB : BlocksToScale) {240 BBFreq = BFI->getBlockFreq(BB).getFrequency();241 // Multiply first by NewFreq and then divide by OldFreq242 // to minimize loss of precision.243 BBFreq *= NewFreq;244 // udiv is an expensive operation in the general case. If this ends up being245 // a hot spot, one of the options proposed in246 // https://reviews.llvm.org/D28535#650071 could be used to avoid this.247 BBFreq = BBFreq.udiv(OldFreq);248 BFI->setBlockFreq(BB, BlockFrequency(BBFreq.getLimitedValue()));249 }250 BFI->setBlockFreq(ReferenceBB, Freq);251}252 253/// Pop up a ghostview window with the current block frequency propagation254/// rendered using dot.255void BlockFrequencyInfo::view(StringRef title) const {256 ViewGraph(const_cast<BlockFrequencyInfo *>(this), title);257}258 259const Function *BlockFrequencyInfo::getFunction() const {260 return BFI ? BFI->getFunction() : nullptr;261}262 263const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {264 return BFI ? &BFI->getBPI() : nullptr;265}266 267BlockFrequency BlockFrequencyInfo::getEntryFreq() const {268 return BFI ? BFI->getEntryFreq() : BlockFrequency(0);269}270 271void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }272 273void BlockFrequencyInfo::print(raw_ostream &OS) const {274 if (BFI)275 BFI->print(OS);276}277 278void BlockFrequencyInfo::verifyMatch(BlockFrequencyInfo &Other) const {279 if (BFI)280 BFI->verifyMatch(*Other.BFI);281}282 283Printable llvm::printBlockFreq(const BlockFrequencyInfo &BFI,284 BlockFrequency Freq) {285 return Printable([&BFI, Freq](raw_ostream &OS) {286 printRelativeBlockFreq(OS, BFI.getEntryFreq(), Freq);287 });288}289 290Printable llvm::printBlockFreq(const BlockFrequencyInfo &BFI,291 const BasicBlock &BB) {292 return printBlockFreq(BFI, BFI.getBlockFreq(&BB));293}294 295INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",296 "Block Frequency Analysis", true, true)297INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)298INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)299INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",300 "Block Frequency Analysis", true, true)301 302char BlockFrequencyInfoWrapperPass::ID = 0;303 304BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()305 : FunctionPass(ID) {}306 307BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() = default;308 309void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,310 const Module *) const {311 BFI.print(OS);312}313 314void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {315 AU.addRequired<BranchProbabilityInfoWrapperPass>();316 AU.addRequired<LoopInfoWrapperPass>();317 AU.setPreservesAll();318}319 320void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }321 322bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {323 BranchProbabilityInfo &BPI =324 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();325 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();326 BFI.calculate(F, BPI, LI);327 return false;328}329 330AnalysisKey BlockFrequencyAnalysis::Key;331BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,332 FunctionAnalysisManager &AM) {333 auto &BP = AM.getResult<BranchProbabilityAnalysis>(F);334 auto &LI = AM.getResult<LoopAnalysis>(F);335 BlockFrequencyInfo BFI;336 BFI.calculate(F, BP, LI);337 return BFI;338}339 340PreservedAnalyses341BlockFrequencyPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {342 OS << "Printing analysis results of BFI for function "343 << "'" << F.getName() << "':"344 << "\n";345 AM.getResult<BlockFrequencyAnalysis>(F).print(OS);346 return PreservedAnalyses::all();347}348