-
Notifications
You must be signed in to change notification settings - Fork 10.8k
/
SampleProf.h
1584 lines (1378 loc) · 56.5 KB
/
SampleProf.h
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//===- SampleProf.h - Sampling profiling format support ---------*- 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
//
//===----------------------------------------------------------------------===//
//
// This file contains common definitions used in the reading and writing of
// sample profile data.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_PROFILEDATA_SAMPLEPROF_H
#define LLVM_PROFILEDATA_SAMPLEPROF_H
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/ProfileData/FunctionId.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorOr.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/ProfileData/HashKeyMap.h"
#include <algorithm>
#include <cstdint>
#include <list>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <system_error>
#include <unordered_map>
#include <utility>
namespace llvm {
class DILocation;
class raw_ostream;
const std::error_category &sampleprof_category();
enum class sampleprof_error {
success = 0,
bad_magic,
unsupported_version,
too_large,
truncated,
malformed,
unrecognized_format,
unsupported_writing_format,
truncated_name_table,
not_implemented,
counter_overflow,
ostream_seek_unsupported,
uncompress_failed,
zlib_unavailable,
hash_mismatch
};
inline std::error_code make_error_code(sampleprof_error E) {
return std::error_code(static_cast<int>(E), sampleprof_category());
}
inline sampleprof_error MergeResult(sampleprof_error &Accumulator,
sampleprof_error Result) {
// Prefer first error encountered as later errors may be secondary effects of
// the initial problem.
if (Accumulator == sampleprof_error::success &&
Result != sampleprof_error::success)
Accumulator = Result;
return Accumulator;
}
} // end namespace llvm
namespace std {
template <>
struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
} // end namespace std
namespace llvm {
namespace sampleprof {
enum SampleProfileFormat {
SPF_None = 0,
SPF_Text = 0x1,
SPF_Compact_Binary = 0x2, // Deprecated
SPF_GCC = 0x3,
SPF_Ext_Binary = 0x4,
SPF_Binary = 0xff
};
enum SampleProfileLayout {
SPL_None = 0,
SPL_Nest = 0x1,
SPL_Flat = 0x2,
};
static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) {
return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
uint64_t('2') << (64 - 56) | uint64_t(Format);
}
static inline uint64_t SPVersion() { return 103; }
// Section Type used by SampleProfileExtBinaryBaseReader and
// SampleProfileExtBinaryBaseWriter. Never change the existing
// value of enum. Only append new ones.
enum SecType {
SecInValid = 0,
SecProfSummary = 1,
SecNameTable = 2,
SecProfileSymbolList = 3,
SecFuncOffsetTable = 4,
SecFuncMetadata = 5,
SecCSNameTable = 6,
// marker for the first type of profile.
SecFuncProfileFirst = 32,
SecLBRProfile = SecFuncProfileFirst
};
static inline std::string getSecName(SecType Type) {
switch ((int)Type) { // Avoid -Wcovered-switch-default
case SecInValid:
return "InvalidSection";
case SecProfSummary:
return "ProfileSummarySection";
case SecNameTable:
return "NameTableSection";
case SecProfileSymbolList:
return "ProfileSymbolListSection";
case SecFuncOffsetTable:
return "FuncOffsetTableSection";
case SecFuncMetadata:
return "FunctionMetadata";
case SecCSNameTable:
return "CSNameTableSection";
case SecLBRProfile:
return "LBRProfileSection";
default:
return "UnknownSection";
}
}
// Entry type of section header table used by SampleProfileExtBinaryBaseReader
// and SampleProfileExtBinaryBaseWriter.
struct SecHdrTableEntry {
SecType Type;
uint64_t Flags;
uint64_t Offset;
uint64_t Size;
// The index indicating the location of the current entry in
// SectionHdrLayout table.
uint64_t LayoutIndex;
};
// Flags common for all sections are defined here. In SecHdrTableEntry::Flags,
// common flags will be saved in the lower 32bits and section specific flags
// will be saved in the higher 32 bits.
enum class SecCommonFlags : uint32_t {
SecFlagInValid = 0,
SecFlagCompress = (1 << 0),
// Indicate the section contains only profile without context.
SecFlagFlat = (1 << 1)
};
// Section specific flags are defined here.
// !!!Note: Everytime a new enum class is created here, please add
// a new check in verifySecFlag.
enum class SecNameTableFlags : uint32_t {
SecFlagInValid = 0,
SecFlagMD5Name = (1 << 0),
// Store MD5 in fixed length instead of ULEB128 so NameTable can be
// accessed like an array.
SecFlagFixedLengthMD5 = (1 << 1),
// Profile contains ".__uniq." suffix name. Compiler shouldn't strip
// the suffix when doing profile matching when seeing the flag.
SecFlagUniqSuffix = (1 << 2)
};
enum class SecProfSummaryFlags : uint32_t {
SecFlagInValid = 0,
/// SecFlagPartial means the profile is for common/shared code.
/// The common profile is usually merged from profiles collected
/// from running other targets.
SecFlagPartial = (1 << 0),
/// SecFlagContext means this is context-sensitive flat profile for
/// CSSPGO
SecFlagFullContext = (1 << 1),
/// SecFlagFSDiscriminator means this profile uses flow-sensitive
/// discriminators.
SecFlagFSDiscriminator = (1 << 2),
/// SecFlagIsPreInlined means this profile contains ShouldBeInlined
/// contexts thus this is CS preinliner computed.
SecFlagIsPreInlined = (1 << 4),
};
enum class SecFuncMetadataFlags : uint32_t {
SecFlagInvalid = 0,
SecFlagIsProbeBased = (1 << 0),
SecFlagHasAttribute = (1 << 1),
};
enum class SecFuncOffsetFlags : uint32_t {
SecFlagInvalid = 0,
// Store function offsets in an order of contexts. The order ensures that
// callee contexts of a given context laid out next to it.
SecFlagOrdered = (1 << 0),
};
// Verify section specific flag is used for the correct section.
template <class SecFlagType>
static inline void verifySecFlag(SecType Type, SecFlagType Flag) {
// No verification is needed for common flags.
if (std::is_same<SecCommonFlags, SecFlagType>())
return;
// Verification starts here for section specific flag.
bool IsFlagLegal = false;
switch (Type) {
case SecNameTable:
IsFlagLegal = std::is_same<SecNameTableFlags, SecFlagType>();
break;
case SecProfSummary:
IsFlagLegal = std::is_same<SecProfSummaryFlags, SecFlagType>();
break;
case SecFuncMetadata:
IsFlagLegal = std::is_same<SecFuncMetadataFlags, SecFlagType>();
break;
default:
case SecFuncOffsetTable:
IsFlagLegal = std::is_same<SecFuncOffsetFlags, SecFlagType>();
break;
}
if (!IsFlagLegal)
llvm_unreachable("Misuse of a flag in an incompatible section");
}
template <class SecFlagType>
static inline void addSecFlag(SecHdrTableEntry &Entry, SecFlagType Flag) {
verifySecFlag(Entry.Type, Flag);
auto FVal = static_cast<uint64_t>(Flag);
bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>();
Entry.Flags |= IsCommon ? FVal : (FVal << 32);
}
template <class SecFlagType>
static inline void removeSecFlag(SecHdrTableEntry &Entry, SecFlagType Flag) {
verifySecFlag(Entry.Type, Flag);
auto FVal = static_cast<uint64_t>(Flag);
bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>();
Entry.Flags &= ~(IsCommon ? FVal : (FVal << 32));
}
template <class SecFlagType>
static inline bool hasSecFlag(const SecHdrTableEntry &Entry, SecFlagType Flag) {
verifySecFlag(Entry.Type, Flag);
auto FVal = static_cast<uint64_t>(Flag);
bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>();
return Entry.Flags & (IsCommon ? FVal : (FVal << 32));
}
/// Represents the relative location of an instruction.
///
/// Instruction locations are specified by the line offset from the
/// beginning of the function (marked by the line where the function
/// header is) and the discriminator value within that line.
///
/// The discriminator value is useful to distinguish instructions
/// that are on the same line but belong to different basic blocks
/// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
struct LineLocation {
LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
void print(raw_ostream &OS) const;
void dump() const;
bool operator<(const LineLocation &O) const {
return LineOffset < O.LineOffset ||
(LineOffset == O.LineOffset && Discriminator < O.Discriminator);
}
bool operator==(const LineLocation &O) const {
return LineOffset == O.LineOffset && Discriminator == O.Discriminator;
}
bool operator!=(const LineLocation &O) const {
return LineOffset != O.LineOffset || Discriminator != O.Discriminator;
}
uint64_t getHashCode() const {
return ((uint64_t) Discriminator << 32) | LineOffset;
}
uint32_t LineOffset;
uint32_t Discriminator;
};
struct LineLocationHash {
uint64_t operator()(const LineLocation &Loc) const {
return Loc.getHashCode();
}
};
raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc);
/// Representation of a single sample record.
///
/// A sample record is represented by a positive integer value, which
/// indicates how frequently was the associated line location executed.
///
/// Additionally, if the associated location contains a function call,
/// the record will hold a list of all the possible called targets. For
/// direct calls, this will be the exact function being invoked. For
/// indirect calls (function pointers, virtual table dispatch), this
/// will be a list of one or more functions.
class SampleRecord {
public:
using CallTarget = std::pair<FunctionId, uint64_t>;
struct CallTargetComparator {
bool operator()(const CallTarget &LHS, const CallTarget &RHS) const {
if (LHS.second != RHS.second)
return LHS.second > RHS.second;
return LHS.first < RHS.first;
}
};
using SortedCallTargetSet = std::set<CallTarget, CallTargetComparator>;
using CallTargetMap = std::unordered_map<FunctionId, uint64_t>;
SampleRecord() = default;
/// Increment the number of samples for this record by \p S.
/// Optionally scale sample count \p S by \p Weight.
///
/// Sample counts accumulate using saturating arithmetic, to avoid wrapping
/// around unsigned integers.
sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
bool Overflowed;
NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
return Overflowed ? sampleprof_error::counter_overflow
: sampleprof_error::success;
}
/// Decrease the number of samples for this record by \p S. Return the amout
/// of samples actually decreased.
uint64_t removeSamples(uint64_t S) {
if (S > NumSamples)
S = NumSamples;
NumSamples -= S;
return S;
}
/// Add called function \p F with samples \p S.
/// Optionally scale sample count \p S by \p Weight.
///
/// Sample counts accumulate using saturating arithmetic, to avoid wrapping
/// around unsigned integers.
sampleprof_error addCalledTarget(FunctionId F, uint64_t S,
uint64_t Weight = 1) {
uint64_t &TargetSamples = CallTargets[F];
bool Overflowed;
TargetSamples =
SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
return Overflowed ? sampleprof_error::counter_overflow
: sampleprof_error::success;
}
/// Remove called function from the call target map. Return the target sample
/// count of the called function.
uint64_t removeCalledTarget(FunctionId F) {
uint64_t Count = 0;
auto I = CallTargets.find(F);
if (I != CallTargets.end()) {
Count = I->second;
CallTargets.erase(I);
}
return Count;
}
/// Return true if this sample record contains function calls.
bool hasCalls() const { return !CallTargets.empty(); }
uint64_t getSamples() const { return NumSamples; }
const CallTargetMap &getCallTargets() const { return CallTargets; }
const SortedCallTargetSet getSortedCallTargets() const {
return SortCallTargets(CallTargets);
}
uint64_t getCallTargetSum() const {
uint64_t Sum = 0;
for (const auto &I : CallTargets)
Sum += I.second;
return Sum;
}
/// Sort call targets in descending order of call frequency.
static const SortedCallTargetSet SortCallTargets(const CallTargetMap &Targets) {
SortedCallTargetSet SortedTargets;
for (const auto &[Target, Frequency] : Targets) {
SortedTargets.emplace(Target, Frequency);
}
return SortedTargets;
}
/// Prorate call targets by a distribution factor.
static const CallTargetMap adjustCallTargets(const CallTargetMap &Targets,
float DistributionFactor) {
CallTargetMap AdjustedTargets;
for (const auto &[Target, Frequency] : Targets) {
AdjustedTargets[Target] = Frequency * DistributionFactor;
}
return AdjustedTargets;
}
/// Merge the samples in \p Other into this record.
/// Optionally scale sample counts by \p Weight.
sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1);
void print(raw_ostream &OS, unsigned Indent) const;
void dump() const;
bool operator==(const SampleRecord &Other) const {
return NumSamples == Other.NumSamples && CallTargets == Other.CallTargets;
}
bool operator!=(const SampleRecord &Other) const {
return !(*this == Other);
}
private:
uint64_t NumSamples = 0;
CallTargetMap CallTargets;
};
raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
// State of context associated with FunctionSamples
enum ContextStateMask {
UnknownContext = 0x0, // Profile without context
RawContext = 0x1, // Full context profile from input profile
SyntheticContext = 0x2, // Synthetic context created for context promotion
InlinedContext = 0x4, // Profile for context that is inlined into caller
MergedContext = 0x8 // Profile for context merged into base profile
};
// Attribute of context associated with FunctionSamples
enum ContextAttributeMask {
ContextNone = 0x0,
ContextWasInlined = 0x1, // Leaf of context was inlined in previous build
ContextShouldBeInlined = 0x2, // Leaf of context should be inlined
ContextDuplicatedIntoBase =
0x4, // Leaf of context is duplicated into the base profile
};
// Represents a context frame with profile function and line location
struct SampleContextFrame {
FunctionId Func;
LineLocation Location;
SampleContextFrame() : Location(0, 0) {}
SampleContextFrame(FunctionId Func, LineLocation Location)
: Func(Func), Location(Location) {}
bool operator==(const SampleContextFrame &That) const {
return Location == That.Location && Func == That.Func;
}
bool operator!=(const SampleContextFrame &That) const {
return !(*this == That);
}
std::string toString(bool OutputLineLocation) const {
std::ostringstream OContextStr;
OContextStr << Func.str();
if (OutputLineLocation) {
OContextStr << ":" << Location.LineOffset;
if (Location.Discriminator)
OContextStr << "." << Location.Discriminator;
}
return OContextStr.str();
}
uint64_t getHashCode() const {
uint64_t NameHash = Func.getHashCode();
uint64_t LocId = Location.getHashCode();
return NameHash + (LocId << 5) + LocId;
}
};
static inline hash_code hash_value(const SampleContextFrame &arg) {
return arg.getHashCode();
}
using SampleContextFrameVector = SmallVector<SampleContextFrame, 1>;
using SampleContextFrames = ArrayRef<SampleContextFrame>;
struct SampleContextFrameHash {
uint64_t operator()(const SampleContextFrameVector &S) const {
return hash_combine_range(S.begin(), S.end());
}
};
// Sample context for FunctionSamples. It consists of the calling context,
// the function name and context state. Internally sample context is represented
// using ArrayRef, which is also the input for constructing a `SampleContext`.
// It can accept and represent both full context string as well as context-less
// function name.
// For a CS profile, a full context vector can look like:
// `main:3 _Z5funcAi:1 _Z8funcLeafi`
// For a base CS profile without calling context, the context vector should only
// contain the leaf frame name.
// For a non-CS profile, the context vector should be empty.
class SampleContext {
public:
SampleContext() : State(UnknownContext), Attributes(ContextNone) {}
SampleContext(StringRef Name)
: Func(Name), State(UnknownContext), Attributes(ContextNone) {
assert(!Name.empty() && "Name is empty");
}
SampleContext(FunctionId Func)
: Func(Func), State(UnknownContext), Attributes(ContextNone) {}
SampleContext(SampleContextFrames Context,
ContextStateMask CState = RawContext)
: Attributes(ContextNone) {
assert(!Context.empty() && "Context is empty");
setContext(Context, CState);
}
// Give a context string, decode and populate internal states like
// Function name, Calling context and context state. Example of input
// `ContextStr`: `[main:3 @ _Z5funcAi:1 @ _Z8funcLeafi]`
SampleContext(StringRef ContextStr,
std::list<SampleContextFrameVector> &CSNameTable,
ContextStateMask CState = RawContext)
: Attributes(ContextNone) {
assert(!ContextStr.empty());
// Note that `[]` wrapped input indicates a full context string, otherwise
// it's treated as context-less function name only.
bool HasContext = ContextStr.starts_with("[");
if (!HasContext) {
State = UnknownContext;
Func = FunctionId(ContextStr);
} else {
CSNameTable.emplace_back();
SampleContextFrameVector &Context = CSNameTable.back();
createCtxVectorFromStr(ContextStr, Context);
setContext(Context, CState);
}
}
/// Create a context vector from a given context string and save it in
/// `Context`.
static void createCtxVectorFromStr(StringRef ContextStr,
SampleContextFrameVector &Context) {
// Remove encapsulating '[' and ']' if any
ContextStr = ContextStr.substr(1, ContextStr.size() - 2);
StringRef ContextRemain = ContextStr;
StringRef ChildContext;
FunctionId Callee;
while (!ContextRemain.empty()) {
auto ContextSplit = ContextRemain.split(" @ ");
ChildContext = ContextSplit.first;
ContextRemain = ContextSplit.second;
LineLocation CallSiteLoc(0, 0);
decodeContextString(ChildContext, Callee, CallSiteLoc);
Context.emplace_back(Callee, CallSiteLoc);
}
}
// Decode context string for a frame to get function name and location.
// `ContextStr` is in the form of `FuncName:StartLine.Discriminator`.
static void decodeContextString(StringRef ContextStr,
FunctionId &Func,
LineLocation &LineLoc) {
// Get function name
auto EntrySplit = ContextStr.split(':');
Func = FunctionId(EntrySplit.first);
LineLoc = {0, 0};
if (!EntrySplit.second.empty()) {
// Get line offset, use signed int for getAsInteger so string will
// be parsed as signed.
int LineOffset = 0;
auto LocSplit = EntrySplit.second.split('.');
LocSplit.first.getAsInteger(10, LineOffset);
LineLoc.LineOffset = LineOffset;
// Get discriminator
if (!LocSplit.second.empty())
LocSplit.second.getAsInteger(10, LineLoc.Discriminator);
}
}
operator SampleContextFrames() const { return FullContext; }
bool hasAttribute(ContextAttributeMask A) { return Attributes & (uint32_t)A; }
void setAttribute(ContextAttributeMask A) { Attributes |= (uint32_t)A; }
uint32_t getAllAttributes() { return Attributes; }
void setAllAttributes(uint32_t A) { Attributes = A; }
bool hasState(ContextStateMask S) { return State & (uint32_t)S; }
void setState(ContextStateMask S) { State |= (uint32_t)S; }
void clearState(ContextStateMask S) { State &= (uint32_t)~S; }
bool hasContext() const { return State != UnknownContext; }
bool isBaseContext() const { return FullContext.size() == 1; }
FunctionId getFunction() const { return Func; }
SampleContextFrames getContextFrames() const { return FullContext; }
static std::string getContextString(SampleContextFrames Context,
bool IncludeLeafLineLocation = false) {
std::ostringstream OContextStr;
for (uint32_t I = 0; I < Context.size(); I++) {
if (OContextStr.str().size()) {
OContextStr << " @ ";
}
OContextStr << Context[I].toString(I != Context.size() - 1 ||
IncludeLeafLineLocation);
}
return OContextStr.str();
}
std::string toString() const {
if (!hasContext())
return Func.str();
return getContextString(FullContext, false);
}
uint64_t getHashCode() const {
if (hasContext())
return hash_value(getContextFrames());
return getFunction().getHashCode();
}
/// Set the name of the function and clear the current context.
void setFunction(FunctionId newFunction) {
Func = newFunction;
FullContext = SampleContextFrames();
State = UnknownContext;
}
void setContext(SampleContextFrames Context,
ContextStateMask CState = RawContext) {
assert(CState != UnknownContext);
FullContext = Context;
Func = Context.back().Func;
State = CState;
}
bool operator==(const SampleContext &That) const {
return State == That.State && Func == That.Func &&
FullContext == That.FullContext;
}
bool operator!=(const SampleContext &That) const { return !(*this == That); }
bool operator<(const SampleContext &That) const {
if (State != That.State)
return State < That.State;
if (!hasContext()) {
return Func < That.Func;
}
uint64_t I = 0;
while (I < std::min(FullContext.size(), That.FullContext.size())) {
auto &Context1 = FullContext[I];
auto &Context2 = That.FullContext[I];
auto V = Context1.Func.compare(Context2.Func);
if (V)
return V < 0;
if (Context1.Location != Context2.Location)
return Context1.Location < Context2.Location;
I++;
}
return FullContext.size() < That.FullContext.size();
}
struct Hash {
uint64_t operator()(const SampleContext &Context) const {
return Context.getHashCode();
}
};
bool IsPrefixOf(const SampleContext &That) const {
auto ThisContext = FullContext;
auto ThatContext = That.FullContext;
if (ThatContext.size() < ThisContext.size())
return false;
ThatContext = ThatContext.take_front(ThisContext.size());
// Compare Leaf frame first
if (ThisContext.back().Func != ThatContext.back().Func)
return false;
// Compare leading context
return ThisContext.drop_back() == ThatContext.drop_back();
}
private:
// The function associated with this context. If CS profile, this is the leaf
// function.
FunctionId Func;
// Full context including calling context and leaf function name
SampleContextFrames FullContext;
// State of the associated sample profile
uint32_t State;
// Attribute of the associated sample profile
uint32_t Attributes;
};
static inline hash_code hash_value(const SampleContext &Context) {
return Context.getHashCode();
}
inline raw_ostream &operator<<(raw_ostream &OS, const SampleContext &Context) {
return OS << Context.toString();
}
class FunctionSamples;
class SampleProfileReaderItaniumRemapper;
using BodySampleMap = std::map<LineLocation, SampleRecord>;
// NOTE: Using a StringMap here makes parsed profiles consume around 17% more
// memory, which is *very* significant for large profiles.
using FunctionSamplesMap = std::map<FunctionId, FunctionSamples>;
using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
using LocToLocMap =
std::unordered_map<LineLocation, LineLocation, LineLocationHash>;
/// Representation of the samples collected for a function.
///
/// This data structure contains all the collected samples for the body
/// of a function. Each sample corresponds to a LineLocation instance
/// within the body of the function.
class FunctionSamples {
public:
FunctionSamples() = default;
void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
void dump() const;
sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
bool Overflowed;
TotalSamples =
SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
return Overflowed ? sampleprof_error::counter_overflow
: sampleprof_error::success;
}
void removeTotalSamples(uint64_t Num) {
if (TotalSamples < Num)
TotalSamples = 0;
else
TotalSamples -= Num;
}
void setTotalSamples(uint64_t Num) { TotalSamples = Num; }
void setHeadSamples(uint64_t Num) { TotalHeadSamples = Num; }
sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
bool Overflowed;
TotalHeadSamples =
SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
return Overflowed ? sampleprof_error::counter_overflow
: sampleprof_error::success;
}
sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
uint64_t Num, uint64_t Weight = 1) {
return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
Num, Weight);
}
sampleprof_error addCalledTargetSamples(uint32_t LineOffset,
uint32_t Discriminator,
FunctionId Func,
uint64_t Num,
uint64_t Weight = 1) {
return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
Func, Num, Weight);
}
sampleprof_error addSampleRecord(LineLocation Location,
const SampleRecord &SampleRecord,
uint64_t Weight = 1) {
return BodySamples[Location].merge(SampleRecord, Weight);
}
// Remove a call target and decrease the body sample correspondingly. Return
// the number of body samples actually decreased.
uint64_t removeCalledTargetAndBodySample(uint32_t LineOffset,
uint32_t Discriminator,
FunctionId Func) {
uint64_t Count = 0;
auto I = BodySamples.find(LineLocation(LineOffset, Discriminator));
if (I != BodySamples.end()) {
Count = I->second.removeCalledTarget(Func);
Count = I->second.removeSamples(Count);
if (!I->second.getSamples())
BodySamples.erase(I);
}
return Count;
}
// Remove all call site samples for inlinees. This is needed when flattening
// a nested profile.
void removeAllCallsiteSamples() {
CallsiteSamples.clear();
}
// Accumulate all call target samples to update the body samples.
void updateCallsiteSamples() {
for (auto &I : BodySamples) {
uint64_t TargetSamples = I.second.getCallTargetSum();
// It's possible that the body sample count can be greater than the call
// target sum. E.g, if some call targets are external targets, they won't
// be considered valid call targets, but the body sample count which is
// from lbr ranges can actually include them.
if (TargetSamples > I.second.getSamples())
I.second.addSamples(TargetSamples - I.second.getSamples());
}
}
// Accumulate all body samples to set total samples.
void updateTotalSamples() {
setTotalSamples(0);
for (const auto &I : BodySamples)
addTotalSamples(I.second.getSamples());
for (auto &I : CallsiteSamples) {
for (auto &CS : I.second) {
CS.second.updateTotalSamples();
addTotalSamples(CS.second.getTotalSamples());
}
}
}
// Set current context and all callee contexts to be synthetic.
void SetContextSynthetic() {
Context.setState(SyntheticContext);
for (auto &I : CallsiteSamples) {
for (auto &CS : I.second) {
CS.second.SetContextSynthetic();
}
}
}
// Query the stale profile matching results and remap the location.
const LineLocation &mapIRLocToProfileLoc(const LineLocation &IRLoc) const {
// There is no remapping if the profile is not stale or the matching gives
// the same location.
if (!IRToProfileLocationMap)
return IRLoc;
const auto &ProfileLoc = IRToProfileLocationMap->find(IRLoc);
if (ProfileLoc != IRToProfileLocationMap->end())
return ProfileLoc->second;
else
return IRLoc;
}
/// Return the number of samples collected at the given location.
/// Each location is specified by \p LineOffset and \p Discriminator.
/// If the location is not found in profile, return error.
ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
uint32_t Discriminator) const {
const auto &ret = BodySamples.find(
mapIRLocToProfileLoc(LineLocation(LineOffset, Discriminator)));
if (ret == BodySamples.end())
return std::error_code();
return ret->second.getSamples();
}
/// Returns the call target map collected at a given location.
/// Each location is specified by \p LineOffset and \p Discriminator.
/// If the location is not found in profile, return error.
ErrorOr<const SampleRecord::CallTargetMap &>
findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
const auto &ret = BodySamples.find(
mapIRLocToProfileLoc(LineLocation(LineOffset, Discriminator)));
if (ret == BodySamples.end())
return std::error_code();
return ret->second.getCallTargets();
}
/// Returns the call target map collected at a given location specified by \p
/// CallSite. If the location is not found in profile, return error.
ErrorOr<const SampleRecord::CallTargetMap &>
findCallTargetMapAt(const LineLocation &CallSite) const {
const auto &Ret = BodySamples.find(mapIRLocToProfileLoc(CallSite));
if (Ret == BodySamples.end())
return std::error_code();
return Ret->second.getCallTargets();
}
/// Return the function samples at the given callsite location.
FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
return CallsiteSamples[mapIRLocToProfileLoc(Loc)];
}
/// Returns the FunctionSamplesMap at the given \p Loc.
const FunctionSamplesMap *
findFunctionSamplesMapAt(const LineLocation &Loc) const {
auto iter = CallsiteSamples.find(mapIRLocToProfileLoc(Loc));
if (iter == CallsiteSamples.end())
return nullptr;
return &iter->second;
}
/// Returns a pointer to FunctionSamples at the given callsite location
/// \p Loc with callee \p CalleeName. If no callsite can be found, relax
/// the restriction to return the FunctionSamples at callsite location
/// \p Loc with the maximum total sample count. If \p Remapper is not
/// nullptr, use \p Remapper to find FunctionSamples with equivalent name
/// as \p CalleeName.
const FunctionSamples *
findFunctionSamplesAt(const LineLocation &Loc, StringRef CalleeName,
SampleProfileReaderItaniumRemapper *Remapper) const;
bool empty() const { return TotalSamples == 0; }
/// Return the total number of samples collected inside the function.
uint64_t getTotalSamples() const { return TotalSamples; }
/// For top-level functions, return the total number of branch samples that
/// have the function as the branch target (or 0 otherwise). This is the raw
/// data fetched from the profile. This should be equivalent to the sample of
/// the first instruction of the symbol. But as we directly get this info for
/// raw profile without referring to potentially inaccurate debug info, this
/// gives more accurate profile data and is preferred for standalone symbols.
uint64_t getHeadSamples() const { return TotalHeadSamples; }
/// Return an estimate of the sample count of the function entry basic block.
/// The function can be either a standalone symbol or an inlined function.
/// For Context-Sensitive profiles, this will prefer returning the head
/// samples (i.e. getHeadSamples()), if non-zero. Otherwise it estimates from
/// the function body's samples or callsite samples.
uint64_t getHeadSamplesEstimate() const {
if (FunctionSamples::ProfileIsCS && getHeadSamples()) {
// For CS profile, if we already have more accurate head samples
// counted by branch sample from caller, use them as entry samples.
return getHeadSamples();
}
uint64_t Count = 0;
// Use either BodySamples or CallsiteSamples which ever has the smaller
// lineno.
if (!BodySamples.empty() &&
(CallsiteSamples.empty() ||
BodySamples.begin()->first < CallsiteSamples.begin()->first))
Count = BodySamples.begin()->second.getSamples();
else if (!CallsiteSamples.empty()) {
// An indirect callsite may be promoted to several inlined direct calls.
// We need to get the sum of them.
for (const auto &N_FS : CallsiteSamples.begin()->second)
Count += N_FS.second.getHeadSamplesEstimate();
}
// Return at least 1 if total sample is not 0.
return Count ? Count : TotalSamples > 0;
}
/// Return all the samples collected in the body of the function.
const BodySampleMap &getBodySamples() const { return BodySamples; }
/// Return all the callsite samples collected in the body of the function.
const CallsiteSampleMap &getCallsiteSamples() const {
return CallsiteSamples;
}
/// Return the maximum of sample counts in a function body. When SkipCallSite
/// is false, which is the default, the return count includes samples in the
/// inlined functions. When SkipCallSite is true, the return count only
/// considers the body samples.
uint64_t getMaxCountInside(bool SkipCallSite = false) const {
uint64_t MaxCount = 0;
for (const auto &L : getBodySamples())
MaxCount = std::max(MaxCount, L.second.getSamples());
if (SkipCallSite)
return MaxCount;
for (const auto &C : getCallsiteSamples())
for (const FunctionSamplesMap::value_type &F : C.second)
MaxCount = std::max(MaxCount, F.second.getMaxCountInside());
return MaxCount;
}
/// Merge the samples in \p Other into this one.
/// Optionally scale samples by \p Weight.
sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
sampleprof_error Result = sampleprof_error::success;
if (!GUIDToFuncNameMap)
GUIDToFuncNameMap = Other.GUIDToFuncNameMap;
if (Context.getFunction().empty())