1 //===- BlockFrequencyInfo.cpp - Block Frequency Analysis ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Loops should be simplified before this analysis.
12 //===----------------------------------------------------------------------===//
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"
27 #define DEBUG_TYPE "block-freq"
29 static cl::opt<GVDAGType> ViewBlockFreqPropagationDAG(
30 "view-block-freq-propagation-dags", cl::Hidden,
31 cl::desc("Pop up a window to show a dag displaying how block "
32 "frequencies propagation through the CFG."),
33 cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
34 clEnumValN(GVDT_Fraction, "fraction",
35 "display a graph using the "
36 "fractional block frequency representation."),
37 clEnumValN(GVDT_Integer, "integer",
38 "display a graph using the raw "
39 "integer fractional block frequency representation."),
40 clEnumValN(GVDT_Count, "count", "display a graph using the real "
41 "profile count if available.")));
44 ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,
45 cl::desc("The option to specify "
46 "the name of the function "
47 "whose CFG will be displayed."));
50 ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
51 cl::desc("An integer in percent used to specify "
52 "the hot blocks/edges to be displayed "
53 "in red: a block or edge whose frequency "
54 "is no less than the max frequency of the "
55 "function multiplied by this percent."));
57 // Command line option to turn on CFG dot dump after profile annotation.
59 PGOViewCounts("pgo-view-counts", cl::init(false), cl::Hidden,
60 cl::desc("A boolean option to show CFG dag with "
61 "block profile counts and branch probabilities "
62 "right after PGO profile annotation step. The "
63 "profile counts are computed using branch "
64 "probabilities from the runtime profile data and "
65 "block frequency propagation algorithm. To view "
66 "the raw counts from the profile, use option "
67 "-pgo-view-raw-counts instead. To limit graph "
68 "display to only one function, use filtering option "
69 "-view-bfi-func-name."));
73 static GVDAGType getGVDT() {
77 return ViewBlockFreqPropagationDAG;
81 struct GraphTraits<BlockFrequencyInfo *> {
82 typedef const BasicBlock *NodeRef;
83 typedef succ_const_iterator ChildIteratorType;
84 typedef pointer_iterator<Function::const_iterator> nodes_iterator;
86 static NodeRef getEntryNode(const BlockFrequencyInfo *G) {
87 return &G->getFunction()->front();
89 static ChildIteratorType child_begin(const NodeRef N) {
92 static ChildIteratorType child_end(const NodeRef N) { return succ_end(N); }
93 static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
94 return nodes_iterator(G->getFunction()->begin());
96 static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
97 return nodes_iterator(G->getFunction()->end());
101 typedef BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>
105 struct DOTGraphTraits<BlockFrequencyInfo *> : public BFIDOTGTraitsBase {
106 explicit DOTGraphTraits(bool isSimple = false)
107 : BFIDOTGTraitsBase(isSimple) {}
109 std::string getNodeLabel(const BasicBlock *Node,
110 const BlockFrequencyInfo *Graph) {
112 return BFIDOTGTraitsBase::getNodeLabel(Node, Graph, getGVDT());
115 std::string getNodeAttributes(const BasicBlock *Node,
116 const BlockFrequencyInfo *Graph) {
117 return BFIDOTGTraitsBase::getNodeAttributes(Node, Graph,
121 std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
122 const BlockFrequencyInfo *BFI) {
123 return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),
128 } // end namespace llvm
130 BlockFrequencyInfo::BlockFrequencyInfo() {}
132 BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
133 const BranchProbabilityInfo &BPI,
134 const LoopInfo &LI) {
135 calculate(F, BPI, LI);
138 BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
139 : BFI(std::move(Arg.BFI)) {}
141 BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
143 BFI = std::move(RHS.BFI);
147 // Explicitly define the default constructor otherwise it would be implicitly
148 // defined at the first ODR-use which is the BFI member in the
149 // LazyBlockFrequencyInfo header. The dtor needs the BlockFrequencyInfoImpl
150 // template instantiated which is not available in the header.
151 BlockFrequencyInfo::~BlockFrequencyInfo() {}
153 bool BlockFrequencyInfo::invalidate(Function &F, const PreservedAnalyses &PA,
154 FunctionAnalysisManager::Invalidator &) {
155 // Check whether the analysis, all analyses on functions, or the function's
156 // CFG have been preserved.
157 auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
158 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
159 PAC.preservedSet<CFGAnalyses>());
162 void BlockFrequencyInfo::calculate(const Function &F,
163 const BranchProbabilityInfo &BPI,
164 const LoopInfo &LI) {
166 BFI.reset(new ImplType);
167 BFI->calculate(F, BPI, LI);
168 if (ViewBlockFreqPropagationDAG != GVDT_None &&
169 (ViewBlockFreqFuncName.empty() ||
170 F.getName().equals(ViewBlockFreqFuncName))) {
175 BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
176 return BFI ? BFI->getBlockFreq(BB) : 0;
180 BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
184 return BFI->getBlockProfileCount(*getFunction(), BB);
188 BlockFrequencyInfo::getProfileCountFromFreq(uint64_t Freq) const {
191 return BFI->getProfileCountFromFreq(*getFunction(), Freq);
194 void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
195 assert(BFI && "Expected analysis to be available");
196 BFI->setBlockFreq(BB, Freq);
199 void BlockFrequencyInfo::setBlockFreqAndScale(
200 const BasicBlock *ReferenceBB, uint64_t Freq,
201 SmallPtrSetImpl<BasicBlock *> &BlocksToScale) {
202 assert(BFI && "Expected analysis to be available");
203 // Use 128 bits APInt to avoid overflow.
204 APInt NewFreq(128, Freq);
205 APInt OldFreq(128, BFI->getBlockFreq(ReferenceBB).getFrequency());
206 APInt BBFreq(128, 0);
207 for (auto *BB : BlocksToScale) {
208 BBFreq = BFI->getBlockFreq(BB).getFrequency();
209 // Multiply first by NewFreq and then divide by OldFreq
210 // to minimize loss of precision.
212 // udiv is an expensive operation in the general case. If this ends up being
213 // a hot spot, one of the options proposed in
214 // https://reviews.llvm.org/D28535#650071 could be used to avoid this.
215 BBFreq = BBFreq.udiv(OldFreq);
216 BFI->setBlockFreq(BB, BBFreq.getLimitedValue());
218 BFI->setBlockFreq(ReferenceBB, Freq);
221 /// Pop up a ghostview window with the current block frequency propagation
222 /// rendered using dot.
223 void BlockFrequencyInfo::view() const {
224 ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
227 const Function *BlockFrequencyInfo::getFunction() const {
228 return BFI ? BFI->getFunction() : nullptr;
231 const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {
232 return BFI ? &BFI->getBPI() : nullptr;
235 raw_ostream &BlockFrequencyInfo::
236 printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
237 return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
241 BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
242 const BasicBlock *BB) const {
243 return BFI ? BFI->printBlockFreq(OS, BB) : OS;
246 uint64_t BlockFrequencyInfo::getEntryFreq() const {
247 return BFI ? BFI->getEntryFreq() : 0;
250 void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
252 void BlockFrequencyInfo::print(raw_ostream &OS) const {
258 INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
259 "Block Frequency Analysis", true, true)
260 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
261 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
262 INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
263 "Block Frequency Analysis", true, true)
265 char BlockFrequencyInfoWrapperPass::ID = 0;
268 BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
270 initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
273 BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {}
275 void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
276 const Module *) const {
280 void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
281 AU.addRequired<BranchProbabilityInfoWrapperPass>();
282 AU.addRequired<LoopInfoWrapperPass>();
283 AU.setPreservesAll();
286 void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
288 bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
289 BranchProbabilityInfo &BPI =
290 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
291 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
292 BFI.calculate(F, BPI, LI);
296 AnalysisKey BlockFrequencyAnalysis::Key;
297 BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
298 FunctionAnalysisManager &AM) {
299 BlockFrequencyInfo BFI;
300 BFI.calculate(F, AM.getResult<BranchProbabilityAnalysis>(F),
301 AM.getResult<LoopAnalysis>(F));
306 BlockFrequencyPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
307 OS << "Printing analysis results of BFI for function "
308 << "'" << F.getName() << "':"
310 AM.getResult<BlockFrequencyAnalysis>(F).print(OS);
311 return PreservedAnalyses::all();