1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
#pragma once
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
//===- Transforms/IPO/SampleContextTracker.h --------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file provides the interface for context-sensitive profile tracker used
/// by CSSPGO.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
#define LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Instructions.h"
#include "llvm/ProfileData/SampleProf.h"
#include <list>
#include <map>
#include <vector>
using namespace llvm;
using namespace sampleprof;
namespace llvm {
// Internal trie tree representation used for tracking context tree and sample
// profiles. The path from root node to a given node represents the context of
// that nodes' profile.
class ContextTrieNode {
public:
ContextTrieNode(ContextTrieNode *Parent = nullptr,
StringRef FName = StringRef(),
FunctionSamples *FSamples = nullptr,
LineLocation CallLoc = {0, 0})
: ParentContext(Parent), FuncName(FName), FuncSamples(FSamples),
CallSiteLoc(CallLoc){};
ContextTrieNode *getChildContext(const LineLocation &CallSite,
StringRef ChildName);
ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);
ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
StringRef ChildName,
bool AllowCreate = true);
ContextTrieNode &moveToChildContext(const LineLocation &CallSite,
ContextTrieNode &&NodeToMove,
uint32_t ContextFramesToRemove,
bool DeleteNode = true);
void removeChildContext(const LineLocation &CallSite, StringRef ChildName);
std::map<uint64_t, ContextTrieNode> &getAllChildContext();
StringRef getFuncName() const;
FunctionSamples *getFunctionSamples() const;
void setFunctionSamples(FunctionSamples *FSamples);
Optional<uint32_t> getFunctionSize() const;
void addFunctionSize(uint32_t FSize);
LineLocation getCallSiteLoc() const;
ContextTrieNode *getParentContext() const;
void setParentContext(ContextTrieNode *Parent);
void dumpNode();
void dumpTree();
private:
// Map line+discriminator location to child context
std::map<uint64_t, ContextTrieNode> AllChildContext;
// Link to parent context node
ContextTrieNode *ParentContext;
// Function name for current context
StringRef FuncName;
// Function Samples for current context
FunctionSamples *FuncSamples;
// Function size for current context
Optional<uint32_t> FuncSize;
// Callsite location in parent context
LineLocation CallSiteLoc;
};
// Profile tracker that manages profiles and its associated context. It
// provides interfaces used by sample profile loader to query context profile or
// base profile for given function or location; it also manages context tree
// manipulation that is needed to accommodate inline decisions so we have
// accurate post-inline profile for functions. Internally context profiles
// are organized in a trie, with each node representing profile for specific
// calling context and the context is identified by path from root to the node.
class SampleContextTracker {
public:
struct ProfileComparer {
bool operator()(FunctionSamples *A, FunctionSamples *B) const {
// Sort function profiles by the number of total samples and their
// contexts.
if (A->getTotalSamples() == B->getTotalSamples())
return A->getContext() < B->getContext();
return A->getTotalSamples() > B->getTotalSamples();
}
};
// Keep profiles of a function sorted so that they will be processed/promoted
// deterministically.
using ContextSamplesTy = std::set<FunctionSamples *, ProfileComparer>;
SampleContextTracker(SampleProfileMap &Profiles,
const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap);
// Query context profile for a specific callee with given name at a given
// call-site. The full context is identified by location of call instruction.
FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst,
StringRef CalleeName);
// Get samples for indirect call targets for call site at given location.
std::vector<const FunctionSamples *>
getIndirectCalleeContextSamplesFor(const DILocation *DIL);
// Query context profile for a given location. The full context
// is identified by input DILocation.
FunctionSamples *getContextSamplesFor(const DILocation *DIL);
// Query context profile for a given sample contxt of a function.
FunctionSamples *getContextSamplesFor(const SampleContext &Context);
// Get all context profile for given function.
ContextSamplesTy &getAllContextSamplesFor(const Function &Func);
ContextSamplesTy &getAllContextSamplesFor(StringRef Name);
// Query base profile for a given function. A base profile is a merged view
// of all context profiles for contexts that are not inlined.
FunctionSamples *getBaseSamplesFor(const Function &Func,
bool MergeContext = true);
// Query base profile for a given function by name.
FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext = true);
// Retrieve the context trie node for given profile context
ContextTrieNode *getContextFor(const SampleContext &Context);
// Get real function name for a given trie node.
StringRef getFuncNameFor(ContextTrieNode *Node) const;
// Mark a context profile as inlined when function is inlined.
// This makes sure that inlined context profile will be excluded in
// function's base profile.
void markContextSamplesInlined(const FunctionSamples *InlinedSamples);
ContextTrieNode &getRootContext();
void promoteMergeContextSamplesTree(const Instruction &Inst,
StringRef CalleeName);
// Dump the internal context profile trie.
void dump();
private:
ContextTrieNode *getContextFor(const DILocation *DIL);
ContextTrieNode *getCalleeContextFor(const DILocation *DIL,
StringRef CalleeName);
ContextTrieNode *getOrCreateContextPath(const SampleContext &Context,
bool AllowCreate);
ContextTrieNode *getTopLevelContextNode(StringRef FName);
ContextTrieNode &addTopLevelContextNode(StringRef FName);
ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo);
void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode,
uint32_t ContextFramesToRemove);
ContextTrieNode &
promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
ContextTrieNode &ToNodeParent,
uint32_t ContextFramesToRemove);
// Map from function name to context profiles (excluding base profile)
StringMap<ContextSamplesTy> FuncToCtxtProfiles;
// Map from function guid to real function names. Only used in md5 mode.
const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap;
// Root node for context trie tree
ContextTrieNode RootContext;
};
} // end namespace llvm
#endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
|
