LLVM: lib/ProfileData/MemProfRadixTree.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
14
15namespace llvm {
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
47template
48LinearCallStackId CallStackRadixTreeBuilder::encodeCallStack(
51 const llvm::DenseMap<FrameIdTy, LinearFrameId> *MemProfFrameIndexes) {
52
53 uint32_t CommonLen = 0;
54 if (Prev) {
55 auto Pos = std::mismatch(Prev->rbegin(), Prev->rend(), CallStack->rbegin(),
57 CommonLen = std::distance(CallStack->rbegin(), Pos.second);
58 }
59
60
61 assert(CommonLen <= Indexes.size());
62 Indexes.resize(CommonLen);
63
64
65 if (CommonLen) {
66 uint32_t CurrentIndex = RadixArray.size();
67 uint32_t ParentIndex = Indexes.back();
68
69
70 assert(ParentIndex < CurrentIndex);
71 RadixArray.push_back(ParentIndex - CurrentIndex);
72 }
73
74
75 assert(CommonLen <= CallStack->size());
77
78 Indexes.push_back(RadixArray.size());
79 RadixArray.push_back(
80 MemProfFrameIndexes ? MemProfFrameIndexes->find(F)->second : F);
81 }
83
84
85 RadixArray.push_back(CallStack->size());
86
87
88
89 return RadixArray.size() - 1;
90}
91
92template
95 &&MemProfCallStackData,
98
99
101
102
103 if (CallStacks.empty()) {
104 RadixArray.clear();
105 CallStackPos.clear();
106 return;
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 llvm::sort(CallStacks, [&](const CSIdPair &L, const CSIdPair &R) {
145
146
147 return std::lexicographical_compare(
148 L.second.rbegin(), L.second.rend(), R.second.rbegin(), R.second.rend(),
149 [&](FrameIdTy F1, FrameIdTy F2) {
150 uint64_t H1 = FrameHistogram[F1].Count;
151 uint64_t H2 = FrameHistogram[F2].Count;
152
153
154 if (H1 != H2)
155 return H1 < H2;
156
157 return F1 < F2;
158 });
159 });
160
161
162 RadixArray.clear();
163 RadixArray.reserve(CallStacks.size() * 8);
164
165
166 Indexes.clear();
167 Indexes.reserve(512);
168
169
170 CallStackPos.clear();
171 CallStackPos.reserve(CallStacks.size());
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
202 encodeCallStack(&CallStack, Prev, MemProfFrameIndexes);
203 CallStackPos.insert({CSId, Pos});
205 }
206
207
208 assert(!RadixArray.empty());
209
210
211
212
213
214 for (size_t I = 0, J = RadixArray.size() - 1; I < J; ++I, --J)
215 std::swap(RadixArray[I], RadixArray[J]);
216
217
218 for (auto &[K, V] : CallStackPos)
219 V = RadixArray.size() - 1 - V;
220}
221
222
225
226template
229 &MemProfCallStackData) {
231
232 for (const auto &KV : MemProfCallStackData) {
233 const auto &CS = KV.second;
234 for (unsigned I = 0, E = CS.size(); I != E; ++I) {
235 auto &S = Histogram[CS[I]];
236 ++S.Count;
237 S.PositionSum += I;
238 }
239 }
240 return Histogram;
241}
242
243
247 &MemProfCallStackData);
251 &MemProfCallStackData);
252}
253}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_EXPORT_TEMPLATE
iterator find(const_arg_type_t< KeyT > Val)
This class implements a map that also provides access to all stored values in a deterministic order.
reverse_iterator rbegin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void build(llvm::MapVector< CallStackId, llvm::SmallVector< FrameIdTy > > &&MemProfCallStackData, const llvm::DenseMap< FrameIdTy, LinearFrameId > *MemProfFrameIndexes, llvm::DenseMap< FrameIdTy, FrameStat > &FrameHistogram)
Definition MemProfRadixTree.cpp:93
Helper class to iterate through stack ids in both metadata (memprof MIB and callsite) and the corresp...
template LLVM_ABI llvm::DenseMap< FrameId, FrameStat > computeFrameHistogram< FrameId >(llvm::MapVector< CallStackId, llvm::SmallVector< FrameId > > &MemProfCallStackData)
uint32_t LinearCallStackId
template LLVM_ABI llvm::DenseMap< LinearFrameId, FrameStat > computeFrameHistogram< LinearFrameId >(llvm::MapVector< CallStackId, llvm::SmallVector< LinearFrameId > > &MemProfCallStackData)
llvm::DenseMap< FrameIdTy, FrameStat > computeFrameHistogram(llvm::MapVector< CallStackId, llvm::SmallVector< FrameIdTy > > &MemProfCallStackData)
Definition MemProfRadixTree.cpp:228
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
auto reverse(ContainerTy &&C)
void sort(IteratorTy Start, IteratorTy End)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.