[AutoFDO][llvm-profgen] Report zero count for unexecuted part of function code

[wlei]

Summary

In order to be consistent with compiler that interprets zero count as unexecuted(cold), this change reports zero-value count for unexecuted part of function code. For the implementation, it leverages the range counter, initializes all the executed function range with the zero-value. After all ranges are merged and converted into disjoint ranges, the remaining zero count will indicates the unexecuted(cold) part of the function.

This change also extends the current findDisjointRanges method which now can support adding zero-value range.

[wlei]

fix one return type error

[hoy]

Thanks for the change. I'm wondering instead of extending findDisjointRanges if we can just add a post-processing pass that adds a zero sample to all line offsets. We did this for probe-based CS profile.

[wlei]

In D109713#3000685, @hoy wrote:

Thanks for the change. I'm wondering instead of extending findDisjointRanges if we can just add a post-processing pass that adds a zero sample to all line offsets. We did this for probe-based CS profile.

The advantage to do it by extending findDisjointRanges is it can save some operations and adding zero sample for line-number is heavier than probe because it need to travels the inline callstack.

For extreme case say if we have counter like [1,9999] : 1. and the function range is [1,10000], post-processing will do both for [1,9999] : 1, [1,10000]: 0 . it's almost double the cost. pre-processing will do [1,9999] : 1 and [10000,10000]:0.

[hoy]

In D109713#3000717, @wlei wrote:

In D109713#3000685, @hoy wrote:

Thanks for the change. I'm wondering instead of extending findDisjointRanges if we can just add a post-processing pass that adds a zero sample to all line offsets. We did this for probe-based CS profile.

The advantage to do it by extending findDisjointRanges is it can save some operations and adding zero sample for line-number is heavier than probe because it need to travels the inline callstack.

For extreme case say if we have counter like [1,9999] : 1. and the function range is [1,10000], post-processing will do both for [1,9999] : 1, [1,10000]: 0 . it's almost double the cost. pre-processing will do [1,9999] : 1 and [10000,10000]:0.

Sounds good. Leveraging the range calculator to avoid redundant scanning is smart.

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

141–142

Add a comment for this? Does it stand for a point that only have a zero count?

208–209

This initialization is probably not needed since you are adding the default constructor.

226

Should this always be true? addBeginCount is called every time a new boundary point is created?

295

Can you remind me of what could lead to a zero count previously? I'm wondering if that kind of zero count should be reported.

325

nit: preProcess -> preprocess

llvm/tools/llvm-profgen/ProfiledBinary.cpp

400–401

Does the initializer list require c++14? emplace_back should work if you see a warning for that.

llvm/tools/llvm-profgen/ProfiledBinary.h

167–169

Nit: rename FuncStartAddrMap to FuncStartOffsetMap?

Please adjust comment to include end offset.

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

226

nvm, I get that.

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

242

Add a comment for this? Suppose we never have a zero-count range, does this change the default behavior?

[wlei]

Addressing Hongtao's feedback.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

141–142

Comments added, not a zero count only, it's also used for the overlapping point. like

[----10 ----]
[--------- 0 ----------]
A            B         C

Point A's count is 10 and the isZeroRangeBegin is true.

208–209

Sounds good, refactor the code to use emplace

242

Comment added. It will change our previous logic a little bit, i, e. previous one can generate new zero-count range.
For example, supposing we have two non-overlapping ranges

[<---- 10 ---->]  
                            [<----20 ----->]
A              B             C             D

Previously, it will add a zero range [B+1, C-1]. (Anyway, this extra zero range will be filtered later as you can see the code below).

After this change, the begin point B+1 is marked invalid(UINT64_MAX), so no extra zero range is added.

295

See the above comment. that's from the gap between two non-overlapping ranges.

325

Fixed!

llvm/tools/llvm-profgen/ProfiledBinary.cpp

400–401

The value here is a std::pair, I guess you mean emplace?

llvm/tools/llvm-profgen/ProfiledBinary.h

167–169

Good catch!

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

208–209

I actually meant you can just do something like below. Sorry for the confusion.

Boundaries[Begin].addBeginCount(Count);
Boundaries[End].addEndCount(Count);
if (Count == 0) {
  BeginPoint.IsZeroRangeBegin = true;
  EndPoint.IsZeroRangeEnd = true;
}

242

Thanks for the explanation. It makes sense to me now. Would be great to include your example in the comment.

[wlei]

addressing Hongtao's feedback.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

208–209

I see, that's clearer. Thanks!

242

example added!

[hoy]

lgtm, thanks.

[wenlei]

lgtm, thanks.

For the implementation, it leverages the range counter, initializes all the executed function range with the zero-value.

This should be quite efficient.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

148

curious why we need this?

221

Since we only add zero ranges for functions, there won't be any overlapping zero range and the Depth is going to be either 0 or 1, right?

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

148

uh, I just wrote it unintentionally, it can be removed.

221

Yes, in our case, function range apparently won't overlap and also there is no zero count in the sample.

[wlei]

rebase

llvm/test/tools/llvm-profgen/inline-noprobe.test

 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/inline-noprobe.perfscript --binary=%S/Inputs/inline-noprobe.perfbin --output=%t --skip-symbolization
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK-RAW-PROFILE
 ; RUN: llvm-profgen --format=text --perfscript=%S/Inputs/inline-noprobe.perfscript --binary=%S/Inputs/inline-noprobe.perfbin --output=%t
 ; RUN: FileCheck %s --input-file %t --check-prefix=CHECK
 
 CHECK: main:836:0
+CHECK:  0: 0
+CHECK:  2: 0
 CHECK:  1: foo:836
 CHECK:   2.1: 42
 CHECK:   3: 62
 CHECK:   3.2: 21
+CHECK:   4: 0
 CHECK:   3.1: bar:252
 CHECK:    1: 42
 CHECK:   3.2: bar:63
 CHECK:    1: 21
 
 CHECK-RAW-PROFILE:      3
 CHECK-RAW-PROFILE-NEXT: 650-691:21
 CHECK-RAW-PROFILE-NEXT: 669-677:20

llvm/test/tools/llvm-profgen/inline-noprobe2.test

 ;CHECK-NEXT:   1: 9
 ;CHECK-NEXT:   2: 9
 ;CHECK-NEXT:   3: 9
 ;CHECK-NEXT:  6: swap:20
 ;CHECK-NEXT:   1: 5
 ;CHECK-NEXT:   2: 5
 ;CHECK-NEXT:   3: 5
 ;CHECK-NEXT: main:213:0
+;CHECK-NEXT:  0: 0
+;CHECK-NEXT:  3: 0
+;CHECK-NEXT:  4.1: 0
+;CHECK-NEXT:  4.3: 0
 ;CHECK-NEXT:  5.1: 10
 ;CHECK-NEXT:  5.3: 10
 ;CHECK-NEXT:  6: 10
 ;CHECK-NEXT:  6.1: 12
 ;CHECK-NEXT:  6.3: 10
+;CHECK-NEXT:  7: 0
 ;CHECK-NEXT:  8: 0 quick_sort:1
+;CHECK-NEXT:  9: 0
+;CHECK-NEXT:  11: 0
+;CHECK-NEXT:  14: 0
 
 ; original code:
 ; clang -O3 -g -fno-optimize-sibling-calls -fdebug-info-for-profiling qsort.c -o a.out
 #include <stdio.h>
 #include <stdlib.h>
 
 void swap(int *a, int *b) {
   int t = *a;

llvm/tools/llvm-profgen/ProfileGenerator.h

 public:
   ProfileGenerator(ProfiledBinary *Binary,
                    const ContextSampleCounterMap &Counters)
       : ProfileGeneratorBase(Binary, Counters){};
   void generateProfile() override;
 
 private:
   void generateLineNumBasedProfile();
+  RangeSample preprocessRangeCounter(const RangeSample &RangeCounter);
   FunctionSamples &getTopLevelFunctionProfile(StringRef FuncName);
   // Helper function to get the leaf frame's FunctionProfile by traversing the
   // inline stack and meanwhile it adds the total samples for each frame's
   // function profile.
   FunctionSamples &
   getLeafProfileAndAddTotalSamples(const SampleContextFrameVector &FrameVec,
                                    uint64_t Count);
   void populateBodySamplesForAllFunctions(const RangeSample &RangeCounter);

llvm/tools/llvm-profgen/ProfileGenerator.cpp

void ProfileGeneratorBase::findDisjointRanges(RangeSample &DisjointRanges,
   samples ends at A, so EndCount is 0.
   Then boundary points A, B, and C with begin/end counts are:
   A: (300, 0)
   B: (0, 100)
   C: (0, 200)
   */
   struct BoundaryPoint {
     // Sum of sample counts beginning at this point
-    uint64_t BeginCount;
+    uint64_t BeginCount = UINT64_MAX;
     // Sum of sample counts ending at this point
-    uint64_t EndCount;
-
-    BoundaryPoint() : BeginCount(0), EndCount(0){};
-
-    void addBeginCount(uint64_t Count) { BeginCount += Count; }
-
-    void addEndCount(uint64_t Count) { EndCount += Count; }
+    uint64_t EndCount = UINT64_MAX;
+    // Is the begin point of a zero range.
+    bool IsZeroRangeBegin = false;
+    // Is the end point of a zero range.
+    bool IsZeroRangeEnd = false;
+
+    void addBeginCount(uint64_t Count) {
+      if (BeginCount == UINT64_MAX)
+        BeginCount = 0;
+      BeginCount += Count;
+    }
+
+    void addEndCount(uint64_t Count) {
+      if (EndCount == UINT64_MAX)
+        EndCount = 0;
+      EndCount += Count;
+    }
   };
 
   /*
   For the above example. With boundary points, follwing logic finds two
   disjoint region of
 
   [A,B]:   300
   [B+1,C]: 200
void ProfileGeneratorBase::findDisjointRanges(RangeSample &DisjointRanges,
   B: (200, 100)
   C: (0, 200)
 
   the disjoint ranges would be
 
   [A, B-1]: 100
   [B, B]:   300
   [B+1, C]: 200.
+
+  Example for zero value range:
+
+    |<--- 100 --->|
+                       |<--- 200 --->|
+  |<---------------  0 ----------------->|
+  A  B            C    D             E   F
+
+  [A, B-1]  : 0
+  [B, C]    : 100
+  [C+1, D-1]: 0
+  [D, E]    : 200
+  [E+1, F]  : 0
   */
   std::map<uint64_t, BoundaryPoint> Boundaries;
 
   for (auto Item : Ranges) {
-    uint64_t Begin = Item.first.first;
-    uint64_t End = Item.first.second;
-    assert(Begin <= End && "Invalid instruction range");
+    assert(Item.first.first <= Item.first.second &&
+           "Invalid instruction range");
+    auto &BeginPoint = Boundaries[Item.first.first];
+    auto &EndPoint = Boundaries[Item.first.second];
     uint64_t Count = Item.second;
-    if (Boundaries.find(Begin) == Boundaries.end())
-      Boundaries[Begin] = BoundaryPoint();
-    Boundaries[Begin].addBeginCount(Count);
-
-    if (Boundaries.find(End) == Boundaries.end())
-      Boundaries[End] = BoundaryPoint();
-    Boundaries[End].addEndCount(Count);
+
+    BeginPoint.addBeginCount(Count);
+    EndPoint.addEndCount(Count);
+    if (Count == 0) {
+      BeginPoint.IsZeroRangeBegin = true;
+      EndPoint.IsZeroRangeEnd = true;
+    }
   }
 
+  // Use UINT64_MAX to indicate there is no existing range between BeginAddress
+  // and the next valid address
   uint64_t BeginAddress = UINT64_MAX;
+  int ZeroRangeDepth = 0;
   uint64_t Count = 0;
   for (auto Item : Boundaries) {
     uint64_t Address = Item.first;
     BoundaryPoint &Point = Item.second;
-    if (Point.BeginCount) {
+    if (Point.BeginCount != UINT64_MAX) {
       if (BeginAddress != UINT64_MAX)
         DisjointRanges[{BeginAddress, Address - 1}] = Count;
       Count += Point.BeginCount;
       BeginAddress = Address;
+      ZeroRangeDepth += Point.IsZeroRangeBegin;
     }
-    if (Point.EndCount) {
+    if (Point.EndCount != UINT64_MAX) {
       assert((BeginAddress != UINT64_MAX) &&
              "First boundary point cannot be 'end' point");
       DisjointRanges[{BeginAddress, Address}] = Count;
       assert(Count >= Point.EndCount && "Mismatched live ranges");
       Count -= Point.EndCount;
       BeginAddress = Address + 1;
+      ZeroRangeDepth -= Point.IsZeroRangeEnd;
+      // If the remaining count is zero and it's no longer in a zero range, this
+      // means we consume all the ranges before, thus mark BeginAddress as
+      // UINT64_MAX. e.g. supposing we have two non-overlapping ranges:
+      //  [<---- 10 ---->]
+      //                       [<---- 20 ---->]
+      //   A             B     C              D
+      // The BeginAddress(B+1) will reset to invalid(UINT64_MAX), so we won't
+      // have the [B+1, C-1] zero range.
+      if (Count == 0 && ZeroRangeDepth == 0)
+        BeginAddress = UINT64_MAX;
     }
   }
 }
 
 void ProfileGeneratorBase::updateBodySamplesforFunctionProfile(
     FunctionSamples &FunctionProfile, const SampleContextFrame &LeafLoc,
     uint64_t Count) {
   // Filter out invalid negative(int type) lineOffset
   if (LeafLoc.Callsite.LineOffset & 0x80000000)
     return;
   // Use the maximum count of samples with same line location
   ErrorOr<uint64_t> R = FunctionProfile.findSamplesAt(
       LeafLoc.Callsite.LineOffset, LeafLoc.Callsite.Discriminator);
   uint64_t PreviousCount = R ? R.get() : 0;
-  if (PreviousCount < Count) {
+  if (PreviousCount <= Count) {
     FunctionProfile.addBodySamples(LeafLoc.Callsite.LineOffset,
                                    LeafLoc.Callsite.Discriminator,
                                    Count - PreviousCount);
   }
 }
 
 FunctionSamples &
 ProfileGenerator::getTopLevelFunctionProfile(StringRef FuncName) {
for (size_t I = 1; I < FrameVec.size(); I++) {
     }
     FunctionProfile = &Ret.first->second;
     FunctionProfile->addTotalSamples(Count);
   }
 
   return *FunctionProfile;
 }
 
+RangeSample
+ProfileGenerator::preprocessRangeCounter(const RangeSample &RangeCounter) {
+  RangeSample Ranges(RangeCounter.begin(), RangeCounter.end());
+  // For each range, we search for the range of the function it belongs to and
+  // initialize it with zero count, so it remains zero if doesn't hit any
+  // samples. This is to be consistent with compiler that interpret zero count
+  // as unexecuted(cold).
+  for (auto I : RangeCounter) {
+    uint64_t RangeBegin = I.first.first;
+    uint64_t RangeEnd = I.first.second;
+    // Find the function offset range the current range begin belongs to.
+    auto FuncRange = Binary->findFuncOffsetRange(RangeBegin);
+    if (FuncRange.second == 0)
+      WithColor::warning()
+          << "[" << format("%8" PRIx64, RangeBegin) << " - "
+          << format("%8" PRIx64, RangeEnd)
+          << "]: Invalid range or disassembling error in profiled binary.\n";
+    else if (RangeEnd > FuncRange.second)
+      WithColor::warning() << "[" << format("%8" PRIx64, RangeBegin) << " - "
+                           << format("%8" PRIx64, RangeEnd)
+                           << "]: Range is across different functions.\n";
+    else
+      Ranges[FuncRange] += 0;
+  }
+  RangeSample DisjointRanges;
+  findDisjointRanges(DisjointRanges, Ranges);
+  return DisjointRanges;
+}
+
 void ProfileGenerator::populateBodySamplesForAllFunctions(
     const RangeSample &RangeCounter) {
-  RangeSample Ranges;
-  findDisjointRanges(Ranges, RangeCounter);
-  for (auto Range : Ranges) {
+  for (auto Range : preprocessRangeCounter(RangeCounter)) {
     uint64_t RangeBegin = Binary->offsetToVirtualAddr(Range.first.first);
     uint64_t RangeEnd = Binary->offsetToVirtualAddr(Range.first.second);
     uint64_t Count = Range.second;
-    // Disjoint ranges have introduce zero-filled gap that
-    // doesn't belong to current context, filter them out.
-    if (Count == 0)
-      continue;
 
     InstructionPointer IP(Binary, RangeBegin, true);
     // Disjoint ranges may have range in the middle of two instr,
     // e.g. If Instr1 at Addr1, and Instr2 at Addr2, disjoint range
     // can be Addr1+1 to Addr2-1. We should ignore such range.
     while (IP.Address <= RangeEnd) {
       uint64_t Offset = Binary->virtualAddrToOffset(IP.Address);
       const SampleContextFrameVector &FrameVec =

llvm/tools/llvm-profgen/ProfiledBinary.h

 #include "llvm/MC/MCSubtargetInfo.h"
 #include "llvm/MC/MCTargetOptions.h"
 #include "llvm/Object/ELFObjectFile.h"
 #include "llvm/ProfileData/SampleProf.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Transforms/IPO/SampleContextTracker.h"
 #include <list>
+#include <map>
 #include <set>
 #include <sstream>
 #include <string>
 #include <unordered_map>
 #include <unordered_set>
 #include <vector>
 
 extern cl::opt<bool> EnableCSPreInliner;

 // we will switch to Dwarf CFI based tracker
 struct PrologEpilogTracker {
   // A set of prolog and epilog offsets. Used by virtual unwinding.
   std::unordered_set<uint64_t> PrologEpilogSet;
   ProfiledBinary *Binary;
   PrologEpilogTracker(ProfiledBinary *Bin) : Binary(Bin){};
 
   // Take the two addresses from the start of function as prolog
-  void inferPrologOffsets(
-      std::unordered_map<uint64_t, std::string> &FuncStartAddrMap) {
-    for (auto I : FuncStartAddrMap) {
+  void inferPrologOffsets(std::map<uint64_t, std::pair<std::string, uint64_t>>
+                              &FuncStartOffsetMap) {
+    for (auto I : FuncStartOffsetMap) {
       PrologEpilogSet.insert(I.first);
       InstructionPointer IP(Binary, I.first);
       IP.advance();
       PrologEpilogSet.insert(IP.Offset);
     }
   }
 
   // Take the last two addresses before the return address as epilog
private:
   // Root node for context trie tree, node that this is a reverse context trie
   // with callee as parent and caller as child. This way we can traverse from
   // root to find the best/longest matching context if an exact match does not
   // exist. It gives us the best possible estimate for function's post-inline,
   // post-optimization byte size.
   ContextTrieNode RootContext;
 };
 
+using OffsetRange = std::pair<uint64_t, uint64_t>;
+
 class ProfiledBinary {
   // Absolute path of the binary.
   std::string Path;
   // The target triple.
   Triple TheTriple;
   // The runtime base address that the first executable segment is loaded at.
   uint64_t BaseAddress = 0;
   // The preferred load address of each executable segment.
   std::vector<uint64_t> PreferredTextSegmentAddresses;
   // The file offset of each executable segment.
   std::vector<uint64_t> TextSegmentOffsets;
 
   // Mutiple MC component info
   std::unique_ptr<const MCRegisterInfo> MRI;
   std::unique_ptr<const MCAsmInfo> AsmInfo;
   std::unique_ptr<const MCSubtargetInfo> STI;
   std::unique_ptr<const MCInstrInfo> MII;
   std::unique_ptr<MCDisassembler> DisAsm;
   std::unique_ptr<const MCInstrAnalysis> MIA;
   std::unique_ptr<MCInstPrinter> IPrinter;
   // A list of text sections sorted by start RVA and size. Used to check
   // if a given RVA is a valid code address.
   std::set<std::pair<uint64_t, uint64_t>> TextSections;
-  // Function offset to name mapping.
-  std::unordered_map<uint64_t, std::string> FuncStartAddrMap;
+  // An ordered map of mapping function's start offset to its name and
+  // end offset.
+  std::map<uint64_t, std::pair<std::string, uint64_t>> FuncStartOffsetMap;
   // Offset to context location map. Used to expand the context.
   std::unordered_map<uint64_t, SampleContextFrameVector> Offset2LocStackMap;
   // An array of offsets of all instructions sorted in increasing order. The
   // sorting is needed to fast advance to the next forward/backward instruction.
   std::vector<uint64_t> CodeAddrs;
   // A set of call instruction offsets. Used by virtual unwinding.
   std::unordered_set<uint64_t> CallAddrs;
   // A set of return instruction offsets. Used by virtual unwinding.
uint64_t getCallAddrFromFrameAddr(uint64_t FrameAddr) const {
     auto I = getIndexForAddr(FrameAddr);
     FrameAddr = I ? getAddressforIndex(I - 1) : 0;
     if (FrameAddr && addressIsCall(FrameAddr))
       return FrameAddr;
     return 0;
   }
 
   StringRef getFuncFromStartOffset(uint64_t Offset) {
-    auto I = FuncStartAddrMap.find(Offset);
-    if (I == FuncStartAddrMap.end())
+    auto I = FuncStartOffsetMap.find(Offset);
+    if (I == FuncStartOffsetMap.end())
       return StringRef();
-    return I->second;
+    return I->second.first;
+  }
+
+  OffsetRange findFuncOffsetRange(uint64_t Offset) {
+    auto I = FuncStartOffsetMap.upper_bound(Offset);
+    if (I == FuncStartOffsetMap.begin())
+      return {0, 0};
+    I--;
+    return {I->first, I->second.second};
   }
 
   uint32_t getFuncSizeForContext(SampleContext &Context) {
     return FuncSizeTracker.getFuncSizeForContext(Context);
   }
 
   const SampleContextFrameVector &getFrameLocationStack(uint64_t Offset) const {
     auto I = Offset2LocStackMap.find(Offset);

llvm/tools/llvm-profgen/ProfiledBinary.cpp

void ProfiledBinary::load() {
   // Disassemble the text sections.
   disassemble(Obj);
 
   // Track size for optimized inlinees when probe is available
   if (UsePseudoProbes && TrackFuncContextSize)
     FuncSizeTracker.trackInlineesOptimizedAway(ProbeDecoder);
 
   // Use function start and return address to infer prolog and epilog
-  ProEpilogTracker.inferPrologOffsets(FuncStartAddrMap);
+  ProEpilogTracker.inferPrologOffsets(FuncStartOffsetMap);
   ProEpilogTracker.inferEpilogOffsets(RetAddrs);
 
   // TODO: decode other sections.
 }
 
 bool ProfiledBinary::inlineContextEqual(uint64_t Address1,
                                         uint64_t Address2) const {
   uint64_t Offset1 = virtualAddrToOffset(Address1);
bool ProfiledBinary::dissassembleSymbol(std::size_t SI, ArrayRef<uint8_t> Bytes,
   }
 
   if (InvalidInstLength)
     WarnInvalidInsts(Offset - InvalidInstLength, Offset - 1);
 
   if (ShowDisassembly)
     outs() << "\n";
 
-  FuncStartAddrMap[StartOffset] = Symbols[SI].Name.str();
+  FuncStartOffsetMap.emplace(StartOffset,
+                             std::make_pair(Symbols[SI].Name.str(), EndOffset));
   return true;
 }
 
 void ProfiledBinary::setUpDisassembler(const ELFObjectFileBase *Obj) {
   const Target *TheTarget = getTarget(Obj);
   std::string TripleName = TheTriple.getTriple();
   StringRef FileName = Obj->getFileName();