xref: /freebsd-src/contrib/llvm-project/llvm/lib/Transforms/IPO/SampleContextTracker.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
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