[PGO] Add a threshold for number of critical edges in PGO

[xur]

Summary

For some auto-generated sources, we have a huge number of critical edges (like from switch statements).
We have seen instance of 183777 critical edges in one function.
After we split the critical edges in PGO instrumentation/profile-use pass, the CFG is so large that we
have compiler time issues in downstream passes (like in machine CSE and block placement).
Here I add a threshold to skip PGO if the number of critical edges are too large.

The threshold is large enough so that it will not affect the majority of PGO compilation.

Also sync the logic for skipping instrumentation and profile-use. I think
this is the correct thing to do.

[davidxl]

Add a small test case (with small threshold)?

[wenlei]

Why is number of critical edges (as opposed to IR size or number of blocks) a better indicator for function size related build speed issues?

[xur]

In D137184#3900121, @wenlei wrote:

Why is number of critical edges (as opposed to IR size or number of blocks) a better indicator for function size related build speed issues?

If we don't split the critical edge, the CFGs are the same for w/ and w/o PGO (for after PGO pass). So if the CFG is too big for some passes, PGO won't make it worse.

When we split the CFG, the CFGs for w/ and w/o PGO are different. The extra BBs added is roughly proportional to number of critical edges. So more critical edges means more discrepancy.
That's the main reason I choose to use number of critical edges as the threshold.

[xur]

Add a test case, per David's suggestion.

[wenlei]

In D137184#3900182, @xur wrote:

In D137184#3900121, @wenlei wrote:

Why is number of critical edges (as opposed to IR size or number of blocks) a better indicator for function size related build speed issues?

If we don't split the critical edge, the CFGs are the same for w/ and w/o PGO (for after PGO pass). So if the CFG is too big for some passes, PGO won't make it worse.

When we split the CFG, the CFGs for w/ and w/o PGO are different. The extra BBs added is roughly proportional to number of critical edges. So more critical edges means more discrepancy.
That's the main reason I choose to use number of critical edges as the threshold.

Makes sense if the goal is to avoid/limit extra build time incurred from PGO. Thanks for clarification.

[davidxl]

lgtm

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

 
 static cl::opt<std::string> PGOTraceFuncHash(
     "pgo-trace-func-hash", cl::init("-"), cl::Hidden,
     cl::value_desc("function name"),
     cl::desc("Trace the hash of the function with this name."));
 
 static cl::opt<unsigned> PGOFunctionSizeThreshold(
     "pgo-function-size-threshold", cl::Hidden,
-    cl::desc("Do not instrument functions smaller than this threshold"));
+    cl::desc("Do not instrument functions smaller than this threshold."));
 
 static cl::opt<bool> MatchMemProf(
     "pgo-match-memprof", cl::init(true), cl::Hidden,
     cl::desc("Perform matching and annotation of memprof profiles."));
 
+static cl::opt<unsigned> PGOFunctionCriticalEdgeThreshold(
+    "pgo-critical-edge-threshold", cl::init(20000), cl::Hidden,
+    cl::desc("Do not instrument functions with the number of critical edges "
+             " greater than this threshold."));
+
 namespace llvm {
 // 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;
static void collectComdatMembers(
   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));
 }
 
+// Don't perform PGO instrumeatnion / profile-use.
+static bool skipPGO(const Function &F) {
+  if (F.isDeclaration())
+    return true;
+  if (F.hasFnAttribute(llvm::Attribute::NoProfile))
+    return true;
+  if (F.hasFnAttribute(llvm::Attribute::SkipProfile))
+    return true;
+  if (F.getInstructionCount() < PGOFunctionSizeThreshold)
+    return true;
+
+  // If there are too many critical edges, PGO might cause
+  // compiler time problem. Skip PGO if the number of
+  // critical edges execeed the threshold.
+  unsigned NumCriticalEdges = 0;
+  for (auto &BB : F) {
+    const Instruction *TI = BB.getTerminator();
+    for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
+      if (isCriticalEdge(TI, I))
+        NumCriticalEdges++;
+    }
+  }
+  if (NumCriticalEdges > PGOFunctionCriticalEdgeThreshold) {
+    LLVM_DEBUG(dbgs() << "In func " << F.getName()
+                      << ", NumCriticalEdges=" << NumCriticalEdges
+                      << " exceed the threshold. Skip PGO.\n");
+    return true;
+  }
+
+  return false;
+}
+
 static bool InstrumentAllFunctions(
     Module &M, function_ref<TargetLibraryInfo &(Function &)> LookupTLI,
     function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
     function_ref<BlockFrequencyInfo *(Function &)> LookupBFI, 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;
-    if (F.hasFnAttribute(llvm::Attribute::NoProfile))
-      continue;
-    if (F.hasFnAttribute(llvm::Attribute::SkipProfile))
-      continue;
-    if (F.getInstructionCount() < PGOFunctionSizeThreshold)
+    if (skipPGO(F))
       continue;
     auto &TLI = LookupTLI(F);
     auto *BPI = LookupBPI(F);
     auto *BFI = LookupBFI(F);
     instrumentOneFunc(F, &M, TLI, BPI, BFI, ComdatMembers, IsCS);
   }
   return true;
 }
static bool annotateAllFunctions(
   std::vector<Function *> ColdFunctions;
 
   // If the profile marked as always instrument the entry BB, do the
   // same. Note this can be overwritten by the internal option in CFGMST.h
   bool InstrumentFuncEntry = PGOReader->instrEntryBBEnabled();
   if (PGOInstrumentEntry.getNumOccurrences() > 0)
     InstrumentFuncEntry = PGOInstrumentEntry;
   for (auto &F : M) {
-    if (F.isDeclaration())
+    if (skipPGO(F))
       continue;
     auto &TLI = LookupTLI(F);
     auto *BPI = LookupBPI(F);
     auto *BFI = LookupBFI(F);
     // Split indirectbr critical edges here before computing the MST rather than
     // later in getInstrBB() to avoid invalidating it.
     SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/false, BPI, BFI);
     PGOUseFunc Func(F, &M, TLI, ComdatMembers, BPI, BFI, PSI, IsCS,

llvm/test/Transforms/PGOProfile/critical-edge-threshold.ll

+; Test the critical edge threahold
+; RUN: opt < %s -passes=pgo-instr-gen -pgo-critical-edge-threshold=1 -pgo-instrument-entry=true -S | FileCheck %s
+
+@sum = dso_local global i32 0, align 4
+
+define void @foo(i32 %a, i32 %b) {
+entry:
+  %tobool.not = icmp eq i32 %a, 0
+  br i1 %tobool.not, label %if.end4, label %if.then
+
+if.then:
+  %0 = load i32, ptr @sum, align 4
+  %inc = add nsw i32 %0, 1
+  store i32 %inc, ptr @sum, align 4
+  %tobool1.not = icmp eq i32 %b, 0
+  br i1 %tobool1.not, label %if.end4, label %if.then2
+
+if.then2:
+  %inc3 = add nsw i32 %0, 2
+  store i32 %inc3, ptr @sum, align 4
+  br label %if.end4
+
+if.end4:
+  ret void
+}
+
+; CHECK-NOT: call void @llvm.instrprof.increment(ptr @__profn_foo