introducing profi flags

[spupyrev]

Summary

There are two changes in the diff:

• adding cmd options for profi weights, so we can experiment/tune different combinations; default values stay the same so this does not impact results;

• modifying the jump distance in FlowAdjuster.

The former doesn't change the logic but simplifies flag tuning. The latter is useful for "large" profile datasets; the older version works well only for smaller binaries from the SPEC dataset but has scaling issues with larger datasets

[spupyrev]

modifying island connectors + removed one (controversial) option

[wenlei]

llvm/lib/Transforms/Utils/SampleProfileInference.cpp

744–746

Could you explain this a bit more, how does this minimizes total multiplicative Flow increase for the remaining edges?

[hoy]

llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h

923

Remove this since it's not used anywhere?

llvm/lib/Transforms/Utils/SampleProfileInference.cpp

744–746

Same question here. Looks like we are turning the previous subtraction into a division. So it's not a linear reduction anymore. For edges with smaller flow, the cost now will be much larger than previously, which would prevent adding more flow to that edge?

[spupyrev]

added back the option for overwriting entry count (ON by default)

[hoy]

llvm/lib/Transforms/Utils/SampleProfileLoaderBaseUtil.cpp

46 ↗

(On Diff #413800)

Will there be a separate change to flip the default value?

[spupyrev]

llvm/lib/Transforms/Utils/SampleProfileLoaderBaseUtil.cpp

46 ↗

(On Diff #413800)

I suggest we keep it as is and test on a couple of prod binaries. If confirmed, we may change the default value

[hoy]

llvm/lib/Transforms/Utils/SampleProfileLoaderBaseUtil.cpp

46 ↗

(On Diff #413800)

sgtm, thanks.

llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h

void SampleProfileLoaderBaseImpl<BT>::finalizeWeightPropagation(
   // If we utilize a flow-based count inference, then we trust the computed
   // counts and set the entry count as computed by the algorithm. This is
   // primarily done to sync the counts produced by profi and BFI inference,
   // which uses the entry count for mass propagation.
   // If profi produces a zero-value for the entry count, we fallback to
   // Samples->getHeadSamples() + 1 to avoid functions with zero count.
   if (SampleProfileUseProfi) {
     const BasicBlockT *EntryBB = getEntryBB(&F);
+    ErrorOr<uint64_t> EntryWeight = getBlockWeight(EntryBB);
     if (BlockWeights[EntryBB] > 0) {
       getFunction(F).setEntryCount(
           ProfileCount(BlockWeights[EntryBB], Function::PCT_Real),
           &InlinedGUIDs);
     }
   }
 }
 

llvm/lib/Transforms/Utils/SampleProfileInference.cpp

static cl::opt<bool> SampleProfileEvenCountDistribution(
     cl::ZeroOrMore,
     cl::desc("Try to evenly distribute counts when there are multiple equally "
              "likely options."));
 
 static cl::opt<unsigned> SampleProfileMaxDfsCalls(
     "sample-profile-max-dfs-calls", cl::init(10), cl::Hidden, cl::ZeroOrMore,
     cl::desc("Maximum number of dfs iterations for even count distribution."));
 
+static cl::opt<unsigned> SampleProfileProfiCostInc(
+    "sample-profile-profi-cost-inc", cl::init(10), cl::Hidden, cl::ZeroOrMore,
+    cl::desc("A cost of increasing a block's count by one."));
+
+static cl::opt<unsigned> SampleProfileProfiCostDec(
+    "sample-profile-profi-cost-dec", cl::init(20), cl::Hidden, cl::ZeroOrMore,
+    cl::desc("A cost of decreasing a block's count by one."));
+
+static cl::opt<unsigned> SampleProfileProfiCostIncZero(
+    "sample-profile-profi-cost-inc-zero", cl::init(11), cl::Hidden,
+    cl::ZeroOrMore,
+    cl::desc("A cost of increasing a count of zero-weight block by one."));
+
+static cl::opt<unsigned> SampleProfileProfiCostIncEntry(
+    "sample-profile-profi-cost-inc-entry", cl::init(40), cl::Hidden,
+    cl::ZeroOrMore,
+    cl::desc("A cost of increasing the entry block's count by one."));
+
+static cl::opt<unsigned> SampleProfileProfiCostDecEntry(
+    "sample-profile-profi-cost-dec-entry", cl::init(10), cl::Hidden,
+    cl::ZeroOrMore,
+    cl::desc("A cost of decreasing the entry block's count by one."));
+
 /// A value indicating an infinite flow/capacity/weight of a block/edge.
 /// Not using numeric_limits<int64_t>::max(), as the values can be summed up
 /// during the execution.
 static constexpr int64_t INF = ((int64_t)1) << 50;
 
 /// The minimum-cost maximum flow algorithm.
 ///
 /// The algorithm finds the maximum flow of minimum cost on a given (directed)
int64_t getFlow(uint64_t Src, uint64_t Dst) const {
     for (auto &Edge : Edges[Src]) {
       if (Edge.Dst == Dst) {
         Flow += Edge.Flow;
       }
     }
     return Flow;
   }
 
-  /// A cost of increasing a block's count by one.
-  static constexpr int64_t AuxCostInc = 10;
-  /// A cost of decreasing a block's count by one.
-  static constexpr int64_t AuxCostDec = 20;
-  /// A cost of increasing a count of zero-weight block by one.
-  static constexpr int64_t AuxCostIncZero = 11;
-  /// A cost of increasing the entry block's count by one.
-  static constexpr int64_t AuxCostIncEntry = 40;
-  /// A cost of decreasing the entry block's count by one.
-  static constexpr int64_t AuxCostDecEntry = 10;
   /// A cost of taking an unlikely jump.
   static constexpr int64_t AuxCostUnlikely = ((int64_t)1) << 30;
+  /// Minimum BaseDistance for the jump distance values in island joining.
+  static constexpr uint64_t MinBaseDistance = 10000;
 
 private:
   /// Iteratively find an augmentation path/dag in the network and send the
   /// flow along its edges. The method returns the number of applied iterations.
   size_t applyFlowAugmentation() {
     size_t AugmentationIters = 0;
     while (findAugmentingPath()) {
       uint64_t PathCapacity = computeAugmentingPathCapacity();
std::vector<FlowJump *> findShortestPath(uint64_t Source, uint64_t Target) {
     // Reverse the path, since it is extracted from Target to Source
     std::reverse(Result.begin(), Result.end());
     return Result;
   }
 
   /// A distance of a path for a given jump.
   /// In order to incite the path to use blocks/jumps with large positive flow,
   /// and avoid changing branch probability of outgoing edges drastically,
-  /// set the distance as follows:
-  ///   if Jump.Flow > 0, then distance = max(100 - Jump->Flow, 0)
-  ///   if Block.Weight > 0, then distance = 1
-  ///   otherwise distance >> 1
+  /// set the jump distance so as:
+  ///   - to minimize the number of unlikely jumps used and subject to that,
+  ///   - to minimize the number of Flow == 0 jumps used and subject to that,
+  ///   - minimizes total multiplicative Flow increase for the remaining edges.
+  /// To capture this objective with integer distances, we round off fractional
+  /// parts to a multiple of 1 / BaseDistance.
   int64_t jumpDistance(FlowJump *Jump) const {
-    int64_t BaseDistance = 100;
+    uint64_t BaseDistance =
+        std::max(MinCostMaxFlow::MinBaseDistance,
+                 std::min(Func.Blocks[Func.Entry].Flow,
+                          MinCostMaxFlow::AuxCostUnlikely / (NumBlocks() + 1)));
     if (Jump->IsUnlikely)
       return MinCostMaxFlow::AuxCostUnlikely;
     if (Jump->Flow > 0)
-      return std::max(BaseDistance - (int64_t)Jump->Flow, (int64_t)0);
-    if (Func.Blocks[Jump->Target].Weight > 0)
-      return BaseDistance;
+      return BaseDistance + BaseDistance / Jump->Flow;
     return BaseDistance * (NumBlocks() + 1);
   };
 
   uint64_t NumBlocks() const { return Func.Blocks.size(); }
 
   /// Rebalance unknown subgraphs so that the flow is split evenly across the
   /// outgoing branches of every block of the subgraph. The method iterates over
   /// blocks with known weight and identifies unknown subgraphs rooted at the
for (uint64_t B = 0; B < NumBlocks; B++) {
     } else if (Block.isExit()) {
       Network.addEdge(Bout, T, 0);
     }
 
     // An auxiliary node to allow increase/reduction of block counts:
     // We assume that decreasing block counts is more expensive than increasing,
     // and thus, setting separate costs here. In the future we may want to tune
     // the relative costs so as to maximize the quality of generated profiles.
-    int64_t AuxCostInc = MinCostMaxFlow::AuxCostInc;
-    int64_t AuxCostDec = MinCostMaxFlow::AuxCostDec;
+    int64_t AuxCostInc = SampleProfileProfiCostInc;
+    int64_t AuxCostDec = SampleProfileProfiCostDec;
     if (Block.UnknownWeight) {
       // Do not penalize changing weights of blocks w/o known profile count
       AuxCostInc = 0;
       AuxCostDec = 0;
     } else {
       // Increasing the count for "cold" blocks with zero initial count is more
       // expensive than for "hot" ones
       if (Block.Weight == 0) {
-        AuxCostInc = MinCostMaxFlow::AuxCostIncZero;
+        AuxCostInc = SampleProfileProfiCostIncZero;
       }
       // Modifying the count of the entry block is expensive
       if (Block.isEntry()) {
-        AuxCostInc = MinCostMaxFlow::AuxCostIncEntry;
-        AuxCostDec = MinCostMaxFlow::AuxCostDecEntry;
+        AuxCostInc = SampleProfileProfiCostIncEntry;
+        AuxCostDec = SampleProfileProfiCostDecEntry;
       }
     }
     // For blocks with self-edges, do not penalize a reduction of the count,
     // as all of the increase can be attributed to the self-edge
     if (Block.HasSelfEdge) {
       AuxCostDec = 0;
     }