[CSSPGO][llvm-profgen] Always report dangling probes for frames with real samples.

[hoy]

Summary

Report dangling probes for frames that have real samples collected. Dangling probes are the probes associated to an empty block. When reported, sample count on a dangling probe will not be trusted by the compiler and we will rely on the counts inference algorithm to get the probe a reasonable count. This actually fixes a bug where previously only those dangling probes with samples collected were reported.

This patch also fixes two existing issues. Pseudo probes are stored in Address2ProbesMap and their pointers are used in PseudoProbeInlineTree. Previously std::vector was used to store probes and the pointers to probes may get obsolete as the vector grows. I'm changing std::vector to std::list instead.

The other issue is that all outlined functions shared the same inline frame previously due to the unchanged Index value as the dummy inlineSite identifier.

Good results seen for SPEC2017 in general regarding profile quality.

[hoy]

Updating D100235: [CSSPGO][llvm-profgen] Fixing an obselete iterator issue.

[wenlei]

Another issue being fixed is that all outlined functions shared the same inline frame previously due to the unchanged Index value as the dummy inlineSite identifier.

Why is this an issue? What problem does this cause? Conceptually, if we want to give them a tree structure, top level inliner are indeed children of dummy root.

They could be used to visit all probes that are associated to an inline frame, which is something else I'll be working on.

We do have containers that can be re-allocated for growth, and doing that itself isn't an issue, unless it breaks specific use case. With what we have now we should not store pointers to inlinee's probe, and we're indeed doing that right now. So there's not bug, right?

If there's a future change that require changing this model (of not keeping probe pointers), perhaps make the vector->list change together with the change that has the new use case?

llvm/tools/llvm-profgen/PseudoProbe.cpp

217

nit: outline function -> top level inliner.

llvm/tools/llvm-profgen/PseudoProbe.h

74

Can we spell out the full return type? It seems we would use typedef if needed, but not so for auto return type.

[hoy]

In D100235#2681312, @wenlei wrote:

Another issue being fixed is that all outlined functions shared the same inline frame previously due to the unchanged Index value as the dummy inlineSite identifier.

Why is this an issue? What problem does this cause? Conceptually, if we want to give them a tree structure, top level inliner are indeed children of dummy root.

Yes, top level inliner is still children of dummy root with this change. However, they do not share dummy callsite id any more. Note that without this change, the dummy callsite id for top-level inliner (Index below) isn't updated correctly.

if (Root != Cur) {
   Index = readUnsignedNumber<uint32_t>();
 }

They could be used to visit all probes that are associated to an inline frame, which is something else I'll be working on.

We do have containers that can be re-allocated for growth, and doing that itself isn't an issue, unless it breaks specific use case. With what we have now we should not store pointers to inlinee's probe, and we're indeed doing that right now. So there's not bug, right?

If there's a future change that require changing this model (of not keeping probe pointers), perhaps make the vector->list change together with the change that has the new use case?

It doesn't break anything so far since PseudoProbeInlineTree.ProbeVector is not used anywhere. It might also be good to remove it for now since the container might end up with invalid pointers.

Probe pointers isn't an issue as long as they are valid. I'm using std::list instead of std::vector to store real probe objects so that taking address of them is never invalidated.

I'm actually working on a feature that reports all dangling probes in an inline frame into a profile, even if there are no samples collected for them. As of now only dangling probes with samples are reported. Since samples collected on a dangling probe doesn't make sense (dangling probes can be placed anywhere), they should always be reported so that the counts inferencer never overlooks them. It makes sense to include the current patch into that work.

[wenlei]

In D100235#2682347, @hoy wrote:

In D100235#2681312, @wenlei wrote:

Another issue being fixed is that all outlined functions shared the same inline frame previously due to the unchanged Index value as the dummy inlineSite identifier.

Why is this an issue? What problem does this cause? Conceptually, if we want to give them a tree structure, top level inliner are indeed children of dummy root.

Yes, top level inliner is still children of dummy root with this change. However, they do not share dummy callsite id any more. Note that without this change, the dummy callsite id for top-level inliner (Index below) isn't updated correctly.

if (Root != Cur) {
   Index = readUnsignedNumber<uint32_t>();
 }

Yeah, index would always be zero. But what problem does this cause? It seems that the call site id for top-level inliner is a dummy field anyways, so value should be ignored. Currently it works just fine, right? Is it also motivated by the upcoming change to report dangling probes with counts (so you need to different call site under dummy root)? If so, it might make sense to include it there as well..

They could be used to visit all probes that are associated to an inline frame, which is something else I'll be working on.

We do have containers that can be re-allocated for growth, and doing that itself isn't an issue, unless it breaks specific use case. With what we have now we should not store pointers to inlinee's probe, and we're indeed doing that right now. So there's not bug, right?

If there's a future change that require changing this model (of not keeping probe pointers), perhaps make the vector->list change together with the change that has the new use case?

It doesn't break anything so far since PseudoProbeInlineTree.ProbeVector is not used anywhere. It might also be good to remove it for now since the container might end up with invalid pointers.

Probe pointers isn't an issue as long as they are valid. I'm using std::list instead of std::vector to store real probe objects so that taking address of them is never invalidated.

I'm actually working on a feature that reports all dangling probes in an inline frame into a profile, even if there are no samples collected for them. As of now only dangling probes with samples are reported. Since samples collected on a dangling probe doesn't make sense (dangling probes can be placed anywhere), they should always be reported so that the counts inferencer never overlooks them. It makes sense to include the current patch into that work.

For dangling probe with counts, we currently use the special value (indicating dangling) instead of the actual count for output, right? What is the new behavior with upcoming change?

[hoy]

In D100235#2683311, @wenlei wrote:

In D100235#2682347, @hoy wrote:

In D100235#2681312, @wenlei wrote:

Another issue being fixed is that all outlined functions shared the same inline frame previously due to the unchanged Index value as the dummy inlineSite identifier.

Why is this an issue? What problem does this cause? Conceptually, if we want to give them a tree structure, top level inliner are indeed children of dummy root.

Yes, top level inliner is still children of dummy root with this change. However, they do not share dummy callsite id any more. Note that without this change, the dummy callsite id for top-level inliner (Index below) isn't updated correctly.

if (Root != Cur) {
   Index = readUnsignedNumber<uint32_t>();
 }

Yeah, index would always be zero. But what problem does this cause? It seems that the call site id for top-level inliner is a dummy field anyways, so value should be ignored. Currently it works just fine, right? Is it also motivated by the upcoming change to report dangling probes with counts (so you need to different call site under dummy root)? If so, it might make sense to include it there as well..

The index starts from zero, and could be updated by parsing an inlinee. And when it comes back to the next top-level inliner, the value index is the leftover from the previous inlinee. This causes top-level inliner frames non-deterministically shared. The fix is motivated by upcoming dangling probe work but I feel that it may also affect inliner context building for shared top-level frames. I'll see if I can find a case for that. Otherwise I'll include this fix in the dangling probe patch as well.

They could be used to visit all probes that are associated to an inline frame, which is something else I'll be working on.

We do have containers that can be re-allocated for growth, and doing that itself isn't an issue, unless it breaks specific use case. With what we have now we should not store pointers to inlinee's probe, and we're indeed doing that right now. So there's not bug, right?

If there's a future change that require changing this model (of not keeping probe pointers), perhaps make the vector->list change together with the change that has the new use case?

It doesn't break anything so far since PseudoProbeInlineTree.ProbeVector is not used anywhere. It might also be good to remove it for now since the container might end up with invalid pointers.

Probe pointers isn't an issue as long as they are valid. I'm using std::list instead of std::vector to store real probe objects so that taking address of them is never invalidated.

I'm actually working on a feature that reports all dangling probes in an inline frame into a profile, even if there are no samples collected for them. As of now only dangling probes with samples are reported. Since samples collected on a dangling probe doesn't make sense (dangling probes can be placed anywhere), they should always be reported so that the counts inferencer never overlooks them. It makes sense to include the current patch into that work.

For dangling probe with counts, we currently use the special value (indicating dangling) instead of the actual count for output, right? What is the new behavior with upcoming change?

The new behavior lets you always report dangling probe regardless of whether there're samples collected for them. Dangling probes may be placed anywhere and if they are accidentally placed next to an instruction not executed, currently the dangling probe will not be reported. And when it comes to the counts inferencer, it won't know the probe is dangling. It'll treat the probe as never executed.

[wenlei]

In D100235#2683507, @hoy wrote:

In D100235#2683311, @wenlei wrote:

In D100235#2682347, @hoy wrote:

In D100235#2681312, @wenlei wrote:

Another issue being fixed is that all outlined functions shared the same inline frame previously due to the unchanged Index value as the dummy inlineSite identifier.

Why is this an issue? What problem does this cause? Conceptually, if we want to give them a tree structure, top level inliner are indeed children of dummy root.

Yes, top level inliner is still children of dummy root with this change. However, they do not share dummy callsite id any more. Note that without this change, the dummy callsite id for top-level inliner (Index below) isn't updated correctly.

if (Root != Cur) {
   Index = readUnsignedNumber<uint32_t>();
 }

Yeah, index would always be zero. But what problem does this cause? It seems that the call site id for top-level inliner is a dummy field anyways, so value should be ignored. Currently it works just fine, right? Is it also motivated by the upcoming change to report dangling probes with counts (so you need to different call site under dummy root)? If so, it might make sense to include it there as well..

The index starts from zero, and could be updated by parsing an inlinee. And when it comes back to the next top-level inliner, the value index is the leftover from the previous inlinee. This causes top-level inliner frames non-deterministically shared. The fix is motivated by upcoming dangling probe work but I feel that it may also affect inliner context building for shared top-level frames. I'll see if I can find a case for that. Otherwise I'll include this fix in the dangling probe patch as well.

I see. If it's not always zero, then it's not good.. In that case, we could fix it here setting it to 0, or change it like what you have and group it with the upcoming change that relies on call site id being differentiator.

They could be used to visit all probes that are associated to an inline frame, which is something else I'll be working on.

We do have containers that can be re-allocated for growth, and doing that itself isn't an issue, unless it breaks specific use case. With what we have now we should not store pointers to inlinee's probe, and we're indeed doing that right now. So there's not bug, right?

If there's a future change that require changing this model (of not keeping probe pointers), perhaps make the vector->list change together with the change that has the new use case?

It doesn't break anything so far since PseudoProbeInlineTree.ProbeVector is not used anywhere. It might also be good to remove it for now since the container might end up with invalid pointers.

Probe pointers isn't an issue as long as they are valid. I'm using std::list instead of std::vector to store real probe objects so that taking address of them is never invalidated.

I'm actually working on a feature that reports all dangling probes in an inline frame into a profile, even if there are no samples collected for them. As of now only dangling probes with samples are reported. Since samples collected on a dangling probe doesn't make sense (dangling probes can be placed anywhere), they should always be reported so that the counts inferencer never overlooks them. It makes sense to include the current patch into that work.

For dangling probe with counts, we currently use the special value (indicating dangling) instead of the actual count for output, right? What is the new behavior with upcoming change?

The new behavior lets you always report dangling probe regardless of whether there're samples collected for them. Dangling probes may be placed anywhere and if they are accidentally placed next to an instruction not executed, currently the dangling probe will not be reported. And when it comes to the counts inferencer, it won't know the probe is dangling. It'll treat the probe as never executed.

Makes sense, thanks for clarification.

[hoy]

Updating D100235: [CSSPGO][llvm-profgen] Always report dangling probes for frames with real samples.

[hoy]

Updating D100235: [CSSPGO][llvm-profgen] Always report dangling probes for frames with real samples.

llvm/tools/llvm-profgen/PseudoProbe.cpp

217

Fixed.

llvm/tools/llvm-profgen/PseudoProbe.h

74

Sounds good.

[wlei]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

518 ↗

(On Diff #338682)

Try to understand this.

If pass2's probe is dangling, then return 0 no matter what in the profile(pass1);

If pass2's probe is not dangling and reading from profile gets a dangling probe(pass1), then return invalid count(UINT64_MAX), (this case happen because later the BB of the probe will be removed)

is that right?

So this change make sure all the future removed BB will be identified as dangling so that the inference algorithm can work on this?

is this issue also coming from the rebalancing algorithm?

like we have TrueBranch :0 and FalseBranch: 0, the rebalancing algorithm can't work on this.

but if we have TrueBranch:0 and FalseBranch:dangling, then it can be rebalanced.

[wenlei]

lgtm, thanks!

llvm/tools/llvm-profgen/ProfileGenerator.cpp

518 ↗

(On Diff #338682)

By return, you meant the return value of SampleProfileLoader::getProbeWeight?

For inference, I think what matters is whether probe is dangling from pass1.

llvm/tools/llvm-profgen/PseudoProbe.h

50

nit: a more reflective type name, something like InlinedProbesMap, InlinedProbeTreeMap?

[hoy]

llvm/tools/llvm-profgen/ProfileGenerator.cpp

518 ↗

(On Diff #338682)

Here is only about pass1. llvm-profgen runs on pass1 binary and perf data. A dangling probe here is from pass1.

When the dangling-ness is imported in pass2, the compiler has to guess its sample count instead of trusting what's collected in pass1. When the same probe is seen also dangling in pass2 compilation, it indicates that the code being probed is removed by pass2, therefore, no matter what samples pass1 collected for it, it shouldn't matter since pass2 is no longer interested in the probe.

The issue was noticed when a dangling probe was not reported dangling, thus the counts inferencer trust its zero sample count instead of inferring a count for it. Though I didn't see it directly related to rebalancing, I believe it will fix your example case.

llvm/tools/llvm-profgen/PseudoProbe.h

50

InlinedProbeTreeMap sounds good.

[hoy]

Renaming ChildrenType to InlinedProbeTreeMap.

[wlei]

LGTM, thanks for the fix.

llvm/tools/llvm-profgen/ProfileGenerator.cpp

518 ↗

(On Diff #338682)

By return, you meant the return value of SampleProfileLoader::getProbeWeight?

Yes, I mean when get the value from pass2.

The issue was noticed when a dangling probe was not reported dangling, thus the counts inferencer trust its zero sample count instead of inferring a count for it. Though I didn't see it directly related to rebalancing, I believe it will fix your example case.

I see, thanks for the helpful explanation.

llvm/include/llvm/MC/MCPseudoProbe.h

 //          ADDRESS_TYPE (uint1)
 //            0 - code address, 1 - address delta
 //          CODE_ADDRESS (uint64 or ULEB128)
 //            code address or address delta, depending on ADDRESS_TYPE
 //    INLINED FUNCTION RECORDS
 //        A list of NUM_INLINED_FUNCTIONS entries describing each of the inlined
 //        callees.  Each record contains:
 //          INLINE SITE
-//            GUID of the inlinee (uint64)
 //            ID of the callsite probe (ULEB128)
 //          FUNCTION BODY
 //            A FUNCTION BODY entry describing the inlined function.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_MC_MCPSEUDOPROBE_H
 #define LLVM_MC_MCPSEUDOPROBE_H
 

llvm/tools/llvm-profgen/PseudoProbe.h

class PseudoProbeInlineTree {
 
   struct InlineSiteHash {
     uint64_t operator()(const InlineSite &Site) const {
       return std::get<0>(Site) ^ std::get<1>(Site);
     }
   };
   std::unordered_map<InlineSite, std::unique_ptr<PseudoProbeInlineTree>,
                      InlineSiteHash>
       Children;
 
 public:
   // Inlinee function GUID
   uint64_t GUID = 0;
   // Inline site to indicate the location in its inliner. As the node could also
   // be an outlined function, it will use a dummy InlineSite whose GUID and
   // Index is 0 connected to the dummy root
   InlineSite ISite;
   // Used for decoding
   uint32_t ChildrenToProcess = 0;
   // Caller node of the inline site
   PseudoProbeInlineTree *Parent;
 
   PseudoProbeInlineTree(){};
   PseudoProbeInlineTree(const InlineSite &Site) : ISite(Site){};
 
   PseudoProbeInlineTree *getOrAddNode(const InlineSite &Site) {
     auto Ret =
         Children.emplace(Site, std::make_unique<PseudoProbeInlineTree>(Site));
     Ret.first->second->Parent = this;
     return Ret.first->second.get();
   }
 
+  auto &getChildren() { return Children; }
   void addProbes(PseudoProbe *Probe) { ProbeVector.push_back(Probe); }
   // Return false if it's a dummy inline site
   bool hasInlineSite() const { return std::get<0>(ISite) != 0; }
 };
 
 // Function descriptor decoded from .pseudo_probe_desc section
 struct PseudoProbeFuncDesc {
   uint64_t FuncGUID = 0;
   uint64_t FuncHash = 0;
   std::string FuncName;
 
   PseudoProbeFuncDesc(uint64_t GUID, uint64_t Hash, StringRef Name)
       : FuncGUID(GUID), FuncHash(Hash), FuncName(Name){};
 
   void print(raw_ostream &OS);
 };
 
 // GUID to PseudoProbeFuncDesc map
 using GUIDProbeFunctionMap = std::unordered_map<uint64_t, PseudoProbeFuncDesc>;
 // Address to pseudo probes map.
-using AddressProbesMap = std::unordered_map<uint64_t, std::vector<PseudoProbe>>;
+using AddressProbesMap = std::unordered_map<uint64_t, std::list<PseudoProbe>>;
 
 /*
 A pseudo probe has the format like below:
   INDEX (ULEB128)
   TYPE (uint4)
     0 - block probe, 1 - indirect call, 2 - direct call
   ATTRIBUTE (uint3)
     1 - tail call, 2 - dangling

llvm/tools/llvm-profgen/PseudoProbe.cpp

void PseudoProbeDecoder::buildAddress2ProbeMap(const uint8_t *Start,
   //           ADDRESS_TYPE (uint1)
   //             0 - code address, 1 - address delta
   //           CODE_ADDRESS (uint64 or ULEB128)
   //             code address or address delta, depending on Flag
   //     INLINED FUNCTION RECORDS
   //         A list of NUM_INLINED_FUNCTIONS entries describing each of the
   //         inlined callees.  Each record contains:
   //           INLINE SITE
-  //             GUID of the inlinee (uint64)
   //             Index of the callsite probe (ULEB128)
   //           FUNCTION BODY
   //             A FUNCTION BODY entry describing the inlined function.
 #ifndef NDEBUG
   SectionName = "pseudo_probe";
 #endif
   Data = Start;
   End = Data + Size;
 
   PseudoProbeInlineTree *Root = &DummyInlineRoot;
   PseudoProbeInlineTree *Cur = &DummyInlineRoot;
   uint64_t LastAddr = 0;
   uint32_t Index = 0;
   // A DFS-based decoding
   while (Data < End) {
+    if (Root == Cur) {
+      // Use a sequential id for outline functions.
+      Index = Root->getChildren().size();
+    } else {
       // Read inline site for inlinees
-    if (Root != Cur) {
       Index = readUnsignedNumber<uint32_t>();
     }
     // Switch/add to a new tree node(inlinee)
     Cur = Cur->getOrAddNode(std::make_tuple(Cur->GUID, Index));
     // Read guid
     Cur->GUID = readUnencodedNumber<uint64_t>();
     // Read number of probes in the current node.
     uint32_t NodeCount = readUnsignedNumber<uint32_t>();
for (std::size_t I = 0; I < NodeCount; I++) {
       uint64_t Addr = 0;
       if (Value & 0x80) {
         int64_t Offset = readSignedNumber<int64_t>();
         Addr = LastAddr + Offset;
       } else {
         Addr = readUnencodedNumber<int64_t>();
       }
       // Populate Address2ProbesMap
-      std::vector<PseudoProbe> &ProbeVec = Address2ProbesMap[Addr];
-      ProbeVec.emplace_back(Addr, Cur->GUID, Index, PseudoProbeType(Kind), Attr,
-                            Cur);
-      Cur->addProbes(&ProbeVec.back());
+      auto &Probes = Address2ProbesMap[Addr];
+      Probes.emplace_back(Addr, Cur->GUID, Index, PseudoProbeType(Kind), Attr,
+      Cur->addProbes(&Probes.back());
       LastAddr = Addr;
     }
 
     // Look for the parent for the next node by subtracting the current
     // node count from tree counts along the parent chain. The first node
     // in the chain that has a non-zero tree count is the target.
     while (Cur != Root) {
       if (Cur->ChildrenToProcess == 0) {
void PseudoProbeDecoder::printProbeForAddress(raw_ostream &OS,
   }
 }
 
 const PseudoProbe *
 PseudoProbeDecoder::getCallProbeForAddr(uint64_t Address) const {
   auto It = Address2ProbesMap.find(Address);
   if (It == Address2ProbesMap.end())
     return nullptr;
-  const std::vector<PseudoProbe> &Probes = It->second;
+  const auto &Probes = It->second;
 
   const PseudoProbe *CallProbe = nullptr;
   for (const auto &Probe : Probes) {
     if (Probe.isCall()) {
       assert(!CallProbe &&
              "There should be only one call probe corresponding to address "
              "which is a callsite.");
       CallProbe = &Probe;