632 lines · cpp
1//===- SampleContextTracker.cpp - Context-sensitive Profile Tracker -------===//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// This file implements the SampleContextTracker used by CSSPGO.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/Transforms/IPO/SampleContextTracker.h"14#include "llvm/ADT/StringRef.h"15#include "llvm/IR/DebugInfoMetadata.h"16#include "llvm/IR/InstrTypes.h"17#include "llvm/IR/Instruction.h"18#include "llvm/ProfileData/SampleProf.h"19#include <map>20#include <queue>21#include <vector>22 23using namespace llvm;24using namespace sampleprof;25 26#define DEBUG_TYPE "sample-context-tracker"27 28namespace llvm {29 30ContextTrieNode *ContextTrieNode::getChildContext(const LineLocation &CallSite,31 FunctionId CalleeName) {32 if (CalleeName.empty())33 return getHottestChildContext(CallSite);34 35 uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite);36 auto It = AllChildContext.find(Hash);37 if (It != AllChildContext.end())38 return &It->second;39 return nullptr;40}41 42ContextTrieNode *43ContextTrieNode::getHottestChildContext(const LineLocation &CallSite) {44 // CSFDO-TODO: This could be slow, change AllChildContext so we can45 // do point look up for child node by call site alone.46 // Retrieve the child node with max count for indirect call47 ContextTrieNode *ChildNodeRet = nullptr;48 uint64_t MaxCalleeSamples = 0;49 for (auto &It : AllChildContext) {50 ContextTrieNode &ChildNode = It.second;51 if (ChildNode.CallSiteLoc != CallSite)52 continue;53 FunctionSamples *Samples = ChildNode.getFunctionSamples();54 if (!Samples)55 continue;56 if (Samples->getTotalSamples() > MaxCalleeSamples) {57 ChildNodeRet = &ChildNode;58 MaxCalleeSamples = Samples->getTotalSamples();59 }60 }61 62 return ChildNodeRet;63}64 65ContextTrieNode &66SampleContextTracker::moveContextSamples(ContextTrieNode &ToNodeParent,67 const LineLocation &CallSite,68 ContextTrieNode &&NodeToMove) {69 uint64_t Hash =70 FunctionSamples::getCallSiteHash(NodeToMove.getFuncName(), CallSite);71 std::map<uint64_t, ContextTrieNode> &AllChildContext =72 ToNodeParent.getAllChildContext();73 assert(!AllChildContext.count(Hash) && "Node to remove must exist");74 ContextTrieNode &NewNode = AllChildContext[Hash];75 NewNode = NodeToMove;76 NewNode.setCallSiteLoc(CallSite);77 78 // Walk through nodes in the moved the subtree, and update79 // FunctionSamples' context as for the context promotion.80 // We also need to set new parant link for all children.81 std::queue<ContextTrieNode *> NodeToUpdate;82 NewNode.setParentContext(&ToNodeParent);83 NodeToUpdate.push(&NewNode);84 85 while (!NodeToUpdate.empty()) {86 ContextTrieNode *Node = NodeToUpdate.front();87 NodeToUpdate.pop();88 FunctionSamples *FSamples = Node->getFunctionSamples();89 90 if (FSamples) {91 setContextNode(FSamples, Node);92 FSamples->getContext().setState(SyntheticContext);93 }94 95 for (auto &It : Node->getAllChildContext()) {96 ContextTrieNode *ChildNode = &It.second;97 ChildNode->setParentContext(Node);98 NodeToUpdate.push(ChildNode);99 }100 }101 102 return NewNode;103}104 105void ContextTrieNode::removeChildContext(const LineLocation &CallSite,106 FunctionId CalleeName) {107 uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite);108 // Note this essentially calls dtor and destroys that child context109 AllChildContext.erase(Hash);110}111 112std::map<uint64_t, ContextTrieNode> &ContextTrieNode::getAllChildContext() {113 return AllChildContext;114}115 116FunctionId ContextTrieNode::getFuncName() const { return FuncName; }117 118FunctionSamples *ContextTrieNode::getFunctionSamples() const {119 return FuncSamples;120}121 122void ContextTrieNode::setFunctionSamples(FunctionSamples *FSamples) {123 FuncSamples = FSamples;124}125 126std::optional<uint32_t> ContextTrieNode::getFunctionSize() const {127 return FuncSize;128}129 130void ContextTrieNode::addFunctionSize(uint32_t FSize) {131 if (!FuncSize)132 FuncSize = 0;133 134 FuncSize = *FuncSize + FSize;135}136 137LineLocation ContextTrieNode::getCallSiteLoc() const { return CallSiteLoc; }138 139ContextTrieNode *ContextTrieNode::getParentContext() const {140 return ParentContext;141}142 143void ContextTrieNode::setParentContext(ContextTrieNode *Parent) {144 ParentContext = Parent;145}146 147void ContextTrieNode::setCallSiteLoc(const LineLocation &Loc) {148 CallSiteLoc = Loc;149}150 151void ContextTrieNode::dumpNode() {152 dbgs() << "Node: " << FuncName << "\n"153 << " Callsite: " << CallSiteLoc << "\n"154 << " Size: " << FuncSize << "\n"155 << " Children:\n";156 157 for (auto &It : AllChildContext) {158 dbgs() << " Node: " << It.second.getFuncName() << "\n";159 }160}161 162void ContextTrieNode::dumpTree() {163 dbgs() << "Context Profile Tree:\n";164 std::queue<ContextTrieNode *> NodeQueue;165 NodeQueue.push(this);166 167 while (!NodeQueue.empty()) {168 ContextTrieNode *Node = NodeQueue.front();169 NodeQueue.pop();170 Node->dumpNode();171 172 for (auto &It : Node->getAllChildContext()) {173 ContextTrieNode *ChildNode = &It.second;174 NodeQueue.push(ChildNode);175 }176 }177}178 179ContextTrieNode *ContextTrieNode::getOrCreateChildContext(180 const LineLocation &CallSite, FunctionId CalleeName, bool AllowCreate) {181 uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite);182 auto It = AllChildContext.find(Hash);183 if (It != AllChildContext.end()) {184 assert(It->second.getFuncName() == CalleeName &&185 "Hash collision for child context node");186 return &It->second;187 }188 189 if (!AllowCreate)190 return nullptr;191 192 ContextTrieNode &ACC = AllChildContext[Hash];193 ACC = ContextTrieNode(this, CalleeName, nullptr, CallSite);194 return &ACC;195}196 197// Profiler tracker than manages profiles and its associated context198SampleContextTracker::SampleContextTracker(199 SampleProfileMap &Profiles,200 const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap)201 : GUIDToFuncNameMap(GUIDToFuncNameMap) {202 for (auto &FuncSample : Profiles) {203 FunctionSamples *FSamples = &FuncSample.second;204 SampleContext Context = FuncSample.second.getContext();205 LLVM_DEBUG(dbgs() << "Tracking Context for function: " << Context.toString()206 << "\n");207 ContextTrieNode *NewNode = getOrCreateContextPath(Context, true);208 assert(!NewNode->getFunctionSamples() &&209 "New node can't have sample profile");210 NewNode->setFunctionSamples(FSamples);211 }212 populateFuncToCtxtMap();213}214 215void SampleContextTracker::populateFuncToCtxtMap() {216 for (auto *Node : *this) {217 FunctionSamples *FSamples = Node->getFunctionSamples();218 if (FSamples) {219 FSamples->getContext().setState(RawContext);220 setContextNode(FSamples, Node);221 FuncToCtxtProfiles[Node->getFuncName()].push_back(FSamples);222 }223 }224}225 226FunctionSamples *227SampleContextTracker::getCalleeContextSamplesFor(const CallBase &Inst,228 StringRef CalleeName) {229 LLVM_DEBUG(dbgs() << "Getting callee context for instr: " << Inst << "\n");230 DILocation *DIL = Inst.getDebugLoc();231 if (!DIL)232 return nullptr;233 234 CalleeName = FunctionSamples::getCanonicalFnName(CalleeName);235 236 FunctionId FName = getRepInFormat(CalleeName);237 238 // For indirect call, CalleeName will be empty, in which case the context239 // profile for callee with largest total samples will be returned.240 ContextTrieNode *CalleeContext = getCalleeContextFor(DIL, FName);241 if (CalleeContext) {242 FunctionSamples *FSamples = CalleeContext->getFunctionSamples();243 LLVM_DEBUG(if (FSamples) {244 dbgs() << " Callee context found: " << getContextString(CalleeContext)245 << "\n";246 });247 return FSamples;248 }249 250 return nullptr;251}252 253std::vector<const FunctionSamples *>254SampleContextTracker::getIndirectCalleeContextSamplesFor(255 const DILocation *DIL) {256 std::vector<const FunctionSamples *> R;257 if (!DIL)258 return R;259 260 ContextTrieNode *CallerNode = getContextFor(DIL);261 LineLocation CallSite = FunctionSamples::getCallSiteIdentifier(DIL);262 for (auto &It : CallerNode->getAllChildContext()) {263 ContextTrieNode &ChildNode = It.second;264 if (ChildNode.getCallSiteLoc() != CallSite)265 continue;266 if (FunctionSamples *CalleeSamples = ChildNode.getFunctionSamples())267 R.push_back(CalleeSamples);268 }269 270 return R;271}272 273FunctionSamples *274SampleContextTracker::getContextSamplesFor(const DILocation *DIL) {275 assert(DIL && "Expect non-null location");276 277 ContextTrieNode *ContextNode = getContextFor(DIL);278 if (!ContextNode)279 return nullptr;280 281 // We may have inlined callees during pre-LTO compilation, in which case282 // we need to rely on the inline stack from !dbg to mark context profile283 // as inlined, instead of `MarkContextSamplesInlined` during inlining.284 // Sample profile loader walks through all instructions to get profile,285 // which calls this function. So once that is done, all previously inlined286 // context profile should be marked properly.287 FunctionSamples *Samples = ContextNode->getFunctionSamples();288 if (Samples && ContextNode->getParentContext() != &RootContext)289 Samples->getContext().setState(InlinedContext);290 291 return Samples;292}293 294FunctionSamples *295SampleContextTracker::getContextSamplesFor(const SampleContext &Context) {296 ContextTrieNode *Node = getContextFor(Context);297 if (!Node)298 return nullptr;299 300 return Node->getFunctionSamples();301}302 303SampleContextTracker::ContextSamplesTy &304SampleContextTracker::getAllContextSamplesFor(const Function &Func) {305 StringRef CanonName = FunctionSamples::getCanonicalFnName(Func);306 return FuncToCtxtProfiles[getRepInFormat(CanonName)];307}308 309SampleContextTracker::ContextSamplesTy &310SampleContextTracker::getAllContextSamplesFor(StringRef Name) {311 return FuncToCtxtProfiles[getRepInFormat(Name)];312}313 314FunctionSamples *SampleContextTracker::getBaseSamplesFor(const Function &Func,315 bool MergeContext) {316 StringRef CanonName = FunctionSamples::getCanonicalFnName(Func);317 return getBaseSamplesFor(getRepInFormat(CanonName), MergeContext);318}319 320FunctionSamples *SampleContextTracker::getBaseSamplesFor(FunctionId Name,321 bool MergeContext) {322 LLVM_DEBUG(dbgs() << "Getting base profile for function: " << Name << "\n");323 324 // Base profile is top-level node (child of root node), so try to retrieve325 // existing top-level node for given function first. If it exists, it could be326 // that we've merged base profile before, or there's actually context-less327 // profile from the input (e.g. due to unreliable stack walking).328 ContextTrieNode *Node = getTopLevelContextNode(Name);329 if (MergeContext) {330 LLVM_DEBUG(dbgs() << " Merging context profile into base profile: " << Name331 << "\n");332 333 // We have profile for function under different contexts,334 // create synthetic base profile and merge context profiles335 // into base profile.336 for (auto *CSamples : FuncToCtxtProfiles[Name]) {337 SampleContext &Context = CSamples->getContext();338 // Skip inlined context profile and also don't re-merge any context339 if (Context.hasState(InlinedContext) || Context.hasState(MergedContext))340 continue;341 342 ContextTrieNode *FromNode = getContextNodeForProfile(CSamples);343 if (FromNode == Node)344 continue;345 346 ContextTrieNode &ToNode = promoteMergeContextSamplesTree(*FromNode);347 assert((!Node || Node == &ToNode) && "Expect only one base profile");348 Node = &ToNode;349 }350 }351 352 // Still no profile even after merge/promotion (if allowed)353 if (!Node)354 return nullptr;355 356 return Node->getFunctionSamples();357}358 359void SampleContextTracker::markContextSamplesInlined(360 const FunctionSamples *InlinedSamples) {361 assert(InlinedSamples && "Expect non-null inlined samples");362 LLVM_DEBUG(dbgs() << "Marking context profile as inlined: "363 << getContextString(*InlinedSamples) << "\n");364 InlinedSamples->getContext().setState(InlinedContext);365}366 367ContextTrieNode &SampleContextTracker::getRootContext() { return RootContext; }368 369void SampleContextTracker::promoteMergeContextSamplesTree(370 const Instruction &Inst, FunctionId CalleeName) {371 LLVM_DEBUG(dbgs() << "Promoting and merging context tree for instr: \n"372 << Inst << "\n");373 // Get the caller context for the call instruction, we don't use callee374 // name from call because there can be context from indirect calls too.375 DILocation *DIL = Inst.getDebugLoc();376 ContextTrieNode *CallerNode = getContextFor(DIL);377 if (!CallerNode)378 return;379 380 // Get the context that needs to be promoted381 LineLocation CallSite = FunctionSamples::getCallSiteIdentifier(DIL);382 // For indirect call, CalleeName will be empty, in which case we need to383 // promote all non-inlined child context profiles.384 if (CalleeName.empty()) {385 for (auto &It : CallerNode->getAllChildContext()) {386 ContextTrieNode *NodeToPromo = &It.second;387 if (CallSite != NodeToPromo->getCallSiteLoc())388 continue;389 FunctionSamples *FromSamples = NodeToPromo->getFunctionSamples();390 if (FromSamples && FromSamples->getContext().hasState(InlinedContext))391 continue;392 promoteMergeContextSamplesTree(*NodeToPromo);393 }394 return;395 }396 397 // Get the context for the given callee that needs to be promoted398 ContextTrieNode *NodeToPromo =399 CallerNode->getChildContext(CallSite, CalleeName);400 if (!NodeToPromo)401 return;402 403 promoteMergeContextSamplesTree(*NodeToPromo);404}405 406ContextTrieNode &SampleContextTracker::promoteMergeContextSamplesTree(407 ContextTrieNode &NodeToPromo) {408 // Promote the input node to be directly under root. This can happen409 // when we decided to not inline a function under context represented410 // by the input node. The promote and merge is then needed to reflect411 // the context profile in the base (context-less) profile.412 FunctionSamples *FromSamples = NodeToPromo.getFunctionSamples();413 assert(FromSamples && "Shouldn't promote a context without profile");414 (void)FromSamples; // Unused in release build.415 416 LLVM_DEBUG(dbgs() << " Found context tree root to promote: "417 << getContextString(&NodeToPromo) << "\n");418 419 assert(!FromSamples->getContext().hasState(InlinedContext) &&420 "Shouldn't promote inlined context profile");421 return promoteMergeContextSamplesTree(NodeToPromo, RootContext);422}423 424#ifndef NDEBUG425std::string426SampleContextTracker::getContextString(const FunctionSamples &FSamples) const {427 return getContextString(getContextNodeForProfile(&FSamples));428}429 430std::string431SampleContextTracker::getContextString(ContextTrieNode *Node) const {432 SampleContextFrameVector Res;433 if (Node == &RootContext)434 return std::string();435 Res.emplace_back(Node->getFuncName(), LineLocation(0, 0));436 437 ContextTrieNode *PreNode = Node;438 Node = Node->getParentContext();439 while (Node && Node != &RootContext) {440 Res.emplace_back(Node->getFuncName(), PreNode->getCallSiteLoc());441 PreNode = Node;442 Node = Node->getParentContext();443 }444 445 std::reverse(Res.begin(), Res.end());446 447 return SampleContext::getContextString(Res);448}449#endif450 451void SampleContextTracker::dump() { RootContext.dumpTree(); }452 453StringRef SampleContextTracker::getFuncNameFor(ContextTrieNode *Node) const {454 if (!FunctionSamples::UseMD5)455 return Node->getFuncName().stringRef();456 assert(GUIDToFuncNameMap && "GUIDToFuncNameMap needs to be populated first");457 return GUIDToFuncNameMap->lookup(Node->getFuncName().getHashCode());458}459 460ContextTrieNode *461SampleContextTracker::getContextFor(const SampleContext &Context) {462 return getOrCreateContextPath(Context, false);463}464 465ContextTrieNode *466SampleContextTracker::getCalleeContextFor(const DILocation *DIL,467 FunctionId CalleeName) {468 assert(DIL && "Expect non-null location");469 470 ContextTrieNode *CallContext = getContextFor(DIL);471 if (!CallContext)472 return nullptr;473 474 // When CalleeName is empty, the child context profile with max475 // total samples will be returned.476 return CallContext->getChildContext(477 FunctionSamples::getCallSiteIdentifier(DIL), CalleeName);478}479 480ContextTrieNode *SampleContextTracker::getContextFor(const DILocation *DIL) {481 assert(DIL && "Expect non-null location");482 SmallVector<std::pair<LineLocation, FunctionId>, 10> S;483 484 // Use C++ linkage name if possible.485 const DILocation *PrevDIL = DIL;486 for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {487 StringRef Name = PrevDIL->getScope()->getSubprogram()->getLinkageName();488 if (Name.empty())489 Name = PrevDIL->getScope()->getSubprogram()->getName();490 S.push_back(491 std::make_pair(FunctionSamples::getCallSiteIdentifier(DIL),492 getRepInFormat(Name)));493 PrevDIL = DIL;494 }495 496 // Push root node, note that root node like main may only497 // a name, but not linkage name.498 StringRef RootName = PrevDIL->getScope()->getSubprogram()->getLinkageName();499 if (RootName.empty())500 RootName = PrevDIL->getScope()->getSubprogram()->getName();501 S.push_back(std::make_pair(LineLocation(0, 0),502 getRepInFormat(RootName)));503 504 ContextTrieNode *ContextNode = &RootContext;505 int I = S.size();506 while (--I >= 0 && ContextNode) {507 LineLocation &CallSite = S[I].first;508 FunctionId CalleeName = S[I].second;509 ContextNode = ContextNode->getChildContext(CallSite, CalleeName);510 }511 512 if (I < 0)513 return ContextNode;514 515 return nullptr;516}517 518ContextTrieNode *519SampleContextTracker::getOrCreateContextPath(const SampleContext &Context,520 bool AllowCreate) {521 ContextTrieNode *ContextNode = &RootContext;522 LineLocation CallSiteLoc(0, 0);523 524 for (const auto &Callsite : Context.getContextFrames()) {525 // Create child node at parent line/disc location526 if (AllowCreate) {527 ContextNode =528 ContextNode->getOrCreateChildContext(CallSiteLoc, Callsite.Func);529 } else {530 ContextNode =531 ContextNode->getChildContext(CallSiteLoc, Callsite.Func);532 }533 CallSiteLoc = Callsite.Location;534 }535 536 assert((!AllowCreate || ContextNode) &&537 "Node must exist if creation is allowed");538 return ContextNode;539}540 541ContextTrieNode *542SampleContextTracker::getTopLevelContextNode(FunctionId FName) {543 assert(!FName.empty() && "Top level node query must provide valid name");544 return RootContext.getChildContext(LineLocation(0, 0), FName);545}546 547ContextTrieNode &548SampleContextTracker::addTopLevelContextNode(FunctionId FName) {549 assert(!getTopLevelContextNode(FName) && "Node to add must not exist");550 return *RootContext.getOrCreateChildContext(LineLocation(0, 0), FName);551}552 553void SampleContextTracker::mergeContextNode(ContextTrieNode &FromNode,554 ContextTrieNode &ToNode) {555 FunctionSamples *FromSamples = FromNode.getFunctionSamples();556 FunctionSamples *ToSamples = ToNode.getFunctionSamples();557 if (FromSamples && ToSamples) {558 // Merge/duplicate FromSamples into ToSamples559 ToSamples->merge(*FromSamples);560 ToSamples->getContext().setState(SyntheticContext);561 FromSamples->getContext().setState(MergedContext);562 if (FromSamples->getContext().hasAttribute(ContextShouldBeInlined))563 ToSamples->getContext().setAttribute(ContextShouldBeInlined);564 } else if (FromSamples) {565 // Transfer FromSamples from FromNode to ToNode566 ToNode.setFunctionSamples(FromSamples);567 setContextNode(FromSamples, &ToNode);568 FromSamples->getContext().setState(SyntheticContext);569 }570}571 572ContextTrieNode &SampleContextTracker::promoteMergeContextSamplesTree(573 ContextTrieNode &FromNode, ContextTrieNode &ToNodeParent) {574 575 // Ignore call site location if destination is top level under root576 LineLocation NewCallSiteLoc = LineLocation(0, 0);577 LineLocation OldCallSiteLoc = FromNode.getCallSiteLoc();578 ContextTrieNode &FromNodeParent = *FromNode.getParentContext();579 ContextTrieNode *ToNode = nullptr;580 bool MoveToRoot = (&ToNodeParent == &RootContext);581 if (!MoveToRoot) {582 NewCallSiteLoc = OldCallSiteLoc;583 }584 585 // Locate destination node, create/move if not existing586 ToNode = ToNodeParent.getChildContext(NewCallSiteLoc, FromNode.getFuncName());587 if (!ToNode) {588 // Do not delete node to move from its parent here because589 // caller is iterating over children of that parent node.590 ToNode =591 &moveContextSamples(ToNodeParent, NewCallSiteLoc, std::move(FromNode));592 LLVM_DEBUG({593 dbgs() << " Context promoted and merged to: " << getContextString(ToNode)594 << "\n";595 });596 } else {597 // Destination node exists, merge samples for the context tree598 mergeContextNode(FromNode, *ToNode);599 LLVM_DEBUG({600 if (ToNode->getFunctionSamples())601 dbgs() << " Context promoted and merged to: "602 << getContextString(ToNode) << "\n";603 });604 605 // Recursively promote and merge children606 for (auto &It : FromNode.getAllChildContext()) {607 ContextTrieNode &FromChildNode = It.second;608 promoteMergeContextSamplesTree(FromChildNode, *ToNode);609 }610 611 // Remove children once they're all merged612 FromNode.getAllChildContext().clear();613 }614 615 // For root of subtree, remove itself from old parent too616 if (MoveToRoot)617 FromNodeParent.removeChildContext(OldCallSiteLoc, ToNode->getFuncName());618 619 return *ToNode;620}621 622void SampleContextTracker::createContextLessProfileMap(623 SampleProfileMap &ContextLessProfiles) {624 for (auto *Node : *this) {625 FunctionSamples *FProfile = Node->getFunctionSamples();626 // Profile's context can be empty, use ContextNode's func name.627 if (FProfile)628 ContextLessProfiles.create(Node->getFuncName()).merge(*FProfile);629 }630}631} // namespace llvm632