text: //===--- CodeGenPGO.cpp - PGO Instrumentation for LLVM CodeGen --*- 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
  //
  //===----------------------------------------------------------------------===//
  //
  // Instrumentation-based profile-guided optimization
  //
  //===----------------------------------------------------------------------===//
  
  #include "CodeGenPGO.h"
  #include "CodeGenFunction.h"
  #include "CoverageMappingGen.h"
  #include "clang/AST/RecursiveASTVisitor.h"
  #include "clang/AST/StmtVisitor.h"
  #include "llvm/IR/Intrinsics.h"
  #include "llvm/IR/MDBuilder.h"
  #include "llvm/Support/CommandLine.h"
  #include "llvm/Support/Endian.h"
  #include "llvm/Support/FileSystem.h"
  #include "llvm/Support/MD5.h"
  
  static llvm::cl::opt<bool>
      EnableValueProfiling("enable-value-profiling", llvm::cl::ZeroOrMore,
                           llvm::cl::desc("Enable value profiling"),
                           llvm::cl::Hidden, llvm::cl::init(false));
  
  using namespace clang;
  using namespace CodeGen;
  
  void CodeGenPGO::setFuncName(StringRef Name,
                               llvm::GlobalValue::LinkageTypes Linkage) {
    llvm::IndexedInstrProfReader *PGOReader = CGM.getPGOReader();
    FuncName = llvm::getPGOFuncName(
        Name, Linkage, CGM.getCodeGenOpts().MainFileName,
        PGOReader ? PGOReader->getVersion() : llvm::IndexedInstrProf::Version);
  
    // If we're generating a profile, create a variable for the name.
    if (CGM.getCodeGenOpts().hasProfileClangInstr())
      FuncNameVar = llvm::createPGOFuncNameVar(CGM.getModule(), Linkage, FuncName);
  }
  
  void CodeGenPGO::setFuncName(llvm::Function *Fn) {
    setFuncName(Fn->getName(), Fn->getLinkage());
    // Create PGOFuncName meta data.
    llvm::createPGOFuncNameMetadata(*Fn, FuncName);
  }
  
  /// The version of the PGO hash algorithm.
  enum PGOHashVersion : unsigned {
    PGO_HASH_V1,
    PGO_HASH_V2,
    PGO_HASH_V3,
  
    // Keep this set to the latest hash version.
    PGO_HASH_LATEST = PGO_HASH_V3
  };
  
  namespace {
  /// Stable hasher for PGO region counters.
  ///
  /// PGOHash produces a stable hash of a given function's control flow.
  ///
  /// Changing the output of this hash will invalidate all previously generated
  /// profiles -- i.e., don't do it.
  ///
  /// \note  When this hash does eventually change (years?), we still need to
  /// support old hashes.  We'll need to pull in the version number from the
  /// profile data format and use the matching hash function.
  class PGOHash {
    uint64_t Working;
    unsigned Count;
    PGOHashVersion HashVersion;
    llvm::MD5 MD5;
  
    static const int NumBitsPerType = 6;
    static const unsigned NumTypesPerWord = sizeof(uint64_t) * 8 / NumBitsPerType;
    static const unsigned TooBig = 1u << NumBitsPerType;
  
  public:
    /// Hash values for AST nodes.
    ///
    /// Distinct values for AST nodes that have region counters attached.
    ///
    /// These values must be stable.  All new members must be added at the end,
    /// and no members should be removed.  Changing the enumeration value for an
    /// AST node will affect the hash of every function that contains that node.
    enum HashType : unsigned char {
      None = 0,
      LabelStmt = 1,
      WhileStmt,
      DoStmt,
      ForStmt,
      CXXForRangeStmt,
      ObjCForCollectionStmt,
      SwitchStmt,
      CaseStmt,
      DefaultStmt,
      IfStmt,
      CXXTryStmt,
      CXXCatchStmt,
      ConditionalOperator,
      BinaryOperatorLAnd,
      BinaryOperatorLOr,
      BinaryConditionalOperator,
      // The preceding values are available with PGO_HASH_V1.
  
      EndOfScope,
      IfThenBranch,
      IfElseBranch,
      GotoStmt,
      IndirectGotoStmt,
      BreakStmt,
      ContinueStmt,
      ReturnStmt,
      ThrowExpr,
      UnaryOperatorLNot,
      BinaryOperatorLT,
      BinaryOperatorGT,
      BinaryOperatorLE,
      BinaryOperatorGE,
      BinaryOperatorEQ,
      BinaryOperatorNE,
      // The preceding values are available since PGO_HASH_V2.
  
      // Keep this last.  It's for the static assert that follows.
      LastHashType
    };
    static_assert(LastHashType <= TooBig, "Too many types in HashType");
  
    PGOHash(PGOHashVersion HashVersion)
        : Working(0), Count(0), HashVersion(HashVersion), MD5() {}
    void combine(HashType Type);
    uint64_t finalize();
    PGOHashVersion getHashVersion() const { return HashVersion; }
  };
  const int PGOHash::NumBitsPerType;
  const unsigned PGOHash::NumTypesPerWord;
  const unsigned PGOHash::TooBig;
  
  /// Get the PGO hash version used in the given indexed profile.
  static PGOHashVersion getPGOHashVersion(llvm::IndexedInstrProfReader *PGOReader,
                                          CodeGenModule &CGM) {
    if (PGOReader->getVersion() <= 4)
      return PGO_HASH_V1;
    if (PGOReader->getVersion() <= 5)
      return PGO_HASH_V2;
    return PGO_HASH_V3;
  }
  
  /// A RecursiveASTVisitor that fills a map of statements to PGO counters.
  struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
    using Base = RecursiveASTVisitor<MapRegionCounters>;
  
    /// The next counter value to assign.
    unsigned NextCounter;
    /// The function hash.
    PGOHash Hash;
    /// The map of statements to counters.
    llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
  
    MapRegionCounters(PGOHashVersion HashVersion,
                      llvm::DenseMap<const Stmt *, unsigned> &CounterMap)
        : NextCounter(0), Hash(HashVersion), CounterMap(CounterMap) {}
  
    // Blocks and lambdas are handled as separate functions, so we need not
    // traverse them in the parent context.
    bool TraverseBlockExpr(BlockExpr *BE) { return true; }
    bool TraverseLambdaExpr(LambdaExpr *LE) {
      // Traverse the captures, but not the body.
      for (auto C : zip(LE->captures(), LE->capture_inits()))
        TraverseLambdaCapture(LE, &std::get<0>(C), std::get<1>(C));
      return true;
    }
    bool TraverseCapturedStmt(CapturedStmt *CS) { return true; }
  
    bool VisitDecl(const Decl *D) {
      switch (D->getKind()) {
      default:
        break;
      case Decl::Function:
      case Decl::CXXMethod:
      case Decl::CXXConstructor:
      case Decl::CXXDestructor:
      case Decl::CXXConversion:
      case Decl::ObjCMethod:
      case Decl::Block:
      case Decl::Captured:
        CounterMap[D->getBody()] = NextCounter++;
        break;
      }
      return true;
    }
  
    /// If \p S gets a fresh counter, update the counter mappings. Return the
    /// V1 hash of \p S.
    PGOHash::HashType updateCounterMappings(Stmt *S) {
      auto Type = getHashType(PGO_HASH_V1, S);
      if (Type != PGOHash::None)
        CounterMap[S] = NextCounter++;
      return Type;
    }
  
    /// Include \p S in the function hash.
    bool VisitStmt(Stmt *S) {
      auto Type = updateCounterMappings(S);
      if (Hash.getHashVersion() != PGO_HASH_V1)
        Type = getHashType(Hash.getHashVersion(), S);
      if (Type != PGOHash::None)
        Hash.combine(Type);
      return true;
    }
  
    bool TraverseIfStmt(IfStmt *If) {
      // If we used the V1 hash, use the default traversal.
      if (Hash.getHashVersion() == PGO_HASH_V1)
        return Base::TraverseIfStmt(If);
  
      // Otherwise, keep track of which branch we're in while traversing.
      VisitStmt(If);
      for (Stmt *CS : If->children()) {
        if (!CS)
          continue;
        if (CS == If->getThen())
          Hash.combine(PGOHash::IfThenBranch);
        else if (CS == If->getElse())
          Hash.combine(PGOHash::IfElseBranch);
        TraverseStmt(CS);
      }
      Hash.combine(PGOHash::EndOfScope);
      return true;
    }
  
  // If the statement type \p N is nestable, and its nesting impacts profile
  // stability, define a custom traversal which tracks the end of the statement
  // in the hash (provided we're not using the V1 hash).
  #define DEFINE_NESTABLE_TRAVERSAL(N)                                           \
    bool Traverse##N(N *S) {                                                     \
      Base::Traverse##N(S);                                                      \
      if (Hash.getHashVersion() != PGO_HASH_V1)                                  \
        Hash.combine(PGOHash::EndOfScope);                                       \
      return true;                                                               \
    }
  
    DEFINE_NESTABLE_TRAVERSAL(WhileStmt)
    DEFINE_NESTABLE_TRAVERSAL(DoStmt)
    DEFINE_NESTABLE_TRAVERSAL(ForStmt)
    DEFINE_NESTABLE_TRAVERSAL(CXXForRangeStmt)
    DEFINE_NESTABLE_TRAVERSAL(ObjCForCollectionStmt)
    DEFINE_NESTABLE_TRAVERSAL(CXXTryStmt)
    DEFINE_NESTABLE_TRAVERSAL(CXXCatchStmt)
  
    /// Get version \p HashVersion of the PGO hash for \p S.
    PGOHash::HashType getHashType(PGOHashVersion HashVersion, const Stmt *S) {
      switch (S->getStmtClass()) {
      default:
        break;
      case Stmt::LabelStmtClass:
        return PGOHash::LabelStmt;
      case Stmt::WhileStmtClass:
        return PGOHash::WhileStmt;
      case Stmt::DoStmtClass:
        return PGOHash::DoStmt;
      case Stmt::ForStmtClass:
        return PGOHash::ForStmt;
      case Stmt::CXXForRangeStmtClass:
        return PGOHash::CXXForRangeStmt;
      case Stmt::ObjCForCollectionStmtClass:
        return PGOHash::ObjCForCollectionStmt;
      case Stmt::SwitchStmtClass:
        return PGOHash::SwitchStmt;
      case Stmt::CaseStmtClass:
        return PGOHash::CaseStmt;
      case Stmt::DefaultStmtClass:
        return PGOHash::DefaultStmt;
      case Stmt::IfStmtClass:
        return PGOHash::IfStmt;
      case Stmt::CXXTryStmtClass:
        return PGOHash::CXXTryStmt;
      case Stmt::CXXCatchStmtClass:
        return PGOHash::CXXCatchStmt;
      case Stmt::ConditionalOperatorClass:
        return PGOHash::ConditionalOperator;
      case Stmt::BinaryConditionalOperatorClass:
        return PGOHash::BinaryConditionalOperator;
      case Stmt::BinaryOperatorClass: {
        const BinaryOperator *BO = cast<BinaryOperator>(S);
        if (BO->getOpcode() == BO_LAnd)
          return PGOHash::BinaryOperatorLAnd;
        if (BO->getOpcode() == BO_LOr)
          return PGOHash::BinaryOperatorLOr;
        if (HashVersion >= PGO_HASH_V2) {
          switch (BO->getOpcode()) {
          default:
            break;
          case BO_LT:
            return PGOHash::BinaryOperatorLT;
          case BO_GT:
            return PGOHash::BinaryOperatorGT;
          case BO_LE:
            return PGOHash::BinaryOperatorLE;
          case BO_GE:
            return PGOHash::BinaryOperatorGE;
          case BO_EQ:
            return PGOHash::BinaryOperatorEQ;
          case BO_NE:
            return PGOHash::BinaryOperatorNE;
          }
        }
        break;
      }
      }
  
      if (HashVersion >= PGO_HASH_V2) {
        switch (S->getStmtClass()) {
        default:
          break;
        case Stmt::GotoStmtClass:
          return PGOHash::GotoStmt;
        case Stmt::IndirectGotoStmtClass:
          return PGOHash::IndirectGotoStmt;
        case Stmt::BreakStmtClass:
          return PGOHash::BreakStmt;
        case Stmt::ContinueStmtClass:
          return PGOHash::ContinueStmt;
        case Stmt::ReturnStmtClass:
          return PGOHash::ReturnStmt;
        case Stmt::CXXThrowExprClass:
          return PGOHash::ThrowExpr;
        case Stmt::UnaryOperatorClass: {
          const UnaryOperator *UO = cast<UnaryOperator>(S);
          if (UO->getOpcode() == UO_LNot)
            return PGOHash::UnaryOperatorLNot;
          break;
        }
        }
      }
  
      return PGOHash::None;
    }
  };
  
  /// A StmtVisitor that propagates the raw counts through the AST and
  /// records the count at statements where the value may change.
  struct ComputeRegionCounts : public ConstStmtVisitor<ComputeRegionCounts> {
    /// PGO state.
    CodeGenPGO &PGO;
  
    /// A flag that is set when the current count should be recorded on the
    /// next statement, such as at the exit of a loop.
    bool RecordNextStmtCount;
  
    /// The count at the current location in the traversal.
    uint64_t CurrentCount;
  
    /// The map of statements to count values.
    llvm::DenseMap<const Stmt *, uint64_t> &CountMap;
  
    /// BreakContinueStack - Keep counts of breaks and continues inside loops.
    struct BreakContinue {
      uint64_t BreakCount;
      uint64_t ContinueCount;
      BreakContinue() : BreakCount(0), ContinueCount(0) {}
    };
    SmallVector<BreakContinue, 8> BreakContinueStack;
  
    ComputeRegionCounts(llvm::DenseMap<const Stmt *, uint64_t> &CountMap,
                        CodeGenPGO &PGO)
        : PGO(PGO), RecordNextStmtCount(false), CountMap(CountMap) {}
  
    void RecordStmtCount(const Stmt *S) {
      if (RecordNextStmtCount) {
        CountMap[S] = CurrentCount;
        RecordNextStmtCount = false;
      }
    }
  
    /// Set and return the current count.
    uint64_t setCount(uint64_t Count) {
      CurrentCount = Count;
      return Count;
    }
  
    void VisitStmt(const Stmt *S) {
      RecordStmtCount(S);
      for (const Stmt *Child : S->children())
        if (Child)
          this->Visit(Child);
    }
  
    void VisitFunctionDecl(const FunctionDecl *D) {
      // Counter tracks entry to the function body.
      uint64_t BodyCount = setCount(PGO.getRegionCount(D->getBody()));
      CountMap[D->getBody()] = BodyCount;
      Visit(D->getBody());
    }
  
    // Skip lambda expressions. We visit these as FunctionDecls when we're
    // generating them and aren't interested in the body when generating a
    // parent context.
    void VisitLambdaExpr(const LambdaExpr *LE) {}
  
    void VisitCapturedDecl(const CapturedDecl *D) {
      // Counter tracks entry to the capture body.
      uint64_t BodyCount = setCount(PGO.getRegionCount(D->getBody()));
      CountMap[D->getBody()] = BodyCount;
      Visit(D->getBody());
    }
  
    void VisitObjCMethodDecl(const ObjCMethodDecl *D) {
      // Counter tracks entry to the method body.
      uint64_t BodyCount = setCount(PGO.getRegionCount(D->getBody()));
      CountMap[D->getBody()] = BodyCount;
      Visit(D->getBody());
    }
  
    void VisitBlockDecl(const BlockDecl *D) {
      // Counter tracks entry to the block body.
      uint64_t BodyCount = setCount(PGO.getRegionCount(D->getBody()));
      CountMap[D->getBody()] = BodyCount;
      Visit(D->getBody());
    }
  
    void VisitReturnStmt(const ReturnStmt *S) {
      RecordStmtCount(S);
      if (S->getRetValue())
        Visit(S->getRetValue());
      CurrentCount = 0;
      RecordNextStmtCount = true;
    }
  
    void VisitCXXThrowExpr(const CXXThrowExpr *E) {
      RecordStmtCount(E);
      if (E->getSubExpr())
        Visit(E->getSubExpr());
      CurrentCount = 0;
      RecordNextStmtCount = true;
    }
  
    void VisitGotoStmt(const GotoStmt *S) {
      RecordStmtCount(S);
      CurrentCount = 0;
      RecordNextStmtCount = true;
    }
  
    void VisitLabelStmt(const LabelStmt *S) {
      RecordNextStmtCount = false;
      // Counter tracks the block following the label.
      uint64_t BlockCount = setCount(PGO.getRegionCount(S));
      CountMap[S] = BlockCount;
      Visit(S->getSubStmt());
    }
  
    void VisitBreakStmt(const BreakStmt *S) {
      RecordStmtCount(S);
      assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
      BreakContinueStack.back().BreakCount += CurrentCount;
      CurrentCount = 0;
      RecordNextStmtCount = true;
    }
  
    void VisitContinueStmt(const ContinueStmt *S) {
      RecordStmtCount(S);
      assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
      BreakContinueStack.back().ContinueCount += CurrentCount;
      CurrentCount = 0;
      RecordNextStmtCount = true;
    }
  
    void VisitWhileStmt(const WhileStmt *S) {
      RecordStmtCount(S);
      uint64_t ParentCount = CurrentCount;
  
      BreakContinueStack.push_back(BreakContinue());
      // Visit the body region first so the break/continue adjustments can be
      // included when visiting the condition.
      uint64_t BodyCount = setCount(PGO.getRegionCount(S));
      CountMap[S->getBody()] = CurrentCount;
      Visit(S->getBody());
      uint64_t BackedgeCount = CurrentCount;
  
      // ...then go back and propagate counts through the condition. The count
      // at the start of the condition is the sum of the incoming edges,
      // the backedge from the end of the loop body, and the edges from
      // continue statements.
      BreakContinue BC = BreakContinueStack.pop_back_val();
      uint64_t CondCount =
          setCount(ParentCount + BackedgeCount + BC.ContinueCount);
      CountMap[S->getCond()] = CondCount;
      Visit(S->getCond());
      setCount(BC.BreakCount + CondCount - BodyCount);
      RecordNextStmtCount = true;
    }
  
    void VisitDoStmt(const DoStmt *S) {
      RecordStmtCount(S);
      uint64_t LoopCount = PGO.getRegionCount(S);
  
      BreakContinueStack.push_back(BreakContinue());
      // The count doesn't include the fallthrough from the parent scope. Add it.
      uint64_t BodyCount = setCount(LoopCount + CurrentCount);
      CountMap[S->getBody()] = BodyCount;
      Visit(S->getBody());
      uint64_t BackedgeCount = CurrentCount;
  
      BreakContinue BC = BreakContinueStack.pop_back_val();
      // The count at the start of the condition is equal to the count at the
      // end of the body, plus any continues.
      uint64_t CondCount = setCount(BackedgeCount + BC.ContinueCount);
      CountMap[S->getCond()] = CondCount;
      Visit(S->getCond());
      setCount(BC.BreakCount + CondCount - LoopCount);
      RecordNextStmtCount = true;
    }
  
    void VisitForStmt(const ForStmt *S) {
      RecordStmtCount(S);
      if (S->getInit())
        Visit(S->getInit());
  
      uint64_t ParentCount = CurrentCount;
  
      BreakContinueStack.push_back(BreakContinue());
      // Visit the body region first. (This is basically the same as a while
      // loop; see further comments in VisitWhileStmt.)
      uint64_t BodyCount = setCount(PGO.getRegionCount(S));
      CountMap[S->getBody()] = BodyCount;
      Visit(S->getBody());
      uint64_t BackedgeCount = CurrentCount;
      BreakContinue BC = BreakContinueStack.pop_back_val();
  
      // The increment is essentially part of the body but it needs to include
      // the count for all the continue statements.
      if (S->getInc()) {
        uint64_t IncCount = setCount(BackedgeCount + BC.ContinueCount);
        CountMap[S->getInc()] = IncCount;
        Visit(S->getInc());
      }
  
      // ...then go back and propagate counts through the condition.
      uint64_t CondCount =
          setCount(ParentCount + BackedgeCount + BC.ContinueCount);
      if (S->getCond()) {
        CountMap[S->getCond()] = CondCount;
        Visit(S->getCond());
      }
      setCount(BC.BreakCount + CondCount - BodyCount);
      RecordNextStmtCount = true;
    }
  
    void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
      RecordStmtCount(S);
      if (S->getInit())
        Visit(S->getInit());
      Visit(S->getLoopVarStmt());
      Visit(S->getRangeStmt());
      Visit(S->getBeginStmt());
      Visit(S->getEndStmt());
  
      uint64_t ParentCount = CurrentCount;
      BreakContinueStack.push_back(BreakContinue());
      // Visit the body region first. (This is basically the same as a while
      // loop; see further comments in VisitWhileStmt.)
      uint64_t BodyCount = setCount(PGO.getRegionCount(S));
      CountMap[S->getBody()] = BodyCount;
      Visit(S->getBody());
      uint64_t BackedgeCount = CurrentCount;
      BreakContinue BC = BreakContinueStack.pop_back_val();
  
      // The increment is essentially part of the body but it needs to include
      // the count for all the continue statements.
      uint64_t IncCount = setCount(BackedgeCount + BC.ContinueCount);
      CountMap[S->getInc()] = IncCount;
      Visit(S->getInc());
  
      // ...then go back and propagate counts through the condition.
      uint64_t CondCount =
          setCount(ParentCount + BackedgeCount + BC.ContinueCount);
      CountMap[S->getCond()] = CondCount;
      Visit(S->getCond());
      setCount(BC.BreakCount + CondCount - BodyCount);
      RecordNextStmtCount = true;
    }
  
    void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
      RecordStmtCount(S);
      Visit(S->getElement());
      uint64_t ParentCount = CurrentCount;
      BreakContinueStack.push_back(BreakContinue());
      // Counter tracks the body of the loop.
      uint64_t BodyCount = setCount(PGO.getRegionCount(S));
      CountMap[S->getBody()] = BodyCount;
      Visit(S->getBody());
      uint64_t BackedgeCount = CurrentCount;
      BreakContinue BC = BreakContinueStack.pop_back_val();
  
      setCount(BC.BreakCount + ParentCount + BackedgeCount + BC.ContinueCount -
               BodyCount);
      RecordNextStmtCount = true;
    }
  
    void VisitSwitchStmt(const SwitchStmt *S) {
      RecordStmtCount(S);
      if (S->getInit())
        Visit(S->getInit());
      Visit(S->getCond());
      CurrentCount = 0;
      BreakContinueStack.push_back(BreakContinue());
      Visit(S->getBody());
      // If the switch is inside a loop, add the continue counts.
      BreakContinue BC = BreakContinueStack.pop_back_val();
      if (!BreakContinueStack.empty())
        BreakContinueStack.back().ContinueCount += BC.ContinueCount;
      // Counter tracks the exit block of the switch.
      setCount(PGO.getRegionCount(S));
      RecordNextStmtCount = true;
    }
  
    void VisitSwitchCase(const SwitchCase *S) {
      RecordNextStmtCount = false;
      // Counter for this particular case. This counts only jumps from the
      // switch header and does not include fallthrough from the case before
      // this one.
      uint64_t CaseCount = PGO.getRegionCount(S);
      setCount(CurrentCount + CaseCount);
      // We need the count without fallthrough in the mapping, so it's more useful
      // for branch probabilities.
      CountMap[S] = CaseCount;
      RecordNextStmtCount = true;
      Visit(S->getSubStmt());
    }
  
    void VisitIfStmt(const IfStmt *S) {
      RecordStmtCount(S);
      uint64_t ParentCount = CurrentCount;
      if (S->getInit())
        Visit(S->getInit());
      Visit(S->getCond());
  
      // Counter tracks the "then" part of an if statement. The count for
      // the "else" part, if it exists, will be calculated from this counter.
      uint64_t ThenCount = setCount(PGO.getRegionCount(S));
      CountMap[S->getThen()] = ThenCount;
      Visit(S->getThen());
      uint64_t OutCount = CurrentCount;
  
      uint64_t ElseCount = ParentCount - ThenCount;
      if (S->getElse()) {
        setCount(ElseCount);
        CountMap[S->getElse()] = ElseCount;
        Visit(S->getElse());
        OutCount += CurrentCount;
      } else
        OutCount += ElseCount;
      setCount(OutCount);
      RecordNextStmtCount = true;
    }
  
    void VisitCXXTryStmt(const CXXTryStmt *S) {
      RecordStmtCount(S);
      Visit(S->getTryBlock());
      for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I)
        Visit(S->getHandler(I));
      // Counter tracks the continuation block of the try statement.
      setCount(PGO.getRegionCount(S));
      RecordNextStmtCount = true;
    }
  
    void VisitCXXCatchStmt(const CXXCatchStmt *S) {
      RecordNextStmtCount = false;
      // Counter tracks the catch statement's handler block.
      uint64_t CatchCount = setCount(PGO.getRegionCount(S));
      CountMap[S] = CatchCount;
      Visit(S->getHandlerBlock());
    }
  
    void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
      RecordStmtCount(E);
      uint64_t ParentCount = CurrentCount;
      Visit(E->getCond());
  
      // Counter tracks the "true" part of a conditional operator. The
      // count in the "false" part will be calculated from this counter.
      uint64_t TrueCount = setCount(PGO.getRegionCount(E));
      CountMap[E->getTrueExpr()] = TrueCount;
      Visit(E->getTrueExpr());
      uint64_t OutCount = CurrentCount;
  
      uint64_t FalseCount = setCount(ParentCount - TrueCount);
      CountMap[E->getFalseExpr()] = FalseCount;
      Visit(E->getFalseExpr());
      OutCount += CurrentCount;
  
      setCount(OutCount);
      RecordNextStmtCount = true;
    }
  
    void VisitBinLAnd(const BinaryOperator *E) {
      RecordStmtCount(E);
      uint64_t ParentCount = CurrentCount;
      Visit(E->getLHS());
      // Counter tracks the right hand side of a logical and operator.
      uint64_t RHSCount = setCount(PGO.getRegionCount(E));
      CountMap[E->getRHS()] = RHSCount;
      Visit(E->getRHS());
      setCount(ParentCount + RHSCount - CurrentCount);
      RecordNextStmtCount = true;
    }
  
    void VisitBinLOr(const BinaryOperator *E) {
      RecordStmtCount(E);
      uint64_t ParentCount = CurrentCount;
      Visit(E->getLHS());
      // Counter tracks the right hand side of a logical or operator.
      uint64_t RHSCount = setCount(PGO.getRegionCount(E));
      CountMap[E->getRHS()] = RHSCount;
      Visit(E->getRHS());
      setCount(ParentCount + RHSCount - CurrentCount);
      RecordNextStmtCount = true;
    }
  };
  } // end anonymous namespace
  
  void PGOHash::combine(HashType Type) {
    // Check that we never combine 0 and only have six bits.
    assert(Type && "Hash is invalid: unexpected type 0");
    assert(unsigned(Type) < TooBig && "Hash is invalid: too many types");
  
    // Pass through MD5 if enough work has built up.
    if (Count && Count % NumTypesPerWord == 0) {
      using namespace llvm::support;
      uint64_t Swapped = endian::byte_swap<uint64_t, little>(Working);
      MD5.update(llvm::makeArrayRef((uint8_t *)&Swapped, sizeof(Swapped)));
      Working = 0;
    }
  
    // Accumulate the current type.
    ++Count;
    Working = Working << NumBitsPerType | Type;
  }
  
  uint64_t PGOHash::finalize() {
    // Use Working as the hash directly if we never used MD5.
    if (Count <= NumTypesPerWord)
      // No need to byte swap here, since none of the math was endian-dependent.
      // This number will be byte-swapped as required on endianness transitions,
      // so we will see the same value on the other side.
      return Working;
  
    // Check for remaining work in Working.
    if (Working) {
      // Keep the buggy behavior from v1 and v2 for backward-compatibility. This
      // is buggy because it converts a uint64_t into an array of uint8_t.
      if (HashVersion < PGO_HASH_V3) {
        MD5.update({(uint8_t)Working});
      } else {
        using namespace llvm::support;
        uint64_t Swapped = endian::byte_swap<uint64_t, little>(Working);
        MD5.update(llvm::makeArrayRef((uint8_t *)&Swapped, sizeof(Swapped)));
      }
    }
  
    // Finalize the MD5 and return the hash.
    llvm::MD5::MD5Result Result;
    MD5.final(Result);
    return Result.low();
  }
  
  void CodeGenPGO::assignRegionCounters(GlobalDecl GD, llvm::Function *Fn) {
    const Decl *D = GD.getDecl();
    if (!D->hasBody())
      return;
  
    // Skip CUDA/HIP kernel launch stub functions.
    if (CGM.getLangOpts().CUDA && !CGM.getLangOpts().CUDAIsDevice &&
        D->hasAttr<CUDAGlobalAttr>())
      return;
  
    bool InstrumentRegions = CGM.getCodeGenOpts().hasProfileClangInstr();
    llvm::IndexedInstrProfReader *PGOReader = CGM.getPGOReader();
    if (!InstrumentRegions && !PGOReader)
      return;
    if (D->isImplicit())
      return;
    // Constructors and destructors may be represented by several functions in IR.
    // If so, instrument only base variant, others are implemented by delegation
    // to the base one, it would be counted twice otherwise.
    if (CGM.getTarget().getCXXABI().hasConstructorVariants()) {
      if (const auto *CCD = dyn_cast<CXXConstructorDecl>(D))
        if (GD.getCtorType() != Ctor_Base &&
            CodeGenFunction::IsConstructorDelegationValid(CCD))
          return;
    }
    if (isa<CXXDestructorDecl>(D) && GD.getDtorType() != Dtor_Base)
      return;
  
    CGM.ClearUnusedCoverageMapping(D);
    setFuncName(Fn);
  
    mapRegionCounters(D);
    if (CGM.getCodeGenOpts().CoverageMapping)
      emitCounterRegionMapping(D);
    if (PGOReader) {
      SourceManager &SM = CGM.getContext().getSourceManager();
      loadRegionCounts(PGOReader, SM.isInMainFile(D->getLocation()));
      computeRegionCounts(D);
      applyFunctionAttributes(PGOReader, Fn);
    }
  }
  
  void CodeGenPGO::mapRegionCounters(const Decl *D) {
    // Use the latest hash version when inserting instrumentation, but use the
    // version in the indexed profile if we're reading PGO data.
    PGOHashVersion HashVersion = PGO_HASH_LATEST;
    if (auto *PGOReader = CGM.getPGOReader())
      HashVersion = getPGOHashVersion(PGOReader, CGM);
  
    RegionCounterMap.reset(new llvm::DenseMap<const Stmt *, unsigned>);
    MapRegionCounters Walker(HashVersion, *RegionCounterMap);
    if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D))
      Walker.TraverseDecl(const_cast<FunctionDecl *>(FD));
    else if (const ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(D))
      Walker.TraverseDecl(const_cast<ObjCMethodDecl *>(MD));
    else if (const BlockDecl *BD = dyn_cast_or_null<BlockDecl>(D))
      Walker.TraverseDecl(const_cast<BlockDecl *>(BD));
    else if (const CapturedDecl *CD = dyn_cast_or_null<CapturedDecl>(D))
      Walker.TraverseDecl(const_cast<CapturedDecl *>(CD));
    assert(Walker.NextCounter > 0 && "no entry counter mapped for decl");
    NumRegionCounters = Walker.NextCounter;
    FunctionHash = Walker.Hash.finalize();
  }
  
  bool CodeGenPGO::skipRegionMappingForDecl(const Decl *D) {
    if (!D->getBody())
      return true;
  
    // Skip host-only functions in the CUDA device compilation and device-only
    // functions in the host compilation. Just roughly filter them out based on
    // the function attributes. If there are effectively host-only or device-only
    // ones, their coverage mapping may still be generated.
    if (CGM.getLangOpts().CUDA &&
        ((CGM.getLangOpts().CUDAIsDevice && !D->hasAttr<CUDADeviceAttr>() &&
          !D->hasAttr<CUDAGlobalAttr>()) ||
         (!CGM.getLangOpts().CUDAIsDevice &&
          (D->hasAttr<CUDAGlobalAttr>() ||
           (!D->hasAttr<CUDAHostAttr>() && D->hasAttr<CUDADeviceAttr>())))))
      return true;
  
    // Don't map the functions in system headers.
    const auto &SM = CGM.getContext().getSourceManager();
    auto Loc = D->getBody()->getBeginLoc();
    return SM.isInSystemHeader(Loc);
  }
  
  void CodeGenPGO::emitCounterRegionMapping(const Decl *D) {
    if (skipRegionMappingForDecl(D))
      return;
  
    std::string CoverageMapping;
    llvm::raw_string_ostream OS(CoverageMapping);
    CoverageMappingGen MappingGen(*CGM.getCoverageMapping(),
                                  CGM.getContext().getSourceManager(),
                                  CGM.getLangOpts(), RegionCounterMap.get());
    MappingGen.emitCounterMapping(D, OS);
    OS.flush();
  
    if (CoverageMapping.empty())
      return;
  
    CGM.getCoverageMapping()->addFunctionMappingRecord(
        FuncNameVar, FuncName, FunctionHash, CoverageMapping);
  }
  
  void
  CodeGenPGO::emitEmptyCounterMapping(const Decl *D, StringRef Name,
                                      llvm::GlobalValue::LinkageTypes Linkage) {
    if (skipRegionMappingForDecl(D))
      return;
  
    std::string CoverageMapping;
    llvm::raw_string_ostream OS(CoverageMapping);
    CoverageMappingGen MappingGen(*CGM.getCoverageMapping(),
                                  CGM.getContext().getSourceManager(),
                                  CGM.getLangOpts());
    MappingGen.emitEmptyMapping(D, OS);
    OS.flush();
  
    if (CoverageMapping.empty())
      return;
  
    setFuncName(Name, Linkage);
    CGM.getCoverageMapping()->addFunctionMappingRecord(
        FuncNameVar, FuncName, FunctionHash, CoverageMapping, false);
  }
  
  void CodeGenPGO::computeRegionCounts(const Decl *D) {
    StmtCountMap.reset(new llvm::DenseMap<const Stmt *, uint64_t>);
    ComputeRegionCounts Walker(*StmtCountMap, *this);
    if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D))
      Walker.VisitFunctionDecl(FD);
    else if (const ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(D))
      Walker.VisitObjCMethodDecl(MD);
    else if (const BlockDecl *BD = dyn_cast_or_null<BlockDecl>(D))
      Walker.VisitBlockDecl(BD);
    else if (const CapturedDecl *CD = dyn_cast_or_null<CapturedDecl>(D))
      Walker.VisitCapturedDecl(const_cast<CapturedDecl *>(CD));
  }
  
  void
  CodeGenPGO::applyFunctionAttributes(llvm::IndexedInstrProfReader *PGOReader,
                                      llvm::Function *Fn) {
    if (!haveRegionCounts())
      return;
  
    uint64_t FunctionCount = getRegionCount(nullptr);
    Fn->setEntryCount(FunctionCount);
  }
  
  void CodeGenPGO::emitCounterIncrement(CGBuilderTy &Builder, const Stmt *S,
                                        llvm::Value *StepV) {
    if (!CGM.getCodeGenOpts().hasProfileClangInstr() || !RegionCounterMap)
      return;
    if (!Builder.GetInsertBlock())
      return;
  
    unsigned Counter = (*RegionCounterMap)[S];
    auto *I8PtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext());
  
    llvm::Value *Args[] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
                           Builder.getInt64(FunctionHash),
                           Builder.getInt32(NumRegionCounters),
                           Builder.getInt32(Counter), StepV};
    if (!StepV)
      Builder.CreateCall(CGM.getIntrinsic(llvm::Intrinsic::instrprof_increment),
                         makeArrayRef(Args, 4));
    else
      Builder.CreateCall(
          CGM.getIntrinsic(llvm::Intrinsic::instrprof_increment_step),
          makeArrayRef(Args));
  }
  
  // This method either inserts a call to the profile run-time during
  // instrumentation or puts profile data into metadata for PGO use.
  void CodeGenPGO::valueProfile(CGBuilderTy &Builder, uint32_t ValueKind,
      llvm::Instruction *ValueSite, llvm::Value *ValuePtr) {
  
    if (!EnableValueProfiling)
      return;
  
    if (!ValuePtr || !ValueSite || !Builder.GetInsertBlock())
      return;
  
    if (isa<llvm::Constant>(ValuePtr))
      return;
  
    bool InstrumentValueSites = CGM.getCodeGenOpts().hasProfileClangInstr();
    if (InstrumentValueSites && RegionCounterMap) {
      auto BuilderInsertPoint = Builder.saveIP();
      Builder.SetInsertPoint(ValueSite);
      llvm::Value *Args[5] = {
          llvm::ConstantExpr::getBitCast(FuncNameVar, Builder.getInt8PtrTy()),
          Builder.getInt64(FunctionHash),
          Builder.CreatePtrToInt(ValuePtr, Builder.getInt64Ty()),
          Builder.getInt32(ValueKind),
          Builder.getInt32(NumValueSites[ValueKind]++)
      };
      Builder.CreateCall(
          CGM.getIntrinsic(llvm::Intrinsic::instrprof_value_profile), Args);
      Builder.restoreIP(BuilderInsertPoint);
      return;
    }
  
    llvm::IndexedInstrProfReader *PGOReader = CGM.getPGOReader();
    if (PGOReader && haveRegionCounts()) {
      // We record the top most called three functions at each call site.
      // Profile metadata contains "VP" string identifying this metadata
      // as value profiling data, then a uint32_t value for the value profiling
      // kind, a uint64_t value for the total number of times the call is
      // executed, followed by the function hash and execution count (uint64_t)
      // pairs for each function.
      if (NumValueSites[ValueKind] >= ProfRecord->getNumValueSites(ValueKind))
        return;
  
      llvm::annotateValueSite(CGM.getModule(), *ValueSite, *ProfRecord,
                              (llvm::InstrProfValueKind)ValueKind,
                              NumValueSites[ValueKind]);
  
      NumValueSites[ValueKind]++;
    }
  }
  
  void CodeGenPGO::loadRegionCounts(llvm::IndexedInstrProfReader *PGOReader,
                                    bool IsInMainFile) {
    CGM.getPGOStats().addVisited(IsInMainFile);
    RegionCounts.clear();
    llvm::Expected<llvm::InstrProfRecord> RecordExpected =
        PGOReader->getInstrProfRecord(FuncName, FunctionHash);
    if (auto E = RecordExpected.takeError()) {
      auto IPE = llvm::InstrProfError::take(std::move(E));
      if (IPE == llvm::instrprof_error::unknown_function)
        CGM.getPGOStats().addMissing(IsInMainFile);
      else if (IPE == llvm::instrprof_error::hash_mismatch)
        CGM.getPGOStats().addMismatched(IsInMainFile);
      else if (IPE == llvm::instrprof_error::malformed)
        // TODO: Consider a more specific warning for this case.
        CGM.getPGOStats().addMismatched(IsInMainFile);
      return;
    }
    ProfRecord =
        std::make_unique<llvm::InstrProfRecord>(std::move(RecordExpected.get()));
    RegionCounts = ProfRecord->Counts;
  }
  
  /// Calculate what to divide by to scale weights.
  ///
  /// Given the maximum weight, calculate a divisor that will scale all the
  /// weights to strictly less than UINT32_MAX.
  static uint64_t calculateWeightScale(uint64_t MaxWeight) {
    return MaxWeight < UINT32_MAX ? 1 : MaxWeight / UINT32_MAX + 1;
  }
  
  /// Scale an individual branch weight (and add 1).
  ///
  /// Scale a 64-bit weight down to 32-bits using \c Scale.
  ///
  /// According to Laplace's Rule of Succession, it is better to compute the
  /// weight based on the count plus 1, so universally add 1 to the value.
  ///
  /// \pre \c Scale was calculated by \a calculateWeightScale() with a weight no
  /// greater than \c Weight.
  static uint32_t scaleBranchWeight(uint64_t Weight, uint64_t Scale) {
    assert(Scale && "scale by 0?");
    uint64_t Scaled = Weight / Scale + 1;
    assert(Scaled <= UINT32_MAX && "overflow 32-bits");
    return Scaled;
  }
  
  llvm::MDNode *CodeGenFunction::createProfileWeights(uint64_t TrueCount,
                                                      uint64_t FalseCount) {
    // Check for empty weights.
    if (!TrueCount && !FalseCount)
      return nullptr;
  
    // Calculate how to scale down to 32-bits.
    uint64_t Scale = calculateWeightScale(std::max(TrueCount, FalseCount));
  
    llvm::MDBuilder MDHelper(CGM.getLLVMContext());
    return MDHelper.createBranchWeights(scaleBranchWeight(TrueCount, Scale),
                                        scaleBranchWeight(FalseCount, Scale));
  }
  
  llvm::MDNode *
  CodeGenFunction::createProfileWeights(ArrayRef<uint64_t> Weights) {
    // We need at least two elements to create meaningful weights.
    if (Weights.size() < 2)
      return nullptr;
  
    // Check for empty weights.
    uint64_t MaxWeight = *std::max_element(Weights.begin(), Weights.end());
    if (MaxWeight == 0)
      return nullptr;
  
    // Calculate how to scale down to 32-bits.
    uint64_t Scale = calculateWeightScale(MaxWeight);
  
    SmallVector<uint32_t, 16> ScaledWeights;
    ScaledWeights.reserve(Weights.size());
    for (uint64_t W : Weights)
      ScaledWeights.push_back(scaleBranchWeight(W, Scale));
  
    llvm::MDBuilder MDHelper(CGM.getLLVMContext());
    return MDHelper.createBranchWeights(ScaledWeights);
  }
  
  llvm::MDNode *CodeGenFunction::createProfileWeightsForLoop(const Stmt *Cond,
                                                             uint64_t LoopCount) {
    if (!PGO.haveRegionCounts())
      return nullptr;
    Optional<uint64_t> CondCount = PGO.getStmtCount(Cond);
    if (!CondCount || *CondCount == 0)
      return nullptr;
    return createProfileWeights(LoopCount,
                                std::max(*CondCount, LoopCount) - LoopCount);
  }
  