diff --git a/llvm/include/llvm/Transforms/Utils/SampleProfileInference.h b/llvm/include/llvm/Transforms/Utils/SampleProfileInference.h --- a/llvm/include/llvm/Transforms/Utils/SampleProfileInference.h +++ b/llvm/include/llvm/Transforms/Utils/SampleProfileInference.h @@ -77,6 +77,36 @@ uint64_t Entry; }; +/// Various thresholds and options controlling the behavior of the profile +/// inference algorithm. Default values are tuned for several large-scale +/// applications, and can be modified via corresponding command-line flags. +struct ProfiParams { + /// Evenly distribute flow when there are multiple equally likely options. + bool EvenFlowDistribution = true; + + /// Maximum number of dfs iterations for even flow distribution. + unsigned MaxDfsCalls = 10; + + /// A cost of increasing a block's count by one. + unsigned CostInc = 10; + + /// A cost of decreasing a block's count by one. + unsigned CostDec = 20; + + /// A cost of increasing a count of zero-weight block by one. + unsigned CostIncZero = 11; + + /// A cost of increasing the entry block's count by one. + unsigned CostIncEntry = 40; + + /// A cost of decreasing the entry block's count by one. + unsigned CostDecEntry = 10; + + /// A cost of taking an unlikely jump. + int64_t CostUnlikely = ((int64_t)1) << 30; +}; + +void applyFlowInference(const ProfiParams &Params, FlowFunction &Func); void applyFlowInference(FlowFunction &Func); /// Sample profile inference pass. diff --git a/llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h b/llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h --- a/llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h +++ b/llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h @@ -76,7 +76,6 @@ } // end namespace afdo_detail extern cl::opt SampleProfileUseProfi; -extern cl::opt SampleProfileInferEntryCount; template class SampleProfileLoaderBaseImpl { public: @@ -922,8 +921,7 @@ if (SampleProfileUseProfi) { const BasicBlockT *EntryBB = getEntryBB(&F); ErrorOr EntryWeight = getBlockWeight(EntryBB); - if (BlockWeights[EntryBB] > 0 && - (SampleProfileInferEntryCount || !EntryWeight)) { + if (BlockWeights[EntryBB] > 0) { getFunction(F).setEntryCount( ProfileCount(BlockWeights[EntryBB], Function::PCT_Real), &InlinedGUIDs); diff --git a/llvm/lib/Transforms/Utils/SampleProfileInference.cpp b/llvm/lib/Transforms/Utils/SampleProfileInference.cpp --- a/llvm/lib/Transforms/Utils/SampleProfileInference.cpp +++ b/llvm/lib/Transforms/Utils/SampleProfileInference.cpp @@ -26,9 +26,9 @@ namespace { -static cl::opt SampleProfileEvenCountDistribution( - "sample-profile-even-count-distribution", cl::init(true), cl::Hidden, - cl::desc("Try to evenly distribute counts when there are multiple equally " +static cl::opt SampleProfileEvenFlowDistribution( + "sample-profile-even-flow-distribution", cl::init(true), cl::Hidden, + cl::desc("Try to evenly distribute flow when there are multiple equally " "likely options.")); static cl::opt SampleProfileMaxDfsCalls( @@ -76,6 +76,8 @@ /// minimum total cost respecting the given edge capacities. class MinCostMaxFlow { public: + MinCostMaxFlow(const ProfiParams &Params) : Params(Params) {} + // Initialize algorithm's data structures for a network of a given size. void initialize(uint64_t NodeCount, uint64_t SourceNode, uint64_t SinkNode) { Source = SourceNode; @@ -83,7 +85,7 @@ Nodes = std::vector(NodeCount); Edges = std::vector>(NodeCount, std::vector()); - if (SampleProfileEvenCountDistribution) + if (Params.EvenFlowDistribution) AugmentingEdges = std::vector>(NodeCount, std::vector()); } @@ -166,11 +168,6 @@ return Flow; } - /// 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. @@ -180,7 +177,7 @@ uint64_t PathCapacity = computeAugmentingPathCapacity(); while (PathCapacity > 0) { bool Progress = false; - if (SampleProfileEvenCountDistribution) { + if (Params.EvenFlowDistribution) { // Identify node/edge candidates for augmentation identifyShortestEdges(PathCapacity); @@ -253,7 +250,7 @@ // from Source to Target; it follows from inequalities // Dist[Source, Target] >= Dist[Source, V] + Dist[V, Target] // >= Dist[Source, V] - if (!SampleProfileEvenCountDistribution && Nodes[Target].Distance == 0) + if (!Params.EvenFlowDistribution && Nodes[Target].Distance == 0) break; if (Nodes[Src].Distance > Nodes[Target].Distance) continue; @@ -342,7 +339,7 @@ if (Edge.OnShortestPath) { // If we haven't seen Edge.Dst so far, continue DFS search there - if (Dst.Discovery == 0 && Dst.NumCalls < SampleProfileMaxDfsCalls) { + if (Dst.Discovery == 0 && Dst.NumCalls < Params.MaxDfsCalls) { Dst.Discovery = ++Time; Stack.emplace(Edge.Dst, 0); Dst.NumCalls++; @@ -566,6 +563,8 @@ uint64_t Target; /// Augmenting edges. std::vector> AugmentingEdges; + /// Params for flow computation. + const ProfiParams &Params; }; /// A post-processing adjustment of control flow. It applies two steps by @@ -586,7 +585,8 @@ /// class FlowAdjuster { public: - FlowAdjuster(FlowFunction &Func) : Func(Func) { + FlowAdjuster(const ProfiParams &Params, FlowFunction &Func) + : Params(Params), Func(Func) { assert(Func.Blocks[Func.Entry].isEntry() && "incorrect index of the entry block"); } @@ -736,12 +736,13 @@ /// To capture this objective with integer distances, we round off fractional /// parts to a multiple of 1 / BaseDistance. int64_t jumpDistance(FlowJump *Jump) const { + if (Jump->IsUnlikely) + return Params.CostUnlikely; + uint64_t BaseDistance = - std::max(MinCostMaxFlow::MinBaseDistance, + std::max(FlowAdjuster::MinBaseDistance, std::min(Func.Blocks[Func.Entry].Flow, - MinCostMaxFlow::AuxCostUnlikely / NumBlocks())); - if (Jump->IsUnlikely) - return MinCostMaxFlow::AuxCostUnlikely; + Params.CostUnlikely / NumBlocks())); if (Jump->Flow > 0) return BaseDistance + BaseDistance / Jump->Flow; return BaseDistance * NumBlocks(); @@ -1019,7 +1020,11 @@ /// A constant indicating an arbitrary exit block of a function. static constexpr uint64_t AnyExitBlock = uint64_t(-1); + /// Minimum BaseDistance for the jump distance values in island joining. + static constexpr uint64_t MinBaseDistance = 10000; + /// Params for flow computation. + const ProfiParams &Params; /// The function. FlowFunction &Func; }; @@ -1029,7 +1034,8 @@ /// Every block is split into three nodes that are responsible for (i) an /// incoming flow, (ii) an outgoing flow, and (iii) penalizing an increase or /// reduction of the block weight. -void initializeNetwork(MinCostMaxFlow &Network, FlowFunction &Func) { +void initializeNetwork(const ProfiParams &Params, MinCostMaxFlow &Network, + FlowFunction &Func) { uint64_t NumBlocks = Func.Blocks.size(); assert(NumBlocks > 1 && "Too few blocks in a function"); LLVM_DEBUG(dbgs() << "Initializing profi for " << NumBlocks << " blocks\n"); @@ -1076,8 +1082,8 @@ // 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 = SampleProfileProfiCostInc; - int64_t AuxCostDec = SampleProfileProfiCostDec; + int64_t AuxCostInc = Params.CostInc; + int64_t AuxCostDec = Params.CostDec; if (Block.UnknownWeight) { // Do not penalize changing weights of blocks w/o known profile count AuxCostInc = 0; @@ -1086,12 +1092,12 @@ // Increasing the count for "cold" blocks with zero initial count is more // expensive than for "hot" ones if (Block.Weight == 0) { - AuxCostInc = SampleProfileProfiCostIncZero; + AuxCostInc = Params.CostIncZero; } // Modifying the count of the entry block is expensive if (Block.isEntry()) { - AuxCostInc = SampleProfileProfiCostIncEntry; - AuxCostDec = SampleProfileProfiCostDecEntry; + AuxCostInc = Params.CostIncEntry; + AuxCostDec = Params.CostDecEntry; } } // For blocks with self-edges, do not penalize a reduction of the count, @@ -1115,7 +1121,7 @@ if (Src != Dst) { uint64_t SrcOut = 3 * Src + 1; uint64_t DstIn = 3 * Dst; - uint64_t Cost = Jump.IsUnlikely ? MinCostMaxFlow::AuxCostUnlikely : 0; + uint64_t Cost = Jump.IsUnlikely ? Params.CostUnlikely : 0; Network.addEdge(SrcOut, DstIn, Cost); } } @@ -1232,17 +1238,17 @@ } // end of anonymous namespace /// Apply the profile inference algorithm for a given flow function -void llvm::applyFlowInference(FlowFunction &Func) { +void llvm::applyFlowInference(const ProfiParams &Params, FlowFunction &Func) { // Create and apply an inference network model - auto InferenceNetwork = MinCostMaxFlow(); - initializeNetwork(InferenceNetwork, Func); + auto InferenceNetwork = MinCostMaxFlow(Params); + initializeNetwork(Params, InferenceNetwork, Func); InferenceNetwork.run(); // Extract flow values for every block and every edge extractWeights(InferenceNetwork, Func); // Post-processing adjustments to the flow - auto Adjuster = FlowAdjuster(Func); + auto Adjuster = FlowAdjuster(Params, Func); Adjuster.run(); #ifndef NDEBUG @@ -1250,3 +1256,18 @@ verifyWeights(Func); #endif } + +/// Apply the profile inference algorithm for a given flow function +void llvm::applyFlowInference(FlowFunction &Func) { + ProfiParams Params; + // Set the params from the command-line flags. + Params.EvenFlowDistribution = SampleProfileEvenFlowDistribution; + Params.MaxDfsCalls = SampleProfileMaxDfsCalls; + Params.CostInc = SampleProfileProfiCostInc; + Params.CostDec = SampleProfileProfiCostDec; + Params.CostIncZero = SampleProfileProfiCostIncZero; + Params.CostIncEntry = SampleProfileProfiCostIncEntry; + Params.CostDecEntry = SampleProfileProfiCostDecEntry; + + applyFlowInference(Params, Func); +} diff --git a/llvm/lib/Transforms/Utils/SampleProfileLoaderBaseUtil.cpp b/llvm/lib/Transforms/Utils/SampleProfileLoaderBaseUtil.cpp --- a/llvm/lib/Transforms/Utils/SampleProfileLoaderBaseUtil.cpp +++ b/llvm/lib/Transforms/Utils/SampleProfileLoaderBaseUtil.cpp @@ -42,10 +42,6 @@ "sample-profile-use-profi", cl::Hidden, cl::desc("Use profi to infer block and edge counts.")); -cl::opt SampleProfileInferEntryCount( - "sample-profile-infer-entry-count", cl::init(true), cl::Hidden, - cl::desc("Use profi to infer function entry count.")); - namespace sampleprofutil { /// Return true if the given callsite is hot wrt to hot cutoff threshold.