profilie inference changes for stale profile matching

[spupyrev]

Summary

This diff facilitates a new stale profile matching in BOLT: D144500

This is a no-op for existing usages of profi (CSSPGO).

[hoy]

llvm/lib/Transforms/Utils/SampleProfileInference.cpp

1236

nit: you can just assert on the return value of the insert operation, which returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

1338

Wondering in what cases a function doesn't come in with samples? Thought we should have bailed out on a higher level in the sample loader.

[spupyrev]

review

[spupyrev]

llvm/lib/Transforms/Utils/SampleProfileInference.cpp

1338

This is going to be called from BOLT in addition to sample loader. One scenario when a function doesn't have samples is when its profile data is so stale that we couldn't match a single block/jump/call.
(I agree that check could be verified earlier but i don't see a big advantage.)

[hoy]

LGTM.

[wenlei]

llvm/lib/Transforms/Utils/SampleProfileInference.cpp

1230

how about noreturn function, or functions with an infinite loop? These are not important functions to optimize, but at least we shouldn't fail on those cases?

1338

SampleProfileInference<BT>::apply has the same logic to check function size and whether there's sample. Better unify and avoid duplication. I also agree that it's better to check at caller side.

llvm/lib/Transforms/Utils/SampleProfileInference.cpp

 
 #include "llvm/Transforms/Utils/SampleProfileInference.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include <queue>
 #include <set>
 #include <stack>
+#include <unordered_set>
 
 using namespace llvm;
 #define DEBUG_TYPE "sample-profile-inference"
 
 namespace {
 
 static cl::opt<bool> SampleProfileEvenFlowDistribution(
     "sample-profile-even-flow-distribution", cl::init(true), cl::Hidden,
for (uint64_t B = 0; B < NumBlocks; B++) {
     auto &Block = Func.Blocks[B];
     Block.Flow = std::max(OutFlow[B], InFlow[B]);
   }
 }
 
 #ifndef NDEBUG
 /// Verify that the provided block/jump weights are as expected.
 void verifyInput(const FlowFunction &Func) {
-  // Verify the entry block
+  // Verify entry and exit blocks
   assert(Func.Entry == 0 && Func.Blocks[0].isEntry());
+  size_t NumExitBlocks = 0;
   for (size_t I = 1; I < Func.Blocks.size(); I++) {
     assert(!Func.Blocks[I].isEntry() && "multiple entry blocks");
+    if (Func.Blocks[I].isExit())
+      NumExitBlocks++;
+  }
+  assert(NumExitBlocks > 0 && "cannot find exit blocks");
+
+  // Verify that there are no parallel edges
+  for (auto &Block : Func.Blocks) {
+    std::unordered_set<uint64_t> UniqueSuccs;
+    for (auto &Jump : Block.SuccJumps) {
+      auto It = UniqueSuccs.insert(Jump->Target);
+      assert(It.second && "input CFG contains parallel edges");
+    }
   }
   // Verify CFG jumps
   for (auto &Block : Func.Blocks) {
     assert((!Block.isEntry() || !Block.isExit()) &&
            "a block cannot be an entry and an exit");
   }
   // Verify input block weights
   for (auto &Block : Func.Blocks) {
for (uint64_t I = 0; I < NumBlocks; I++) {
     auto &Block = Func.Blocks[I];
     assert((Visited[I] || Block.Flow == 0) && "an isolated flow component");
   }
 }
 #endif
 
 } // end of anonymous namespace
 
-/// Apply the profile inference algorithm for a given function
+/// Apply the profile inference algorithm for a given function and provided
+/// profi options
 void llvm::applyFlowInference(const ProfiParams &Params, FlowFunction &Func) {
+  // Check if the function has samples and assign initial flow values
+  bool HasSamples = false;
+  for (FlowBlock &Block : Func.Blocks) {
+    if (Block.Weight > 0)
+      HasSamples = true;
+    Block.Flow = Block.Weight;
+  }
+  for (FlowJump &Jump : Func.Jumps) {
+    if (Jump.Weight > 0)
+      HasSamples = true;
+    Jump.Flow = Jump.Weight;
+  }
+
+  // Quit early for functions with a single block or ones w/o samples
+  if (Func.Blocks.size() <= 1 || !HasSamples)
+    return;
+
 #ifndef NDEBUG
   // Verify the input data
   verifyInput(Func);
 #endif
 
   // Create and apply an inference network model
   auto InferenceNetwork = MinCostMaxFlow(Params);
   initializeNetwork(Params, InferenceNetwork, Func);