Add prefix based function layout when profile is available.

[danielcdh]

Summary

If a function is hot, put it in text.hot section.

[davidxl]

lib/CodeGen/TargetLoweringObjectFileImpl.cpp

303

1. please introduce placeholder query APIs in include/llvm/ProfileData/ProfileCommon.h for this purpose (can be a static method of ProfileSummary class:
   
   bool ProfileSummary::isFunctionHot(Function *); bool ProfileSummary::isFunctionUnlikely(Function *)

2. using the existence of entry profile count as the criteria is wrong -- the entry count can be 0 or a very low value. The right tuning will need to look at the max Block count of the function and program summary -- so I think we need to leave that part out and wait for Easwaran's tuning work is in

3. Before the summary based work is in, for now, implement a simpler heuristic similar to what is used in the current inliner:
   
   a) check attribute 'hot' of the function (in practice, this may not work well -- after ininling, the out of line copy of the original hot function may become cold) b) check attribute 'cold' for the function -- this is more reliable c) if the function's has zero bb count/sample, mark it as cold (Inliner's herustics is 0.01* maxFunctionCount) -- but I think we can be more conservative here by checking zero count ones)

In short, the initial heuristic should be conservative in the sense we only filter out those we are really confident with -- mainly cold ones never executed which can go a long way.

4. Define two helper functions to return .hot and .unlikely suffixes instead of using hard coded strings here.

5. We can also introduce an internal option to turn this layout optimization on |off. By default it can be off. When it is off, the query functions above will simply return 'false'.

[danielcdh]

Integrate David's comments.

[davidxl]

include/llvm/ProfileData/ProfileCommon.h

73

Document this method -- what does it do?

lib/CodeGen/TargetLoweringObjectFileImpl.cpp

248

Move these two functions into ProfileSummary.h (as a standalone function in llvm:: namespace)

252

Better name it as: GroupFunctionsByHotness

255

I think the initial value should be false. To turn it on by default, more data is needed (and announced more widely).

lib/ProfileData/ProfileSummary.cpp

82

use FIXME

88

FIXME

99

FIXME

[danielcdh]

Integrate comments.

[danielcdh]

done

[davidxl]

lib/ProfileData/ProfileSummary.cpp

81

If this takes Function * as an argument, it can be a wrapper of getEntryCount call

92

I suggest changing this interface's name to be 'isFunctionRarelyCalled'. It is different from 'isFunctionCold' which should be checking the internal block count. These two interfaces are for different purposes. The later can be used to guide decisions such as optimize for size etc, while the former can be used for layout decision to reduce itlb misses.

Similarly, isFunctionHot does not mean it is frequently called either -- so the interface need to be split up too.

96

the check of hasProfile is probably redundant.

[eraman]

include/llvm/ProfileData/ProfileCommon.h

33

These two functions should be elsewhere. Perhaps in TargetLowering ?

lib/ProfileData/ProfileSummary.cpp

92

This and isFunctionHot should be made as a member functions of Function.

96

I think what David says is true (!F->genEntryCount() implies !hasProfile()).

[davidxl]

include/llvm/ProfileData/ProfileCommon.h

33

I think it is fine to be here -- it is generic enough and it is profile related.

lib/ProfileData/ProfileSummary.cpp

92

I think it is better to keep all/most of the profile related query APIs here in this file.

[eraman]

include/llvm/ProfileData/ProfileCommon.h

33

The strings themselves are not profile related. One might want to use .unlikely for error handling routines even without profile data.

lib/ProfileData/ProfileSummary.cpp

92

Again, the function itself is not fully profile dependent. I think ProfileCommon should only have APIs like isCountConsideredHot(uint64_t Count).

[davidxl]

include/llvm/ProfileData/ProfileCommon.h

33

Aren't those also related to profile too (it is profile that can be determined statically)?

lib/ProfileData/ProfileSummary.cpp

92

You have a point about Function being not profile dependent, but I think we should not restrict the scope of ProfileCommon.h too much like this. It is reasonable for ProfileCommon to reference IR related headers.

[danielcdh]

update

lib/ProfileData/ProfileSummary.cpp

81

!getEntryCount() does not mean no profile for the binary, but no profile for the function. We need to have this function to indicate if this is an FDO/AFDO build.

92

After a second thought, I think it still makes sense to group "hot" functions together instead of "frequently called" This is because the hot path of an "infrequently called" hot function may have many calls to a frequently called function. So if these two functions are far apart, it will waste an ITLB entry. Additionally, this will pollute the heat map and makes performance tuning more difficult.

96

I've updated the logic, PTAL.

[davidxl]

include/llvm/ProfileData/ProfileCommon.h

74

If it is used to indicate profile availability at program level, it should take Module as argument.

lib/ProfileData/ProfileSummary.cpp

100

Should return false -- as we don't know (no profile data)

103

This will work well for instr profile but may produce false positive for sampleFDO -- this will be fixed when summary based computation is used.

[danielcdh]

lib/ProfileData/ProfileSummary.cpp

100

For AutoFDO, F->setEntryCount() is only called when there is sample in that function. So for those 0-sampled functions, F->getEntryCount() will be false.

103

Yes, but we can always set entry-count as no less than 1 if the function has profile. Otherwise we have no way to calculate bb counts.

[danielcdh]

update

[davidxl]

Looks good in general.

1. Need a test case covering both regular case and -ffunction-sections (-function-sections for llc)

2. Need a follow up discussion to introduce user level option -freorder-function (and turn on by default with profile) in LLVM. Also talk to other maintainers of other main platforms (MachO, etc) to add this support there.

[eraman]

lib/ProfileData/ProfileSummary.cpp

83

return M->getMaximumFunctionCount().hasValue();

I know this doesn't work for sample profile, but it works for instrumentation profile and is better than returning false.

100

I think sample profile loader pass should set 0 to the entry count. The meaning of getEntryCount() should not be dependent on the profile format that is used. (To be clear, I am not saying that should be fixed as part of this patch)

[danielcdh]

add test and remove hasProfile.

[danielcdh]

added the unittest. also removed hasProfile to use getEntryCount()'s boolean value to check. I will have a follow-up patch to make getEntryCount() behavior consistent between sample profile and instr profile.

[davidxl]

test/CodeGen/X86/partition-sections.ll

1

Can you also add a test without -function-sections option.

[danielcdh]

add more test

[davidxl]

LGTM.

To repeat the follow ups needed:

1. tuning, performance number and turning on by default for PGO
2. support for other platforms (and consider user options if applicable).

[deadalnix]

This is broken on OSX.

[davidxl]

The test case misses mtriple option.

Dehao, we should not leave buildbot failing for long period of time.
The buildbot message should arrive at your inbox very shortly after
the commit -- can you check if there is any issue there (e.g. in spam
filter)?

thanks,

David

include/llvm/ProfileData/ProfileCommon.h

 #include <functional>
 #include <map>
 #include <vector>
 
 #ifndef LLVM_PROFILEDATA_PROFILE_COMMON_H
 #define LLVM_PROFILEDATA_PROFILE_COMMON_H
 
 namespace llvm {
+class Function;
+class Module;
 namespace IndexedInstrProf {
 struct Summary;
 }
 namespace sampleprof {
 class FunctionSamples;
 }
 struct InstrProfRecord;
+inline const char *getHotSectionPrefix() { return ".hot"; }
+inline const char *getUnlikelySectionPrefix() { return ".unlikely"; }
 // The profile summary is one or more (Cutoff, MinCount, NumCounts) triplets.
 // The semantics of counts depend on the type of profile. For instrumentation
 // profile, counts are block counts and for sample profile, counts are
 // per-line samples. Given a target counts percentile, we compute the minimum
 // number of counts needed to reach this target and the minimum among these
 // counts.
 struct ProfileSummaryEntry {
   uint32_t Cutoff;    ///< The required percentile of counts.
protected:
   ProfileSummary(std::vector<ProfileSummaryEntry> DetailedSummary,
                  uint64_t TotalCount, uint64_t MaxCount, uint32_t NumCounts)
       : DetailedSummary(DetailedSummary), TotalCount(TotalCount),
         MaxCount(MaxCount), NumCounts(NumCounts) {}
   inline void addCount(uint64_t Count);
 
 public:
   static const int Scale = 1000000;
+  // \brief Returns true if F is a hot function.
+  static bool isFunctionHot(const Function *F);
+  // \brief Returns true if F is unlikley executed.
+  static bool isFunctionUnlikely(const Function *F);
   inline std::vector<ProfileSummaryEntry> &getDetailedSummary();
   void computeDetailedSummary();
   /// \brief A vector of useful cutoff values for detailed summary.
   static const std::vector<uint32_t> DefaultCutoffs;
 };
 
 class InstrProfSummary : public ProfileSummary {
   uint64_t MaxInternalBlockCount, MaxFunctionCount;

lib/CodeGen/TargetLoweringObjectFileImpl.cpp

 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCSectionCOFF.h"
 #include "llvm/MC/MCSectionELF.h"
 #include "llvm/MC/MCSectionMachO.h"
 #include "llvm/MC/MCStreamer.h"
 #include "llvm/MC/MCSymbolELF.h"
 #include "llvm/MC/MCValue.h"
 #include "llvm/ProfileData/InstrProf.h"
+#include "llvm/ProfileData/ProfileCommon.h"
 #include "llvm/Support/COFF.h"
 #include "llvm/Support/Dwarf.h"
 #include "llvm/Support/ELF.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
static StringRef getSectionPrefixForGlobal(SectionKind Kind) {
   if (Kind.isThreadBSS())
     return ".tbss";
   if (Kind.isData())
     return ".data";
   assert(Kind.isReadOnlyWithRel() && "Unknown section kind");
   return ".data.rel.ro";
 }
 
+static cl::opt<bool> GroupFunctionsByHotness(
+    "group-functions-by-hotness",
+    llvm::cl::desc("Partition hot/cold functions by sections prefix"),
+    cl::init(false));
+
 static MCSectionELF *
 selectELFSectionForGlobal(MCContext &Ctx, const GlobalValue *GV,
                           SectionKind Kind, Mangler &Mang,
                           const TargetMachine &TM, bool EmitUniqueSection,
                           unsigned Flags, unsigned *NextUniqueID) {
   unsigned EntrySize = 0;
   if (Kind.isMergeableCString()) {
     if (Kind.isMergeable2ByteCString()) {
       EntrySize = 2;
     } else if (Kind.isMergeable4ByteCString()) {
       EntrySize = 4;
if (Kind.isMergeableCString()) {
     Name = SizeSpec + utostr(Align);
   } else if (Kind.isMergeableConst()) {
     Name = ".rodata.cst";
     Name += utostr(EntrySize);
   } else {
     Name = getSectionPrefixForGlobal(Kind);
   }
 
+  if (GroupFunctionsByHotness) {
+    if (const Function *F = dyn_cast<Function>(GV)) {
+      if (ProfileSummary::isFunctionHot(F)) {
+        Name += getHotSectionPrefix();
+      } else if (ProfileSummary::isFunctionUnlikely(F)) {
+        Name += getUnlikelySectionPrefix();
+      }
+    }
+  }
+
   if (EmitUniqueSection && UniqueSectionNames) {
     Name.push_back('.');
     TM.getNameWithPrefix(Name, GV, Mang, true);
   }
   unsigned UniqueID = ~0;
   if (EmitUniqueSection && !UniqueSectionNames) {
     UniqueID = *NextUniqueID;
     (*NextUniqueID)++;

lib/ProfileData/ProfileSummary.cpp

 //=-- Profilesummary.cpp - Profile summary computation ----------------------=//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains support for computing profile summary data.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/ProfileData/ProfileCommon.h"
 #include "llvm/ProfileData/SampleProf.h"
 
 using namespace llvm;
 
 // A set of cutoff values. Each value, when divided by ProfileSummary::Scale
 // (which is 1000000) is a desired percentile of total counts.
while (CurrSum < DesiredCount && Iter != End) {
       Iter++;
     }
     assert(CurrSum >= DesiredCount);
     ProfileSummaryEntry PSE = {Cutoff, Count, CountsSeen};
     DetailedSummary.push_back(PSE);
   }
 }
 
+// Returns true if the function is a hot function.
+bool ProfileSummary::isFunctionHot(const Function *F) {
+  // FIXME: update when summary data is stored in module's metadata.
+  return false;
+}
+
+// Returns true if the function is a cold function.
+bool ProfileSummary::isFunctionUnlikely(const Function *F) {
+  if (F->hasFnAttribute(Attribute::Cold)) {
+    return true;
+  }
+  if (!F->getEntryCount()) {
+    return false;
+  }
+  // FIXME: update when summary data is stored in module's metadata.
+  return (*F->getEntryCount()) == 0;
+}
+
 InstrProfSummary::InstrProfSummary(const IndexedInstrProf::Summary &S)
     : ProfileSummary(), MaxInternalBlockCount(S.get(
                             IndexedInstrProf::Summary::MaxInternalBlockCount)),
       MaxFunctionCount(S.get(IndexedInstrProf::Summary::MaxFunctionCount)),
       NumFunctions(S.get(IndexedInstrProf::Summary::TotalNumFunctions)) {
 
   TotalCount = S.get(IndexedInstrProf::Summary::TotalBlockCount);
   MaxCount = S.get(IndexedInstrProf::Summary::MaxBlockCount);
   NumCounts = S.get(IndexedInstrProf::Summary::TotalNumBlocks);
 
   for (unsigned I = 0; I < S.NumCutoffEntries; I++) {
     const IndexedInstrProf::Summary::Entry &Ent = S.getEntry(I);
     DetailedSummary.emplace_back((uint32_t)Ent.Cutoff, Ent.MinBlockCount,

test/CodeGen/X86/partition-sections.ll

+; RUN: llc < %s -function-sections -group-functions-by-hotness=false | FileCheck %s -check-prefix=NO-PARTITION
+; RUN: llc < %s -function-sections -group-functions-by-hotness=true | FileCheck %s -check-prefix=PARTITION
+
+; NO-PARTITION: .text._Z3foov
+; PARTITION: .text.unlikely._Z3foov
+; Function Attrs: nounwind uwtable
+define i32 @_Z3foov() #0 {
+  ret i32 0
+}
+
+; NO-PARTITION: .text._Z3barv
+; PARTITION: .text.unlikely._Z3barv
+; Function Attrs: nounwind uwtable
+define i32 @_Z3barv() #1 !prof !0 {
+  ret i32 1
+}
+
+; NO-PARTITION: .text._Z3bazv
+; PARTITION: .text._Z3bazv
+; Function Attrs: nounwind uwtable
+define i32 @_Z3bazv() #1 {
+  ret i32 2
+}
+
+attributes #0 = { nounwind uwtable cold }
+attributes #1 = { nounwind uwtable }
+
+!0 = !{!"function_entry_count", i64 0}