//===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file implements the SampleProfileLoader transformation. This pass

// reads a profile file generated by a sampling profiler (e.g. Linux Perf -

// http://perf.wiki.kernel.org/) and generates IR metadata to reflect the

// profile information in the given profile.

//

// This pass generates branch weight annotations on the IR:

//

// - prof: Represents branch weights. This annotation is added to branches

//      to indicate the weights of each edge coming out of the branch.

//      The weight of each edge is the weight of the target block for

//      that edge. The weight of a block B is computed as the maximum

//      number of samples found in B.

//

//===----------------------------------------------------------------------===//

#include "llvm/Transforms/IPO/SampleProfile.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/DenseSet.h"

#include "llvm/ADT/MapVector.h"

#include "llvm/ADT/PriorityQueue.h"

#include "llvm/ADT/SCCIterator.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/Statistic.h"

#include "llvm/ADT/StringMap.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/ADT/Twine.h"

#include "llvm/Analysis/AssumptionCache.h"

#include "llvm/Analysis/BlockFrequencyInfoImpl.h"

#include "llvm/Analysis/InlineAdvisor.h"

#include "llvm/Analysis/InlineCost.h"

#include "llvm/Analysis/LazyCallGraph.h"

#include "llvm/Analysis/OptimizationRemarkEmitter.h"

#include "llvm/Analysis/ProfileSummaryInfo.h"

#include "llvm/Analysis/ReplayInlineAdvisor.h"

#include "llvm/Analysis/TargetLibraryInfo.h"

#include "llvm/Analysis/TargetTransformInfo.h"

#include "llvm/IR/BasicBlock.h"

#include "llvm/IR/DebugLoc.h"

#include "llvm/IR/DiagnosticInfo.h"

#include "llvm/IR/Function.h"

#include "llvm/IR/GlobalValue.h"

#include "llvm/IR/InstrTypes.h"

#include "llvm/IR/Instruction.h"

#include "llvm/IR/Instructions.h"

#include "llvm/IR/IntrinsicInst.h"

#include "llvm/IR/LLVMContext.h"

#include "llvm/IR/MDBuilder.h"

#include "llvm/IR/Module.h"

#include "llvm/IR/PassManager.h"

#include "llvm/IR/ProfDataUtils.h"

#include "llvm/IR/PseudoProbe.h"

#include "llvm/IR/ValueSymbolTable.h"

#include "llvm/ProfileData/InstrProf.h"

#include "llvm/ProfileData/SampleProf.h"

#include "llvm/ProfileData/SampleProfReader.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/CommandLine.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/ErrorOr.h"

#include "llvm/Support/VirtualFileSystem.h"

#include "llvm/Support/raw_ostream.h"

#include "llvm/Transforms/IPO.h"

#include "llvm/Transforms/IPO/ProfiledCallGraph.h"

#include "llvm/Transforms/IPO/SampleContextTracker.h"

#include "llvm/Transforms/IPO/SampleProfileProbe.h"

#include "llvm/Transforms/Instrumentation.h"

#include "llvm/Transforms/Utils/CallPromotionUtils.h"

#include "llvm/Transforms/Utils/Cloning.h"

#include "llvm/Transforms/Utils/MisExpect.h"

#include "llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h"

#include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h"

#include <algorithm>

#include <cassert>

#include <cstdint>

#include <functional>

#include <limits>

#include <map>

#include <memory>

#include <queue>

#include <string>

#include <system_error>

#include <utility>

#include <vector>

using namespace llvm;

using namespace sampleprof;

using namespace llvm::sampleprofutil;

using ProfileCount = Function::ProfileCount;

#define DEBUG_TYPE "sample-profile"

#define CSINLINE_DEBUG DEBUG_TYPE "-inline"

STATISTIC(NumCSInlined,

          "Number of functions inlined with context sensitive profile");

STATISTIC(NumCSNotInlined,

          "Number of functions not inlined with context sensitive profile");

STATISTIC(NumMismatchedProfile,

          "Number of functions with CFG mismatched profile");

STATISTIC(NumMatchedProfile, "Number of functions with CFG matched profile");

STATISTIC(NumDuplicatedInlinesite,

          "Number of inlined callsites with a partial distribution factor");

STATISTIC(NumCSInlinedHitMinLimit,

          "Number of functions with FDO inline stopped due to min size limit");

STATISTIC(NumCSInlinedHitMaxLimit,

          "Number of functions with FDO inline stopped due to max size limit");

STATISTIC(

    NumCSInlinedHitGrowthLimit,

    "Number of functions with FDO inline stopped due to growth size limit");

// Command line option to specify the file to read samples from. This is

// mainly used for debugging.

static cl::opt<std::string> SampleProfileFile(

    "sample-profile-file", cl::init(""), cl::value_desc("filename"),

    cl::desc("Profile file loaded by -sample-profile"), cl::Hidden);

// The named file contains a set of transformations that may have been applied

// to the symbol names between the program from which the sample data was

// collected and the current program's symbols.

static cl::opt<std::string> SampleProfileRemappingFile(

    "sample-profile-remapping-file", cl::init(""), cl::value_desc("filename"),

    cl::desc("Profile remapping file loaded by -sample-profile"), cl::Hidden);

static cl::opt<bool> SalvageStaleProfile(

    "salvage-stale-profile", cl::Hidden, cl::init(false),

    cl::desc("Salvage stale profile by fuzzy matching and use the remapped "

             "location for sample profile query."));

static cl::opt<bool> ReportProfileStaleness(

    "report-profile-staleness", cl::Hidden, cl::init(false),

    cl::desc("Compute and report stale profile statistical metrics."));

static cl::opt<bool> PersistProfileStaleness(

    "persist-profile-staleness", cl::Hidden, cl::init(false),

    cl::desc("Compute stale profile statistical metrics and write it into the "

             "native object file(.llvm_stats section)."));

static cl::opt<bool> ProfileSampleAccurate(

    "profile-sample-accurate", cl::Hidden, cl::init(false),

    cl::desc("If the sample profile is accurate, we will mark all un-sampled "

             "callsite and function as having 0 samples. Otherwise, treat "

             "un-sampled callsites and functions conservatively as unknown. "));

static cl::opt<bool> ProfileSampleBlockAccurate(

    "profile-sample-block-accurate", cl::Hidden, cl::init(false),

    cl::desc("If the sample profile is accurate, we will mark all un-sampled "

             "branches and calls as having 0 samples. Otherwise, treat "

             "them conservatively as unknown. "));

static cl::opt<bool> ProfileAccurateForSymsInList(

    "profile-accurate-for-symsinlist", cl::Hidden, cl::init(true),

    cl::desc("For symbols in profile symbol list, regard their profiles to "

             "be accurate. It may be overriden by profile-sample-accurate. "));

static cl::opt<bool> ProfileMergeInlinee(

    "sample-profile-merge-inlinee", cl::Hidden, cl::init(true),

    cl::desc("Merge past inlinee's profile to outline version if sample "

             "profile loader decided not to inline a call site. It will "

             "only be enabled when top-down order of profile loading is "

             "enabled. "));

static cl::opt<bool> ProfileTopDownLoad(

    "sample-profile-top-down-load", cl::Hidden, cl::init(true),

    cl::desc("Do profile annotation and inlining for functions in top-down "

             "order of call graph during sample profile loading. It only "

             "works for new pass manager. "));

static cl::opt<bool>

    UseProfiledCallGraph("use-profiled-call-graph", cl::init(true), cl::Hidden,

                         cl::desc("Process functions in a top-down order "

                                  "defined by the profiled call graph when "

                                  "-sample-profile-top-down-load is on."));

static cl::opt<bool> ProfileSizeInline(

    "sample-profile-inline-size", cl::Hidden, cl::init(false),

    cl::desc("Inline cold call sites in profile loader if it's beneficial "

             "for code size."));

// Since profiles are consumed by many passes, turning on this option has

// side effects. For instance, pre-link SCC inliner would see merged profiles

// and inline the hot functions (that are skipped in this pass).

static cl::opt<bool> DisableSampleLoaderInlining(

    "disable-sample-loader-inlining", cl::Hidden, cl::init(false),

    cl::desc("If true, artifically skip inline transformation in sample-loader "

             "pass, and merge (or scale) profiles (as configured by "

             "--sample-profile-merge-inlinee)."));

namespace llvm {

cl::opt<bool>

    SortProfiledSCC("sort-profiled-scc-member", cl::init(true), cl::Hidden,

                    cl::desc("Sort profiled recursion by edge weights."));

cl::opt<int> ProfileInlineGrowthLimit(

    "sample-profile-inline-growth-limit", cl::Hidden, cl::init(12),

    cl::desc("The size growth ratio limit for proirity-based sample profile "

             "loader inlining."));

cl::opt<int> ProfileInlineLimitMin(

    "sample-profile-inline-limit-min", cl::Hidden, cl::init(100),

    cl::desc("The lower bound of size growth limit for "

             "proirity-based sample profile loader inlining."));

cl::opt<int> ProfileInlineLimitMax(

    "sample-profile-inline-limit-max", cl::Hidden, cl::init(10000),

    cl::desc("The upper bound of size growth limit for "

             "proirity-based sample profile loader inlining."));

cl::opt<int> SampleHotCallSiteThreshold(

    "sample-profile-hot-inline-threshold", cl::Hidden, cl::init(3000),

    cl::desc("Hot callsite threshold for proirity-based sample profile loader "

             "inlining."));

cl::opt<int> SampleColdCallSiteThreshold(

    "sample-profile-cold-inline-threshold", cl::Hidden, cl::init(45),

    cl::desc("Threshold for inlining cold callsites"));

} // namespace llvm

static cl::opt<unsigned> ProfileICPRelativeHotness(

    "sample-profile-icp-relative-hotness", cl::Hidden, cl::init(25),

    cl::desc(

        "Relative hotness percentage threshold for indirect "

        "call promotion in proirity-based sample profile loader inlining."));

static cl::opt<unsigned> ProfileICPRelativeHotnessSkip(

    "sample-profile-icp-relative-hotness-skip", cl::Hidden, cl::init(1),

    cl::desc(

        "Skip relative hotness check for ICP up to given number of targets."));

static cl::opt<bool> CallsitePrioritizedInline(

    "sample-profile-prioritized-inline", cl::Hidden,

    cl::desc("Use call site prioritized inlining for sample profile loader."

             "Currently only CSSPGO is supported."));

static cl::opt<bool> UsePreInlinerDecision(

    "sample-profile-use-preinliner", cl::Hidden,

    cl::desc("Use the preinliner decisions stored in profile context."));

static cl::opt<bool> AllowRecursiveInline(

    "sample-profile-recursive-inline", cl::Hidden,

    cl::desc("Allow sample loader inliner to inline recursive calls."));

static cl::opt<std::string> ProfileInlineReplayFile(

    "sample-profile-inline-replay", cl::init(""), cl::value_desc("filename"),

    cl::desc(

        "Optimization remarks file containing inline remarks to be replayed "

        "by inlining from sample profile loader."),

    cl::Hidden);

static cl::opt<ReplayInlinerSettings::Scope> ProfileInlineReplayScope(

    "sample-profile-inline-replay-scope",

    cl::init(ReplayInlinerSettings::Scope::Function),

    cl::values(clEnumValN(ReplayInlinerSettings::Scope::Function, "Function",

                          "Replay on functions that have remarks associated "

                          "with them (default)"),

               clEnumValN(ReplayInlinerSettings::Scope::Module, "Module",

                          "Replay on the entire module")),

    cl::desc("Whether inline replay should be applied to the entire "

             "Module or just the Functions (default) that are present as "

             "callers in remarks during sample profile inlining."),

    cl::Hidden);

static cl::opt<ReplayInlinerSettings::Fallback> ProfileInlineReplayFallback(

    "sample-profile-inline-replay-fallback",

    cl::init(ReplayInlinerSettings::Fallback::Original),

    cl::values(

        clEnumValN(

            ReplayInlinerSettings::Fallback::Original, "Original",

            "All decisions not in replay send to original advisor (default)"),

        clEnumValN(ReplayInlinerSettings::Fallback::AlwaysInline,

                   "AlwaysInline", "All decisions not in replay are inlined"),

        clEnumValN(ReplayInlinerSettings::Fallback::NeverInline, "NeverInline",

                   "All decisions not in replay are not inlined")),

    cl::desc("How sample profile inline replay treats sites that don't come "

             "from the replay. Original: defers to original advisor, "

             "AlwaysInline: inline all sites not in replay, NeverInline: "

             "inline no sites not in replay"),

    cl::Hidden);

static cl::opt<CallSiteFormat::Format> ProfileInlineReplayFormat(

    "sample-profile-inline-replay-format",

    cl::init(CallSiteFormat::Format::LineColumnDiscriminator),

    cl::values(

        clEnumValN(CallSiteFormat::Format::Line, "Line", "<Line Number>"),

        clEnumValN(CallSiteFormat::Format::LineColumn, "LineColumn",

                   "<Line Number>:<Column Number>"),

        clEnumValN(CallSiteFormat::Format::LineDiscriminator,

                   "LineDiscriminator", "<Line Number>.<Discriminator>"),

        clEnumValN(CallSiteFormat::Format::LineColumnDiscriminator,

                   "LineColumnDiscriminator",

                   "<Line Number>:<Column Number>.<Discriminator> (default)")),

    cl::desc("How sample profile inline replay file is formatted"), cl::Hidden);

static cl::opt<unsigned>

    MaxNumPromotions("sample-profile-icp-max-prom", cl::init(3), cl::Hidden,

                     cl::desc("Max number of promotions for a single indirect "

                              "call callsite in sample profile loader"));

static cl::opt<bool> OverwriteExistingWeights(

    "overwrite-existing-weights", cl::Hidden, cl::init(false),

    cl::desc("Ignore existing branch weights on IR and always overwrite."));

static cl::opt<bool> AnnotateSampleProfileInlinePhase(

    "annotate-sample-profile-inline-phase", cl::Hidden, cl::init(false),

    cl::desc("Annotate LTO phase (prelink / postlink), or main (no LTO) for "

             "sample-profile inline pass name."));

namespace llvm {

extern cl::opt<bool> EnableExtTspBlockPlacement;

}

namespace {

using BlockWeightMap = DenseMap<const BasicBlock *, uint64_t>;

using EquivalenceClassMap = DenseMap<const BasicBlock *, const BasicBlock *>;

using Edge = std::pair<const BasicBlock *, const BasicBlock *>;

using EdgeWeightMap = DenseMap<Edge, uint64_t>;

using BlockEdgeMap =

    DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>;

class GUIDToFuncNameMapper {

public:

  GUIDToFuncNameMapper(Module &M, SampleProfileReader &Reader,

                       DenseMap<uint64_t, StringRef> &GUIDToFuncNameMap)

      : CurrentReader(Reader), CurrentModule(M),

        CurrentGUIDToFuncNameMap(GUIDToFuncNameMap) {

    if (!CurrentReader.useMD5())

      return;

    for (const auto &F : CurrentModule) {

      StringRef OrigName = F.getName();

      CurrentGUIDToFuncNameMap.insert(

          {Function::getGUID(OrigName), OrigName});

      // Local to global var promotion used by optimization like thinlto

      // will rename the var and add suffix like ".llvm.xxx" to the

      // original local name. In sample profile, the suffixes of function

      // names are all stripped. Since it is possible that the mapper is

      // built in post-thin-link phase and var promotion has been done,

      // we need to add the substring of function name without the suffix

      // into the GUIDToFuncNameMap.

      StringRef CanonName = FunctionSamples::getCanonicalFnName(F);

      if (CanonName != OrigName)

        CurrentGUIDToFuncNameMap.insert(

            {Function::getGUID(CanonName), CanonName});

    }

    // Update GUIDToFuncNameMap for each function including inlinees.

    SetGUIDToFuncNameMapForAll(&CurrentGUIDToFuncNameMap);

  }

  ~GUIDToFuncNameMapper() {

    if (!CurrentReader.useMD5())

      return;

    CurrentGUIDToFuncNameMap.clear();

    // Reset GUIDToFuncNameMap for of each function as they're no

    // longer valid at this point.

    SetGUIDToFuncNameMapForAll(nullptr);

  }

private:

  void SetGUIDToFuncNameMapForAll(DenseMap<uint64_t, StringRef> *Map) {

    std::queue<FunctionSamples *> FSToUpdate;

    for (auto &IFS : CurrentReader.getProfiles()) {

      FSToUpdate.push(&IFS.second);

    }

    while (!FSToUpdate.empty()) {

      FunctionSamples *FS = FSToUpdate.front();

      FSToUpdate.pop();

      FS->GUIDToFuncNameMap = Map;

      for (const auto &ICS : FS->getCallsiteSamples()) {

        const FunctionSamplesMap &FSMap = ICS.second;

        for (const auto &IFS : FSMap) {

          FunctionSamples &FS = const_cast<FunctionSamples &>(IFS.second);

          FSToUpdate.push(&FS);

        }

      }

    }

  }

  SampleProfileReader &CurrentReader;

  Module &CurrentModule;

  DenseMap<uint64_t, StringRef> &CurrentGUIDToFuncNameMap;

};

// Inline candidate used by iterative callsite prioritized inliner

struct InlineCandidate {

  CallBase *CallInstr;

  const FunctionSamples *CalleeSamples;

  // Prorated callsite count, which will be used to guide inlining. For example,

  // if a callsite is duplicated in LTO prelink, then in LTO postlink the two

  // copies will get their own distribution factors and their prorated counts

  // will be used to decide if they should be inlined independently.

  uint64_t CallsiteCount;

  // Call site distribution factor to prorate the profile samples for a

  // duplicated callsite. Default value is 1.0.

  float CallsiteDistribution;

};

// Inline candidate comparer using call site weight

struct CandidateComparer {

  bool operator()(const InlineCandidate &LHS, const InlineCandidate &RHS) {

    if (LHS.CallsiteCount != RHS.CallsiteCount)

      return LHS.CallsiteCount < RHS.CallsiteCount;

    const FunctionSamples *LCS = LHS.CalleeSamples;

    const FunctionSamples *RCS = RHS.CalleeSamples;

    assert(LCS && RCS && "Expect non-null FunctionSamples");

    // Tie breaker using number of samples try to favor smaller functions first

    if (LCS->getBodySamples().size() != RCS->getBodySamples().size())

      return LCS->getBodySamples().size() > RCS->getBodySamples().size();

    // Tie breaker using GUID so we have stable/deterministic inlining order

    return LCS->getGUID() < RCS->getGUID();

  }

};

using CandidateQueue =

    PriorityQueue<InlineCandidate, std::vector<InlineCandidate>,

                  CandidateComparer>;

// Sample profile matching - fuzzy match.

class SampleProfileMatcher {

  Module &M;

  SampleProfileReader &Reader;

  const PseudoProbeManager *ProbeManager;

  SampleProfileMap FlattenedProfiles;

  // For each function, the matcher generates a map, of which each entry is a

  // mapping from the source location of current build to the source location in

  // the profile.

  StringMap<LocToLocMap> FuncMappings;

  // Profile mismatching statstics.

  uint64_t TotalProfiledCallsites = 0;

  uint64_t NumMismatchedCallsites = 0;

  uint64_t MismatchedCallsiteSamples = 0;

  uint64_t TotalCallsiteSamples = 0;

  uint64_t TotalProfiledFunc = 0;

  uint64_t NumMismatchedFuncHash = 0;

  uint64_t MismatchedFuncHashSamples = 0;

  uint64_t TotalFuncHashSamples = 0;

  // A dummy name for unknown indirect callee, used to differentiate from a

  // non-call instruction that also has an empty callee name.

  static constexpr const char *UnknownIndirectCallee =

      "unknown.indirect.callee";

public:

  SampleProfileMatcher(Module &M, SampleProfileReader &Reader,

                       const PseudoProbeManager *ProbeManager)

      : M(M), Reader(Reader), ProbeManager(ProbeManager){};

  void runOnModule();

private:

  FunctionSamples *getFlattenedSamplesFor(const Function &F) {

    StringRef CanonFName = FunctionSamples::getCanonicalFnName(F);

    auto It = FlattenedProfiles.find(FunctionId(CanonFName));

    if (It != FlattenedProfiles.end())

      return &It->second;

    return nullptr;

  }

  void runOnFunction(const Function &F);

  void findIRAnchors(const Function &F,

                     std::map<LineLocation, StringRef> &IRAnchors);

  void findProfileAnchors(

      const FunctionSamples &FS,

      std::map<LineLocation, std::unordered_set<FunctionId>>

          &ProfileAnchors);

  void countMismatchedSamples(const FunctionSamples &FS);

  void countProfileMismatches(

      const Function &F, const FunctionSamples &FS,

      const std::map<LineLocation, StringRef> &IRAnchors,

      const std::map<LineLocation, std::unordered_set<FunctionId>>

          &ProfileAnchors);

  void countProfileCallsiteMismatches(

      const FunctionSamples &FS,

      const std::map<LineLocation, StringRef> &IRAnchors,

      const std::map<LineLocation, std::unordered_set<FunctionId>>

          &ProfileAnchors,

      uint64_t &FuncMismatchedCallsites, uint64_t &FuncProfiledCallsites);

  LocToLocMap &getIRToProfileLocationMap(const Function &F) {

    auto Ret = FuncMappings.try_emplace(

        FunctionSamples::getCanonicalFnName(F.getName()), LocToLocMap());

    return Ret.first->second;

  }

  void distributeIRToProfileLocationMap();

  void distributeIRToProfileLocationMap(FunctionSamples &FS);

  void runStaleProfileMatching(

      const Function &F, const std::map<LineLocation, StringRef> &IRAnchors,

      const std::map<LineLocation, std::unordered_set<FunctionId>>

          &ProfileAnchors,

      LocToLocMap &IRToProfileLocationMap);

};

/// Sample profile pass.

///

/// This pass reads profile data from the file specified by

/// -sample-profile-file and annotates every affected function with the

/// profile information found in that file.

class SampleProfileLoader final : public SampleProfileLoaderBaseImpl<Function> {

public:

  SampleProfileLoader(

      StringRef Name, StringRef RemapName, ThinOrFullLTOPhase LTOPhase,

      IntrusiveRefCntPtr<vfs::FileSystem> FS,

      std::function<AssumptionCache &(Function &)> GetAssumptionCache,

      std::function<TargetTransformInfo &(Function &)> GetTargetTransformInfo,

      std::function<const TargetLibraryInfo &(Function &)> GetTLI)

      : SampleProfileLoaderBaseImpl(std::string(Name), std::string(RemapName),

                                    std::move(FS)),

        GetAC(std::move(GetAssumptionCache)),

        GetTTI(std::move(GetTargetTransformInfo)), GetTLI(std::move(GetTLI)),

        LTOPhase(LTOPhase),

        AnnotatedPassName(AnnotateSampleProfileInlinePhase

                              ? llvm::AnnotateInlinePassName(InlineContext{

                                    LTOPhase, InlinePass::SampleProfileInliner})

                              : CSINLINE_DEBUG) {}

  bool doInitialization(Module &M, FunctionAnalysisManager *FAM = nullptr);

  bool runOnModule(Module &M, ModuleAnalysisManager *AM,

                   ProfileSummaryInfo *_PSI, LazyCallGraph &CG);

protected:

  bool runOnFunction(Function &F, ModuleAnalysisManager *AM);

  bool emitAnnotations(Function &F);

  ErrorOr<uint64_t> getInstWeight(const Instruction &I) override;

  const FunctionSamples *findCalleeFunctionSamples(const CallBase &I) const;

  const FunctionSamples *

  findFunctionSamples(const Instruction &I) const override;

  std::vector<const FunctionSamples *>

  findIndirectCallFunctionSamples(const Instruction &I, uint64_t &Sum) const;

  void findExternalInlineCandidate(CallBase *CB, const FunctionSamples *Samples,

                                   DenseSet<GlobalValue::GUID> &InlinedGUIDs,

                                   uint64_t Threshold);

  // Attempt to promote indirect call and also inline the promoted call

  bool tryPromoteAndInlineCandidate(

      Function &F, InlineCandidate &Candidate, uint64_t SumOrigin,

      uint64_t &Sum, SmallVector<CallBase *, 8> *InlinedCallSites = nullptr);

  bool inlineHotFunctions(Function &F,

                          DenseSet<GlobalValue::GUID> &InlinedGUIDs);

  std::optional<InlineCost> getExternalInlineAdvisorCost(CallBase &CB);

  bool getExternalInlineAdvisorShouldInline(CallBase &CB);

  InlineCost shouldInlineCandidate(InlineCandidate &Candidate);

  bool getInlineCandidate(InlineCandidate *NewCandidate, CallBase *CB);

  bool

  tryInlineCandidate(InlineCandidate &Candidate,

                     SmallVector<CallBase *, 8> *InlinedCallSites = nullptr);

  bool

  inlineHotFunctionsWithPriority(Function &F,

                                 DenseSet<GlobalValue::GUID> &InlinedGUIDs);

  // Inline cold/small functions in addition to hot ones

  bool shouldInlineColdCallee(CallBase &CallInst);

  void emitOptimizationRemarksForInlineCandidates(

      const SmallVectorImpl<CallBase *> &Candidates, const Function &F,

      bool Hot);

  void promoteMergeNotInlinedContextSamples(

      MapVector<CallBase *, const FunctionSamples *> NonInlinedCallSites,

      const Function &F);

  std::vector<Function *> buildFunctionOrder(Module &M, LazyCallGraph &CG);

  std::unique_ptr<ProfiledCallGraph> buildProfiledCallGraph(Module &M);

  void generateMDProfMetadata(Function &F);

  /// Map from function name to Function *. Used to find the function from

  /// the function name. If the function name contains suffix, additional

  /// entry is added to map from the stripped name to the function if there

  /// is one-to-one mapping.

  HashKeyMap<std::unordered_map, FunctionId, Function *> SymbolMap;

  std::function<AssumptionCache &(Function &)> GetAC;

  std::function<TargetTransformInfo &(Function &)> GetTTI;

  std::function<const TargetLibraryInfo &(Function &)> GetTLI;

  /// Profile tracker for different context.

  std::unique_ptr<SampleContextTracker> ContextTracker;

  /// Flag indicating which LTO/ThinLTO phase the pass is invoked in.

  ///

  /// We need to know the LTO phase because for example in ThinLTOPrelink

  /// phase, in annotation, we should not promote indirect calls. Instead,

  /// we will mark GUIDs that needs to be annotated to the function.

  const ThinOrFullLTOPhase LTOPhase;

  const std::string AnnotatedPassName;

  /// Profle Symbol list tells whether a function name appears in the binary

  /// used to generate the current profile.

  std::unique_ptr<ProfileSymbolList> PSL;

  /// Total number of samples collected in this profile.

  ///

  /// This is the sum of all the samples collected in all the functions executed

  /// at runtime.

  uint64_t TotalCollectedSamples = 0;

  // Information recorded when we declined to inline a call site

  // because we have determined it is too cold is accumulated for

  // each callee function. Initially this is just the entry count.

  struct NotInlinedProfileInfo {

    uint64_t entryCount;

  };

  DenseMap<Function *, NotInlinedProfileInfo> notInlinedCallInfo;

  // GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for

  // all the function symbols defined or declared in current module.

  DenseMap<uint64_t, StringRef> GUIDToFuncNameMap;

  // All the Names used in FunctionSamples including outline function

  // names, inline instance names and call target names.

  StringSet<> NamesInProfile;

  // MD5 version of NamesInProfile. Either NamesInProfile or GUIDsInProfile is

  // populated, depends on whether the profile uses MD5. Because the name table

  // generally contains several magnitude more entries than the number of

  // functions, we do not want to convert all names from one form to another.

  llvm::DenseSet<uint64_t> GUIDsInProfile;

  // For symbol in profile symbol list, whether to regard their profiles

  // to be accurate. It is mainly decided by existance of profile symbol

  // list and -profile-accurate-for-symsinlist flag, but it can be

  // overriden by -profile-sample-accurate or profile-sample-accurate

  // attribute.

  bool ProfAccForSymsInList;

  // External inline advisor used to replay inline decision from remarks.

  std::unique_ptr<InlineAdvisor> ExternalInlineAdvisor;

  // A helper to implement the sample profile matching algorithm.

  std::unique_ptr<SampleProfileMatcher> MatchingManager;

private:

  const char *getAnnotatedRemarkPassName() const {

    return AnnotatedPassName.c_str();

  }

};

} // end anonymous namespace

namespace llvm {

template <>

inline bool SampleProfileInference<Function>::isExit(const BasicBlock *BB) {

  return succ_empty(BB);

}

template <>

inline void SampleProfileInference<Function>::findUnlikelyJumps(

    const std::vector<const BasicBlockT *> &BasicBlocks,

    BlockEdgeMap &Successors, FlowFunction &Func) {

  for (auto &Jump : Func.Jumps) {

    const auto *BB = BasicBlocks[Jump.Source];

    const auto *Succ = BasicBlocks[Jump.Target];

    const Instruction *TI = BB->getTerminator();

    // Check if a block ends with InvokeInst and mark non-taken branch unlikely.

    // In that case block Succ should be a landing pad

    if (Successors[BB].size() == 2 && Successors[BB].back() == Succ) {

      if (isa<InvokeInst>(TI)) {

        Jump.IsUnlikely = true;

      }

    }

    const Instruction *SuccTI = Succ->getTerminator();

    // Check if the target block contains UnreachableInst and mark it unlikely

    if (SuccTI->getNumSuccessors() == 0) {

      if (isa<UnreachableInst>(SuccTI)) {

        Jump.IsUnlikely = true;

      }

    }

  }

}

template <>

void SampleProfileLoaderBaseImpl<Function>::computeDominanceAndLoopInfo(

    Function &F) {

  DT.reset(new DominatorTree);

  DT->recalculate(F);

  PDT.reset(new PostDominatorTree(F));

  LI.reset(new LoopInfo);

  LI->analyze(*DT);

}

} // namespace llvm

ErrorOr<uint64_t> SampleProfileLoader::getInstWeight(const Instruction &Inst) {

  if (FunctionSamples::ProfileIsProbeBased)

    return getProbeWeight(Inst);

  const DebugLoc &DLoc = Inst.getDebugLoc();

  if (!DLoc)

    return std::error_code();

  // Ignore all intrinsics, phinodes and branch instructions.

  // Branch and phinodes instruction usually contains debug info from sources

  // outside of the residing basic block, thus we ignore them during annotation.

  if (isa<BranchInst>(Inst) || isa<IntrinsicInst>(Inst) || isa<PHINode>(Inst))

    return std::error_code();

  // For non-CS profile, if a direct call/invoke instruction is inlined in

  // profile (findCalleeFunctionSamples returns non-empty result), but not

  // inlined here, it means that the inlined callsite has no sample, thus the

  // call instruction should have 0 count.

  // For CS profile, the callsite count of previously inlined callees is

  // populated with the entry count of the callees.

  if (!FunctionSamples::ProfileIsCS)

    if (const auto *CB = dyn_cast<CallBase>(&Inst))

      if (!CB->isIndirectCall() && findCalleeFunctionSamples(*CB))

        return 0;

  return getInstWeightImpl(Inst);

}

/// Get the FunctionSamples for a call instruction.

///

/// The FunctionSamples of a call/invoke instruction \p Inst is the inlined

/// instance in which that call instruction is calling to. It contains

/// all samples that resides in the inlined instance. We first find the

/// inlined instance in which the call instruction is from, then we

/// traverse its children to find the callsite with the matching

/// location.

///

/// \param Inst Call/Invoke instruction to query.

///

/// \returns The FunctionSamples pointer to the inlined instance.

const FunctionSamples *

SampleProfileLoader::findCalleeFunctionSamples(const CallBase &Inst) const {

  const DILocation *DIL = Inst.getDebugLoc();

  if (!DIL) {

    return nullptr;

  }

  StringRef CalleeName;

  if (Function *Callee = Inst.getCalledFunction())

    CalleeName = Callee->getName();

  if (FunctionSamples::ProfileIsCS)

    return ContextTracker->getCalleeContextSamplesFor(Inst, CalleeName);

  const FunctionSamples *FS = findFunctionSamples(Inst);

  if (FS == nullptr)

    return nullptr;

  return FS->findFunctionSamplesAt(FunctionSamples::getCallSiteIdentifier(DIL),

                                   CalleeName, Reader->getRemapper());

}

/// Returns a vector of FunctionSamples that are the indirect call targets

/// of \p Inst. The vector is sorted by the total number of samples. Stores

/// the total call count of the indirect call in \p Sum.

std::vector<const FunctionSamples *>

SampleProfileLoader::findIndirectCallFunctionSamples(

    const Instruction &Inst, uint64_t &Sum) const {

  const DILocation *DIL = Inst.getDebugLoc();

  std::vector<const FunctionSamples *> R;

  if (!DIL) {

    return R;

  }

  auto FSCompare = [](const FunctionSamples *L, const FunctionSamples *R) {

    assert(L && R && "Expect non-null FunctionSamples");

    if (L->getHeadSamplesEstimate() != R->getHeadSamplesEstimate())

      return L->getHeadSamplesEstimate() > R->getHeadSamplesEstimate();

    return L->getGUID() < R->getGUID();

  };

  if (FunctionSamples::ProfileIsCS) {

    auto CalleeSamples =

        ContextTracker->getIndirectCalleeContextSamplesFor(DIL);

    if (CalleeSamples.empty())

      return R;

    // For CSSPGO, we only use target context profile's entry count

    // as that already includes both inlined callee and non-inlined ones..

    Sum = 0;

    for (const auto *const FS : CalleeSamples) {

      Sum += FS->getHeadSamplesEstimate();

      R.push_back(FS);

    }

    llvm::sort(R, FSCompare);

    return R;

  }

  const FunctionSamples *FS = findFunctionSamples(Inst);

  if (FS == nullptr)

    return R;

  auto CallSite = FunctionSamples::getCallSiteIdentifier(DIL);

  Sum = 0;

  if (auto T = FS->findCallTargetMapAt(CallSite))

    for (const auto &T_C : *T)

      Sum += T_C.second;

  if (const FunctionSamplesMap *M = FS->findFunctionSamplesMapAt(CallSite)) {

    if (M->empty())

      return R;

    for (const auto &NameFS : *M) {

      Sum += NameFS.second.getHeadSamplesEstimate();

      R.push_back(&NameFS.second);

    }

    llvm::sort(R, FSCompare);

  }

  return R;

}

const FunctionSamples *

SampleProfileLoader::findFunctionSamples(const Instruction &Inst) const {

  if (FunctionSamples::ProfileIsProbeBased) {

    std::optional<PseudoProbe> Probe = extractProbe(Inst);

    if (!Probe)

      return nullptr;

  }

  const DILocation *DIL = Inst.getDebugLoc();

  if (!DIL)

    return Samples;

  auto it = DILocation2SampleMap.try_emplace(DIL,nullptr);

  if (it.second) {

    if (FunctionSamples::ProfileIsCS)

      it.first->second = ContextTracker->getContextSamplesFor(DIL);

    else

      it.first->second =

          Samples->findFunctionSamples(DIL, Reader->getRemapper());

  }

  return it.first->second;

}

/// Check whether the indirect call promotion history of \p Inst allows

/// the promotion for \p Candidate.

/// If the profile count for the promotion candidate \p Candidate is

/// NOMORE_ICP_MAGICNUM, it means \p Candidate has already been promoted

/// for \p Inst. If we already have at least MaxNumPromotions

/// NOMORE_ICP_MAGICNUM count values in the value profile of \p Inst, we

/// cannot promote for \p Inst anymore.

static bool doesHistoryAllowICP(const Instruction &Inst, StringRef Candidate) {

  uint32_t NumVals = 0;

  uint64_t TotalCount = 0;

  std::unique_ptr<InstrProfValueData[]> ValueData =

      std::make_unique<InstrProfValueData[]>(MaxNumPromotions);

  bool Valid =

      getValueProfDataFromInst(Inst, IPVK_IndirectCallTarget, MaxNumPromotions,

                               ValueData.get(), NumVals, TotalCount, true);

  // No valid value profile so no promoted targets have been recorded

  // before. Ok to do ICP.

  if (!Valid)

    return true;

  unsigned NumPromoted = 0;

  for (uint32_t I = 0; I < NumVals; I++) {

    if (ValueData[I].Count != NOMORE_ICP_MAGICNUM)

      continue;

    // If the promotion candidate has NOMORE_ICP_MAGICNUM count in the

    // metadata, it means the candidate has been promoted for this

    // indirect call.

    if (ValueData[I].Value == Function::getGUID(Candidate))

      return false;

    NumPromoted++;

    // If already have MaxNumPromotions promotion, don't do it anymore.

    if (NumPromoted == MaxNumPromotions)

      return false;

  }

  return true;

}

/// Update indirect call target profile metadata for \p Inst.

/// Usually \p Sum is the sum of counts of all the targets for \p Inst.

/// If it is 0, it means updateIDTMetaData is used to mark a

/// certain target to be promoted already. If it is not zero,

/// we expect to use it to update the total count in the value profile.

static void

updateIDTMetaData(Instruction &Inst,

                  const SmallVectorImpl<InstrProfValueData> &CallTargets,

                  uint64_t Sum) {

  // Bail out early if MaxNumPromotions is zero.

  // This prevents allocating an array of zero length below.

  //

  // Note `updateIDTMetaData` is called in two places so check

  // `MaxNumPromotions` inside it.

  if (MaxNumPromotions == 0)

    return;

  uint32_t NumVals = 0;

  // OldSum is the existing total count in the value profile data.

  uint64_t OldSum = 0;

  std::unique_ptr<InstrProfValueData[]> ValueData =

      std::make_unique<InstrProfValueData[]>(MaxNumPromotions);

  bool Valid =

      getValueProfDataFromInst(Inst, IPVK_IndirectCallTarget, MaxNumPromotions,

                               ValueData.get(), NumVals, OldSum, true);

  DenseMap<uint64_t, uint64_t> ValueCountMap;

  if (Sum == 0) {

    assert((CallTargets.size() == 1 &&

            CallTargets[0].Count == NOMORE_ICP_MAGICNUM) &&

           "If sum is 0, assume only one element in CallTargets "

           "with count being NOMORE_ICP_MAGICNUM");

    // Initialize ValueCountMap with existing value profile data.

    if (Valid) {

      for (uint32_t I = 0; I < NumVals; I++)

        ValueCountMap[ValueData[I].Value] = ValueData[I].Count;

    }

    auto Pair =

        ValueCountMap.try_emplace(CallTargets[0].Value, CallTargets[0].Count);

    // If the target already exists in value profile, decrease the total

    // count OldSum and reset the target's count to NOMORE_ICP_MAGICNUM.

    if (!Pair.second) {

      OldSum -= Pair.first->second;

      Pair.first->second = NOMORE_ICP_MAGICNUM;

    }

    Sum = OldSum;

  } else {

    // Initialize ValueCountMap with existing NOMORE_ICP_MAGICNUM

    // counts in the value profile.

    if (Valid) {

      for (uint32_t I = 0; I < NumVals; I++) {

        if (ValueData[I].Count == NOMORE_ICP_MAGICNUM)

          ValueCountMap[ValueData[I].Value] = ValueData[I].Count;

      }

    }

    for (const auto &Data : CallTargets) {

      auto Pair = ValueCountMap.try_emplace(Data.Value, Data.Count);

      if (Pair.second)

        continue;

      // The target represented by Data.Value has already been promoted.

      // Keep the count as NOMORE_ICP_MAGICNUM in the profile and decrease

      // Sum by Data.Count.

      assert(Sum >= Data.Count && "Sum should never be less than Data.Count");

      Sum -= Data.Count;

    }

  }

  SmallVector<InstrProfValueData, 8> NewCallTargets;

  for (const auto &ValueCount : ValueCountMap) {

    NewCallTargets.emplace_back(

        InstrProfValueData{ValueCount.first, ValueCount.second});

  }

  llvm::sort(NewCallTargets,

             [](const InstrProfValueData &L, const InstrProfValueData &R) {

               if (L.Count != R.Count)

                 return L.Count > R.Count;

               return L.Value > R.Value;

             });

  uint32_t MaxMDCount =

      std::min(NewCallTargets.size(), static_cast<size_t>(MaxNumPromotions));

  annotateValueSite(*Inst.getParent()->getParent()->getParent(), Inst,

                    NewCallTargets, Sum, IPVK_IndirectCallTarget, MaxMDCount);

}

/// Attempt to promote indirect call and also inline the promoted call.

///

/// \param F  Caller function.

/// \param Candidate  ICP and inline candidate.

/// \param SumOrigin  Original sum of target counts for indirect call before

///                   promoting given candidate.

/// \param Sum        Prorated sum of remaining target counts for indirect call

///                   after promoting given candidate.

/// \param InlinedCallSite  Output vector for new call sites exposed after

/// inlining.

bool SampleProfileLoader::tryPromoteAndInlineCandidate(

    Function &F, InlineCandidate &Candidate, uint64_t SumOrigin, uint64_t &Sum,

    SmallVector<CallBase *, 8> *InlinedCallSite) {

  // Bail out early if sample-loader inliner is disabled.

  if (DisableSampleLoaderInlining)

    return false;

  // Bail out early if MaxNumPromotions is zero.

  // This prevents allocating an array of zero length in callees below.

  if (MaxNumPromotions == 0)

    return false;

  auto CalleeFunctionName = Candidate.CalleeSamples->getFunction();

  auto R = SymbolMap.find(CalleeFunctionName);

  if (R == SymbolMap.end() || !R->second)

    return false;

  auto &CI = *Candidate.CallInstr;

  if (!doesHistoryAllowICP(CI, R->second->getName()))

    return false;

  const char *Reason = "Callee function not available";

  // R->getValue() != &F is to prevent promoting a recursive call.

  // If it is a recursive call, we do not inline it as it could bloat

  // the code exponentially. There is way to better handle this, e.g.

  // clone the caller first, and inline the cloned caller if it is

  // recursive. As llvm does not inline recursive calls, we will

  // simply ignore it instead of handling it explicitly.

  if (!R->second->isDeclaration() && R->second->getSubprogram() &&

      R->second->hasFnAttribute("use-sample-profile") &&

      R->second != &F && isLegalToPromote(CI, R->second, &Reason)) {

    // For promoted target, set its value with NOMORE_ICP_MAGICNUM count

    // in the value profile metadata so the target won't be promoted again.

    SmallVector<InstrProfValueData, 1> SortedCallTargets = {InstrProfValueData{

        Function::getGUID(R->second->getName()), NOMORE_ICP_MAGICNUM}};

    updateIDTMetaData(CI, SortedCallTargets, 0);

    auto *DI = &pgo::promoteIndirectCall(

        CI, R->second, Candidate.CallsiteCount, Sum, false, ORE);

    if (DI) {

      Sum -= Candidate.CallsiteCount;

      // Do not prorate the indirect callsite distribution since the original

      // distribution will be used to scale down non-promoted profile target

      // counts later. By doing this we lose track of the real callsite count

      // for the leftover indirect callsite as a trade off for accurate call

      // target counts.

      // TODO: Ideally we would have two separate factors, one for call site