X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FProfileData%2FSampleProf.h;h=6c39cf9458dcb4f39e86303cef6b03b40f5fc4be;hp=ef782c11043d3005df352d201f9597a7ae383b8a;hb=21314fb7684a3055e440155016b95b91c7cae9bb;hpb=e75c2b3e5421c1d0b19f3d166001778c7ee80023 diff --git a/include/llvm/ProfileData/SampleProf.h b/include/llvm/ProfileData/SampleProf.h index ef782c11043..6c39cf9458d 100644 --- a/include/llvm/ProfileData/SampleProf.h +++ b/include/llvm/ProfileData/SampleProf.h @@ -11,13 +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 #include namespace llvm { @@ -30,13 +34,28 @@ enum class sampleprof_error { unsupported_version, too_large, truncated, - malformed + malformed, + 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(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 { @@ -55,9 +74,9 @@ 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; } -/// \brief Represents the relative location of an instruction. +/// 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 @@ -67,38 +86,38 @@ 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 { - typedef DenseMapInfo OffsetInfo; - typedef DenseMapInfo 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>::getHashValue( - std::pair(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); -/// \brief Representation of a single sample record. +/// 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. @@ -110,32 +129,68 @@ namespace sampleprof { /// will be a list of one or more functions. class SampleRecord { public: - typedef SmallVector, 8> CallTargetList; + typedef StringMap CallTargetMap; SampleRecord() : NumSamples(0), CallTargets() {} - /// \brief Increment the number of samples for this record by \p S. - void addSamples(unsigned S) { NumSamples += S; } + /// 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; + } - /// \brief Add called function \p F with samples \p S. - void addCalledTarget(std::string F, unsigned S) { - CallTargets.push_back(std::make_pair(F, 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(StringRef 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; } - /// \brief Return true if this sample record contains function calls. + /// Return true if this sample record contains function calls. bool hasCalls() const { return CallTargets.size() > 0; } - unsigned getSamples() const { return NumSamples; } - const CallTargetList &getCallTargets() const { return CallTargets; } + uint64_t getSamples() const { return NumSamples; } + const CallTargetMap &getCallTargets() const { return CallTargets; } + + /// 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) { + 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; - CallTargetList CallTargets; + uint64_t NumSamples; + CallTargetMap CallTargets; }; -typedef DenseMap BodySampleMap; +raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample); + +typedef std::map BodySampleMap; +class FunctionSamples; +typedef std::map CallsiteSampleMap; -/// \brief Representation of the samples collected for a function. +/// 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 @@ -143,64 +198,164 @@ typedef DenseMap BodySampleMap; class FunctionSamples { public: FunctionSamples() : TotalSamples(0), TotalHeadSamples(0) {} - void print(raw_ostream &OS); - 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 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; + } + 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; } - void addCalledTargetSamples(int LineOffset, unsigned Discriminator, - std::string FName, unsigned Num) { - assert(LineOffset >= 0); - BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(FName, - Num); + 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); } - /// \brief Return the number of samples collected at the given location. + /// 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 BodySamples[LineLocation(LineOffset, Discriminator)].getSamples(); + /// If the location is not found in profile, return error. + ErrorOr 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]; + } - /// \brief Return the total number of samples collected inside the function. - unsigned getTotalSamples() const { return TotalSamples; } + /// 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. + uint64_t getTotalSamples() const { return TotalSamples; } - /// \brief Return the total number of samples collected at the head of the + /// Return the total number of samples collected at the head of the /// function. - unsigned getHeadSamples() const { return TotalHeadSamples; } + uint64_t getHeadSamples() const { return TotalHeadSamples; } - /// \brief Return all the samples collected in the body of the function. + /// 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. + /// 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; + 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: - /// \brief Total number of samples collected inside this function. + /// Total number of samples collected inside this function. /// /// Samples are cumulative, they include all the samples collected /// inside this function and all its inlined callees. - unsigned TotalSamples; + uint64_t TotalSamples; - /// \brief Total number of samples collected at the head of the function. - unsigned TotalHeadSamples; + /// 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. + uint64_t TotalHeadSamples; - /// \brief Map instruction locations to collected samples. + /// Map instruction locations to collected samples. /// /// Each entry in this map contains the number of samples /// 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 records by ascending +/// order of LocationT. +template class SampleSorter { +public: + typedef std::pair SamplesWithLoc; + typedef SmallVector SamplesWithLocList; + + SampleSorter(const std::map &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_