[CSSPGO][Preinliner] Trim cold call edges of the profiled call graph for a more stable profile generation.

[hoy]

Summary

I've noticed that for some services CSSPGO profile is less stable than non-CS AutoFDO profile from profiling to profiling without source changes. This is manifested by comparing profile similarities. For example in my experiments, AutoFDO profiles are always 99+% similar over same binary but different inputs (very close dynamic traffics) while CSSPGO profile similarity is around 90%.

The main source of the profile stability is the top-down order computed on the profiled call graph in the llvm-profgen CS preinliner. The top-down order is used to guide the CS preinliner to pre-compute an inline decision that is later on fulfilled by the compiler. A subtle change in the top-down order from run to run could cause a different inline decision computed. A deeper look in the diversion of the top-down order revealed that:

• The topological sorting inside one SCC isn't quite right. This is fixed by D130717: [SCCIterator] Fix an issue in scc_member_iterator sorting.
• The profiled call graphs of the two sides of the A/B run isn't 100% the same. The call edges in the two runs do not subsume each other, and edges appear in both graphs may not have exactly the same weight. This is due to the nature that the graphs are dynamic. However, I saw that the graphs can be made more close by removing the cold edges from them and this bumped up the CSSPGO profile stableness to the same level of the AutoFDO profile.

Removing cold call edges from the dynamic call graph may have an impact on cold inlining, but so far I haven't seen any performance issues since the CS preinliner mainly targets hot callsites, and cold inlining can always be done by the compiler CGSCC inliner.

Also fixing an issue where the largest weight instead of the accumulated weight for a call edge is used in the profiled call graph.

[wenlei]

llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h

164

good catch

llvm/tools/llvm-profgen/CSPreInliner.cpp

89

I understand that you want to do this only for preinliner, not for sample loader in compiler. But the current way of doing this - exposing internals of profiled calll graph only for users to tweak the actual graph, is less than idea as it breaks the abstraction.

Can we have a separate parameter (i.e. hotCallonly) for ctor of ProfiledCallGraph, so this is all self contained? And perhaps slight more efficient as it avoids add and then removal.

[hoy]

llvm/tools/llvm-profgen/CSPreInliner.cpp

89

I can pass in the threshold and do the trimming in place inside ProfiledCallGraph, wdyt?

Perhaps we have to add the edges first and then remove the cold ones after the weight accumulation is done.

[wenlei]

llvm/tools/llvm-profgen/CSPreInliner.cpp

89

Sounds good.

(I'm still leaning towards something like hotEdgesOnly as extra argument to keep the interface simple. But I can see that we will need to pass in ProfileSummary anyways, so passing a threshold value directly sounds good.)

[hoy]

Addressing comments.

[wenlei]

llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h

67–68

nit: IgnoreColdCallThreshold

llvm/tools/llvm-profgen/CSPreInliner.cpp

84

why is +1 needed? if cold threshold is 0, nothing is cold, and we filter out nothing -- it just works?

[wlei]

llvm/tools/llvm-profgen/CSPreInliner.cpp

82

I kinda remember we discussed offline that you tested for trimming hot edges vs trimming cold edges, how about other threshold, like trimming non-hot edges, or it's just a balance, then I'm wondering if other value can perform better, in that case we can tune a new threshold?

[hoy]

llvm/tools/llvm-profgen/CSPreInliner.cpp

82

Good question. With the cold threshold, CSSPGO profile goes up to 99% similar run to run, so using hot threshold isn't that helpful and it also regresses performance a little bit.

84

There are still zero-weight edges coming from callstack unwinding and they do not show up in the profile. I think. we want to trim them.

[hoy]

Addressing feedbacks.

[wenlei]

llvm/tools/llvm-profgen/CSPreInliner.cpp

84

what I meant is if cold threshold is already zero anyways, that would mean nothing is cold. so nothing should be trimmed. Usually cold threshold is never zero, in which case all those zero-weight edges will be trimmed without +1.

[hoy]

llvm/tools/llvm-profgen/CSPreInliner.cpp

84

The cold threshold is mainly computed from LBR samples and it shouldn't be zero. But we are trimming edges with weight below the threshold (line 199 in ProfiledCallGraph.h), so the +1 here is to make sure all cold edges go away.

The +1 is not needed here if we use a less-equal check on the profiled call graph check. But there isn't a way to not trim any edges unless we make the zero threshold special in the interface. (well, I have the check in line 192 in ProfiledCallGraph.h to make is special right now, but it's unnecessary as interface-wise zero is not considered special).

[wenlei]

llvm/tools/llvm-profgen/CSPreInliner.cpp

84

I understand what you said. But let me try one more time. :) So you want to differentiate 0 as special value to disable trimming vs 0 as a real threshold for trimming. What I meant we don't need to differentiate, because 0 as a real threshold also means no need for trimming at all.

If we consider anything "< threshold" as cold, threshold equals 0 means nothing is cold, hence nothing needs to be trimmed. This is not a big deal anyways, but I just feel that things fits together nicely already without needing +1.

[hoy]

Addressing feedbacks.

llvm/tools/llvm-profgen/CSPreInliner.cpp

84

Talked off. Would like to go with inclusive for the threshold.

[wenlei]

lgtm, thanks.

llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h

struct ProfiledCallGraphNode {
   edges Edges;
 };
 
 class ProfiledCallGraph {
 public:
   using iterator = ProfiledCallGraphNode::iterator;
 
   // Constructor for non-CS profile.
-  ProfiledCallGraph(SampleProfileMap &ProfileMap) {
+  ProfiledCallGraph(SampleProfileMap &ProfileMap,
+                    uint64_t IgnoreColdCallThreshold = 0) {
     assert(!FunctionSamples::ProfileIsCS &&
            "CS flat profile is not handled here");
     for (const auto &Samples : ProfileMap) {
       addProfiledCalls(Samples.second);
     }
+
+    // Trim edges with weight up to `IgnoreColdCallThreshold`. This aims
+    // for a more stable call graph with "determinstic" edges from run to run.
+    trimColdEges(IgnoreColdCallThreshold);
   }
 
   // Constructor for CS profile.
-  ProfiledCallGraph(SampleContextTracker &ContextTracker) {
+  ProfiledCallGraph(SampleContextTracker &ContextTracker,
+                    uint64_t IgnoreColdCallThreshold = 0) {
     // BFS traverse the context profile trie to add call edges for calls shown
     // in context.
     std::queue<ContextTrieNode *> Queue;
     for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
       ContextTrieNode *Callee = &Child.second;
       addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
       Queue.push(Callee);
     }
while (!Queue.empty()) {
           }
           Weight = std::max(CallsiteCount, CalleeEntryCount);
         }
 
         addProfiledCall(ContextTracker.getFuncNameFor(Caller),
                         ContextTracker.getFuncNameFor(Callee), Weight);
       }
     }
+
+    // Trim edges with weight up to `IgnoreColdCallThreshold`. This aims
+    // for a more stable call graph with "determinstic" edges from run to run.
+    trimColdEges(IgnoreColdCallThreshold);
   }
 
   iterator begin() { return Root.Edges.begin(); }
   iterator end() { return Root.Edges.end(); }
   ProfiledCallGraphNode *getEntryNode() { return &Root; }
+
   void addProfiledFunction(StringRef Name) {
     if (!ProfiledFunctions.count(Name)) {
       // Link to synthetic root to make sure every node is reachable
       // from root. This does not affect SCC order.
       ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
       Root.Edges.emplace(&Root, &ProfiledFunctions[Name], 0);
     }
   }
 
 private:
   void addProfiledCall(StringRef CallerName, StringRef CalleeName,
                        uint64_t Weight = 0) {
     assert(ProfiledFunctions.count(CallerName));
     auto CalleeIt = ProfiledFunctions.find(CalleeName);
     if (CalleeIt == ProfiledFunctions.end())
       return;
     ProfiledCallGraphEdge Edge(&ProfiledFunctions[CallerName],
                                &CalleeIt->second, Weight);
     auto &Edges = ProfiledFunctions[CallerName].Edges;
     auto EdgeIt = Edges.find(Edge);
     if (EdgeIt == Edges.end()) {
       Edges.insert(Edge);
-    } else if (EdgeIt->Weight < Edge.Weight) {
-      // Replace existing call edges with same target but smaller weight.
+    } else {
+      // Accumulate weight to the existing edge.
+      Edge.Weight += EdgeIt->Weight;
       Edges.erase(EdgeIt);
       Edges.insert(Edge);
     }
   }
 
   void addProfiledCalls(const FunctionSamples &Samples) {
     addProfiledFunction(Samples.getFuncName());
 
for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
         addProfiledFunction(InlinedSamples.first);
         addProfiledCall(Samples.getFuncName(), InlinedSamples.first,
                         InlinedSamples.second.getHeadSamplesEstimate());
         addProfiledCalls(InlinedSamples.second);
       }
     }
   }
 
+  // Trim edges with weight up to `Threshold`. Do not trim anything if
+  // `Threshold` is zero.
+  void trimColdEges(uint64_t Threshold = 0) {
+    if (!Threshold)
+      return;
+
+    for (auto &Node : ProfiledFunctions) {
+      auto &Edges = Node.second.Edges;
+      auto I = Edges.begin();
+      while (I != Edges.end()) {
+        if (I->Weight <= Threshold)
+          I = Edges.erase(I);
+        else
+          I++;
+      }
+    }
+  }
+
   ProfiledCallGraphNode Root;
   StringMap<ProfiledCallGraphNode> ProfiledFunctions;
 };
 
 } // end namespace sampleprof
 
 template <> struct GraphTraits<ProfiledCallGraphNode *> {
   using NodeType = ProfiledCallGraphNode;

llvm/tools/llvm-profgen/CSPreInliner.cpp

CSPreInliner::CSPreInliner(SampleContextTracker &Tracker,
   if (!SampleColdCallSiteThreshold.getNumOccurrences())
     SampleColdCallSiteThreshold = 0;
   if (!ProfileInlineLimitMax.getNumOccurrences())
     ProfileInlineLimitMax = 50000;
 }
 
 std::vector<StringRef> CSPreInliner::buildTopDownOrder() {
   std::vector<StringRef> Order;
-  ProfiledCallGraph ProfiledCG(ContextTracker);
+  // Trim cold edges to get a more stable call graph. This allows for a more
+  // stable top-down order which in turns helps the stablity of the generated
+  // profile from run to run.
+  uint64_t ColdCountThreshold = ProfileSummaryBuilder::getColdCountThreshold(
+      (Summary->getDetailedSummary()));
+  ProfiledCallGraph ProfiledCG(ContextTracker, ColdCountThreshold);
 
   // Now that we have a profiled call graph, construct top-down order
   // by building up SCC and reversing SCC order.
   scc_iterator<ProfiledCallGraph *> I = scc_begin(&ProfiledCG);
   while (!I.isAtEnd()) {
     auto Range = *I;
     if (SortProfiledSCC) {
       // Sort nodes in one SCC based on callsite hotness.
       scc_member_iterator<ProfiledCallGraph *> SI(*I);
       Range = *SI;
     }
     for (auto *Node : Range) {
       if (Node != ProfiledCG.getEntryNode())