1e8d8bef9SDimitry Andric //===- SampleContextTracker.cpp - Context-sensitive Profile Tracker -------===// 2e8d8bef9SDimitry Andric // 3e8d8bef9SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4e8d8bef9SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5e8d8bef9SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6e8d8bef9SDimitry Andric // 7e8d8bef9SDimitry Andric //===----------------------------------------------------------------------===// 8e8d8bef9SDimitry Andric // 9e8d8bef9SDimitry Andric // This file implements the SampleContextTracker used by CSSPGO. 10e8d8bef9SDimitry Andric // 11e8d8bef9SDimitry Andric //===----------------------------------------------------------------------===// 12e8d8bef9SDimitry Andric 13e8d8bef9SDimitry Andric #include "llvm/Transforms/IPO/SampleContextTracker.h" 14e8d8bef9SDimitry Andric #include "llvm/ADT/StringRef.h" 15e8d8bef9SDimitry Andric #include "llvm/IR/DebugInfoMetadata.h" 1681ad6265SDimitry Andric #include "llvm/IR/InstrTypes.h" 1781ad6265SDimitry Andric #include "llvm/IR/Instruction.h" 18e8d8bef9SDimitry Andric #include "llvm/ProfileData/SampleProf.h" 19e8d8bef9SDimitry Andric #include <map> 20e8d8bef9SDimitry Andric #include <queue> 21e8d8bef9SDimitry Andric #include <vector> 22e8d8bef9SDimitry Andric 23e8d8bef9SDimitry Andric using namespace llvm; 24e8d8bef9SDimitry Andric using namespace sampleprof; 25e8d8bef9SDimitry Andric 26e8d8bef9SDimitry Andric #define DEBUG_TYPE "sample-context-tracker" 27e8d8bef9SDimitry Andric 28e8d8bef9SDimitry Andric namespace llvm { 29e8d8bef9SDimitry Andric 30e8d8bef9SDimitry Andric ContextTrieNode *ContextTrieNode::getChildContext(const LineLocation &CallSite, 315f757f3fSDimitry Andric FunctionId CalleeName) { 32e8d8bef9SDimitry Andric if (CalleeName.empty()) 33d409305fSDimitry Andric return getHottestChildContext(CallSite); 34e8d8bef9SDimitry Andric 350eae32dcSDimitry Andric uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite); 36e8d8bef9SDimitry Andric auto It = AllChildContext.find(Hash); 37e8d8bef9SDimitry Andric if (It != AllChildContext.end()) 38e8d8bef9SDimitry Andric return &It->second; 39e8d8bef9SDimitry Andric return nullptr; 40e8d8bef9SDimitry Andric } 41e8d8bef9SDimitry Andric 42e8d8bef9SDimitry Andric ContextTrieNode * 43d409305fSDimitry Andric ContextTrieNode::getHottestChildContext(const LineLocation &CallSite) { 44e8d8bef9SDimitry Andric // CSFDO-TODO: This could be slow, change AllChildContext so we can 45e8d8bef9SDimitry Andric // do point look up for child node by call site alone. 46d409305fSDimitry Andric // Retrieve the child node with max count for indirect call 47e8d8bef9SDimitry Andric ContextTrieNode *ChildNodeRet = nullptr; 48d409305fSDimitry Andric uint64_t MaxCalleeSamples = 0; 49e8d8bef9SDimitry Andric for (auto &It : AllChildContext) { 50e8d8bef9SDimitry Andric ContextTrieNode &ChildNode = It.second; 51d409305fSDimitry Andric if (ChildNode.CallSiteLoc != CallSite) 52d409305fSDimitry Andric continue; 53d409305fSDimitry Andric FunctionSamples *Samples = ChildNode.getFunctionSamples(); 54d409305fSDimitry Andric if (!Samples) 55d409305fSDimitry Andric continue; 56d409305fSDimitry Andric if (Samples->getTotalSamples() > MaxCalleeSamples) { 57e8d8bef9SDimitry Andric ChildNodeRet = &ChildNode; 58d409305fSDimitry Andric MaxCalleeSamples = Samples->getTotalSamples(); 59e8d8bef9SDimitry Andric } 60e8d8bef9SDimitry Andric } 61e8d8bef9SDimitry Andric 62e8d8bef9SDimitry Andric return ChildNodeRet; 63e8d8bef9SDimitry Andric } 64e8d8bef9SDimitry Andric 6581ad6265SDimitry Andric ContextTrieNode & 6681ad6265SDimitry Andric SampleContextTracker::moveContextSamples(ContextTrieNode &ToNodeParent, 6781ad6265SDimitry Andric const LineLocation &CallSite, 6881ad6265SDimitry Andric ContextTrieNode &&NodeToMove) { 690eae32dcSDimitry Andric uint64_t Hash = 700eae32dcSDimitry Andric FunctionSamples::getCallSiteHash(NodeToMove.getFuncName(), CallSite); 7181ad6265SDimitry Andric std::map<uint64_t, ContextTrieNode> &AllChildContext = 7281ad6265SDimitry Andric ToNodeParent.getAllChildContext(); 73e8d8bef9SDimitry Andric assert(!AllChildContext.count(Hash) && "Node to remove must exist"); 74e8d8bef9SDimitry Andric AllChildContext[Hash] = NodeToMove; 75e8d8bef9SDimitry Andric ContextTrieNode &NewNode = AllChildContext[Hash]; 7681ad6265SDimitry Andric NewNode.setCallSiteLoc(CallSite); 77e8d8bef9SDimitry Andric 78e8d8bef9SDimitry Andric // Walk through nodes in the moved the subtree, and update 79e8d8bef9SDimitry Andric // FunctionSamples' context as for the context promotion. 80e8d8bef9SDimitry Andric // We also need to set new parant link for all children. 81e8d8bef9SDimitry Andric std::queue<ContextTrieNode *> NodeToUpdate; 8281ad6265SDimitry Andric NewNode.setParentContext(&ToNodeParent); 83e8d8bef9SDimitry Andric NodeToUpdate.push(&NewNode); 84e8d8bef9SDimitry Andric 85e8d8bef9SDimitry Andric while (!NodeToUpdate.empty()) { 86e8d8bef9SDimitry Andric ContextTrieNode *Node = NodeToUpdate.front(); 87e8d8bef9SDimitry Andric NodeToUpdate.pop(); 88e8d8bef9SDimitry Andric FunctionSamples *FSamples = Node->getFunctionSamples(); 89e8d8bef9SDimitry Andric 90e8d8bef9SDimitry Andric if (FSamples) { 9181ad6265SDimitry Andric setContextNode(FSamples, Node); 92e8d8bef9SDimitry Andric FSamples->getContext().setState(SyntheticContext); 93e8d8bef9SDimitry Andric } 94e8d8bef9SDimitry Andric 95e8d8bef9SDimitry Andric for (auto &It : Node->getAllChildContext()) { 96e8d8bef9SDimitry Andric ContextTrieNode *ChildNode = &It.second; 97e8d8bef9SDimitry Andric ChildNode->setParentContext(Node); 98e8d8bef9SDimitry Andric NodeToUpdate.push(ChildNode); 99e8d8bef9SDimitry Andric } 100e8d8bef9SDimitry Andric } 101e8d8bef9SDimitry Andric 102e8d8bef9SDimitry Andric return NewNode; 103e8d8bef9SDimitry Andric } 104e8d8bef9SDimitry Andric 105e8d8bef9SDimitry Andric void ContextTrieNode::removeChildContext(const LineLocation &CallSite, 1065f757f3fSDimitry Andric FunctionId CalleeName) { 1070eae32dcSDimitry Andric uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite); 108e8d8bef9SDimitry Andric // Note this essentially calls dtor and destroys that child context 109e8d8bef9SDimitry Andric AllChildContext.erase(Hash); 110e8d8bef9SDimitry Andric } 111e8d8bef9SDimitry Andric 112349cc55cSDimitry Andric std::map<uint64_t, ContextTrieNode> &ContextTrieNode::getAllChildContext() { 113e8d8bef9SDimitry Andric return AllChildContext; 114e8d8bef9SDimitry Andric } 115e8d8bef9SDimitry Andric 1165f757f3fSDimitry Andric FunctionId ContextTrieNode::getFuncName() const { return FuncName; } 117e8d8bef9SDimitry Andric 118e8d8bef9SDimitry Andric FunctionSamples *ContextTrieNode::getFunctionSamples() const { 119e8d8bef9SDimitry Andric return FuncSamples; 120e8d8bef9SDimitry Andric } 121e8d8bef9SDimitry Andric 122e8d8bef9SDimitry Andric void ContextTrieNode::setFunctionSamples(FunctionSamples *FSamples) { 123e8d8bef9SDimitry Andric FuncSamples = FSamples; 124e8d8bef9SDimitry Andric } 125e8d8bef9SDimitry Andric 126bdd1243dSDimitry Andric std::optional<uint32_t> ContextTrieNode::getFunctionSize() const { 127bdd1243dSDimitry Andric return FuncSize; 128bdd1243dSDimitry Andric } 129349cc55cSDimitry Andric 130349cc55cSDimitry Andric void ContextTrieNode::addFunctionSize(uint32_t FSize) { 13181ad6265SDimitry Andric if (!FuncSize) 132349cc55cSDimitry Andric FuncSize = 0; 133349cc55cSDimitry Andric 134bdd1243dSDimitry Andric FuncSize = *FuncSize + FSize; 135349cc55cSDimitry Andric } 136349cc55cSDimitry Andric 137e8d8bef9SDimitry Andric LineLocation ContextTrieNode::getCallSiteLoc() const { return CallSiteLoc; } 138e8d8bef9SDimitry Andric 139e8d8bef9SDimitry Andric ContextTrieNode *ContextTrieNode::getParentContext() const { 140e8d8bef9SDimitry Andric return ParentContext; 141e8d8bef9SDimitry Andric } 142e8d8bef9SDimitry Andric 143e8d8bef9SDimitry Andric void ContextTrieNode::setParentContext(ContextTrieNode *Parent) { 144e8d8bef9SDimitry Andric ParentContext = Parent; 145e8d8bef9SDimitry Andric } 146e8d8bef9SDimitry Andric 14781ad6265SDimitry Andric void ContextTrieNode::setCallSiteLoc(const LineLocation &Loc) { 14881ad6265SDimitry Andric CallSiteLoc = Loc; 14981ad6265SDimitry Andric } 15081ad6265SDimitry Andric 151349cc55cSDimitry Andric void ContextTrieNode::dumpNode() { 152e8d8bef9SDimitry Andric dbgs() << "Node: " << FuncName << "\n" 153e8d8bef9SDimitry Andric << " Callsite: " << CallSiteLoc << "\n" 154349cc55cSDimitry Andric << " Size: " << FuncSize << "\n" 155e8d8bef9SDimitry Andric << " Children:\n"; 156e8d8bef9SDimitry Andric 157e8d8bef9SDimitry Andric for (auto &It : AllChildContext) { 158e8d8bef9SDimitry Andric dbgs() << " Node: " << It.second.getFuncName() << "\n"; 159e8d8bef9SDimitry Andric } 160e8d8bef9SDimitry Andric } 161e8d8bef9SDimitry Andric 162349cc55cSDimitry Andric void ContextTrieNode::dumpTree() { 163349cc55cSDimitry Andric dbgs() << "Context Profile Tree:\n"; 164349cc55cSDimitry Andric std::queue<ContextTrieNode *> NodeQueue; 165349cc55cSDimitry Andric NodeQueue.push(this); 166349cc55cSDimitry Andric 167349cc55cSDimitry Andric while (!NodeQueue.empty()) { 168349cc55cSDimitry Andric ContextTrieNode *Node = NodeQueue.front(); 169349cc55cSDimitry Andric NodeQueue.pop(); 170349cc55cSDimitry Andric Node->dumpNode(); 171349cc55cSDimitry Andric 172349cc55cSDimitry Andric for (auto &It : Node->getAllChildContext()) { 173349cc55cSDimitry Andric ContextTrieNode *ChildNode = &It.second; 174349cc55cSDimitry Andric NodeQueue.push(ChildNode); 175349cc55cSDimitry Andric } 176349cc55cSDimitry Andric } 177349cc55cSDimitry Andric } 178349cc55cSDimitry Andric 179e8d8bef9SDimitry Andric ContextTrieNode *ContextTrieNode::getOrCreateChildContext( 1805f757f3fSDimitry Andric const LineLocation &CallSite, FunctionId CalleeName, bool AllowCreate) { 1810eae32dcSDimitry Andric uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite); 182e8d8bef9SDimitry Andric auto It = AllChildContext.find(Hash); 183e8d8bef9SDimitry Andric if (It != AllChildContext.end()) { 184e8d8bef9SDimitry Andric assert(It->second.getFuncName() == CalleeName && 185e8d8bef9SDimitry Andric "Hash collision for child context node"); 186e8d8bef9SDimitry Andric return &It->second; 187e8d8bef9SDimitry Andric } 188e8d8bef9SDimitry Andric 189e8d8bef9SDimitry Andric if (!AllowCreate) 190e8d8bef9SDimitry Andric return nullptr; 191e8d8bef9SDimitry Andric 192e8d8bef9SDimitry Andric AllChildContext[Hash] = ContextTrieNode(this, CalleeName, nullptr, CallSite); 193e8d8bef9SDimitry Andric return &AllChildContext[Hash]; 194e8d8bef9SDimitry Andric } 195e8d8bef9SDimitry Andric 196e8d8bef9SDimitry Andric // Profiler tracker than manages profiles and its associated context 197e8d8bef9SDimitry Andric SampleContextTracker::SampleContextTracker( 198349cc55cSDimitry Andric SampleProfileMap &Profiles, 199349cc55cSDimitry Andric const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap) 200349cc55cSDimitry Andric : GUIDToFuncNameMap(GUIDToFuncNameMap) { 201e8d8bef9SDimitry Andric for (auto &FuncSample : Profiles) { 202e8d8bef9SDimitry Andric FunctionSamples *FSamples = &FuncSample.second; 2035f757f3fSDimitry Andric SampleContext Context = FuncSample.second.getContext(); 204349cc55cSDimitry Andric LLVM_DEBUG(dbgs() << "Tracking Context for function: " << Context.toString() 205349cc55cSDimitry Andric << "\n"); 206e8d8bef9SDimitry Andric ContextTrieNode *NewNode = getOrCreateContextPath(Context, true); 207e8d8bef9SDimitry Andric assert(!NewNode->getFunctionSamples() && 208e8d8bef9SDimitry Andric "New node can't have sample profile"); 209e8d8bef9SDimitry Andric NewNode->setFunctionSamples(FSamples); 210e8d8bef9SDimitry Andric } 21181ad6265SDimitry Andric populateFuncToCtxtMap(); 21281ad6265SDimitry Andric } 21381ad6265SDimitry Andric 21481ad6265SDimitry Andric void SampleContextTracker::populateFuncToCtxtMap() { 21581ad6265SDimitry Andric for (auto *Node : *this) { 21681ad6265SDimitry Andric FunctionSamples *FSamples = Node->getFunctionSamples(); 21781ad6265SDimitry Andric if (FSamples) { 21881ad6265SDimitry Andric FSamples->getContext().setState(RawContext); 21981ad6265SDimitry Andric setContextNode(FSamples, Node); 22081ad6265SDimitry Andric FuncToCtxtProfiles[Node->getFuncName()].push_back(FSamples); 22181ad6265SDimitry Andric } 22281ad6265SDimitry Andric } 223e8d8bef9SDimitry Andric } 224e8d8bef9SDimitry Andric 225e8d8bef9SDimitry Andric FunctionSamples * 226e8d8bef9SDimitry Andric SampleContextTracker::getCalleeContextSamplesFor(const CallBase &Inst, 227e8d8bef9SDimitry Andric StringRef CalleeName) { 228e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << "Getting callee context for instr: " << Inst << "\n"); 229e8d8bef9SDimitry Andric DILocation *DIL = Inst.getDebugLoc(); 230e8d8bef9SDimitry Andric if (!DIL) 231e8d8bef9SDimitry Andric return nullptr; 232e8d8bef9SDimitry Andric 233fe6060f1SDimitry Andric CalleeName = FunctionSamples::getCanonicalFnName(CalleeName); 2345f757f3fSDimitry Andric 2355f757f3fSDimitry Andric FunctionId FName = getRepInFormat(CalleeName); 236fe6060f1SDimitry Andric 237d409305fSDimitry Andric // For indirect call, CalleeName will be empty, in which case the context 238d409305fSDimitry Andric // profile for callee with largest total samples will be returned. 2395f757f3fSDimitry Andric ContextTrieNode *CalleeContext = getCalleeContextFor(DIL, FName); 240e8d8bef9SDimitry Andric if (CalleeContext) { 241e8d8bef9SDimitry Andric FunctionSamples *FSamples = CalleeContext->getFunctionSamples(); 242e8d8bef9SDimitry Andric LLVM_DEBUG(if (FSamples) { 24381ad6265SDimitry Andric dbgs() << " Callee context found: " << getContextString(CalleeContext) 244349cc55cSDimitry Andric << "\n"; 245e8d8bef9SDimitry Andric }); 246e8d8bef9SDimitry Andric return FSamples; 247e8d8bef9SDimitry Andric } 248e8d8bef9SDimitry Andric 249e8d8bef9SDimitry Andric return nullptr; 250e8d8bef9SDimitry Andric } 251e8d8bef9SDimitry Andric 252d409305fSDimitry Andric std::vector<const FunctionSamples *> 253d409305fSDimitry Andric SampleContextTracker::getIndirectCalleeContextSamplesFor( 254d409305fSDimitry Andric const DILocation *DIL) { 255d409305fSDimitry Andric std::vector<const FunctionSamples *> R; 256d409305fSDimitry Andric if (!DIL) 257d409305fSDimitry Andric return R; 258d409305fSDimitry Andric 259d409305fSDimitry Andric ContextTrieNode *CallerNode = getContextFor(DIL); 260d409305fSDimitry Andric LineLocation CallSite = FunctionSamples::getCallSiteIdentifier(DIL); 261d409305fSDimitry Andric for (auto &It : CallerNode->getAllChildContext()) { 262d409305fSDimitry Andric ContextTrieNode &ChildNode = It.second; 263d409305fSDimitry Andric if (ChildNode.getCallSiteLoc() != CallSite) 264d409305fSDimitry Andric continue; 265d409305fSDimitry Andric if (FunctionSamples *CalleeSamples = ChildNode.getFunctionSamples()) 266d409305fSDimitry Andric R.push_back(CalleeSamples); 267d409305fSDimitry Andric } 268d409305fSDimitry Andric 269d409305fSDimitry Andric return R; 270d409305fSDimitry Andric } 271d409305fSDimitry Andric 272e8d8bef9SDimitry Andric FunctionSamples * 273e8d8bef9SDimitry Andric SampleContextTracker::getContextSamplesFor(const DILocation *DIL) { 274e8d8bef9SDimitry Andric assert(DIL && "Expect non-null location"); 275e8d8bef9SDimitry Andric 276e8d8bef9SDimitry Andric ContextTrieNode *ContextNode = getContextFor(DIL); 277e8d8bef9SDimitry Andric if (!ContextNode) 278e8d8bef9SDimitry Andric return nullptr; 279e8d8bef9SDimitry Andric 280e8d8bef9SDimitry Andric // We may have inlined callees during pre-LTO compilation, in which case 281e8d8bef9SDimitry Andric // we need to rely on the inline stack from !dbg to mark context profile 282e8d8bef9SDimitry Andric // as inlined, instead of `MarkContextSamplesInlined` during inlining. 283e8d8bef9SDimitry Andric // Sample profile loader walks through all instructions to get profile, 284e8d8bef9SDimitry Andric // which calls this function. So once that is done, all previously inlined 285e8d8bef9SDimitry Andric // context profile should be marked properly. 286e8d8bef9SDimitry Andric FunctionSamples *Samples = ContextNode->getFunctionSamples(); 287e8d8bef9SDimitry Andric if (Samples && ContextNode->getParentContext() != &RootContext) 288e8d8bef9SDimitry Andric Samples->getContext().setState(InlinedContext); 289e8d8bef9SDimitry Andric 290e8d8bef9SDimitry Andric return Samples; 291e8d8bef9SDimitry Andric } 292e8d8bef9SDimitry Andric 293e8d8bef9SDimitry Andric FunctionSamples * 294e8d8bef9SDimitry Andric SampleContextTracker::getContextSamplesFor(const SampleContext &Context) { 295e8d8bef9SDimitry Andric ContextTrieNode *Node = getContextFor(Context); 296e8d8bef9SDimitry Andric if (!Node) 297e8d8bef9SDimitry Andric return nullptr; 298e8d8bef9SDimitry Andric 299e8d8bef9SDimitry Andric return Node->getFunctionSamples(); 300e8d8bef9SDimitry Andric } 301e8d8bef9SDimitry Andric 302d409305fSDimitry Andric SampleContextTracker::ContextSamplesTy & 303d409305fSDimitry Andric SampleContextTracker::getAllContextSamplesFor(const Function &Func) { 304d409305fSDimitry Andric StringRef CanonName = FunctionSamples::getCanonicalFnName(Func); 3055f757f3fSDimitry Andric return FuncToCtxtProfiles[getRepInFormat(CanonName)]; 306d409305fSDimitry Andric } 307d409305fSDimitry Andric 308d409305fSDimitry Andric SampleContextTracker::ContextSamplesTy & 309d409305fSDimitry Andric SampleContextTracker::getAllContextSamplesFor(StringRef Name) { 3105f757f3fSDimitry Andric return FuncToCtxtProfiles[getRepInFormat(Name)]; 311d409305fSDimitry Andric } 312d409305fSDimitry Andric 313e8d8bef9SDimitry Andric FunctionSamples *SampleContextTracker::getBaseSamplesFor(const Function &Func, 314e8d8bef9SDimitry Andric bool MergeContext) { 315e8d8bef9SDimitry Andric StringRef CanonName = FunctionSamples::getCanonicalFnName(Func); 3165f757f3fSDimitry Andric return getBaseSamplesFor(getRepInFormat(CanonName), MergeContext); 317e8d8bef9SDimitry Andric } 318e8d8bef9SDimitry Andric 3195f757f3fSDimitry Andric FunctionSamples *SampleContextTracker::getBaseSamplesFor(FunctionId Name, 320e8d8bef9SDimitry Andric bool MergeContext) { 321e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << "Getting base profile for function: " << Name << "\n"); 322349cc55cSDimitry Andric 323e8d8bef9SDimitry Andric // Base profile is top-level node (child of root node), so try to retrieve 324e8d8bef9SDimitry Andric // existing top-level node for given function first. If it exists, it could be 325e8d8bef9SDimitry Andric // that we've merged base profile before, or there's actually context-less 326e8d8bef9SDimitry Andric // profile from the input (e.g. due to unreliable stack walking). 327e8d8bef9SDimitry Andric ContextTrieNode *Node = getTopLevelContextNode(Name); 328e8d8bef9SDimitry Andric if (MergeContext) { 329e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << " Merging context profile into base profile: " << Name 330e8d8bef9SDimitry Andric << "\n"); 331e8d8bef9SDimitry Andric 332e8d8bef9SDimitry Andric // We have profile for function under different contexts, 333e8d8bef9SDimitry Andric // create synthetic base profile and merge context profiles 334e8d8bef9SDimitry Andric // into base profile. 335fe6060f1SDimitry Andric for (auto *CSamples : FuncToCtxtProfiles[Name]) { 336e8d8bef9SDimitry Andric SampleContext &Context = CSamples->getContext(); 337e8d8bef9SDimitry Andric // Skip inlined context profile and also don't re-merge any context 338e8d8bef9SDimitry Andric if (Context.hasState(InlinedContext) || Context.hasState(MergedContext)) 339e8d8bef9SDimitry Andric continue; 340e8d8bef9SDimitry Andric 34181ad6265SDimitry Andric ContextTrieNode *FromNode = getContextNodeForProfile(CSamples); 342349cc55cSDimitry Andric if (FromNode == Node) 343349cc55cSDimitry Andric continue; 344349cc55cSDimitry Andric 345e8d8bef9SDimitry Andric ContextTrieNode &ToNode = promoteMergeContextSamplesTree(*FromNode); 346e8d8bef9SDimitry Andric assert((!Node || Node == &ToNode) && "Expect only one base profile"); 347e8d8bef9SDimitry Andric Node = &ToNode; 348e8d8bef9SDimitry Andric } 349e8d8bef9SDimitry Andric } 350e8d8bef9SDimitry Andric 351e8d8bef9SDimitry Andric // Still no profile even after merge/promotion (if allowed) 352e8d8bef9SDimitry Andric if (!Node) 353e8d8bef9SDimitry Andric return nullptr; 354e8d8bef9SDimitry Andric 355e8d8bef9SDimitry Andric return Node->getFunctionSamples(); 356e8d8bef9SDimitry Andric } 357e8d8bef9SDimitry Andric 358e8d8bef9SDimitry Andric void SampleContextTracker::markContextSamplesInlined( 359e8d8bef9SDimitry Andric const FunctionSamples *InlinedSamples) { 360e8d8bef9SDimitry Andric assert(InlinedSamples && "Expect non-null inlined samples"); 361e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << "Marking context profile as inlined: " 36281ad6265SDimitry Andric << getContextString(*InlinedSamples) << "\n"); 363e8d8bef9SDimitry Andric InlinedSamples->getContext().setState(InlinedContext); 364e8d8bef9SDimitry Andric } 365e8d8bef9SDimitry Andric 366fe6060f1SDimitry Andric ContextTrieNode &SampleContextTracker::getRootContext() { return RootContext; } 367fe6060f1SDimitry Andric 368e8d8bef9SDimitry Andric void SampleContextTracker::promoteMergeContextSamplesTree( 3695f757f3fSDimitry Andric const Instruction &Inst, FunctionId CalleeName) { 370e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << "Promoting and merging context tree for instr: \n" 371e8d8bef9SDimitry Andric << Inst << "\n"); 372e8d8bef9SDimitry Andric // Get the caller context for the call instruction, we don't use callee 373e8d8bef9SDimitry Andric // name from call because there can be context from indirect calls too. 374e8d8bef9SDimitry Andric DILocation *DIL = Inst.getDebugLoc(); 375e8d8bef9SDimitry Andric ContextTrieNode *CallerNode = getContextFor(DIL); 376e8d8bef9SDimitry Andric if (!CallerNode) 377e8d8bef9SDimitry Andric return; 378e8d8bef9SDimitry Andric 379e8d8bef9SDimitry Andric // Get the context that needs to be promoted 380d409305fSDimitry Andric LineLocation CallSite = FunctionSamples::getCallSiteIdentifier(DIL); 381d409305fSDimitry Andric // For indirect call, CalleeName will be empty, in which case we need to 382d409305fSDimitry Andric // promote all non-inlined child context profiles. 383d409305fSDimitry Andric if (CalleeName.empty()) { 384d409305fSDimitry Andric for (auto &It : CallerNode->getAllChildContext()) { 385d409305fSDimitry Andric ContextTrieNode *NodeToPromo = &It.second; 386d409305fSDimitry Andric if (CallSite != NodeToPromo->getCallSiteLoc()) 387d409305fSDimitry Andric continue; 388d409305fSDimitry Andric FunctionSamples *FromSamples = NodeToPromo->getFunctionSamples(); 389d409305fSDimitry Andric if (FromSamples && FromSamples->getContext().hasState(InlinedContext)) 390d409305fSDimitry Andric continue; 391d409305fSDimitry Andric promoteMergeContextSamplesTree(*NodeToPromo); 392d409305fSDimitry Andric } 393d409305fSDimitry Andric return; 394d409305fSDimitry Andric } 395d409305fSDimitry Andric 396d409305fSDimitry Andric // Get the context for the given callee that needs to be promoted 397e8d8bef9SDimitry Andric ContextTrieNode *NodeToPromo = 398e8d8bef9SDimitry Andric CallerNode->getChildContext(CallSite, CalleeName); 399e8d8bef9SDimitry Andric if (!NodeToPromo) 400e8d8bef9SDimitry Andric return; 401e8d8bef9SDimitry Andric 402e8d8bef9SDimitry Andric promoteMergeContextSamplesTree(*NodeToPromo); 403e8d8bef9SDimitry Andric } 404e8d8bef9SDimitry Andric 405e8d8bef9SDimitry Andric ContextTrieNode &SampleContextTracker::promoteMergeContextSamplesTree( 406e8d8bef9SDimitry Andric ContextTrieNode &NodeToPromo) { 407e8d8bef9SDimitry Andric // Promote the input node to be directly under root. This can happen 408e8d8bef9SDimitry Andric // when we decided to not inline a function under context represented 409e8d8bef9SDimitry Andric // by the input node. The promote and merge is then needed to reflect 410e8d8bef9SDimitry Andric // the context profile in the base (context-less) profile. 411e8d8bef9SDimitry Andric FunctionSamples *FromSamples = NodeToPromo.getFunctionSamples(); 412e8d8bef9SDimitry Andric assert(FromSamples && "Shouldn't promote a context without profile"); 41381ad6265SDimitry Andric (void)FromSamples; // Unused in release build. 41481ad6265SDimitry Andric 415e8d8bef9SDimitry Andric LLVM_DEBUG(dbgs() << " Found context tree root to promote: " 41681ad6265SDimitry Andric << getContextString(&NodeToPromo) << "\n"); 417e8d8bef9SDimitry Andric 418d409305fSDimitry Andric assert(!FromSamples->getContext().hasState(InlinedContext) && 419d409305fSDimitry Andric "Shouldn't promote inlined context profile"); 42081ad6265SDimitry Andric return promoteMergeContextSamplesTree(NodeToPromo, RootContext); 421e8d8bef9SDimitry Andric } 422e8d8bef9SDimitry Andric 42381ad6265SDimitry Andric #ifndef NDEBUG 42481ad6265SDimitry Andric std::string 42581ad6265SDimitry Andric SampleContextTracker::getContextString(const FunctionSamples &FSamples) const { 42681ad6265SDimitry Andric return getContextString(getContextNodeForProfile(&FSamples)); 42781ad6265SDimitry Andric } 42881ad6265SDimitry Andric 42981ad6265SDimitry Andric std::string 43081ad6265SDimitry Andric SampleContextTracker::getContextString(ContextTrieNode *Node) const { 43181ad6265SDimitry Andric SampleContextFrameVector Res; 43281ad6265SDimitry Andric if (Node == &RootContext) 43381ad6265SDimitry Andric return std::string(); 43481ad6265SDimitry Andric Res.emplace_back(Node->getFuncName(), LineLocation(0, 0)); 43581ad6265SDimitry Andric 43681ad6265SDimitry Andric ContextTrieNode *PreNode = Node; 43781ad6265SDimitry Andric Node = Node->getParentContext(); 43881ad6265SDimitry Andric while (Node && Node != &RootContext) { 43981ad6265SDimitry Andric Res.emplace_back(Node->getFuncName(), PreNode->getCallSiteLoc()); 44081ad6265SDimitry Andric PreNode = Node; 44181ad6265SDimitry Andric Node = Node->getParentContext(); 44281ad6265SDimitry Andric } 44381ad6265SDimitry Andric 44481ad6265SDimitry Andric std::reverse(Res.begin(), Res.end()); 44581ad6265SDimitry Andric 44681ad6265SDimitry Andric return SampleContext::getContextString(Res); 44781ad6265SDimitry Andric } 44881ad6265SDimitry Andric #endif 44981ad6265SDimitry Andric 450349cc55cSDimitry Andric void SampleContextTracker::dump() { RootContext.dumpTree(); } 451e8d8bef9SDimitry Andric 452349cc55cSDimitry Andric StringRef SampleContextTracker::getFuncNameFor(ContextTrieNode *Node) const { 453349cc55cSDimitry Andric if (!FunctionSamples::UseMD5) 4545f757f3fSDimitry Andric return Node->getFuncName().stringRef(); 455349cc55cSDimitry Andric assert(GUIDToFuncNameMap && "GUIDToFuncNameMap needs to be populated first"); 4565f757f3fSDimitry Andric return GUIDToFuncNameMap->lookup(Node->getFuncName().getHashCode()); 457e8d8bef9SDimitry Andric } 458e8d8bef9SDimitry Andric 459e8d8bef9SDimitry Andric ContextTrieNode * 460e8d8bef9SDimitry Andric SampleContextTracker::getContextFor(const SampleContext &Context) { 461e8d8bef9SDimitry Andric return getOrCreateContextPath(Context, false); 462e8d8bef9SDimitry Andric } 463e8d8bef9SDimitry Andric 464e8d8bef9SDimitry Andric ContextTrieNode * 465e8d8bef9SDimitry Andric SampleContextTracker::getCalleeContextFor(const DILocation *DIL, 4665f757f3fSDimitry Andric FunctionId CalleeName) { 467e8d8bef9SDimitry Andric assert(DIL && "Expect non-null location"); 468e8d8bef9SDimitry Andric 469e8d8bef9SDimitry Andric ContextTrieNode *CallContext = getContextFor(DIL); 470e8d8bef9SDimitry Andric if (!CallContext) 471e8d8bef9SDimitry Andric return nullptr; 472e8d8bef9SDimitry Andric 473d409305fSDimitry Andric // When CalleeName is empty, the child context profile with max 474d409305fSDimitry Andric // total samples will be returned. 475e8d8bef9SDimitry Andric return CallContext->getChildContext( 476d409305fSDimitry Andric FunctionSamples::getCallSiteIdentifier(DIL), CalleeName); 477e8d8bef9SDimitry Andric } 478e8d8bef9SDimitry Andric 479e8d8bef9SDimitry Andric ContextTrieNode *SampleContextTracker::getContextFor(const DILocation *DIL) { 480e8d8bef9SDimitry Andric assert(DIL && "Expect non-null location"); 4815f757f3fSDimitry Andric SmallVector<std::pair<LineLocation, FunctionId>, 10> S; 482e8d8bef9SDimitry Andric 483e8d8bef9SDimitry Andric // Use C++ linkage name if possible. 484e8d8bef9SDimitry Andric const DILocation *PrevDIL = DIL; 485e8d8bef9SDimitry Andric for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) { 486e8d8bef9SDimitry Andric StringRef Name = PrevDIL->getScope()->getSubprogram()->getLinkageName(); 487e8d8bef9SDimitry Andric if (Name.empty()) 488e8d8bef9SDimitry Andric Name = PrevDIL->getScope()->getSubprogram()->getName(); 489e8d8bef9SDimitry Andric S.push_back( 4905f757f3fSDimitry Andric std::make_pair(FunctionSamples::getCallSiteIdentifier(DIL), 4915f757f3fSDimitry Andric getRepInFormat(Name))); 492e8d8bef9SDimitry Andric PrevDIL = DIL; 493e8d8bef9SDimitry Andric } 494e8d8bef9SDimitry Andric 495e8d8bef9SDimitry Andric // Push root node, note that root node like main may only 496e8d8bef9SDimitry Andric // a name, but not linkage name. 497e8d8bef9SDimitry Andric StringRef RootName = PrevDIL->getScope()->getSubprogram()->getLinkageName(); 498e8d8bef9SDimitry Andric if (RootName.empty()) 499e8d8bef9SDimitry Andric RootName = PrevDIL->getScope()->getSubprogram()->getName(); 5005f757f3fSDimitry Andric S.push_back(std::make_pair(LineLocation(0, 0), 5015f757f3fSDimitry Andric getRepInFormat(RootName))); 502349cc55cSDimitry Andric 503e8d8bef9SDimitry Andric ContextTrieNode *ContextNode = &RootContext; 504e8d8bef9SDimitry Andric int I = S.size(); 505e8d8bef9SDimitry Andric while (--I >= 0 && ContextNode) { 506e8d8bef9SDimitry Andric LineLocation &CallSite = S[I].first; 5075f757f3fSDimitry Andric FunctionId CalleeName = S[I].second; 508e8d8bef9SDimitry Andric ContextNode = ContextNode->getChildContext(CallSite, CalleeName); 509e8d8bef9SDimitry Andric } 510e8d8bef9SDimitry Andric 511e8d8bef9SDimitry Andric if (I < 0) 512e8d8bef9SDimitry Andric return ContextNode; 513e8d8bef9SDimitry Andric 514e8d8bef9SDimitry Andric return nullptr; 515e8d8bef9SDimitry Andric } 516e8d8bef9SDimitry Andric 517e8d8bef9SDimitry Andric ContextTrieNode * 518e8d8bef9SDimitry Andric SampleContextTracker::getOrCreateContextPath(const SampleContext &Context, 519e8d8bef9SDimitry Andric bool AllowCreate) { 520e8d8bef9SDimitry Andric ContextTrieNode *ContextNode = &RootContext; 521e8d8bef9SDimitry Andric LineLocation CallSiteLoc(0, 0); 522e8d8bef9SDimitry Andric 523bdd1243dSDimitry Andric for (const auto &Callsite : Context.getContextFrames()) { 524e8d8bef9SDimitry Andric // Create child node at parent line/disc location 525e8d8bef9SDimitry Andric if (AllowCreate) { 526e8d8bef9SDimitry Andric ContextNode = 5275f757f3fSDimitry Andric ContextNode->getOrCreateChildContext(CallSiteLoc, Callsite.Func); 528e8d8bef9SDimitry Andric } else { 529349cc55cSDimitry Andric ContextNode = 5305f757f3fSDimitry Andric ContextNode->getChildContext(CallSiteLoc, Callsite.Func); 531e8d8bef9SDimitry Andric } 532349cc55cSDimitry Andric CallSiteLoc = Callsite.Location; 533e8d8bef9SDimitry Andric } 534e8d8bef9SDimitry Andric 535e8d8bef9SDimitry Andric assert((!AllowCreate || ContextNode) && 536e8d8bef9SDimitry Andric "Node must exist if creation is allowed"); 537e8d8bef9SDimitry Andric return ContextNode; 538e8d8bef9SDimitry Andric } 539e8d8bef9SDimitry Andric 5405f757f3fSDimitry Andric ContextTrieNode * 5415f757f3fSDimitry Andric SampleContextTracker::getTopLevelContextNode(FunctionId FName) { 542fe6060f1SDimitry Andric assert(!FName.empty() && "Top level node query must provide valid name"); 543e8d8bef9SDimitry Andric return RootContext.getChildContext(LineLocation(0, 0), FName); 544e8d8bef9SDimitry Andric } 545e8d8bef9SDimitry Andric 5465f757f3fSDimitry Andric ContextTrieNode & 5475f757f3fSDimitry Andric SampleContextTracker::addTopLevelContextNode(FunctionId FName) { 548e8d8bef9SDimitry Andric assert(!getTopLevelContextNode(FName) && "Node to add must not exist"); 549e8d8bef9SDimitry Andric return *RootContext.getOrCreateChildContext(LineLocation(0, 0), FName); 550e8d8bef9SDimitry Andric } 551e8d8bef9SDimitry Andric 552e8d8bef9SDimitry Andric void SampleContextTracker::mergeContextNode(ContextTrieNode &FromNode, 55381ad6265SDimitry Andric ContextTrieNode &ToNode) { 554e8d8bef9SDimitry Andric FunctionSamples *FromSamples = FromNode.getFunctionSamples(); 555e8d8bef9SDimitry Andric FunctionSamples *ToSamples = ToNode.getFunctionSamples(); 556e8d8bef9SDimitry Andric if (FromSamples && ToSamples) { 557e8d8bef9SDimitry Andric // Merge/duplicate FromSamples into ToSamples 558e8d8bef9SDimitry Andric ToSamples->merge(*FromSamples); 559e8d8bef9SDimitry Andric ToSamples->getContext().setState(SyntheticContext); 560e8d8bef9SDimitry Andric FromSamples->getContext().setState(MergedContext); 561349cc55cSDimitry Andric if (FromSamples->getContext().hasAttribute(ContextShouldBeInlined)) 562349cc55cSDimitry Andric ToSamples->getContext().setAttribute(ContextShouldBeInlined); 563e8d8bef9SDimitry Andric } else if (FromSamples) { 564e8d8bef9SDimitry Andric // Transfer FromSamples from FromNode to ToNode 565e8d8bef9SDimitry Andric ToNode.setFunctionSamples(FromSamples); 56681ad6265SDimitry Andric setContextNode(FromSamples, &ToNode); 567e8d8bef9SDimitry Andric FromSamples->getContext().setState(SyntheticContext); 568e8d8bef9SDimitry Andric } 569e8d8bef9SDimitry Andric } 570e8d8bef9SDimitry Andric 571e8d8bef9SDimitry Andric ContextTrieNode &SampleContextTracker::promoteMergeContextSamplesTree( 57281ad6265SDimitry Andric ContextTrieNode &FromNode, ContextTrieNode &ToNodeParent) { 573e8d8bef9SDimitry Andric 574e8d8bef9SDimitry Andric // Ignore call site location if destination is top level under root 575e8d8bef9SDimitry Andric LineLocation NewCallSiteLoc = LineLocation(0, 0); 576e8d8bef9SDimitry Andric LineLocation OldCallSiteLoc = FromNode.getCallSiteLoc(); 577e8d8bef9SDimitry Andric ContextTrieNode &FromNodeParent = *FromNode.getParentContext(); 578e8d8bef9SDimitry Andric ContextTrieNode *ToNode = nullptr; 579e8d8bef9SDimitry Andric bool MoveToRoot = (&ToNodeParent == &RootContext); 580e8d8bef9SDimitry Andric if (!MoveToRoot) { 581e8d8bef9SDimitry Andric NewCallSiteLoc = OldCallSiteLoc; 582e8d8bef9SDimitry Andric } 583e8d8bef9SDimitry Andric 584e8d8bef9SDimitry Andric // Locate destination node, create/move if not existing 585e8d8bef9SDimitry Andric ToNode = ToNodeParent.getChildContext(NewCallSiteLoc, FromNode.getFuncName()); 586e8d8bef9SDimitry Andric if (!ToNode) { 587e8d8bef9SDimitry Andric // Do not delete node to move from its parent here because 588e8d8bef9SDimitry Andric // caller is iterating over children of that parent node. 58981ad6265SDimitry Andric ToNode = 59081ad6265SDimitry Andric &moveContextSamples(ToNodeParent, NewCallSiteLoc, std::move(FromNode)); 59181ad6265SDimitry Andric LLVM_DEBUG({ 59281ad6265SDimitry Andric dbgs() << " Context promoted and merged to: " << getContextString(ToNode) 59381ad6265SDimitry Andric << "\n"; 59481ad6265SDimitry Andric }); 595e8d8bef9SDimitry Andric } else { 596e8d8bef9SDimitry Andric // Destination node exists, merge samples for the context tree 59781ad6265SDimitry Andric mergeContextNode(FromNode, *ToNode); 598fe6060f1SDimitry Andric LLVM_DEBUG({ 599fe6060f1SDimitry Andric if (ToNode->getFunctionSamples()) 600fe6060f1SDimitry Andric dbgs() << " Context promoted and merged to: " 60181ad6265SDimitry Andric << getContextString(ToNode) << "\n"; 602fe6060f1SDimitry Andric }); 603e8d8bef9SDimitry Andric 604e8d8bef9SDimitry Andric // Recursively promote and merge children 605e8d8bef9SDimitry Andric for (auto &It : FromNode.getAllChildContext()) { 606e8d8bef9SDimitry Andric ContextTrieNode &FromChildNode = It.second; 60781ad6265SDimitry Andric promoteMergeContextSamplesTree(FromChildNode, *ToNode); 608e8d8bef9SDimitry Andric } 609e8d8bef9SDimitry Andric 610e8d8bef9SDimitry Andric // Remove children once they're all merged 611e8d8bef9SDimitry Andric FromNode.getAllChildContext().clear(); 612e8d8bef9SDimitry Andric } 613e8d8bef9SDimitry Andric 614e8d8bef9SDimitry Andric // For root of subtree, remove itself from old parent too 615e8d8bef9SDimitry Andric if (MoveToRoot) 616e8d8bef9SDimitry Andric FromNodeParent.removeChildContext(OldCallSiteLoc, ToNode->getFuncName()); 617e8d8bef9SDimitry Andric 618e8d8bef9SDimitry Andric return *ToNode; 619e8d8bef9SDimitry Andric } 62081ad6265SDimitry Andric 62181ad6265SDimitry Andric void SampleContextTracker::createContextLessProfileMap( 62281ad6265SDimitry Andric SampleProfileMap &ContextLessProfiles) { 62381ad6265SDimitry Andric for (auto *Node : *this) { 62481ad6265SDimitry Andric FunctionSamples *FProfile = Node->getFunctionSamples(); 62581ad6265SDimitry Andric // Profile's context can be empty, use ContextNode's func name. 62681ad6265SDimitry Andric if (FProfile) 627*0fca6ea1SDimitry Andric ContextLessProfiles.create(Node->getFuncName()).merge(*FProfile); 62881ad6265SDimitry Andric } 62981ad6265SDimitry Andric } 630e8d8bef9SDimitry Andric } // namespace llvm 631