LLVM 24.0.0git
BasicBlockMatchingAndInference.cpp
Go to the documentation of this file.
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
22#include "CodeGenOptions.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/DenseSet.h"
28#include "llvm/CodeGen/Passes.h"
31#include "llvm/IR/LLVMContext.h"
32#include "llvm/IR/Module.h"
36#include "llvm/Support/Debug.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.
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(std::make_pair(Hashes[I], Block));
55 }
56 }
57
58 /// Find the most similar block for a given hash.
60 auto BlockIt = OpHashToBlocks.find(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(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 *>;
81};
82
84 "machine-block-match-infer",
85 "Machine Block Matching and Inference Analysis", true,
86 true)
90 "Machine Block Matching and Inference Analysis", true, true)
91
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,
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(DIL, 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(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(Max, *W);
133 HasWeight = true;
134 }
135 }
136 if (!HasWeight)
137 return std::error_code();
138 return Max;
139 }
140
141private:
142 const FunctionSamples &Samples;
144 // Samples of the inlined instance each location comes from.
146};
147} // namespace
148
151
153
160
161std::optional<BasicBlockMatchingAndInference::WeightInfo>
163 auto It = ProgramWeightInfo.find(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;
176 for (auto &Block : MF) {
177 Blocks.push_back(&Block);
178 Hashes.push_back(BlendedBlockHash(MBHI->getMBBHash(Block)));
179 }
180 StaleMatcher Matcher;
181 Matcher.init(Blocks, Hashes);
182 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
183 const CFGProfile *CFG = BSPR->getFunctionCFGProfile(MF.getName());
184 if (CFG == nullptr)
185 return MatchWeight;
186 for (auto &BlockCount : CFG->NodeCounts) {
187 if (CFG->BBHashes.count(BlockCount.first.BaseID)) {
188 auto Hash = CFG->BBHashes.lookup(BlockCount.first.BaseID);
189 MachineBasicBlock *Block = Matcher.matchBlock(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(PredID))
198 continue;
199 auto PredHash = CFG->BBHashes.lookup(PredID);
200 MachineBasicBlock *PredBlock =
201 Matcher.matchBlock(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(SuccID)) {
208 auto SuccHash = CFG->BBHashes.lookup(SuccID);
209 MachineBasicBlock *SuccBlock =
210 Matcher.matchBlock(BlendedBlockHash(SuccHash));
211 // When an edge has clone copies, sum their counts.
212 if (SuccBlock != nullptr)
213 MatchWeight.EdgeWeights[std::make_pair(PredBlock, 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(BBID))
233 return MBB;
234 return BBIDToMBB.lookup(UniqueBBID{BBID.BaseID, 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(SuccMBB))
247 continue;
248 if (PredMBB)
249 MismatchedMBBs.insert(PredMBB);
250 if (SuccMBB)
251 MismatchedMBBs.insert(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(MBB);
258 DenseSet<const MachineBasicBlock *> MatchedMBBs;
259 for (auto &MBB : MF) {
260 if (!ProfiledMBBs.contains(&MBB))
261 continue;
262 if (MismatchedMBBs.contains(&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(&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(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(PredMBB))
278 continue;
279 for (const auto &[SuccID, EdgeCount] : Succs) {
280 MachineBasicBlock *SuccMBB = FindMBB(SuccID);
281 if (!SuccMBB || !MatchedMBBs.count(SuccMBB))
282 continue;
283 MatchWeight.EdgeWeights[std::make_pair(PredMBB, 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(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 MF.getName(), BasicBlockMatchingAndInference::WeightInfo{
304 std::move(BlockWeights), std::move(EdgeWeights)});
305}
306
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(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 ProfileFile, Ctx, Ctx.getVirtualFileSystem(),
324 EnableFSDiscriminator ? FSDiscriminatorPass::PassLast
325 : FSDiscriminatorPass::Base,
326 Opts.sample_profile_supplement_remapping_file);
327 if (std::error_code EC = ReaderOrErr.getError()) {
328 Ctx.diagnose(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(DiagnosticInfoSampleProfile(
337 ProfileFile, "Could not read supplemental sample profile"));
338 return false;
339 }
340 if (Reader->profileIsProbeBased()) {
341 Ctx.diagnose(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(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(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(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(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>(MatchWeight.BlockWeights.lookup(&EntryBB), 1);
393 uint64_t SampleEntryWeight = 0;
394 if (ErrorOr<uint64_t> W = Query.getBlockWeight(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(&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(*SampleWeight, PropellerEntryWeight, SampleEntryWeight);
414 if (Weight != 0)
415 MatchWeight.BlockWeights[&MBB] = Weight;
416 }
417}
418
420 // The profile is read for each module.
421 SampleReader.reset();
422 return false;
423}
424
426 if (MF.empty())
427 return false;
429 const CFGProfile *CFG = BSPR->getFunctionCFGProfile(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);
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
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
MachineBasicBlock & MBB
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
Flatten the CFG
IRTranslator LLVM IR MI
Module.h This file contains the declarations for the Module class.
#define I(x, y, z)
Definition MD5.cpp:57
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
#define LLVM_DEBUG(...)
Definition Debug.h:119
The object is used to identify and match basic blocks given their hashes.
void init(const std::vector< MachineBasicBlock * > &Blocks, const std::vector< BlendedBlockHash > &Hashes)
Initialize stale matcher.
MachineBasicBlock * matchBlock(BlendedBlockHash BlendedHash) const
Find the most similar block for a given hash.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
std::optional< WeightInfo > getWeightInfo(StringRef FuncName) const
bool doFinalization(Module &M) override
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
bool runOnMachineFunction(MachineFunction &F) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool doInitialization(Module &M) override
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
unsigned getBaseDiscriminator() const
Returns the base discriminator stored in the discriminator.
Subprogram description. Uses SubclassData1.
unsigned size() const
Definition DenseMap.h:717
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
Definition DenseMap.h:793
Diagnostic information for the sample profiler.
Represents either an error or a value T.
Definition ErrorOr.h:56
DISubprogram * getSubprogram() const
Get the attached subprogram.
This is an important class for using LLVM in a threaded context.
Definition LLVMContext.h:76
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
std::optional< UniqueBBID > getBBID() const
LLVM_ABI bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Legacy MachineFunctionPass for MachineBlockHashInfo.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Function & getFunction()
Return the LLVM function that this machine code represents.
const MachineBasicBlock & front() const
Representation of each machine instruction.
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
Analysis providing profile information.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
constexpr bool empty() const
Check if the string is empty.
Definition StringRef.h:141
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:210
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition DenseSet.h:183
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition DenseSet.h:188
Representation of the samples collected for a function.
Definition SampleProf.h:854
uint64_t getHeadSamples() const
For top-level functions, return the total number of branch samples that have the function as the bran...
LLVM_ABI const FunctionSamples * findFunctionSamples(const DILocation *DIL, SampleProfileReaderItaniumRemapper *Remapper=nullptr, const HashKeyMap< DenseMap, FunctionId, FunctionId > *FuncNameToProfNameMap=nullptr) const LLVM_LIFETIME_BOUND
Get the FunctionSamples of the inline instance where DIL originates from.
static LLVM_ABI unsigned getOffset(const DILocation *DIL)
Returns the line offset to the start line of the subprogram.
SampleProfileReaderItaniumRemapper remaps the profile data from a sample profile data reader,...
static LLVM_ABI ErrorOr< std::unique_ptr< SampleProfileReader > > create(StringRef Filename, LLVMContext &C, vfs::FileSystem &FS, FSDiscriminatorPass P=FSDiscriminatorPass::Base, StringRef RemapFilename="")
Create a sample profile reader appropriate to the file format.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI cl::opt< bool > EnableFSDiscriminator
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
LLVM_ABI uint64_t mulDivNearest(uint64_t X, uint64_t Y, uint64_t Z)
Returns (X * Y) / Z rounded by round-half-up, like divideNearest.
LLVM_ABI MachineFunctionPass * createBasicBlockMatchingAndInferencePass()
createBasicBlockMatchingAndInferencePass - This pass enables matching and inference when using propel...
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
An object wrapping several components of a basic block hash.
uint64_t distance(const BlendedBlockHash &BBH) const
Compute a distance between two given blended hashes.