Separate the ICP total threshold and remaining threshold.

[danielcdh]

Summary

In the current implementation, isPromotionProfitable only checks if the call count to a direct target is no less than a certain percentage threshold of the remaining call counts that have not been promoted. This causes code size problems when the target count is small but greater than a large portion of remaining counts. E.g. target1 takes 99.9%, while target2 takes 0.1%. Both targets will be promoted and inlined, makes the function size too large, which potentially prevents it from further inlining into its callers. This patch adds another percentage threshold against the total indirect call count. If the target count needs to be no less than both thresholds in order to be promoted speculatively.

[tejohnson]

lib/Analysis/IndirectCallPromotionAnalysis.cpp

47

In your 99.9% and 0.1% case, won't the 0.1% still get promoted since it is 100% of the remaining count after promoting the 99.9% target?

[danielcdh]

lib/Analysis/IndirectCallPromotionAnalysis.cpp

47

Before the patch, yes, but with the patch, the 0.1% will be lower than the 5% threshold, thus it will not be promoted.

[tejohnson]

LGTM

lib/Analysis/IndirectCallPromotionAnalysis.cpp

47

Got it - I was thinking the remaining count check was the new one, but it is essentially the old one.

include/llvm/Analysis/IndirectCallPromotionAnalysis.h

 
 // Class for identifying profitable indirect call promotion candidates when
 // the indirect-call value profile metadata is available.
 class ICallPromotionAnalysis {
 private:
   // Allocate space to read the profile annotation.
   std::unique_ptr<InstrProfValueData[]> ValueDataArray;
 
-  // Count is the call count for the direct-call target and
-  // TotalCount is the call count for the indirect-call callsite.
+  // Count is the call count for the direct-call target.
+  // TotalCount is the total call count for the indirect-call callsite.
+  // RemainingCount is the TotalCount minus promoted-direct-call count.
   // Return true we should promote this indirect-call target.
-  bool isPromotionProfitable(uint64_t Count, uint64_t TotalCount);
+  bool isPromotionProfitable(uint64_t Count, uint64_t TotalCount,
+                             uint64_t RemainingCount);
 
   // Returns the number of profitable candidates to promote for the
   // current ValueDataArray and the given \p Inst.
   uint32_t getProfitablePromotionCandidates(const Instruction *Inst,
                                             uint32_t NumVals,
                                             uint64_t TotalCount);
 
   // Noncopyable

lib/Analysis/IndirectCallPromotionAnalysis.cpp

 // promotion candidate.
 static cl::opt<unsigned>
     ICPCountThreshold("icp-count-threshold", cl::Hidden, cl::ZeroOrMore,
                       cl::init(1000),
                       cl::desc("The minimum count to the direct call target "
                                "for the promotion"));
 
 // The percent threshold for the direct-call target (this call site vs the
+// remaining call count) for it to be considered as the promotion target.
+static cl::opt<unsigned> ICPRemainingPercentThreshold(
+    "icp-remaining-percent-threshold", cl::init(30), cl::Hidden, cl::ZeroOrMore,
+    cl::desc("The percentage threshold against remaining unpromoted indirect "
+             "call count for the promotion"));
+
+// The percent threshold for the direct-call target (this call site vs the
 // total call count) for it to be considered as the promotion target.
 static cl::opt<unsigned>
-    ICPPercentThreshold("icp-percent-threshold", cl::init(30), cl::Hidden,
-                        cl::ZeroOrMore,
-                        cl::desc("The percentage threshold for the promotion"));
+    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>
     MaxNumPromotions("icp-max-prom", cl::init(2), cl::Hidden, cl::ZeroOrMore,
                      cl::desc("Max number of promotions for a single indirect "
                               "call callsite"));
 
 ICallPromotionAnalysis::ICallPromotionAnalysis() {
   ValueDataArray = llvm::make_unique<InstrProfValueData[]>(MaxNumPromotions);
 }
 
 bool ICallPromotionAnalysis::isPromotionProfitable(uint64_t Count,
-                                                   uint64_t TotalCount) {
-  if (Count < ICPCountThreshold)
-    return false;
-
-  unsigned Percentage = (Count * 100) / TotalCount;
-  return (Percentage >= ICPPercentThreshold);
+                                                   uint64_t TotalCount,
+                                                   uint64_t RemainingCount) {
+  return Count >= ICPCountThreshold &&
+         Count * 100 >= ICPRemainingPercentThreshold * RemainingCount &&
+         Count * 100 >= ICPTotalPercentThreshold * TotalCount;
 }
 
 // Indirect-call promotion heuristic. The direct targets are sorted based on
 // the count. Stop at the first target that is not promoted. Returns the
 // number of candidates deemed profitable.
 uint32_t ICallPromotionAnalysis::getProfitablePromotionCandidates(
     const Instruction *Inst, uint32_t NumVals, uint64_t TotalCount) {
   ArrayRef<InstrProfValueData> ValueDataRef(ValueDataArray.get(), NumVals);
 
   DEBUG(dbgs() << " \nWork on callsite " << *Inst << " Num_targets: " << NumVals
                << "\n");
 
   uint32_t I = 0;
+  uint64_t RemainingCount = TotalCount;
   for (; I < MaxNumPromotions && I < NumVals; I++) {
     uint64_t Count = ValueDataRef[I].Count;
-    assert(Count <= TotalCount);
+    assert(Count <= RemainingCount);
     DEBUG(dbgs() << " Candidate " << I << " Count=" << Count
                  << "  Target_func: " << ValueDataRef[I].Value << "\n");
 
-    if (!isPromotionProfitable(Count, TotalCount)) {
+    if (!isPromotionProfitable(Count, TotalCount, RemainingCount)) {
       DEBUG(dbgs() << " Not promote: Cold target.\n");
       return I;
     }
-    TotalCount -= Count;
+    RemainingCount -= Count;
   }
   return I;
 }
 
 ArrayRef<InstrProfValueData>
 ICallPromotionAnalysis::getPromotionCandidatesForInstruction(
     const Instruction *I, uint32_t &NumVals, uint64_t &TotalCount,
     uint32_t &NumCandidates) {

test/Transforms/PGOProfile/indirect_call_promotion.ll

 ; RUN: opt < %s -pgo-icall-prom -S | FileCheck %s --check-prefix=ICALL-PROM
 ; RUN: opt < %s -pgo-icall-prom -S -icp-samplepgo | FileCheck %s --check-prefix=ICALL-PROM
 ; RUN: opt < %s -pgo-icall-prom -S -icp-samplepgo | FileCheck %s --check-prefix=ICALL-PROM-SAMPLEPGO
 ; RUN: opt < %s -passes=pgo-icall-prom -S | FileCheck %s --check-prefix=ICALL-PROM
-; RUN: opt < %s -pgo-icall-prom -S -pass-remarks=pgo-icall-prom -icp-count-threshold=0 -icp-percent-threshold=0 -icp-max-prom=4 2>&1 | FileCheck %s --check-prefix=PASS-REMARK
-; RUN: opt < %s -passes=pgo-icall-prom -S -pass-remarks=pgo-icall-prom -icp-count-threshold=0 -icp-percent-threshold=0 -icp-max-prom=4 2>&1 | FileCheck %s --check-prefix=PASS-REMARK
+; RUN: opt < %s -pgo-icall-prom -S -pass-remarks=pgo-icall-prom -icp-count-threshold=0 -icp-remaining-percent-threshold=0 -icp-total-percent-threshold=0 -icp-max-prom=4 2>&1 | FileCheck %s --check-prefix=PASS-REMARK
+; RUN: opt < %s -passes=pgo-icall-prom -S -pass-remarks=pgo-icall-prom -icp-count-threshold=0 -icp-remaining-percent-threshold=0 -icp-total-percent-threshold=0 -icp-max-prom=4 2>&1 | FileCheck %s --check-prefix=PASS-REMARK
+; RUN: opt < %s -passes=pgo-icall-prom -S -pass-remarks=pgo-icall-prom -icp-count-threshold=0 -icp-remaining-percent-threshold=0 -icp-total-percent-threshold=20 -icp-max-prom=4 2>&1 | FileCheck %s --check-prefix=PASS2-REMARK
+
 ; PASS-REMARK: remark: <unknown>:0:0: Promote indirect call to func4 with count 1030 out of 1600
 ; PASS-REMARK: remark: <unknown>:0:0: Promote indirect call to func2 with count 410 out of 570
 ; PASS-REMARK: remark: <unknown>:0:0: Promote indirect call to func3 with count 150 out of 160
 ; PASS-REMARK: remark: <unknown>:0:0: Promote indirect call to func1 with count 10 out of 10
 
+; PASS2-REMARK: remark: <unknown>:0:0: Promote indirect call to func4 with count 1030 out of 1600
+; PASS2-REMARK: remark: <unknown>:0:0: Promote indirect call to func2 with count 410 out of 570
+; PASS2-REMARK-NOT: remark: <unknown>:0:0: Promote indirect call to func3
+; PASS2-REMARK-NOT: remark: <unknown>:0:0: Promote indirect call to func1
+
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @foo = common global i32 ()* null, align 8
 
 define i32 @func1() {
 entry:
   ret i32 0