[llvm-profgen] Add duplication factor for line-number based profile

[wlei]

Summary

This change adds duplication factor multiplier while accumulating body samples for line-number based profile. The body sample count will be duplication-factor * count. Base discriminator and duplication factor is decoded from the raw discriminator, this requires some refactor works.

[wenlei]

llvm/test/tools/llvm-profgen/duplication-factor.test

6 ↗

(On Diff #373087)

Can you comment on the profile line where the duplication factor is being changed to 10? and what's the count if there's no duplication factor?

30 ↗

(On Diff #373087)

I think it's better to have a test that can naturally generate duplication factor. That way it's easier to update the test case in the future if needed. To do that we can grab one of the test cases from loop unrolling, and if we enable fdebug-info-for-profiling, i think we should see duplication factor.

53 ↗

(On Diff #373087)

is this intentional?

llvm/tools/llvm-profgen/ProfileGenerator.cpp

547

nit: Count *= getDuplicationFactor(LeafLoc->Callsite.Discriminator)? Same for other places.

llvm/tools/llvm-profgen/ProfiledBinary.cpp

224

Current this function is only used for dwarf based profile, but is it guaranteed that this path will never be used by pseudo probe? we will need to handle discriminator differently for probe case (extractProbeIndex).

543–546

By removing this part, we will have duplication factor as part of location in NameStrings and call stack, is that what we want? Logically, duplication factor does not belong to location.

[wlei]

rebase and addressing some review feedbacks

llvm/test/tools/llvm-profgen/duplication-factor.test

30 ↗

(On Diff #373087)

I see, After adding the bigger test case(quick sort program), I found that will naturally generate a duplication factor case. So I just removed this test.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

547

Fixed!

llvm/tools/llvm-profgen/ProfiledBinary.cpp

224

Here the code is guaranteed only used by line-number based because this is the function to generate the StringBasedCtxKey.

std::shared_ptr<StringBasedCtxKey> FrameStack::getContextKey() {
  std::shared_ptr<StringBasedCtxKey> KeyStr =
      std::make_shared<StringBasedCtxKey>();
  KeyStr->Context = Binary->getExpandedContext(Stack, KeyStr->WasLeafInlined);
  ... 
}

543–546

I checked that our internal tools also used duplication factor this way, i. e decoding it when we need it in profile generation.

Alternatively, we can also have a hash map like {offset, duplication factor} offset2DuplicationFactorMap which can be built on-demand as well, which one do you think is better?

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

547

Am I not on the latest version? This seems not fixed.

llvm/tools/llvm-profgen/ProfiledBinary.cpp

543–546

Looks like the duplication factor is dropped during profile key generation (for CS it's dropped in getExpandedContext), while it is used when computing sample counts. So it should work.

Adding a map is cleaner, but I'm a bit concerned about its efficiency.

[wlei]

Updating D109934: [llvm-profgen] Add duplication factor for line-number based profile

[hoy]

lgtm

[wenlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

400

It looks like we get all duplication factors from callsite duplication factor, which is a bit weird given duplication factor applies to normal locations too. However this is a confusion cause by misleading naming. The name SampleContextFrame::Callsite is misleading because when used to represent leaf, there's no call site. It's FuncName/Location, rather than CallerName/Callsite.. I think the struct name was rename from Callsite into SampleContextFrame, but member names were kept as call site. Perhaps we should rename too, Hongtao?

llvm/tools/llvm-profgen/ProfiledBinary.cpp

543–546

I guess practically we only need to keep duplication factor for leaf frame, but not for middle call sites.. That way we don't need extra map. And call sites won't have different location due to duplication factor.

[wenlei]

llvm/tools/llvm-profgen/ProfileGenerator.h

46

nit: getBaseDiscriminator? (thought I commented on this before, but looks like I missed..)

[wlei]

getDiscriminator --> getBaseDiscriminator

llvm/tools/llvm-profgen/ProfileGenerator.h

46

Fixed!

llvm/tools/llvm-profgen/ProfiledBinary.cpp

543–546

I found that for CS line-number based context, the leaf frame of one address can be the middle of the whole context. In that case, we still need to manually decode the base discriminator for that frame. This might cause some inconsistencies.

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

400

Agreed. CallerName/Callsite is misleading as a field in SampleContextFrame. FuncName/Location sounds better. There are probably a lot places using them. Refactoring can be done in a separate change.

struct SampleContextFrame {
  StringRef CallerName;
  LineLocation Callsite;

  SampleContextFrame() : Callsite(0, 0) {}

  SampleContextFrame(StringRef CallerName, LineLocation Callsite)
      : CallerName(CallerName), Callsite(Callsite) {}

[wlei]

rebase

[wenlei]

lgtm, thanks.

llvm/tools/llvm-profgen/ProfiledBinary.cpp

543–546

Ok, sounds good.

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

 ;CHECK-NEXT:  4.2: swap:100
 ;CHECK-NEXT:   1: 25
 ;CHECK-NEXT:   2: 25
 ;CHECK-NEXT:   3: 25
 ;CHECK-NEXT:  5: swap:24
 ;CHECK-NEXT:   1: 6
 ;CHECK-NEXT:   2: 6
 ;CHECK-NEXT:   3: 6
-;CHECK-NEXT: quick_sort:414:25
-;CHECK-NEXT:  1: 24
-;CHECK-NEXT:  2: 12 partition_pivot_last:7 partition_pivot_first:5
-;CHECK-NEXT:  3: 11 quick_sort:12
-;CHECK-NEXT:  4: 12 quick_sort:12
-;CHECK-NEXT:  6: 24
-;CHECK-NEXT: partition_pivot_last:391:7
+;CHECK-NEXT: partition_pivot_last:649:7
 ;CHECK-NEXT:  1: 6
 ;CHECK-NEXT:  2: 6
 ;CHECK-NEXT:  3: 6
-;CHECK-NEXT:  3.1: 18
-;CHECK-NEXT:  3.3: 18
-;CHECK-NEXT:  4: 19
-;CHECK-NEXT:  5: 9
+
+;w/o duplication factor :  3.1: 18
+;w/o duplication factor :  3.3: 18
+;w/o duplication factor :  4: 19
+;w/o duplication factor :  5: 9
+;CHECK-NEXT:  3.1: 36
+;CHECK-NEXT:  3.3: 36
+;CHECK-NEXT:  4: 38
+;CHECK-NEXT:  5: 18
+
 ;CHECK-NEXT:  6: 5
 ;CHECK-NEXT:  7: 5
-;CHECK-NEXT:  5: swap:61
-;CHECK-NEXT:   1: 9
-;CHECK-NEXT:   2: 9
-;CHECK-NEXT:   3: 9
+;CHECK-NEXT:  5: swap:116
+
+;w/o duplication factor :  1: 9
+;w/o duplication factor :  2: 9
+;w/o duplication factor :  3: 9
+;CHECK-NEXT:   1: 18
+;CHECK-NEXT:   2: 18
+;CHECK-NEXT:   3: 18
+
 ;CHECK-NEXT:  6: swap:20
 ;CHECK-NEXT:   1: 5
 ;CHECK-NEXT:   2: 5
 ;CHECK-NEXT:   3: 5
+;CHECK-NEXT: quick_sort:414:25
+;CHECK-NEXT:  1: 24
+;CHECK-NEXT:  2: 12 partition_pivot_last:7 partition_pivot_first:5
+;CHECK-NEXT:  3: 11 quick_sort:12
+;CHECK-NEXT:  4: 12 quick_sort:12
+;CHECK-NEXT:  6: 24
 ;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

llvm/tools/llvm-profgen/ProfileGenerator.h

ProfileGeneratorBase(ProfiledBinary *Binary,
       : Binary(Binary), SampleCounters(Counters){};
   virtual ~ProfileGeneratorBase() = default;
   static std::unique_ptr<ProfileGeneratorBase>
   create(ProfiledBinary *Binary, const ContextSampleCounterMap &SampleCounters,
          bool ProfileIsCS);
   virtual void generateProfile() = 0;
   void write();
 
+  static uint32_t getDuplicationFactor(unsigned Discriminator) {
+    return llvm::DILocation::getDuplicationFactorFromDiscriminator(
+        Discriminator);
+  }
+
+  static uint32_t getBaseDiscriminator(unsigned Discriminator) {
+    return DILocation::getBaseDiscriminatorFromDiscriminator(
+        Discriminator, /* IsFSDiscriminator */ false);
+  }
+
 protected:
   // Use SampleProfileWriter to serialize profile map
   void write(std::unique_ptr<SampleProfileWriter> Writer,
              SampleProfileMap &ProfileMap);
   /*
   For each region boundary point, mark if it is begin or end (or both) of
   the region. Boundary points are inclusive. Log the sample count as well
   so we can use it when we compute the sample count of each disjoint region

llvm/tools/llvm-profgen/ProfileGenerator.cpp

 
 void ProfileGeneratorBase::updateBodySamplesforFunctionProfile(
     FunctionSamples &FunctionProfile, const SampleContextFrame &LeafLoc,
     uint64_t Count) {
   // Filter out invalid negative(int type) lineOffset
   if (LeafLoc.Location.LineOffset & 0x80000000)
     return;
   // Use the maximum count of samples with same line location
-  ErrorOr<uint64_t> R = FunctionProfile.findSamplesAt(
-      LeafLoc.Location.LineOffset, LeafLoc.Location.Discriminator);
+  uint32_t Discriminator = getBaseDiscriminator(LeafLoc.Location.Discriminator);
+  ErrorOr<uint64_t> R =
+      FunctionProfile.findSamplesAt(LeafLoc.Location.LineOffset, Discriminator);
+
   uint64_t PreviousCount = R ? R.get() : 0;
   if (PreviousCount <= Count) {
-    FunctionProfile.addBodySamples(LeafLoc.Location.LineOffset,
-                                   LeafLoc.Location.Discriminator,
+    FunctionProfile.addBodySamples(LeafLoc.Location.LineOffset, Discriminator,
                                    Count - PreviousCount);
   }
 }
 
 FunctionSamples &
 ProfileGenerator::getTopLevelFunctionProfile(StringRef FuncName) {
   SampleContext Context(FuncName);
   auto Ret = ProfileMap.emplace(Context, FunctionSamples());

 FunctionSamples &ProfileGenerator::getLeafProfileAndAddTotalSamples(
     const SampleContextFrameVector &FrameVec, uint64_t Count) {
   // Get top level profile
   FunctionSamples *FunctionProfile =
       &getTopLevelFunctionProfile(FrameVec[0].FuncName);
   FunctionProfile->addTotalSamples(Count);
 
   for (size_t I = 1; I < FrameVec.size(); I++) {
+    LineLocation Callsite(
+        FrameVec[I - 1].Location.LineOffset,
+        getBaseDiscriminator(FrameVec[I - 1].Location.Discriminator));
     FunctionSamplesMap &SamplesMap =
-        FunctionProfile->functionSamplesAt(FrameVec[I - 1].Location);
+        FunctionProfile->functionSamplesAt(Callsite);
     auto Ret =
         SamplesMap.emplace(FrameVec[I].FuncName.str(), FunctionSamples());
     if (Ret.second) {
       SampleContext Context(FrameVec[I].FuncName);
       Ret.first->second.setContext(Context);
     }
     FunctionProfile = &Ret.first->second;
     FunctionProfile->addTotalSamples(Count);
for (auto Range : preprocessRangeCounter(RangeCounter)) {
     // 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 =
           Binary->getFrameLocationStack(Offset);
       if (!FrameVec.empty()) {
+        uint64_t DC = Count * getDuplicationFactor(
+                                  FrameVec.back().Location.Discriminator);
         FunctionSamples &FunctionProfile =
-            getLeafProfileAndAddTotalSamples(FrameVec, Count);
+            getLeafProfileAndAddTotalSamples(FrameVec, DC);
         updateBodySamplesforFunctionProfile(FunctionProfile, FrameVec.back(),
-                                            Count);
+                                            DC);
       }
       // Move to next IP within the range.
       IP.advance();
     }
   }
 }
 
 void ProfileGenerator::populateBoundarySamplesForAllFunctions(
     const BranchSample &BranchCounters) {
   for (auto Entry : BranchCounters) {
     uint64_t SourceOffset = Entry.first.first;
     uint64_t TargetOffset = Entry.first.second;
     uint64_t Count = Entry.second;
     assert(Count != 0 && "Unexpected zero weight branch");
 
     // Get the callee name by branch target if it's a call branch.
     StringRef CalleeName = FunctionSamples::getCanonicalFnName(
         Binary->getFuncFromStartOffset(TargetOffset));
     if (CalleeName.size() == 0)
       continue;
     // Record called target sample and its count.
     const SampleContextFrameVector &FrameVec =
         Binary->getFrameLocationStack(SourceOffset);
     if (!FrameVec.empty()) {
+      Count *= getDuplicationFactor(FrameVec.back().Location.Discriminator);
       FunctionSamples &FunctionProfile =
           getLeafProfileAndAddTotalSamples(FrameVec, Count);
       FunctionProfile.addCalledTargetSamples(
           FrameVec.back().Location.LineOffset,
-          FrameVec.back().Location.Discriminator, CalleeName, Count);
+          getBaseDiscriminator(FrameVec.back().Location.Discriminator),
+          CalleeName, Count);
     }
     // Add head samples for callee.
     FunctionSamples &CalleeProfile = getTopLevelFunctionProfile(CalleeName);
     CalleeProfile.addHeadSamples(Count);
   }
 }
 
 FunctionSamples &CSProfileGenerator::getFunctionProfileForContext(
for (auto Range : Ranges) {
     // 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);
       auto LeafLoc = Binary->getInlineLeafFrameLoc(Offset);
       if (LeafLoc.hasValue()) {
         // Recording body sample for this specific context
-        updateBodySamplesforFunctionProfile(FunctionProfile, *LeafLoc, Count);
+        uint64_t DC =
+            Count * getDuplicationFactor(LeafLoc->Location.Discriminator);
+        updateBodySamplesforFunctionProfile(FunctionProfile, *LeafLoc, DC);
+        FunctionProfile.addTotalSamples(DC);
       }
-      // Accumulate total sample count even it's a line with invalid debug info
-      FunctionProfile.addTotalSamples(Count);
+
       // Move to next IP within the range
       IP.advance();
     }
   }
 }
 
 void CSProfileGenerator::populateBoundarySamplesForFunction(
     SampleContextFrames ContextId, FunctionSamples &FunctionProfile,
StringRef CalleeName = FunctionSamples::getCanonicalFnName(
         Binary->getFuncFromStartOffset(TargetOffset));
     if (CalleeName.size() == 0)
       continue;
 
     // Record called target sample and its count
     auto LeafLoc = Binary->getInlineLeafFrameLoc(SourceOffset);
     if (!LeafLoc.hasValue())
       continue;
-    FunctionProfile.addCalledTargetSamples(LeafLoc->Location.LineOffset,
-                                           LeafLoc->Location.Discriminator,
-                                           CalleeName, Count);
+    Count *= getDuplicationFactor(LeafLoc->Location.Discriminator);
+    FunctionProfile.addCalledTargetSamples(
+        LeafLoc->Location.LineOffset,
+        getBaseDiscriminator(LeafLoc->Location.Discriminator), CalleeName,
+        Count);
 
     // Record head sample for called target(callee)
     SampleContextFrameVector CalleeCtx(ContextId.begin(), ContextId.end());
     assert(CalleeCtx.back().FuncName == LeafLoc->FuncName &&
            "Leaf function name doesn't match");
     CalleeCtx.back() = *LeafLoc;
     CalleeCtx.emplace_back(CalleeName, LineLocation(0, 0));
     FunctionSamples &CalleeProfile = getFunctionProfileForContext(CalleeCtx);

llvm/tools/llvm-profgen/ProfiledBinary.cpp

for (auto Address : Stack) {
     if (ExpandedContext.empty())
       return SampleContextFrameVector();
     // Set WasLeafInlined to the size of inlined frame count for the last
     // address which is leaf
     WasLeafInlined = (ExpandedContext.size() > 1);
     ContextVec.append(ExpandedContext);
   }
 
+  // Replace with decoded base discriminator
+  for (auto &Frame : ContextVec) {
+    Frame.Location.Discriminator = ProfileGeneratorBase::getBaseDiscriminator(
+        Frame.Location.Discriminator);
+  }
+
   assert(ContextVec.size() && "Context length should be at least 1");
 
   // Compress the context string except for the leaf frame
   auto LeafFrame = ContextVec.back();
   LeafFrame.Location = LineLocation(0, 0);
   ContextVec.pop_back();
   CSProfileGenerator::compressRecursionContext(ContextVec);
   CSProfileGenerator::trimContext(ContextVec);
if (UseCanonicalFnName)
       FunctionName = FunctionSamples::getCanonicalFnName(FunctionName);
 
     uint32_t Discriminator = CallerFrame.Discriminator;
     uint32_t LineOffset = CallerFrame.Line - CallerFrame.StartLine;
     if (UseProbeDiscriminator) {
       LineOffset =
           PseudoProbeDwarfDiscriminator::extractProbeIndex(Discriminator);
       Discriminator = 0;
-    } else {
-      Discriminator = DILocation::getBaseDiscriminatorFromDiscriminator(
-          CallerFrame.Discriminator,
-          /* IsFSDiscriminator */ false);
     }
 
     LineLocation Line(LineOffset, Discriminator);
     auto It = NameStrings.insert(FunctionName.str());
     CallStack.emplace_back(*It.first, Line);
   }
 
   return CallStack;