Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

////===- SampleProfileLoadBaseImpl.h - Profile loader base impl --*- C++-*-===//

//

// 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

//

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

//

/// \file

/// This file provides the interface for the sampled PGO profile loader base

/// implementation.

//

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

#ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H

#define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/DenseSet.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/SmallSet.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/Analysis/LoopInfo.h"

#include "llvm/Analysis/OptimizationRemarkEmitter.h"

#include "llvm/Analysis/PostDominators.h"

#include "llvm/IR/BasicBlock.h"

#include "llvm/IR/CFG.h"

#include "llvm/IR/DebugInfoMetadata.h"

#include "llvm/IR/DebugLoc.h"

#include "llvm/IR/Dominators.h"

#include "llvm/IR/Function.h"

#include "llvm/IR/Instruction.h"

#include "llvm/IR/Instructions.h"

#include "llvm/IR/Module.h"

#include "llvm/ProfileData/SampleProf.h"

#include "llvm/ProfileData/SampleProfReader.h"

#include "llvm/Support/CommandLine.h"

#include "llvm/Support/GenericDomTree.h"

#include "llvm/Support/raw_ostream.h"

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

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

namespace llvm {

using namespace sampleprof;

using namespace sampleprofutil;

using ProfileCount = Function::ProfileCount;

#define DEBUG_TYPE "sample-profile-impl"

namespace afdo_detail {

template <typename BlockT> struct IRTraits;

template <> struct IRTraits<BasicBlock> {

  using InstructionT = Instruction;

  using BasicBlockT = BasicBlock;

  using FunctionT = Function;

  using BlockFrequencyInfoT = BlockFrequencyInfo;

  using LoopT = Loop;

  using LoopInfoPtrT = std::unique_ptr<LoopInfo>;

  using DominatorTreePtrT = std::unique_ptr<DominatorTree>;

  using PostDominatorTreeT = PostDominatorTree;

  using PostDominatorTreePtrT = std::unique_ptr<PostDominatorTree>;

  using OptRemarkEmitterT = OptimizationRemarkEmitter;

  using OptRemarkAnalysisT = OptimizationRemarkAnalysis;

  using PredRangeT = pred_range;

  using SuccRangeT = succ_range;

  static Function &getFunction(Function &F) { return F; }

  static const BasicBlock *getEntryBB(const Function *F) {

    return &F->getEntryBlock();

  }

  static pred_range getPredecessors(BasicBlock *BB) { return predecessors(BB); }

  static succ_range getSuccessors(BasicBlock *BB) { return successors(BB); }

};

} // end namespace afdo_detail

extern cl::opt<bool> SampleProfileUseProfi;

template <typename BT> class SampleProfileLoaderBaseImpl {

public:

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

      : Filename(Name), RemappingFilename(RemapName) {}

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

  using InstructionT = typename afdo_detail::IRTraits<BT>::InstructionT;

  using BasicBlockT = typename afdo_detail::IRTraits<BT>::BasicBlockT;

  using BlockFrequencyInfoT =

      typename afdo_detail::IRTraits<BT>::BlockFrequencyInfoT;

  using FunctionT = typename afdo_detail::IRTraits<BT>::FunctionT;

  using LoopT = typename afdo_detail::IRTraits<BT>::LoopT;

  using LoopInfoPtrT = typename afdo_detail::IRTraits<BT>::LoopInfoPtrT;

  using DominatorTreePtrT =

      typename afdo_detail::IRTraits<BT>::DominatorTreePtrT;

  using PostDominatorTreePtrT =

      typename afdo_detail::IRTraits<BT>::PostDominatorTreePtrT;

  using PostDominatorTreeT =

      typename afdo_detail::IRTraits<BT>::PostDominatorTreeT;

  using OptRemarkEmitterT =

      typename afdo_detail::IRTraits<BT>::OptRemarkEmitterT;

  using OptRemarkAnalysisT =

      typename afdo_detail::IRTraits<BT>::OptRemarkAnalysisT;

  using PredRangeT = typename afdo_detail::IRTraits<BT>::PredRangeT;

  using SuccRangeT = typename afdo_detail::IRTraits<BT>::SuccRangeT;

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

  using EquivalenceClassMap =

      DenseMap<const BasicBlockT *, const BasicBlockT *>;

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

  using EdgeWeightMap = DenseMap<Edge, uint64_t>;

  using BlockEdgeMap =

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

protected:

  ~SampleProfileLoaderBaseImpl() = default;

  friend class SampleCoverageTracker;

  Function &getFunction(FunctionT &F) {

    return afdo_detail::IRTraits<BT>::getFunction(F);

  }

  const BasicBlockT *getEntryBB(const FunctionT *F) {

    return afdo_detail::IRTraits<BT>::getEntryBB(F);

  }

  PredRangeT getPredecessors(BasicBlockT *BB) {

    return afdo_detail::IRTraits<BT>::getPredecessors(BB);

  }

  SuccRangeT getSuccessors(BasicBlockT *BB) {

    return afdo_detail::IRTraits<BT>::getSuccessors(BB);

  }

  unsigned getFunctionLoc(FunctionT &Func);

  virtual ErrorOr<uint64_t> getInstWeight(const InstructionT &Inst);

  ErrorOr<uint64_t> getInstWeightImpl(const InstructionT &Inst);

  ErrorOr<uint64_t> getBlockWeight(const BasicBlockT *BB);

  mutable DenseMap<const DILocation *, const FunctionSamples *>

      DILocation2SampleMap;

  virtual const FunctionSamples *

  findFunctionSamples(const InstructionT &I) const;

  void printEdgeWeight(raw_ostream &OS, Edge E);

  void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const;

  void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB);

  bool computeBlockWeights(FunctionT &F);

  void findEquivalenceClasses(FunctionT &F);

  void findEquivalencesFor(BasicBlockT *BB1,

                           ArrayRef<BasicBlockT *> Descendants,

                           PostDominatorTreeT *DomTree);

  void propagateWeights(FunctionT &F);

  void applyProfi(FunctionT &F, BlockEdgeMap &Successors,

                  BlockWeightMap &SampleBlockWeights,

                  BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights);

  uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);

  void buildEdges(FunctionT &F);

  bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount);

  void clearFunctionData(bool ResetDT = true);

  void computeDominanceAndLoopInfo(FunctionT &F);

  bool

  computeAndPropagateWeights(FunctionT &F,

                             const DenseSet<GlobalValue::GUID> &InlinedGUIDs);

  void initWeightPropagation(FunctionT &F,

                             const DenseSet<GlobalValue::GUID> &InlinedGUIDs);

  void

  finalizeWeightPropagation(FunctionT &F,

                            const DenseSet<GlobalValue::GUID> &InlinedGUIDs);

  void emitCoverageRemarks(FunctionT &F);

  /// 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;

  /// Map edges to their computed weights.

  ///

  /// Edge weights are computed by propagating basic block weights in

  /// SampleProfile::propagateWeights.

  EdgeWeightMap EdgeWeights;

  /// Set of visited blocks during propagation.

  SmallPtrSet<const BasicBlockT *, 32> VisitedBlocks;

  /// Set of visited edges during propagation.

  SmallSet<Edge, 32> VisitedEdges;

  /// 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;

  /// Dominance, post-dominance and loop information.

  DominatorTreePtrT DT;

  PostDominatorTreePtrT PDT;

  LoopInfoPtrT LI;

  /// Predecessors for each basic block in the CFG.

  BlockEdgeMap Predecessors;

  /// Successors for each basic block in the CFG.

  BlockEdgeMap Successors;

  /// Profile coverage tracker.

  SampleCoverageTracker CoverageTracker;

  /// Profile reader object.

  std::unique_ptr<SampleProfileReader> Reader;

  /// Samples collected for the body of this function.

  FunctionSamples *Samples = nullptr;

  /// Name of the profile file to load.

  std::string Filename;

  /// Name of the profile remapping file to load.

  std::string RemappingFilename;

  /// Profile Summary Info computed from sample profile.

  ProfileSummaryInfo *PSI = nullptr;

  /// Optimization Remark Emitter used to emit diagnostic remarks.

  OptRemarkEmitterT *ORE = nullptr;

};

/// Clear all the per-function data used to load samples and propagate weights.

template <typename BT>

void SampleProfileLoaderBaseImpl<BT>::clearFunctionData(bool ResetDT) {

  BlockWeights.clear();

  EdgeWeights.clear();

  VisitedBlocks.clear();

  VisitedEdges.clear();

  EquivalenceClass.clear();

  if (ResetDT) {

    DT = nullptr;

    PDT = nullptr;

    LI = nullptr;

  }

  Predecessors.clear();

  Successors.clear();

  CoverageTracker.clear();

}

#ifndef NDEBUG

/// Print the weight of edge \p E on stream \p OS.

///

/// \param OS  Stream to emit the output to.

/// \param E  Edge to print.

template <typename BT>

void SampleProfileLoaderBaseImpl<BT>::printEdgeWeight(raw_ostream &OS, Edge E) {

  OS << "weight[" << E.first->getName() << "->" << E.second->getName()

     << "]: " << EdgeWeights[E] << "\n";

}

/// 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.

template <typename BT>

void SampleProfileLoaderBaseImpl<BT>::printBlockEquivalence(

    raw_ostream &OS, const BasicBlockT *BB) {

  const BasicBlockT *Equiv = EquivalenceClass[BB];

  OS << "equivalence[" << BB->getName()

     << "]: " << ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE") << "\n";

}

/// Print the weight of block \p BB on stream \p OS.

///

/// \param OS  Stream to emit the output to.

/// \param BB  Block to print.

template <typename BT>

void SampleProfileLoaderBaseImpl<BT>::printBlockWeight(

    raw_ostream &OS, const BasicBlockT *BB) const {

  const auto &I = BlockWeights.find(BB);

  uint64_t W = (I == BlockWeights.end() ? 0 : I->second);

  OS << "weight[" << BB->getName() << "]: " << W << "\n";

}

#endif

/// 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.

template <typename BT>

ErrorOr<uint64_t>

SampleProfileLoaderBaseImpl<BT>::getInstWeight(const InstructionT &Inst) {

  return getInstWeightImpl(Inst);

}

template <typename BT>

ErrorOr<uint64_t>

SampleProfileLoaderBaseImpl<BT>::getInstWeightImpl(const InstructionT &Inst) {

  const FunctionSamples *FS = findFunctionSamples(Inst);

  if (!FS)

    return std::error_code();

  const DebugLoc &DLoc = Inst.getDebugLoc();

  if (!DLoc)

    return std::error_code();

  const DILocation *DIL = DLoc;

  uint32_t LineOffset = FunctionSamples::getOffset(DIL);

  uint32_t Discriminator;

  if (EnableFSDiscriminator)

    Discriminator = DIL->getDiscriminator();

  else

    Discriminator = DIL->getBaseDiscriminator();

  ErrorOr<uint64_t> R = FS->findSamplesAt(LineOffset, Discriminator);

  if (R) {

    bool FirstMark =

        CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());

    if (FirstMark) {

      ORE->emit([&]() {

        OptRemarkAnalysisT Remark(DEBUG_TYPE, "AppliedSamples", &Inst);

        Remark << "Applied " << ore::NV("NumSamples", *R);

        Remark << " samples from profile (offset: ";

        Remark << ore::NV("LineOffset", LineOffset);

        if (Discriminator) {

          Remark << ".";

          Remark << ore::NV("Discriminator", Discriminator);

        }

        Remark << ")";

        return Remark;

      });

    }

    LLVM_DEBUG(dbgs() << "    " << DLoc.getLine() << "." << Discriminator << ":"

                      << Inst << " (line offset: " << LineOffset << "."

                      << Discriminator << " - weight: " << R.get() << ")\n");

  }

  return R;

}

/// Compute the weight of a basic block.

///

/// The weight of basic block \p BB is the maximum weight of all the

/// instructions in BB.

///

/// \param BB The basic block to query.

///

/// \returns the weight for \p BB.

template <typename BT>

ErrorOr<uint64_t>

SampleProfileLoaderBaseImpl<BT>::getBlockWeight(const BasicBlockT *BB) {

  uint64_t Max = 0;

  bool HasWeight = false;

  for (auto &I : *BB) {

    const ErrorOr<uint64_t> &R = getInstWeight(I);

    if (R) {

      Max = std::max(Max, R.get());

      HasWeight = true;

    }

  }

  return HasWeight ? ErrorOr<uint64_t>(Max) : std::error_code();

}

/// Compute and store the weights of every basic block.

///

/// This populates the BlockWeights map by computing

/// the weights of every basic block in the CFG.

///

/// \param F The function to query.

template <typename BT>

bool SampleProfileLoaderBaseImpl<BT>::computeBlockWeights(FunctionT &F) {

  bool Changed = false;

  LLVM_DEBUG(dbgs() << "Block weights\n");

  for (const auto &BB : F) {

    ErrorOr<uint64_t> Weight = getBlockWeight(&BB);

    if (Weight) {

      BlockWeights[&BB] = Weight.get();

      VisitedBlocks.insert(&BB);

      Changed = true;

    }

    LLVM_DEBUG(printBlockWeight(dbgs(), &BB));

  }

  return Changed;

}

/// Get the FunctionSamples for an instruction.

///

/// The FunctionSamples of an instruction \p Inst is the inlined instance

/// in which that instruction is coming from. We traverse the inline stack

/// of that instruction, and match it with the tree nodes in the profile.

///

/// \param Inst Instruction to query.

///

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

template <typename BT>

const FunctionSamples *SampleProfileLoaderBaseImpl<BT>::findFunctionSamples(

    const InstructionT &Inst) const {

  const DILocation *DIL = Inst.getDebugLoc();

  if (!DIL)

    return Samples;

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

  if (it.second) {

    it.first->second = Samples->findFunctionSamples(DIL, Reader->getRemapper());

  }

  return it.first->second;

}

/// Find equivalence classes for the given block.

///

/// This finds all the blocks that are guaranteed to execute the same

/// number of times as \p BB1. To do this, it traverses all the

/// descendants of \p BB1 in the dominator or post-dominator tree.

///

/// A block BB2 will be in the same equivalence class as \p BB1 if

/// the following holds:

///

/// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2

///    is a descendant of \p BB1 in the dominator tree, then BB2 should

///    dominate BB1 in the post-dominator tree.

///

/// 2- Both BB2 and \p BB1 must be in the same loop.

///

/// For every block BB2 that meets those two requirements, we set BB2's

/// equivalence class to \p BB1.

///

/// \param BB1  Block to check.

/// \param Descendants  Descendants of \p BB1 in either the dom or pdom tree.

/// \param DomTree  Opposite dominator tree. If \p Descendants is filled

///                 with blocks from \p BB1's dominator tree, then

///                 this is the post-dominator tree, and vice versa.

template <typename BT>

void SampleProfileLoaderBaseImpl<BT>::findEquivalencesFor(

    BasicBlockT *BB1, ArrayRef<BasicBlockT *> Descendants,

    PostDominatorTreeT *DomTree) {

  const BasicBlockT *EC = EquivalenceClass[BB1];

  uint64_t Weight = BlockWeights[EC];

  for (const auto *BB2 : Descendants) {

    bool IsDomParent = DomTree->dominates(BB2, BB1);

    bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);

    if (BB1 != BB2 && IsDomParent && IsInSameLoop) {

      EquivalenceClass[BB2] = EC;

      // If BB2 is visited, then the entire EC should be marked as visited.

      if (VisitedBlocks.count(BB2)) {

        VisitedBlocks.insert(EC);

      }

      // If BB2 is heavier than BB1, make BB2 have the same weight

      // as BB1.

      //

      // Note that we don't worry about the opposite situation here

      // (when BB2 is lighter than BB1). We will deal with this

      // during the propagation phase. Right now, we just want to

      // make sure that BB1 has the largest weight of all the

      // members of its equivalence set.

      Weight = std::max(Weight, BlockWeights[BB2]);

    }

  }

  const BasicBlockT *EntryBB = getEntryBB(EC->getParent());

  if (EC == EntryBB) {

    BlockWeights[EC] = Samples->getHeadSamples() + 1;

  } else {

    BlockWeights[EC] = Weight;

  }

}

/// Find equivalence classes.

///

/// Since samples may be missing from blocks, we can fill in the gaps by setting

/// the weights of all the blocks in the same equivalence class to the same

/// weight. To compute the concept of equivalence, we use dominance and loop

/// information. Two blocks B1 and B2 are in the same equivalence class if B1

/// dominates B2, B2 post-dominates B1 and both are in the same loop.

///

/// \param F The function to query.

template <typename BT>

void SampleProfileLoaderBaseImpl<BT>::findEquivalenceClasses(FunctionT &F) {

  SmallVector<BasicBlockT *, 8> DominatedBBs;

  LLVM_DEBUG(dbgs() << "\nBlock equivalence classes\n");

  // Find equivalence sets based on dominance and post-dominance information.

  for (auto &BB : F) {

    BasicBlockT *BB1 = &BB;

    // Compute BB1's equivalence class once.

    if (EquivalenceClass.count(BB1)) {

      LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1));

      continue;

    }

    // By default, blocks are in their own equivalence class.

    EquivalenceClass[BB1] = BB1;

    // Traverse all the blocks dominated by BB1. We are looking for

    // every basic block BB2 such that:

    //

    // 1- BB1 dominates BB2.

    // 2- BB2 post-dominates BB1.

    // 3- BB1 and BB2 are in the same loop nest.

    //

    // If all those conditions hold, it means that BB2 is executed

    // as many times as BB1, so they are placed in the same equivalence

    // class by making BB2's equivalence class be BB1.

    DominatedBBs.clear();

    DT->getDescendants(BB1, DominatedBBs);

    findEquivalencesFor(BB1, DominatedBBs, &*PDT);

    LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1));

  }

  // Assign weights to equivalence classes.

  //

  // All the basic blocks in the same equivalence class will execute

  // the same number of times. Since we know that the head block in

  // each equivalence class has the largest weight, assign that weight

  // to all the blocks in that equivalence class.

  LLVM_DEBUG(

      dbgs() << "\nAssign the same weight to all blocks in the same class\n");

  for (auto &BI : F) {

    const BasicBlockT *BB = &BI;

    const BasicBlockT *EquivBB = EquivalenceClass[BB];

    if (BB != EquivBB)

      BlockWeights[BB] = BlockWeights[EquivBB];

    LLVM_DEBUG(printBlockWeight(dbgs(), BB));

  }

}

/// Visit the given edge to decide if it has a valid weight.

///

/// If \p E has not been visited before, we copy to \p UnknownEdge

/// and increment the count of unknown edges.

///

/// \param E  Edge to visit.

/// \param NumUnknownEdges  Current number of unknown edges.

/// \param UnknownEdge  Set if E has not been visited before.

///

/// \returns E's weight, if known. Otherwise, return 0.

template <typename BT>

uint64_t SampleProfileLoaderBaseImpl<BT>::visitEdge(Edge E,

                                                    unsigned *NumUnknownEdges,

                                                    Edge *UnknownEdge) {

  if (!VisitedEdges.count(E)) {

    (*NumUnknownEdges)++;

    *UnknownEdge = E;

    return 0;

  }

  return EdgeWeights[E];

}

/// Propagate weights through incoming/outgoing edges.

///

/// If the weight of a basic block is known, and there is only one edge

/// with an unknown weight, we can calculate the weight of that edge.

///

/// Similarly, if all the edges have a known count, we can calculate the

/// count of the basic block, if needed.

///

/// \param F  Function to process.

/// \param UpdateBlockCount  Whether we should update basic block counts that

///                          has already been annotated.

///

/// \returns  True if new weights were assigned to edges or blocks.

template <typename BT>

bool SampleProfileLoaderBaseImpl<BT>::propagateThroughEdges(

    FunctionT &F, bool UpdateBlockCount) {

  bool Changed = false;

  LLVM_DEBUG(dbgs() << "\nPropagation through edges\n");

  for (const auto &BI : F) {

    const BasicBlockT *BB = &BI;

    const BasicBlockT *EC = EquivalenceClass[BB];

    // Visit all the predecessor and successor edges to determine

    // which ones have a weight assigned already. Note that it doesn't

    // matter that we only keep track of a single unknown edge. The

    // only case we are interested in handling is when only a single

    // edge is unknown (see setEdgeOrBlockWeight).

    for (unsigned i = 0; i < 2; i++) {

      uint64_t TotalWeight = 0;

      unsigned NumUnknownEdges = 0, NumTotalEdges = 0;

      Edge UnknownEdge, SelfReferentialEdge, SingleEdge;

      if (i == 0) {

        // First, visit all predecessor edges.

        NumTotalEdges = Predecessors[BB].size();

        for (auto *Pred : Predecessors[BB]) {

          Edge E = std::make_pair(Pred, BB);

          TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);

          if (E.first == E.second)

            SelfReferentialEdge = E;

        }

        if (NumTotalEdges == 1) {

          SingleEdge = std::make_pair(Predecessors[BB][0], BB);

        }

      } else {

        // On the second round, visit all successor edges.

        NumTotalEdges = Successors[BB].size();

        for (auto *Succ : Successors[BB]) {

          Edge E = std::make_pair(BB, Succ);

          TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);

        }

        if (NumTotalEdges == 1) {

          SingleEdge = std::make_pair(BB, Successors[BB][0]);

        }

      }

      // After visiting all the edges, there are three cases that we

      // can handle immediately:

      //

      // - All the edge weights are known (i.e., NumUnknownEdges == 0).

      //   In this case, we simply check that the sum of all the edges

      //   is the same as BB's weight. If not, we change BB's weight

      //   to match. Additionally, if BB had not been visited before,

      //   we mark it visited.

      //

      // - Only one edge is unknown and BB has already been visited.

      //   In this case, we can compute the weight of the edge by

      //   subtracting the total block weight from all the known

      //   edge weights. If the edges weight more than BB, then the

      //   edge of the last remaining edge is set to zero.

      //

      // - There exists a self-referential edge and the weight of BB is

      //   known. In this case, this edge can be based on BB's weight.

      //   We add up all the other known edges and set the weight on

      //   the self-referential edge as we did in the previous case.

      //

      // In any other case, we must continue iterating. Eventually,

      // all edges will get a weight, or iteration will stop when

      // it reaches SampleProfileMaxPropagateIterations.

      if (NumUnknownEdges <= 1) {

        uint64_t &BBWeight = BlockWeights[EC];

        if (NumUnknownEdges == 0) {

          if (!VisitedBlocks.count(EC)) {

            // If we already know the weight of all edges, the weight of the

            // basic block can be computed. It should be no larger than the sum

            // of all edge weights.

            if (TotalWeight > BBWeight) {

              BBWeight = TotalWeight;

              Changed = true;

              LLVM_DEBUG(dbgs() << "All edge weights for " << BB->getName()

                                << " known. Set weight for block: ";

                         printBlockWeight(dbgs(), BB););

            }

          } else if (NumTotalEdges == 1 &&

                     EdgeWeights[SingleEdge] < BlockWeights[EC]) {

            // If there is only one edge for the visited basic block, use the

            // block weight to adjust edge weight if edge weight is smaller.

            EdgeWeights[SingleEdge] = BlockWeights[EC];

            Changed = true;

          }

        } else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {

          // If there is a single unknown edge and the block has been

          // visited, then we can compute E's weight.

          if (BBWeight >= TotalWeight)

            EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;

          else

            EdgeWeights[UnknownEdge] = 0;

          const BasicBlockT *OtherEC;

          if (i == 0)

            OtherEC = EquivalenceClass[UnknownEdge.first];

          else

            OtherEC = EquivalenceClass[UnknownEdge.second];

          // Edge weights should never exceed the BB weights it connects.

          if (VisitedBlocks.count(OtherEC) &&

              EdgeWeights[UnknownEdge] > BlockWeights[OtherEC])

            EdgeWeights[UnknownEdge] = BlockWeights[OtherEC];

          VisitedEdges.insert(UnknownEdge);

          Changed = true;

          LLVM_DEBUG(dbgs() << "Set weight for edge: ";

                     printEdgeWeight(dbgs(), UnknownEdge));

        }

      } else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) {

        // If a block Weights 0, all its in/out edges should weight 0.

        if (i == 0) {

          for (auto *Pred : Predecessors[BB]) {

            Edge E = std::make_pair(Pred, BB);

            EdgeWeights[E] = 0;

            VisitedEdges.insert(E);

          }

        } else {

          for (auto *Succ : Successors[BB]) {

            Edge E = std::make_pair(BB, Succ);

            EdgeWeights[E] = 0;

            VisitedEdges.insert(E);

          }

        }

      } else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {

        uint64_t &BBWeight = BlockWeights[BB];

        // We have a self-referential edge and the weight of BB is known.

        if (BBWeight >= TotalWeight)

          EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;

        else

          EdgeWeights[SelfReferentialEdge] = 0;

        VisitedEdges.insert(SelfReferentialEdge);

        Changed = true;

        LLVM_DEBUG(dbgs() << "Set self-referential edge weight to: ";

                   printEdgeWeight(dbgs(), SelfReferentialEdge));

      }

      if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) {

        BlockWeights[EC] = TotalWeight;

        VisitedBlocks.insert(EC);

        Changed = true;

      }

    }

  }

  return Changed;

}

/// Build in/out edge lists for each basic block in the CFG.

///

/// We are interested in unique edges. If a block B1 has multiple

/// edges to another block B2, we only add a single B1->B2 edge.

template <typename BT>

void SampleProfileLoaderBaseImpl<BT>::buildEdges(FunctionT &F) {

  for (auto &BI : F) {

    BasicBlockT *B1 = &BI;

    // Add predecessors for B1.

    SmallPtrSet<BasicBlockT *, 16> Visited;

    if (!Predecessors[B1].empty())

      llvm_unreachable("Found a stale predecessors list in a basic block.");

    for (auto *B2 : getPredecessors(B1))

      if (Visited.insert(B2).second)

        Predecessors[B1].push_back(B2);

    // Add successors for B1.

    Visited.clear();

    if (!Successors[B1].empty())

      llvm_unreachable("Found a stale successors list in a basic block.");

    for (auto *B2 : getSuccessors(B1))

      if (Visited.insert(B2).second)

        Successors[B1].push_back(B2);

  }

}

/// Propagate weights into edges

///

/// The following rules are applied to every block BB in the CFG:

///

/// - If BB has a single predecessor/successor, then the weight

///   of that edge is the weight of the block.

///

/// - If all incoming or outgoing edges are known except one, and the

///   weight of the block is already known, the weight of the unknown

///   edge will be the weight of the block minus the sum of all the known

///   edges. If the sum of all the known edges is larger than BB's weight,

///   we set the unknown edge weight to zero.

///

/// - If there is a self-referential edge, and the weight of the block is

///   known, the weight for that edge is set to the weight of the block

///   minus the weight of the other incoming edges to that block (if

///   known).

template <typename BT>

void SampleProfileLoaderBaseImpl<BT>::propagateWeights(FunctionT &F) {

  // Flow-based profile inference is only usable with BasicBlock instantiation

  // of SampleProfileLoaderBaseImpl.

  if (SampleProfileUseProfi) {

    // Prepare block sample counts for inference.

    BlockWeightMap SampleBlockWeights;

    for (const auto &BI : F) {

      ErrorOr<uint64_t> Weight = getBlockWeight(&BI);

      if (Weight)

        SampleBlockWeights[&BI] = Weight.get();

    }

    // Fill in BlockWeights and EdgeWeights using an inference algorithm.

    applyProfi(F, Successors, SampleBlockWeights, BlockWeights, EdgeWeights);

  } else {

    bool Changed = true;

    unsigned I = 0;

    // If BB weight is larger than its corresponding loop's header BB weight,

    // use the BB weight to replace the loop header BB weight.

    for (auto &BI : F) {

      BasicBlockT *BB = &BI;