[PGO] Function section hotness prefix should look at all blocks

[tejohnson]

Summary

The function section prefix for PGO based layout (e.g. hot/unlikely)
should look at the hotness of all blocks not just the entry BB.
A function with a cold entry but a very hot loop should be placed in the
hot section, for example, so that it is located close to other hot
functions it may call. For SamplePGO it was already looking at the
branch weights on calls, and I made that code conditional on whether
this is SamplePGO since it was essentially a noop for instrumentation
PGO anyway.

[davidxl]

lgtm

llvm/trunk/include/llvm/Analysis/ProfileSummaryInfo.h

public:
 
   /// Returns the profile count for \p CallInst.
   Optional<uint64_t> getProfileCount(const Instruction *CallInst,
                                      BlockFrequencyInfo *BFI);
   /// Returns true if the working set size of the code is considered huge.
   bool hasHugeWorkingSetSize();
   /// \brief Returns true if \p F has hot function entry.
   bool isFunctionEntryHot(const Function *F);
-  /// Returns true if \p F has hot function entry or hot call edge.
-  bool isFunctionHotInCallGraph(const Function *F);
+  /// Returns true if \p F contains hot code.
+  bool isFunctionHotInCallGraph(const Function *F, BlockFrequencyInfo &BFI);
   /// \brief Returns true if \p F has cold function entry.
   bool isFunctionEntryCold(const Function *F);
-  /// Returns true if \p F has cold function entry or cold call edge.
-  bool isFunctionColdInCallGraph(const Function *F);
+  /// Returns true if \p F contains only cold code.
+  bool isFunctionColdInCallGraph(const Function *F, BlockFrequencyInfo &BFI);
   /// \brief Returns true if \p F is a hot function.
   bool isHotCount(uint64_t C);
   /// \brief Returns true if count \p C is considered cold.
   bool isColdCount(uint64_t C);
   /// \brief Returns true if BasicBlock \p B is considered hot.
   bool isHotBB(const BasicBlock *B, BlockFrequencyInfo *BFI);
   /// \brief Returns true if BasicBlock \p B is considered cold.
   bool isColdBB(const BasicBlock *B, BlockFrequencyInfo *BFI);

llvm/trunk/lib/Analysis/ProfileSummaryInfo.cpp

if (!F || !computeSummary())
     return false;
   auto FunctionCount = F->getEntryCount();
   // FIXME: The heuristic used below for determining hotness is based on
   // preliminary SPEC tuning for inliner. This will eventually be a
   // convenience method that calls isHotCount.
   return FunctionCount && isHotCount(FunctionCount.getValue());
 }
 
-/// Returns true if the function's entry or total call edge count is hot.
+/// Returns true if the function contains hot code. This can include a hot
+/// function entry count, hot basic block, or (in the case of Sample PGO)
+/// hot total call edge count.
 /// If it returns false, it either means it is not hot or it is unknown
-/// whether it is hot or not (for example, no profile data is available).
-bool ProfileSummaryInfo::isFunctionHotInCallGraph(const Function *F) {
+/// (for example, no profile data is available).
+bool ProfileSummaryInfo::isFunctionHotInCallGraph(const Function *F,
+                                                  BlockFrequencyInfo &BFI) {
   if (!F || !computeSummary())
     return false;
   if (auto FunctionCount = F->getEntryCount())
     if (isHotCount(FunctionCount.getValue()))
       return true;
 
+  if (hasSampleProfile()) {
     uint64_t TotalCallCount = 0;
     for (const auto &BB : *F)
       for (const auto &I : BB)
         if (isa<CallInst>(I) || isa<InvokeInst>(I))
           if (auto CallCount = getProfileCount(&I, nullptr))
             TotalCallCount += CallCount.getValue();
-  return isHotCount(TotalCallCount);
+    if (isHotCount(TotalCallCount))
+      return true;
+  }
+  for (const auto &BB : *F)
+    if (isHotBB(&BB, &BFI))
+      return true;
+  return false;
 }
 
-/// Returns true if the function's entry and total call edge count is cold.
+/// Returns true if the function only contains cold code. This means that
+/// the function entry and blocks are all cold, and (in the case of Sample PGO)
+/// the total call edge count is cold.
 /// If it returns false, it either means it is not cold or it is unknown
-/// whether it is cold or not (for example, no profile data is available).
-bool ProfileSummaryInfo::isFunctionColdInCallGraph(const Function *F) {
+/// (for example, no profile data is available).
+bool ProfileSummaryInfo::isFunctionColdInCallGraph(const Function *F,
+                                                   BlockFrequencyInfo &BFI) {
   if (!F || !computeSummary())
     return false;
   if (auto FunctionCount = F->getEntryCount())
     if (!isColdCount(FunctionCount.getValue()))
       return false;
-  
+  if (hasSampleProfile()) {
     uint64_t TotalCallCount = 0;
     for (const auto &BB : *F)
-    for (const auto &I : BB) 
+      for (const auto &I : BB)
         if (isa<CallInst>(I) || isa<InvokeInst>(I))
           if (auto CallCount = getProfileCount(&I, nullptr))
             TotalCallCount += CallCount.getValue();
-  return isColdCount(TotalCallCount);
+    if (!isColdCount(TotalCallCount))
+      return false;
+  }
+  for (const auto &BB : *F)
+    if (!isColdBB(&BB, &BFI))
+      return false;
+  return true;
 }
 
 /// Returns true if the function's entry is a cold. If it returns false, it
 /// either means it is not cold or it is unknown whether it is cold or not (for
 /// example, no profile data is available).
 bool ProfileSummaryInfo::isFunctionEntryCold(const Function *F) {
   if (!F)
     return false;

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

if (skipFunction(F))
     return false;
 
   DL = &F.getParent()->getDataLayout();
 
   bool EverMadeChange = false;
   // Clear per function information.
   InsertedInsts.clear();
   PromotedInsts.clear();
-  BFI.reset();
-  BPI.reset();
 
   ModifiedDT = false;
   if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>()) {
     TM = &TPC->getTM<TargetMachine>();
     SubtargetInfo = TM->getSubtargetImpl(F);
     TLI = SubtargetInfo->getTargetLowering();
     TRI = SubtargetInfo->getRegisterInfo();
   }
   TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  BPI.reset(new BranchProbabilityInfo(F, *LI));
+  BFI.reset(new BlockFrequencyInfo(F, *BPI, *LI));
   OptSize = F.optForSize();
 
   ProfileSummaryInfo *PSI =
       getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
   if (ProfileGuidedSectionPrefix) {
-    if (PSI->isFunctionHotInCallGraph(&F))
+    if (PSI->isFunctionHotInCallGraph(&F, *BFI))
       F.setSectionPrefix(".hot");
-    else if (PSI->isFunctionColdInCallGraph(&F))
+    else if (PSI->isFunctionColdInCallGraph(&F, *BFI))
       F.setSectionPrefix(".unlikely");
   }
 
   /// This optimization identifies DIV instructions that can be
   /// profitably bypassed and carried out with a shorter, faster divide.
   if (!OptSize && !PSI->hasHugeWorkingSetSize() && TLI &&
       TLI->isSlowDivBypassed()) {
     const DenseMap<unsigned int, unsigned int> &BypassWidths =
bool CodeGenPrepare::isMergingEmptyBlockProfitable(BasicBlock *BB,
   }
 
   // See if all BB's incoming values are same as the value from Pred. In this
   // case, no reason to skip merging because COPYs are expected to be place in
   // Pred already.
   if (SameIncomingValueBBs.count(Pred))
     return true;
 
-  if (!BFI) {
-    Function &F = *BB->getParent();
-    LoopInfo LI{DominatorTree(F)};
-    BPI.reset(new BranchProbabilityInfo(F, LI));
-    BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
-  }
-
   BlockFrequency PredFreq = BFI->getBlockFreq(Pred);
   BlockFrequency BBFreq = BFI->getBlockFreq(BB);
 
   for (auto SameValueBB : SameIncomingValueBBs)
     if (SameValueBB->getUniquePredecessor() == Pred &&
         DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
       BBFreq += BFI->getBlockFreq(SameValueBB);
 

llvm/trunk/test/Transforms/CodeGenPrepare/section.ll

 ; RUN: opt < %s -codegenprepare -S | FileCheck %s
 
 target triple = "x86_64-pc-linux-gnu"
 
 ; This tests that hot/cold functions get correct section prefix assigned
 
-; CHECK: hot_func{{.*}}!section_prefix ![[HOT_ID:[0-9]+]]
+; CHECK: hot_func1{{.*}}!section_prefix ![[HOT_ID:[0-9]+]]
 ; The entry is hot
-define void @hot_func() !prof !15 {
+define void @hot_func1() !prof !15 {
   ret void
 }
 
-; For instrumentation based PGO, we should only look at entry counts,
+; CHECK: hot_func2{{.*}}!section_prefix ![[HOT_ID:[0-9]+]]
+; Entry is cold but inner block is hot
+define void @hot_func2(i32 %n) !prof !16 {
+entry:
+  %n.addr = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32 %n, i32* %n.addr, align 4
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:
+  %0 = load i32, i32* %i, align 4
+  %1 = load i32, i32* %n.addr, align 4
+  %cmp = icmp slt i32 %0, %1
+  br i1 %cmp, label %for.body, label %for.end, !prof !19
+
+for.body:
+  %2 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %2, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond
+
+for.end:
+  ret void
+}
+
+; For instrumentation based PGO, we should only look at block counts,
 ; not call site VP metadata (which can exist on value profiled memcpy,
 ; or possibly left behind after static analysis based devirtualization).
 ; CHECK: cold_func1{{.*}}!section_prefix ![[COLD_ID:[0-9]+]]
 define void @cold_func1() !prof !16 {
-  call void @hot_func(), !prof !17
-  call void @hot_func(), !prof !17
+  call void @hot_func1(), !prof !17
+  call void @hot_func1(), !prof !17
   ret void
 }
 
-; CHECK: cold_func2{{.*}}!section_prefix
+; CHECK: cold_func2{{.*}}!section_prefix ![[COLD_ID]]
 define void @cold_func2() !prof !16 {
-  call void @hot_func(), !prof !17
-  call void @hot_func(), !prof !18
-  call void @hot_func(), !prof !18
+  call void @hot_func1(), !prof !17
+  call void @hot_func1(), !prof !18
+  call void @hot_func1(), !prof !18
   ret void
 }
 
 ; CHECK: cold_func3{{.*}}!section_prefix ![[COLD_ID]]
 define void @cold_func3() !prof !16 {
-  call void @hot_func(), !prof !18
+  call void @hot_func1(), !prof !18
   ret void
 }
 
 ; CHECK: ![[HOT_ID]] = !{!"function_section_prefix", !".hot"}
 ; CHECK: ![[COLD_ID]] = !{!"function_section_prefix", !".unlikely"}
 !llvm.module.flags = !{!1}
 !1 = !{i32 1, !"ProfileSummary", !2}
 !2 = !{!3, !4, !5, !6, !7, !8, !9, !10}
 !3 = !{!"ProfileFormat", !"InstrProf"}
 !4 = !{!"TotalCount", i64 10000}
 !5 = !{!"MaxCount", i64 1000}
 !6 = !{!"MaxInternalCount", i64 1}
 !7 = !{!"MaxFunctionCount", i64 1000}
 !8 = !{!"NumCounts", i64 3}
 !9 = !{!"NumFunctions", i64 3}
 !10 = !{!"DetailedSummary", !11}
 !11 = !{!12, !13, !14}
 !12 = !{i32 10000, i64 100, i32 1}
 !13 = !{i32 999000, i64 100, i32 1}
 !14 = !{i32 999999, i64 1, i32 2}
 !15 = !{!"function_entry_count", i64 1000}
 !16 = !{!"function_entry_count", i64 1}
 !17 = !{!"branch_weights", i32 80}
 !18 = !{!"branch_weights", i32 1}
+!19 = !{!"branch_weights", i32 1000, i32 1}