llvm/include/llvm/Analysis/ProfileSummaryInfo.h

   1 //===- llvm/Analysis/ProfileSummaryInfo.h - profile summary ---*- 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 // This file contains a pass that provides access to profile summary
  10 // information.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ANALYSIS_PROFILESUMMARYINFO_H
  15 #define LLVM_ANALYSIS_PROFILESUMMARYINFO_H
  16
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/IR/Function.h"
  19 #include "llvm/IR/Instructions.h"
  20 #include "llvm/IR/PassManager.h"
  21 #include "llvm/IR/ProfileSummary.h"
  22 #include "llvm/Pass.h"
  23 #include "llvm/Support/BlockFrequency.h"
  24 #include <memory>
  25 #include <optional>
  26
  27 namespace llvm {
  28 class BlockFrequencyInfo;
  29 class MachineFunction;
  30
  31 /// Analysis providing profile information.
  32 ///
  33 /// This is an immutable analysis pass that provides ability to query global
  34 /// (program-level) profile information. The main APIs are isHotCount and
  35 /// isColdCount that tells whether a given profile count is considered hot/cold
  36 /// based on the profile summary. This also provides convenience methods to
  37 /// check whether a function is hot or cold.
  38
  39 // FIXME: Provide convenience methods to determine hotness/coldness of other IR
  40 // units. This would require making this depend on BFI.
  41 class ProfileSummaryInfo {
  42 private:
  43   const Module *M;
  44   std::unique_ptr<ProfileSummary> Summary;
  45   void computeThresholds();
  46   // Count thresholds to answer isHotCount and isColdCount queries.
  47   std::optional<uint64_t> HotCountThreshold, ColdCountThreshold;
  48   // True if the working set size of the code is considered huge,
  49   // because the number of profile counts required to reach the hot
  50   // percentile is above a huge threshold.
  51   std::optional<bool> HasHugeWorkingSetSize;
  52   // True if the working set size of the code is considered large,
  53   // because the number of profile counts required to reach the hot
  54   // percentile is above a large threshold.
  55   std::optional<bool> HasLargeWorkingSetSize;
  56   // Compute the threshold for a given cutoff.
  57   std::optional<uint64_t> computeThreshold(int PercentileCutoff) const;
  58   // The map that caches the threshold values. The keys are the percentile
  59   // cutoff values and the values are the corresponding threshold values.
  60   mutable DenseMap<int, uint64_t> ThresholdCache;
  61
  62 public:
  63   ProfileSummaryInfo(const Module &M) : M(&M) { refresh(); }
  64   ProfileSummaryInfo(ProfileSummaryInfo &&Arg) = default;
  65
  66   /// If no summary is present, attempt to refresh.
  67   void refresh();
  68
  69   /// Returns true if profile summary is available.
  70   bool hasProfileSummary() const { return Summary != nullptr; }
  71
  72   /// Returns true if module \c M has sample profile.
  73   bool hasSampleProfile() const {
  74     return hasProfileSummary() &&
  75            Summary->getKind() == ProfileSummary::PSK_Sample;
  76   }
  77
  78   /// Returns true if module \c M has instrumentation profile.
  79   bool hasInstrumentationProfile() const {
  80     return hasProfileSummary() &&
  81            Summary->getKind() == ProfileSummary::PSK_Instr;
  82   }
  83
  84   /// Returns true if module \c M has context sensitive instrumentation profile.
  85   bool hasCSInstrumentationProfile() const {
  86     return hasProfileSummary() &&
  87            Summary->getKind() == ProfileSummary::PSK_CSInstr;
  88   }
  89
  90   /// Handle the invalidation of this information.
  91   ///
  92   /// When used as a result of \c ProfileSummaryAnalysis this method will be
  93   /// called when the module this was computed for changes. Since profile
  94   /// summary is immutable after it is annotated on the module, we return false
  95   /// here.
  96   bool invalidate(Module &, const PreservedAnalyses &,
  97                   ModuleAnalysisManager::Invalidator &) {
  98     return false;
  99   }
 100
 101   /// Returns the profile count for \p CallInst.
 102   std::optional<uint64_t> getProfileCount(const CallBase &CallInst,
 103                                           BlockFrequencyInfo *BFI,
 104                                           bool AllowSynthetic = false) const;
 105   /// Returns true if module \c M has partial-profile sample profile.
 106   bool hasPartialSampleProfile() const;
 107   /// Returns true if the working set size of the code is considered huge.
 108   bool hasHugeWorkingSetSize() const;
 109   /// Returns true if the working set size of the code is considered large.
 110   bool hasLargeWorkingSetSize() const;
 111   /// Returns true if \p F has hot function entry. If it returns false, it
 112   /// either means it is not hot or it is unknown whether it is hot or not (for
 113   /// example, no profile data is available).
 114   template <typename FuncT> bool isFunctionEntryHot(const FuncT *F) const {
 115     if (!F || !hasProfileSummary())
 116       return false;
 117     std::optional<Function::ProfileCount> FunctionCount = getEntryCount(F);
 118     // FIXME: The heuristic used below for determining hotness is based on
 119     // preliminary SPEC tuning for inliner. This will eventually be a
 120     // convenience method that calls isHotCount.
 121     return FunctionCount && isHotCount(FunctionCount->getCount());
 122   }
 123
 124   /// Returns true if \p F contains hot code.
 125   template <typename FuncT, typename BFIT>
 126   bool isFunctionHotInCallGraph(const FuncT *F, BFIT &BFI) const {
 127     if (!F || !hasProfileSummary())
 128       return false;
 129     if (auto FunctionCount = getEntryCount(F))
 130       if (isHotCount(FunctionCount->getCount()))
 131         return true;
 132
 133     if (auto TotalCallCount = getTotalCallCount(F))
 134       if (isHotCount(*TotalCallCount))
 135         return true;
 136
 137     for (const auto &BB : *F)
 138       if (isHotBlock(&BB, &BFI))
 139         return true;
 140     return false;
 141   }
 142   /// Returns true if \p F has cold function entry.
 143   bool isFunctionEntryCold(const Function *F) const;
 144   /// Returns true if \p F contains only cold code.
 145   template <typename FuncT, typename BFIT>
 146   bool isFunctionColdInCallGraph(const FuncT *F, BFIT &BFI) const {
 147     if (!F || !hasProfileSummary())
 148       return false;
 149     if (auto FunctionCount = getEntryCount(F))
 150       if (!isColdCount(FunctionCount->getCount()))
 151         return false;
 152
 153     if (auto TotalCallCount = getTotalCallCount(F))
 154       if (!isColdCount(*TotalCallCount))
 155         return false;
 156
 157     for (const auto &BB : *F)
 158       if (!isColdBlock(&BB, &BFI))
 159         return false;
 160     return true;
 161   }
 162   /// Returns true if the hotness of \p F is unknown.
 163   bool isFunctionHotnessUnknown(const Function &F) const;
 164   /// Returns true if \p F contains hot code with regard to a given hot
 165   /// percentile cutoff value.
 166   template <typename FuncT, typename BFIT>
 167   bool isFunctionHotInCallGraphNthPercentile(int PercentileCutoff,
 168                                              const FuncT *F, BFIT &BFI) const {
 169     return isFunctionHotOrColdInCallGraphNthPercentile<true, FuncT, BFIT>(
 170         PercentileCutoff, F, BFI);
 171   }
 172   /// Returns true if \p F contains cold code with regard to a given cold
 173   /// percentile cutoff value.
 174   template <typename FuncT, typename BFIT>
 175   bool isFunctionColdInCallGraphNthPercentile(int PercentileCutoff,
 176                                               const FuncT *F, BFIT &BFI) const {
 177     return isFunctionHotOrColdInCallGraphNthPercentile<false, FuncT, BFIT>(
 178         PercentileCutoff, F, BFI);
 179   }
 180   /// Returns true if count \p C is considered hot.
 181   bool isHotCount(uint64_t C) const;
 182   /// Returns true if count \p C is considered cold.
 183   bool isColdCount(uint64_t C) const;
 184   /// Returns true if count \p C is considered hot with regard to a given
 185   /// hot percentile cutoff value.
 186   /// PercentileCutoff is encoded as a 6 digit decimal fixed point number, where
 187   /// the first two digits are the whole part. E.g. 995000 for 99.5 percentile.
 188   bool isHotCountNthPercentile(int PercentileCutoff, uint64_t C) const;
 189   /// Returns true if count \p C is considered cold with regard to a given
 190   /// cold percentile cutoff value.
 191   /// PercentileCutoff is encoded as a 6 digit decimal fixed point number, where
 192   /// the first two digits are the whole part. E.g. 995000 for 99.5 percentile.
 193   bool isColdCountNthPercentile(int PercentileCutoff, uint64_t C) const;
 194
 195   /// Returns true if BasicBlock \p BB is considered hot.
 196   template <typename BBType, typename BFIT>
 197   bool isHotBlock(const BBType *BB, BFIT *BFI) const {
 198     auto Count = BFI->getBlockProfileCount(BB);
 199     return Count && isHotCount(*Count);
 200   }
 201
 202   /// Returns true if BasicBlock \p BB is considered cold.
 203   template <typename BBType, typename BFIT>
 204   bool isColdBlock(const BBType *BB, BFIT *BFI) const {
 205     auto Count = BFI->getBlockProfileCount(BB);
 206     return Count && isColdCount(*Count);
 207   }
 208
 209   template <typename BFIT>
 210   bool isColdBlock(BlockFrequency BlockFreq, const BFIT *BFI) const {
 211     auto Count = BFI->getProfileCountFromFreq(BlockFreq);
 212     return Count && isColdCount(*Count);
 213   }
 214
 215   template <typename BBType, typename BFIT>
 216   bool isHotBlockNthPercentile(int PercentileCutoff, const BBType *BB,
 217                                BFIT *BFI) const {
 218     return isHotOrColdBlockNthPercentile<true, BBType, BFIT>(PercentileCutoff,
 219                                                              BB, BFI);
 220   }
 221
 222   template <typename BFIT>
 223   bool isHotBlockNthPercentile(int PercentileCutoff, BlockFrequency BlockFreq,
 224                                BFIT *BFI) const {
 225     return isHotOrColdBlockNthPercentile<true, BFIT>(PercentileCutoff,
 226                                                      BlockFreq, BFI);
 227   }
 228
 229   /// Returns true if BasicBlock \p BB is considered cold with regard to a given
 230   /// cold percentile cutoff value.
 231   /// PercentileCutoff is encoded as a 6 digit decimal fixed point number, where
 232   /// the first two digits are the whole part. E.g. 995000 for 99.5 percentile.
 233   template <typename BBType, typename BFIT>
 234   bool isColdBlockNthPercentile(int PercentileCutoff, const BBType *BB,
 235                                 BFIT *BFI) const {
 236     return isHotOrColdBlockNthPercentile<false, BBType, BFIT>(PercentileCutoff,
 237                                                               BB, BFI);
 238   }
 239   template <typename BFIT>
 240   bool isColdBlockNthPercentile(int PercentileCutoff, BlockFrequency BlockFreq,
 241                                 BFIT *BFI) const {
 242     return isHotOrColdBlockNthPercentile<false, BFIT>(PercentileCutoff,
 243                                                       BlockFreq, BFI);
 244   }
 245   /// Returns true if the call site \p CB is considered hot.
 246   bool isHotCallSite(const CallBase &CB, BlockFrequencyInfo *BFI) const;
 247   /// Returns true if call site \p CB is considered cold.
 248   bool isColdCallSite(const CallBase &CB, BlockFrequencyInfo *BFI) const;
 249   /// Returns HotCountThreshold if set. Recompute HotCountThreshold
 250   /// if not set.
 251   uint64_t getOrCompHotCountThreshold() const;
 252   /// Returns ColdCountThreshold if set. Recompute HotCountThreshold
 253   /// if not set.
 254   uint64_t getOrCompColdCountThreshold() const;
 255   /// Returns HotCountThreshold if set.
 256   uint64_t getHotCountThreshold() const {
 257     return HotCountThreshold.value_or(0);
 258   }
 259   /// Returns ColdCountThreshold if set.
 260   uint64_t getColdCountThreshold() const {
 261     return ColdCountThreshold.value_or(0);
 262   }
 263
 264 private:
 265   template <typename FuncT>
 266   std::optional<uint64_t> getTotalCallCount(const FuncT *F) const {
 267     return std::nullopt;
 268   }
 269
 270   template <bool isHot, typename FuncT, typename BFIT>
 271   bool isFunctionHotOrColdInCallGraphNthPercentile(int PercentileCutoff,
 272                                                    const FuncT *F,
 273                                                    BFIT &FI) const {
 274     if (!F || !hasProfileSummary())
 275       return false;
 276     if (auto FunctionCount = getEntryCount(F)) {
 277       if (isHot &&
 278           isHotCountNthPercentile(PercentileCutoff, FunctionCount->getCount()))
 279         return true;
 280       if (!isHot && !isColdCountNthPercentile(PercentileCutoff,
 281                                               FunctionCount->getCount()))
 282         return false;
 283     }
 284     if (auto TotalCallCount = getTotalCallCount(F)) {
 285       if (isHot && isHotCountNthPercentile(PercentileCutoff, *TotalCallCount))
 286         return true;
 287       if (!isHot &&
 288           !isColdCountNthPercentile(PercentileCutoff, *TotalCallCount))
 289         return false;
 290     }
 291     for (const auto &BB : *F) {
 292       if (isHot && isHotBlockNthPercentile(PercentileCutoff, &BB, &FI))
 293         return true;
 294       if (!isHot && !isColdBlockNthPercentile(PercentileCutoff, &BB, &FI))
 295         return false;
 296     }
 297     return !isHot;
 298   }
 299
 300   template <bool isHot>
 301   bool isHotOrColdCountNthPercentile(int PercentileCutoff, uint64_t C) const;
 302
 303   template <bool isHot, typename BBType, typename BFIT>
 304   bool isHotOrColdBlockNthPercentile(int PercentileCutoff, const BBType *BB,
 305                                      BFIT *BFI) const {
 306     auto Count = BFI->getBlockProfileCount(BB);
 307     if (isHot)
 308       return Count && isHotCountNthPercentile(PercentileCutoff, *Count);
 309     else
 310       return Count && isColdCountNthPercentile(PercentileCutoff, *Count);
 311   }
 312
 313   template <bool isHot, typename BFIT>
 314   bool isHotOrColdBlockNthPercentile(int PercentileCutoff,
 315                                      BlockFrequency BlockFreq,
 316                                      BFIT *BFI) const {
 317     auto Count = BFI->getProfileCountFromFreq(BlockFreq);
 318     if (isHot)
 319       return Count && isHotCountNthPercentile(PercentileCutoff, *Count);
 320     else
 321       return Count && isColdCountNthPercentile(PercentileCutoff, *Count);
 322   }
 323
 324   template <typename FuncT>
 325   std::optional<Function::ProfileCount> getEntryCount(const FuncT *F) const {
 326     return F->getEntryCount();
 327   }
 328 };
 329
 330 template <>
 331 inline std::optional<uint64_t>
 332 ProfileSummaryInfo::getTotalCallCount<Function>(const Function *F) const {
 333   if (!hasSampleProfile())
 334     return std::nullopt;
 335   uint64_t TotalCallCount = 0;
 336   for (const auto &BB : *F)
 337     for (const auto &I : BB)
 338       if (isa<CallInst>(I) || isa<InvokeInst>(I))
 339         if (auto CallCount = getProfileCount(cast<CallBase>(I), nullptr))
 340           TotalCallCount += *CallCount;
 341   return TotalCallCount;
 342 }
 343
 344 // Declare template specialization for llvm::MachineFunction. Do not implement
 345 // here, because we cannot include MachineFunction header here, that would break
 346 // dependency rules.
 347 template <>
 348 std::optional<Function::ProfileCount>
 349 ProfileSummaryInfo::getEntryCount<MachineFunction>(
 350     const MachineFunction *F) const;
 351
 352 /// An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
 353 class ProfileSummaryInfoWrapperPass : public ImmutablePass {
 354   std::unique_ptr<ProfileSummaryInfo> PSI;
 355
 356 public:
 357   static char ID;
 358   ProfileSummaryInfoWrapperPass();
 359
 360   ProfileSummaryInfo &getPSI() { return *PSI; }
 361   const ProfileSummaryInfo &getPSI() const { return *PSI; }
 362
 363   bool doInitialization(Module &M) override;
 364   bool doFinalization(Module &M) override;
 365   void getAnalysisUsage(AnalysisUsage &AU) const override {
 366     AU.setPreservesAll();
 367   }
 368 };
 369
 370 /// An analysis pass based on the new PM to deliver ProfileSummaryInfo.
 371 class ProfileSummaryAnalysis
 372     : public AnalysisInfoMixin<ProfileSummaryAnalysis> {
 373 public:
 374   typedef ProfileSummaryInfo Result;
 375
 376   Result run(Module &M, ModuleAnalysisManager &);
 377
 378 private:
 379   friend AnalysisInfoMixin<ProfileSummaryAnalysis>;
 380   static AnalysisKey Key;
 381 };
 382
 383 /// Printer pass that uses \c ProfileSummaryAnalysis.
 384 class ProfileSummaryPrinterPass
 385     : public PassInfoMixin<ProfileSummaryPrinterPass> {
 386   raw_ostream &OS;
 387
 388 public:
 389   explicit ProfileSummaryPrinterPass(raw_ostream &OS) : OS(OS) {}
 390   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 391   static bool isRequired() { return true; }
 392 };
 393
 394 } // end namespace llvm
 395
 396 #endif