llvm/tools/llvm-profgen/ProfileGenerator.h

   1 //===-- ProfileGenerator.h - Profile Generator -----------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_TOOLS_LLVM_PROGEN_PROFILEGENERATOR_H
  10 #define LLVM_TOOLS_LLVM_PROGEN_PROFILEGENERATOR_H
  11 #include "CSPreInliner.h"
  12 #include "ErrorHandling.h"
  13 #include "PerfReader.h"
  14 #include "ProfiledBinary.h"
  15 #include "llvm/ProfileData/SampleProfWriter.h"
  16 #include <memory>
  17 #include <unordered_set>
  18
  19 using namespace llvm;
  20 using namespace sampleprof;
  21
  22 namespace llvm {
  23 namespace sampleprof {
  24
  25 // This base class for profile generation of sample-based PGO. We reuse all
  26 // structures relating to function profiles and profile writers as seen in
  27 // /ProfileData/SampleProf.h.
  28 class ProfileGeneratorBase {
  29
  30 public:
  31   ProfileGeneratorBase(ProfiledBinary *Binary,
  32                        const ContextSampleCounterMap &Counters)
  33       : Binary(Binary), SampleCounters(Counters){};
  34   virtual ~ProfileGeneratorBase() = default;
  35   static std::unique_ptr<ProfileGeneratorBase>
  36   create(ProfiledBinary *Binary, const ContextSampleCounterMap &SampleCounters,
  37          bool ProfileIsCSFlat);
  38   virtual void generateProfile() = 0;
  39   void write();
  40
  41   static uint32_t
  42   getDuplicationFactor(unsigned Discriminator,
  43                        bool UseFSD = ProfileGeneratorBase::UseFSDiscriminator) {
  44     return UseFSD ? 1
  45                   : llvm::DILocation::getDuplicationFactorFromDiscriminator(
  46                         Discriminator);
  47   }
  48
  49   static uint32_t
  50   getBaseDiscriminator(unsigned Discriminator,
  51                        bool UseFSD = ProfileGeneratorBase::UseFSDiscriminator) {
  52     return UseFSD ? Discriminator
  53                   : DILocation::getBaseDiscriminatorFromDiscriminator(
  54                         Discriminator, /* IsFSDiscriminator */ false);
  55   }
  56
  57   static bool UseFSDiscriminator;
  58
  59 protected:
  60   // Use SampleProfileWriter to serialize profile map
  61   void write(std::unique_ptr<SampleProfileWriter> Writer,
  62              SampleProfileMap &ProfileMap);
  63   /*
  64   For each region boundary point, mark if it is begin or end (or both) of
  65   the region. Boundary points are inclusive. Log the sample count as well
  66   so we can use it when we compute the sample count of each disjoint region
  67   later. Note that there might be multiple ranges with different sample
  68   count that share same begin/end point. We need to accumulate the sample
  69   count for the boundary point for such case, because for the example
  70   below,
  71
  72   |<--100-->|
  73   |<------200------>|
  74   A         B       C
  75
  76   sample count for disjoint region [A,B] would be 300.
  77   */
  78   void findDisjointRanges(RangeSample &DisjointRanges,
  79                           const RangeSample &Ranges);
  80   // Helper function for updating body sample for a leaf location in
  81   // FunctionProfile
  82   void updateBodySamplesforFunctionProfile(FunctionSamples &FunctionProfile,
  83                                            const SampleContextFrame &LeafLoc,
  84                                            uint64_t Count);
  85   void updateTotalSamples();
  86
  87   StringRef getCalleeNameForOffset(uint64_t TargetOffset);
  88
  89   void computeSummaryAndThreshold();
  90
  91   void calculateAndShowDensity(const SampleProfileMap &Profiles);
  92
  93   double calculateDensity(const SampleProfileMap &Profiles,
  94                           uint64_t HotCntThreshold);
  95
  96   void showDensitySuggestion(double Density);
  97
  98   // Thresholds from profile summary to answer isHotCount/isColdCount queries.
  99   uint64_t HotCountThreshold;
 100
 101   uint64_t ColdCountThreshold;
 102
 103   // Used by SampleProfileWriter
 104   SampleProfileMap ProfileMap;
 105
 106   ProfiledBinary *Binary = nullptr;
 107
 108   const ContextSampleCounterMap &SampleCounters;
 109 };
 110
 111 class ProfileGenerator : public ProfileGeneratorBase {
 112
 113 public:
 114   ProfileGenerator(ProfiledBinary *Binary,
 115                    const ContextSampleCounterMap &Counters)
 116       : ProfileGeneratorBase(Binary, Counters){};
 117   void generateProfile() override;
 118
 119 private:
 120   void generateLineNumBasedProfile();
 121   RangeSample preprocessRangeCounter(const RangeSample &RangeCounter);
 122   FunctionSamples &getTopLevelFunctionProfile(StringRef FuncName);
 123   // Helper function to get the leaf frame's FunctionProfile by traversing the
 124   // inline stack and meanwhile it adds the total samples for each frame's
 125   // function profile.
 126   FunctionSamples &
 127   getLeafProfileAndAddTotalSamples(const SampleContextFrameVector &FrameVec,
 128                                    uint64_t Count);
 129   void populateBodySamplesForAllFunctions(const RangeSample &RangeCounter);
 130   void
 131   populateBoundarySamplesForAllFunctions(const BranchSample &BranchCounters);
 132   void postProcessProfiles();
 133   void trimColdProfiles(const SampleProfileMap &Profiles,
 134                         uint64_t ColdCntThreshold);
 135 };
 136
 137 using ProbeCounterMap =
 138     std::unordered_map<const MCDecodedPseudoProbe *, uint64_t>;
 139
 140 class CSProfileGenerator : public ProfileGeneratorBase {
 141 public:
 142   CSProfileGenerator(ProfiledBinary *Binary,
 143                      const ContextSampleCounterMap &Counters)
 144       : ProfileGeneratorBase(Binary, Counters){};
 145
 146   void generateProfile() override;
 147
 148   // Trim the context stack at a given depth.
 149   template <typename T>
 150   static void trimContext(SmallVectorImpl<T> &S, int Depth = MaxContextDepth) {
 151     if (Depth < 0 || static_cast<size_t>(Depth) >= S.size())
 152       return;
 153     std::copy(S.begin() + S.size() - static_cast<size_t>(Depth), S.end(),
 154               S.begin());
 155     S.resize(Depth);
 156   }
 157
 158   // Remove adjacent repeated context sequences up to a given sequence length,
 159   // -1 means no size limit. Note that repeated sequences are identified based
 160   // on the exact call site, this is finer granularity than function recursion.
 161   template <typename T>
 162   static void compressRecursionContext(SmallVectorImpl<T> &Context,
 163                                        int32_t CSize = MaxCompressionSize) {
 164     uint32_t I = 1;
 165     uint32_t HS = static_cast<uint32_t>(Context.size() / 2);
 166     uint32_t MaxDedupSize =
 167         CSize == -1 ? HS : std::min(static_cast<uint32_t>(CSize), HS);
 168     auto BeginIter = Context.begin();
 169     // Use an in-place algorithm to save memory copy
 170     // End indicates the end location of current iteration's data
 171     uint32_t End = 0;
 172     // Deduplicate from length 1 to the max possible size of a repeated
 173     // sequence.
 174     while (I <= MaxDedupSize) {
 175       // This is a linear algorithm that deduplicates adjacent repeated
 176       // sequences of size I. The deduplication detection runs on a sliding
 177       // window whose size is 2*I and it keeps sliding the window to deduplicate
 178       // the data inside. Once duplication is detected, deduplicate it by
 179       // skipping the right half part of the window, otherwise just copy back
 180       // the new one by appending them at the back of End pointer(for the next
 181       // iteration).
 182       //
 183       // For example:
 184       // Input: [a1, a2, b1, b2]
 185       // (Added index to distinguish the same char, the origin is [a, a, b,
 186       // b], the size of the dedup window is 2(I = 1) at the beginning)
 187       //
 188       // 1) The initial status is a dummy window[null, a1], then just copy the
 189       // right half of the window(End = 0), then slide the window.
 190       // Result: [a1], a2, b1, b2 (End points to the element right before ],
 191       // after ] is the data of the previous iteration)
 192       //
 193       // 2) Next window is [a1, a2]. Since a1 == a2, then skip the right half of
 194       // the window i.e the duplication happen. Only slide the window.
 195       // Result: [a1], a2, b1, b2
 196       //
 197       // 3) Next window is [a2, b1], copy the right half of the window(b1 is
 198       // new) to the End and slide the window.
 199       // Result: [a1, b1], b1, b2
 200       //
 201       // 4) Next window is [b1, b2], same to 2), skip b2.
 202       // Result: [a1, b1], b1, b2
 203       // After resize, it will be [a, b]
 204
 205       // Use pointers like below to do comparison inside the window
 206       //    [a         b         c        a       b        c]
 207       //     |         |         |                |        |
 208       // LeftBoundary Left     Right           Left+I    Right+I
 209       // A duplication found if Left < LeftBoundry.
 210
 211       int32_t Right = I - 1;
 212       End = I;
 213       int32_t LeftBoundary = 0;
 214       while (Right + I < Context.size()) {
 215         // To avoids scanning a part of a sequence repeatedly, it finds out
 216         // the common suffix of two hald in the window. The common suffix will
 217         // serve as the common prefix of next possible pair of duplicate
 218         // sequences. The non-common part will be ignored and never scanned
 219         // again.
 220
 221         // For example.
 222         // Input: [a, b1], c1, b2, c2
 223         // I = 2
 224         //
 225         // 1) For the window [a, b1, c1, b2], non-common-suffix for the right
 226         // part is 'c1', copy it and only slide the window 1 step.
 227         // Result: [a, b1, c1], b2, c2
 228         //
 229         // 2) Next window is [b1, c1, b2, c2], so duplication happen.
 230         // Result after resize: [a, b, c]
 231
 232         int32_t Left = Right;
 233         while (Left >= LeftBoundary && Context[Left] == Context[Left + I]) {
 234           // Find the longest suffix inside the window. When stops, Left points
 235           // at the diverging point in the current sequence.
 236           Left--;
 237         }
 238
 239         bool DuplicationFound = (Left < LeftBoundary);
 240         // Don't need to recheck the data before Right
 241         LeftBoundary = Right + 1;
 242         if (DuplicationFound) {
 243           // Duplication found, skip right half of the window.
 244           Right += I;
 245         } else {
 246           // Copy the non-common-suffix part of the adjacent sequence.
 247           std::copy(BeginIter + Right + 1, BeginIter + Left + I + 1,
 248                     BeginIter + End);
 249           End += Left + I - Right;
 250           // Only slide the window by the size of non-common-suffix
 251           Right = Left + I;
 252         }
 253       }
 254       // Don't forget the remaining part that's not scanned.
 255       std::copy(BeginIter + Right + 1, Context.end(), BeginIter + End);
 256       End += Context.size() - Right - 1;
 257       I++;
 258       Context.resize(End);
 259       MaxDedupSize = std::min(static_cast<uint32_t>(End / 2), MaxDedupSize);
 260     }
 261   }
 262
 263 private:
 264   void generateLineNumBasedProfile();
 265   // Lookup or create FunctionSamples for the context
 266   FunctionSamples &
 267   getFunctionProfileForContext(const SampleContextFrameVector &Context,
 268                                bool WasLeafInlined = false);
 269   // For profiled only functions, on-demand compute their inline context
 270   // function byte size which is used by the pre-inliner.
 271   void computeSizeForProfiledFunctions();
 272   // Post processing for profiles before writing out, such as mermining
 273   // and trimming cold profiles, running preinliner on profiles.
 274   void postProcessProfiles();
 275
 276   void populateBodySamplesForFunction(FunctionSamples &FunctionProfile,
 277                                       const RangeSample &RangeCounters);
 278   void populateBoundarySamplesForFunction(SampleContextFrames ContextId,
 279                                           FunctionSamples &FunctionProfile,
 280                                           const BranchSample &BranchCounters);
 281   void populateInferredFunctionSamples();
 282
 283   void generateProbeBasedProfile();
 284   // Go through each address from range to extract the top frame probe by
 285   // looking up in the Address2ProbeMap
 286   void extractProbesFromRange(const RangeSample &RangeCounter,
 287                               ProbeCounterMap &ProbeCounter);
 288   // Fill in function body samples from probes
 289   void populateBodySamplesWithProbes(const RangeSample &RangeCounter,
 290                                      SampleContextFrames ContextStack);
 291   // Fill in boundary samples for a call probe
 292   void populateBoundarySamplesWithProbes(const BranchSample &BranchCounter,
 293                                          SampleContextFrames ContextStack);
 294   // Helper function to get FunctionSamples for the leaf probe
 295   FunctionSamples &
 296   getFunctionProfileForLeafProbe(SampleContextFrames ContextStack,
 297                                  const MCDecodedPseudoProbe *LeafProbe);
 298
 299   // Underlying context table serves for sample profile writer.
 300   std::unordered_set<SampleContextFrameVector, SampleContextFrameHash> Contexts;
 301
 302 public:
 303   // Deduplicate adjacent repeated context sequences up to a given sequence
 304   // length. -1 means no size limit.
 305   static int32_t MaxCompressionSize;
 306   static int MaxContextDepth;
 307 };
 308
 309 } // end namespace sampleprof
 310 } // end namespace llvm
 311
 312 #endif