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/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(Callee: CalleeName, Callsite: CallSite);
36 auto It = AllChildContext.find(x: 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 can
45 // do point look up for child node by call site alone.
46 // Retrieve the child node with max count for indirect call
47 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(Callee: NodeToMove.getFuncName(), Callsite: 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 update
79 // 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(x: &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(FSample: 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(x: ChildNode);
99 }
100 }
101
102 return NewNode;
103}
104
105void ContextTrieNode::removeChildContext(const LineLocation &CallSite,
106 FunctionId CalleeName) {
107 uint64_t Hash = FunctionSamples::getCallSiteHash(Callee: CalleeName, Callsite: CallSite);
108 // Note this essentially calls dtor and destroys that child context
109 AllChildContext.erase(x: 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(x: 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(x: ChildNode);
175 }
176 }
177}
178
179ContextTrieNode *ContextTrieNode::getOrCreateChildContext(
180 const LineLocation &CallSite, FunctionId CalleeName, bool AllowCreate) {
181 uint64_t Hash = FunctionSamples::getCallSiteHash(Callee: CalleeName, Callsite: CallSite);
182 auto It = AllChildContext.find(x: 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 context
198SampleContextTracker::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, AllowCreate: 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(FSample: FSamples, Node);
221 FuncToCtxtProfiles[Node->getFuncName()].push_back(x: 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(FnName: CalleeName);
235
236 FunctionId FName = getRepInFormat(Name: CalleeName);
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: 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(x: 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 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
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(F: Func);
306 return FuncToCtxtProfiles[getRepInFormat(Name: 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(F: Func);
317 return getBaseSamplesFor(Name: getRepInFormat(Name: 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 retrieve
325 // existing top-level node for given function first. If it exists, it could be
326 // that we've merged base profile before, or there's actually context-less
327 // profile from the input (e.g. due to unreliable stack walking).
328 ContextTrieNode *Node = getTopLevelContextNode(FName: Name);
329 if (MergeContext) {
330 LLVM_DEBUG(dbgs() << " Merging context profile into base profile: " << Name
331 << "\n");
332
333 // We have profile for function under different contexts,
334 // create synthetic base profile and merge context profiles
335 // 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 context
339 if (Context.hasState(S: InlinedContext) || Context.hasState(S: MergedContext))
340 continue;
341
342 ContextTrieNode *FromNode = getContextNodeForProfile(FSamples: CSamples);
343 if (FromNode == Node)
344 continue;
345
346 ContextTrieNode &ToNode = promoteMergeContextSamplesTree(NodeToPromo&: *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 callee
374 // 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 promoted
381 LineLocation CallSite = FunctionSamples::getCallSiteIdentifier(DIL);
382 // For indirect call, CalleeName will be empty, in which case we need to
383 // 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(S: InlinedContext))
391 continue;
392 promoteMergeContextSamplesTree(NodeToPromo&: *NodeToPromo);
393 }
394 return;
395 }
396
397 // Get the context for the given callee that needs to be promoted
398 ContextTrieNode *NodeToPromo =
399 CallerNode->getChildContext(CallSite, CalleeName);
400 if (!NodeToPromo)
401 return;
402
403 promoteMergeContextSamplesTree(NodeToPromo&: *NodeToPromo);
404}
405
406ContextTrieNode &SampleContextTracker::promoteMergeContextSamplesTree(
407 ContextTrieNode &NodeToPromo) {
408 // Promote the input node to be directly under root. This can happen
409 // when we decided to not inline a function under context represented
410 // by the input node. The promote and merge is then needed to reflect
411 // 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(FromNode&: NodeToPromo, ToNodeParent&: RootContext);
422}
423
424#ifndef NDEBUG
425std::string
426SampleContextTracker::getContextString(const FunctionSamples &FSamples) const {
427 return getContextString(getContextNodeForProfile(&FSamples));
428}
429
430std::string
431SampleContextTracker::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#endif
450
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(Val: Node->getFuncName().getHashCode());
458}
459
460ContextTrieNode *
461SampleContextTracker::getContextFor(const SampleContext &Context) {
462 return getOrCreateContextPath(Context, AllowCreate: 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 max
475 // total samples will be returned.
476 return CallContext->getChildContext(
477 CallSite: 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 Elt: std::make_pair(x: FunctionSamples::getCallSiteIdentifier(DIL),
492 y: getRepInFormat(Name)));
493 PrevDIL = DIL;
494 }
495
496 // Push root node, note that root node like main may only
497 // 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(Elt: std::make_pair(x: LineLocation(0, 0),
502 y: getRepInFormat(Name: 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 location
526 if (AllowCreate) {
527 ContextNode =
528 ContextNode->getOrCreateChildContext(CallSite: CallSiteLoc, CalleeName: Callsite.Func);
529 } else {
530 ContextNode =
531 ContextNode->getChildContext(CallSite: CallSiteLoc, CalleeName: 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(CallSite: LineLocation(0, 0), CalleeName: FName);
545}
546
547ContextTrieNode &
548SampleContextTracker::addTopLevelContextNode(FunctionId FName) {
549 assert(!getTopLevelContextNode(FName) && "Node to add must not exist");
550 return *RootContext.getOrCreateChildContext(CallSite: LineLocation(0, 0), CalleeName: 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 ToSamples
559 ToSamples->merge(Other: *FromSamples);
560 ToSamples->getContext().setState(SyntheticContext);
561 FromSamples->getContext().setState(MergedContext);
562 if (FromSamples->getContext().hasAttribute(A: ContextShouldBeInlined))
563 ToSamples->getContext().setAttribute(ContextShouldBeInlined);
564 } else if (FromSamples) {
565 // Transfer FromSamples from FromNode to ToNode
566 ToNode.setFunctionSamples(FromSamples);
567 setContextNode(FSample: FromSamples, Node: &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 root
576 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 existing
586 ToNode = ToNodeParent.getChildContext(CallSite: NewCallSiteLoc, CalleeName: FromNode.getFuncName());
587 if (!ToNode) {
588 // Do not delete node to move from its parent here because
589 // caller is iterating over children of that parent node.
590 ToNode =
591 &moveContextSamples(ToNodeParent, CallSite: NewCallSiteLoc, NodeToMove: 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 tree
598 mergeContextNode(FromNode, ToNode&: *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 children
606 for (auto &It : FromNode.getAllChildContext()) {
607 ContextTrieNode &FromChildNode = It.second;
608 promoteMergeContextSamplesTree(FromNode&: FromChildNode, ToNodeParent&: *ToNode);
609 }
610
611 // Remove children once they're all merged
612 FromNode.getAllChildContext().clear();
613 }
614
615 // For root of subtree, remove itself from old parent too
616 if (MoveToRoot)
617 FromNodeParent.removeChildContext(CallSite: OldCallSiteLoc, CalleeName: 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(Ctx: Node->getFuncName()).merge(Other: *FProfile);
629 }
630}
631} // namespace llvm
632