[PGO] De-Optimizing cold functions based on PGO info (PATCH 1/2)

[myhsu]

Summary

This patch disables optimizations on IR Functions that are considered “cold” by PGO
profiles. The primary goal for this work is to improve code optimization
speed (which also improves compilation and LTO speed) without making too
much impact on target code performance.

The mechanism is pretty simple: In the second phase (i.e. optimization
phase) of PGO, we would add optnone attributes on functions that are
considered “cold”. That is, functions with low profiling counts.

In addition to de-optimizing on functions whose profiling counts are
exactly zero (the -profile-omit-cold-func-opt flag). If the previous CLI flag
is enabled, another knob (-profile-omit-cold-func-opt-percent=<X percent>) can
be used to adjust the “cold threshold”. That is, after sorting profiling counts
of all functions, this knob provides an option to de-optimize functions
whose count values are sitting in the lower X percent.

Our evaluation results showed an average of 10% compilation speed
improvement with up to 2% performance overhead on various of thresholds using the
LLVM Test Suite as the benchmark. Using with FullLTO, it brought average
of 20% (LTO) link time improvement with up to 2% performance overhead.

Second part of this patch series: https://reviews.llvm.org/D87338

authors: myhsu, probinson, and edd

[davidxl]

This is in theory similar to profile guided size optimization -- the difference is that optnone may not result in size reduction.

[lebedev.ri]

As per https://llvm.org/docs/LangRef.html, deopt term appears to be already coined.

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1776

llvm::sort

[hjyamauchi]

In D87337#2262611, @lebedev.ri wrote:

As per https://llvm.org/docs/LangRef.html, deopt term appears to be already coined.

Yeah, I think deopt already means something else in the JIT compiler. I'd avoid the term.

[myhsu]

In D87337#2263611, @yamauchi wrote:

In D87337#2262611, @lebedev.ri wrote:

As per https://llvm.org/docs/LangRef.html, deopt term appears to be already coined.

Yeah, I think deopt already means something else in the JIT compiler. I'd avoid the term.

Good call, I didn't know that. I'll come up with an alternative one

[myhsu]

1. Fix minor formatting issues (NFC)
2. Rename "profile-deopt-cold-*" into "profile-omit-cold-func-opt-*"

[rengolin]

Implementation-wise, this looks good, but I wonder if we could join minsize with this using the same (or very similar) controls.

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1808

Nit: keep the same language "Set optnone..."

llvm/test/Transforms/PGOProfile/omit-cold-func-opt.ll

12

IIUC, the range is inclusive. So, would be nice to have an additional 50% test to show that.

[myhsu]

In D87337#2265379, @rengolin wrote:

Implementation-wise, this looks good, but I wonder if we could join minsize with this using the same (or very similar) controls.

As I mentioned in the RFC thread, I think it's a good idea :-) Though I prefer to send out a separate review for the optsize / minsize work since I think they should have their own flags, given the fact that they're kinda conflict with optnone here (i.e. it doesn't really make sense to add both optsize and optnone at the same time).
Does that make sense to you?

[myhsu]

• Fix wording (NFC)
• Add 50% test and restructure the test file

[myhsu]

Ping. Just want to check out if we all agree to flush out this patch series first before supporting optsize / minsize as per our discussions in the RFC thread

[rengolin]

In D87337#2272515, @myhsu wrote:

Ping. Just want to check out if we all agree to flush out this patch series first before supporting optsize / minsize as per our discussions in the RFC thread

I'm happy as long as there's a short period between the two implementations, hopefully weeks. They should definitely not cross the release branch barrier.

But I haven't worked on the PGO side and I don't use PGO directly, so perhaps someone working on the area should voice their opinions, which will certainly be stronger than mine.

[myhsu]

just realized I haven't updated this patch for years. I'll come up with an up-to-date version when I have time.

llvm/include/llvm/IR/Function.h

public:
   bool hasOptSize() const {
     return hasFnAttribute(Attribute::OptimizeForSize) || hasMinSize();
   }
 
   /// copyAttributesFrom - copy all additional attributes (those not needed to
   /// create a Function) from the Function Src to this one.
   void copyAttributesFrom(const Function *Src);
 
+  /// markOptnoneIfPossible - mark this function with `optnone` without
+  /// conflicting with other attributes (e.g. alwaysinline)
+  void markOptnoneIfPossible();
+
   /// deleteBody - This method deletes the body of the function, and converts
   /// the linkage to external.
   ///
   void deleteBody() {
     dropAllReferences();
     setLinkage(ExternalLinkage);
   }
 

llvm/lib/IR/Function.cpp

void Function::copyAttributesFrom(const Function *Src) {
   if (Src->hasPersonalityFn())
     setPersonalityFn(Src->getPersonalityFn());
   if (Src->hasPrefixData())
     setPrefixData(Src->getPrefixData());
   if (Src->hasPrologueData())
     setPrologueData(Src->getPrologueData());
 }
 
+/// Mark this function with `optnone` without conflicting
+/// with other attributes (e.g. alwaysinline)
+void Function::markOptnoneIfPossible() {
+  if (hasFnAttribute(Attribute::MinSize) ||
+      hasFnAttribute(Attribute::AlwaysInline))
+    return;
+  // OptimizeNone requires NoInline.
+  addFnAttr(Attribute::OptimizeNone);
+  addFnAttr(Attribute::NoInline);
+}
+
 /// Table of string intrinsic names indexed by enum value.
 static const char * const IntrinsicNameTable[] = {
   "not_intrinsic",
 #define GET_INTRINSIC_NAME_TABLE
 #include "llvm/IR/IntrinsicImpl.inc"
 #undef GET_INTRINSIC_NAME_TABLE
 };
 

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

 // 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 cl::opt<bool>
     PGOOldCFGHashing("pgo-instr-old-cfg-hashing", cl::init(false), cl::Hidden,
                      cl::desc("Use the old CFG function hashing"));
 
+// Command-line option to mark cold functions as Optnone.
+cl::opt<bool> OmitColdFuncOpt("profile-omit-cold-func-opt", cl::init(false),
+                              cl::Hidden,
+                              cl::desc("Add 'optnone' to cold functions "
+                                       "if possible"));
+cl::opt<unsigned> OmitColdFuncOptPercentage(
+    "profile-omit-cold-func-opt-percent", cl::init(0U), cl::Hidden,
+    cl::desc("Function at the # lower percentage would be "
+             "considered cold"));
+
 // Return a string describing the branch condition that can be
 // used in static branch probability heuristics:
 static std::string getBranchCondString(Instruction *TI) {
   BranchInst *BI = dyn_cast<BranchInst>(TI);
   if (!BI || !BI->isConditional())
     return std::string();
 
   Value *Cond = BI->getCondition();
M.setProfileSummary(PGOReader->getSummary(IsCS).getMD(M.getContext()),
                            : ProfileSummary::PSK_Instr);
   PSI->refresh();
 
   std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
   collectComdatMembers(M, ComdatMembers);
   std::vector<Function *> HotFunctions;
   std::vector<Function *> ColdFunctions;
 
+  if (OmitColdFuncOpt) {
+    // OmitColdFuncOptPercentage validation
+    if (OmitColdFuncOptPercentage > 100U) {
+      Ctx.diagnose(DiagnosticInfoPGOProfile(
+          ProfileFileName.data(),
+          "Invalid range of `-profile-deopt-cold-percent` "
+          "(should be within [0,100])"));
+      return false;
+    }
+  }
+
   // 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;
+
+  using FuncCountEntry = std::pair<Function *, CountSumOrPercent>;
+  SmallVector<FuncCountEntry, 4> FuncCounts;
+
   for (auto &F : M) {
     if (F.isDeclaration())
       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, BPI, BFI);
     PGOUseFunc Func(F, &M, TLI, ComdatMembers, BPI, BFI, PSI, IsCS,
                     InstrumentFuncEntry);
     // When AllMinusOnes is true, it means the profile for the function
     // is unrepresentative and this function is actually hot. Set the
     // entry count of the function to be multiple times of hot threshold
     // and drop all its internal counters.
     bool AllMinusOnes = false;
     bool AllZeros = false;
     if (!Func.readCounters(PGOReader.get(), AllZeros, AllMinusOnes))
       continue;
+
     if (AllZeros) {
       F.setEntryCount(ProfileCount(0, Function::PCT_Real));
       if (Func.getProgramMaxCount() != 0)
         ColdFunctions.push_back(&F);
       continue;
     }
+
+    CountSumOrPercent FuncAccumCount;
+    Func.getProfileRecord().accumulateCounts(FuncAccumCount);
+    FuncCounts.emplace_back(&F, std::move(FuncAccumCount));
+
     const unsigned MultiplyFactor = 3;
     if (AllMinusOnes) {
       uint64_t HotThreshold = PSI->getHotCountThreshold();
       if (HotThreshold)
         F.setEntryCount(
             ProfileCount(HotThreshold * MultiplyFactor, Function::PCT_Real));
       HotFunctions.push_back(&F);
       continue;
if (PGOViewRawCounts != PGOVCT_None &&
           ViewGraph(&Func, Twine("PGORawCounts_") + Func.getFunc().getName());
       else if (PGOViewRawCounts == PGOVCT_Text) {
         dbgs() << "pgo-view-raw-counts: " << Func.getFunc().getName() << "\n";
         Func.dumpInfo();
       }
     }
   }
 
+  if (OmitColdFuncOpt) {
+    llvm::sort(FuncCounts.begin(), FuncCounts.end(),
+               [](const FuncCountEntry &LHS, const FuncCountEntry &RHS) {
+                 const auto &LHSCount = LHS.second;
+                 const auto &RHSCount = RHS.second;
+                 uint64_t LHSAvg = LHSCount.CountSum / LHSCount.NumEntries;
+                 uint64_t RHSAvg = RHSCount.CountSum / RHSCount.NumEntries;
+                 return LHSAvg < RHSAvg;
+               });
+
+    auto NumFuncs = FuncCounts.size();
+    int NumCold = NumFuncs * OmitColdFuncOptPercentage / 100U;
+    for (int I = 0; I < NumCold; ++I) {
+      ColdFunctions.push_back(FuncCounts[I].first);
+    }
+  }
+
   // Set function hotness attribute from the profile.
   // We have to apply these attributes at the end because their presence
   // can affect the BranchProbabilityInfo of any callers, resulting in an
   // inconsistent MST between prof-gen and prof-use.
   for (auto &F : HotFunctions) {
     F->addFnAttr(Attribute::InlineHint);
     LLVM_DEBUG(dbgs() << "Set inline attribute to function: " << F->getName()
                       << "\n");
   }
   for (auto &F : ColdFunctions) {
     F->addFnAttr(Attribute::Cold);
     LLVM_DEBUG(dbgs() << "Set cold attribute to function: " << F->getName()
                       << "\n");
+    // Optionally mark optnone as well.
+    if (OmitColdFuncOpt) {
+      F->markOptnoneIfPossible();
+      LLVM_DEBUG(dbgs() << "Set optnone attribute to function: " << F->getName()
+                        << "\n");
+    }
   }
   return true;
 }
 
 PGOInstrumentationUse::PGOInstrumentationUse(std::string Filename,
                                              std::string RemappingFilename,
                                              bool IsCS)
     : ProfileFileName(std::move(Filename)),

llvm/test/Transforms/PGOProfile/Inputs/omit-cold-func-opt.proftext

+# IR level Instrumentation Flag
+:ir
+func_0
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+0
+
+func_10
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+3
+
+func_100
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+12
+
+func_20
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+4
+
+func_30
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+5
+
+func_40
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+6
+
+func_50
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+7
+
+func_60
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+8
+
+func_70
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+9
+
+func_80
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+10
+
+func_90
+# Func Hash:
+742261418966908927
+# Num Counters:
+1
+# Counter Values:
+11
+
+main
+# Func Hash:
+950994589843891609
+# Num Counters:
+11
+# Counter Values:
+4
+5
+6
+7
+8
+9
+10
+11
+12
+3
+1
+

llvm/test/Transforms/PGOProfile/omit-cold-func-opt.ll

+; ModuleID = './test_disopt_cold.c'
+
+; RUN: llvm-profdata merge %S/Inputs/omit-cold-func-opt.proftext -o %t.profdata
+
+source_filename = "./test_disopt_cold.c"
+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"
+
+; RUN: opt < %s -pgo-instr-use -pgo-test-profile-file=%t.profdata -profile-omit-cold-func-opt -S -o - | FileCheck --check-prefix=CHECK-0-PERCENT %s
+
+; RUN: opt < %s -pgo-instr-use -pgo-test-profile-file=%t.profdata -profile-omit-cold-func-opt -profile-omit-cold-func-opt-percent=25 -S -o - | FileCheck --check-prefix=CHECK-25-PERCENT %s
+
+; RUN: opt < %s -pgo-instr-use -pgo-test-profile-file=%t.profdata -profile-omit-cold-func-opt -profile-omit-cold-func-opt-percent=50 -S -o - | FileCheck --check-prefix=CHECK-50-PERCENT %s
+
+; CHECK-0-PERCENT: optnone
+; CHECK-0-PERCENT-NEXT: define {{.*}} i32 @func_0
+
+; CHECK-25-PERCENT: optnone
+; CHECK-25-PERCENT-NEXT: define {{.*}} i32 @func_0
+; CHECK-25-PERCENT: optnone
+; CHECK-25-PERCENT-NEXT: define {{.*}} i32 @func_10
+; CHECK-25-PERCENT: optnone
+; CHECK-25-PERCENT-NEXT: define {{.*}} i32 @func_20
+
+; CHECK-50-PERCENT: optnone
+; CHECK-50-PERCENT-NEXT: define {{.*}} i32 @func_0
+; CHECK-50-PERCENT: optnone
+; CHECK-50-PERCENT-NEXT: define {{.*}} i32 @func_10
+; CHECK-50-PERCENT: optnone
+; CHECK-50-PERCENT-NEXT: define {{.*}} i32 @func_20
+; CHECK-50-PERCENT: optnone
+; CHECK-50-PERCENT-NEXT: define {{.*}} i32 @func_30
+; CHECK-50-PERCENT: optnone
+; CHECK-50-PERCENT-NEXT: define {{.*}} i32 @func_40
+; CHECK-50-PERCENT: optnone
+; CHECK-50-PERCENT-NEXT: define {{.*}} i32 @func_50
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_0(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 94
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_10(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 894794
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_20(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 894794
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_30(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 994874
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_40(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 879944
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_50(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 994487
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_60(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 984794
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_70(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 949487
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_80(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 948794
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_90(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 9487
+  ret i32 %add
+}
+
+; Function Attrs: norecurse nounwind readnone uwtable
+define dso_local i32 @func_100(i32 %x) local_unnamed_addr #0 {
+entry:
+  %add = add nsw i32 %x, 87
+  ret i32 %add
+}
+
+attributes #0 = { norecurse nounwind readnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "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-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"https://github.com/llvm/llvm-project"}