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