1034 lines · cpp
1//===- bolt/Profile/StaleProfileMatching.cpp - Profile data matching ----===//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-exception6//7//===----------------------------------------------------------------------===//8//9// BOLT often has to deal with profiles collected on binaries built from several10// revisions behind release. As a result, a certain percentage of functions is11// considered stale and not optimized. This file implements an ability to match12// profile to functions that are not 100% binary identical, and thus, increasing13// the optimization coverage and boost the performance of applications.14//15// The algorithm consists of two phases: matching and inference:16// - At the matching phase, we try to "guess" as many block and jump counts from17// the stale profile as possible. To this end, the content of each basic block18// is hashed and stored in the (yaml) profile. When BOLT optimizes a binary,19// it computes block hashes and identifies the corresponding entries in the20// stale profile. It yields a partial profile for every CFG in the binary.21// - At the inference phase, we employ a network flow-based algorithm (profi) to22// reconstruct "realistic" block and jump counts from the partial profile23// generated at the first stage. In practice, we don't always produce proper24// profile data but the majority (e.g., >90%) of CFGs get the correct counts.25//26//===----------------------------------------------------------------------===//27 28#include "bolt/Core/HashUtilities.h"29#include "bolt/Profile/YAMLProfileReader.h"30#include "llvm/ADT/Bitfields.h"31#include "llvm/ADT/Hashing.h"32#include "llvm/MC/MCPseudoProbe.h"33#include "llvm/Support/CommandLine.h"34#include "llvm/Support/Timer.h"35#include "llvm/Support/xxhash.h"36#include "llvm/Transforms/Utils/SampleProfileInference.h"37 38#include <queue>39 40using namespace llvm;41 42#undef DEBUG_TYPE43#define DEBUG_TYPE "bolt-prof"44 45namespace opts {46 47extern cl::opt<bool> TimeRewrite;48extern cl::OptionCategory BoltOptCategory;49 50cl::opt<bool>51 InferStaleProfile("infer-stale-profile",52 cl::desc("Infer counts from stale profile data."),53 cl::init(false), cl::Hidden, cl::cat(BoltOptCategory));54 55static cl::opt<unsigned> StaleMatchingMinMatchedBlock(56 "stale-matching-min-matched-block",57 cl::desc("Percentage threshold of matched basic blocks at which stale "58 "profile inference is executed."),59 cl::init(0), cl::Hidden, cl::cat(BoltOptCategory));60 61static cl::opt<unsigned> StaleMatchingMaxFuncSize(62 "stale-matching-max-func-size",63 cl::desc("The maximum size of a function to consider for inference."),64 cl::init(10000), cl::Hidden, cl::cat(BoltOptCategory));65 66// Parameters of the profile inference algorithm. The default values are tuned67// on several benchmarks.68static cl::opt<bool> StaleMatchingEvenFlowDistribution(69 "stale-matching-even-flow-distribution",70 cl::desc("Try to evenly distribute flow when there are multiple equally "71 "likely options."),72 cl::init(true), cl::ReallyHidden, cl::cat(BoltOptCategory));73 74static cl::opt<bool> StaleMatchingRebalanceUnknown(75 "stale-matching-rebalance-unknown",76 cl::desc("Evenly re-distribute flow among unknown subgraphs."),77 cl::init(false), cl::ReallyHidden, cl::cat(BoltOptCategory));78 79static cl::opt<bool> StaleMatchingJoinIslands(80 "stale-matching-join-islands",81 cl::desc("Join isolated components having positive flow."), cl::init(true),82 cl::ReallyHidden, cl::cat(BoltOptCategory));83 84static cl::opt<unsigned> StaleMatchingCostBlockInc(85 "stale-matching-cost-block-inc",86 cl::desc("The cost of increasing a block count by one."), cl::init(150),87 cl::ReallyHidden, cl::cat(BoltOptCategory));88 89static cl::opt<unsigned> StaleMatchingCostBlockDec(90 "stale-matching-cost-block-dec",91 cl::desc("The cost of decreasing a block count by one."), cl::init(150),92 cl::ReallyHidden, cl::cat(BoltOptCategory));93 94static cl::opt<unsigned> StaleMatchingCostJumpInc(95 "stale-matching-cost-jump-inc",96 cl::desc("The cost of increasing a jump count by one."), cl::init(150),97 cl::ReallyHidden, cl::cat(BoltOptCategory));98 99static cl::opt<unsigned> StaleMatchingCostJumpDec(100 "stale-matching-cost-jump-dec",101 cl::desc("The cost of decreasing a jump count by one."), cl::init(150),102 cl::ReallyHidden, cl::cat(BoltOptCategory));103 104static cl::opt<unsigned> StaleMatchingCostBlockUnknownInc(105 "stale-matching-cost-block-unknown-inc",106 cl::desc("The cost of increasing an unknown block count by one."),107 cl::init(1), cl::ReallyHidden, cl::cat(BoltOptCategory));108 109static cl::opt<unsigned> StaleMatchingCostJumpUnknownInc(110 "stale-matching-cost-jump-unknown-inc",111 cl::desc("The cost of increasing an unknown jump count by one."),112 cl::init(140), cl::ReallyHidden, cl::cat(BoltOptCategory));113 114static cl::opt<unsigned> StaleMatchingCostJumpUnknownFTInc(115 "stale-matching-cost-jump-unknown-ft-inc",116 cl::desc(117 "The cost of increasing an unknown fall-through jump count by one."),118 cl::init(3), cl::ReallyHidden, cl::cat(BoltOptCategory));119 120cl::opt<bool> StaleMatchingWithPseudoProbes(121 "stale-matching-with-pseudo-probes",122 cl::desc("Turns on stale matching with block pseudo probes."),123 cl::init(false), cl::ReallyHidden, cl::cat(BoltOptCategory));124 125} // namespace opts126 127namespace llvm {128namespace bolt {129 130/// An object wrapping several components of a basic block hash. The combined131/// (blended) hash is represented and stored as one uint64_t, while individual132/// components are of smaller size (e.g., uint16_t or uint8_t).133struct BlendedBlockHash {134private:135 using ValueOffset = Bitfield::Element<uint16_t, 0, 16>;136 using ValueOpcode = Bitfield::Element<uint16_t, 16, 16>;137 using ValueInstr = Bitfield::Element<uint16_t, 32, 16>;138 using ValuePred = Bitfield::Element<uint8_t, 48, 8>;139 using ValueSucc = Bitfield::Element<uint8_t, 56, 8>;140 141public:142 explicit BlendedBlockHash() {}143 144 explicit BlendedBlockHash(uint64_t Hash) {145 Offset = Bitfield::get<ValueOffset>(Hash);146 OpcodeHash = Bitfield::get<ValueOpcode>(Hash);147 InstrHash = Bitfield::get<ValueInstr>(Hash);148 PredHash = Bitfield::get<ValuePred>(Hash);149 SuccHash = Bitfield::get<ValueSucc>(Hash);150 }151 152 /// Combine the blended hash into uint64_t.153 uint64_t combine() const {154 uint64_t Hash = 0;155 Bitfield::set<ValueOffset>(Hash, Offset);156 Bitfield::set<ValueOpcode>(Hash, OpcodeHash);157 Bitfield::set<ValueInstr>(Hash, InstrHash);158 Bitfield::set<ValuePred>(Hash, PredHash);159 Bitfield::set<ValueSucc>(Hash, SuccHash);160 return Hash;161 }162 163 /// Compute a distance between two given blended hashes. The smaller the164 /// distance, the more similar two blocks are. For identical basic blocks,165 /// the distance is zero.166 uint64_t distance(const BlendedBlockHash &BBH) const {167 assert(OpcodeHash == BBH.OpcodeHash &&168 "incorrect blended hash distance computation");169 uint64_t Dist = 0;170 // Account for NeighborHash171 Dist += SuccHash == BBH.SuccHash ? 0 : 1;172 Dist += PredHash == BBH.PredHash ? 0 : 1;173 Dist <<= 16;174 // Account for InstrHash175 Dist += InstrHash == BBH.InstrHash ? 0 : 1;176 Dist <<= 16;177 // Account for Offset178 Dist += (Offset >= BBH.Offset ? Offset - BBH.Offset : BBH.Offset - Offset);179 return Dist;180 }181 182 /// The offset of the basic block from the function start.183 uint16_t Offset{0};184 /// (Loose) Hash of the basic block instructions, excluding operands.185 uint16_t OpcodeHash{0};186 /// (Strong) Hash of the basic block instructions, including opcodes and187 /// operands.188 uint16_t InstrHash{0};189 /// (Loose) Hashes of the predecessors of the basic block.190 uint8_t PredHash{0};191 /// (Loose) Hashes of the successors of the basic block.192 uint8_t SuccHash{0};193};194 195/// The object is used to identify and match basic blocks in a BinaryFunction196/// given their hashes computed on a binary built from several revisions behind197/// release.198class StaleMatcher {199public:200 /// Initialize stale matcher.201 void init(const std::vector<FlowBlock *> &Blocks,202 const std::vector<BlendedBlockHash> &Hashes,203 const std::vector<uint64_t> &CallHashes) {204 assert(Blocks.size() == Hashes.size() &&205 Hashes.size() == CallHashes.size() &&206 "incorrect matcher initialization");207 for (size_t I = 0; I < Blocks.size(); I++) {208 FlowBlock *Block = Blocks[I];209 uint16_t OpHash = Hashes[I].OpcodeHash;210 OpHashToBlocks[OpHash].push_back(std::make_pair(Hashes[I], Block));211 if (CallHashes[I])212 CallHashToBlocks[CallHashes[I]].push_back(213 std::make_pair(Hashes[I], Block));214 }215 }216 217 /// Creates a mapping from a pseudo probe to a flow block.218 void mapProbeToBB(const MCDecodedPseudoProbe *Probe, FlowBlock *Block) {219 BBPseudoProbeToBlock[Probe] = Block;220 }221 222 enum MatchMethod : char {223 MATCH_EXACT = 0,224 MATCH_PROBE_EXACT,225 MATCH_PROBE_LOOSE,226 MATCH_OPCODE,227 MATCH_CALL,228 NO_MATCH229 };230 231 /// Find the most similar flow block for a profile block given blended hash.232 std::pair<const FlowBlock *, MatchMethod>233 matchBlockStrict(BlendedBlockHash BlendedHash) {234 const auto &[Block, ExactHash] = matchWithOpcodes(BlendedHash);235 if (Block && ExactHash)236 return {Block, MATCH_EXACT};237 return {nullptr, NO_MATCH};238 }239 240 /// Find the most similar flow block for a profile block given pseudo probes.241 std::pair<const FlowBlock *, MatchMethod> matchBlockProbe(242 const ArrayRef<yaml::bolt::PseudoProbeInfo> PseudoProbes,243 const YAMLProfileReader::InlineTreeNodeMapTy &InlineTreeNodeMap) {244 const auto &[ProbeBlock, ExactProbe] =245 matchWithPseudoProbes(PseudoProbes, InlineTreeNodeMap);246 if (ProbeBlock)247 return {ProbeBlock, ExactProbe ? MATCH_PROBE_EXACT : MATCH_PROBE_LOOSE};248 return {nullptr, NO_MATCH};249 }250 251 /// Find the most similar flow block for a profile block given its hashes.252 std::pair<const FlowBlock *, MatchMethod>253 matchBlockLoose(BlendedBlockHash BlendedHash, uint64_t CallHash) {254 if (const FlowBlock *CallBlock = matchWithCalls(BlendedHash, CallHash))255 return {CallBlock, MATCH_CALL};256 if (const FlowBlock *OpcodeBlock = matchWithOpcodes(BlendedHash).first)257 return {OpcodeBlock, MATCH_OPCODE};258 return {nullptr, NO_MATCH};259 }260 261 /// Returns true if the two basic blocks (in the binary and in the profile)262 /// corresponding to the given hashes are matched to each other with a high263 /// confidence.264 static bool isHighConfidenceMatch(BlendedBlockHash Hash1,265 BlendedBlockHash Hash2) {266 return Hash1.InstrHash == Hash2.InstrHash;267 }268 269private:270 using HashBlockPairType = std::pair<BlendedBlockHash, FlowBlock *>;271 std::unordered_map<uint16_t, std::vector<HashBlockPairType>> OpHashToBlocks;272 std::unordered_map<uint64_t, std::vector<HashBlockPairType>> CallHashToBlocks;273 DenseMap<const MCDecodedPseudoProbe *, FlowBlock *> BBPseudoProbeToBlock;274 275 // Uses OpcodeHash to find the most similar block for a given hash.276 std::pair<const FlowBlock *, bool>277 matchWithOpcodes(BlendedBlockHash BlendedHash) const {278 auto BlockIt = OpHashToBlocks.find(BlendedHash.OpcodeHash);279 if (BlockIt == OpHashToBlocks.end())280 return {nullptr, false};281 FlowBlock *BestBlock = nullptr;282 uint64_t BestDist = std::numeric_limits<uint64_t>::max();283 BlendedBlockHash BestHash;284 for (const auto &[Hash, Block] : BlockIt->second) {285 uint64_t Dist = Hash.distance(BlendedHash);286 if (BestBlock == nullptr || Dist < BestDist) {287 BestDist = Dist;288 BestBlock = Block;289 BestHash = Hash;290 }291 }292 return {BestBlock, isHighConfidenceMatch(BestHash, BlendedHash)};293 }294 295 // Uses CallHash to find the most similar block for a given hash.296 const FlowBlock *matchWithCalls(BlendedBlockHash BlendedHash,297 uint64_t CallHash) const {298 if (!CallHash)299 return nullptr;300 auto BlockIt = CallHashToBlocks.find(CallHash);301 if (BlockIt == CallHashToBlocks.end())302 return nullptr;303 FlowBlock *BestBlock = nullptr;304 uint64_t BestDist = std::numeric_limits<uint64_t>::max();305 for (const auto &[Hash, Block] : BlockIt->second) {306 uint64_t Dist = Hash.OpcodeHash > BlendedHash.OpcodeHash307 ? Hash.OpcodeHash - BlendedHash.OpcodeHash308 : BlendedHash.OpcodeHash - Hash.OpcodeHash;309 if (BestBlock == nullptr || Dist < BestDist) {310 BestDist = Dist;311 BestBlock = Block;312 }313 }314 return BestBlock;315 }316 317 /// Matches a profile block with a binary block based on pseudo probes.318 /// Returns the best matching block (or nullptr) and whether the match is319 /// unambiguous.320 std::pair<const FlowBlock *, bool> matchWithPseudoProbes(321 const ArrayRef<yaml::bolt::PseudoProbeInfo> BlockPseudoProbes,322 const YAMLProfileReader::InlineTreeNodeMapTy &InlineTreeNodeMap) const {323 324 if (!opts::StaleMatchingWithPseudoProbes)325 return {nullptr, false};326 327 DenseMap<const FlowBlock *, uint32_t> FlowBlockMatchCount;328 329 auto matchProfileProbeToBlock = [&](uint32_t NodeId,330 uint64_t ProbeId) -> const FlowBlock * {331 const MCDecodedPseudoProbeInlineTree *BinaryNode =332 InlineTreeNodeMap.getInlineTreeNode(NodeId);333 if (!BinaryNode)334 return nullptr;335 const MCDecodedPseudoProbe Dummy(0, ProbeId, PseudoProbeType::Block, 0, 0,336 nullptr);337 ArrayRef<MCDecodedPseudoProbe> BinaryProbes = BinaryNode->getProbes();338 auto BinaryProbeIt = llvm::lower_bound(339 BinaryProbes, Dummy, [](const auto &LHS, const auto &RHS) {340 return LHS.getIndex() < RHS.getIndex();341 });342 if (BinaryProbeIt == BinaryNode->getProbes().end() ||343 BinaryProbeIt->getIndex() != ProbeId)344 return nullptr;345 auto It = BBPseudoProbeToBlock.find(&*BinaryProbeIt);346 if (It == BBPseudoProbeToBlock.end())347 return nullptr;348 return It->second;349 };350 351 for (const yaml::bolt::PseudoProbeInfo &ProfileProbe : BlockPseudoProbes)352 for (uint32_t Node : ProfileProbe.InlineTreeNodes)353 for (uint64_t Probe : ProfileProbe.BlockProbes)354 ++FlowBlockMatchCount[matchProfileProbeToBlock(Node, Probe)];355 uint32_t BestMatchCount = 0;356 uint32_t TotalMatchCount = 0;357 const FlowBlock *BestMatchBlock = nullptr;358 for (const auto &[FlowBlock, Count] : FlowBlockMatchCount) {359 TotalMatchCount += Count;360 if (Count < BestMatchCount || (Count == BestMatchCount && BestMatchBlock))361 continue;362 BestMatchBlock = FlowBlock;363 BestMatchCount = Count;364 }365 return {BestMatchBlock, BestMatchCount == TotalMatchCount};366 }367};368 369void BinaryFunction::computeBlockHashes(HashFunction HashFunction) const {370 if (size() == 0)371 return;372 373 assert(hasCFG() && "the function is expected to have CFG");374 375 std::vector<BlendedBlockHash> BlendedHashes(BasicBlocks.size());376 std::vector<uint64_t> OpcodeHashes(BasicBlocks.size());377 // Initialize hash components.378 for (size_t I = 0; I < BasicBlocks.size(); I++) {379 const BinaryBasicBlock *BB = BasicBlocks[I];380 assert(BB->getIndex() == I && "incorrect block index");381 BlendedHashes[I].Offset = BB->getOffset();382 // Hashing complete instructions.383 std::string InstrHashStr = hashBlock(384 BC, *BB, [&](const MCOperand &Op) { return hashInstOperand(BC, Op); });385 if (HashFunction == HashFunction::StdHash) {386 uint64_t InstrHash = std::hash<std::string>{}(InstrHashStr);387 BlendedHashes[I].InstrHash = (uint16_t)hash_value(InstrHash);388 } else if (HashFunction == HashFunction::XXH3) {389 uint64_t InstrHash = llvm::xxh3_64bits(InstrHashStr);390 BlendedHashes[I].InstrHash = (uint16_t)InstrHash;391 } else {392 llvm_unreachable("Unhandled HashFunction");393 }394 // Hashing opcodes.395 std::string OpcodeHashStr = hashBlockLoose(BC, *BB);396 if (HashFunction == HashFunction::StdHash) {397 OpcodeHashes[I] = std::hash<std::string>{}(OpcodeHashStr);398 BlendedHashes[I].OpcodeHash = (uint16_t)hash_value(OpcodeHashes[I]);399 } else if (HashFunction == HashFunction::XXH3) {400 OpcodeHashes[I] = llvm::xxh3_64bits(OpcodeHashStr);401 BlendedHashes[I].OpcodeHash = (uint16_t)OpcodeHashes[I];402 } else {403 llvm_unreachable("Unhandled HashFunction");404 }405 }406 407 // Initialize neighbor hash.408 for (size_t I = 0; I < BasicBlocks.size(); I++) {409 const BinaryBasicBlock *BB = BasicBlocks[I];410 // Append hashes of successors.411 uint64_t Hash = 0;412 for (BinaryBasicBlock *SuccBB : BB->successors()) {413 uint64_t SuccHash = OpcodeHashes[SuccBB->getIndex()];414 Hash = hashing::detail::hash_16_bytes(Hash, SuccHash);415 }416 if (HashFunction == HashFunction::StdHash) {417 // Compatibility with old behavior.418 BlendedHashes[I].SuccHash = (uint8_t)hash_value(Hash);419 } else {420 BlendedHashes[I].SuccHash = (uint8_t)Hash;421 }422 423 // Append hashes of predecessors.424 Hash = 0;425 for (BinaryBasicBlock *PredBB : BB->predecessors()) {426 uint64_t PredHash = OpcodeHashes[PredBB->getIndex()];427 Hash = hashing::detail::hash_16_bytes(Hash, PredHash);428 }429 if (HashFunction == HashFunction::StdHash) {430 // Compatibility with old behavior.431 BlendedHashes[I].PredHash = (uint8_t)hash_value(Hash);432 } else {433 BlendedHashes[I].PredHash = (uint8_t)Hash;434 }435 }436 437 // Assign hashes.438 for (size_t I = 0; I < BasicBlocks.size(); I++) {439 const BinaryBasicBlock *BB = BasicBlocks[I];440 BB->setHash(BlendedHashes[I].combine());441 }442}443// TODO: mediate the difference between flow function construction here in BOLT444// and in the compiler by splitting blocks with exception throwing calls at the445// call and adding the landing pad as the successor.446/// Create a wrapper flow function to use with the profile inference algorithm,447/// and initialize its jumps and metadata.448FlowFunction449createFlowFunction(const BinaryFunction::BasicBlockOrderType &BlockOrder) {450 FlowFunction Func;451 452 // Add a special "dummy" source so that there is always a unique entry point.453 FlowBlock EntryBlock;454 EntryBlock.Index = 0;455 Func.Blocks.push_back(EntryBlock);456 457 // Create FlowBlock for every basic block in the binary function.458 for (const BinaryBasicBlock *BB : BlockOrder) {459 Func.Blocks.emplace_back();460 FlowBlock &Block = Func.Blocks.back();461 Block.Index = Func.Blocks.size() - 1;462 (void)BB;463 assert(Block.Index == BB->getIndex() + 1 &&464 "incorrectly assigned basic block index");465 }466 467 // Add a special "dummy" sink block so there is always a unique sink.468 FlowBlock SinkBlock;469 SinkBlock.Index = Func.Blocks.size();470 Func.Blocks.push_back(SinkBlock);471 472 // Create FlowJump for each jump between basic blocks in the binary function.473 std::vector<uint64_t> InDegree(Func.Blocks.size(), 0);474 for (const BinaryBasicBlock *SrcBB : BlockOrder) {475 std::unordered_set<const BinaryBasicBlock *> UniqueSuccs;476 // Collect regular jumps477 for (const BinaryBasicBlock *DstBB : SrcBB->successors()) {478 // Ignoring parallel edges479 if (UniqueSuccs.find(DstBB) != UniqueSuccs.end())480 continue;481 482 Func.Jumps.emplace_back();483 FlowJump &Jump = Func.Jumps.back();484 Jump.Source = SrcBB->getIndex() + 1;485 Jump.Target = DstBB->getIndex() + 1;486 InDegree[Jump.Target]++;487 UniqueSuccs.insert(DstBB);488 }489 // TODO: set jump from exit block to landing pad to Unlikely.490 // If the block is an exit, add a dummy edge from it to the sink block.491 if (UniqueSuccs.empty()) {492 Func.Jumps.emplace_back();493 FlowJump &Jump = Func.Jumps.back();494 Jump.Source = SrcBB->getIndex() + 1;495 Jump.Target = Func.Blocks.size() - 1;496 InDegree[Jump.Target]++;497 }498 499 // Collect jumps to landing pads500 for (const BinaryBasicBlock *DstBB : SrcBB->landing_pads()) {501 // Ignoring parallel edges502 if (UniqueSuccs.find(DstBB) != UniqueSuccs.end())503 continue;504 505 Func.Jumps.emplace_back();506 FlowJump &Jump = Func.Jumps.back();507 Jump.Source = SrcBB->getIndex() + 1;508 Jump.Target = DstBB->getIndex() + 1;509 InDegree[Jump.Target]++;510 UniqueSuccs.insert(DstBB);511 }512 }513 514 // Add dummy edges to the extra sources. If there are multiple entry blocks,515 // add an unlikely edge from 0 to the subsequent ones. Skips the sink block.516 assert(InDegree[0] == 0 && "dummy entry blocks shouldn't have predecessors");517 for (uint64_t I = 1; I < Func.Blocks.size() - 1; I++) {518 const BinaryBasicBlock *BB = BlockOrder[I - 1];519 if (BB->isEntryPoint() || InDegree[I] == 0) {520 Func.Jumps.emplace_back();521 FlowJump &Jump = Func.Jumps.back();522 Jump.Source = 0;523 Jump.Target = I;524 if (!BB->isEntryPoint())525 Jump.IsUnlikely = true;526 }527 }528 529 // Create necessary metadata for the flow function530 for (FlowJump &Jump : Func.Jumps) {531 assert(Jump.Source < Func.Blocks.size());532 Func.Blocks[Jump.Source].SuccJumps.push_back(&Jump);533 assert(Jump.Target < Func.Blocks.size());534 Func.Blocks[Jump.Target].PredJumps.push_back(&Jump);535 }536 return Func;537}538 539/// Assign initial block/jump weights based on the stale profile data. The goal540/// is to extract as much information from the stale profile as possible. Here541/// we assume that each basic block is specified via a hash value computed from542/// its content and the hashes of the unchanged basic blocks stay the same543/// across different revisions of the binary. Blocks may also have pseudo probe544/// information in the profile and the binary which is used for matching.545/// Whenever there is a count in the profile with the hash corresponding to one546/// of the basic blocks in the binary, the count is "matched" to the block.547/// Similarly, if both the source and the target of a count in the profile are548/// matched to a jump in the binary, the count is recorded in CFG.549size_t matchWeights(550 BinaryContext &BC, const BinaryFunction::BasicBlockOrderType &BlockOrder,551 const yaml::bolt::BinaryFunctionProfile &YamlBF, FlowFunction &Func,552 HashFunction HashFunction, YAMLProfileReader::ProfileLookupMap &IdToYamlBF,553 const BinaryFunction &BF,554 const ArrayRef<YAMLProfileReader::ProbeMatchSpec> ProbeMatchSpecs) {555 556 assert(Func.Blocks.size() == BlockOrder.size() + 2);557 558 std::vector<uint64_t> CallHashes;559 std::vector<FlowBlock *> Blocks;560 std::vector<BlendedBlockHash> BlendedHashes;561 for (uint64_t I = 0; I < BlockOrder.size(); I++) {562 const BinaryBasicBlock *BB = BlockOrder[I];563 assert(BB->getHash() != 0 && "empty hash of BinaryBasicBlock");564 565 std::string CallHashStr = hashBlockCalls(BC, *BB);566 if (CallHashStr.empty()) {567 CallHashes.push_back(0);568 } else {569 if (HashFunction == HashFunction::StdHash)570 CallHashes.push_back(std::hash<std::string>{}(CallHashStr));571 else if (HashFunction == HashFunction::XXH3)572 CallHashes.push_back(llvm::xxh3_64bits(CallHashStr));573 else574 llvm_unreachable("Unhandled HashFunction");575 }576 577 Blocks.push_back(&Func.Blocks[I + 1]);578 BlendedBlockHash BlendedHash(BB->getHash());579 BlendedHashes.push_back(BlendedHash);580 LLVM_DEBUG(dbgs() << "BB with index " << I << " has hash = "581 << Twine::utohexstr(BB->getHash()) << "\n");582 }583 StaleMatcher Matcher;584 // Collects function pseudo probes for use in the StaleMatcher.585 if (opts::StaleMatchingWithPseudoProbes) {586 const MCPseudoProbeDecoder *Decoder = BC.getPseudoProbeDecoder();587 assert(Decoder &&588 "If pseudo probes are in use, pseudo probe decoder should exist");589 const AddressProbesMap &ProbeMap = Decoder->getAddress2ProbesMap();590 const uint64_t FuncAddr = BF.getAddress();591 for (const MCDecodedPseudoProbe &Probe :592 ProbeMap.find(FuncAddr, FuncAddr + BF.getSize()))593 if (const BinaryBasicBlock *BB =594 BF.getBasicBlockContainingOffset(Probe.getAddress() - FuncAddr))595 Matcher.mapProbeToBB(&Probe, Blocks[BB->getIndex()]);596 }597 Matcher.init(Blocks, BlendedHashes, CallHashes);598 599 using FlowBlockTy =600 std::pair<const FlowBlock *, const yaml::bolt::BinaryBasicBlockProfile *>;601 using ProfileBlockMatchMap = DenseMap<uint32_t, FlowBlockTy>;602 // Binary profile => block index => matched block + its block profile603 DenseMap<const yaml::bolt::BinaryFunctionProfile *, ProfileBlockMatchMap>604 MatchedBlocks;605 606 // Map of FlowBlock and matching method.607 DenseMap<const FlowBlock *, StaleMatcher::MatchMethod> MatchedFlowBlocks;608 609 auto addMatchedBlock =610 [&](std::pair<const FlowBlock *, StaleMatcher::MatchMethod> BlockMethod,611 const yaml::bolt::BinaryFunctionProfile &YamlBP,612 const yaml::bolt::BinaryBasicBlockProfile &YamlBB) {613 const auto &[MatchedBlock, Method] = BlockMethod;614 if (!MatchedBlock)615 return;616 // Don't override earlier matches617 if (MatchedFlowBlocks.contains(MatchedBlock))618 return;619 MatchedFlowBlocks.try_emplace(MatchedBlock, Method);620 MatchedBlocks[&YamlBP][YamlBB.Index] = {MatchedBlock, &YamlBB};621 };622 623 // Match blocks from the profile to the blocks in CFG by strict hash.624 for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {625 // Update matching stats.626 ++BC.Stats.NumStaleBlocks;627 BC.Stats.StaleSampleCount += YamlBB.ExecCount;628 629 assert(YamlBB.Hash != 0 && "empty hash of BinaryBasicBlockProfile");630 BlendedBlockHash YamlHash(YamlBB.Hash);631 addMatchedBlock(Matcher.matchBlockStrict(YamlHash), YamlBF, YamlBB);632 }633 // Match blocks from the profile to the blocks in CFG by pseudo probes.634 for (const auto &[InlineNodeMap, YamlBP] : ProbeMatchSpecs) {635 for (const yaml::bolt::BinaryBasicBlockProfile &BB : YamlBP.get().Blocks)636 if (!BB.PseudoProbes.empty())637 addMatchedBlock(Matcher.matchBlockProbe(BB.PseudoProbes, InlineNodeMap),638 YamlBP, BB);639 }640 // Match blocks from the profile to the blocks in CFG with loose methods.641 for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF.Blocks) {642 assert(YamlBB.Hash != 0 && "empty hash of BinaryBasicBlockProfile");643 BlendedBlockHash YamlHash(YamlBB.Hash);644 645 std::string CallHashStr = hashBlockCalls(IdToYamlBF, YamlBB);646 uint64_t CallHash = 0;647 if (!CallHashStr.empty()) {648 if (HashFunction == HashFunction::StdHash)649 CallHash = std::hash<std::string>{}(CallHashStr);650 else if (HashFunction == HashFunction::XXH3)651 CallHash = llvm::xxh3_64bits(CallHashStr);652 else653 llvm_unreachable("Unhandled HashFunction");654 }655 auto [MatchedBlock, Method] = Matcher.matchBlockLoose(YamlHash, CallHash);656 if (MatchedBlock == nullptr && YamlBB.Index == 0) {657 MatchedBlock = Blocks[0];658 // Report as loose match659 Method = StaleMatcher::MATCH_OPCODE;660 }661 if (!MatchedBlock) {662 LLVM_DEBUG(dbgs() << "Couldn't match yaml block (bid = " << YamlBB.Index663 << ")" << " with hash " << Twine::utohexstr(YamlBB.Hash)664 << "\n");665 continue;666 }667 addMatchedBlock({MatchedBlock, Method}, YamlBF, YamlBB);668 }669 670 // Match jumps from the profile to the jumps from CFG671 std::vector<uint64_t> OutWeight(Func.Blocks.size(), 0);672 std::vector<uint64_t> InWeight(Func.Blocks.size(), 0);673 674 for (const auto &[YamlBF, MatchMap] : MatchedBlocks) {675 for (const auto &[YamlBBIdx, FlowBlockProfile] : MatchMap) {676 const auto &[MatchedBlock, YamlBB] = FlowBlockProfile;677 StaleMatcher::MatchMethod Method = MatchedFlowBlocks.lookup(MatchedBlock);678 BlendedBlockHash BinHash = BlendedHashes[MatchedBlock->Index - 1];679 LLVM_DEBUG(dbgs() << "Matched yaml block (bid = " << YamlBBIdx << ")"680 << " with hash " << Twine::utohexstr(YamlBB->Hash)681 << " to BB (index = " << MatchedBlock->Index - 1 << ")"682 << " with hash " << Twine::utohexstr(BinHash.combine())683 << "\n");684 (void)BinHash;685 uint64_t ExecCount = YamlBB->ExecCount;686 // Update matching stats accounting for the matched block.687 switch (Method) {688 case StaleMatcher::MATCH_EXACT:689 ++BC.Stats.NumExactMatchedBlocks;690 BC.Stats.ExactMatchedSampleCount += ExecCount;691 LLVM_DEBUG(dbgs() << " exact match\n");692 break;693 case StaleMatcher::MATCH_PROBE_EXACT:694 ++BC.Stats.NumPseudoProbeExactMatchedBlocks;695 BC.Stats.PseudoProbeExactMatchedSampleCount += ExecCount;696 LLVM_DEBUG(dbgs() << " exact pseudo probe match\n");697 break;698 case StaleMatcher::MATCH_PROBE_LOOSE:699 ++BC.Stats.NumPseudoProbeLooseMatchedBlocks;700 BC.Stats.PseudoProbeLooseMatchedSampleCount += ExecCount;701 LLVM_DEBUG(dbgs() << " loose pseudo probe match\n");702 break;703 case StaleMatcher::MATCH_CALL:704 ++BC.Stats.NumCallMatchedBlocks;705 BC.Stats.CallMatchedSampleCount += ExecCount;706 LLVM_DEBUG(dbgs() << " call match\n");707 break;708 case StaleMatcher::MATCH_OPCODE:709 ++BC.Stats.NumLooseMatchedBlocks;710 BC.Stats.LooseMatchedSampleCount += ExecCount;711 LLVM_DEBUG(dbgs() << " loose match\n");712 break;713 case StaleMatcher::NO_MATCH:714 LLVM_DEBUG(dbgs() << " no match\n");715 }716 }717 718 for (const yaml::bolt::BinaryBasicBlockProfile &YamlBB : YamlBF->Blocks) {719 for (const yaml::bolt::SuccessorInfo &YamlSI : YamlBB.Successors) {720 if (YamlSI.Count == 0)721 continue;722 723 // Try to find the jump for a given (src, dst) pair from the profile and724 // assign the jump weight based on the profile count725 const uint64_t SrcIndex = YamlBB.Index;726 const uint64_t DstIndex = YamlSI.Index;727 728 const FlowBlock *MatchedSrcBlock = MatchMap.lookup(SrcIndex).first;729 const FlowBlock *MatchedDstBlock = MatchMap.lookup(DstIndex).first;730 731 if (MatchedSrcBlock != nullptr && MatchedDstBlock != nullptr) {732 // Find a jump between the two blocks733 FlowJump *Jump = nullptr;734 for (FlowJump *SuccJump : MatchedSrcBlock->SuccJumps) {735 if (SuccJump->Target == MatchedDstBlock->Index) {736 Jump = SuccJump;737 break;738 }739 }740 // Assign the weight, if the corresponding jump is found741 if (Jump != nullptr) {742 Jump->Weight = YamlSI.Count;743 Jump->HasUnknownWeight = false;744 }745 }746 // Assign the weight for the src block, if it is found747 if (MatchedSrcBlock != nullptr)748 OutWeight[MatchedSrcBlock->Index] += YamlSI.Count;749 // Assign the weight for the dst block, if it is found750 if (MatchedDstBlock != nullptr)751 InWeight[MatchedDstBlock->Index] += YamlSI.Count;752 }753 }754 }755 756 // Assign block counts based on in-/out- jumps757 for (FlowBlock &Block : Func.Blocks) {758 if (OutWeight[Block.Index] == 0 && InWeight[Block.Index] == 0) {759 assert(Block.HasUnknownWeight && "unmatched block with a positive count");760 continue;761 }762 Block.HasUnknownWeight = false;763 Block.Weight = std::max(OutWeight[Block.Index], InWeight[Block.Index]);764 }765 766 return MatchedBlocks[&YamlBF].size();767}768 769/// The function finds all blocks that are (i) reachable from the Entry block770/// and (ii) do not have a path to an exit, and marks all such blocks 'cold'771/// so that profi does not send any flow to such blocks.772void preprocessUnreachableBlocks(FlowFunction &Func) {773 const uint64_t NumBlocks = Func.Blocks.size();774 775 // Start bfs from the source776 std::queue<uint64_t> Queue;777 std::vector<bool> VisitedEntry(NumBlocks, false);778 for (uint64_t I = 0; I < NumBlocks; I++) {779 FlowBlock &Block = Func.Blocks[I];780 if (Block.isEntry()) {781 Queue.push(I);782 VisitedEntry[I] = true;783 break;784 }785 }786 while (!Queue.empty()) {787 const uint64_t Src = Queue.front();788 Queue.pop();789 for (FlowJump *Jump : Func.Blocks[Src].SuccJumps) {790 const uint64_t Dst = Jump->Target;791 if (!VisitedEntry[Dst]) {792 Queue.push(Dst);793 VisitedEntry[Dst] = true;794 }795 }796 }797 798 // Start bfs from all sinks799 std::vector<bool> VisitedExit(NumBlocks, false);800 for (uint64_t I = 0; I < NumBlocks; I++) {801 FlowBlock &Block = Func.Blocks[I];802 if (Block.isExit() && VisitedEntry[I]) {803 Queue.push(I);804 VisitedExit[I] = true;805 }806 }807 while (!Queue.empty()) {808 const uint64_t Src = Queue.front();809 Queue.pop();810 for (FlowJump *Jump : Func.Blocks[Src].PredJumps) {811 const uint64_t Dst = Jump->Source;812 if (!VisitedExit[Dst]) {813 Queue.push(Dst);814 VisitedExit[Dst] = true;815 }816 }817 }818 819 // Make all blocks of zero weight so that flow is not sent820 for (uint64_t I = 0; I < NumBlocks; I++) {821 FlowBlock &Block = Func.Blocks[I];822 if (Block.Weight == 0)823 continue;824 if (!VisitedEntry[I] || !VisitedExit[I]) {825 Block.Weight = 0;826 Block.HasUnknownWeight = true;827 Block.IsUnlikely = true;828 for (FlowJump *Jump : Block.SuccJumps) {829 if (Jump->Source == Block.Index && Jump->Target == Block.Index) {830 Jump->Weight = 0;831 Jump->HasUnknownWeight = true;832 Jump->IsUnlikely = true;833 }834 }835 }836 }837}838 839/// Decide if stale profile matching can be applied for a given function.840/// Currently we skip inference for (very) large instances and for instances841/// having "unexpected" control flow (e.g., having no sink basic blocks).842bool canApplyInference(const FlowFunction &Func,843 const yaml::bolt::BinaryFunctionProfile &YamlBF,844 const uint64_t &MatchedBlocks) {845 if (Func.Blocks.size() > opts::StaleMatchingMaxFuncSize)846 return false;847 848 if (MatchedBlocks * 100 <849 opts::StaleMatchingMinMatchedBlock * YamlBF.Blocks.size())850 return false;851 852 // Returns false if the artificial sink block has no predecessors meaning853 // there are no exit blocks.854 if (Func.Blocks[Func.Blocks.size() - 1].isEntry())855 return false;856 857 return true;858}859 860/// Apply the profile inference algorithm for a given flow function.861void applyInference(FlowFunction &Func) {862 ProfiParams Params;863 // Set the params from the command-line flags.864 Params.EvenFlowDistribution = opts::StaleMatchingEvenFlowDistribution;865 Params.RebalanceUnknown = opts::StaleMatchingRebalanceUnknown;866 Params.JoinIslands = opts::StaleMatchingJoinIslands;867 868 Params.CostBlockInc = opts::StaleMatchingCostBlockInc;869 Params.CostBlockEntryInc = opts::StaleMatchingCostBlockInc;870 Params.CostBlockDec = opts::StaleMatchingCostBlockDec;871 Params.CostBlockEntryDec = opts::StaleMatchingCostBlockDec;872 Params.CostBlockUnknownInc = opts::StaleMatchingCostBlockUnknownInc;873 874 Params.CostJumpInc = opts::StaleMatchingCostJumpInc;875 Params.CostJumpFTInc = opts::StaleMatchingCostJumpInc;876 Params.CostJumpDec = opts::StaleMatchingCostJumpDec;877 Params.CostJumpFTDec = opts::StaleMatchingCostJumpDec;878 Params.CostJumpUnknownInc = opts::StaleMatchingCostJumpUnknownInc;879 Params.CostJumpUnknownFTInc = opts::StaleMatchingCostJumpUnknownFTInc;880 881 applyFlowInference(Params, Func);882}883 884/// Collect inferred counts from the flow function and update annotations in885/// the binary function.886void assignProfile(BinaryFunction &BF,887 const BinaryFunction::BasicBlockOrderType &BlockOrder,888 FlowFunction &Func) {889 BinaryContext &BC = BF.getBinaryContext();890 891 assert(Func.Blocks.size() == BlockOrder.size() + 2);892 for (uint64_t I = 0; I < BlockOrder.size(); I++) {893 FlowBlock &Block = Func.Blocks[I + 1];894 BinaryBasicBlock *BB = BlockOrder[I];895 896 // Update block's count897 BB->setExecutionCount(Block.Flow);898 899 // Update jump counts: (i) clean existing counts and then (ii) set new ones900 auto BI = BB->branch_info_begin();901 for (const BinaryBasicBlock *DstBB : BB->successors()) {902 (void)DstBB;903 BI->Count = 0;904 BI->MispredictedCount = 0;905 ++BI;906 }907 for (FlowJump *Jump : Block.SuccJumps) {908 if (Jump->IsUnlikely)909 continue;910 if (Jump->Flow == 0)911 continue;912 913 // Skips the artificial sink block.914 if (Jump->Target == Func.Blocks.size() - 1)915 continue;916 BinaryBasicBlock &SuccBB = *BlockOrder[Jump->Target - 1];917 // Check if the edge corresponds to a regular jump or a landing pad918 if (BB->getSuccessor(SuccBB.getLabel())) {919 BinaryBasicBlock::BinaryBranchInfo &BI = BB->getBranchInfo(SuccBB);920 BI.Count += Jump->Flow;921 } else {922 BinaryBasicBlock *LP = BB->getLandingPad(SuccBB.getLabel());923 if (LP && LP->getKnownExecutionCount() < Jump->Flow)924 LP->setExecutionCount(Jump->Flow);925 }926 }927 928 // Update call-site annotations929 auto setOrUpdateAnnotation = [&](MCInst &Instr, StringRef Name,930 uint64_t Count) {931 if (BC.MIB->hasAnnotation(Instr, Name))932 BC.MIB->removeAnnotation(Instr, Name);933 // Do not add zero-count annotations934 if (Count == 0)935 return;936 BC.MIB->addAnnotation(Instr, Name, Count);937 };938 939 for (MCInst &Instr : *BB) {940 // Ignore pseudo instructions941 if (BC.MIB->isPseudo(Instr))942 continue;943 // Ignore jump tables944 const MCInst *LastInstr = BB->getLastNonPseudoInstr();945 if (BC.MIB->getJumpTable(*LastInstr) && LastInstr == &Instr)946 continue;947 948 if (BC.MIB->isIndirectCall(Instr) || BC.MIB->isIndirectBranch(Instr)) {949 auto &ICSP = BC.MIB->getOrCreateAnnotationAs<IndirectCallSiteProfile>(950 Instr, "CallProfile");951 if (!ICSP.empty()) {952 // Try to evenly distribute the counts among the call sites953 const uint64_t TotalCount = Block.Flow;954 const uint64_t NumSites = ICSP.size();955 for (uint64_t Idx = 0; Idx < ICSP.size(); Idx++) {956 IndirectCallProfile &CSP = ICSP[Idx];957 uint64_t CountPerSite = TotalCount / NumSites;958 // When counts cannot be exactly distributed, increase by 1 the959 // counts of the first (TotalCount % NumSites) call sites960 if (Idx < TotalCount % NumSites)961 CountPerSite++;962 CSP.Count = CountPerSite;963 }964 } else {965 ICSP.emplace_back(nullptr, Block.Flow, 0);966 }967 } else if (BC.MIB->getConditionalTailCall(Instr)) {968 // We don't know exactly the number of times the conditional tail call969 // is executed; conservatively, setting it to the count of the block970 setOrUpdateAnnotation(Instr, "CTCTakenCount", Block.Flow);971 BC.MIB->removeAnnotation(Instr, "CTCMispredCount");972 } else if (BC.MIB->isCall(Instr)) {973 setOrUpdateAnnotation(Instr, "Count", Block.Flow);974 }975 }976 }977 978 // Update function's execution count and mark the function inferred.979 BF.setExecutionCount(Func.Blocks[0].Flow);980 BF.setHasInferredProfile(true);981}982 983bool YAMLProfileReader::inferStaleProfile(984 BinaryFunction &BF, const yaml::bolt::BinaryFunctionProfile &YamlBF,985 const ArrayRef<ProbeMatchSpec> ProbeMatchSpecs) {986 987 NamedRegionTimer T("inferStaleProfile", "stale profile inference", "rewrite",988 "Rewrite passes", opts::TimeRewrite);989 990 if (!BF.hasCFG())991 return false;992 993 LLVM_DEBUG(dbgs() << "BOLT-INFO: applying profile inference for "994 << "\"" << BF.getPrintName() << "\"\n");995 996 // Make sure that block hashes are up to date.997 BF.computeBlockHashes(YamlBP.Header.HashFunction);998 999 const BinaryFunction::BasicBlockOrderType BlockOrder(1000 BF.getLayout().block_begin(), BF.getLayout().block_end());1001 1002 // Tracks the number of matched blocks.1003 1004 // Create a wrapper flow function to use with the profile inference algorithm.1005 FlowFunction Func = createFlowFunction(BlockOrder);1006 1007 // Match as many block/jump counts from the stale profile as possible1008 size_t MatchedBlocks =1009 matchWeights(BF.getBinaryContext(), BlockOrder, YamlBF, Func,1010 YamlBP.Header.HashFunction, IdToYamLBF, BF, ProbeMatchSpecs);1011 1012 // Adjust the flow function by marking unreachable blocks Unlikely so that1013 // they don't get any counts assigned.1014 preprocessUnreachableBlocks(Func);1015 1016 // Check if profile inference can be applied for the instance.1017 if (!canApplyInference(Func, YamlBF, MatchedBlocks))1018 return false;1019 1020 // Apply the profile inference algorithm.1021 applyInference(Func);1022 1023 // Collect inferred counts and update function annotations.1024 assignProfile(BF, BlockOrder, Func);1025 1026 // As of now, we always mark the binary function having "correct" profile.1027 // In the future, we may discard the results for instances with poor inference1028 // metrics and keep such functions un-optimized.1029 return true;1030}1031 1032} // end namespace bolt1033} // end namespace llvm1034