1//===-------- MIRSampleProfile.cpp: MIRSampleFDO (For FSAFDO) -------------===//
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// This file provides the implementation of the MIRSampleProfile loader, mainly
10// for flow sensitive SampleFDO.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/CodeGen/MIRSampleProfile.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/Analysis/BlockFrequencyInfo.h"
18#include "llvm/Analysis/BlockFrequencyInfoImpl.h"
19#include "llvm/CodeGen/MIRFSDiscriminatorOptions.h"
20#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
21#include "llvm/CodeGen/MachineCycleAnalysis.h"
22#include "llvm/CodeGen/MachineDominators.h"
23#include "llvm/CodeGen/MachineInstr.h"
24#include "llvm/CodeGen/MachineLoopInfo.h"
25#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
26#include "llvm/CodeGen/MachinePostDominators.h"
27#include "llvm/CodeGen/Passes.h"
28#include "llvm/IR/Function.h"
29#include "llvm/IR/PseudoProbe.h"
30#include "llvm/InitializePasses.h"
31#include "llvm/Support/CommandLine.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/Support/VirtualFileSystem.h"
34#include "llvm/Support/raw_ostream.h"
35#include "llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h"
36#include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"
37#include <optional>
38
39using namespace llvm;
40using namespace sampleprof;
41using namespace llvm::sampleprofutil;
42
43#define DEBUG_TYPE "fs-profile-loader"
44
45static cl::opt<bool> ShowFSBranchProb(
46 "show-fs-branchprob", cl::Hidden, cl::init(Val: false),
47 cl::desc("Print setting flow sensitive branch probabilities"));
48static cl::opt<unsigned> FSProfileDebugProbDiffThreshold(
49 "fs-profile-debug-prob-diff-threshold", cl::init(Val: 10),
50 cl::desc(
51 "Only show debug message if the branch probability is greater than "
52 "this value (in percentage)."));
53
54static cl::opt<unsigned> FSProfileDebugBWThreshold(
55 "fs-profile-debug-bw-threshold", cl::init(Val: 10000),
56 cl::desc("Only show debug message if the source branch weight is greater "
57 " than this value."));
58
59static cl::opt<bool> ViewBFIBefore("fs-viewbfi-before", cl::Hidden,
60 cl::init(Val: false),
61 cl::desc("View BFI before MIR loader"));
62static cl::opt<bool> ViewBFIAfter("fs-viewbfi-after", cl::Hidden,
63 cl::init(Val: false),
64 cl::desc("View BFI after MIR loader"));
65
66char MIRProfileLoaderPass::ID = 0;
67
68INITIALIZE_PASS_BEGIN(MIRProfileLoaderPass, DEBUG_TYPE,
69 "Load MIR Sample Profile",
70 /* cfg = */ false, /* is_analysis = */ false)
71INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
72INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
73INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
74INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
75INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
76INITIALIZE_PASS_END(MIRProfileLoaderPass, DEBUG_TYPE, "Load MIR Sample Profile",
77 /* cfg = */ false, /* is_analysis = */ false)
78
79char &llvm::MIRProfileLoaderPassID = MIRProfileLoaderPass::ID;
80
81FunctionPass *
82llvm::createMIRProfileLoaderPass(std::string File, std::string RemappingFile,
83 FSDiscriminatorPass P,
84 IntrusiveRefCntPtr<vfs::FileSystem> FS) {
85 return new MIRProfileLoaderPass(File, RemappingFile, P, std::move(FS));
86}
87
88namespace llvm {
89
90// Internal option used to control BFI display only after MBP pass.
91// Defined in CodeGen/MachineBlockFrequencyInfo.cpp:
92// -view-block-layout-with-bfi={none | fraction | integer | count}
93extern cl::opt<GVDAGType> ViewBlockLayoutWithBFI;
94
95std::optional<PseudoProbe> extractProbe(const MachineInstr &MI) {
96 if (MI.isPseudoProbe()) {
97 PseudoProbe Probe;
98 Probe.Id = MI.getOperand(i: 1).getImm();
99 Probe.Type = MI.getOperand(i: 2).getImm();
100 Probe.Attr = MI.getOperand(i: 3).getImm();
101 Probe.Factor = 1;
102 DILocation *DebugLoc = MI.getDebugLoc();
103 Probe.Discriminator = DebugLoc ? DebugLoc->getDiscriminator() : 0;
104 return Probe;
105 }
106
107 // Ignore callsite probes since they do not have FS discriminators.
108 return std::nullopt;
109}
110
111namespace afdo_detail {
112template <> struct IRTraits<MachineBasicBlock> {
113 using InstructionT = MachineInstr;
114 using BasicBlockT = MachineBasicBlock;
115 using FunctionT = MachineFunction;
116 using BlockFrequencyInfoT = MachineBlockFrequencyInfo;
117 using LoopT = MachineLoop;
118 using LoopInfoPtrT = MachineLoopInfo *;
119 using DominatorTreePtrT = MachineDominatorTree *;
120 using PostDominatorTreePtrT = MachinePostDominatorTree *;
121 using PostDominatorTreeT = MachinePostDominatorTree;
122 using OptRemarkEmitterT = MachineOptimizationRemarkEmitter;
123 using OptRemarkAnalysisT = MachineOptimizationRemarkAnalysis;
124 using PredRangeT =
125 iterator_range<SmallVectorImpl<MachineBasicBlock *>::iterator>;
126 using SuccRangeT =
127 iterator_range<SmallVectorImpl<MachineBasicBlock *>::iterator>;
128 static Function &getFunction(MachineFunction &F) { return F.getFunction(); }
129 static const MachineBasicBlock *getEntryBB(const MachineFunction *F) {
130 return GraphTraits<const MachineFunction *>::getEntryNode(F);
131 }
132 static PredRangeT getPredecessors(MachineBasicBlock *BB) {
133 return BB->predecessors();
134 }
135 static SuccRangeT getSuccessors(MachineBasicBlock *BB) {
136 return BB->successors();
137 }
138};
139} // namespace afdo_detail
140
141class MIRProfileLoader final
142 : public SampleProfileLoaderBaseImpl<MachineFunction> {
143public:
144 void setInitVals(MachineDominatorTree *MDT, MachinePostDominatorTree *MPDT,
145 MachineLoopInfo *MLI, MachineBlockFrequencyInfo *MBFI,
146 MachineOptimizationRemarkEmitter *MORE) {
147 DT = MDT;
148 PDT = MPDT;
149 LI = MLI;
150 BFI = MBFI;
151 ORE = MORE;
152 }
153 void setFSPass(FSDiscriminatorPass Pass) {
154 P = Pass;
155 LowBit = getFSPassBitBegin(P);
156 HighBit = getFSPassBitEnd(P);
157 assert(LowBit < HighBit && "HighBit needs to be greater than Lowbit");
158 }
159
160 MIRProfileLoader(StringRef Name, StringRef RemapName,
161 IntrusiveRefCntPtr<vfs::FileSystem> FS)
162 : SampleProfileLoaderBaseImpl(std::string(Name), std::string(RemapName),
163 std::move(FS)) {}
164
165 void setBranchProbs(MachineFunction &F);
166 bool runOnFunction(MachineFunction &F);
167 bool doInitialization(Module &M);
168 bool isValid() const { return ProfileIsValid; }
169
170protected:
171 friend class SampleCoverageTracker;
172
173 /// Hold the information of the basic block frequency.
174 MachineBlockFrequencyInfo *BFI;
175
176 /// PassNum is the sequence number this pass is called, start from 1.
177 FSDiscriminatorPass P;
178
179 // LowBit in the FS discriminator used by this instance. Note the number is
180 // 0-based. Base discrimnator use bit 0 to bit 11.
181 unsigned LowBit;
182 // HighwBit in the FS discriminator used by this instance. Note the number
183 // is 0-based.
184 unsigned HighBit;
185
186 bool ProfileIsValid = true;
187 ErrorOr<uint64_t> getInstWeight(const MachineInstr &MI) override {
188 if (FunctionSamples::ProfileIsProbeBased)
189 return getProbeWeight(Inst: MI);
190 if (ImprovedFSDiscriminator && MI.isMetaInstruction())
191 return std::error_code();
192 return getInstWeightImpl(Inst: MI);
193 }
194};
195
196template <>
197void SampleProfileLoaderBaseImpl<MachineFunction>::computeDominanceAndLoopInfo(
198 MachineFunction &F) {}
199
200void MIRProfileLoader::setBranchProbs(MachineFunction &F) {
201 LLVM_DEBUG(dbgs() << "\nPropagation complete. Setting branch probs\n");
202 for (auto &BI : F) {
203 MachineBasicBlock *BB = &BI;
204 if (BB->succ_size() < 2)
205 continue;
206 const MachineBasicBlock *EC = EquivalenceClass[BB];
207 uint64_t BBWeight = BlockWeights[EC];
208 uint64_t SumEdgeWeight = 0;
209 for (MachineBasicBlock *Succ : BB->successors()) {
210 Edge E = std::make_pair(x&: BB, y&: Succ);
211 SumEdgeWeight += EdgeWeights[E];
212 }
213
214 if (BBWeight != SumEdgeWeight) {
215 LLVM_DEBUG(dbgs() << "BBweight is not equal to SumEdgeWeight: BBWWeight="
216 << BBWeight << " SumEdgeWeight= " << SumEdgeWeight
217 << "\n");
218 BBWeight = SumEdgeWeight;
219 }
220 if (BBWeight == 0) {
221 LLVM_DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
222 continue;
223 }
224
225#ifndef NDEBUG
226 uint64_t BBWeightOrig = BBWeight;
227#endif
228 uint32_t MaxWeight = std::numeric_limits<uint32_t>::max();
229 uint32_t Factor = 1;
230 if (BBWeight > MaxWeight) {
231 Factor = BBWeight / MaxWeight + 1;
232 BBWeight /= Factor;
233 LLVM_DEBUG(dbgs() << "Scaling weights by " << Factor << "\n");
234 }
235
236 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(),
237 SE = BB->succ_end();
238 SI != SE; ++SI) {
239 MachineBasicBlock *Succ = *SI;
240 Edge E = std::make_pair(x&: BB, y&: Succ);
241 uint64_t EdgeWeight = EdgeWeights[E];
242 EdgeWeight /= Factor;
243
244 assert(BBWeight >= EdgeWeight &&
245 "BBweight is larger than EdgeWeight -- should not happen.\n");
246
247 BranchProbability OldProb = BB->getSuccProbability(Succ: SI);
248 BranchProbability NewProb(EdgeWeight, BBWeight);
249 if (OldProb == NewProb)
250 continue;
251 BB->setSuccProbability(I: SI, Prob: NewProb);
252#ifndef NDEBUG
253 if (!ShowFSBranchProb)
254 continue;
255 bool Show = false;
256 BranchProbability Diff;
257 if (OldProb > NewProb)
258 Diff = OldProb - NewProb;
259 else
260 Diff = NewProb - OldProb;
261 Show = (Diff >= BranchProbability(FSProfileDebugProbDiffThreshold, 100));
262 Show &= (BBWeightOrig >= FSProfileDebugBWThreshold);
263
264 auto DIL = BB->findBranchDebugLoc();
265 auto SuccDIL = Succ->findBranchDebugLoc();
266 if (Show) {
267 dbgs() << "Set branch fs prob: MBB (" << BB->getNumber() << " -> "
268 << Succ->getNumber() << "): ";
269 if (DIL)
270 dbgs() << DIL->getFilename() << ":" << DIL->getLine() << ":"
271 << DIL->getColumn();
272 if (SuccDIL)
273 dbgs() << "-->" << SuccDIL->getFilename() << ":" << SuccDIL->getLine()
274 << ":" << SuccDIL->getColumn();
275 dbgs() << " W=" << BBWeightOrig << " " << OldProb << " --> " << NewProb
276 << "\n";
277 }
278#endif
279 }
280 }
281}
282
283bool MIRProfileLoader::doInitialization(Module &M) {
284 auto &Ctx = M.getContext();
285
286 auto ReaderOrErr = sampleprof::SampleProfileReader::create(
287 Filename, C&: Ctx, FS&: *FS, P, RemapFilename: RemappingFilename);
288 if (std::error_code EC = ReaderOrErr.getError()) {
289 std::string Msg = "Could not open profile: " + EC.message();
290 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(Filename, Msg));
291 return false;
292 }
293
294 Reader = std::move(ReaderOrErr.get());
295 Reader->setModule(&M);
296 ProfileIsValid = (Reader->read() == sampleprof_error::success);
297
298 // Load pseudo probe descriptors for probe-based function samples.
299 if (Reader->profileIsProbeBased()) {
300 ProbeManager = std::make_unique<PseudoProbeManager>(args&: M);
301 if (!ProbeManager->moduleIsProbed(M)) {
302 return false;
303 }
304 }
305
306 return true;
307}
308
309bool MIRProfileLoader::runOnFunction(MachineFunction &MF) {
310 // Do not load non-FS profiles. A line or probe can get a zero-valued
311 // discriminator at certain pass which could result in accidentally loading
312 // the corresponding base counter in the non-FS profile, while a non-zero
313 // discriminator would end up getting zero samples. This could in turn undo
314 // the sample distribution effort done by previous BFI maintenance and the
315 // probe distribution factor work for pseudo probes.
316 if (!Reader->profileIsFS())
317 return false;
318
319 Function &Func = MF.getFunction();
320 clearFunctionData(ResetDT: false);
321 Samples = Reader->getSamplesFor(F: Func);
322 if (!Samples || Samples->empty())
323 return false;
324
325 if (FunctionSamples::ProfileIsProbeBased) {
326 if (!ProbeManager->profileIsValid(F: MF.getFunction(), Samples: *Samples))
327 return false;
328 } else {
329 if (getFunctionLoc(F&: MF) == 0)
330 return false;
331 }
332
333 DenseSet<GlobalValue::GUID> InlinedGUIDs;
334 bool Changed = computeAndPropagateWeights(F&: MF, InlinedGUIDs);
335
336 // Set the new BPI, BFI.
337 setBranchProbs(MF);
338
339 return Changed;
340}
341
342} // namespace llvm
343
344MIRProfileLoaderPass::MIRProfileLoaderPass(
345 std::string FileName, std::string RemappingFileName, FSDiscriminatorPass P,
346 IntrusiveRefCntPtr<vfs::FileSystem> FS)
347 : MachineFunctionPass(ID), ProfileFileName(FileName), P(P) {
348 LowBit = getFSPassBitBegin(P);
349 HighBit = getFSPassBitEnd(P);
350
351 auto VFS = FS ? std::move(FS) : vfs::getRealFileSystem();
352 MIRSampleLoader = std::make_unique<MIRProfileLoader>(
353 args&: FileName, args&: RemappingFileName, args: std::move(VFS));
354 assert(LowBit < HighBit && "HighBit needs to be greater than Lowbit");
355}
356
357bool MIRProfileLoaderPass::runOnMachineFunction(MachineFunction &MF) {
358 if (!MIRSampleLoader->isValid())
359 return false;
360
361 LLVM_DEBUG(dbgs() << "MIRProfileLoader pass working on Func: "
362 << MF.getFunction().getName() << "\n");
363 MBFI = &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
364 auto *MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
365 auto *MPDT =
366 &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
367
368 MF.RenumberBlocks();
369
370 MIRSampleLoader->setInitVals(
371 MDT, MPDT, MLI: &getAnalysis<MachineLoopInfoWrapperPass>().getLI(), MBFI,
372 MORE: &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE());
373
374 StringRef ViewFuncName =
375 getViewBlockFreqFuncName(C: MF.getFunction().getContext());
376 if (ViewBFIBefore && ViewBlockLayoutWithBFI != GVDAGType::None &&
377 (ViewFuncName.empty() || MF.getFunction().getName() == ViewFuncName)) {
378 MBFI->view(Name: "MIR_Prof_loader_b." + MF.getName(), isSimple: false);
379 }
380
381 bool Changed = MIRSampleLoader->runOnFunction(MF);
382 if (Changed) {
383 MachineCycleInfo MCI;
384 MCI.compute(F&: MF);
385 MBFI->calculate(F: MF, MBPI: *MBFI->getMBPI(), MCI);
386 }
387
388 if (ViewBFIAfter && ViewBlockLayoutWithBFI != GVDAGType::None &&
389 (ViewFuncName.empty() || MF.getFunction().getName() == ViewFuncName)) {
390 MBFI->view(Name: "MIR_prof_loader_a." + MF.getName(), isSimple: false);
391 }
392
393 return Changed;
394}
395
396bool MIRProfileLoaderPass::doInitialization(Module &M) {
397 LLVM_DEBUG(dbgs() << "MIRProfileLoader pass working on Module " << M.getName()
398 << "\n");
399
400 MIRSampleLoader->setFSPass(P);
401 return MIRSampleLoader->doInitialization(M);
402}
403
404void MIRProfileLoaderPass::getAnalysisUsage(AnalysisUsage &AU) const {
405 AU.setPreservesAll();
406 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
407 AU.addRequired<MachineDominatorTreeWrapperPass>();
408 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
409 AU.addRequiredTransitive<MachineLoopInfoWrapperPass>();
410 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
411 MachineFunctionPass::getAnalysisUsage(AU);
412}
413