blob: 162e98c71630b5962298e392f6c485f441b84cab [file] [edit]
//===- llvm/CodeGen/BasicBlockMatchingAndInference.cpp ----------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// In Propeller's profile, we have already read the hash values of basic blocks,
// as well as the weights of basic blocks and edges in the CFG. In this file,
// we first match the basic blocks in the profile with those in the current
// MachineFunction using the basic block hash, thereby obtaining the weights of
// some basic blocks and edges. Subsequently, we infer the weights of all basic
// blocks using an inference algorithm.
//
// TODO: Integrate part of the code in this file with BOLT's implementation into
// the LLVM infrastructure, enabling both BOLT and Propeller to reuse it.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/BasicBlockMatchingAndInference.h"
#include "CodeGenOptions.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
#include "llvm/CodeGen/MachineBlockHashInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/InitializePasses.h"
#include "llvm/ProfileData/SampleProf.h"
#include "llvm/ProfileData/SampleProfReader.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
using namespace llvm;
#define DEBUG_TYPE "machine-block-match-infer"
/// The object is used to identify and match basic blocks given their hashes.
class StaleMatcher {
public:
/// Initialize stale matcher.
void init(const std::vector<MachineBasicBlock *> &Blocks,
const std::vector<BlendedBlockHash> &Hashes) {
assert(Blocks.size() == Hashes.size() &&
"incorrect matcher initialization");
for (size_t I = 0; I < Blocks.size(); I++) {
MachineBasicBlock *Block = Blocks[I];
uint16_t OpHash = Hashes[I].getOpcodeHash();
OpHashToBlocks[OpHash].push_back(std::make_pair(Hashes[I], Block));
}
}
/// Find the most similar block for a given hash.
MachineBasicBlock *matchBlock(BlendedBlockHash BlendedHash) const {
auto BlockIt = OpHashToBlocks.find(BlendedHash.getOpcodeHash());
if (BlockIt == OpHashToBlocks.end()) {
return nullptr;
}
MachineBasicBlock *BestBlock = nullptr;
uint64_t BestDist = std::numeric_limits<uint64_t>::max();
for (auto It : BlockIt->second) {
MachineBasicBlock *Block = It.second;
BlendedBlockHash Hash = It.first;
uint64_t Dist = Hash.distance(BlendedHash);
if (BestBlock == nullptr || Dist < BestDist) {
BestDist = Dist;
BestBlock = Block;
}
}
return BestBlock;
}
private:
using HashBlockPairType = std::pair<BlendedBlockHash, MachineBasicBlock *>;
DenseMap<uint16_t, std::vector<HashBlockPairType>> OpHashToBlocks;
};
INITIALIZE_PASS_BEGIN(BasicBlockMatchingAndInference,
"machine-block-match-infer",
"Machine Block Matching and Inference Analysis", true,
true)
INITIALIZE_PASS_DEPENDENCY(MachineBlockHashInfo)
INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReaderWrapperPass)
INITIALIZE_PASS_END(BasicBlockMatchingAndInference, "machine-block-match-infer",
"Machine Block Matching and Inference Analysis", true, true)
char BasicBlockMatchingAndInference::ID = 0;
namespace {
/// Looks up the sampled weights of the instructions of one machine function in
/// a line-based sample profile. This is the lookup part of
/// SampleProfileLoaderBaseImpl without its weight propagation, remarks and
/// coverage tracking, which are not needed to supplement the Propeller profile.
class FunctionSamplesQuery {
public:
FunctionSamplesQuery(const FunctionSamples &Samples,
SampleProfileReaderItaniumRemapper *Remapper)
: Samples(Samples), Remapper(Remapper) {}
/// Returns the weight of \p MI, or an error if it has no samples.
ErrorOr<uint64_t> getInstWeight(const MachineInstr &MI) {
const DILocation *DIL = MI.getDebugLoc();
if (!DIL || DIL->getLine() == 0)
return std::error_code();
// Find the samples of the inlined instance MI comes from.
auto [It, Inserted] = InlinedSamplesCache.try_emplace(DIL, nullptr);
if (Inserted)
It->second = Samples.findFunctionSamples(DIL, Remapper);
if (!It->second)
return std::error_code();
uint32_t Discriminator = EnableFSDiscriminator
? DIL->getDiscriminator()
: DIL->getBaseDiscriminator();
return It->second->findSamplesAt(FunctionSamples::getOffset(DIL),
Discriminator);
}
/// Returns the maximum weight among the non-meta instructions of \p MBB, or
/// an error if none of them has samples.
ErrorOr<uint64_t> getBlockWeight(const MachineBasicBlock &MBB) {
uint64_t Max = 0;
bool HasWeight = false;
for (const MachineInstr &MI : MBB) {
if (MI.isMetaInstruction())
continue;
if (ErrorOr<uint64_t> W = getInstWeight(MI)) {
Max = std::max(Max, *W);
HasWeight = true;
}
}
if (!HasWeight)
return std::error_code();
return Max;
}
private:
const FunctionSamples &Samples;
SampleProfileReaderItaniumRemapper *Remapper;
// Samples of the inlined instance each location comes from.
DenseMap<const DILocation *, const FunctionSamples *> InlinedSamplesCache;
};
} // namespace
BasicBlockMatchingAndInference::BasicBlockMatchingAndInference()
: MachineFunctionPass(ID) {}
BasicBlockMatchingAndInference::~BasicBlockMatchingAndInference() = default;
void BasicBlockMatchingAndInference::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<MachineBlockHashInfo>();
AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();
AU.setPreservesAll();
MachineFunctionPass::getAnalysisUsage(AU);
}
std::optional<BasicBlockMatchingAndInference::WeightInfo>
BasicBlockMatchingAndInference::getWeightInfo(StringRef FuncName) const {
auto It = ProgramWeightInfo.find(FuncName);
if (It == ProgramWeightInfo.end()) {
return std::nullopt;
}
return It->second;
}
BasicBlockMatchingAndInference::WeightInfo
BasicBlockMatchingAndInference::initWeightInfoByMatching(MachineFunction &MF) {
std::vector<MachineBasicBlock *> Blocks;
std::vector<BlendedBlockHash> Hashes;
auto BSPR = &getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>();
auto MBHI = &getAnalysis<MachineBlockHashInfo>();
for (auto &Block : MF) {
Blocks.push_back(&Block);
Hashes.push_back(BlendedBlockHash(MBHI->getMBBHash(Block)));
}
StaleMatcher Matcher;
Matcher.init(Blocks, Hashes);
BasicBlockMatchingAndInference::WeightInfo MatchWeight;
const CFGProfile *CFG = BSPR->getFunctionCFGProfile(MF.getName());
if (CFG == nullptr)
return MatchWeight;
for (auto &BlockCount : CFG->NodeCounts) {
if (CFG->BBHashes.count(BlockCount.first.BaseID)) {
auto Hash = CFG->BBHashes.lookup(BlockCount.first.BaseID);
MachineBasicBlock *Block = Matcher.matchBlock(BlendedBlockHash(Hash));
// When a basic block has clone copies, sum their counts.
if (Block != nullptr)
MatchWeight.BlockWeights[Block] += BlockCount.second;
}
}
for (auto &PredItem : CFG->EdgeCounts) {
auto PredID = PredItem.first.BaseID;
if (!CFG->BBHashes.count(PredID))
continue;
auto PredHash = CFG->BBHashes.lookup(PredID);
MachineBasicBlock *PredBlock =
Matcher.matchBlock(BlendedBlockHash(PredHash));
if (PredBlock == nullptr)
continue;
for (auto &SuccItem : PredItem.second) {
auto SuccID = SuccItem.first.BaseID;
auto EdgeWeight = SuccItem.second;
if (CFG->BBHashes.count(SuccID)) {
auto SuccHash = CFG->BBHashes.lookup(SuccID);
MachineBasicBlock *SuccBlock =
Matcher.matchBlock(BlendedBlockHash(SuccHash));
// When an edge has clone copies, sum their counts.
if (SuccBlock != nullptr)
MatchWeight.EdgeWeights[std::make_pair(PredBlock, SuccBlock)] +=
EdgeWeight;
}
}
}
return MatchWeight;
}
BasicBlockMatchingAndInference::WeightInfo
BasicBlockMatchingAndInference::initWeightInfoByBBID(MachineFunction &MF,
const CFGProfile &CFG) {
// Match blocks by their full UniqueBBID (including CloneID). If a cloned
// block in the profile does not exist in MF (e.g., because its cloning path
// was rejected), fall back to the original block so its counts are
// attributed to the original block.
DenseMap<UniqueBBID, MachineBasicBlock *> BBIDToMBB;
for (auto &MBB : MF)
BBIDToMBB[*MBB.getBBID()] = &MBB;
auto FindMBB = [&](const UniqueBBID &BBID) {
if (MachineBasicBlock *MBB = BBIDToMBB.lookup(BBID))
return MBB;
return BBIDToMBB.lookup(UniqueBBID{BBID.BaseID, 0});
};
// A basic block is matched only if it exists in CFG.NodeCounts and all of its
// edges in the CFG profile are also edges in the MIR. The profile may omit
// edges without samples, so MIR edges missing from the profile are allowed.
// Both ends of a profile edge that is not in the MIR are kept as unknown.
DenseSet<const MachineBasicBlock *> MismatchedMBBs;
for (const auto &[PredID, Succs] : CFG.EdgeCounts) {
MachineBasicBlock *PredMBB = FindMBB(PredID);
for (const auto &[SuccID, EdgeCount] : Succs) {
MachineBasicBlock *SuccMBB = FindMBB(SuccID);
if (PredMBB && SuccMBB && PredMBB->isSuccessor(SuccMBB))
continue;
if (PredMBB)
MismatchedMBBs.insert(PredMBB);
if (SuccMBB)
MismatchedMBBs.insert(SuccMBB);
}
}
DenseSet<const MachineBasicBlock *> ProfiledMBBs;
for (const auto &[BBID, BlockCount] : CFG.NodeCounts)
if (MachineBasicBlock *MBB = FindMBB(BBID))
ProfiledMBBs.insert(MBB);
DenseSet<const MachineBasicBlock *> MatchedMBBs;
for (auto &MBB : MF) {
if (!ProfiledMBBs.contains(&MBB))
continue;
if (MismatchedMBBs.contains(&MBB))
LLVM_DEBUG(dbgs() << MF.getName() << ": bb." << MBB.getNumber()
<< " has profile edges that are not in the CFG\n");
else
MatchedMBBs.insert(&MBB);
}
BasicBlockMatchingAndInference::WeightInfo MatchWeight;
for (const auto &[BBID, BlockCount] : CFG.NodeCounts) {
MachineBasicBlock *MBB = FindMBB(BBID);
if (MBB && MatchedMBBs.count(MBB))
MatchWeight.BlockWeights[MBB] += BlockCount;
}
for (const auto &[PredID, Succs] : CFG.EdgeCounts) {
MachineBasicBlock *PredMBB = FindMBB(PredID);
if (!PredMBB || !MatchedMBBs.count(PredMBB))
continue;
for (const auto &[SuccID, EdgeCount] : Succs) {
MachineBasicBlock *SuccMBB = FindMBB(SuccID);
if (!SuccMBB || !MatchedMBBs.count(SuccMBB))
continue;
MatchWeight.EdgeWeights[std::make_pair(PredMBB, SuccMBB)] += EdgeCount;
}
}
return MatchWeight;
}
void BasicBlockMatchingAndInference::generateWeightInfoByInference(
MachineFunction &MF,
BasicBlockMatchingAndInference::WeightInfo &MatchWeight) {
BlockEdgeMap Successors;
for (auto &Block : MF) {
for (auto *Succ : Block.successors())
Successors[&Block].push_back(Succ);
}
SampleProfileInference<MachineFunction> SPI(
MF, Successors, MatchWeight.BlockWeights, MatchWeight.EdgeWeights);
BlockWeightMap BlockWeights;
EdgeWeightMap EdgeWeights;
SPI.apply(BlockWeights, EdgeWeights);
ProgramWeightInfo.try_emplace(
MF.getName(), BasicBlockMatchingAndInference::WeightInfo{
std::move(BlockWeights), std::move(EdgeWeights)});
}
bool BasicBlockMatchingAndInference::doInitialization(Module &M) {
const CodeGenOptions &Opts = getCodeGenOptions(M);
StringRef ProfileFile = Opts.sample_profile_supplement;
// Only the weights matched by BBIDs are supplemented.
if (ProfileFile.empty() || !Opts.propeller_match_bbid)
return false;
LLVMContext &Ctx = M.getContext();
if (ProfileSummaryInfo(M).hasSampleProfile() ||
!Opts.fs_profile_file.empty()) {
Ctx.diagnose(DiagnosticInfoSampleProfile(
ProfileFile,
"Supplemental sample profiles are not supported with SampleFDO",
DS_Warning));
return false;
}
auto ReaderOrErr = SampleProfileReader::create(
ProfileFile, Ctx, Ctx.getVirtualFileSystem(),
EnableFSDiscriminator ? FSDiscriminatorPass::PassLast
: FSDiscriminatorPass::Base,
Opts.sample_profile_supplement_remapping_file);
if (std::error_code EC = ReaderOrErr.getError()) {
Ctx.diagnose(DiagnosticInfoSampleProfile(
ProfileFile,
"Could not open supplemental sample profile: " + EC.message()));
return false;
}
std::unique_ptr<SampleProfileReader> Reader = std::move(*ReaderOrErr);
Reader->setModule(&M);
if (Reader->read() != sampleprof_error::success) {
Ctx.diagnose(DiagnosticInfoSampleProfile(
ProfileFile, "Could not read supplemental sample profile"));
return false;
}
if (Reader->profileIsProbeBased()) {
Ctx.diagnose(DiagnosticInfoSampleProfile(
ProfileFile,
"Pseudo probe based supplemental sample profiles are not supported",
DS_Warning));
return false;
}
if (Reader->profileIsCS()) {
Ctx.diagnose(DiagnosticInfoSampleProfile(
ProfileFile,
"Context-sensitive supplemental sample profiles are not supported",
DS_Warning));
return false;
}
if (Reader->profileIsFS() && !EnableFSDiscriminator) {
Ctx.diagnose(DiagnosticInfoSampleProfile(
ProfileFile,
"Flow-sensitive supplemental sample profiles require "
"-enable-fs-discriminator",
DS_Warning));
return false;
}
if (!Reader->profileIsFS() && EnableFSDiscriminator) {
Ctx.diagnose(DiagnosticInfoSampleProfile(
ProfileFile,
"Non-flow-sensitive supplemental sample profiles are not supported "
"with -enable-fs-discriminator",
DS_Warning));
return false;
}
SampleReader = std::move(Reader);
return false;
}
void BasicBlockMatchingAndInference::supplementWithSampleProfile(
MachineFunction &MF, WeightInfo &MatchWeight) {
if (!SampleReader)
return;
const DISubprogram *Subprogram = MF.getFunction().getSubprogram();
if (!Subprogram || Subprogram->getLine() == 0)
return;
const FunctionSamples *Samples =
SampleReader->getSamplesFor(MF.getFunction());
if (!Samples || Samples->empty())
return;
FunctionSamplesQuery Query(*Samples, SampleReader->getRemapper());
// Scale the weights of the supplemental profile so that the entry block
// weights of both profiles agree. Skip functions with neither entry-block
// samples nor head samples, since their scale is unknown.
const MachineBasicBlock &EntryBB = MF.front();
uint64_t PropellerEntryWeight =
std::max<uint64_t>(MatchWeight.BlockWeights.lookup(&EntryBB), 1);
uint64_t SampleEntryWeight = 0;
if (ErrorOr<uint64_t> W = Query.getBlockWeight(EntryBB))
SampleEntryWeight = *W;
if (SampleEntryWeight == 0)
SampleEntryWeight = Samples->getHeadSamples();
if (SampleEntryWeight == 0)
return;
for (const MachineBasicBlock &MBB : MF) {
// Only supplement blocks that have no samples in the Propeller profile, so
// that code executed in production is not assumed cold prior to inference.
// Blocks that already have Propeller samples keep their Propeller weight.
if (MatchWeight.BlockWeights.lookup(&MBB) != 0)
continue;
ErrorOr<uint64_t> SampleWeight = Query.getBlockWeight(MBB);
if (!SampleWeight)
continue;
// Skip weights that round to zero, so that blocks missing from
// BlockWeights stay unknown to inference rather than known to be cold.
uint64_t Weight =
mulDivNearest(*SampleWeight, PropellerEntryWeight, SampleEntryWeight);
if (Weight != 0)
MatchWeight.BlockWeights[&MBB] = Weight;
}
}
bool BasicBlockMatchingAndInference::doFinalization(Module &M) {
// The profile is read for each module.
SampleReader.reset();
return false;
}
bool BasicBlockMatchingAndInference::runOnMachineFunction(MachineFunction &MF) {
if (MF.empty())
return false;
auto *BSPR = &getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>();
const CFGProfile *CFG = BSPR->getFunctionCFGProfile(MF.getName());
if (CFG == nullptr || (CFG->NodeCounts.empty() && CFG->EdgeCounts.empty()))
return false;
const CodeGenOptions &Opts = getCodeGenOptions(MF);
BasicBlockMatchingAndInference::WeightInfo MatchWeight;
if (Opts.propeller_match_bbid) {
MatchWeight = initWeightInfoByBBID(MF, *CFG);
supplementWithSampleProfile(MF, MatchWeight);
} else {
MatchWeight = initWeightInfoByMatching(MF);
// If the ratio of the number of MBBs in matching to the total number of
// MBBs in the function is less than the threshold value, the processing
// should be abandoned.
if (static_cast<float>(MatchWeight.BlockWeights.size()) / MF.size() <
Opts.propeller_infer_threshold) {
return false;
}
}
generateWeightInfoByInference(MF, MatchWeight);
return false;
}
MachineFunctionPass *llvm::createBasicBlockMatchingAndInferencePass() {
return new BasicBlockMatchingAndInference();
}