[SampleFDO] Stop repeated indirect call promotion for the same target

[wmi]

Summary

Found a problem in indirect call promotion in sample loader pass. Currently if an indirect call is promoted for a target, and if the parent function is inlined into some other function, the indirect call can be promoted for the same target again. That is redundent which can harm performance and can cause excessive compile time in some extreme case.

The patch fixes the issue. If a target is promoted for an indirect call, the patch will write ICP metadata with the target call count being set to 0. In the later ICP in sample profile loader, if it sees a target has 0 count for an indirect call, it knows the target has been promoted and won't do indirect call promotion for the indirect call.

The fix brings 0.1~0.2% performance on our search benchmark.

[wmi]

Currently to prevent recursive indirect call promotion, SampleLoaderPass use a DenseSet PromotedInsns to memorize which indirect call has been promoted inside of current function. However, PromotedInsns is cleared everytime emitAnnotation has done for a function, so it cannot prevent the same indirect call being promoted for the same target again in another iteration of emitAnnotation.

On the other side, because of PromotedInsns, an indirect call is limited to be promoted only for one target in every iteration of emitAnnotation. That limits inline instance profile annotation related with indirect call targets. I think PromotedInsns can be deleted after this patch. I will address it in a followup patch after performance testing.

[davidxl]

llvm/lib/Transforms/IPO/SampleProfile.cpp

882

Why do we need to keep the zero count data in the first place?

918

Why updating here? Is the meta data more up to date?

[hoy]

In D96806#2566458, @wmi wrote:

Currently to prevent recursive indirect call promotion, SampleLoaderPass use a DenseSet PromotedInsns to memorize which indirect call has been promoted inside of current function. However, PromotedInsns is cleared everytime emitAnnotation has done for a function, so it cannot prevent the same indirect call being promoted for the same target again in another iteration of emitAnnotation.

On the other side, because of PromotedInsns, an indirect call is limited to be promoted only for one target in every iteration of emitAnnotation. That limits inline instance profile annotation related with indirect call targets. I think PromotedInsns can be deleted after this patch. I will address it in a followup patch after performance testing.

Did you see the recursive indirect call promotion between functions that do not follow top-down order, like functions in an SCC?

I remember this change https://reviews.llvm.org/D38763 prevents re-promotion done by subsequent PGO ICP. Could the existing heuristic in inlineHotFunctions be tweaked like PGO ICP? BTW, multiple indirect call targets can be promoted by inlineHotFunctionsWithPriority.

[wmi]

llvm/lib/Transforms/IPO/SampleProfile.cpp

882

I added the zero count data in updateIDTMetaData to indicate that a target has been promoted so it won't be promoted again. Once an indirect call is promoted for a target, we hope it won't be promoted for the same target again in any case, no matter where it is inlined into, so I think metadata is the best place to save the information. Currently I use zero count to represent that a target cannot be promoted anymore, this is consistent with how regular ICP handles zero count profile.

918

Yes, SampleFDO is different from PGO. PGO initialize the value profiling data once and only substract count of a target when the target is promoted. For SampleFDO, it needs to update metadata every time the indirect call is reannotated with more precise profile after inlining.

[wmi]

In D96806#2566946, @hoy wrote:

In D96806#2566458, @wmi wrote:

Currently to prevent recursive indirect call promotion, SampleLoaderPass use a DenseSet PromotedInsns to memorize which indirect call has been promoted inside of current function. However, PromotedInsns is cleared everytime emitAnnotation has done for a function, so it cannot prevent the same indirect call being promoted for the same target again in another iteration of emitAnnotation.

On the other side, because of PromotedInsns, an indirect call is limited to be promoted only for one target in every iteration of emitAnnotation. That limits inline instance profile annotation related with indirect call targets. I think PromotedInsns can be deleted after this patch. I will address it in a followup patch after performance testing.

Did you see the recursive indirect call promotion between functions that do not follow top-down order, like functions in an SCC?

Right. If everything follow top-down order, the recursive indirect call issue will be mostly hidden. But currently even the top-down order flag is enabled by default, SCC and missing call graph edges from indirect call can lead to bottom-up inlining.

I remember this change https://reviews.llvm.org/D38763 prevents re-promotion done by subsequent PGO ICP. Could the existing heuristic in inlineHotFunctions be tweaked like PGO ICP?

I think there is a major difference between SampleFDO ICP and regular ICP.

Regular ICP uses the value profile metadata to decide which targets should be promoted. Once metadata is populated, the promotion candidates are mostly decided.

SampleFDO ICP is different. The metadata is refreshed every time the indirect call is inlined into a new function and new inline instance profile is annotated to it. Even if the indirect call is promoted before, the metadata updated after the promotion will be dropped when the new profile is annotated. That is why I am trying to keep "0" counts for those targets which have already been promoted, and need to merge those "0" counts when we update the metadata with new profile -- if there is "0" count for a target, we will keep it as "0" during metadata merge. That will ensure the target won't be promoted again. I think we need this process no matter how we tweak existing heuristic like regular ICP.

BTW, multiple indirect call targets can be promoted by inlineHotFunctionsWithPriority.

I was wrong that PromotedInsns prevent an indirect call from being promoted for multiple targets in every iteration of emitAnnotation. It could. I misread the code. PromotedInsns can still be useful as a cache so it doesn't need to access metadata every loop iteration in inlineHotFunctions, so we may want to keep it in the end. Sorry about it.

[wmi]

Rebase to resolve some conflicts.

[wenlei]

PromotedInsns can still be useful as a cache so it doesn't need to access metadata every loop iteration in inlineHotFunctions, so we may want to keep it in the end. Sorry about it.

I would still remove PromotedInsns to keep it simple. If we worry about build time in inlineHotFunctions loop, we can change it to a work list to avoid revisiting all call sites on each iteration, similar to InlineHotFunctionWithPriority does this. That will save more repeated work.

The fix brings 0.1~0.2% performance on our search benchmark.

This is great - thanks for the fix. Without top-down order, the performance improvement would probably be larger.

llvm/lib/Transforms/IPO/SampleProfile.cpp

706

Do we expect the same function to appear multiple times in ValueData? If not, we could exit as long as the candidate is found?

742

When we update a non-zero count to zero to represent promoted call, do we need to reduce the total as well to reflect the remaining count for the actual indirect call?

794

A comment here would be helpful too.

[hoy]

In D96806#2567120, @wmi wrote:

In D96806#2566946, @hoy wrote:

In D96806#2566458, @wmi wrote:

Currently to prevent recursive indirect call promotion, SampleLoaderPass use a DenseSet PromotedInsns to memorize which indirect call has been promoted inside of current function. However, PromotedInsns is cleared everytime emitAnnotation has done for a function, so it cannot prevent the same indirect call being promoted for the same target again in another iteration of emitAnnotation.

On the other side, because of PromotedInsns, an indirect call is limited to be promoted only for one target in every iteration of emitAnnotation. That limits inline instance profile annotation related with indirect call targets. I think PromotedInsns can be deleted after this patch. I will address it in a followup patch after performance testing.

Did you see the recursive indirect call promotion between functions that do not follow top-down order, like functions in an SCC?

Right. If everything follow top-down order, the recursive indirect call issue will be mostly hidden. But currently even the top-down order flag is enabled by default, SCC and missing call graph edges from indirect call can lead to bottom-up inlining.

I remember this change https://reviews.llvm.org/D38763 prevents re-promotion done by subsequent PGO ICP. Could the existing heuristic in inlineHotFunctions be tweaked like PGO ICP?

I think there is a major difference between SampleFDO ICP and regular ICP.

Regular ICP uses the value profile metadata to decide which targets should be promoted. Once metadata is populated, the promotion candidates are mostly decided.

SampleFDO ICP is different. The metadata is refreshed every time the indirect call is inlined into a new function and new inline instance profile is annotated to it. Even if the indirect call is promoted before, the metadata updated after the promotion will be dropped when the new profile is annotated. That is why I am trying to keep "0" counts for those targets which have already been promoted, and need to merge those "0" counts when we update the metadata with new profile -- if there is "0" count for a target, we will keep it as "0" during metadata merge. That will ensure the target won't be promoted again. I think we need this process no matter how we tweak existing heuristic like regular ICP.

I see. I remember that I had to use probe distribution factor to scale down the unpromoted indirect callsites.

BTW, multiple indirect call targets can be promoted by inlineHotFunctionsWithPriority.

I was wrong that PromotedInsns prevent an indirect call from being promoted for multiple targets in every iteration of emitAnnotation. It could. I misread the code. PromotedInsns can still be useful as a cache so it doesn't need to access metadata every loop iteration in inlineHotFunctions, so we may want to keep it in the end. Sorry about it.

llvm/lib/Transforms/IPO/SampleProfile.cpp

737

Nit: group this if-statement and the one below?

741

Is a zero count automatically set when a target is promoted in a callee?

[wmi]

Address Wenlei and Hongtao's comments.

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

707–709

nit: return (ValueData[I].Count == 0);?

745

In what case do we have Total < Data.Count? And Total == Data.Count should be fine for subtraction too?

[wmi]

I would still remove PromotedInsns to keep it simple.

Yes, it is simpler. I removed them.

llvm/lib/Transforms/IPO/SampleProfile.cpp

706

Good point. Changed.

737

I added some other statement after the statement below when I addressed Wenlei's comment so now it is clearer not to group them.

741

It is set by updateIDTMetaData with CallTargets containing the promoted target and count being set to 0.

742

Another good point. Changed.

794

Comment added.

[wmi]

llvm/lib/Transforms/IPO/SampleProfile.cpp

707–709

That is better. Will fix.

745

Currently we won't have such case. It is just some extra protect in case of future change. I think assertion will be better. Will change it.

Right, Total == Data.Count should be added. will change it.

[wmi]

llvm/lib/Transforms/IPO/SampleProfile.cpp

745

The assertion catches a case where we have Total < Data.Count when running the test test/Transforms/SampleProfile/csspgo-inline-icall.ll.

For CS profile, the sum computed in findIndirectCallFunctionSamples can be smaller than the sum of the target counts returned by findCallTargetMapAt. Is it expected?

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

745

For CS profile, we use callsite count (including both inlined and non-inlined targets) instead of using entry counts, since there's yet a way to tell if an indirect call target is inlined or not from a CS profile.

We have a fix for this to review. Haven't sent it out yet. It basically replaces this code

uint64_t Sum = 0;
 findIndirectCallFunctionSamples(I, Sum);

with

if (FunctionSamples::ProfileIsCS) {
            // With CSSPGO all indirect call targets are counted towards the
            // original indirect call site in the profile, including both
            // inlined and non-inlined targets.
            Sum = 0;
            for (const auto &T_C : T.get())
              Sum += T_C.second;
          } else {
            findIndirectCallFunctionSamples(I, Sum);
          }

[wmi]

llvm/lib/Transforms/IPO/SampleProfile.cpp

745

findIndirectCallFunctionSamples

745

Thanks. That fix makes sense to me. This change will depend on your fix if I keep the assumption Total >= Data.Count and the assertion.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

745

Sure, let me send out the fix.

[wmi]

Address Wenlei's comment. Rebase on Hongtao's fix https://reviews.llvm.org/D96990

[wenlei]

lgtm, thanks!

[wmi]

I added PromotedInsns back in https://reviews.llvm.org/rG4ffad1fb489f691825d6c7d78e1626de142f26cf because I found there was some problem in current implementation and it may cause repeated ICP without the protection of PromotedInsns. Basically, when we read value profile using getValueProfDataFromInst, we specify MaxNumPromotions as the maximum value to read. It is possible that the size of valuedata is larger than MaxNumPromotions so getValueProfDataFromInst ignore some of the 0 count values. I added PromotedInsns back temporarily while I am figuring out what is the best way to fix this.

llvm/include/llvm/ProfileData/InstrProf.h

 
 /// 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);
+                              uint32_t &ActualNumValueData, uint64_t &TotalC,
+                              bool GetZeroCntValue = false);
 
 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

llvm/lib/Analysis/IndirectCallPromotionAnalysis.cpp

 static cl::opt<unsigned>
     ICPTotalPercentThreshold("icp-total-percent-threshold", cl::init(5),
                              cl::Hidden, cl::ZeroOrMore,
                              cl::desc("The percentage threshold against total "
                                       "count for the promotion"));
 
 // Set the maximum number of targets to promote for a single indirect-call
 // callsite.
-static cl::opt<unsigned>
+cl::opt<unsigned>
     MaxNumPromotions("icp-max-prom", cl::init(3), cl::Hidden, cl::ZeroOrMore,
                      cl::desc("Max number of promotions for a single indirect "
                               "call callsite"));
 
 ICallPromotionAnalysis::ICallPromotionAnalysis() {
   ValueDataArray = std::make_unique<InstrProfValueData[]>(MaxNumPromotions);
 }
 

llvm/lib/ProfileData/InstrProf.cpp

void annotateValueSite(Module &M, Instruction &Inst,
   }
   Inst.setMetadata(LLVMContext::MD_prof, MDNode::get(Ctx, Vals));
 }
 
 bool getValueProfDataFromInst(const Instruction &Inst,
                               InstrProfValueKind ValueKind,
                               uint32_t MaxNumValueData,
                               InstrProfValueData ValueData[],
-                              uint32_t &ActualNumValueData, uint64_t &TotalC) {
+                              uint32_t &ActualNumValueData, uint64_t &TotalC,
+                              bool GetZeroCntValue) {
   MDNode *MD = Inst.getMetadata(LLVMContext::MD_prof);
   if (!MD)
     return false;
 
   unsigned NOps = MD->getNumOperands();
 
   if (NOps < 5)
     return false;
bool getValueProfDataFromInst(const Instruction &Inst,
   ConstantInt *KindInt = mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
   if (!KindInt)
     return false;
   if (KindInt->getZExtValue() != ValueKind)
     return false;
 
   // Get total count
   ConstantInt *TotalCInt = mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
-  if (!TotalCInt)
+  if (!TotalCInt && !GetZeroCntValue)
     return false;
   TotalC = TotalCInt->getZExtValue();
 
   ActualNumValueData = 0;
 
   for (unsigned I = 3; 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)
+    if (!Value || (!Count && !GetZeroCntValue))
       return false;
     ValueData[ActualNumValueData].Value = Value->getZExtValue();
     ValueData[ActualNumValueData].Count = Count->getZExtValue();
     ActualNumValueData++;
   }
   return true;
 }
 

llvm/lib/Transforms/IPO/SampleProfile.cpp

 
 static cl::opt<std::string> ProfileInlineReplayFile(
     "sample-profile-inline-replay", cl::init(""), cl::value_desc("filename"),
     cl::desc(
         "Optimization remarks file containing inline remarks to be replayed "
         "by inlining from sample profile loader."),
     cl::Hidden);
 
+extern cl::opt<unsigned> MaxNumPromotions;
+
 namespace {
 
 using BlockWeightMap = DenseMap<const BasicBlock *, uint64_t>;
 using EquivalenceClassMap = DenseMap<const BasicBlock *, const BasicBlock *>;
 using Edge = std::pair<const BasicBlock *, const BasicBlock *>;
 using EdgeWeightMap = DenseMap<Edge, uint64_t>;
 using BlockEdgeMap =
     DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>;
protected:
   const FunctionSamples *findCalleeFunctionSamples(const CallBase &I) const;
   const FunctionSamples *
   findFunctionSamples(const Instruction &I) const override;
   std::vector<const FunctionSamples *>
   findIndirectCallFunctionSamples(const Instruction &I, uint64_t &Sum) const;
   // Attempt to promote indirect call and also inline the promoted call
   bool tryPromoteAndInlineCandidate(
       Function &F, InlineCandidate &Candidate, uint64_t SumOrigin,
-      uint64_t &Sum, DenseSet<Instruction *> &PromotedInsns,
-      SmallVector<CallBase *, 8> *InlinedCallSites = nullptr);
+      uint64_t &Sum, SmallVector<CallBase *, 8> *InlinedCallSites = nullptr);
   bool inlineHotFunctions(Function &F,
                           DenseSet<GlobalValue::GUID> &InlinedGUIDs);
   InlineCost shouldInlineCandidate(InlineCandidate &Candidate);
   bool getInlineCandidate(InlineCandidate *NewCandidate, CallBase *CB);
   bool
   tryInlineCandidate(InlineCandidate &Candidate,
                      SmallVector<CallBase *, 8> *InlinedCallSites = nullptr);
   bool
if (ProfileIsCS)
       it.first->second = ContextTracker->getContextSamplesFor(DIL);
     else
       it.first->second =
           Samples->findFunctionSamples(DIL, Reader->getRemapper());
   }
   return it.first->second;
 }
 
+/// If the profile count for the promotion candidate \p Candidate is 0,
+/// it means \p Candidate has already been promoted for \p Inst.
+static bool isPromotedBefore(const Instruction &Inst, StringRef Candidate) {
+  uint32_t NumVals = 0;
+  uint64_t TotalCount = 0;
+  std::unique_ptr<InstrProfValueData[]> ValueData =
+      std::make_unique<InstrProfValueData[]>(MaxNumPromotions);
+  bool Valid =
+      getValueProfDataFromInst(Inst, IPVK_IndirectCallTarget, MaxNumPromotions,
+                               ValueData.get(), NumVals, TotalCount, true);
+  if (Valid) {
+    for (uint32_t I = 0; I < NumVals; I++) {
+      // If the promotion candidate has 0 count in the metadata, it
+      // means the candidate has been promoted for this indirect call.
+      if (ValueData[I].Value == Function::getGUID(Candidate))
+        return ValueData[I].Count == 0;
+    }
+  }
+  return false;
+}
+
+/// Update indirect call target profile metadata for \p Inst. If \p Total
+/// is given, set TotalCount of call targets counts to \p Total, otherwise
+/// keep the original value in metadata.
+static void
+updateIDTMetaData(Instruction &Inst,
+                  const SmallVectorImpl<InstrProfValueData> &CallTargets,
+                  uint64_t Total = 0) {
+  DenseMap<uint64_t, uint64_t> ValueCountMap;
+
+  uint32_t NumVals = 0;
+  uint64_t TotalCount = 0;
+  std::unique_ptr<InstrProfValueData[]> ValueData =
+      std::make_unique<InstrProfValueData[]>(MaxNumPromotions);
+  bool Valid =
+      getValueProfDataFromInst(Inst, IPVK_IndirectCallTarget, MaxNumPromotions,
+                               ValueData.get(), NumVals, TotalCount, true);
+  if (Valid) {
+    for (uint32_t I = 0; I < NumVals; I++)
+      ValueCountMap[ValueData[I].Value] = ValueData[I].Count;
+  }
+
+  for (const auto &Data : CallTargets) {
+    auto Pair = ValueCountMap.try_emplace(Data.Value, Data.Count);
+    if (Pair.second)
+      continue;
+    // Update existing profile count of the call target if it is not 0.
+    // If it is 0, the call target has been promoted so keep it as 0.
+    if (Pair.first->second != 0)
+      Pair.first->second = Data.Count;
+    else {
+      assert(Total >= Data.Count && "Total should be >= Data.Count");
+      Total -= Data.Count;
+    }
+  }
+
+  SmallVector<InstrProfValueData, 8> NewCallTargets;
+  for (const auto &ValueCount : ValueCountMap) {
+    NewCallTargets.emplace_back(
+        InstrProfValueData{ValueCount.first, ValueCount.second});
+  }
+  llvm::sort(NewCallTargets,
+             [](const InstrProfValueData &L, const InstrProfValueData &R) {
+               if (L.Count != R.Count)
+                 return L.Count > R.Count;
+               return L.Value > R.Value;
+             });
+  annotateValueSite(*Inst.getParent()->getParent()->getParent(), Inst,
+                    NewCallTargets, Total ? Total : TotalCount,
+                    IPVK_IndirectCallTarget, NewCallTargets.size());
+}
+
 /// Attempt to promote indirect call and also inline the promoted call.
 ///
 /// \param F  Caller function.
 /// \param Candidate  ICP and inline candidate.
 /// \param Sum  Sum of target counts for indirect call.
-/// \param PromotedInsns  Map to keep track of indirect call already processed.
 /// \param InlinedCallSite  Output vector for new call sites exposed after
 /// inlining.
 bool SampleProfileLoader::tryPromoteAndInlineCandidate(
     Function &F, InlineCandidate &Candidate, uint64_t SumOrigin, uint64_t &Sum,
-    DenseSet<Instruction *> &PromotedInsns,
     SmallVector<CallBase *, 8> *InlinedCallSite) {
+  auto CalleeFunctionName = Candidate.CalleeSamples->getFuncName();
+  auto R = SymbolMap.find(CalleeFunctionName);
+  if (R == SymbolMap.end() || !R->getValue())
+    return false;
+
+  auto &CI = *Candidate.CallInstr;
+  if (isPromotedBefore(CI, R->getValue()->getName()))
+    return false;
+
   const char *Reason = "Callee function not available";
   // R->getValue() != &F is to prevent promoting a recursive call.
   // If it is a recursive call, we do not inline it as it could bloat
   // the code exponentially. There is way to better handle this, e.g.
   // clone the caller first, and inline the cloned caller if it is
   // recursive. As llvm does not inline recursive calls, we will
   // simply ignore it instead of handling it explicitly.
-  auto R = SymbolMap.find(Candidate.CalleeSamples->getFuncName());
-  if (R != SymbolMap.end() && R->getValue() &&
-      !R->getValue()->isDeclaration() && R->getValue()->getSubprogram() &&
+  if (!R->getValue()->isDeclaration() && R->getValue()->getSubprogram() &&
       R->getValue()->hasFnAttribute("use-sample-profile") &&
-      R->getValue() != &F &&
-      isLegalToPromote(*Candidate.CallInstr, R->getValue(), &Reason)) {
-    auto *DI =
-        &pgo::promoteIndirectCall(*Candidate.CallInstr, R->getValue(),
-                                  Candidate.CallsiteCount, Sum, false, ORE);
+      R->getValue() != &F && isLegalToPromote(CI, R->getValue(), &Reason)) {
+    // For promoted target, save 0 count in the value profile metadata so
+    // the target won't be promoted again.
+    SmallVector<InstrProfValueData, 1> SortedCallTargets = {
+        InstrProfValueData{Function::getGUID(R->getValue()->getName()), 0}};
+    updateIDTMetaData(CI, SortedCallTargets);
+
+    auto *DI = &pgo::promoteIndirectCall(
+        CI, R->getValue(), Candidate.CallsiteCount, Sum, false, ORE);
     if (DI) {
       Sum -= Candidate.CallsiteCount;
       // Prorate the indirect callsite distribution.
       // Do not update the promoted direct callsite distribution at this
       // point since the original distribution combined with the callee
       // profile will be used to prorate callsites from the callee if
       // inlined. Once not inlined, the direct callsite distribution should
       // be prorated so that the it will reflect the real callsite counts.
-      setProbeDistributionFactor(*Candidate.CallInstr,
-                                 Candidate.CallsiteDistribution * Sum /
+      setProbeDistributionFactor(CI, Candidate.CallsiteDistribution * Sum /
                                          SumOrigin);
-      PromotedInsns.insert(Candidate.CallInstr);
       Candidate.CallInstr = DI;
       if (isa<CallInst>(DI) || isa<InvokeInst>(DI)) {
         bool Inlined = tryInlineCandidate(Candidate, InlinedCallSite);
         if (!Inlined) {
           // Prorate the direct callsite distribution so that it reflects real
           // callsite counts.
           setProbeDistributionFactor(*DI, Candidate.CallsiteDistribution *
                                               Candidate.CallsiteCount /

 /// it to direct call. Each indirect call is limited with a single target.
 ///
 /// \param F function to perform iterative inlining.
 /// \param InlinedGUIDs a set to be updated to include all GUIDs that are
 ///     inlined in the profiled binary.
 ///
 /// \returns True if there is any inline happened.
 bool SampleProfileLoader::inlineHotFunctions(
     Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
-  DenseSet<Instruction *> PromotedInsns;
-
   // ProfAccForSymsInList is used in callsiteIsHot. The assertion makes sure
   // Profile symbol list is ignored when profile-sample-accurate is on.
   assert((!ProfAccForSymsInList ||
           (!ProfileSampleAccurate &&
            !F.hasFnAttribute("profile-sample-accurate"))) &&
          "ProfAccForSymsInList should be false when profile-sample-accurate "
          "is enabled");
 
for (auto &BB : F) {
             if (callsiteIsHot(FS, PSI, ProfAccForSymsInList))
               Hot = true;
             else if (shouldInlineColdCallee(*CB))
               ColdCandidates.push_back(CB);
           }
         }
       }
       if (Hot || ExternalInlineAdvisor) {
         CIS.insert(CIS.begin(), AllCandidates.begin(), AllCandidates.end());
         emitOptimizationRemarksForInlineCandidates(AllCandidates, F, true);
       } else {
         CIS.insert(CIS.begin(), ColdCandidates.begin(), ColdCandidates.end());
         emitOptimizationRemarksForInlineCandidates(ColdCandidates, F, false);
       }
     }
     for (CallBase *I : CIS) {
       Function *CalledFunction = I->getCalledFunction();
       InlineCandidate Candidate = {
           I,
           LocalNotInlinedCallSites.count(I) ? LocalNotInlinedCallSites[I]
                                             : nullptr,
           0 /* dummy count */, 1.0 /* dummy distribution factor */};
       // Do not inline recursive calls.
       if (CalledFunction == &F)
         continue;
       if (I->isIndirectCall()) {
-        if (PromotedInsns.count(I))
-          continue;
         uint64_t Sum;
         for (const auto *FS : findIndirectCallFunctionSamples(*I, Sum)) {
           uint64_t SumOrigin = Sum;
           if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
             FS->findInlinedFunctions(InlinedGUIDs, F.getParent(),
                                      PSI->getOrCompHotCountThreshold());
             continue;
           }
           if (!callsiteIsHot(FS, PSI, ProfAccForSymsInList))
             continue;
 
           Candidate = {I, FS, FS->getEntrySamples(), 1.0};
-          if (tryPromoteAndInlineCandidate(F, Candidate, SumOrigin, Sum,
-                                           PromotedInsns)) {
+          if (tryPromoteAndInlineCandidate(F, Candidate, SumOrigin, Sum)) {
             LocalNotInlinedCallSites.erase(I);
             LocalChanged = true;
           }
         }
       } else if (CalledFunction && CalledFunction->getSubprogram() &&
                  !CalledFunction->isDeclaration()) {
         if (tryInlineCandidate(Candidate)) {
           LocalNotInlinedCallSites.erase(I);
SampleProfileLoader::shouldInlineCandidate(InlineCandidate &Candidate) {
 
   // Otherwise only use the cost from call analyzer, but overwite threshold with
   // Sample PGO threshold.
   return InlineCost::get(Cost.getCost(), SampleThreshold);
 }
 
 bool SampleProfileLoader::inlineHotFunctionsWithPriority(
     Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
-  DenseSet<Instruction *> PromotedInsns;
   assert(ProfileIsCS && "Prioritiy based inliner only works with CSSPGO now");
 
   // ProfAccForSymsInList is used in callsiteIsHot. The assertion makes sure
   // Profile symbol list is ignored when profile-sample-accurate is on.
   assert((!ProfAccForSymsInList ||
           (!ProfileSampleAccurate &&
            !F.hasFnAttribute("profile-sample-accurate"))) &&
          "ProfAccForSymsInList should be false when profile-sample-accurate "
while (!CQueue.empty() && F.getInstructionCount() < SizeLimit) {
     InlineCandidate Candidate = CQueue.top();
     CQueue.pop();
     CallBase *I = Candidate.CallInstr;
     Function *CalledFunction = I->getCalledFunction();
 
     if (CalledFunction == &F)
       continue;
     if (I->isIndirectCall()) {
-      if (PromotedInsns.count(I))
-        continue;
       uint64_t Sum;
       auto CalleeSamples = findIndirectCallFunctionSamples(*I, Sum);
       uint64_t SumOrigin = Sum;
       Sum *= Candidate.CallsiteDistribution;
       for (const auto *FS : CalleeSamples) {
         // TODO: Consider disable pre-lTO ICP for MonoLTO as well
         if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) {
           FS->findInlinedFunctions(InlinedGUIDs, F.getParent(),
if (I->isIndirectCall()) {
         if (!PSI->isHotCount(EntryCountDistributed))
           break;
         SmallVector<CallBase *, 8> InlinedCallSites;
         // Attach function profile for promoted indirect callee, and update
         // call site count for the promoted inline candidate too.
         Candidate = {I, FS, EntryCountDistributed,
                      Candidate.CallsiteDistribution};
         if (tryPromoteAndInlineCandidate(F, Candidate, SumOrigin, Sum,
-                                         PromotedInsns, &InlinedCallSites)) {
+                                         &InlinedCallSites)) {
           for (auto *CB : InlinedCallSites) {
             if (getInlineCandidate(&NewCandidate, CB))
               CQueue.emplace(NewCandidate);
           }
           Changed = true;
         }
       }
     } else if (CalledFunction && CalledFunction->getSubprogram() &&
if (BlockWeights[BB]) {
           // inlined and non-inlined targets.
           if (!FunctionSamples::ProfileIsCS) {
             if (const FunctionSamplesMap *M =
                     FS->findFunctionSamplesMapAt(CallSite)) {
               for (const auto &NameFS : *M)
                 Sum += NameFS.second.getEntrySamples();
             }
           }
-          annotateValueSite(*I.getParent()->getParent()->getParent(), I,
-                            SortedCallTargets, Sum, IPVK_IndirectCallTarget,
-                            SortedCallTargets.size());
+          updateIDTMetaData(I, SortedCallTargets, Sum);
         } else if (!isa<IntrinsicInst>(&I)) {
           I.setMetadata(LLVMContext::MD_prof,
                         MDB.createBranchWeights(
                             {static_cast<uint32_t>(BlockWeights[BB])}));
         }
       }
     }
     Instruction *TI = BB->getTerminator();

llvm/test/Transforms/SampleProfile/Inputs/norepeated-icp.prof

+_Z3foov:225715:1
+ 2: 5553
+ 3: 5391
+ 1: _Z3goov:5860
+  1: 5279
+  2: 5279
+  1: _Z3hoov:5860
+    1: 5000
+_Z3goov:5860:1
+ 1: 5279
+ 2: 5279
+ 1: _Z3hoov:5860
+   1: 5000

llvm/test/Transforms/SampleProfile/indirect-call.ll

 !1 = !DIFile(filename: "test.cc", directory: "/")
 !2 = !{i32 2, !"Debug Info Version", i32 3}
 !3 = distinct !DISubprogram(name: "test", scope: !1, file: !1, line: 3, unit: !0)
 !4 = !DILocation(line: 4, scope: !3)
 !5 = !DILocation(line: 6, scope: !3)
 ; CHECK: ![[PROF]] = !{!"VP", i32 0, i64 3457, i64 9191153033785521275, i64 2059, i64 -1069303473483922844, i64 1398}
 ; CHECK: ![[BR1]] = !{!"branch_weights", i32 4000, i32 4000}
 ; CHECK: ![[BR2]] = !{!"branch_weights", i32 3000, i32 1000}
-; CHECK: ![[VP]] = !{!"VP", i32 0, i64 8000, i64 -6391416044382067764, i64 1000}
+; CHECK: ![[VP]] = !{!"VP", i32 0, i64 8000, i64 -6391416044382067764, i64 1000, i64 7476224446746900038, i64 0, i64 925324185419832389, i64 0}
 ; CHECK: ![[BR3]] = !{!"branch_weights", i32 1, i32 0}
 !6 = distinct !DISubprogram(name: "test_inline", scope: !1, file: !1, line: 6, unit: !0)
 !7 = !DILocation(line: 7, scope: !6)
 !8 = distinct !DISubprogram(name: "test_inline_strip", scope: !1, file: !1, line: 8, unit: !0)
 !9 = !DILocation(line: 9, scope: !8)
 !10 = distinct !DISubprogram(name: "test_inline_strip_conflict", scope: !1, file: !1, line: 10, unit: !0)
 !11 = !DILocation(line: 11, scope: !10)
 !12 = distinct !DISubprogram(name: "test_noinline", scope: !1, file: !1, line: 12, unit: !0)

llvm/test/Transforms/SampleProfile/norepeated-icp.ll

+; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/norepeated-icp.prof -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"
+
+@.str = private unnamed_addr constant [5 x i8] c"hoo\0A\00", align 1
+@p = dso_local global void ()* null, align 8
+@str = private unnamed_addr constant [4 x i8] c"hoo\00", align 1
+
+; Function Attrs: uwtable mustprogress
+define dso_local void @_Z3hoov() #0 !dbg !7 {
+entry:
+  %puts = call i32 @puts(i8* nonnull dereferenceable(1) getelementptr inbounds ([4 x i8], [4 x i8]* @str, i64 0, i64 0)), !dbg !9
+  ret void, !dbg !10
+}
+
+; Function Attrs: nofree nounwind
+declare dso_local noundef i32 @printf(i8* nocapture noundef readonly, ...) #1
+
+; Function Attrs: uwtable mustprogress
+define dso_local void @_Z3goov() #0 !dbg !11 {
+entry:
+  %0 = load void ()*, void ()** @p, align 8, !dbg !12, !tbaa !13
+  call void %0(), !dbg !17
+  ret void, !dbg !18
+}
+
+; Check the indirect call in _Z3goov inlined into _Z3foov won't be indirect
+; call promoted for _Z3hoov twice in _Z3foov.
+; CHECK-LABEL: @_Z3foov(
+; CHECK: icmp eq void ()* {{.*}} @_Z3hoov
+; CHECK-NOT: icmp eq void ()* {{.*}} @_Z3hoov
+; CHECK: ret void
+
+; Function Attrs: uwtable mustprogress
+define dso_local void @_Z3foov() #0 !dbg !19 {
+entry:
+  call void @_Z3goov(), !dbg !20
+  ret void, !dbg !21
+}
+
+; Function Attrs: nofree nounwind
+declare noundef i32 @puts(i8* nocapture noundef readonly) #2
+
+attributes #0 = { uwtable mustprogress "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-sample-profile" "use-soft-float"="false" }
+attributes #1 = { nofree nounwind "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nofree nounwind }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "", isOptimized: true, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !2, splitDebugInlining: false, debugInfoForProfiling: true, nameTableKind: None)
+!1 = !DIFile(filename: "1.cc", directory: "")
+!2 = !{}
+!3 = !{i32 7, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!""}
+!7 = distinct !DISubprogram(name: "hoo", linkageName: "_Z3hoov", scope: !1, file: !1, line: 1, type: !8, scopeLine: 1, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!8 = !DISubroutineType(types: !2)
+!9 = !DILocation(line: 2, column: 3, scope: !7)
+!10 = !DILocation(line: 3, column: 1, scope: !7)
+!11 = distinct !DISubprogram(name: "goo", linkageName: "_Z3goov", scope: !1, file: !1, line: 6, type: !8, scopeLine: 6, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!12 = !DILocation(line: 7, column: 5, scope: !11)
+!13 = !{!14, !14, i64 0}
+!14 = !{!"any pointer", !15, i64 0}
+!15 = !{!"omnipotent char", !16, i64 0}
+!16 = !{!"Simple C++ TBAA"}
+!17 = !DILocation(line: 7, column: 3, scope: !11)
+!18 = !DILocation(line: 8, column: 1, scope: !11)
+!19 = distinct !DISubprogram(name: "foo", linkageName: "_Z3foov", scope: !1, file: !1, line: 10, type: !8, scopeLine: 10, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2)
+!20 = !DILocation(line: 11, column: 3, scope: !19)
+!21 = !DILocation(line: 12, column: 3, scope: !19)