LCOV - code coverage report
Current view: top level - include/llvm/ProfileData - SampleProf.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 98 98 100.0 %
Date: 2017-09-14 15:23:50 Functions: 14 14 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        2523 :   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        1224 :   if (Accumulator == sampleprof_error::success &&
      64             :       Result != sampleprof_error::success)
      65           5 :     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             : static inline uint64_t SPMagic() {
      82             :   return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
      83             :          uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
      84             :          uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
      85             :          uint64_t('2') << (64 - 56) | uint64_t(0xff);
      86             : }
      87             : 
      88             : static inline uint64_t SPVersion() { return 103; }
      89             : 
      90             : /// Represents the relative location of an instruction.
      91             : ///
      92             : /// Instruction locations are specified by the line offset from the
      93             : /// beginning of the function (marked by the line where the function
      94             : /// header is) and the discriminator value within that line.
      95             : ///
      96             : /// The discriminator value is useful to distinguish instructions
      97             : /// that are on the same line but belong to different basic blocks
      98             : /// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
      99             : struct LineLocation {
     100        2360 :   LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
     101             : 
     102             :   void print(raw_ostream &OS) const;
     103             :   void dump() const;
     104             : 
     105             :   bool operator<(const LineLocation &O) const {
     106        8521 :     return LineOffset < O.LineOffset ||
     107        3825 :            (LineOffset == O.LineOffset && Discriminator < O.Discriminator);
     108             :   }
     109             : 
     110             :   uint32_t LineOffset;
     111             :   uint32_t Discriminator;
     112             : };
     113             : 
     114             : raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc);
     115             : 
     116             : /// Representation of a single sample record.
     117             : ///
     118             : /// A sample record is represented by a positive integer value, which
     119             : /// indicates how frequently was the associated line location executed.
     120             : ///
     121             : /// Additionally, if the associated location contains a function call,
     122             : /// the record will hold a list of all the possible called targets. For
     123             : /// direct calls, this will be the exact function being invoked. For
     124             : /// indirect calls (function pointers, virtual table dispatch), this
     125             : /// will be a list of one or more functions.
     126         879 : class SampleRecord {
     127             : public:
     128             :   using CallTargetMap = StringMap<uint64_t>;
     129             : 
     130        1762 :   SampleRecord() = default;
     131             : 
     132             :   /// Increment the number of samples for this record by \p S.
     133             :   /// Optionally scale sample count \p S by \p Weight.
     134             :   ///
     135             :   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
     136             :   /// around unsigned integers.
     137             :   sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
     138             :     bool Overflowed;
     139         942 :     NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
     140         942 :     return Overflowed ? sampleprof_error::counter_overflow
     141             :                       : sampleprof_error::success;
     142             :   }
     143             : 
     144             :   /// Add called function \p F with samples \p S.
     145             :   /// Optionally scale sample count \p S by \p Weight.
     146             :   ///
     147             :   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
     148             :   /// around unsigned integers.
     149          84 :   sampleprof_error addCalledTarget(StringRef F, uint64_t S,
     150             :                                    uint64_t Weight = 1) {
     151         168 :     uint64_t &TargetSamples = CallTargets[F];
     152             :     bool Overflowed;
     153          84 :     TargetSamples =
     154          84 :         SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
     155          84 :     return Overflowed ? sampleprof_error::counter_overflow
     156          84 :                       : sampleprof_error::success;
     157             :   }
     158             : 
     159             :   /// Return true if this sample record contains function calls.
     160         132 :   bool hasCalls() const { return !CallTargets.empty(); }
     161             : 
     162             :   uint64_t getSamples() const { return NumSamples; }
     163          16 :   const CallTargetMap &getCallTargets() const { return CallTargets; }
     164             : 
     165             :   /// Merge the samples in \p Other into this record.
     166             :   /// Optionally scale sample counts by \p Weight.
     167         250 :   sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) {
     168         500 :     sampleprof_error Result = addSamples(Other.getSamples(), Weight);
     169        1042 :     for (const auto &I : Other.getCallTargets()) {
     170          63 :       MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
     171             :     }
     172         250 :     return Result;
     173             :   }
     174             : 
     175             :   void print(raw_ostream &OS, unsigned Indent) const;
     176             :   void dump() const;
     177             : 
     178             : private:
     179             :   uint64_t NumSamples = 0;
     180             :   CallTargetMap CallTargets;
     181             : };
     182             : 
     183             : raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
     184             : 
     185             : class FunctionSamples;
     186             : 
     187             : using BodySampleMap = std::map<LineLocation, SampleRecord>;
     188             : using FunctionSamplesMap = StringMap<FunctionSamples>;
     189             : using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
     190             : 
     191             : /// Representation of the samples collected for a function.
     192             : ///
     193             : /// This data structure contains all the collected samples for the body
     194             : /// of a function. Each sample corresponds to a LineLocation instance
     195             : /// within the body of the function.
     196        1980 : class FunctionSamples {
     197             : public:
     198        1853 :   FunctionSamples() = default;
     199             : 
     200             :   void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
     201             :   void dump() const;
     202             : 
     203             :   sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
     204             :     bool Overflowed;
     205         527 :     TotalSamples =
     206         527 :         SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
     207         286 :     return Overflowed ? sampleprof_error::counter_overflow
     208             :                       : sampleprof_error::success;
     209             :   }
     210             : 
     211             :   sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
     212             :     bool Overflowed;
     213         260 :     TotalHeadSamples =
     214         260 :         SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
     215         219 :     return Overflowed ? sampleprof_error::counter_overflow
     216             :                       : sampleprof_error::success;
     217             :   }
     218             : 
     219         692 :   sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
     220             :                                   uint64_t Num, uint64_t Weight = 1) {
     221        1384 :     return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
     222        2076 :         Num, Weight);
     223             :   }
     224             : 
     225          63 :   sampleprof_error addCalledTargetSamples(uint32_t LineOffset,
     226             :                                           uint32_t Discriminator,
     227             :                                           const std::string &FName,
     228             :                                           uint64_t Num, uint64_t Weight = 1) {
     229         189 :     return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
     230         126 :         FName, Num, Weight);
     231             :   }
     232             : 
     233             :   /// Return the number of samples collected at the given location.
     234             :   /// Each location is specified by \p LineOffset and \p Discriminator.
     235             :   /// If the location is not found in profile, return error.
     236         710 :   ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
     237             :                                   uint32_t Discriminator) const {
     238        2130 :     const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
     239        1420 :     if (ret == BodySamples.end())
     240         268 :       return std::error_code();
     241             :     else
     242        1152 :       return ret->second.getSamples();
     243             :   }
     244             : 
     245             :   /// Returns the call target map collected at a given location.
     246             :   /// Each location is specified by \p LineOffset and \p Discriminator.
     247             :   /// If the location is not found in profile, return error.
     248             :   ErrorOr<SampleRecord::CallTargetMap>
     249          20 :   findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
     250          60 :     const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
     251          40 :     if (ret == BodySamples.end())
     252           8 :       return std::error_code();
     253          32 :     return ret->second.getCallTargets();
     254             :   }
     255             : 
     256             :   /// Return the function samples at the given callsite location.
     257             :   FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
     258         153 :     return CallsiteSamples[Loc];
     259             :   }
     260             : 
     261             :   /// Returns the FunctionSamplesMap at the given \p Loc.
     262             :   const FunctionSamplesMap *
     263             :   findFunctionSamplesMapAt(const LineLocation &Loc) const {
     264          10 :     auto iter = CallsiteSamples.find(Loc);
     265          10 :     if (iter == CallsiteSamples.end())
     266             :       return nullptr;
     267           5 :     return &iter->second;
     268             :   }
     269             : 
     270             :   /// Returns a pointer to FunctionSamples at the given callsite location \p Loc
     271             :   /// with callee \p CalleeName. If no callsite can be found, relax the
     272             :   /// restriction to return the FunctionSamples at callsite location \p Loc
     273             :   /// with the maximum total sample count.
     274         300 :   const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
     275             :                                                StringRef CalleeName) const {
     276         600 :     auto iter = CallsiteSamples.find(Loc);
     277         600 :     if (iter == CallsiteSamples.end())
     278             :       return nullptr;
     279         162 :     auto FS = iter->second.find(CalleeName);
     280         486 :     if (FS != iter->second.end())
     281         250 :       return &FS->getValue();
     282             :     // If we cannot find exact match of the callee name, return the FS with
     283             :     // the max total count.
     284          37 :     uint64_t MaxTotalSamples = 0;
     285          37 :     const FunctionSamples *R = nullptr;
     286         160 :     for (const auto &NameFS : iter->second)
     287          43 :       if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
     288          43 :         MaxTotalSamples = NameFS.second.getTotalSamples();
     289          43 :         R = &NameFS.second;
     290             :       }
     291             :     return R;
     292             :   }
     293             : 
     294             :   bool empty() const { return TotalSamples == 0; }
     295             : 
     296             :   /// Return the total number of samples collected inside the function.
     297             :   uint64_t getTotalSamples() const { return TotalSamples; }
     298             : 
     299             :   /// Return the total number of samples collected at the head of the
     300             :   /// function.
     301             :   uint64_t getHeadSamples() const { return TotalHeadSamples; }
     302             : 
     303             :   /// Return all the samples collected in the body of the function.
     304          43 :   const BodySampleMap &getBodySamples() const { return BodySamples; }
     305             : 
     306             :   /// Return all the callsite samples collected in the body of the function.
     307             :   const CallsiteSampleMap &getCallsiteSamples() const {
     308          43 :     return CallsiteSamples;
     309             :   }
     310             : 
     311             :   /// Merge the samples in \p Other into this one.
     312             :   /// Optionally scale samples by \p Weight.
     313          89 :   sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
     314          89 :     sampleprof_error Result = sampleprof_error::success;
     315          89 :     Name = Other.getName();
     316         178 :     MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight));
     317         267 :     MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight));
     318         517 :     for (const auto &I : Other.getBodySamples()) {
     319         250 :       const LineLocation &Loc = I.first;
     320         250 :       const SampleRecord &Rec = I.second;
     321         500 :       MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
     322             :     }
     323         312 :     for (const auto &I : Other.getCallsiteSamples()) {
     324          45 :       const LineLocation &Loc = I.first;
     325          45 :       FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
     326         233 :       for (const auto &Rec : I.second)
     327         147 :         MergeResult(Result, FSMap[Rec.first()].merge(Rec.second, Weight));
     328             :     }
     329          89 :     return Result;
     330             :   }
     331             : 
     332             :   /// Recursively traverses all children, if the corresponding function is
     333             :   /// not defined in module \p M, and its total sample is no less than
     334             :   /// \p Threshold, add its corresponding GUID to \p S.
     335          11 :   void findImportedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
     336             :                              uint64_t Threshold) const {
     337          11 :     if (TotalSamples <= Threshold)
     338             :       return;
     339          10 :     Function *F = M->getFunction(Name);
     340          10 :     if (!F || !F->getSubprogram())
     341          18 :       S.insert(Function::getGUID(Name));
     342          36 :     for (auto CS : CallsiteSamples)
     343          12 :       for (const auto &NameFS : CS.second)
     344           2 :         NameFS.second.findImportedFunctions(S, M, Threshold);
     345             :   }
     346             : 
     347             :   /// Set the name of the function.
     348         277 :   void setName(StringRef FunctionName) { Name = FunctionName; }
     349             : 
     350             :   /// Return the function name.
     351         109 :   const StringRef &getName() const { return Name; }
     352             : 
     353             : private:
     354             :   /// Mangled name of the function.
     355             :   StringRef Name;
     356             : 
     357             :   /// Total number of samples collected inside this function.
     358             :   ///
     359             :   /// Samples are cumulative, they include all the samples collected
     360             :   /// inside this function and all its inlined callees.
     361             :   uint64_t TotalSamples = 0;
     362             : 
     363             :   /// Total number of samples collected at the head of the function.
     364             :   /// This is an approximation of the number of calls made to this function
     365             :   /// at runtime.
     366             :   uint64_t TotalHeadSamples = 0;
     367             : 
     368             :   /// Map instruction locations to collected samples.
     369             :   ///
     370             :   /// Each entry in this map contains the number of samples
     371             :   /// collected at the corresponding line offset. All line locations
     372             :   /// are an offset from the start of the function.
     373             :   BodySampleMap BodySamples;
     374             : 
     375             :   /// Map call sites to collected samples for the called function.
     376             :   ///
     377             :   /// Each entry in this map corresponds to all the samples
     378             :   /// collected for the inlined function call at the given
     379             :   /// location. For example, given:
     380             :   ///
     381             :   ///     void foo() {
     382             :   ///  1    bar();
     383             :   ///  ...
     384             :   ///  8    baz();
     385             :   ///     }
     386             :   ///
     387             :   /// If the bar() and baz() calls were inlined inside foo(), this
     388             :   /// map will contain two entries.  One for all the samples collected
     389             :   /// in the call to bar() at line offset 1, the other for all the samples
     390             :   /// collected in the call to baz() at line offset 8.
     391             :   CallsiteSampleMap CallsiteSamples;
     392             : };
     393             : 
     394             : raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
     395             : 
     396             : /// Sort a LocationT->SampleT map by LocationT.
     397             : ///
     398             : /// It produces a sorted list of <LocationT, SampleT> records by ascending
     399             : /// order of LocationT.
     400         306 : template <class LocationT, class SampleT> class SampleSorter {
     401             : public:
     402             :   using SamplesWithLoc = std::pair<const LocationT, SampleT>;
     403             :   using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>;
     404             : 
     405         306 :   SampleSorter(const std::map<LocationT, SampleT> &Samples) {
     406         792 :     for (const auto &I : Samples)
     407         333 :       V.push_back(&I);
     408         612 :     std::stable_sort(V.begin(), V.end(),
     409             :                      [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
     410         380 :                        return A->first < B->first;
     411         380 :                      });
     412         153 :   }
     413             : 
     414             :   const SamplesWithLocList &get() const { return V; }
     415             : 
     416             : private:
     417             :   SamplesWithLocList V;
     418             : };
     419             : 
     420             : } // end namespace sampleprof
     421             : } // end namespace llvm
     422             : 
     423             : #endif // LLVM_PROFILEDATA_SAMPLEPROF_H

Generated by: LCOV version 1.13