1 //===- Transforms/IPO/SampleContextTracker.h --------------------*- C++ -*-===//
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 /// \file
10 /// This file provides the interface for context-sensitive profile tracker used
11 /// by CSSPGO.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
16 #define LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
17 
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/StringMap.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/IR/DebugInfoMetadata.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/ProfileData/SampleProf.h"
24 #include <list>
25 #include <map>
26 #include <vector>
27 
28 using namespace llvm;
29 using namespace sampleprof;
30 
31 namespace llvm {
32 
33 // Internal trie tree representation used for tracking context tree and sample
34 // profiles. The path from root node to a given node represents the context of
35 // that nodes' profile.
36 class ContextTrieNode {
37 public:
38   ContextTrieNode(ContextTrieNode *Parent = nullptr,
39                   StringRef FName = StringRef(),
40                   FunctionSamples *FSamples = nullptr,
41                   LineLocation CallLoc = {0, 0})
42       : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples),
43         CallSiteLoc(CallLoc){};
44   ContextTrieNode *getChildContext(const LineLocation &CallSite,
45                                    StringRef CalleeName);
46   ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);
47   ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
48                                            StringRef CalleeName,
49                                            bool AllowCreate = true);
50 
51   ContextTrieNode &moveToChildContext(const LineLocation &CallSite,
52                                       ContextTrieNode &&NodeToMove,
53                                       StringRef ContextStrToRemove,
54                                       bool DeleteNode = true);
55   void removeChildContext(const LineLocation &CallSite, StringRef CalleeName);
56   std::map<uint32_t, ContextTrieNode> &getAllChildContext();
57   StringRef getFuncName() const;
58   FunctionSamples *getFunctionSamples() const;
59   void setFunctionSamples(FunctionSamples *FSamples);
60   LineLocation getCallSiteLoc() const;
61   ContextTrieNode *getParentContext() const;
62   void setParentContext(ContextTrieNode *Parent);
63   void dump();
64 
65 private:
66   static uint32_t nodeHash(StringRef ChildName, const LineLocation &Callsite);
67 
68   // Map line+discriminator location to child context
69   std::map<uint32_t, ContextTrieNode> AllChildContext;
70 
71   // Link to parent context node
72   ContextTrieNode *ParentContext;
73 
74   // Function name for current context
75   StringRef FuncName;
76 
77   // Function Samples for current context
78   FunctionSamples *FuncSamples;
79 
80   // Callsite location in parent context
81   LineLocation CallSiteLoc;
82 };
83 
84 // Profile tracker that manages profiles and its associated context. It
85 // provides interfaces used by sample profile loader to query context profile or
86 // base profile for given function or location; it also manages context tree
87 // manipulation that is needed to accommodate inline decisions so we have
88 // accurate post-inline profile for functions. Internally context profiles
89 // are organized in a trie, with each node representing profile for specific
90 // calling context and the context is identified by path from root to the node.
91 class SampleContextTracker {
92 public:
93   using ContextSamplesTy = SmallVector<FunctionSamples *, 16>;
94 
95   SampleContextTracker(StringMap<FunctionSamples> &Profiles);
96   // Query context profile for a specific callee with given name at a given
97   // call-site. The full context is identified by location of call instruction.
98   FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst,
99                                               StringRef CalleeName);
100   // Get samples for indirect call targets for call site at given location.
validate()101   std::vector<const FunctionSamples *>
102   getIndirectCalleeContextSamplesFor(const DILocation *DIL);
103   // Query context profile for a given location. The full context
104   // is identified by input DILocation.
105   FunctionSamples *getContextSamplesFor(const DILocation *DIL);
106   // Query context profile for a given sample contxt of a function.
107   FunctionSamples *getContextSamplesFor(const SampleContext &Context);
108   // Get all context profile for given function.
109   ContextSamplesTy &getAllContextSamplesFor(const Function &Func);
110   ContextSamplesTy &getAllContextSamplesFor(StringRef Name);
111   // Query base profile for a given function. A base profile is a merged view
112   // of all context profiles for contexts that are not inlined.
113   FunctionSamples *getBaseSamplesFor(const Function &Func,
114                                      bool MergeContext = true);
115   // Query base profile for a given function by name.
116   FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext = true);
117   // Retrieve the context trie node for given profile context
118   ContextTrieNode *getContextFor(const SampleContext &Context);
119   // Mark a context profile as inlined when function is inlined.
120   // This makes sure that inlined context profile will be excluded in
121   // function's base profile.
122   void markContextSamplesInlined(const FunctionSamples *InlinedSamples);
123   ContextTrieNode &getRootContext();
124   void promoteMergeContextSamplesTree(const Instruction &Inst,
125                                       StringRef CalleeName);
126   // Dump the internal context profile trie.
127   void dump();
128 
129 private:
130   ContextTrieNode *getContextFor(const DILocation *DIL);
131   ContextTrieNode *getCalleeContextFor(const DILocation *DIL,
132                                        StringRef CalleeName);
133   ContextTrieNode *getOrCreateContextPath(const SampleContext &Context,
134                                           bool AllowCreate);
135   ContextTrieNode *getTopLevelContextNode(StringRef FName);
136   ContextTrieNode &addTopLevelContextNode(StringRef FName);
137   ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo);
138   void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode,
139                         StringRef ContextStrToRemove);
140   ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
141                                                   ContextTrieNode &ToNodeParent,
142                                                   StringRef ContextStrToRemove);
143 
144   // Map from function name to context profiles (excluding base profile)
145   StringMap<ContextSamplesTy> FuncToCtxtProfiles;
delete(void * Ptr,BumpPtrAllocator & Alloc,size_t Size)146 
147   // Root node for context trie tree
148   ContextTrieNode RootContext;
149 };
150 
151 } // end namespace llvm
152 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
153