[PGO] Add Value Profiling for Loop Trip Count (WIP)

[w2yehia]

Summary

This is Work In Progress.
I'm posting here to solicit feedback.
One motivation for doing this is to improve the loop versioning currently done by LoopVectorizer (LoopVectorizePass::processLoop).

Description:
For certain loops, (TBD what kind), we would like to profile the exact trip count and the
frequency of that trip count. In other words, we want to value profile an expression that
represents the trip count of a loop, whenever it is computable.
The instrumentation point is the loop pre-header, and the value profile (VP) metadata (MD)
is appended to the llvm.loop MD which sits on the branch instruction of the latch block.
In order to find or create a loop pre-header, we run the LoopSimplifyPass pass in the
pipeline for the new pass manager.
The logic in LoopInfoPlugin in ValueProfilePlugins.inc determines the instrumentation
point (needed during the -fprofile-generate step) and what to associate the MD (needed
during the -fprofile-use step).
Instead of having the plugin decide the exact instruction for associating the MD to, we allow
the plugin to select a Loop to associate it to, and then in PGOUseFunc::annotateValueSites
in PGOInstrumentation.cpp we call setLoopTripCount(MD) on the Loop object.
This way, the Loop object maintains control (set/get) over what MD is associated to the
loop id MD node (a.k.a. the !llvm.loop MD).

[hoy]

The work is interesting. I'm wondering if it is still ongoing. I haven't looked into the implementation details here yet, but here are a couple basic questions:

1. Does the generated loop MD reflect the average loop trip count per loop run or the accumulated total trip count for all runs of the loop?
2. How does the generated loop MD differ from the synthesized loop tripe count based on the branch_weight metadata?
3. Have you seen a particular loop optimization pass benefits from this work?

Thanks.

[w2yehia]

In D70688#3395357, @hoy wrote:

The work is interesting. I'm wondering if it is still ongoing. I haven't looked into the implementation details here yet, but here are a couple basic questions:

1. Does the generated loop MD reflect the average loop trip count per loop run or the accumulated total trip count for all runs of the loop?
2. How does the generated loop MD differ from the synthesized loop tripe count based on the branch_weight metadata?
3. Have you seen a particular loop optimization pass benefits from this work?

Thanks.

Hi, we currently have this implementation downstream more or less. Feel free to contribute or even take over. I just haven't found the time to push this through further.

1. No, not the average. The loop MD will contain a set of the most frequent trip counts observed, with the frequency of each trip count.
2. implied from (1): the branch_weight MD will give the average trip count, while the loop MD will give exact numbers
3. you first version the code and then knowing the trip count at compile time you can vectorize and any loop optimization that benefits from having a constant trip count.

[wenlei]

Indeed this looks interesting.

How do you maintain the new profile metadata? Trip count can change as you unroll/reroll/vectorize a loop.

The new profile metadata seems disconnected with existing branch weights, which can also derive total trip count. However branch weights are adjusted for optimizations (i.e. scaling for inlining etc), so chances are branch weights derived total trip count can be more accurate in some cases. Do you consider using branch weights derived total trip count to scale trip count value profile (based on histogram's total)?

I'm also curious if you have any perf evaluation done based on this work, i.e. what target and on what workload/benchmark did you see perf improvement through versioning, by how much?

compiler-rt/include/profile/InstrProfData.inc

  * when the raw profile data is read during profile merging.
  *
  * For this remapping the ProfData is used.  ProfData contains both the function
  * name hash and the function address.
  */
 VALUE_PROF_KIND(IPVK_IndirectCallTarget, 0, "indirect call target")
 /* For memory intrinsic functions size profiling. */
 VALUE_PROF_KIND(IPVK_MemOPSize, 1, "memory intrinsic functions size")
+/* For loop versioning opportunities. */
+VALUE_PROF_KIND(IPVK_LoopTripCnt, 2, "loop trip count")
 /* These two kinds must be the last to be
  * declared. This is to make sure the string
  * array created with the template can be
  * indexed with the kind value.
  */
 VALUE_PROF_KIND(IPVK_First, IPVK_IndirectCallTarget, "first")
-VALUE_PROF_KIND(IPVK_Last, IPVK_MemOPSize, "last")
+VALUE_PROF_KIND(IPVK_Last, IPVK_LoopTripCnt, "last")
 
 #undef VALUE_PROF_KIND
 /* VALUE_PROF_KIND end */
 
 /* COVMAP_FUNC_RECORD start */
 /* Definition of member fields of the function record structure in coverage
  * map.
  */

compiler-rt/test/profile/instrprof-looptc.c

+// RUN: %clang_pgogen -fexperimental-new-pass-manager -O2 -mllvm -pgo-loop-trip-count -o %t %s
+// RUN: env LLVM_PROFILE_FILE=%t.1.profraw %run %t 5 || echo ignore rc
+// RUN: env LLVM_PROFILE_FILE=%t.2.profraw %run %t 4 || echo ignore rc
+// RUN: env LLVM_PROFILE_FILE=%t.3.profraw %run %t 4 || echo ignore rc
+// RUN: llvm-profdata merge -text -o %t.proftext %t.1.profraw %t.2.profraw %t.3.profraw
+// FileCheck %s < %t.proftext
+
+int atoi(const char *);
+
+int main(int argc, char *argv[]) {
+  unsigned N = atoi(argv[1]);
+  int c = 0;
+  int ar[100] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+  for (unsigned i = 0; i < N; i += 1)
+    c += ar[i];
+
+  return c;
+}
+
+// CHECK: # Num Value Kinds:
+// CHECK-NEXT: 1
+// CHECK-NEXT: # ValueKind = IPVK_LoopTripCnt:
+// CHECK-NEXT: 2
+// CHECK-NEXT: # NumValueSites:
+// CHECK-NEXT: 1
+// CHECK-NEXT: 2
+// CHECK-NEXT: 4:2
+// CHECK-NEXT: 5:1

llvm/include/llvm/Analysis/LoopInfo.h

 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Allocator.h"
 #include <algorithm>
 #include <utility>
 
+struct InstrProfValueData;
+
 namespace llvm {
 
 class DominatorTree;
 class LoopInfo;
 class Loop;
 class InductionDescriptor;
 class MDNode;
 class MemorySSAUpdater;
public:
   /// Add llvm.loop.unroll.disable to this loop's loop id metadata.
   ///
   /// Remove existing unroll metadata and add unroll disable metadata to
   /// indicate the loop has already been unrolled.  This prevents a loop
   /// from being unrolled more than is directed by a pragma if the loop
   /// unrolling pass is run more than once (which it generally is).
   void setLoopAlreadyUnrolled();
 
+  /// Add the trip count value profile metadata to the llvm.loop metadata of
+  /// this loop.
+  void setLoopTripCount(MDNode *TripCountValueProfile) const;
+
+  /// Return the trip count value profile metadata if available. The metadata is
+  /// stored inside the llvm.loop (MD_loop) metadata.
+  MDNode *getLoopTripCount() const;
+
+  /// Fetch the top \p MaxNumOfValues trip counts based on value profiling info.
+  /// Populate the \p ValueData array with {value,count} pairs, where `value` is
+  /// a profiled/recorded value of this loop's trip count, and `count` is the
+  /// corresponding number of times this value appears in the training run. Also
+  /// set \p NumVals to the number of values fetched (should be less than or
+  /// equal to \p MaxNumOfValues), and set \p TotalCount to the total number of
+  /// trip counts recorded for this loop (i.e. the number of times the loop
+  /// pre-header executed).
+  /// Returns false if no profile data exist, true otherwise.
+  bool getLoopTripCount(uint32_t MaxNumOfValues,
+                        SmallVectorImpl<InstrProfValueData> &ValueData,
+                        uint32_t &NumVals, uint64_t &TotalCount);
+
   void dump() const;
   void dumpVerbose() const;
 
   /// Return the debug location of the start of this loop.
   /// This looks for a BB terminating instruction with a known debug
   /// location by looking at the preheader and header blocks. If it
   /// cannot find a terminating instruction with location information,
   /// it returns an unknown location.

 ///
 /// This can be used when no follow-up loop attributes are defined
 /// (llvm::makeFollowupLoopID returning None) to stop transformations to be
 /// applied again.
 ///
 /// @param Context        The LLVMContext in which to create the new LoopID.
 /// @param OrigLoopID     The original LoopID; can be nullptr if the original
 ///                       loop has no LoopID.
-/// @param RemovePrefixes Remove all loop attributes that have these prefixes.
-///                       Use to remove metadata of the transformation that has
-///                       been applied.
 /// @param AddAttrs       Add these loop attributes to the new LoopID.
 ///
+/// @param RemovePred     A predicate to test each metadata operand of the
+///                       LoopID, and if true then remove that metadata.
 /// @return A new LoopID that can be applied using Loop::setLoopID().
 llvm::MDNode *
 makePostTransformationMetadata(llvm::LLVMContext &Context, MDNode *OrigLoopID,
-                               llvm::ArrayRef<llvm::StringRef> RemovePrefixes,
-                               llvm::ArrayRef<llvm::MDNode *> AddAttrs);
+                               ArrayRef<MDNode *> AddAttrs,
+                               function_ref<bool(Metadata *)> RemovePred);
 
+/// A special case of the above function, where the predicate returns true if
+/// the metadata operand is an MDString that has a prefix from the given list
+/// of prefixes (the array  \p RemovePrefixes)
+llvm::MDNode *makePostTransformationMetadata(llvm::LLVMContext &Context,
+                                             MDNode *OrigLoopID,
+                                             ArrayRef<StringRef> RemovePrefixes,
+                                             ArrayRef<MDNode *> AddAttrs);
 } // End llvm namespace
 
 #endif

llvm/include/llvm/ProfileData/InstrProf.h

void annotateValueSite(Module &M, Instruction &Inst,
                        InstrProfValueKind ValueKind, uint32_t SiteIndx,
                        uint32_t MaxMDCount = 3);
 
 /// Same as the above interface but using an ArrayRef, as well as \p Sum.
 void annotateValueSite(Module &M, Instruction &Inst,
                        ArrayRef<InstrProfValueData> VDs, uint64_t Sum,
                        InstrProfValueKind ValueKind, uint32_t MaxMDCount);
 
+/// Get the value profile data for value site \p SiteIdx from \p InstrProfR,
+/// extracting up to \p MaxMDCount number of records per value site.
+MDNode *createValueProfileMD(Module &M, const InstrProfRecord &InstrProfR,
+                             InstrProfValueKind ValueKind, uint32_t SiteIdx,
+                             uint32_t MaxMDCount);
+
+/// Same as the above interface but using an ArrayRef, as well as \p Sum.
+MDNode *createValueProfileMD(LLVMContext &Ctx, ArrayRef<InstrProfValueData> VDs,
+                             uint64_t Sum, InstrProfValueKind ValueKind,
+                             uint32_t MaxMDCount);
+
+/// Return true if this a Value Profiling metadata node.
+bool isValueProfMD(MDNode *MD, InstrProfValueKind ValueKind);
+
 /// Extract the value profile data from \p Inst which is annotated with
 /// value profile meta data. Return false if there is no value data annotated,
 /// otherwise  return true.
 bool getValueProfDataFromInst(const Instruction &Inst,
                               InstrProfValueKind ValueKind,
                               uint32_t MaxNumValueData,
                               InstrProfValueData ValueData[],
                               uint32_t &ActualNumValueData, uint64_t &TotalC);
 
+/// Extract the value profile data from the given metadata. Return true if
+/// successful.
+bool getValueProfDataFromMD(const MDNode *MD, uint32_t MaxNumValueData,
+                            InstrProfValueData ValueData[],
+                            uint32_t &ActualNumValueData, uint64_t &TotalC);
+
 inline StringRef getPGOFuncNameMetadataName() { return "PGOFuncName"; }
 
 /// Return the PGOFuncName meta data associated with a function.
 MDNode *getPGOFuncNameMetadata(const Function &F);
 
 /// Create the PGOFuncName meta data if PGOFuncName is different from
 /// function's raw name. This should only apply to internal linkage functions
 /// declared by users only.
struct InstrProfRecord {
   void overlapValueProfData(uint32_t ValueKind, InstrProfRecord &Src,
                             OverlapStats &Overlap,
                             OverlapStats &FuncLevelOverlap);
 
 private:
   struct ValueProfData {
     std::vector<InstrProfValueSiteRecord> IndirectCallSites;
     std::vector<InstrProfValueSiteRecord> MemOPSizes;
+    std::vector<InstrProfValueSiteRecord> LoopTCSites;
   };
   std::unique_ptr<ValueProfData> ValueData;
 
   MutableArrayRef<InstrProfValueSiteRecord>
   getValueSitesForKind(uint32_t ValueKind) {
     // Cast to /add/ const (should be an implicit_cast, ideally, if that's ever
     // implemented in LLVM) to call the const overload of this function, then
     // cast away the constness from the result.
     auto AR = const_cast<const InstrProfRecord *>(this)->getValueSitesForKind(
         ValueKind);
     return makeMutableArrayRef(
         const_cast<InstrProfValueSiteRecord *>(AR.data()), AR.size());
   }
   ArrayRef<InstrProfValueSiteRecord>
   getValueSitesForKind(uint32_t ValueKind) const {
     if (!ValueData)
       return None;
     switch (ValueKind) {
     case IPVK_IndirectCallTarget:
       return ValueData->IndirectCallSites;
     case IPVK_MemOPSize:
       return ValueData->MemOPSizes;
+    case IPVK_LoopTripCnt:
+      return ValueData->LoopTCSites;
     default:
       llvm_unreachable("Unknown value kind!");
     }
   }
 
   std::vector<InstrProfValueSiteRecord> &
   getOrCreateValueSitesForKind(uint32_t ValueKind) {
     if (!ValueData)
       ValueData = std::make_unique<ValueProfData>();
     switch (ValueKind) {
     case IPVK_IndirectCallTarget:
       return ValueData->IndirectCallSites;
     case IPVK_MemOPSize:
       return ValueData->MemOPSizes;
+    case IPVK_LoopTripCnt:
+      return ValueData->LoopTCSites;
     default:
       llvm_unreachable("Unknown value kind!");
     }
   }
 
   // Map indirect call target name hash to name string.
   uint64_t remapValue(uint64_t Value, uint32_t ValueKind,
                       InstrProfSymtab *SymTab);

llvm/include/llvm/ProfileData/InstrProfData.inc

  * when the raw profile data is read during profile merging.
  *
  * For this remapping the ProfData is used.  ProfData contains both the function
  * name hash and the function address.
  */
 VALUE_PROF_KIND(IPVK_IndirectCallTarget, 0, "indirect call target")
 /* For memory intrinsic functions size profiling. */
 VALUE_PROF_KIND(IPVK_MemOPSize, 1, "memory intrinsic functions size")
+/* For loop versioning opportunities. */
+VALUE_PROF_KIND(IPVK_LoopTripCnt, 2, "loop trip count")
+
 /* These two kinds must be the last to be
  * declared. This is to make sure the string
  * array created with the template can be
  * indexed with the kind value.
  */
 VALUE_PROF_KIND(IPVK_First, IPVK_IndirectCallTarget, "first")
-VALUE_PROF_KIND(IPVK_Last, IPVK_MemOPSize, "last")
+VALUE_PROF_KIND(IPVK_Last, IPVK_LoopTripCnt, "last")
 
 #undef VALUE_PROF_KIND
 /* VALUE_PROF_KIND end */
 
 /* COVMAP_FUNC_RECORD start */
 /* Definition of member fields of the function record structure in coverage
  * map.
  */

llvm/lib/Analysis/LoopInfo.cpp

 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/InitializePasses.h"
+#include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 using namespace llvm;
 
 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
 template class llvm::LoopBase<BasicBlock, Loop>;

 MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
   return findOptionMDForLoopID(TheLoop->getLoopID(), Name);
 }
 
 bool llvm::isValidAsAccessGroup(MDNode *Node) {
   return Node->getNumOperands() == 0 && Node->isDistinct();
 }
 
+void Loop::setLoopTripCount(MDNode *TripCountValueProfile) const {
+  assert(isValueProfMD(TripCountValueProfile, IPVK_LoopTripCnt) &&
+         "Expecting a Value Profile metadata");
+  LLVMContext &Context = getHeader()->getContext();
+
+  // Remove any existing trip count value profile nodes.
+  auto RemovePred = [](Metadata *Op) {
+    MDNode *MD = dyn_cast<MDNode>(Op);
+    return MD && isValueProfMD(MD, IPVK_LoopTripCnt);
+  };
+
+  MDNode *NewLoopID = makePostTransformationMetadata(
+      Context, getLoopID(), {TripCountValueProfile}, RemovePred);
+  setLoopID(NewLoopID);
+}
+
+MDNode *Loop::getLoopTripCount() const {
+  MDNode *LoopID = getLoopID();
+  if (!LoopID)
+    return nullptr;
+
+  for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
+    MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
+    if (MD && isValueProfMD(MD, IPVK_LoopTripCnt))
+      return MD;
+  }
+  return nullptr;
+}
+
+bool Loop::getLoopTripCount(uint32_t MaxNumValueData,
+                            SmallVectorImpl<InstrProfValueData> &ValueData,
+                            uint32_t &NumVals, uint64_t &TotalCount) {
+  MDNode *LoopTC = getLoopTripCount();
+  if (!LoopTC)
+    return false;
+
+  ValueData.reserve(MaxNumValueData);
+  return getValueProfDataFromMD(LoopTC, MaxNumValueData, ValueData.data(),
+                                NumVals, TotalCount);
+}
+
 MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
                                              MDNode *OrigLoopID,
                                              ArrayRef<StringRef> RemovePrefixes,
                                              ArrayRef<MDNode *> AddAttrs) {
+  auto RemovePred = [&RemovePrefixes](Metadata *Op) {
+    if (MDNode *MD = dyn_cast<MDNode>(Op))
+      if (const MDString *S = dyn_cast<MDString>(MD->getOperand(0)))
+        return llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
+          return S->getString().startswith(Prefix);
+        });
+    return false;
+  };
+  return makePostTransformationMetadata(Context, OrigLoopID, AddAttrs,
+                                        RemovePred);
+}
+
+MDNode *llvm::makePostTransformationMetadata(
+    LLVMContext &Context, MDNode *OrigLoopID, ArrayRef<MDNode *> AddAttrs,
+    function_ref<bool(Metadata *)> RemovePred) {
   // First remove any existing loop metadata related to this transformation.
   SmallVector<Metadata *, 4> MDs;
 
   // Reserve first location for self reference to the LoopID metadata node.
   TempMDTuple TempNode = MDNode::getTemporary(Context, None);
   MDs.push_back(TempNode.get());
 
   // Remove metadata for the transformation that has been applied or that became
   // outdated.
   if (OrigLoopID) {
     for (unsigned i = 1, ie = OrigLoopID->getNumOperands(); i < ie; ++i) {
-      bool IsVectorMetadata = false;
       Metadata *Op = OrigLoopID->getOperand(i);
-      if (MDNode *MD = dyn_cast<MDNode>(Op)) {
-        const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
-        if (S)
-          IsVectorMetadata =
-              llvm::any_of(RemovePrefixes, [S](StringRef Prefix) -> bool {
-                return S->getString().startswith(Prefix);
-              });
-      }
-      if (!IsVectorMetadata)
+      if (!RemovePred(Op))
         MDs.push_back(Op);
     }
   }
 
   // Add metadata to avoid reapplying a transformation, such as
   // llvm.loop.unroll.disable and llvm.loop.isvectorized.
   MDs.append(AddAttrs.begin(), AddAttrs.end());
 

llvm/lib/Passes/PassBuilder.cpp

if (!isOptimizingForSize(Level) && !IsCS) {
     CGPipeline.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM)));
 
     MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPipeline)));
 
     // Delete anything that is now dead to make sure that we don't instrument
     // dead code. Instrumentation can end up keeping dead code around and
     // dramatically increase code size.
     MPM.addPass(GlobalDCEPass());
+    MPM.addPass(createModuleToFunctionPassAdaptor(LoopSimplifyPass()));
   }
 
   if (!RunProfileGen) {
     assert(!ProfileFile.empty() && "Profile use expecting a profile file!");
     MPM.addPass(PGOInstrumentationUse(ProfileFile, ProfileRemappingFile, IsCS));
     // Cache ProfileSummaryAnalysis once to avoid the potential need to insert
     // RequireAnalysisPass for PSI before subsequent non-module passes.
     MPM.addPass(RequireAnalysisPass<ProfileSummaryAnalysis, Module>());

llvm/lib/ProfileData/InstrProf.cpp

 uint64_t InstrProfRecord::remapValue(uint64_t Value, uint32_t ValueKind,
                                      InstrProfSymtab *SymTab) {
   if (!SymTab)
     return Value;
 
   if (ValueKind == IPVK_IndirectCallTarget)
     return SymTab->getFunctionHashFromAddress(Value);
 
+  assert((ValueKind == IPVK_MemOPSize || ValueKind == IPVK_LoopTripCnt) &&
+         "unexpected Value Profile kind");
   return Value;
 }
 
 void InstrProfRecord::addValueData(uint32_t ValueKind, uint32_t Site,
                                    InstrProfValueData *VData, uint32_t N,
                                    InstrProfSymtab *ValueMap) {
   for (uint32_t I = 0; I < N; I++) {
     VData[I].Value = remapValue(VData[I].Value, ValueKind, ValueMap);
void ValueProfData::swapBytesFromHost(support::endianness Endianness) {
   sys::swapByteOrder<uint32_t>(TotalSize);
   sys::swapByteOrder<uint32_t>(NumValueKinds);
 }
 
 void annotateValueSite(Module &M, Instruction &Inst,
                        const InstrProfRecord &InstrProfR,
                        InstrProfValueKind ValueKind, uint32_t SiteIdx,
                        uint32_t MaxMDCount) {
+
+  MDNode *MD =
+      createValueProfileMD(M, InstrProfR, ValueKind, SiteIdx, MaxMDCount);
+  if (MD)
+    Inst.setMetadata(LLVMContext::MD_prof, MD);
+}
+
+MDNode *createValueProfileMD(Module &M, const InstrProfRecord &InstrProfR,
+                             InstrProfValueKind ValueKind, uint32_t SiteIdx,
+                             uint32_t MaxMDCount) {
   uint32_t NV = InstrProfR.getNumValueDataForSite(ValueKind, SiteIdx);
   if (!NV)
-    return;
+    return nullptr;
 
   uint64_t Sum = 0;
   std::unique_ptr<InstrProfValueData[]> VD =
       InstrProfR.getValueForSite(ValueKind, SiteIdx, &Sum);
 
   ArrayRef<InstrProfValueData> VDs(VD.get(), NV);
-  annotateValueSite(M, Inst, VDs, Sum, ValueKind, MaxMDCount);
+  return createValueProfileMD(M.getContext(), VDs, Sum, ValueKind, MaxMDCount);
 }
 
 void annotateValueSite(Module &M, Instruction &Inst,
                        ArrayRef<InstrProfValueData> VDs,
                        uint64_t Sum, InstrProfValueKind ValueKind,
                        uint32_t MaxMDCount) {
-  LLVMContext &Ctx = M.getContext();
+  MDNode *MD =
+      createValueProfileMD(M.getContext(), VDs, Sum, ValueKind, MaxMDCount);
+  Inst.setMetadata(LLVMContext::MD_prof, MD);
+}
+
+MDNode *createValueProfileMD(LLVMContext &Ctx, ArrayRef<InstrProfValueData> VDs,
+                             uint64_t Sum, InstrProfValueKind ValueKind,
+                             uint32_t MaxMDCount) {
   MDBuilder MDHelper(Ctx);
   SmallVector<Metadata *, 3> Vals;
   // Tag
   Vals.push_back(MDHelper.createString("VP"));
   // Value Kind
   Vals.push_back(MDHelper.createConstant(
       ConstantInt::get(Type::getInt32Ty(Ctx), ValueKind)));
   // Total Count
   Vals.push_back(
       MDHelper.createConstant(ConstantInt::get(Type::getInt64Ty(Ctx), Sum)));
 
   // Value Profile Data
   uint32_t MDCount = MaxMDCount;
   for (auto &VD : VDs) {
     Vals.push_back(MDHelper.createConstant(
         ConstantInt::get(Type::getInt64Ty(Ctx), VD.Value)));
     Vals.push_back(MDHelper.createConstant(
         ConstantInt::get(Type::getInt64Ty(Ctx), VD.Count)));
     if (--MDCount == 0)
       break;
   }
-  Inst.setMetadata(LLVMContext::MD_prof, MDNode::get(Ctx, Vals));
+  return MDNode::get(Ctx, Vals);
 }
 
-bool getValueProfDataFromInst(const Instruction &Inst,
-                              InstrProfValueKind ValueKind,
-                              uint32_t MaxNumValueData,
-                              InstrProfValueData ValueData[],
-                              uint32_t &ActualNumValueData, uint64_t &TotalC) {
-  MDNode *MD = Inst.getMetadata(LLVMContext::MD_prof);
-  if (!MD)
-    return false;
-
+bool isValueProfMD(MDNode *MD, InstrProfValueKind ValueKind) {
   unsigned NOps = MD->getNumOperands();
 
   if (NOps < 5)
     return false;
 
   // Operand 0 is a string tag "VP":
   MDString *Tag = cast<MDString>(MD->getOperand(0));
   if (!Tag)
     return false;
 
   if (!Tag->getString().equals("VP"))
     return false;
 
   // Now check kind:
   ConstantInt *KindInt = mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
   if (!KindInt)
     return false;
   if (KindInt->getZExtValue() != ValueKind)
     return false;
 
+  return true;
+}
+
+bool getValueProfDataFromInst(const Instruction &Inst,
+                              InstrProfValueKind ValueKind,
+                              uint32_t MaxNumValueData,
+                              InstrProfValueData ValueData[],
+                              uint32_t &ActualNumValueData, uint64_t &TotalC) {
+  MDNode *MD = Inst.getMetadata(LLVMContext::MD_prof);
+  if (!MD || !isValueProfMD(MD, ValueKind))
+    return false;
+
+  return getValueProfDataFromMD(MD, MaxNumValueData, ValueData,
+                                ActualNumValueData, TotalC);
+}
+
+bool getValueProfDataFromMD(const MDNode *MD, uint32_t MaxNumValueData,
+                            InstrProfValueData ValueData[],
+                            uint32_t &ActualNumValueData, uint64_t &TotalC) {
   // Get total count
   ConstantInt *TotalCInt = mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
   if (!TotalCInt)
     return false;
   TotalC = TotalCInt->getZExtValue();
 
   ActualNumValueData = 0;
 
-  for (unsigned I = 3; I < NOps; I += 2) {
+  for (unsigned I = 3, NOps = MD->getNumOperands(); I < NOps; I += 2) {
     if (ActualNumValueData >= MaxNumValueData)
       break;
     ConstantInt *Value = mdconst::dyn_extract<ConstantInt>(MD->getOperand(I));
     ConstantInt *Count =
         mdconst::dyn_extract<ConstantInt>(MD->getOperand(I + 1));
     if (!Value || !Count)
       return false;
     ValueData[ActualNumValueData].Value = Value->getZExtValue();

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
+#include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Comdat.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DiagnosticInfo.h"

 #include "llvm/Support/DOTGraphTraits.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/GraphWriter.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/MisExpect.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <memory>
 #include <numeric>
 #include <string>
 #include <unordered_map>

 
 // Command line option to set the maximum number of value annotations
 // to write to the metadata for a single memop intrinsic.
 static cl::opt<unsigned> MaxNumMemOPAnnotations(
     "memop-max-annotations", cl::init(4), cl::Hidden, cl::ZeroOrMore,
     cl::desc("Max number of preicise value annotations for a single memop"
              "intrinsic"));
 
+// Command line option to set the maximum number of value annotations
+// to write to the metadata for a single Loop-Trip-Count value profile site.
+static cl::opt<unsigned> MaxNumLoopTCAnnotations(
+    "loop-trip-count-max-annotations", cl::init(4), cl::Hidden, cl::ZeroOrMore,
+    cl::desc("Max number of precise value annotations for "
+             "the trip count of a loop"));
+
 // Command line option to control appending FunctionHash to the name of a COMDAT
 // function. This is to avoid the hash mismatch caused by the preinliner.
 static cl::opt<bool> DoComdatRenaming(
     "do-comdat-renaming", cl::init(false), cl::Hidden,
     cl::desc("Append function hash to the name of COMDAT function to avoid "
              "function hash mismatch due to the preinliner"));
 
 // Command line option to enable/disable the warning about missing profile

 // Emit branch probability as optimization remarks.
 static cl::opt<bool>
     EmitBranchProbability("pgo-emit-branch-prob", cl::init(false), cl::Hidden,
                           cl::desc("When this option is on, the annotated "
                                    "branch probability will be emitted as "
                                    "optimization remarks: -{Rpass|"
                                    "pass-remarks}=pgo-instrumentation"));
 
+// Control loop trip count profiling instrumentation.
+static cl::opt<bool>
+    LoopTC("pgo-loop-trip-count", cl::init(false), cl::Hidden,
+           cl::desc("Disable loop trip count profiling instrumentation when "
+                    "this option is ON"));
+
 // Command line option to turn on CFG dot dump after profile annotation.
 // Defined in Analysis/BlockFrequencyInfo.cpp:  -pgo-view-counts
 extern cl::opt<PGOViewCountsType> PGOViewCounts;
 
 // Command line option to specify the name of the function for CFG dump
 // Defined in Analysis/BlockFrequencyInfo.cpp:  -view-bfi-func-name=
 extern cl::opt<std::string> ViewBlockFreqFuncName;
 

 
 private:
   // Is this is context-sensitive instrumentation.
   bool IsCS;
   bool runOnModule(Module &M) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<BlockFrequencyInfoWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
   }
 };
 
 class PGOInstrumentationUseLegacyPass : public ModulePass {
 public:
   static char ID;
 
   // Provide the profile filename as the parameter.
private:
   // Is this is context-sensitive instrumentation use.
   bool IsCS;
 
   bool runOnModule(Module &M) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<ProfileSummaryInfoWrapperPass>();
     AU.addRequired<BlockFrequencyInfoWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
   }
 };
 
 class PGOInstrumentationGenCreateVarLegacyPass : public ModulePass {
 public:
   static char ID;
   StringRef getPassName() const override {
     return "PGOInstrumentationGenCreateVarPass";

 } // end anonymous namespace
 
 char PGOInstrumentationGenLegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(PGOInstrumentationGenLegacyPass, "pgo-instr-gen",
                       "PGO instrumentation.", false, false)
 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(PGOInstrumentationGenLegacyPass, "pgo-instr-gen",
                     "PGO instrumentation.", false, false)
 
 ModulePass *llvm::createPGOInstrumentationGenLegacyPass(bool IsCS) {
   return new PGOInstrumentationGenLegacyPass(IsCS);
 }
 
 char PGOInstrumentationUseLegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(PGOInstrumentationUseLegacyPass, "pgo-instr-use",
                       "Read PGO instrumentation profile.", false, false)
 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
 INITIALIZE_PASS_END(PGOInstrumentationUseLegacyPass, "pgo-instr-use",
                     "Read PGO instrumentation profile.", false, false)
 
 ModulePass *llvm::createPGOInstrumentationUseLegacyPass(StringRef Filename,
                                                         bool IsCS) {
   return new PGOInstrumentationUseLegacyPass(Filename.str(), IsCS);
 }
public:
 
   // Dump edges and BB information.
   void dumpInfo(std::string Str = "") const {
     MST.dumpEdges(dbgs(), Twine("Dump Function ") + FuncName + " Hash: " +
                               Twine(FunctionHash) + "\t" + Str);
   }
 
   FuncPGOInstrumentation(
-      Function &Func,
+      Function &Func, LoopInfo &LI,
       std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
       bool CreateGlobalVar = false, BranchProbabilityInfo *BPI = nullptr,
-      BlockFrequencyInfo *BFI = nullptr, bool IsCS = false)
-      : F(Func), IsCS(IsCS), ComdatMembers(ComdatMembers), VPC(Func),
+      BlockFrequencyInfo *BFI = nullptr, ScalarEvolution *SE = nullptr,
+      bool IsCS = false)
+      : F(Func), IsCS(IsCS), ComdatMembers(ComdatMembers), VPC(Func, LI, SE),
         ValueSites(IPVK_Last + 1), SIVisitor(Func), MST(F, BPI, BFI) {
+    // Run Loop trip count profiling first because it might insert selects.
+    if (LoopTC)
+      ValueSites[IPVK_LoopTripCnt] = VPC.get(IPVK_LoopTripCnt);
+
     // This should be done before CFG hash computation.
     SIVisitor.countSelects(Func);
     ValueSites[IPVK_MemOPSize] = VPC.get(IPVK_MemOPSize);
     if (!IsCS) {
       NumOfPGOSelectInsts += SIVisitor.getNumOfSelectInsts();
       NumOfPGOMemIntrinsics += ValueSites[IPVK_MemOPSize].size();
       NumOfPGOBB += MST.BBInfos.size();
       ValueSites[IPVK_IndirectCallTarget] = VPC.get(IPVK_IndirectCallTarget);
BasicBlock *FuncPGOInstrumentation<Edge, BBInfo>::getInstrBB(Edge *E) {
 
   return canInstrument(InstrBB);
 }
 
 // Visit all edge and instrument the edges not in MST, and do value profiling.
 // Critical edges will be split.
 static void instrumentOneFunc(
     Function &F, Module *M, BranchProbabilityInfo *BPI, BlockFrequencyInfo *BFI,
+    LoopInfo *LI, ScalarEvolution *SE,
     std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
     bool IsCS) {
   // Split indirectbr critical edges here before computing the MST rather than
   // later in getInstrBB() to avoid invalidating it.
   SplitIndirectBrCriticalEdges(F, BPI, BFI);
 
-  FuncPGOInstrumentation<PGOEdge, BBInfo> FuncInfo(F, ComdatMembers, true, BPI,
-                                                   BFI, IsCS);
+  FuncPGOInstrumentation<PGOEdge, BBInfo> FuncInfo(F, *LI, ComdatMembers, true,
+                                                   BPI, BFI, SE, IsCS);
   std::vector<BasicBlock *> InstrumentBBs;
   FuncInfo.getInstrumentBBs(InstrumentBBs);
   unsigned NumCounters =
       InstrumentBBs.size() + FuncInfo.SIVisitor.getNumOfSelectInsts();
 
   uint32_t I = 0;
   Type *I8PtrTy = Type::getInt8PtrTy(M->getContext());
   for (auto *InstrBB : InstrumentBBs) {
static uint64_t sumEdgeCount(const ArrayRef<PGOUseEdge *> Edges) {
   }
   return Total;
 }
 
 namespace {
 
 class PGOUseFunc {
 public:
-  PGOUseFunc(Function &Func, Module *Modu,
+  PGOUseFunc(Function &Func, Module *Modu, LoopInfo &LI,
              std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
              BranchProbabilityInfo *BPI, BlockFrequencyInfo *BFIin,
-             ProfileSummaryInfo *PSI, bool IsCS)
+             ProfileSummaryInfo *PSI, ScalarEvolution *SE, bool IsCS)
       : F(Func), M(Modu), BFI(BFIin), PSI(PSI),
-        FuncInfo(Func, ComdatMembers, false, BPI, BFIin, IsCS),
+        FuncInfo(Func, LI, ComdatMembers, false, BPI, BFIin, SE, IsCS),
         FreqAttr(FFA_Normal), IsCS(IsCS) {}
 
   // Read counts for the instrumented BB from profile.
   bool readCounters(IndexedInstrProfReader *PGOReader, bool &AllZeros);
 
   // Populate the counts for all BBs.
   void populateCounters();
 

 
 void SelectInstVisitor::visitSelectInst(SelectInst &SI) {
   if (!PGOInstrSelect)
     return;
   // FIXME: do not handle this yet.
   if (SI.getCondition()->getType()->isVectorTy())
     return;
 
+  // Other instrumentation kinds might insert selects, skip them.
+  // FIXME: There is a tiny chance this might skip user selects.
+  if (SI.use_empty() ||
+      llvm::all_of(SI.users(), [](User *U) {
+        return U->use_empty() &&
+               isa<Instruction>(U) &&
+               wouldInstructionBeTriviallyDead(cast<Instruction>(U));
+      })) {
+    LLVM_DEBUG(dbgs() << "skipping unused " << SI << "\n");
+    return;
+  }
+
   switch (Mode) {
   case VM_counting:
     NSIs++;
     return;
   case VM_instrument:
     instrumentOneSelectInst(SI);
     return;
   case VM_annotate:
Ctx.diagnose(DiagnosticInfoPGOProfile(
         Twine("Inconsistent number of value sites for ") +
             Twine(ValueProfKindDescr[Kind]) +
             Twine(" profiling in \"") + F.getName().str() +
             Twine("\", possibly due to the use of a stale profile."),
         DS_Warning));
     return;
   }
 
+  uint32_t MaxMDCount = Kind == IPVK_MemOPSize   ? MaxNumMemOPAnnotations :
+                        Kind == IPVK_LoopTripCnt ? MaxNumLoopTCAnnotations
+                                                 : MaxNumAnnotations;
+  InstrProfValueKind K = static_cast<InstrProfValueKind>(Kind);
   for (VPCandidateInfo &I : ValueSites) {
     LLVM_DEBUG(dbgs() << "Read one value site profile (kind = " << Kind
                       << "): Index = " << ValueSiteIndex << " out of "
                       << NumValueSites << "\n");
-    annotateValueSite(*M, *I.AnnotatedInst, ProfileRecord,
-                      static_cast<InstrProfValueKind>(Kind), ValueSiteIndex,
-                      Kind == IPVK_MemOPSize ? MaxNumMemOPAnnotations
-                                             : MaxNumAnnotations);
+    if (I.MDHolder.is<Instruction *>())
+      annotateValueSite(*M, *I.MDHolder.get<Instruction *>(), ProfileRecord, K,
+                        ValueSiteIndex, MaxMDCount);
+    else if (MDNode *MD = createValueProfileMD(*M, ProfileRecord, K,
+                                               ValueSiteIndex, MaxMDCount))
+      I.MDHolder.get<Loop *>()->setLoopTripCount(MD);
+      
     ValueSiteIndex++;
   }
 }
 
 // Collect the set of members for each Comdat in module M and store
 // in ComdatMembers.
 static void collectComdatMembers(
     Module &M,
     std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
   if (!DoComdatRenaming)
     return;
   for (Function &F : M)
     if (Comdat *C = F.getComdat())
       ComdatMembers.insert(std::make_pair(C, &F));
   for (GlobalVariable &GV : M.globals())
     if (Comdat *C = GV.getComdat())
       ComdatMembers.insert(std::make_pair(C, &GV));
   for (GlobalAlias &GA : M.aliases())
     if (Comdat *C = GA.getComdat())
       ComdatMembers.insert(std::make_pair(C, &GA));
 }
 
 static bool InstrumentAllFunctions(
     Module &M, function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
-    function_ref<BlockFrequencyInfo *(Function &)> LookupBFI, bool IsCS) {
+    function_ref<BlockFrequencyInfo *(Function &)> LookupBFI,
+    function_ref<LoopInfo *(Function &)> LookupLI,
+    function_ref<ScalarEvolution *(Function &)> LookupSE, bool IsCS) {
   // For the context-sensitve instrumentation, we should have a separated pass
   // (before LTO/ThinLTO linking) to create these variables.
   if (!IsCS)
     createIRLevelProfileFlagVar(M, /* IsCS */ false);
   std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
   collectComdatMembers(M, ComdatMembers);
 
   for (auto &F : M) {
     if (F.isDeclaration())
       continue;
     auto *BPI = LookupBPI(F);
     auto *BFI = LookupBFI(F);
-    instrumentOneFunc(F, &M, BPI, BFI, ComdatMembers, IsCS);
+    auto *LI = LookupLI(F);
+    auto *SE = LookupSE(F);
+    instrumentOneFunc(F, &M, BPI, BFI, LI, SE, ComdatMembers, IsCS);
   }
   return true;
 }
 
 PreservedAnalyses
 PGOInstrumentationGenCreateVar::run(Module &M, ModuleAnalysisManager &AM) {
   createProfileFileNameVar(M, CSInstrName);
   createIRLevelProfileFlagVar(M, /* IsCS */ true);
   return PreservedAnalyses::all();
 }
 
 bool PGOInstrumentationGenLegacyPass::runOnModule(Module &M) {
   if (skipModule(M))
     return false;
 
   auto LookupBPI = [this](Function &F) {
     return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
   };
   auto LookupBFI = [this](Function &F) {
     return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
   };
-  return InstrumentAllFunctions(M, LookupBPI, LookupBFI, IsCS);
+  auto LookupLI = [this](Function &F) {
+    return &this->getAnalysis<LoopInfoWrapperPass>(F).getLoopInfo();
+  };
+  auto LookupSE = [](Function &F) { return nullptr; };
+
+  return InstrumentAllFunctions(M, LookupBPI, LookupBFI, LookupLI, LookupSE,
+                                IsCS);
 }
 
 PreservedAnalyses PGOInstrumentationGen::run(Module &M,
                                              ModuleAnalysisManager &AM) {
   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
   auto LookupBPI = [&FAM](Function &F) {
     return &FAM.getResult<BranchProbabilityAnalysis>(F);
   };
 
   auto LookupBFI = [&FAM](Function &F) {
     return &FAM.getResult<BlockFrequencyAnalysis>(F);
   };
-
-  if (!InstrumentAllFunctions(M, LookupBPI, LookupBFI, IsCS))
+  auto LookupLI = [&FAM](Function &F) {
+    return &FAM.getResult<LoopAnalysis>(F);
+  };
+  auto LookupSE = [&FAM](Function &F) {
+    return &FAM.getResult<ScalarEvolutionAnalysis>(F);
+  };
+  if (!InstrumentAllFunctions(M, LookupBPI, LookupBFI, LookupLI, LookupSE,
+                              IsCS))
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }
 
 static bool annotateAllFunctions(
     Module &M, StringRef ProfileFileName, StringRef ProfileRemappingFileName,
     function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
     function_ref<BlockFrequencyInfo *(Function &)> LookupBFI,
+    function_ref<LoopInfo *(Function &)> LookupLI,
+    function_ref<ScalarEvolution *(Function &)> LookupSE,
     ProfileSummaryInfo *PSI, bool IsCS) {
   LLVM_DEBUG(dbgs() << "Read in profile counters: ");
   auto &Ctx = M.getContext();
   // Read the counter array from file.
   auto ReaderOrErr =
       IndexedInstrProfReader::create(ProfileFileName, ProfileRemappingFileName);
   if (Error E = ReaderOrErr.takeError()) {
     handleAllErrors(std::move(E), [&](const ErrorInfoBase &EI) {
static bool annotateAllFunctions(
   collectComdatMembers(M, ComdatMembers);
   std::vector<Function *> HotFunctions;
   std::vector<Function *> ColdFunctions;
   for (auto &F : M) {
     if (F.isDeclaration())
       continue;
     auto *BPI = LookupBPI(F);
     auto *BFI = LookupBFI(F);
+    auto *LI = LookupLI(F);
+    auto *SE = LookupSE(F);
+    assert(LI && "need a LoopInfo");
     // Split indirectbr critical edges here before computing the MST rather than
     // later in getInstrBB() to avoid invalidating it.
     SplitIndirectBrCriticalEdges(F, BPI, BFI);
-    PGOUseFunc Func(F, &M, ComdatMembers, BPI, BFI, PSI, IsCS);
+    PGOUseFunc Func(F, &M, *LI, ComdatMembers, BPI, BFI, PSI, SE, IsCS);
     bool AllZeros = false;
     if (!Func.readCounters(PGOReader.get(), AllZeros))
       continue;
     if (AllZeros) {
       F.setEntryCount(ProfileCount(0, Function::PCT_Real));
       if (Func.getProgramMaxCount() != 0)
         ColdFunctions.push_back(&F);
       continue;
PreservedAnalyses PGOInstrumentationUse::run(Module &M,
   auto LookupBPI = [&FAM](Function &F) {
     return &FAM.getResult<BranchProbabilityAnalysis>(F);
   };
 
   auto LookupBFI = [&FAM](Function &F) {
     return &FAM.getResult<BlockFrequencyAnalysis>(F);
   };
 
+  auto LookupLI = [&FAM](Function &F) {
+    return &FAM.getResult<LoopAnalysis>(F);
+  };
+
+  auto LookupSE = [&FAM](Function &F) {
+    return &FAM.getResult<ScalarEvolutionAnalysis>(F);
+  };
+  
   auto *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);
 
   if (!annotateAllFunctions(M, ProfileFileName, ProfileRemappingFileName,
-                            LookupBPI, LookupBFI, PSI, IsCS))
+                            LookupBPI, LookupBFI, LookupLI, LookupSE, PSI, 
+                            IsCS))
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }
 
 bool PGOInstrumentationUseLegacyPass::runOnModule(Module &M) {
   if (skipModule(M))
     return false;
 
   auto LookupBPI = [this](Function &F) {
     return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
   };
   auto LookupBFI = [this](Function &F) {
     return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
   };
+  auto LookupLI = [this](Function &F) {
+    return &this->getAnalysis<LoopInfoWrapperPass>(F).getLoopInfo();
+  };
+  auto LookupSE = [](Function &F) { return nullptr; };
 
   auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
-  return annotateAllFunctions(M, ProfileFileName, "", LookupBPI, LookupBFI, PSI,
-                              IsCS);
+  return annotateAllFunctions(M, ProfileFileName, "", LookupBPI, LookupBFI,
+                              LookupLI, LookupSE, PSI, IsCS);
 }
 
 static std::string getSimpleNodeName(const BasicBlock *Node) {
   if (!Node->getName().empty())
     return Node->getName();
 
   std::string SimpleNodeName;
   raw_string_ostream OS(SimpleNodeName);

llvm/lib/Transforms/Instrumentation/ValueProfileCollector.h

 
 #include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 #include "llvm/ProfileData/InstrProf.h"
 
 namespace llvm {
 
+class LoopInfo;
+class ScalarEvolution;
+class Loop;
+
 /// Utility analysis that determines what values are worth profiling.
 /// The actual logic is inside the ValueProfileCollectorImpl, whose job is to
 /// populate the Candidates vector.
 ///
 /// Value profiling an expression means to track the values that this expression
 /// takes at runtime and the frequency of each value.
 /// It is important to distinguish between two sets of value profiles for a
 /// particular expression:

 /// For this reason, a plugin is responsible for computing the insertion point
 /// for each value to be profiled. The `CandidateInfo` structure encapsulates
 /// all the information needed for each value profile site.
 class ValueProfileCollector {
 public:
   struct CandidateInfo {
     Value *V;                   // The value to profile.
     Instruction *InsertPt;      // Insert the VP lib call before this instr.
-    Instruction *AnnotatedInst; // Where metadata is attached.
+    PointerUnion<Loop *, Instruction *> MDHolder; // Where metadata is attached.
   };
 
-  ValueProfileCollector(Function &Fn);
+  ValueProfileCollector(Function &Fn, LoopInfo &LI, ScalarEvolution *SE);
   ValueProfileCollector(ValueProfileCollector &&) = delete;
   ValueProfileCollector &operator=(ValueProfileCollector &&) = delete;
 
   ValueProfileCollector(const ValueProfileCollector &) = delete;
   ValueProfileCollector &operator=(const ValueProfileCollector &) = delete;
   ~ValueProfileCollector();
 
   /// returns a list of value profiling candidates of the given kind

llvm/lib/Transforms/Instrumentation/ValueProfileCollector.cpp

 //===----------------------------------------------------------------------===//
 
 #include "ValueProfilePlugins.inc"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/InitializePasses.h"
 
 #include <cassert>
+#include <type_traits>
 
 using namespace llvm;
 
 namespace {
 
+// A wrapper class around a Plugin type that allows constructing the plugin from
+// one of the arguments given to the wrapper.
+template <class PluginT> class SelectiveCtor {
+  PluginT obj;
+
+public:
+  // clang-format off
+  template <typename U = PluginT>
+  explicit SelectiveCtor(Function &F, LoopInfo &LI, ScalarEvolution *SE,
+                         typename std::enable_if<std::is_constructible<U, Function &>::value>::type* = 0)
+      : obj(F) {}
+  template <typename U = PluginT>
+  explicit SelectiveCtor(Function &F, LoopInfo &LI, ScalarEvolution *SE,
+                         typename std::enable_if<std::is_constructible<U, LoopInfo &, ScalarEvolution *>::value>::type * = 0)
+      : obj(LI, SE) {}
+  // clang-format on
+  PluginT *operator->() { return &obj; }
+};
+
 /// A plugin-based class that takes an arbitrary number of Plugin types.
 /// Each plugin type must satisfy the following API:
-///  1) the constructor must take a `Function &f`. Typically, the plugin would
-///     scan the function looking for candidates.
+///  1) the constructor must take a `Function &` or a
+///     `LoopInfo &, ScalarEvolution *`. Typically, the plugin would scan the
+///     function or traverse the loops looking for candidates.
 ///  2) contain a member function with the following signature and name:
 ///        void run(std::vector<CandidateInfo> &Candidates);
 ///    such that the plugin would append its result into the vector parameter.
 ///
 /// Plugins are defined in ValueProfilePlugins.inc
 template <class... Ts> class PluginChain;
 
 /// The type PluginChainFinal is the final chain of plugins that will be used by
 /// ValueProfileCollectorImpl.
 using PluginChainFinal = PluginChain<VP_PLUGIN_LIST>;
 
 template <> class PluginChain<> {
 public:
-  PluginChain(Function &F) {}
+  PluginChain(Function &F, LoopInfo &LI, ScalarEvolution *SE) {}
   void get(InstrProfValueKind K, std::vector<CandidateInfo> &Candidates) {}
 };
 
 template <class PluginT, class... Ts>
 class PluginChain<PluginT, Ts...> : public PluginChain<Ts...> {
-  PluginT Plugin;
+  SelectiveCtor<PluginT> Plugin;
   using Base = PluginChain<Ts...>;
 
 public:
-  PluginChain(Function &F) : PluginChain<Ts...>(F), Plugin(F) {}
+  PluginChain(Function &F, LoopInfo &LI, ScalarEvolution *SE)
+       : Base(F, LI, SE), Plugin(F, LI, SE) {}
 
   void get(InstrProfValueKind K, std::vector<CandidateInfo> &Candidates) {
     if (K == PluginT::Kind)
-      Plugin.run(Candidates);
+      Plugin->run(Candidates);
     Base::get(K, Candidates);
   }
 };
 
 } // end anonymous namespace
 
 /// ValueProfileCollectorImpl inherits the API of PluginChainFinal.
 class ValueProfileCollector::ValueProfileCollectorImpl : public PluginChainFinal {
 public:
   using PluginChainFinal::PluginChainFinal;
 };
 
-ValueProfileCollector::ValueProfileCollector(Function &F)
-    : PImpl(new ValueProfileCollectorImpl(F)) {}
+ValueProfileCollector::ValueProfileCollector(Function &F, LoopInfo &LI,
+                                             ScalarEvolution *SE)
+    : PImpl(new ValueProfileCollectorImpl(F, LI, SE)) {}
 
 ValueProfileCollector::~ValueProfileCollector() = default;
 
 std::vector<CandidateInfo>
 ValueProfileCollector::get(InstrProfValueKind Kind) const {
   std::vector<CandidateInfo> Result;
   PImpl->get(Kind, Result);
   return Result;
 }

llvm/lib/Transforms/Instrumentation/ValueProfilePlugins.inc

 // Each plugin is responsible for collecting Value Profiling candidates for a
 // particular optimization.
 // Each plugin must satisfy the interface described in ValueProfileCollector.cpp
 //
 //===----------------------------------------------------------------------===//
 
 #include "ValueProfileCollector.h"
 #include "llvm/Analysis/IndirectCallVisitor.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/IR/InstVisitor.h"
+#include "llvm/Support/Debug.h"
+
+#define DEBUG_TYPE "vpo"
 
 using namespace llvm;
 using CandidateInfo = ValueProfileCollector::CandidateInfo;
 
 ///--------------------------- MemIntrinsicPlugin ------------------------------
 class MemIntrinsicPlugin : public InstVisitor<MemIntrinsicPlugin> {
   Function &F;
   std::vector<CandidateInfo> *Candidates;
for (Instruction *I : Result) {
       Value *Callee = CallSite(I).getCalledValue();
       Instruction *InsertPt = I;
       Instruction *AnnotatedInst = I;
       Candidates.emplace_back(CandidateInfo{Callee, InsertPt, AnnotatedInst});
     }
   }
 };
 
+///------------------------------ LoopInfoPlugin -------------------------------
+class LoopInfoPlugin {
+  LoopInfo &LI;
+  ScalarEvolution *SE;
+  std::unique_ptr<SCEVExpander> Expander;
+public:
+  static constexpr InstrProfValueKind Kind = IPVK_LoopTripCnt;
+
+  LoopInfoPlugin(LoopInfo &LInfo, ScalarEvolution *SE)
+      : LI(LInfo), SE(SE), Expander(nullptr) {
+    if (SE && !LI.empty()) {
+      Module *M = (*LI.begin())->getHeader()->getModule();
+      Expander = std::make_unique<SCEVExpander>(*SE, M->getDataLayout(),
+                                    "trip-count-prof");
+    }
+  }
+  void run(std::vector<CandidateInfo> &Candidates) { 
+    LLVM_DEBUG(dbgs() << "running LoopInfoPlugin on LoopInfo " << &LI << "\n");
+    SmallVector<Loop *, 8> LoopStack(LI.begin(), LI.end());
+
+    while (!LoopStack.empty()) {
+      Loop *L = LoopStack.pop_back_val();
+      LoopStack.insert(LoopStack.end(), L->begin(), L->end());
+      processLoop(L, Candidates);
+    }
+  }
+
+  void processLoop(Loop *L, std::vector<CandidateInfo> &Candidates) {
+    if (!L->isLoopSimplifyForm() || !SE)
+      return;
+
+    // Handle loops with single exit point because their trip count should be
+    // accurately measurable.
+    BasicBlock *ExitingBlock = L->getExitingBlock();
+    if (!ExitingBlock)
+      return;
+
+    const SCEV *ExitCount = SE->getExitCount(L, ExitingBlock);
+    if (isa<SCEVCouldNotCompute>(ExitCount) || isa<SCEVConstant>(ExitCount))
+      return;
+
+    // Insert the trip count calculation and recording in the preheader.
+    BasicBlock *PreHeader = L->getLoopPreheader();
+    Value *TripCount = Expander->expandCodeFor(ExitCount, ExitCount->getType(),
+                                               PreHeader->getTerminator());
+    Instruction *InsertPt = PreHeader->getTerminator();
+    Loop *MDHolder = L;
+    LLVM_DEBUG(dbgs() << "Adding candidate: \n"
+                      << "  Profiled Value = " << *TripCount << "\n"
+                      << "  Insertion Point = " << *InsertPt << "\n"
+                      << "  Metadata Holder = " << MDHolder << "\n");
+    Candidates.emplace_back(CandidateInfo{TripCount, InsertPt, MDHolder});
+  }
+};
+
 ///----------------------- Registration of the plugins -------------------------
 /// For now, registering a plugin with the ValueProfileCollector is done by
 /// adding the plugin type to the VP_PLUGIN_LIST macro.
 #define VP_PLUGIN_LIST           \
     MemIntrinsicPlugin,          \
-    IndirectCallPromotionPlugin
+    IndirectCallPromotionPlugin, \
+    LoopInfoPlugin
+

llvm/lib/Transforms/Utils/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
 name = TransformUtils
 parent = Transforms
-required_libraries = Analysis Core Support
+required_libraries = Analysis Core ProfileData Support

llvm/lib/Transforms/Utils/LoopUtils.cpp

 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
+#include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "loop-utils"
Optional<MDNode *> llvm::makeFollowupLoopID(
   if (InheritAllAttrs || InheritSomeAttrs) {
     for (const MDOperand &Existing : drop_begin(OrigLoopID->operands(), 1)) {
       MDNode *Op = cast<MDNode>(Existing.get());
 
       auto InheritThisAttribute = [InheritSomeAttrs,
                                    InheritOptionsExceptPrefix](MDNode *Op) {
         if (!InheritSomeAttrs)
           return false;
+        if (isValueProfMD(Op, IPVK_LoopTripCnt))
+          return false;
 
         // Skip malformatted attribute metadata nodes.
         if (Op->getNumOperands() == 0)
           return true;
         Metadata *NameMD = Op->getOperand(0).get();
         if (!isa<MDString>(NameMD))
           return true;
         StringRef AttrName = cast<MDString>(NameMD)->getString();

llvm/test/Instrumentation/InstrProfiling/PR23499.ll

 ; RUN: opt < %s -mtriple=x86_64-pc-win32-coff -passes=instrprof -S | FileCheck %s --check-prefix=COFF
 
 $_Z3barIvEvv = comdat any
 
 @__profn__Z3barIvEvv = linkonce_odr hidden constant [11 x i8] c"_Z3barIvEvv", align 1
 
 ; CHECK-NOT: __profn__Z3barIvEvv
 ; CHECK: @__profc__Z3barIvEvv = linkonce_odr hidden global [1 x i64] zeroinitializer, section "{{.*}}__llvm_prf_cnts", comdat, align 8
-; CHECK: @__profd__Z3barIvEvv = linkonce_odr hidden global { i64, i64, i64*, i8*, i8*, i32, [2 x i16] } { i64 4947693190065689389, i64 0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__Z3barIvEvv, i32 0, i32 0), i8*{{.*}}, i8* null, i32 1, [2 x i16] zeroinitializer }, section "{{.*}}__llvm_prf_data{{.*}}", comdat, align 8
+; CHECK: @__profd__Z3barIvEvv = linkonce_odr hidden global { i64, i64, i64*, i8*, i8*, i32, [3 x i16] } { i64 4947693190065689389, i64 0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__Z3barIvEvv, i32 0, i32 0), i8*{{.*}}, i8* null, i32 1, [3 x i16] zeroinitializer }, section "{{.*}}__llvm_prf_data{{.*}}", comdat, align 8
 ; CHECK: @__llvm_prf_nm = private constant [{{.*}} x i8] c"{{.*}}", section "{{.*}}__llvm_prf_names"
 
 
 ; COFF-NOT: __profn__Z3barIvEvv
 ; COFF: @__profc__Z3barIvEvv = linkonce_odr hidden global [1 x i64] zeroinitializer, section "{{.*}}prfc$M", comdat, align 8
-; COFF: @__profd__Z3barIvEvv = linkonce_odr hidden global { i64, i64, i64*, i8*, i8*, i32, [2 x i16] } { i64 4947693190065689389, i64 0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__Z3barIvEvv, i32 0, i32 0), i8*{{.*}}, i8* null, i32 1, [2 x i16] zeroinitializer }, section "{{.*}}prfd{{.*}}", comdat, align 8
+; COFF: @__profd__Z3barIvEvv = linkonce_odr hidden global { i64, i64, i64*, i8*, i8*, i32, [3 x i16] } { i64 4947693190065689389, i64 0, i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__Z3barIvEvv, i32 0, i32 0), i8*{{.*}}, i8* null, i32 1, [3 x i16] zeroinitializer }, section "{{.*}}prfd{{.*}}", comdat, align 8
 
 
 declare void @llvm.instrprof.increment(i8*, i64, i32, i32) #1
 
 define linkonce_odr void @_Z3barIvEvv() comdat {
 entry:
   call void @llvm.instrprof.increment(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @__profn__Z3barIvEvv, i32 0, i32 0), i64 0, i32 1, i32 0)
   ret void
 }

llvm/test/Instrumentation/InstrProfiling/icall.ll

 attributes #0 = { nounwind }
 
 ; STATIC: @__profvp_foo
 ; STATIC: @__llvm_prf_vnodes
 
 ; DYN-NOT: @__profvp_foo
 ; DYN-NOT: @__llvm_prf_vnodes
 
-; STATIC: call void @__llvm_profile_instrument_target(i64 %3, i8* bitcast ({ i64, i64, i64*, i8*, i8*, i32, [2 x i16] }* @__profd_foo to i8*), i32 0)
-; STATIC-EXT: call void @__llvm_profile_instrument_target(i64 %3, i8* bitcast ({ i64, i64, i64*, i8*, i8*, i32, [2 x i16] }* @__profd_foo to i8*), i32 zeroext 0)
-; STATIC-SEXT: call void @__llvm_profile_instrument_target(i64 %3, i8* bitcast ({ i64, i64, i64*, i8*, i8*, i32, [2 x i16] }* @__profd_foo to i8*), i32 signext 0)
+; STATIC: call void @__llvm_profile_instrument_target(i64 %3, i8* bitcast ({ i64, i64, i64*, i8*, i8*, i32, [3 x i16] }* @__profd_foo to i8*), i32 0)
+; STATIC-EXT: call void @__llvm_profile_instrument_target(i64 %3, i8* bitcast ({ i64, i64, i64*, i8*, i8*, i32, [3 x i16] }* @__profd_foo to i8*), i32 zeroext 0)
+; STATIC-SEXT: call void @__llvm_profile_instrument_target(i64 %3, i8* bitcast ({ i64, i64, i64*, i8*, i8*, i32, [3 x i16] }* @__profd_foo to i8*), i32 signext 0)
 
 ; STATIC: declare void @__llvm_profile_instrument_target(i64, i8*, i32)
 ; STATIC-EXT: declare void @__llvm_profile_instrument_target(i64, i8*, i32 zeroext)
 ; STATIC-SEXT: declare void @__llvm_profile_instrument_target(i64, i8*, i32 signext)

llvm/test/Transforms/PGOProfile/Inputs/looptc.proftext

+# IR level Instrumentation Flag
+:ir
+main
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
+13
+3
+# Num Value Kinds:
+1
+# ValueKind = IPVK_LoopTripCnt:
+2
+# NumValueSites:
+1
+# Number of Values seen for site #1
+2
+# The value:count pairs for site #1
+4:2
+5:1

llvm/test/Transforms/PGOProfile/comdat_internal.ll

 ; RUN: opt < %s -pgo-instr-gen -instrprof -S | FileCheck %s
 ; RUN: opt < %s -passes=pgo-instr-gen,instrprof -S | FileCheck %s
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 $foo = comdat any
 ; CHECK: $foo = comdat any
 
 ; CHECK: $__llvm_profile_raw_version = comdat any
 
 @bar = global i32 ()* @foo, align 8
 
 ; CHECK: @__llvm_profile_raw_version = constant i64 {{[0-9]+}}, comdat
 ; CHECK-NOT: __profn__stdin__foo
 ; CHECK: @__profc__stdin__foo.[[FOO_HASH:[0-9]+]] = private global [1 x i64] zeroinitializer, section "__llvm_prf_cnts", comdat, align 8
-; CHECK: @__profd__stdin__foo.[[FOO_HASH]] = private global { i64, i64, i64*, i8*, i8*, i32, [2 x i16] } { i64 -5640069336071256030, i64 [[FOO_HASH]], i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__stdin__foo.[[FOO_HASH]], i32 0, i32 0), i8* null
+; CHECK: @__profd__stdin__foo.[[FOO_HASH]] = private global { i64, i64, i64*, i8*, i8*, i32, [3 x i16] } { i64 -5640069336071256030, i64 [[FOO_HASH]], i64* getelementptr inbounds ([1 x i64], [1 x i64]* @__profc__stdin__foo.[[FOO_HASH]], i32 0, i32 0), i8* null
 ; CHECK-NOT: bitcast (i32 ()* @foo to i8*)
-; CHECK-SAME: , i8* null, i32 1, [2 x i16] zeroinitializer }, section "__llvm_prf_data", comdat, align 8
+; CHECK-SAME: , i8* null, i32 1, [3 x i16] zeroinitializer }, section "__llvm_prf_data", comdat, align 8
 ; CHECK: @__llvm_prf_nm
 ; CHECK: @llvm.used
 
 define internal i32 @foo() comdat {
 entry:
   ret i32 1
 }

llvm/test/Transforms/PGOProfile/looptc.ll

+;------------------------------------------------------------------------------
+; 1) Test that loop trip count profile instrumentation is generated in the  
+;    correct location. Note this is only implemented for the new PM.;
+; RUN: opt < %s -passes=pgo-instr-gen,instrprof -pgo-loop-trip-count -S | FileCheck %s --check-prefix=CG-CHECK
+;
+; To generate the looptc.proftext file, do:
+;   1) clang -fprofile-generate -mllvm -pgo-loop-trip-count %s -o looptc.exe
+;   2) LLVM_PROFILE_FILE=t.profraw looptc.exe 4
+;      LLVM_PROFILE_FILE=t.profraw looptc.exe 4
+;      LLVM_PROFILE_FILE=t.profraw looptc.exe 5
+;   3) llvm-profdata merge -text -output=looptc.proftext t.profraw
+;
+; 2) Test that llvm-profdata can consume the textual profile data containing 
+;    loop trip count profile info.
+; RUN: llvm-profdata merge %S/Inputs/looptc.proftext -o %t.profdata
+;
+; 3) Test that loop trip count profile is correctly read and annotated on the IR.
+; RUN: opt < %s -passes=pgo-instr-use -pgo-test-profile-file=%t.profdata -pgo-loop-trip-count -S | FileCheck %s --check-prefix=VP-ANNOTATION
+;
+;-------------------------------------------------------------------------------
+
+target datalayout = "e-m:e-i64:64-n32:64"
+target triple = "powerpc64le-unknown-linux-gnu"
+
+declare i32 @atoi(i8*)
+
+@__const.array = private unnamed_addr constant <{ [10 x i32], [90 x i32] }> <{ [10 x i32] [i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9, i32 10], [90 x i32] zeroinitializer }>, align 4
+
+define i32 @main(i32 signext %argc, i8** %argv) {
+entry:
+  %arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1
+  %0 = load i8*, i8** %arrayidx, align 8
+  %call = call signext i32 @atoi(i8* %0)
+; CG-CHECK: [[ZEXT:%[0-9]+]] = zext i32 %call to i64
+; CG-CHECK: call void @__llvm_profile_instrument_target(i64 [[ZEXT]], i8* bitcast ({ i64, i64, i64*, i8*, i8*, i32, [3 x i16] }* @__profd_main to i8*), i32 zeroext 0)  
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %c.0 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %i.0 = phi i32 [ 0, %entry ], [ %add2, %for.body ]
+  %cmp = icmp ult i32 %i.0, %call
+  br i1 %cmp, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  ret i32 %c.0
+
+for.body:                                         ; preds = %for.cond
+  %idxprom = zext i32 %i.0 to i64
+  %arrayidx1 = getelementptr inbounds [100 x i32], [100 x i32]* bitcast (<{ [10 x i32], [90 x i32] }>* @__const.array to [100 x i32]*), i64 0, i64 %idxprom
+  %1 = load i32, i32* %arrayidx1, align 4
+  %add = add nsw i32 %c.0, %1
+  %add2 = add i32 %i.0, 1
+  br label %for.cond
+; VP-ANNOTATION: br label %for.cond, !llvm.loop ![[LOOP_MD:[0-9]+]]  
+}
+
+; VP-ANNOTATION: ![[LOOP_MD]] = distinct !{![[LOOP_MD]], ![[LOOP_TRIP_COUNT:[0-9]*]]}
+; VP-ANNOTATION: ![[LOOP_TRIP_COUNT]] = !{!"VP", i32 2, i64 3, i64 4, i64 2, i64 5, i64 1}

llvm/test/Transforms/PGOProfile/memcpy.ll

for.cond1:
   %add.ptr = getelementptr inbounds i32, i32* %a, i64 %idx.ext
   %0 = load i32, i32* %add.ptr, align 4
   %cmp2 = icmp slt i32 %j.0, %0
   %add = add nsw i32 %i.0, 1
   br i1 %cmp2, label %for.body3, label %for.cond
 
 for.body3:
   %conv = sext i32 %add to i64
-; CHECK: call void @__llvm_profile_instrument_range(i64 %conv, i8* bitcast ({ i64, i64, i64*, i8*, i8*, i32, [2 x i16] }* @__profd_foo to i8*), i32 0, i64 0, i64 8, i64 8192)
+; CHECK: call void @__llvm_profile_instrument_range(i64 %conv, i8* bitcast ({ i64, i64, i64*, i8*, i8*, i32, [3 x i16] }* @__profd_foo to i8*), i32 0, i64 0, i64 8, i64 8192)
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %dst, i8* %src, i64 %conv, i1 false)
   %inc = add nsw i32 %j.0, 1
   br label %for.cond1
 
 for.end6:
   ret void
 }
 
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture writeonly, i8* nocapture readonly, i64, i1)

llvm/test/Transforms/PGOProfile/select1.ll

 ; RUN: opt < %s -pgo-instr-gen -pgo-instr-select=true -S | FileCheck %s --check-prefix=GEN
 ; RUN: opt < %s -passes=pgo-instr-gen -pgo-instr-select=true -S | FileCheck %s --check-prefix=GEN
 ; RUN: opt < %s -pgo-instr-gen -pgo-instr-select=false -S | FileCheck %s --check-prefix=NOSELECT
 ; RUN: opt < %s -passes=pgo-instr-gen -pgo-instr-select=false -S | FileCheck %s --check-prefix=NOSELECT
 ; RUN: llvm-profdata merge %S/Inputs/select1.proftext -o %t.profdata
 ; RUN: opt < %s -pgo-instr-use -pgo-test-profile-file=%t.profdata -pgo-instr-select=true -S | FileCheck %s --check-prefix=USE
 ; RUN: opt < %s -passes=pgo-instr-use -pgo-test-profile-file=%t.profdata -pgo-instr-select=true -S | FileCheck %s --check-prefix=USE
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
+declare void @use(i32)
+
 define i32 @test_br_2(i32 %i) {
 entry:
   %cmp = icmp sgt i32 %i, 0
   br i1 %cmp, label %if.then, label %if.else
 
 if.then:
   %add = add nsw i32 %i, 2
 ;GEN: %[[STEP:[0-9]+]] = zext i1 %cmp to i64
 ;GEN: call void @llvm.instrprof.increment.step({{.*}} i32 3, i32 2, i64 %[[STEP]])
 ;NOSELECT-NOT: call void @llvm.instrprof.increment.step
   %s = select i1 %cmp, i32 %add, i32 0
-;USE: select i1 %cmp{{.*}}, !prof ![[BW_ENTRY:[0-9]+]]
+;USE: %s = select i1 %cmp{{.*}}, !prof ![[BW_ENTRY:[0-9]+]]
 ;USE: ![[BW_ENTRY]] = !{!"branch_weights", i32 1, i32 3}
-
+  call void @use(i32 %s)
   br label %if.end
 
 if.else:
   %sub = sub nsw i32 %i, 2
   br label %if.end
 
 if.end:
   %retv = phi i32 [ %add, %if.then ], [ %sub, %if.else ]
   ret i32 %retv
 }

llvm/test/tools/llvm-profdata/raw-64-bits-be.test

+The Header: __llvm_profile_header
 RUN: printf '\377lprofr\201' > %t
 RUN: printf '\0\0\0\0\0\0\0\5' >> %t
 RUN: printf '\0\0\0\0\0\0\0\2' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\3' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\20' >> %t
 RUN: printf '\0\0\0\1\0\4\0\0' >> %t
 RUN: printf '\0\0\0\2\0\4\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 
+N __llvm_profile_data objects, where N is Header.DataSize
 RUN: printf '\134\370\302\114\333\030\275\254' >> %t
 RUN: printf '\0\0\0\0\0\0\0\1' >> %t
 RUN: printf '\0\0\0\1\0\4\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\1\0\0\0\0' >> %t
+RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 
 RUN: printf '\344\023\165\112\031\035\265\067' >> %t
 RUN: printf '\0\0\0\0\0\0\0\02' >> %t
 RUN: printf '\0\0\0\1\0\4\0\10' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\02\0\0\0\0' >> %t
+RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 
+Counters
 RUN: printf '\0\0\0\0\0\0\0\023' >> %t
 RUN: printf '\0\0\0\0\0\0\0\067' >> %t
 RUN: printf '\0\0\0\0\0\0\0\101' >> %t
 RUN: printf '\7\0foo\1bar\0\0\0\0\0\0\0' >> %t
 
 RUN: llvm-profdata show %t -all-functions -counts | FileCheck %s
 
 CHECK: Counters:

llvm/test/tools/llvm-profdata/raw-64-bits-le.test

+The Header: __llvm_profile_header
 RUN: printf '\201rforpl\377' > %t
 RUN: printf '\5\0\0\0\0\0\0\0' >> %t
 RUN: printf '\2\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\3\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\20\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\4\0\1\0\0\0' >> %t
 RUN: printf '\0\0\4\0\2\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 
+N __llvm_profile_data objects, where N is Header.DataSize
 RUN: printf '\254\275\030\333\114\302\370\134' >> %t
 RUN: printf '\1\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\4\0\1\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\1\0\0\0\0\0\0\0' >> %t
+RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 
 RUN: printf '\067\265\035\031\112\165\023\344' >> %t
 RUN: printf '\02\0\0\0\0\0\0\0' >> %t
 RUN: printf '\10\0\4\0\1\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 RUN: printf '\02\0\0\0\0\0\0\0' >> %t
+RUN: printf '\0\0\0\0\0\0\0\0' >> %t
 
+Counters
 RUN: printf '\023\0\0\0\0\0\0\0' >> %t
 RUN: printf '\067\0\0\0\0\0\0\0' >> %t
 RUN: printf '\101\0\0\0\0\0\0\0' >> %t
 RUN: printf '\7\0foo\1bar\0\0\0\0\0\0\0' >> %t
 
 RUN: llvm-profdata show %t -all-functions -counts | FileCheck %s
 
 CHECK: Counters:

llvm/test/tools/llvm-profdata/raw-two-profiles.test

 RUN: printf '\0\0\0\0\0\0\0\0' >> %t-foo.profraw
 
 RUN: printf '\254\275\030\333\114\302\370\134' >> %t-foo.profraw
 RUN: printf '\1\0\0\0\0\0\0\0' >> %t-foo.profraw
 RUN: printf '\0\0\4\0\1\0\0\0' >> %t-foo.profraw
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t-foo.profraw
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t-foo.profraw
 RUN: printf '\1\0\0\0\0\0\0\0' >> %t-foo.profraw
+RUN: printf '\0\0\0\0\0\0\0\0' >> %t-foo.profraw
+
 
 RUN: printf '\023\0\0\0\0\0\0\0' >> %t-foo.profraw
 RUN: printf '\3\0foo\0\0\0' >> %t-foo.profraw
 
 RUN: printf '\201rforpl\377' > %t-bar.profraw
 RUN: printf '\5\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\1\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\2\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\10\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\0\0\6\0\1\0\0\0' >> %t-bar.profraw
 RUN: printf '\0\0\6\0\2\0\0\0' >> %t-bar.profraw
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t-bar.profraw
 
 RUN: printf '\067\265\035\031\112\165\023\344' >> %t-bar.profraw
 RUN: printf '\02\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\0\0\6\0\1\0\0\0' >> %t-bar.profraw
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\0\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\02\0\0\0\0\0\0\0' >> %t-bar.profraw
+RUN: printf '\0\0\0\0\0\0\0\0' >> %t-bar.profraw
 
 RUN: printf '\067\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\101\0\0\0\0\0\0\0' >> %t-bar.profraw
 RUN: printf '\3\0bar\0\0\0' >> %t-bar.profraw
 
 RUN: cat %t-foo.profraw %t-bar.profraw > %t-pad.profraw
 RUN: llvm-profdata show %t-pad.profraw -all-functions -counts | FileCheck %s