LCOV - code coverage report
Current view: top level - include/llvm/ProfileData - SampleProf.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 95 98 96.9 %
Date: 2018-07-13 00:08:38 Functions: 15 15 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- SampleProf.h - Sampling profiling format support ---------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file contains common definitions used in the reading and writing of
      11             : // sample profile data.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H
      16             : #define LLVM_PROFILEDATA_SAMPLEPROF_H
      17             : 
      18             : #include "llvm/ADT/DenseSet.h"
      19             : #include "llvm/ADT/SmallVector.h"
      20             : #include "llvm/ADT/StringMap.h"
      21             : #include "llvm/ADT/StringRef.h"
      22             : #include "llvm/IR/Function.h"
      23             : #include "llvm/IR/GlobalValue.h"
      24             : #include "llvm/IR/Module.h"
      25             : #include "llvm/Support/Debug.h"
      26             : #include "llvm/Support/ErrorOr.h"
      27             : #include "llvm/Support/MathExtras.h"
      28             : #include <algorithm>
      29             : #include <cstdint>
      30             : #include <map>
      31             : #include <string>
      32             : #include <system_error>
      33             : #include <utility>
      34             : 
      35             : namespace llvm {
      36             : 
      37             : class raw_ostream;
      38             : 
      39             : const std::error_category &sampleprof_category();
      40             : 
      41             : enum class sampleprof_error {
      42             :   success = 0,
      43             :   bad_magic,
      44             :   unsupported_version,
      45             :   too_large,
      46             :   truncated,
      47             :   malformed,
      48             :   unrecognized_format,
      49             :   unsupported_writing_format,
      50             :   truncated_name_table,
      51             :   not_implemented,
      52             :   counter_overflow
      53             : };
      54             : 
      55             : inline std::error_code make_error_code(sampleprof_error E) {
      56        1160 :   return std::error_code(static_cast<int>(E), sampleprof_category());
      57             : }
      58             : 
      59             : inline sampleprof_error MergeResult(sampleprof_error &Accumulator,
      60             :                                     sampleprof_error Result) {
      61             :   // Prefer first error encountered as later errors may be secondary effects of
      62             :   // the initial problem.
      63        1297 :   if (Accumulator == sampleprof_error::success &&
      64             :       Result != sampleprof_error::success)
      65             :     Accumulator = Result;
      66             :   return Accumulator;
      67             : }
      68             : 
      69             : } // end namespace llvm
      70             : 
      71             : namespace std {
      72             : 
      73             : template <>
      74             : struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
      75             : 
      76             : } // end namespace std
      77             : 
      78             : namespace llvm {
      79             : namespace sampleprof {
      80             : 
      81             : enum SampleProfileFormat {
      82             :   SPF_None = 0,
      83             :   SPF_Text = 0x1,
      84             :   SPF_Compact_Binary = 0x2,
      85             :   SPF_GCC = 0x3,
      86             :   SPF_Binary = 0xff
      87             : };
      88             : 
      89             : static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) {
      90             :   return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
      91             :          uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
      92             :          uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
      93             :          uint64_t('2') << (64 - 56) | uint64_t(Format);
      94             : }
      95             : 
      96             : // Get the proper representation of a string in the input Format.
      97         366 : static inline StringRef getRepInFormat(StringRef Name,
      98             :                                        SampleProfileFormat Format,
      99             :                                        std::string &GUIDBuf) {
     100         366 :   if (Name.empty())
     101          31 :     return Name;
     102         670 :   GUIDBuf = std::to_string(Function::getGUID(Name));
     103         654 :   return (Format == SPF_Compact_Binary) ? StringRef(GUIDBuf) : Name;
     104             : }
     105             : 
     106             : static inline uint64_t SPVersion() { return 103; }
     107             : 
     108             : /// Represents the relative location of an instruction.
     109             : ///
     110             : /// Instruction locations are specified by the line offset from the
     111             : /// beginning of the function (marked by the line where the function
     112             : /// header is) and the discriminator value within that line.
     113             : ///
     114             : /// The discriminator value is useful to distinguish instructions
     115             : /// that are on the same line but belong to different basic blocks
     116             : /// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
     117             : struct LineLocation {
     118        2721 :   LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
     119             : 
     120             :   void print(raw_ostream &OS) const;
     121             :   void dump() const;
     122             : 
     123             :   bool operator<(const LineLocation &O) const {
     124        9343 :     return LineOffset < O.LineOffset ||
     125        4317 :            (LineOffset == O.LineOffset && Discriminator < O.Discriminator);
     126             :   }
     127             : 
     128             :   uint32_t LineOffset;
     129             :   uint32_t Discriminator;
     130             : };
     131             : 
     132             : raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc);
     133             : 
     134             : /// Representation of a single sample record.
     135             : ///
     136             : /// A sample record is represented by a positive integer value, which
     137             : /// indicates how frequently was the associated line location executed.
     138             : ///
     139             : /// Additionally, if the associated location contains a function call,
     140             : /// the record will hold a list of all the possible called targets. For
     141             : /// direct calls, this will be the exact function being invoked. For
     142             : /// indirect calls (function pointers, virtual table dispatch), this
     143             : /// will be a list of one or more functions.
     144         936 : class SampleRecord {
     145             : public:
     146             :   using CallTargetMap = StringMap<uint64_t>;
     147             : 
     148             :   SampleRecord() = default;
     149             : 
     150             :   /// Increment the number of samples for this record by \p S.
     151             :   /// Optionally scale sample count \p S by \p Weight.
     152             :   ///
     153             :   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
     154             :   /// around unsigned integers.
     155             :   sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
     156             :     bool Overflowed;
     157         999 :     NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
     158         999 :     return Overflowed ? sampleprof_error::counter_overflow
     159             :                       : sampleprof_error::success;
     160             :   }
     161             : 
     162             :   /// Add called function \p F with samples \p S.
     163             :   /// Optionally scale sample count \p S by \p Weight.
     164             :   ///
     165             :   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
     166             :   /// around unsigned integers.
     167         101 :   sampleprof_error addCalledTarget(StringRef F, uint64_t S,
     168             :                                    uint64_t Weight = 1) {
     169         101 :     uint64_t &TargetSamples = CallTargets[F];
     170             :     bool Overflowed;
     171         101 :     TargetSamples =
     172         101 :         SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
     173         101 :     return Overflowed ? sampleprof_error::counter_overflow
     174         101 :                       : sampleprof_error::success;
     175             :   }
     176             : 
     177             :   /// Return true if this sample record contains function calls.
     178         132 :   bool hasCalls() const { return !CallTargets.empty(); }
     179             : 
     180             :   uint64_t getSamples() const { return NumSamples; }
     181          34 :   const CallTargetMap &getCallTargets() const { return CallTargets; }
     182             : 
     183             :   /// Merge the samples in \p Other into this record.
     184             :   /// Optionally scale sample counts by \p Weight.
     185         251 :   sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) {
     186         251 :     sampleprof_error Result = addSamples(Other.getSamples(), Weight);
     187         524 :     for (const auto &I : Other.getCallTargets()) {
     188          44 :       MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
     189             :     }
     190         251 :     return Result;
     191             :   }
     192             : 
     193             :   void print(raw_ostream &OS, unsigned Indent) const;
     194             :   void dump() const;
     195             : 
     196             : private:
     197             :   uint64_t NumSamples = 0;
     198             :   CallTargetMap CallTargets;
     199             : };
     200             : 
     201             : raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
     202             : 
     203             : class FunctionSamples;
     204             : 
     205             : using BodySampleMap = std::map<LineLocation, SampleRecord>;
     206             : // NOTE: Using a StringMap here makes parsed profiles consume around 17% more
     207             : // memory, which is *very* significant for large profiles.
     208             : using FunctionSamplesMap = std::map<std::string, FunctionSamples>;
     209             : using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
     210             : 
     211             : /// Representation of the samples collected for a function.
     212             : ///
     213             : /// This data structure contains all the collected samples for the body
     214             : /// of a function. Each sample corresponds to a LineLocation instance
     215             : /// within the body of the function.
     216        1436 : class FunctionSamples {
     217             : public:
     218         380 :   FunctionSamples() = default;
     219             : 
     220             :   void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
     221             :   void dump() const;
     222             : 
     223             :   sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
     224             :     bool Overflowed;
     225         557 :     TotalSamples =
     226         557 :         SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
     227         309 :     return Overflowed ? sampleprof_error::counter_overflow
     228             :                       : sampleprof_error::success;
     229             :   }
     230             : 
     231             :   sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
     232             :     bool Overflowed;
     233         276 :     TotalHeadSamples =
     234         276 :         SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
     235         229 :     return Overflowed ? sampleprof_error::counter_overflow
     236             :                       : sampleprof_error::success;
     237             :   }
     238             : 
     239         748 :   sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
     240             :                                   uint64_t Num, uint64_t Weight = 1) {
     241        1496 :     return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
     242         748 :         Num, Weight);
     243             :   }
     244             : 
     245          28 :   sampleprof_error addCalledTargetSamples(uint32_t LineOffset,
     246             :                                           uint32_t Discriminator,
     247             :                                           StringRef FName, uint64_t Num,
     248             :                                           uint64_t Weight = 1) {
     249         158 :     return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
     250         107 :         FName, Num, Weight);
     251             :   }
     252             : 
     253             :   /// Return the number of samples collected at the given location.
     254             :   /// Each location is specified by \p LineOffset and \p Discriminator.
     255             :   /// If the location is not found in profile, return error.
     256         853 :   ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
     257             :                                   uint32_t Discriminator) const {
     258         853 :     const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
     259         853 :     if (ret == BodySamples.end())
     260             :       return std::error_code();
     261             :     else
     262         656 :       return ret->second.getSamples();
     263             :   }
     264             : 
     265             :   /// Returns the call target map collected at a given location.
     266             :   /// Each location is specified by \p LineOffset and \p Discriminator.
     267             :   /// If the location is not found in profile, return error.
     268             :   ErrorOr<SampleRecord::CallTargetMap>
     269          43 :   findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
     270          43 :     const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
     271          43 :     if (ret == BodySamples.end())
     272             :       return std::error_code();
     273             :     return ret->second.getCallTargets();
     274             :   }
     275             : 
     276             :   /// Return the function samples at the given callsite location.
     277             :   FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
     278         166 :     return CallsiteSamples[Loc];
     279             :   }
     280             : 
     281             :   /// Returns the FunctionSamplesMap at the given \p Loc.
     282             :   const FunctionSamplesMap *
     283             :   findFunctionSamplesMapAt(const LineLocation &Loc) const {
     284             :     auto iter = CallsiteSamples.find(Loc);
     285          21 :     if (iter == CallsiteSamples.end())
     286             :       return nullptr;
     287           9 :     return &iter->second;
     288             :   }
     289             : 
     290             :   /// Returns a pointer to FunctionSamples at the given callsite location \p Loc
     291             :   /// with callee \p CalleeName. If no callsite can be found, relax the
     292             :   /// restriction to return the FunctionSamples at callsite location \p Loc
     293             :   /// with the maximum total sample count.
     294         355 :   const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
     295             :                                                StringRef CalleeName) const {
     296             :     auto iter = CallsiteSamples.find(Loc);
     297         355 :     if (iter == CallsiteSamples.end())
     298             :       return nullptr;
     299         213 :     auto FS = iter->second.find(CalleeName);
     300         213 :     if (FS != iter->second.end())
     301         141 :       return &FS->second;
     302             :     // If we cannot find exact match of the callee name, return the FS with
     303             :     // the max total count.
     304             :     uint64_t MaxTotalSamples = 0;
     305             :     const FunctionSamples *R = nullptr;
     306         147 :     for (const auto &NameFS : iter->second)
     307          75 :       if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
     308             :         MaxTotalSamples = NameFS.second.getTotalSamples();
     309          75 :         R = &NameFS.second;
     310             :       }
     311             :     return R;
     312             :   }
     313             : 
     314             :   bool empty() const { return TotalSamples == 0; }
     315             : 
     316             :   /// Return the total number of samples collected inside the function.
     317             :   uint64_t getTotalSamples() const { return TotalSamples; }
     318             : 
     319             :   /// Return the total number of branch samples that have the function as the
     320             :   /// branch target. This should be equivalent to the sample of the first
     321             :   /// instruction of the symbol. But as we directly get this info for raw
     322             :   /// profile without referring to potentially inaccurate debug info, this
     323             :   /// gives more accurate profile data and is preferred for standalone symbols.
     324             :   uint64_t getHeadSamples() const { return TotalHeadSamples; }
     325             : 
     326             :   /// Return the sample count of the first instruction of the function.
     327             :   /// The function can be either a standalone symbol or an inlined function.
     328          25 :   uint64_t getEntrySamples() const {
     329             :     // Use either BodySamples or CallsiteSamples which ever has the smaller
     330             :     // lineno.
     331          50 :     if (!BodySamples.empty() &&
     332             :         (CallsiteSamples.empty() ||
     333             :          BodySamples.begin()->first < CallsiteSamples.begin()->first))
     334          25 :       return BodySamples.begin()->second.getSamples();
     335           0 :     if (!CallsiteSamples.empty()) {
     336             :       uint64_t T = 0;
     337             :       // An indirect callsite may be promoted to several inlined direct calls.
     338             :       // We need to get the sum of them.
     339           0 :       for (const auto &N_FS : CallsiteSamples.begin()->second)
     340           0 :         T += N_FS.second.getEntrySamples();
     341             :       return T;
     342             :     }
     343             :     return 0;
     344             :   }
     345             : 
     346             :   /// Return all the samples collected in the body of the function.
     347          43 :   const BodySampleMap &getBodySamples() const { return BodySamples; }
     348             : 
     349             :   /// Return all the callsite samples collected in the body of the function.
     350             :   const CallsiteSampleMap &getCallsiteSamples() const {
     351          43 :     return CallsiteSamples;
     352             :   }
     353             : 
     354             :   /// Merge the samples in \p Other into this one.
     355             :   /// Optionally scale samples by \p Weight.
     356          88 :   sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
     357             :     sampleprof_error Result = sampleprof_error::success;
     358          88 :     Name = Other.getName();
     359          88 :     MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight));
     360          88 :     MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight));
     361         339 :     for (const auto &I : Other.getBodySamples()) {
     362         251 :       const LineLocation &Loc = I.first;
     363         251 :       const SampleRecord &Rec = I.second;
     364         251 :       MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
     365             :     }
     366         132 :     for (const auto &I : Other.getCallsiteSamples()) {
     367          44 :       const LineLocation &Loc = I.first;
     368             :       FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
     369          92 :       for (const auto &Rec : I.second)
     370          48 :         MergeResult(Result, FSMap[Rec.first].merge(Rec.second, Weight));
     371             :     }
     372          88 :     return Result;
     373             :   }
     374             : 
     375             :   /// Recursively traverses all children, if the total sample count of the
     376             :   /// corresponding function is no less than \p Threshold, add its corresponding
     377             :   /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
     378             :   /// to \p S.
     379           7 :   void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
     380             :                             uint64_t Threshold, bool isCompact) const {
     381           7 :     if (TotalSamples <= Threshold)
     382             :       return;
     383          14 :     S.insert(Function::getGUID(Name));
     384             :     // Import hot CallTargets, which may not be available in IR because full
     385             :     // profile annotation cannot be done until backend compilation in ThinLTO.
     386           9 :     for (const auto &BS : BodySamples)
     387           5 :       for (const auto &TS : BS.second.getCallTargets())
     388           1 :         if (TS.getValue() > Threshold) {
     389           1 :           Function *Callee = M->getFunction(TS.getKey());
     390           1 :           if (!Callee || !Callee->getSubprogram())
     391           4 :             S.insert(isCompact ? std::stol(TS.getKey().data())
     392             :                                : Function::getGUID(TS.getKey()));
     393             :         }
     394          10 :     for (const auto &CS : CallsiteSamples)
     395           6 :       for (const auto &NameFS : CS.second)
     396           3 :         NameFS.second.findInlinedFunctions(S, M, Threshold, isCompact);
     397             :   }
     398             : 
     399             :   /// Set the name of the function.
     400         308 :   void setName(StringRef FunctionName) { Name = FunctionName; }
     401             : 
     402             :   /// Return the function name.
     403         109 :   const StringRef &getName() const { return Name; }
     404             : 
     405             :   /// Returns the line offset to the start line of the subprogram.
     406             :   /// We assume that a single function will not exceed 65535 LOC.
     407             :   static unsigned getOffset(const DILocation *DIL);
     408             : 
     409             :   /// Get the FunctionSamples of the inline instance where DIL originates
     410             :   /// from.
     411             :   ///
     412             :   /// The FunctionSamples of the instruction (Machine or IR) associated to
     413             :   /// \p DIL is the inlined instance in which that instruction is coming from.
     414             :   /// We traverse the inline stack of that instruction, and match it with the
     415             :   /// tree nodes in the profile.
     416             :   ///
     417             :   /// \returns the FunctionSamples pointer to the inlined instance.
     418             :   const FunctionSamples *findFunctionSamples(const DILocation *DIL) const;
     419             : 
     420             : private:
     421             :   /// Mangled name of the function.
     422             :   StringRef Name;
     423             : 
     424             :   /// Total number of samples collected inside this function.
     425             :   ///
     426             :   /// Samples are cumulative, they include all the samples collected
     427             :   /// inside this function and all its inlined callees.
     428             :   uint64_t TotalSamples = 0;
     429             : 
     430             :   /// Total number of samples collected at the head of the function.
     431             :   /// This is an approximation of the number of calls made to this function
     432             :   /// at runtime.
     433             :   uint64_t TotalHeadSamples = 0;
     434             : 
     435             :   /// Map instruction locations to collected samples.
     436             :   ///
     437             :   /// Each entry in this map contains the number of samples
     438             :   /// collected at the corresponding line offset. All line locations
     439             :   /// are an offset from the start of the function.
     440             :   BodySampleMap BodySamples;
     441             : 
     442             :   /// Map call sites to collected samples for the called function.
     443             :   ///
     444             :   /// Each entry in this map corresponds to all the samples
     445             :   /// collected for the inlined function call at the given
     446             :   /// location. For example, given:
     447             :   ///
     448             :   ///     void foo() {
     449             :   ///  1    bar();
     450             :   ///  ...
     451             :   ///  8    baz();
     452             :   ///     }
     453             :   ///
     454             :   /// If the bar() and baz() calls were inlined inside foo(), this
     455             :   /// map will contain two entries.  One for all the samples collected
     456             :   /// in the call to bar() at line offset 1, the other for all the samples
     457             :   /// collected in the call to baz() at line offset 8.
     458             :   CallsiteSampleMap CallsiteSamples;
     459             : };
     460             : 
     461             : raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
     462             : 
     463             : /// Sort a LocationT->SampleT map by LocationT.
     464             : ///
     465             : /// It produces a sorted list of <LocationT, SampleT> records by ascending
     466             : /// order of LocationT.
     467          43 : template <class LocationT, class SampleT> class SampleSorter {
     468             : public:
     469             :   using SamplesWithLoc = std::pair<const LocationT, SampleT>;
     470             :   using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>;
     471             : 
     472         153 :   SampleSorter(const std::map<LocationT, SampleT> &Samples) {
     473         486 :     for (const auto &I : Samples)
     474         333 :       V.push_back(&I);
     475             :     std::stable_sort(V.begin(), V.end(),
     476             :                      [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
     477             :                        return A->first < B->first;
     478             :                      });
     479         153 :   }
     480             : 
     481             :   const SamplesWithLocList &get() const { return V; }
     482             : 
     483             : private:
     484             :   SamplesWithLocList V;
     485             : };
     486             : 
     487             : } // end namespace sampleprof
     488             : } // end namespace llvm
     489             : 
     490             : #endif // LLVM_PROFILEDATA_SAMPLEPROF_H

Generated by: LCOV version 1.13