41#define DEBUG_TYPE "machine-block-match-infer"
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++) {
53 uint16_t OpHash = Hashes[
I].getOpcodeHash();
54 OpHashToBlocks[OpHash].push_back(std::make_pair(Hashes[
I],
Block));
60 auto BlockIt = OpHashToBlocks.find(BlendedHash.
getOpcodeHash());
61 if (BlockIt == OpHashToBlocks.end()) {
65 uint64_t BestDist = std::numeric_limits<uint64_t>::max();
66 for (
auto It : BlockIt->second) {
69 uint64_t Dist = Hash.
distance(BlendedHash);
70 if (BestBlock ==
nullptr || Dist < BestDist) {
79 using HashBlockPairType = std::pair<BlendedBlockHash, MachineBasicBlock *>;
84 "machine-block-match-infer",
85 "Machine Block Matching and Inference Analysis",
true,
90 "Machine Block Matching and Inference Analysis",
true,
true)
99class FunctionSamplesQuery {
103 : Samples(Samples), Remapper(Remapper) {}
108 if (!DIL || DIL->getLine() == 0)
109 return std::error_code();
111 auto [It, Inserted] = InlinedSamplesCache.try_emplace(DIL,
nullptr);
115 return std::error_code();
117 ? DIL->getDiscriminator()
127 bool HasWeight =
false;
129 if (
MI.isMetaInstruction())
132 Max = std::max(Max, *W);
137 return std::error_code();
161std::optional<BasicBlockMatchingAndInference::WeightInfo>
163 auto It = ProgramWeightInfo.find(FuncName);
164 if (It == ProgramWeightInfo.end()) {
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);
181 Matcher.
init(Blocks, Hashes);
182 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
183 const CFGProfile *
CFG = BSPR->getFunctionCFGProfile(MF.getName());
186 for (
auto &BlockCount :
CFG->NodeCounts) {
187 if (
CFG->BBHashes.count(BlockCount.first.BaseID)) {
188 auto Hash =
CFG->BBHashes.lookup(BlockCount.first.BaseID);
191 if (
Block !=
nullptr)
192 MatchWeight.BlockWeights[
Block] += BlockCount.second;
195 for (
auto &PredItem :
CFG->EdgeCounts) {
196 auto PredID = PredItem.first.BaseID;
197 if (!
CFG->BBHashes.count(PredID))
199 auto PredHash =
CFG->BBHashes.lookup(PredID);
200 MachineBasicBlock *PredBlock =
201 Matcher.
matchBlock(BlendedBlockHash(PredHash));
202 if (PredBlock ==
nullptr)
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));
212 if (SuccBlock !=
nullptr)
213 MatchWeight.EdgeWeights[std::make_pair(PredBlock, SuccBlock)] +=
221BasicBlockMatchingAndInference::WeightInfo
222BasicBlockMatchingAndInference::initWeightInfoByBBID(
MachineFunction &MF,
228 DenseMap<UniqueBBID, MachineBasicBlock *> BBIDToMBB;
231 auto FindMBB = [&](
const UniqueBBID &BBID) {
232 if (MachineBasicBlock *
MBB = BBIDToMBB.
lookup(BBID))
234 return BBIDToMBB.
lookup(UniqueBBID{BBID.BaseID, 0});
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))
249 MismatchedMBBs.
insert(PredMBB);
251 MismatchedMBBs.
insert(SuccMBB);
254 DenseSet<const MachineBasicBlock *> ProfiledMBBs;
255 for (
const auto &[BBID, BlockCount] :
CFG.NodeCounts)
256 if (MachineBasicBlock *
MBB = FindMBB(BBID))
258 DenseSet<const MachineBasicBlock *> MatchedMBBs;
259 for (
auto &
MBB : MF) {
264 <<
" has profile edges that are not in the CFG\n");
269 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
270 for (
const auto &[BBID, BlockCount] :
CFG.NodeCounts) {
271 MachineBasicBlock *
MBB = FindMBB(BBID);
273 MatchWeight.BlockWeights[
MBB] += BlockCount;
275 for (
const auto &[PredID, Succs] :
CFG.EdgeCounts) {
276 MachineBasicBlock *PredMBB = FindMBB(PredID);
277 if (!PredMBB || !MatchedMBBs.
count(PredMBB))
279 for (
const auto &[SuccID, EdgeCount] : Succs) {
280 MachineBasicBlock *SuccMBB = FindMBB(SuccID);
281 if (!SuccMBB || !MatchedMBBs.
count(SuccMBB))
283 MatchWeight.EdgeWeights[std::make_pair(PredMBB, SuccMBB)] += EdgeCount;
289void BasicBlockMatchingAndInference::generateWeightInfoByInference(
291 BasicBlockMatchingAndInference::WeightInfo &MatchWeight) {
292 BlockEdgeMap Successors;
293 for (
auto &
Block : MF) {
294 for (
auto *Succ :
Block.successors())
295 Successors[&
Block].push_back(Succ);
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)});
309 StringRef ProfileFile = Opts.sample_profile_supplement;
311 if (ProfileFile.
empty() || !Opts.propeller_match_bbid)
315 !Opts.fs_profile_file.empty()) {
318 "Supplemental sample profiles are not supported with SampleFDO",
323 ProfileFile, Ctx, Ctx.getVirtualFileSystem(),
325 : FSDiscriminatorPass::Base,
326 Opts.sample_profile_supplement_remapping_file);
327 if (std::error_code EC = ReaderOrErr.getError()) {
330 "Could not open supplemental sample profile: " + EC.message()));
333 std::unique_ptr<SampleProfileReader> Reader = std::move(*ReaderOrErr);
334 Reader->setModule(&M);
337 ProfileFile,
"Could not read supplemental sample profile"));
340 if (Reader->profileIsProbeBased()) {
343 "Pseudo probe based supplemental sample profiles are not supported",
347 if (Reader->profileIsCS()) {
350 "Context-sensitive supplemental sample profiles are not supported",
357 "Flow-sensitive supplemental sample profiles require "
358 "-enable-fs-discriminator",
365 "Non-flow-sensitive supplemental sample profiles are not supported "
366 "with -enable-fs-discriminator",
370 SampleReader = std::move(Reader);
374void BasicBlockMatchingAndInference::supplementWithSampleProfile(
379 if (!Subprogram || Subprogram->getLine() == 0)
383 if (!Samples || Samples->
empty())
385 FunctionSamplesQuery Query(*Samples, SampleReader->getRemapper());
391 uint64_t PropellerEntryWeight =
392 std::max<uint64_t>(MatchWeight.BlockWeights.lookup(&EntryBB), 1);
393 uint64_t SampleEntryWeight = 0;
395 SampleEntryWeight = *W;
396 if (SampleEntryWeight == 0)
398 if (SampleEntryWeight == 0)
405 if (MatchWeight.BlockWeights.lookup(&
MBB) != 0)
413 mulDivNearest(*SampleWeight, PropellerEntryWeight, SampleEntryWeight);
415 MatchWeight.BlockWeights[&
MBB] = Weight;
421 SampleReader.reset();
430 if (
CFG ==
nullptr || (
CFG->NodeCounts.empty() &&
CFG->EdgeCounts.empty()))
434 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
435 if (Opts.propeller_match_bbid) {
436 MatchWeight = initWeightInfoByBBID(MF, *
CFG);
437 supplementWithSampleProfile(MF, MatchWeight);
439 MatchWeight = initWeightInfoByMatching(MF);
443 if (
static_cast<float>(MatchWeight.BlockWeights.
size()) / MF.
size() <
444 Opts.propeller_infer_threshold) {
448 generateWeightInfoByInference(MF, MatchWeight);
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
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...
BasicBlockMatchingAndInference()
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 ...
~BasicBlockMatchingAndInference() override
unsigned getBaseDiscriminator() const
Returns the base discriminator stored in the discriminator.
Subprogram description. Uses SubclassData1.
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.
Diagnostic information for the sample profiler.
Represents either an error or a value T.
DISubprogram * getSubprogram() const
Get the attached subprogram.
This is an important class for using LLVM in a threaded context.
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...
MachineFunctionPass(char &ID)
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.
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.
constexpr bool empty() const
Check if the string is empty.
std::pair< iterator, bool > insert(const ValueT &V)
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Representation of the samples collected for a function.
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.
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.
uint16_t getOpcodeHash() const
uint64_t distance(const BlendedBlockHash &BBH) const
Compute a distance between two given blended hashes.