<commit_before>//===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//
//
//                      The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// 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/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/Pass.h"
#include "llvm/ProfileData/SampleProfReader.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorOr.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Transforms/InstCombine/InstCombine.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include <cctype>

using namespace llvm;
using namespace sampleprof;

#define DEBUG_TYPE "sample-profile"

// 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);
static cl::opt<unsigned> SampleProfileMaxPropagateIterations(
    "sample-profile-max-propagate-iterations", cl::init(100),
    cl::desc("Maximum number of iterations to go through when propagating "
             "sample block/edge weights through the CFG."));
static cl::opt<unsigned> SampleProfileRecordCoverage(
    "sample-profile-check-record-coverage", cl::init(0), cl::value_desc("N"),
    cl::desc("Emit a warning if less than N% of records in the input profile "
             "are matched to the IR."));
static cl::opt<unsigned> SampleProfileSampleCoverage(
    "sample-profile-check-sample-coverage", cl::init(0), cl::value_desc("N"),
    cl::desc("Emit a warning if less than N% of samples in the input profile "
             "are matched to the IR."));
static cl::opt<double> SampleProfileHotThreshold(
    "sample-profile-inline-hot-threshold", cl::init(0.1), cl::value_desc("N"),
    cl::desc("Inlined functions that account for more than N% of all samples "
             "collected in the parent function, will be inlined again."));
static cl::opt<double> SampleProfileGlobalHotThreshold(
    "sample-profile-global-hot-threshold", cl::init(30), cl::value_desc("N"),
    cl::desc("Top-level functions that account for more than N% of all samples "
             "collected in the profile, will be marked as hot for the inliner "
             "to consider."));
static cl::opt<double> SampleProfileGlobalColdThreshold(
    "sample-profile-global-cold-threshold", cl::init(0.5), cl::value_desc("N"),
    cl::desc("Top-level functions that account for less than N% of all samples "
             "collected in the profile, will be marked as cold for the inliner "
             "to consider."));

namespace {
typedef DenseMap<const BasicBlock *, uint64_t> BlockWeightMap;
typedef DenseMap<const BasicBlock *, const BasicBlock *> EquivalenceClassMap;
typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
typedef DenseMap<Edge, uint64_t> EdgeWeightMap;
typedef DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>
    BlockEdgeMap;

/// \brief 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 : public ModulePass {
public:
  // Class identification, replacement for typeinfo
  static char ID;

  SampleProfileLoader(StringRef Name = SampleProfileFile)
      : ModulePass(ID), DT(nullptr), PDT(nullptr), LI(nullptr), Reader(),
        Samples(nullptr), Filename(Name), ProfileIsValid(false),
        TotalCollectedSamples(0) {
    initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry());
  }

  bool doInitialization(Module &M) override;

  void dump() { Reader->dump(); }

  const char *getPassName() const override { return "Sample profile pass"; }

  bool runOnModule(Module &M) override;

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequired<InstructionCombiningPass>();
  }

protected:
  bool runOnFunction(Function &F);
  unsigned getFunctionLoc(Function &F);
  bool emitAnnotations(Function &F);
  ErrorOr<uint64_t> getInstWeight(const Instruction &I) const;
  ErrorOr<uint64_t> getBlockWeight(const BasicBlock *BB) const;
  const FunctionSamples *findCalleeFunctionSamples(const CallInst &I) const;
  const FunctionSamples *findFunctionSamples(const Instruction &I) const;
  bool inlineHotFunctions(Function &F);
  bool emitInlineHints(Function &F);
  void printEdgeWeight(raw_ostream &OS, Edge E);
  void printBlockWeight(raw_ostream &OS, const BasicBlock *BB) const;
  void printBlockEquivalence(raw_ostream &OS, const BasicBlock *BB);
  bool computeBlockWeights(Function &F);
  void findEquivalenceClasses(Function &F);
  void findEquivalencesFor(BasicBlock *BB1, ArrayRef<BasicBlock *> Descendants,
                           DominatorTreeBase<BasicBlock> *DomTree);
  void propagateWeights(Function &F);
  uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
  void buildEdges(Function &F);
  bool propagateThroughEdges(Function &F);
  void computeDominanceAndLoopInfo(Function &F);
  unsigned getOffset(unsigned L, unsigned H) const;
  void clearFunctionData();

  /// \brief Map basic blocks to their computed weights.
  ///
  /// The weight of a basic block is defined to be the maximum
  /// of all the instruction weights in that block.
  BlockWeightMap BlockWeights;

  /// \brief Map edges to their computed weights.
  ///
  /// Edge weights are computed by propagating basic block weights in
  /// SampleProfile::propagateWeights.
  EdgeWeightMap EdgeWeights;

  /// \brief Set of visited blocks during propagation.
  SmallPtrSet<const BasicBlock *, 32> VisitedBlocks;

  /// \brief Set of visited edges during propagation.
  SmallSet<Edge, 32> VisitedEdges;

  /// \brief Equivalence classes for block weights.
  ///
  /// Two blocks BB1 and BB2 are in the same equivalence class if they
  /// dominate and post-dominate each other, and they are in the same loop
  /// nest. When this happens, the two blocks are guaranteed to execute
  /// the same number of times.
  EquivalenceClassMap EquivalenceClass;

  /// \brief Dominance, post-dominance and loop information.
  std::unique_ptr<DominatorTree> DT;
  std::unique_ptr<DominatorTreeBase<BasicBlock>> PDT;
  std::unique_ptr<LoopInfo> LI;

  /// \brief Predecessors for each basic block in the CFG.
  BlockEdgeMap Predecessors;

  /// \brief Successors for each basic block in the CFG.
  BlockEdgeMap Successors;

  /// \brief Profile reader object.
  std::unique_ptr<SampleProfileReader> Reader;

  /// \brief Samples collected for the body of this function.
  FunctionSamples *Samples;

  /// \brief Name of the profile file to load.
  StringRef Filename;

  /// \brief Flag indicating whether the profile input loaded successfully.
  bool ProfileIsValid;

  /// \brief 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;
};

class SampleCoverageTracker {
public:
  SampleCoverageTracker() : SampleCoverage(), TotalUsedSamples(0) {}

  bool markSamplesUsed(const FunctionSamples *FS, uint32_t LineOffset,
                       uint32_t Discriminator, uint64_t Samples);
  unsigned computeCoverage(unsigned Used, unsigned Total) const;
  unsigned countUsedRecords(const FunctionSamples *FS) const;
  unsigned countBodyRecords(const FunctionSamples *FS) const;
  uint64_t getTotalUsedSamples() const { return TotalUsedSamples; }
  uint64_t countBodySamples(const FunctionSamples *FS) const;
  void clear() {
    SampleCoverage.clear();
    TotalUsedSamples = 0;
  }

private:
  typedef std::map<LineLocation, unsigned> BodySampleCoverageMap;
  typedef DenseMap<const FunctionSamples *, BodySampleCoverageMap>
      FunctionSamplesCoverageMap;

  /// Coverage map for sampling records.
  ///
  /// This map keeps a record of sampling records that have been matched to
  /// an IR instruction. This is used to detect some form of staleness in
  /// profiles (see flag -sample-profile-check-coverage).
  ///
  /// Each entry in the map corresponds to a FunctionSamples instance.  This is
  /// another map that counts how many times the sample record at the
  /// given location has been used.
  FunctionSamplesCoverageMap SampleCoverage;

  /// Number of samples used from the profile.
  ///
  /// When a sampling record is used for the first time, the samples from
  /// that record are added to this accumulator.  Coverage is later computed
  /// based on the total number of samples available in this function and
  /// its callsites.
  ///
  /// Note that this accumulator tracks samples used from a single function
  /// and all the inlined callsites. Strictly, we should have a map of counters
  /// keyed by FunctionSamples pointers, but these stats are cleared after
  /// every function, so we just need to keep a single counter.
  uint64_t TotalUsedSamples;
};

SampleCoverageTracker CoverageTracker;

/// Return true if the given callsite is hot wrt to its caller.
///
/// Functions that were inlined in the original binary will be represented
/// in the inline stack in the sample profile. If the profile shows that
/// the original inline decision was "good" (i.e., the callsite is executed
/// frequently), then we will recreate the inline decision and apply the
/// profile from the inlined callsite.
///
/// To decide whether an inlined callsite is hot, we compute the fraction
/// of samples used by the callsite with respect to the total number of samples
/// collected in the caller.
///
/// If that fraction is larger than the default given by
/// SampleProfileHotThreshold, the callsite will be inlined again.
bool callsiteIsHot(const FunctionSamples *CallerFS,
                   const FunctionSamples *CallsiteFS) {
  if (!CallsiteFS)
    return false; // The callsite was not inlined in the original binary.

  uint64_t ParentTotalSamples = CallerFS->getTotalSamples();
  if (ParentTotalSamples == 0)
    return false; // Avoid division by zero.

  uint64_t CallsiteTotalSamples = CallsiteFS->getTotalSamples();
  if (CallsiteTotalSamples == 0)
    return false; // Callsite is trivially cold.

  double PercentSamples =
      (double)CallsiteTotalSamples / (double)ParentTotalSamples * 100.0;
  return PercentSamples >= SampleProfileHotThreshold;
}
}

/// Mark as used the sample record for the given function samples at
/// (LineOffset, Discriminator).
///
/// \returns true if this is the first time we mark the given record.
bool SampleCoverageTracker::markSamplesUsed(const FunctionSamples *FS,
                                            uint32_t LineOffset,
                                            uint32_t Discriminator,
                                            uint64_t Samples) {
  LineLocation Loc(LineOffset, Discriminator);
  unsigned &Count = SampleCoverage[FS][Loc];
  bool FirstTime = (++Count == 1);
  if (FirstTime)
    TotalUsedSamples += Samples;
  return FirstTime;
}

/// Return the number of sample records that were applied from this profile.
///
/// This count does not include records from cold inlined callsites.
unsigned
SampleCoverageTracker::countUsedRecords(const FunctionSamples *FS) const {
  auto I = SampleCoverage.find(FS);

  // The size of the coverage map for FS represents the number of records
  // that were marked used at least once.
  unsigned Count = (I != SampleCoverage.end()) ? I->second.size() : 0;

  // If there are inlined callsites in this function, count the samples found
  // in the respective bodies. However, do not bother counting callees with 0
  // total samples, these are callees that were never invoked at runtime.
  for (const auto &I : FS->getCallsiteSamples()) {
    const FunctionSamples *CalleeSamples = &I.second;
    if (callsiteIsHot(FS, CalleeSamples))
      Count += countUsedRecords(CalleeSamples);
  }

  return Count;
}

/// Return the number of sample records in the body of this profile.
///
/// This count does not include records from cold inlined callsites.
unsigned
SampleCoverageTracker::countBodyRecords(const FunctionSamples *FS) const {
  unsigned Count = FS->getBodySamples().size();

  // Only count records in hot callsites.
  for (const auto &I : FS->getCallsiteSamples()) {
    const FunctionSamples *CalleeSamples = &I.second;
    if (callsiteIsHot(FS, CalleeSamples))
      Count += countBodyRecords(CalleeSamples);
  }

  return Count;
}

/// Return the number of samples collected in the body of this profile.
///
/// This count does not include samples from cold inlined callsites.
uint64_t
SampleCoverageTracker::countBodySamples(const FunctionSamples *FS) const {
  uint64_t Total = 0;
  for (const auto &I : FS->getBodySamples())
    Total += I.second.getSamples();

  // Only count samples in hot callsites.
  for (const auto &I : FS->getCallsiteSamples()) {
    const FunctionSamples *CalleeSamples = &I.second;
    if (callsiteIsHot(FS, CalleeSamples))
      Total += countBodySamples(CalleeSamples);
  }

  return Total;
}

/// Return the fraction of sample records used in this profile.
///
/// The returned value is an unsigned integer in the range 0-100 indicating
/// the percentage of sample records that were used while applying this
/// profile to the associated function.
unsigned SampleCoverageTracker::computeCoverage(unsigned Used,
                                                unsigned Total) const {
  assert(Used <= Total &&
         "number of used records cannot exceed the total number of records");
  return Total > 0 ? Used * 100 / Total : 100;
}

/// Clear all the per-function data used to load samples and propagate weights.
void SampleProfileLoader::clearFunctionData() {
  BlockWeights.clear();
  EdgeWeights.clear();
  VisitedBlocks.clear();
  VisitedEdges.clear();
  EquivalenceClass.clear();
  DT = nullptr;
  PDT = nullptr;
  LI = nullptr;
  Predecessors.clear();
  Successors.clear();
  CoverageTracker.clear();
}

/// \brief Returns the offset of lineno \p L to head_lineno \p H
///
/// \param L  Lineno
/// \param H  Header lineno of the function
///
/// \returns offset to the header lineno. 16 bits are used to represent offset.
/// We assume that a single function will not exceed 65535 LOC.
unsigned SampleProfileLoader::getOffset(unsigned L, unsigned H) const {
  return (L - H) & 0xffff;
}

/// \brief Print the weight of edge \p E on stream \p OS.
///
/// \param OS  Stream to emit the output to.
/// \param E  Edge to print.
void SampleProfileLoader::printEdgeWeight(raw_ostream &OS, Edge E) {
  OS << "weight[" << E.first->getName() << "->" << E.second->getName()
     << "]: " << EdgeWeights[E] << "\n";
}

/// \brief Print the equivalence class of block \p BB on stream \p OS.
///
/// \param OS  Stream to emit the output to.
/// \param BB  Block to print.
void SampleProfileLoader::printBlockEquivalence(raw_ostream &OS,
                                                const BasicBlock *BB) {
  const BasicBlock *Equiv = EquivalenceClass[BB];
  OS << "equivalence[" << BB->getName()
     << "]: " << ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE") << "\n";
}

/// \brief Print the weight of block \p BB on stream \p OS.
///
/// \param OS  Stream to emit the output to.
/// \param BB  Block to print.
void SampleProfileLoader::printBlockWeight(raw_ostream &OS,
                                           const BasicBlock *BB) const {
  const auto &I = BlockWeights.find(BB);
  uint64_t W = (I == BlockWeights.end() ? 0 : I->second);
  OS << "weight[" << BB->getName() << "]: " << W << "\n";
}

/// \brief Get the weight for an instruction.
///
/// The "weight" of an instruction \p Inst is the number of samples
/// collected on that instruction at runtime. To retrieve it, we
/// need to compute the line number of \p Inst relative to the start of its
/// function. We use HeaderLineno to compute the offset. We then
/// look up the samples collected for \p Inst using BodySamples.
///
/// \param Inst Instruction to query.
///
/// \returns the weight of \p Inst.
ErrorOr<uint64_t>
SampleProfileLoader::getInstWeight(const Instruction &Inst) const {
  DebugLoc DLoc = Inst.getDebugLoc();
  if (!DLoc)
    return std::error_code();

  const FunctionSamples *FS = findFunctionSamples(Inst);
  if (!FS)
    return std::error_code();

  const DILocation *DIL = DLoc;
  unsigned Lineno = DLoc.getLine();
  unsigned HeaderLineno = DIL->getScope()->getSubprogram()->getLine();

  uint32_t LineOffset = getOffset(Lineno, HeaderLineno);
  uint32_t Discriminator = DIL->getDiscriminator();
  ErrorOr<uint64_t> R = FS->findSamplesAt(LineOffset, Discriminator);
  if (R) {
    bool FirstMark =
        CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());
    if (FirstMark) {
      const Function *F = Inst.getParent()->getParent();
      LLVMContext &Ctx = F->getContext();
      emitOptimizationRemark(
          Ctx, DEBUG_TYPE, *F, DLoc,
          Twine("Applied ") + Twine(*R) + " samples from profile (offset: " +
              Twine(LineOffset) +
              ((Discriminator) ? Twine(".") + Twine(Discriminator) : "") + ")");
    }
    DEBUG(dbgs() << "    " << Lineno << "." << DIL->getDiscriminator() << ":"
                 << Inst << " (line offset: " << Lineno - HeaderLineno << "."
                 << DIL->getDiscriminator() << " - weight: " << R.get()
                 << ")\n");
  }
  return R;<commit_msg>Refine instruction weight annotation algorithm for sample profiler.<commit_after>//===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//
//
//                      The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// 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/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/Pass.h"
#include "llvm/ProfileData/SampleProfReader.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorOr.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Transforms/InstCombine/InstCombine.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include <cctype>

using namespace llvm;
using namespace sampleprof;

#define DEBUG_TYPE "sample-profile"

// 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);
static cl::opt<unsigned> SampleProfileMaxPropagateIterations(
    "sample-profile-max-propagate-iterations", cl::init(100),
    cl::desc("Maximum number of iterations to go through when propagating "
             "sample block/edge weights through the CFG."));
static cl::opt<unsigned> SampleProfileRecordCoverage(
    "sample-profile-check-record-coverage", cl::init(0), cl::value_desc("N"),
    cl::desc("Emit a warning if less than N% of records in the input profile "
             "are matched to the IR."));
static cl::opt<unsigned> SampleProfileSampleCoverage(
    "sample-profile-check-sample-coverage", cl::init(0), cl::value_desc("N"),
    cl::desc("Emit a warning if less than N% of samples in the input profile "
             "are matched to the IR."));
static cl::opt<double> SampleProfileHotThreshold(
    "sample-profile-inline-hot-threshold", cl::init(0.1), cl::value_desc("N"),
    cl::desc("Inlined functions that account for more than N% of all samples "
             "collected in the parent function, will be inlined again."));
static cl::opt<double> SampleProfileGlobalHotThreshold(
    "sample-profile-global-hot-threshold", cl::init(30), cl::value_desc("N"),
    cl::desc("Top-level functions that account for more than N% of all samples "
             "collected in the profile, will be marked as hot for the inliner "
             "to consider."));
static cl::opt<double> SampleProfileGlobalColdThreshold(
    "sample-profile-global-cold-threshold", cl::init(0.5), cl::value_desc("N"),
    cl::desc("Top-level functions that account for less than N% of all samples "
             "collected in the profile, will be marked as cold for the inliner "
             "to consider."));

namespace {
typedef DenseMap<const BasicBlock *, uint64_t> BlockWeightMap;
typedef DenseMap<const BasicBlock *, const BasicBlock *> EquivalenceClassMap;
typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
typedef DenseMap<Edge, uint64_t> EdgeWeightMap;
typedef DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>
    BlockEdgeMap;

/// \brief 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 : public ModulePass {
public:
  // Class identification, replacement for typeinfo
  static char ID;

  SampleProfileLoader(StringRef Name = SampleProfileFile)
      : ModulePass(ID), DT(nullptr), PDT(nullptr), LI(nullptr), Reader(),
        Samples(nullptr), Filename(Name), ProfileIsValid(false),
        TotalCollectedSamples(0) {
    initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry());
  }

  bool doInitialization(Module &M) override;

  void dump() { Reader->dump(); }

  const char *getPassName() const override { return "Sample profile pass"; }

  bool runOnModule(Module &M) override;

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequired<InstructionCombiningPass>();
  }

protected:
  bool runOnFunction(Function &F);
  unsigned getFunctionLoc(Function &F);
  bool emitAnnotations(Function &F);
  ErrorOr<uint64_t> getInstWeight(const Instruction &I) const;
  ErrorOr<uint64_t> getBlockWeight(const BasicBlock *BB) const;
  const FunctionSamples *findCalleeFunctionSamples(const CallInst &I) const;
  const FunctionSamples *findFunctionSamples(const Instruction &I) const;
  bool inlineHotFunctions(Function &F);
  bool emitInlineHints(Function &F);
  void printEdgeWeight(raw_ostream &OS, Edge E);
  void printBlockWeight(raw_ostream &OS, const BasicBlock *BB) const;
  void printBlockEquivalence(raw_ostream &OS, const BasicBlock *BB);
  bool computeBlockWeights(Function &F);
  void findEquivalenceClasses(Function &F);
  void findEquivalencesFor(BasicBlock *BB1, ArrayRef<BasicBlock *> Descendants,
                           DominatorTreeBase<BasicBlock> *DomTree);
  void propagateWeights(Function &F);
  uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
  void buildEdges(Function &F);
  bool propagateThroughEdges(Function &F);
  void computeDominanceAndLoopInfo(Function &F);
  unsigned getOffset(unsigned L, unsigned H) const;
  void clearFunctionData();

  /// \brief Map basic blocks to their computed weights.
  ///
  /// The weight of a basic block is defined to be the maximum
  /// of all the instruction weights in that block.
  BlockWeightMap BlockWeights;

  /// \brief Map edges to their computed weights.
  ///
  /// Edge weights are computed by propagating basic block weights in
  /// SampleProfile::propagateWeights.
  EdgeWeightMap EdgeWeights;

  /// \brief Set of visited blocks during propagation.
  SmallPtrSet<const BasicBlock *, 32> VisitedBlocks;

  /// \brief Set of visited edges during propagation.
  SmallSet<Edge, 32> VisitedEdges;

  /// \brief Equivalence classes for block weights.
  ///
  /// Two blocks BB1 and BB2 are in the same equivalence class if they
  /// dominate and post-dominate each other, and they are in the same loop
  /// nest. When this happens, the two blocks are guaranteed to execute
  /// the same number of times.
  EquivalenceClassMap EquivalenceClass;

  /// \brief Dominance, post-dominance and loop information.
  std::unique_ptr<DominatorTree> DT;
  std::unique_ptr<DominatorTreeBase<BasicBlock>> PDT;
  std::unique_ptr<LoopInfo> LI;

  /// \brief Predecessors for each basic block in the CFG.
  BlockEdgeMap Predecessors;

  /// \brief Successors for each basic block in the CFG.
  BlockEdgeMap Successors;

  /// \brief Profile reader object.
  std::unique_ptr<SampleProfileReader> Reader;

  /// \brief Samples collected for the body of this function.
  FunctionSamples *Samples;

  /// \brief Name of the profile file to load.
  StringRef Filename;

  /// \brief Flag indicating whether the profile input loaded successfully.
  bool ProfileIsValid;

  /// \brief 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;
};

class SampleCoverageTracker {
public:
  SampleCoverageTracker() : SampleCoverage(), TotalUsedSamples(0) {}

  bool markSamplesUsed(const FunctionSamples *FS, uint32_t LineOffset,
                       uint32_t Discriminator, uint64_t Samples);
  unsigned computeCoverage(unsigned Used, unsigned Total) const;
  unsigned countUsedRecords(const FunctionSamples *FS) const;
  unsigned countBodyRecords(const FunctionSamples *FS) const;
  uint64_t getTotalUsedSamples() const { return TotalUsedSamples; }
  uint64_t countBodySamples(const FunctionSamples *FS) const;
  void clear() {
    SampleCoverage.clear();
    TotalUsedSamples = 0;
  }

private:
  typedef std::map<LineLocation, unsigned> BodySampleCoverageMap;
  typedef DenseMap<const FunctionSamples *, BodySampleCoverageMap>
      FunctionSamplesCoverageMap;

  /// Coverage map for sampling records.
  ///
  /// This map keeps a record of sampling records that have been matched to
  /// an IR instruction. This is used to detect some form of staleness in
  /// profiles (see flag -sample-profile-check-coverage).
  ///
  /// Each entry in the map corresponds to a FunctionSamples instance.  This is
  /// another map that counts how many times the sample record at the
  /// given location has been used.
  FunctionSamplesCoverageMap SampleCoverage;

  /// Number of samples used from the profile.
  ///
  /// When a sampling record is used for the first time, the samples from
  /// that record are added to this accumulator.  Coverage is later computed
  /// based on the total number of samples available in this function and
  /// its callsites.
  ///
  /// Note that this accumulator tracks samples used from a single function
  /// and all the inlined callsites. Strictly, we should have a map of counters
  /// keyed by FunctionSamples pointers, but these stats are cleared after
  /// every function, so we just need to keep a single counter.
  uint64_t TotalUsedSamples;
};

SampleCoverageTracker CoverageTracker;

/// Return true if the given callsite is hot wrt to its caller.
///
/// Functions that were inlined in the original binary will be represented
/// in the inline stack in the sample profile. If the profile shows that
/// the original inline decision was "good" (i.e., the callsite is executed
/// frequently), then we will recreate the inline decision and apply the
/// profile from the inlined callsite.
///
/// To decide whether an inlined callsite is hot, we compute the fraction
/// of samples used by the callsite with respect to the total number of samples
/// collected in the caller.
///
/// If that fraction is larger than the default given by
/// SampleProfileHotThreshold, the callsite will be inlined again.
bool callsiteIsHot(const FunctionSamples *CallerFS,
                   const FunctionSamples *CallsiteFS) {
  if (!CallsiteFS)
    return false; // The callsite was not inlined in the original binary.

  uint64_t ParentTotalSamples = CallerFS->getTotalSamples();
  if (ParentTotalSamples == 0)
    return false; // Avoid division by zero.

  uint64_t CallsiteTotalSamples = CallsiteFS->getTotalSamples();
  if (CallsiteTotalSamples == 0)
    return false; // Callsite is trivially cold.

  double PercentSamples =
      (double)CallsiteTotalSamples / (double)ParentTotalSamples * 100.0;
  return PercentSamples >= SampleProfileHotThreshold;
}
}

/// Mark as used the sample record for the given function samples at
/// (LineOffset, Discriminator).
///
/// \returns true if this is the first time we mark the given record.
bool SampleCoverageTracker::markSamplesUsed(const FunctionSamples *FS,
                                            uint32_t LineOffset,
                                            uint32_t Discriminator,
                                            uint64_t Samples) {
  LineLocation Loc(LineOffset, Discriminator);
  unsigned &Count = SampleCoverage[FS][Loc];
  bool FirstTime = (++Count == 1);
  if (FirstTime)
    TotalUsedSamples += Samples;
  return FirstTime;
}

/// Return the number of sample records that were applied from this profile.
///
/// This count does not include records from cold inlined callsites.
unsigned
SampleCoverageTracker::countUsedRecords(const FunctionSamples *FS) const {
  auto I = SampleCoverage.find(FS);

  // The size of the coverage map for FS represents the number of records
  // that were marked used at least once.
  unsigned Count = (I != SampleCoverage.end()) ? I->second.size() : 0;

  // If there are inlined callsites in this function, count the samples found
  // in the respective bodies. However, do not bother counting callees with 0
  // total samples, these are callees that were never invoked at runtime.
  for (const auto &I : FS->getCallsiteSamples()) {
    const FunctionSamples *CalleeSamples = &I.second;
    if (callsiteIsHot(FS, CalleeSamples))
      Count += countUsedRecords(CalleeSamples);
  }

  return Count;
}

/// Return the number of sample records in the body of this profile.
///
/// This count does not include records from cold inlined callsites.
unsigned
SampleCoverageTracker::countBodyRecords(const FunctionSamples *FS) const {
  unsigned Count = FS->getBodySamples().size();

  // Only count records in hot callsites.
  for (const auto &I : FS->getCallsiteSamples()) {
    const FunctionSamples *CalleeSamples = &I.second;
    if (callsiteIsHot(FS, CalleeSamples))
      Count += countBodyRecords(CalleeSamples);
  }

  return Count;
}

/// Return the number of samples collected in the body of this profile.
///
/// This count does not include samples from cold inlined callsites.
uint64_t
SampleCoverageTracker::countBodySamples(const FunctionSamples *FS) const {
  uint64_t Total = 0;
  for (const auto &I : FS->getBodySamples())
    Total += I.second.getSamples();

  // Only count samples in hot callsites.
  for (const auto &I : FS->getCallsiteSamples()) {
    const FunctionSamples *CalleeSamples = &I.second;
    if (callsiteIsHot(FS, CalleeSamples))
      Total += countBodySamples(CalleeSamples);
  }

  return Total;
}

/// Return the fraction of sample records used in this profile.
///
/// The returned value is an unsigned integer in the range 0-100 indicating
/// the percentage of sample records that were used while applying this
/// profile to the associated function.
unsigned SampleCoverageTracker::computeCoverage(unsigned Used,
                                                unsigned Total) const {
  assert(Used <= Total &&
         "number of used records cannot exceed the total number of records");
  return Total > 0 ? Used * 100 / Total : 100;
}

/// Clear all the per-function data used to load samples and propagate weights.
void SampleProfileLoader::clearFunctionData() {
  BlockWeights.clear();
  EdgeWeights.clear();
  VisitedBlocks.clear();
  VisitedEdges.clear();
  EquivalenceClass.clear();
  DT = nullptr;
  PDT = nullptr;
  LI = nullptr;
  Predecessors.clear();
  Successors.clear();
  CoverageTracker.clear();
}

/// \brief Returns the offset of lineno \p L to head_lineno \p H
///
/// \param L  Lineno
/// \param H  Header lineno of the function
///
/// \returns offset to the header lineno. 16 bits are used to represent offset.
/// We assume that a single function will not exceed 65535 LOC.
unsigned SampleProfileLoader::getOffset(unsigned L, unsigned H) const {
  return (L - H) & 0xffff;
}

/// \brief Print the weight of edge \p E on stream \p OS.
///
/// \param OS  Stream to emit the output to.
/// \param E  Edge to print.
void SampleProfileLoader::printEdgeWeight(raw_ostream &OS, Edge E) {
  OS << "weight[" << E.first->getName() << "->" << E.second->getName()
     << "]: " << EdgeWeights[E] << "\n";
}

/// \brief Print the equivalence class of block \p BB on stream \p OS.
///
/// \param OS  Stream to emit the output to.
/// \param BB  Block to print.
void SampleProfileLoader::printBlockEquivalence(raw_ostream &OS,
                                                const BasicBlock *BB) {
  const BasicBlock *Equiv = EquivalenceClass[BB];
  OS << "equivalence[" << BB->getName()
     << "]: " << ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE") << "\n";
}

/// \brief Print the weight of block \p BB on stream \p OS.
///
/// \param OS  Stream to emit the output to.
/// \param BB  Block to print.
void SampleProfileLoader::printBlockWeight(raw_ostream &OS,
                                           const BasicBlock *BB) const {
  const auto &I = BlockWeights.find(BB);
  uint64_t W = (I == BlockWeights.end() ? 0 : I->second);
  OS << "weight[" << BB->getName() << "]: " << W << "\n";
}

/// \brief Get the weight for an instruction.
///
/// The "weight" of an instruction \p Inst is the number of samples
/// collected on that instruction at runtime. To retrieve it, we
/// need to compute the line number of \p Inst relative to the start of its
/// function. We use HeaderLineno to compute the offset. We then
/// look up the samples collected for \p Inst using BodySamples.
///
/// \param Inst Instruction to query.
///
/// \returns the weight of \p Inst.
ErrorOr<uint64_t>
SampleProfileLoader::getInstWeight(const Instruction &Inst) const {
  DebugLoc DLoc = Inst.getDebugLoc();
  if (!DLoc)
    return std::error_code();

  const FunctionSamples *FS = findFunctionSamples(Inst);
  if (!FS)
    return std::error_code();

  // Ignore all dbg_value intrinsics.
  const IntrinsicInst *II = dyn_cast<IntrinsicInst>(&Inst);
  if (II && II->getIntrinsicID() == Intrinsic::dbg_value)
    return std::error_code();

  const DILocation *DIL = DLoc;
  unsigned Lineno = DLoc.getLine();
  unsigned HeaderLineno = DIL->getScope()->getSubprogram()->getLine();

  uint32_t LineOffset = getOffset(Lineno, HeaderLineno);
  uint32_t Discriminator = DIL->getDiscriminator();
  ErrorOr<uint64_t> R = FS->findSamplesAt(LineOffset, Discriminator);
  if (R) {
    bool FirstMark =
        CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());
    if (FirstMark) {
      const Function *F = Inst.getParent()->getParent();
      LLVMContext &Ctx = F->getContext();
      emitOptimizationRemark(
          Ctx, DEBUG_TYPE, *F, DLoc,
          Twine("Applied ") + Twine(*R) + " samples from profile (offset: " +
              Twine(LineOffset) +
              ((Discriminator) ? Twine(".") + Twine(Discriminator) : "") + ")");
    }
    DEBUG(dbgs() << "    " << Lineno << "." << DIL->getDiscriminator() << ":"
                 << Inst << " (line offset: " << Lineno - HeaderLineno << "."
                 << DIL->getDiscriminator() << " - weight: " << R.get()
                 << ")\n");
  } else {
    // If a call instruction is inlined in profile, but not inlined here,
    // it means that the inlined callsite has no sample, thus the call
    // instruction should have 0 count.
    const CallInst *CI = dyn_cast<CallInst>(&Inst);
    if (CI && findCalleeFunctionSamples(*CI))
      R = 0;
  }
  return R;
{'fraction_non_alphanumeric': 0.11756746207291369, 'fraction_numerical': 0.005256446954123188, 'mean_word_length': 3.3145840350286293, 'pattern_counts': {'":': 2, '<': 187, '<?xml version=': 0, '>': 120, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '349174', 'n_tokens_mistral': 11126, 'n_tokens_neox': 10586, 'n_words': 3833}