diff options
Diffstat (limited to 'include/llvm/ProfileData/SampleProf.h')
| -rw-r--r-- | include/llvm/ProfileData/SampleProf.h | 301 |
1 files changed, 219 insertions, 82 deletions
diff --git a/include/llvm/ProfileData/SampleProf.h b/include/llvm/ProfileData/SampleProf.h index 1b82e55aa77a..8df3fe803209 100644 --- a/include/llvm/ProfileData/SampleProf.h +++ b/include/llvm/ProfileData/SampleProf.h @@ -11,14 +11,17 @@ // sample profile data. // //===----------------------------------------------------------------------===// + #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H_ #define LLVM_PROFILEDATA_SAMPLEPROF_H_ -#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorOr.h" #include "llvm/Support/raw_ostream.h" + +#include <map> #include <system_error> namespace llvm { @@ -32,13 +35,27 @@ enum class sampleprof_error { too_large, truncated, malformed, - unrecognized_format + unrecognized_format, + unsupported_writing_format, + truncated_name_table, + not_implemented, + counter_overflow }; 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 { @@ -57,7 +74,7 @@ static inline uint64_t SPMagic() { uint64_t('2') << (64 - 56) | uint64_t(0xff); } -static inline uint64_t SPVersion() { return 100; } +static inline uint64_t SPVersion() { return 102; } /// Represents the relative location of an instruction. /// @@ -69,36 +86,36 @@ static inline uint64_t SPVersion() { return 100; } /// 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(int L, unsigned D) : LineOffset(L), Discriminator(D) {} - int LineOffset; - unsigned Discriminator; + 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); + } + + uint32_t LineOffset; + uint32_t Discriminator; }; -} // End namespace sampleprof +raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc); -template <> struct DenseMapInfo<sampleprof::LineLocation> { - typedef DenseMapInfo<int> OffsetInfo; - typedef DenseMapInfo<unsigned> DiscriminatorInfo; - static inline sampleprof::LineLocation getEmptyKey() { - return sampleprof::LineLocation(OffsetInfo::getEmptyKey(), - DiscriminatorInfo::getEmptyKey()); - } - static inline sampleprof::LineLocation getTombstoneKey() { - return sampleprof::LineLocation(OffsetInfo::getTombstoneKey(), - DiscriminatorInfo::getTombstoneKey()); - } - static inline unsigned getHashValue(sampleprof::LineLocation Val) { - return DenseMapInfo<std::pair<int, unsigned>>::getHashValue( - std::pair<int, unsigned>(Val.LineOffset, Val.Discriminator)); - } - static inline bool isEqual(sampleprof::LineLocation LHS, - sampleprof::LineLocation RHS) { - return LHS.LineOffset == RHS.LineOffset && - LHS.Discriminator == RHS.Discriminator; - } +/// Represents the relative location of a callsite. +/// +/// Callsite locations are specified by the line offset from the +/// beginning of the function (marked by the line where the function +/// head is), the discriminator value within that line, and the callee +/// function name. +struct CallsiteLocation : public LineLocation { + CallsiteLocation(uint32_t L, uint32_t D, StringRef N) + : LineLocation(L, D), CalleeName(N) {} + void print(raw_ostream &OS) const; + void dump() const; + + StringRef CalleeName; }; -namespace sampleprof { +raw_ostream &operator<<(raw_ostream &OS, const CallsiteLocation &Loc); /// Representation of a single sample record. /// @@ -112,52 +129,79 @@ namespace sampleprof { /// will be a list of one or more functions. class SampleRecord { public: - typedef StringMap<unsigned> CallTargetMap; + typedef StringMap<uint64_t> CallTargetMap; SampleRecord() : NumSamples(0), CallTargets() {} /// 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. - void addSamples(unsigned S) { - if (NumSamples <= std::numeric_limits<unsigned>::max() - S) - NumSamples += S; - else - NumSamples = std::numeric_limits<unsigned>::max(); + sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) { + bool Overflowed; + if (Weight > 1) { + S = SaturatingMultiply(S, Weight, &Overflowed); + if (Overflowed) + return sampleprof_error::counter_overflow; + } + NumSamples = SaturatingAdd(NumSamples, S, &Overflowed); + if (Overflowed) + return sampleprof_error::counter_overflow; + + return sampleprof_error::success; } /// 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. - void addCalledTarget(StringRef F, unsigned S) { - unsigned &TargetSamples = CallTargets[F]; - if (TargetSamples <= std::numeric_limits<unsigned>::max() - S) - TargetSamples += S; - else - TargetSamples = std::numeric_limits<unsigned>::max(); + sampleprof_error addCalledTarget(StringRef F, uint64_t S, + uint64_t Weight = 1) { + uint64_t &TargetSamples = CallTargets[F]; + bool Overflowed; + if (Weight > 1) { + S = SaturatingMultiply(S, Weight, &Overflowed); + if (Overflowed) + return sampleprof_error::counter_overflow; + } + TargetSamples = SaturatingAdd(TargetSamples, S, &Overflowed); + if (Overflowed) + return sampleprof_error::counter_overflow; + + return sampleprof_error::success; } /// Return true if this sample record contains function calls. bool hasCalls() const { return CallTargets.size() > 0; } - unsigned getSamples() const { return NumSamples; } + uint64_t getSamples() const { return NumSamples; } const CallTargetMap &getCallTargets() const { return CallTargets; } /// Merge the samples in \p Other into this record. - void merge(const SampleRecord &Other) { - addSamples(Other.getSamples()); - for (const auto &I : Other.getCallTargets()) - addCalledTarget(I.first(), I.second); + /// Optionally scale sample counts by \p Weight. + sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) { + sampleprof_error Result = addSamples(Other.getSamples(), Weight); + for (const auto &I : Other.getCallTargets()) { + MergeResult(Result, addCalledTarget(I.first(), I.second, Weight)); + } + return Result; } + void print(raw_ostream &OS, unsigned Indent) const; + void dump() const; + private: - unsigned NumSamples; + uint64_t NumSamples; CallTargetMap CallTargets; }; -typedef DenseMap<LineLocation, SampleRecord> BodySampleMap; +raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample); + +typedef std::map<LineLocation, SampleRecord> BodySampleMap; +class FunctionSamples; +typedef std::map<CallsiteLocation, FunctionSamples> CallsiteSampleMap; /// Representation of the samples collected for a function. /// @@ -167,59 +211,109 @@ typedef DenseMap<LineLocation, SampleRecord> BodySampleMap; class FunctionSamples { public: FunctionSamples() : TotalSamples(0), TotalHeadSamples(0) {} - void print(raw_ostream &OS = dbgs()); - void addTotalSamples(unsigned Num) { TotalSamples += Num; } - void addHeadSamples(unsigned Num) { TotalHeadSamples += Num; } - void addBodySamples(int LineOffset, unsigned Discriminator, unsigned Num) { - assert(LineOffset >= 0); - // When dealing with instruction weights, we use the value - // zero to indicate the absence of a sample. If we read an - // actual zero from the profile file, use the value 1 to - // avoid the confusion later on. - if (Num == 0) - Num = 1; - BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(Num); - } - void addCalledTargetSamples(int LineOffset, unsigned Discriminator, - std::string FName, unsigned Num) { - assert(LineOffset >= 0); - BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(FName, - Num); + 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; + if (Weight > 1) { + Num = SaturatingMultiply(Num, Weight, &Overflowed); + if (Overflowed) + return sampleprof_error::counter_overflow; + } + TotalSamples = SaturatingAdd(TotalSamples, Num, &Overflowed); + if (Overflowed) + return sampleprof_error::counter_overflow; + + return sampleprof_error::success; } + sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) { + bool Overflowed; + if (Weight > 1) { + Num = SaturatingMultiply(Num, Weight, &Overflowed); + if (Overflowed) + return sampleprof_error::counter_overflow; + } + TotalHeadSamples = SaturatingAdd(TotalHeadSamples, Num, &Overflowed); + if (Overflowed) + return sampleprof_error::counter_overflow; - /// Return the sample record at the given location. - /// Each location is specified by \p LineOffset and \p Discriminator. - SampleRecord &sampleRecordAt(const LineLocation &Loc) { - return BodySamples[Loc]; + return 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, + std::string FName, uint64_t Num, + uint64_t Weight = 1) { + return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget( + FName, Num, Weight); } /// Return the number of samples collected at the given location. /// Each location is specified by \p LineOffset and \p Discriminator. - unsigned samplesAt(int LineOffset, unsigned Discriminator) { - return sampleRecordAt(LineLocation(LineOffset, Discriminator)).getSamples(); + /// 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(LineLocation(LineOffset, Discriminator)); + if (ret == BodySamples.end()) + return std::error_code(); + else + return ret->second.getSamples(); } - bool empty() const { return BodySamples.empty(); } + /// Return the function samples at the given callsite location. + FunctionSamples &functionSamplesAt(const CallsiteLocation &Loc) { + return CallsiteSamples[Loc]; + } + + /// Return a pointer to function samples at the given callsite location. + const FunctionSamples * + findFunctionSamplesAt(const CallsiteLocation &Loc) const { + auto iter = CallsiteSamples.find(Loc); + if (iter == CallsiteSamples.end()) { + return nullptr; + } else { + return &iter->second; + } + } + + bool empty() const { return TotalSamples == 0; } /// Return the total number of samples collected inside the function. - unsigned getTotalSamples() const { return TotalSamples; } + uint64_t getTotalSamples() const { return TotalSamples; } /// Return the total number of samples collected at the head of the /// function. - unsigned getHeadSamples() const { return TotalHeadSamples; } + uint64_t getHeadSamples() const { return TotalHeadSamples; } /// 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; + } + /// Merge the samples in \p Other into this one. - void merge(const FunctionSamples &Other) { - addTotalSamples(Other.getTotalSamples()); - addHeadSamples(Other.getHeadSamples()); + /// Optionally scale samples by \p Weight. + sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) { + sampleprof_error Result = sampleprof_error::success; + MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight)); + MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight)); for (const auto &I : Other.getBodySamples()) { const LineLocation &Loc = I.first; const SampleRecord &Rec = I.second; - sampleRecordAt(Loc).merge(Rec); + MergeResult(Result, BodySamples[Loc].merge(Rec, Weight)); + } + for (const auto &I : Other.getCallsiteSamples()) { + const CallsiteLocation &Loc = I.first; + const FunctionSamples &Rec = I.second; + MergeResult(Result, functionSamplesAt(Loc).merge(Rec, Weight)); } + return Result; } private: @@ -227,12 +321,12 @@ private: /// /// Samples are cumulative, they include all the samples collected /// inside this function and all its inlined callees. - unsigned TotalSamples; + uint64_t TotalSamples; /// Total number of samples collected at the head of the function. /// This is an approximation of the number of calls made to this function /// at runtime. - unsigned TotalHeadSamples; + uint64_t TotalHeadSamples; /// Map instruction locations to collected samples. /// @@ -240,10 +334,53 @@ private: /// collected at the corresponding line offset. All line locations /// are an offset from the start of the function. BodySampleMap BodySamples; + + /// Map call sites to collected samples for the called function. + /// + /// Each entry in this map corresponds to all the samples + /// collected for the inlined function call at the given + /// location. For example, given: + /// + /// void foo() { + /// 1 bar(); + /// ... + /// 8 baz(); + /// } + /// + /// If the bar() and baz() calls were inlined inside foo(), this + /// map will contain two entries. One for all the samples collected + /// in the call to bar() at line offset 1, the other for all the samples + /// collected in the call to baz() at line offset 8. + CallsiteSampleMap CallsiteSamples; +}; + +raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS); + +/// Sort a LocationT->SampleT map by LocationT. +/// +/// It produces a sorted list of <LocationT, SampleT> records by ascending +/// order of LocationT. +template <class LocationT, class SampleT> class SampleSorter { +public: + typedef std::pair<const LocationT, SampleT> SamplesWithLoc; + typedef SmallVector<const SamplesWithLoc *, 20> SamplesWithLocList; + + SampleSorter(const std::map<LocationT, SampleT> &Samples) { + for (const auto &I : Samples) + V.push_back(&I); + std::stable_sort(V.begin(), V.end(), + [](const SamplesWithLoc *A, const SamplesWithLoc *B) { + return A->first < B->first; + }); + } + const SamplesWithLocList &get() const { return V; } + +private: + SamplesWithLocList V; }; -} // End namespace sampleprof +} // end namespace sampleprof -} // End namespace llvm +} // end namespace llvm #endif // LLVM_PROFILEDATA_SAMPLEPROF_H_ |