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 "AnalysisOptions.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/iterator.h"
17#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
18#include "llvm/Analysis/BranchProbabilityInfo.h"
19#include "llvm/Analysis/CycleAnalysis.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/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
35StringRef llvm::getViewBlockFreqFuncName(const LLVMContext &C) {
36 return getAnalysisOptions(C).view_bfi_func_name;
37}
38unsigned llvm::getViewHotFreqPercent(const LLVMContext &C) {
39 return getAnalysisOptions(C).view_hot_freq_percent;
40}
41PGOViewCountsType llvm::getPGOViewCounts(const LLVMContext &C) {
42 return getAnalysisOptions(C).pgo_view_counts;
43}
44StringRef llvm::getPrintBFIFuncName(const LLVMContext &C) {
45 return getAnalysisOptions(C).print_bfi_func_name;
46}
47
48namespace llvm {
49
50static GVDAGType getGVDT(const LLVMContext &C) {
51 if (getPGOViewCounts(C) == PGOViewCountsType::Graph)
52 return GVDAGType::Count;
53 return getAnalysisOptions(C).view_block_freq_propagation_dags;
54}
55
56template <>
57struct GraphTraits<BlockFrequencyInfo *> {
58 using NodeRef = const BasicBlock *;
59 using ChildIteratorType = const_succ_iterator;
60 using nodes_iterator = pointer_iterator<Function::const_iterator>;
61
62 static NodeRef getEntryNode(const BlockFrequencyInfo *G) {
63 return &G->getFunction()->front();
64 }
65
66 static ChildIteratorType child_begin(const NodeRef N) {
67 return succ_begin(BB: N);
68 }
69
70 static ChildIteratorType child_end(const NodeRef N) { return succ_end(BB: N); }
71
72 static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
73 return nodes_iterator(G->getFunction()->begin());
74 }
75
76 static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
77 return nodes_iterator(G->getFunction()->end());
78 }
79};
80
81using BFIDOTGTraitsBase =
82 BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>;
83
84template <>
85struct DOTGraphTraits<BlockFrequencyInfo *> : public BFIDOTGTraitsBase {
86 explicit DOTGraphTraits(bool isSimple = false)
87 : BFIDOTGTraitsBase(isSimple) {}
88
89 std::string getNodeLabel(const BasicBlock *Node,
90 const BlockFrequencyInfo *Graph) {
91
92 return BFIDOTGTraitsBase::getNodeLabel(Node, Graph,
93 GType: getGVDT(C: Node->getContext()));
94 }
95
96 std::string getNodeAttributes(const BasicBlock *Node,
97 const BlockFrequencyInfo *Graph) {
98 return BFIDOTGTraitsBase::getNodeAttributes(
99 Node, Graph, HotPercentThreshold: getViewHotFreqPercent(C: Node->getContext()));
100 }
101
102 std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
103 const BlockFrequencyInfo *BFI) {
104 return BFIDOTGTraitsBase::getEdgeAttributes(
105 Node, EI, BFI, BPI: BFI->getBPI(),
106 HotPercentThreshold: getViewHotFreqPercent(C: Node->getContext()));
107 }
108};
109
110} // end namespace llvm
111
112BlockFrequencyInfo::BlockFrequencyInfo() = default;
113
114BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
115 const BranchProbabilityInfo &BPI,
116 const CycleInfo &CI) {
117 calculate(F, BPI, CI);
118}
119
120BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
121 : BFI(std::move(Arg.BFI)) {}
122
123BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
124 releaseMemory();
125 BFI = std::move(RHS.BFI);
126 return *this;
127}
128
129// Explicitly define the default constructor otherwise it would be implicitly
130// defined at the first ODR-use which is the BFI member in the
131// LazyBlockFrequencyInfo header. The dtor needs the BlockFrequencyInfoImpl
132// template instantiated which is not available in the header.
133BlockFrequencyInfo::~BlockFrequencyInfo() = default;
134
135bool BlockFrequencyInfo::invalidate(Function &F, const PreservedAnalyses &PA,
136 FunctionAnalysisManager::Invalidator &) {
137 // Check whether the analysis, all analyses on functions, or the function's
138 // CFG have been preserved.
139 auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
140 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
141 PAC.preservedSet<CFGAnalyses>());
142}
143
144void BlockFrequencyInfo::calculate(const Function &F,
145 const BranchProbabilityInfo &BPI,
146 const CycleInfo &CI) {
147 if (!BFI)
148 BFI.reset(p: new ImplType);
149 BFI->calculate(F, BPI, CI);
150 const AnalysisOptions &Opts = getAnalysisOptions(F);
151 if (Opts.view_block_freq_propagation_dags != GVDAGType::None &&
152 (Opts.view_bfi_func_name.empty() ||
153 F.getName() == Opts.view_bfi_func_name)) {
154 view();
155 }
156 if (Opts.print_bfi && (Opts.print_bfi_func_name.empty() ||
157 F.getName() == Opts.print_bfi_func_name)) {
158 print(OS&: dbgs());
159 }
160}
161
162BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
163 return BFI ? BFI->getBlockFreq(BB) : BlockFrequency(0);
164}
165
166std::optional<uint64_t>
167BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
168 if (!BFI)
169 return std::nullopt;
170
171 return BFI->getBlockProfileCount(F: *getFunction(), BB);
172}
173
174std::optional<uint64_t>
175BlockFrequencyInfo::getProfileCountFromFreq(BlockFrequency Freq) const {
176 if (!BFI)
177 return std::nullopt;
178 return BFI->getProfileCountFromFreq(F: *getFunction(), Freq);
179}
180
181bool BlockFrequencyInfo::isIrrLoopHeader(const BasicBlock *BB) {
182 assert(BFI && "Expected analysis to be available");
183 return BFI->isIrrLoopHeader(BB);
184}
185
186void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB,
187 BlockFrequency Freq) {
188 assert(BFI && "Expected analysis to be available");
189 BFI->setBlockFreq(BB, Freq);
190}
191
192/// Return min(BBFreq * NewFreq / OldFreq, UINT64_MAX). Multiplies before
193/// dividing, to minimize loss of precision.
194static uint64_t scaleFrequency(uint64_t BBFreq, uint64_t NewFreq,
195 uint64_t OldFreq) {
196 assert(OldFreq != 0 && "Divide by zero?");
197 // clang-cl defines __SIZEOF_INT128__, but MSVC's runtime does not provide
198 // the 128-bit division helper (__udivti3).
199#if defined(__SIZEOF_INT128__) && !defined(_MSC_VER)
200 __uint128_t Scaled = __uint128_t(BBFreq) * NewFreq / OldFreq;
201 return std::min<__uint128_t>(a: Scaled, UINT64_MAX);
202#else
203 return (APInt(128, BBFreq) * NewFreq).udiv(OldFreq).getLimitedValue();
204#endif
205}
206
207void BlockFrequencyInfo::setBlockFreqAndScale(
208 const BasicBlock *ReferenceBB, BlockFrequency Freq,
209 SmallPtrSetImpl<BasicBlock *> &BlocksToScale) {
210 assert(BFI && "Expected analysis to be available");
211 uint64_t NewFreq = Freq.getFrequency();
212 uint64_t OldFreq = BFI->getBlockFreq(BB: ReferenceBB).getFrequency();
213 for (auto *BB : BlocksToScale) {
214 uint64_t BBFreq = BFI->getBlockFreq(BB).getFrequency();
215 BFI->setBlockFreq(BB,
216 Freq: BlockFrequency(scaleFrequency(BBFreq, NewFreq, OldFreq)));
217 }
218 BFI->setBlockFreq(BB: ReferenceBB, Freq);
219}
220
221/// Pop up a ghostview window with the current block frequency propagation
222/// rendered using dot.
223void BlockFrequencyInfo::view(StringRef title) const {
224 ViewGraph(G: const_cast<BlockFrequencyInfo *>(this), Name: title);
225}
226
227const Function *BlockFrequencyInfo::getFunction() const {
228 return BFI ? BFI->getFunction() : nullptr;
229}
230
231const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {
232 return BFI ? &BFI->getBPI() : nullptr;
233}
234
235BlockFrequency BlockFrequencyInfo::getEntryFreq() const {
236 return BFI ? BFI->getEntryFreq() : BlockFrequency(0);
237}
238
239void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
240
241void BlockFrequencyInfo::print(raw_ostream &OS) const {
242 if (BFI)
243 BFI->print(OS);
244}
245
246void BlockFrequencyInfo::verifyMatch(BlockFrequencyInfo &Other) const {
247 if (BFI)
248 BFI->verifyMatch(Other&: *Other.BFI);
249}
250
251Printable llvm::printBlockFreq(const BlockFrequencyInfo &BFI,
252 BlockFrequency Freq) {
253 return Printable([&BFI, Freq](raw_ostream &OS) {
254 printRelativeBlockFreq(OS, EntryFreq: BFI.getEntryFreq(), Freq);
255 });
256}
257
258Printable llvm::printBlockFreq(const BlockFrequencyInfo &BFI,
259 const BasicBlock &BB) {
260 return printBlockFreq(BFI, Freq: BFI.getBlockFreq(BB: &BB));
261}
262
263INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
264 "Block Frequency Analysis", true, true)
265INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
266INITIALIZE_PASS_DEPENDENCY(CycleInfoWrapperPass)
267INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
268 "Block Frequency Analysis", true, true)
269
270char BlockFrequencyInfoWrapperPass::ID = 0;
271
272BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
273 : FunctionPass(ID) {}
274
275BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() = default;
276
277void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
278 const Module *) const {
279 BFI.print(OS);
280}
281
282void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
283 AU.addRequired<BranchProbabilityInfoWrapperPass>();
284 AU.addRequired<CycleInfoWrapperPass>();
285 AU.setPreservesAll();
286}
287
288void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
289
290bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
291 BranchProbabilityInfo &BPI =
292 getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
293 CycleInfo &LI = getAnalysis<CycleInfoWrapperPass>().getResult();
294 BFI.calculate(F, BPI, CI: LI);
295 return false;
296}
297
298AnalysisKey BlockFrequencyAnalysis::Key;
299BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
300 FunctionAnalysisManager &AM) {
301 auto &BP = AM.getResult<BranchProbabilityAnalysis>(IR&: F);
302 auto &LI = AM.getResult<CycleAnalysis>(IR&: F);
303 BlockFrequencyInfo BFI;
304 BFI.calculate(F, BPI: BP, CI: LI);
305 return BFI;
306}
307
308PreservedAnalyses
309BlockFrequencyPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
310 OS << "Printing analysis results of BFI for function "
311 << "'" << F.getName() << "':"
312 << "\n";
313 AM.getResult<BlockFrequencyAnalysis>(IR&: F).print(OS);
314 return PreservedAnalyses::all();
315}
316