1//===- llvm/CodeGen/BasicBlockMatchingAndInference.cpp ----------*- C++ -*-===//
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// In Propeller's profile, we have already read the hash values of basic blocks,
10// as well as the weights of basic blocks and edges in the CFG. In this file,
11// we first match the basic blocks in the profile with those in the current
12// MachineFunction using the basic block hash, thereby obtaining the weights of
13// some basic blocks and edges. Subsequently, we infer the weights of all basic
14// blocks using an inference algorithm.
15//
16// TODO: Integrate part of the code in this file with BOLT's implementation into
17// the LLVM infrastructure, enabling both BOLT and Propeller to reuse it.
18//
19//===----------------------------------------------------------------------===//
20
21#include "llvm/CodeGen/BasicBlockMatchingAndInference.h"
22#include "CodeGenOptions.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/DenseSet.h"
25#include "llvm/Analysis/ProfileSummaryInfo.h"
26#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
27#include "llvm/CodeGen/MachineBlockHashInfo.h"
28#include "llvm/CodeGen/Passes.h"
29#include "llvm/IR/DebugInfoMetadata.h"
30#include "llvm/IR/DiagnosticInfo.h"
31#include "llvm/IR/LLVMContext.h"
32#include "llvm/IR/Module.h"
33#include "llvm/InitializePasses.h"
34#include "llvm/ProfileData/SampleProf.h"
35#include "llvm/ProfileData/SampleProfReader.h"
36#include "llvm/Support/Debug.h"
37#include "llvm/Support/MathExtras.h"
38
39using namespace llvm;
40
41#define DEBUG_TYPE "machine-block-match-infer"
42
43/// The object is used to identify and match basic blocks given their hashes.
44class StaleMatcher {
45public:
46 /// Initialize stale matcher.
47 void init(const std::vector<MachineBasicBlock *> &Blocks,
48 const std::vector<BlendedBlockHash> &Hashes) {
49 assert(Blocks.size() == Hashes.size() &&
50 "incorrect matcher initialization");
51 for (size_t I = 0; I < Blocks.size(); I++) {
52 MachineBasicBlock *Block = Blocks[I];
53 uint16_t OpHash = Hashes[I].getOpcodeHash();
54 OpHashToBlocks[OpHash].push_back(x: std::make_pair(x: Hashes[I], y&: Block));
55 }
56 }
57
58 /// Find the most similar block for a given hash.
59 MachineBasicBlock *matchBlock(BlendedBlockHash BlendedHash) const {
60 auto BlockIt = OpHashToBlocks.find(Val: BlendedHash.getOpcodeHash());
61 if (BlockIt == OpHashToBlocks.end()) {
62 return nullptr;
63 }
64 MachineBasicBlock *BestBlock = nullptr;
65 uint64_t BestDist = std::numeric_limits<uint64_t>::max();
66 for (auto It : BlockIt->second) {
67 MachineBasicBlock *Block = It.second;
68 BlendedBlockHash Hash = It.first;
69 uint64_t Dist = Hash.distance(BBH: BlendedHash);
70 if (BestBlock == nullptr || Dist < BestDist) {
71 BestDist = Dist;
72 BestBlock = Block;
73 }
74 }
75 return BestBlock;
76 }
77
78private:
79 using HashBlockPairType = std::pair<BlendedBlockHash, MachineBasicBlock *>;
80 DenseMap<uint16_t, std::vector<HashBlockPairType>> OpHashToBlocks;
81};
82
83INITIALIZE_PASS_BEGIN(BasicBlockMatchingAndInference,
84 "machine-block-match-infer",
85 "Machine Block Matching and Inference Analysis", true,
86 true)
87INITIALIZE_PASS_DEPENDENCY(MachineBlockHashInfo)
88INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReaderWrapperPass)
89INITIALIZE_PASS_END(BasicBlockMatchingAndInference, "machine-block-match-infer",
90 "Machine Block Matching and Inference Analysis", true, true)
91
92char BasicBlockMatchingAndInference::ID = 0;
93
94namespace {
95/// Looks up the sampled weights of the instructions of one machine function in
96/// a line-based sample profile. This is the lookup part of
97/// SampleProfileLoaderBaseImpl without its weight propagation, remarks and
98/// coverage tracking, which are not needed to supplement the Propeller profile.
99class FunctionSamplesQuery {
100public:
101 FunctionSamplesQuery(const FunctionSamples &Samples,
102 SampleProfileReaderItaniumRemapper *Remapper)
103 : Samples(Samples), Remapper(Remapper) {}
104
105 /// Returns the weight of \p MI, or an error if it has no samples.
106 ErrorOr<uint64_t> getInstWeight(const MachineInstr &MI) {
107 const DILocation *DIL = MI.getDebugLoc();
108 if (!DIL || DIL->getLine() == 0)
109 return std::error_code();
110 // Find the samples of the inlined instance MI comes from.
111 auto [It, Inserted] = InlinedSamplesCache.try_emplace(Key: DIL, Args: nullptr);
112 if (Inserted)
113 It->second = Samples.findFunctionSamples(DIL, Remapper);
114 if (!It->second)
115 return std::error_code();
116 uint32_t Discriminator = EnableFSDiscriminator
117 ? DIL->getDiscriminator()
118 : DIL->getBaseDiscriminator();
119 return It->second->findSamplesAt(LineOffset: FunctionSamples::getOffset(DIL),
120 Discriminator);
121 }
122
123 /// Returns the maximum weight among the non-meta instructions of \p MBB, or
124 /// an error if none of them has samples.
125 ErrorOr<uint64_t> getBlockWeight(const MachineBasicBlock &MBB) {
126 uint64_t Max = 0;
127 bool HasWeight = false;
128 for (const MachineInstr &MI : MBB) {
129 if (MI.isMetaInstruction())
130 continue;
131 if (ErrorOr<uint64_t> W = getInstWeight(MI)) {
132 Max = std::max(a: Max, b: *W);
133 HasWeight = true;
134 }
135 }
136 if (!HasWeight)
137 return std::error_code();
138 return Max;
139 }
140
141private:
142 const FunctionSamples &Samples;
143 SampleProfileReaderItaniumRemapper *Remapper;
144 // Samples of the inlined instance each location comes from.
145 DenseMap<const DILocation *, const FunctionSamples *> InlinedSamplesCache;
146};
147} // namespace
148
149BasicBlockMatchingAndInference::BasicBlockMatchingAndInference()
150 : MachineFunctionPass(ID) {}
151
152BasicBlockMatchingAndInference::~BasicBlockMatchingAndInference() = default;
153
154void BasicBlockMatchingAndInference::getAnalysisUsage(AnalysisUsage &AU) const {
155 AU.addRequired<MachineBlockHashInfo>();
156 AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();
157 AU.setPreservesAll();
158 MachineFunctionPass::getAnalysisUsage(AU);
159}
160
161std::optional<BasicBlockMatchingAndInference::WeightInfo>
162BasicBlockMatchingAndInference::getWeightInfo(StringRef FuncName) const {
163 auto It = ProgramWeightInfo.find(Key: FuncName);
164 if (It == ProgramWeightInfo.end()) {
165 return std::nullopt;
166 }
167 return It->second;
168}
169
170BasicBlockMatchingAndInference::WeightInfo
171BasicBlockMatchingAndInference::initWeightInfoByMatching(MachineFunction &MF) {
172 std::vector<MachineBasicBlock *> Blocks;
173 std::vector<BlendedBlockHash> Hashes;
174 auto BSPR = &getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>();
175 auto MBHI = &getAnalysis<MachineBlockHashInfo>();
176 for (auto &Block : MF) {
177 Blocks.push_back(x: &Block);
178 Hashes.push_back(x: BlendedBlockHash(MBHI->getMBBHash(MBB: Block)));
179 }
180 StaleMatcher Matcher;
181 Matcher.init(Blocks, Hashes);
182 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
183 const CFGProfile *CFG = BSPR->getFunctionCFGProfile(FuncName: MF.getName());
184 if (CFG == nullptr)
185 return MatchWeight;
186 for (auto &BlockCount : CFG->NodeCounts) {
187 if (CFG->BBHashes.count(Val: BlockCount.first.BaseID)) {
188 auto Hash = CFG->BBHashes.lookup(Val: BlockCount.first.BaseID);
189 MachineBasicBlock *Block = Matcher.matchBlock(BlendedHash: BlendedBlockHash(Hash));
190 // When a basic block has clone copies, sum their counts.
191 if (Block != nullptr)
192 MatchWeight.BlockWeights[Block] += BlockCount.second;
193 }
194 }
195 for (auto &PredItem : CFG->EdgeCounts) {
196 auto PredID = PredItem.first.BaseID;
197 if (!CFG->BBHashes.count(Val: PredID))
198 continue;
199 auto PredHash = CFG->BBHashes.lookup(Val: PredID);
200 MachineBasicBlock *PredBlock =
201 Matcher.matchBlock(BlendedHash: BlendedBlockHash(PredHash));
202 if (PredBlock == nullptr)
203 continue;
204 for (auto &SuccItem : PredItem.second) {
205 auto SuccID = SuccItem.first.BaseID;
206 auto EdgeWeight = SuccItem.second;
207 if (CFG->BBHashes.count(Val: SuccID)) {
208 auto SuccHash = CFG->BBHashes.lookup(Val: SuccID);
209 MachineBasicBlock *SuccBlock =
210 Matcher.matchBlock(BlendedHash: BlendedBlockHash(SuccHash));
211 // When an edge has clone copies, sum their counts.
212 if (SuccBlock != nullptr)
213 MatchWeight.EdgeWeights[std::make_pair(x&: PredBlock, y&: SuccBlock)] +=
214 EdgeWeight;
215 }
216 }
217 }
218 return MatchWeight;
219}
220
221BasicBlockMatchingAndInference::WeightInfo
222BasicBlockMatchingAndInference::initWeightInfoByBBID(MachineFunction &MF,
223 const CFGProfile &CFG) {
224 // Match blocks by their full UniqueBBID (including CloneID). If a cloned
225 // block in the profile does not exist in MF (e.g., because its cloning path
226 // was rejected), fall back to the original block so its counts are
227 // attributed to the original block.
228 DenseMap<UniqueBBID, MachineBasicBlock *> BBIDToMBB;
229 for (auto &MBB : MF)
230 BBIDToMBB[*MBB.getBBID()] = &MBB;
231 auto FindMBB = [&](const UniqueBBID &BBID) {
232 if (MachineBasicBlock *MBB = BBIDToMBB.lookup(Val: BBID))
233 return MBB;
234 return BBIDToMBB.lookup(Val: UniqueBBID{.BaseID: BBID.BaseID, .CloneID: 0});
235 };
236
237 // A basic block is matched only if it exists in CFG.NodeCounts and all of its
238 // edges in the CFG profile are also edges in the MIR. The profile may omit
239 // edges without samples, so MIR edges missing from the profile are allowed.
240 // Both ends of a profile edge that is not in the MIR are kept as unknown.
241 DenseSet<const MachineBasicBlock *> MismatchedMBBs;
242 for (const auto &[PredID, Succs] : CFG.EdgeCounts) {
243 MachineBasicBlock *PredMBB = FindMBB(PredID);
244 for (const auto &[SuccID, EdgeCount] : Succs) {
245 MachineBasicBlock *SuccMBB = FindMBB(SuccID);
246 if (PredMBB && SuccMBB && PredMBB->isSuccessor(MBB: SuccMBB))
247 continue;
248 if (PredMBB)
249 MismatchedMBBs.insert(V: PredMBB);
250 if (SuccMBB)
251 MismatchedMBBs.insert(V: SuccMBB);
252 }
253 }
254 DenseSet<const MachineBasicBlock *> ProfiledMBBs;
255 for (const auto &[BBID, BlockCount] : CFG.NodeCounts)
256 if (MachineBasicBlock *MBB = FindMBB(BBID))
257 ProfiledMBBs.insert(V: MBB);
258 DenseSet<const MachineBasicBlock *> MatchedMBBs;
259 for (auto &MBB : MF) {
260 if (!ProfiledMBBs.contains(V: &MBB))
261 continue;
262 if (MismatchedMBBs.contains(V: &MBB))
263 LLVM_DEBUG(dbgs() << MF.getName() << ": bb." << MBB.getNumber()
264 << " has profile edges that are not in the CFG\n");
265 else
266 MatchedMBBs.insert(V: &MBB);
267 }
268
269 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
270 for (const auto &[BBID, BlockCount] : CFG.NodeCounts) {
271 MachineBasicBlock *MBB = FindMBB(BBID);
272 if (MBB && MatchedMBBs.count(V: MBB))
273 MatchWeight.BlockWeights[MBB] += BlockCount;
274 }
275 for (const auto &[PredID, Succs] : CFG.EdgeCounts) {
276 MachineBasicBlock *PredMBB = FindMBB(PredID);
277 if (!PredMBB || !MatchedMBBs.count(V: PredMBB))
278 continue;
279 for (const auto &[SuccID, EdgeCount] : Succs) {
280 MachineBasicBlock *SuccMBB = FindMBB(SuccID);
281 if (!SuccMBB || !MatchedMBBs.count(V: SuccMBB))
282 continue;
283 MatchWeight.EdgeWeights[std::make_pair(x&: PredMBB, y&: SuccMBB)] += EdgeCount;
284 }
285 }
286 return MatchWeight;
287}
288
289void BasicBlockMatchingAndInference::generateWeightInfoByInference(
290 MachineFunction &MF,
291 BasicBlockMatchingAndInference::WeightInfo &MatchWeight) {
292 BlockEdgeMap Successors;
293 for (auto &Block : MF) {
294 for (auto *Succ : Block.successors())
295 Successors[&Block].push_back(Elt: Succ);
296 }
297 SampleProfileInference<MachineFunction> SPI(
298 MF, Successors, MatchWeight.BlockWeights, MatchWeight.EdgeWeights);
299 BlockWeightMap BlockWeights;
300 EdgeWeightMap EdgeWeights;
301 SPI.apply(BlockWeights, EdgeWeights);
302 ProgramWeightInfo.try_emplace(
303 Key: MF.getName(), Args: BasicBlockMatchingAndInference::WeightInfo{
304 .BlockWeights: std::move(BlockWeights), .EdgeWeights: std::move(EdgeWeights)});
305}
306
307bool BasicBlockMatchingAndInference::doInitialization(Module &M) {
308 const CodeGenOptions &Opts = getCodeGenOptions(M);
309 StringRef ProfileFile = Opts.sample_profile_supplement;
310 // Only the weights matched by BBIDs are supplemented.
311 if (ProfileFile.empty() || !Opts.propeller_match_bbid)
312 return false;
313 LLVMContext &Ctx = M.getContext();
314 if (ProfileSummaryInfo(M).hasSampleProfile() ||
315 !Opts.fs_profile_file.empty()) {
316 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(
317 ProfileFile,
318 "Supplemental sample profiles are not supported with SampleFDO",
319 DS_Warning));
320 return false;
321 }
322 auto ReaderOrErr = SampleProfileReader::create(
323 Filename: ProfileFile, C&: Ctx, FS&: Ctx.getVirtualFileSystem(),
324 P: EnableFSDiscriminator ? FSDiscriminatorPass::PassLast
325 : FSDiscriminatorPass::Base,
326 RemapFilename: Opts.sample_profile_supplement_remapping_file);
327 if (std::error_code EC = ReaderOrErr.getError()) {
328 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(
329 ProfileFile,
330 "Could not open supplemental sample profile: " + EC.message()));
331 return false;
332 }
333 std::unique_ptr<SampleProfileReader> Reader = std::move(*ReaderOrErr);
334 Reader->setModule(&M);
335 if (Reader->read() != sampleprof_error::success) {
336 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(
337 ProfileFile, "Could not read supplemental sample profile"));
338 return false;
339 }
340 if (Reader->profileIsProbeBased()) {
341 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(
342 ProfileFile,
343 "Pseudo probe based supplemental sample profiles are not supported",
344 DS_Warning));
345 return false;
346 }
347 if (Reader->profileIsCS()) {
348 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(
349 ProfileFile,
350 "Context-sensitive supplemental sample profiles are not supported",
351 DS_Warning));
352 return false;
353 }
354 if (Reader->profileIsFS() && !EnableFSDiscriminator) {
355 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(
356 ProfileFile,
357 "Flow-sensitive supplemental sample profiles require "
358 "-enable-fs-discriminator",
359 DS_Warning));
360 return false;
361 }
362 if (!Reader->profileIsFS() && EnableFSDiscriminator) {
363 Ctx.diagnose(DI: DiagnosticInfoSampleProfile(
364 ProfileFile,
365 "Non-flow-sensitive supplemental sample profiles are not supported "
366 "with -enable-fs-discriminator",
367 DS_Warning));
368 return false;
369 }
370 SampleReader = std::move(Reader);
371 return false;
372}
373
374void BasicBlockMatchingAndInference::supplementWithSampleProfile(
375 MachineFunction &MF, WeightInfo &MatchWeight) {
376 if (!SampleReader)
377 return;
378 const DISubprogram *Subprogram = MF.getFunction().getSubprogram();
379 if (!Subprogram || Subprogram->getLine() == 0)
380 return;
381 const FunctionSamples *Samples =
382 SampleReader->getSamplesFor(F: MF.getFunction());
383 if (!Samples || Samples->empty())
384 return;
385 FunctionSamplesQuery Query(*Samples, SampleReader->getRemapper());
386
387 // Scale the weights of the supplemental profile so that the entry block
388 // weights of both profiles agree. Skip functions with neither entry-block
389 // samples nor head samples, since their scale is unknown.
390 const MachineBasicBlock &EntryBB = MF.front();
391 uint64_t PropellerEntryWeight =
392 std::max<uint64_t>(a: MatchWeight.BlockWeights.lookup(Val: &EntryBB), b: 1);
393 uint64_t SampleEntryWeight = 0;
394 if (ErrorOr<uint64_t> W = Query.getBlockWeight(MBB: EntryBB))
395 SampleEntryWeight = *W;
396 if (SampleEntryWeight == 0)
397 SampleEntryWeight = Samples->getHeadSamples();
398 if (SampleEntryWeight == 0)
399 return;
400
401 for (const MachineBasicBlock &MBB : MF) {
402 // Only supplement blocks that have no samples in the Propeller profile, so
403 // that code executed in production is not assumed cold prior to inference.
404 // Blocks that already have Propeller samples keep their Propeller weight.
405 if (MatchWeight.BlockWeights.lookup(Val: &MBB) != 0)
406 continue;
407 ErrorOr<uint64_t> SampleWeight = Query.getBlockWeight(MBB);
408 if (!SampleWeight)
409 continue;
410 // Skip weights that round to zero, so that blocks missing from
411 // BlockWeights stay unknown to inference rather than known to be cold.
412 uint64_t Weight =
413 mulDivNearest(X: *SampleWeight, Y: PropellerEntryWeight, Z: SampleEntryWeight);
414 if (Weight != 0)
415 MatchWeight.BlockWeights[&MBB] = Weight;
416 }
417}
418
419bool BasicBlockMatchingAndInference::doFinalization(Module &M) {
420 // The profile is read for each module.
421 SampleReader.reset();
422 return false;
423}
424
425bool BasicBlockMatchingAndInference::runOnMachineFunction(MachineFunction &MF) {
426 if (MF.empty())
427 return false;
428 auto *BSPR = &getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>();
429 const CFGProfile *CFG = BSPR->getFunctionCFGProfile(FuncName: MF.getName());
430 if (CFG == nullptr || (CFG->NodeCounts.empty() && CFG->EdgeCounts.empty()))
431 return false;
432
433 const CodeGenOptions &Opts = getCodeGenOptions(MF);
434 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
435 if (Opts.propeller_match_bbid) {
436 MatchWeight = initWeightInfoByBBID(MF, CFG: *CFG);
437 supplementWithSampleProfile(MF, MatchWeight);
438 } else {
439 MatchWeight = initWeightInfoByMatching(MF);
440 // If the ratio of the number of MBBs in matching to the total number of
441 // MBBs in the function is less than the threshold value, the processing
442 // should be abandoned.
443 if (static_cast<float>(MatchWeight.BlockWeights.size()) / MF.size() <
444 Opts.propeller_infer_threshold) {
445 return false;
446 }
447 }
448 generateWeightInfoByInference(MF, MatchWeight);
449 return false;
450}
451
452MachineFunctionPass *llvm::createBasicBlockMatchingAndInferencePass() {
453 return new BasicBlockMatchingAndInference();
454}
455