[llvm-profgen] Fix bug of loop scope mismatch

[wlei]

Summary

One performance issue happened in profile generation and it turned out the line 525 loop is the bottleneck.
Moving the code outside of loop scope can fix this issue. The run time is improved from 30+mins to ~30s.

[wenlei]

Good catch! Is this cause of the slow down we saw today and is this a regression?

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

I'm wondering here if FunctionSamples * should be Vector<FunctionSamples *> as same frame can point to different FunctionSamples?

[wlei]

In D107529#2927429, @wenlei wrote:

Good catch! Is this cause of the slow down we saw today and is this a regression?

Yes, it's today's slowing down and regression(it should also improve other cases), I reproduced @spupyrev 's script and saw 99% of the time spent is in line 525 loop and the loop size is 100,000+.

[hoy]

Good catch, thanks for the fix!

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

An inline context under a given calling context should uniquely identify an inline frame, therefore can only point to one leaf profile. Am I missing anything?

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

Sorry I meant std::set<FunctionSamples *>.

I'm thinking the multiple probes cases from different call stack and they have the same leaf probe. like
[Probe1, Probe3] and [Probe1, Probe2]

Here Probe1 will have two FunctionSamples.

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

Oh. Here in populateBodySamplesWithProbes has already guaranteed to have unique call stack, so no multiple probe cases. Sorry for the confusing.

[wlei]

Hmm, I compared this patch against previous output, it's not identical. I still need some time digging it before land this.

[wlei]

change to std::unordered_set<FunctionSamples *> instead of FunctionSamples *

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

@hoy I found that the probe->getInlineTreeNode() is not the leaf frame so here it's not unique, the unique one should be like "probe + leaf function" and the leaf function is given from its FuncDesc. It happened that there are different the leaf functions.

See the reference below, "Note that the context from probe doesn't include leaf frame, hence we need to retrieve and prepend leaf if requested.", when we extract the inline context, we still need to append the leaf frame.

void MCPseudoProbeDecoder::getInlineContextForProbe(
    const MCDecodedPseudoProbe *Probe,
    SmallVectorImpl<std::string> &InlineContextStack, bool IncludeLeaf) const {
  Probe->getInlineContext(InlineContextStack, GUID2FuncDescMap, true);
  if (!IncludeLeaf)
    return;
  // Note that the context from probe doesn't include leaf frame,
  // hence we need to retrieve and prepend leaf if requested.
  const auto *FuncDesc = getFuncDescForGUID(Probe->getGuid());
  InlineContextStack.emplace_back(FuncDesc->FuncName + ":" +
                                  Twine(Probe->getIndex()).str());
}

So I changed to use unordered_set for multiple leaf frame FunctionSample. See if this looks good to you?

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

I see, a callsite can lead to different leaf frames, if it is an indirect callsite. That's a good find, thanks! Yeah, using unordered_set sounds good to me. Does it close the gap you saw with the loop scope change?

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

Yes, Now the output of this change is identical to the one without this change while building the clang script

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

That's nice. Wondering what could cause same inline context to point to different frames. For the clang pass1 build, ICP shouldn't be triggered?

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

My understanding is the same frame can point to different inline contexts, same inline context should point to same frame. e.g. probe1(GUID:foo) and probe2(GUID:bar) can point to the same frame(inlinetree) and when the inlinetree's context is extracted like main @ goo and there full context will be
probe1 : main @ goo @ foo
probe2: main @ goo @ bar.

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

In your example, does foo and bar share the same callsite in goo?

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

Yes, that's why here changed to unordered_set, and as you mentioned, foo and bar is indirect call

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

I was wondering for clang pass1 build, how was the indirect call promoted. We don't use profile for pass1 thus ICP should not be triggered?

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

I guess two probes with inline contexts can be merged, and the merged inline context is trimmed to empty of a common part of the inputs. Anyway, that's unrelated to this patch. Using an unordered_set sounds good to me.

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

524–525

Thanks for the discussion! That's interesting question, I'm trying to find something in the clang asm, but it's too large to debug. I will land this first and later try to run on SPEC to see if something easy to catch.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

 //===-- ProfileGenerator.cpp - Profile Generator  ---------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "ProfileGenerator.h"
 #include "llvm/ProfileData/ProfileCommon.h"
+#include <unordered_set>
 
 static cl::opt<std::string> OutputFilename("output", cl::value_desc("output"),
                                            cl::Required,
                                            cl::desc("Output profile file"));
 static cl::alias OutputA("o", cl::desc("Alias for --output"),
                          cl::aliasopt(OutputFilename));
 
 static cl::opt<SampleProfileFormat> OutputFormat(

 
 void PseudoProbeCSProfileGenerator::populateBodySamplesWithProbes(
     const RangeSample &RangeCounter,
     SmallVectorImpl<std::string> &ContextStrStack, ProfiledBinary *Binary) {
   ProbeCounterMap ProbeCounter;
   // Extract the top frame probes by looking up each address among the range in
   // the Address2ProbeMap
   extractProbesFromRange(RangeCounter, ProbeCounter, Binary);
-  std::unordered_map<MCDecodedPseudoProbeInlineTree *, FunctionSamples *>
+  std::unordered_map<MCDecodedPseudoProbeInlineTree *,
+                     std::unordered_set<FunctionSamples *>>
       FrameSamples;
   for (auto PI : ProbeCounter) {
     const MCDecodedPseudoProbe *Probe = PI.first;
     uint64_t Count = PI.second;
     FunctionSamples &FunctionProfile =
         getFunctionProfileForLeafProbe(ContextStrStack, Probe, Binary);
     // Record the current frame and FunctionProfile whenever samples are
     // collected for non-danglie probes. This is for reporting all of the
     // zero count probes of the frame later.
-    FrameSamples[Probe->getInlineTreeNode()] = &FunctionProfile;
+    FrameSamples[Probe->getInlineTreeNode()].insert(&FunctionProfile);
     FunctionProfile.addBodySamplesForProbe(Probe->getIndex(), Count);
     FunctionProfile.addTotalSamples(Count);
     if (Probe->isEntry()) {
       FunctionProfile.addHeadSamples(Count);
       // Look up for the caller's function profile
       const auto *InlinerDesc = Binary->getInlinerDescForProbe(Probe);
       if (InlinerDesc != nullptr) {
         // Since the context id will be compressed, we have to use callee's
if (Probe->isEntry()) {
         CallerProfile.setFunctionHash(InlinerDesc->FuncHash);
         CallerProfile.addBodySamples(CallerIndex, 0, Count);
         CallerProfile.addTotalSamples(Count);
         CallerProfile.addCalledTargetSamples(
             CallerIndex, 0,
             FunctionProfile.getContext().getNameWithoutContext(), Count);
       }
     }
+  }
 
-    // Assign zero count for remaining probes without sample hits to
-    // differentiate from probes optimized away, of which the counts are unknown
-    // and will be inferred by the compiler.
-    for (auto &I : FrameSamples) {
-      auto *FunctionProfile = I.second;
+    for (auto *FunctionProfile : I.second) {
       for (auto *Probe : I.first->getProbes()) {
         FunctionProfile->addBodySamplesForProbe(Probe->getIndex(), 0);
       }
     }
   }
 }
 
 void PseudoProbeCSProfileGenerator::populateBoundarySamplesWithProbes(