1 //===- Transforms/Utils/SampleProfileInference.h ----------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// This file provides the interface for the profile inference algorithm, profi.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
15 #define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
16 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/DepthFirstIterator.h"
19 #include "llvm/ADT/SmallVector.h"
20 
21 namespace llvm {
22 
23 struct FlowJump;
24 
25 /// A wrapper of a binary basic block.
26 struct FlowBlock {
27   uint64_t Index;
28   uint64_t Weight{0};
29   bool HasUnknownWeight{true};
30   bool IsUnlikely{false};
31   uint64_t Flow{0};
32   std::vector<FlowJump *> SuccJumps;
33   std::vector<FlowJump *> PredJumps;
34 
35   /// Check if it is the entry block in the function.
36   bool isEntry() const { return PredJumps.empty(); }
37 
38   /// Check if it is an exit block in the function.
39   bool isExit() const { return SuccJumps.empty(); }
40 };
41 
42 /// A wrapper of a jump between two basic blocks.
43 struct FlowJump {
44   uint64_t Source;
45   uint64_t Target;
46   uint64_t Weight{0};
47   bool HasUnknownWeight{true};
48   bool IsUnlikely{false};
49   uint64_t Flow{0};
50 };
51 
52 /// A wrapper of binary function with basic blocks and jumps.
53 struct FlowFunction {
54   /// Basic blocks in the function.
55   std::vector<FlowBlock> Blocks;
56   /// Jumps between the basic blocks.
57   std::vector<FlowJump> Jumps;
58   /// The index of the entry block.
59   uint64_t Entry{0};
60 };
61 
62 /// Various thresholds and options controlling the behavior of the profile
63 /// inference algorithm. Default values are tuned for several large-scale
64 /// applications, and can be modified via corresponding command-line flags.
65 struct ProfiParams {
66   /// Evenly distribute flow when there are multiple equally likely options.
67   bool EvenFlowDistribution{false};
68 
69   /// Evenly re-distribute flow among unknown subgraphs.
70   bool RebalanceUnknown{false};
71 
72   /// Join isolated components having positive flow.
73   bool JoinIslands{false};
74 
75   /// The cost of increasing a block's count by one.
76   unsigned CostBlockInc{0};
77 
78   /// The cost of decreasing a block's count by one.
79   unsigned CostBlockDec{0};
80 
81   /// The cost of increasing a count of zero-weight block by one.
82   unsigned CostBlockZeroInc{0};
83 
84   /// The cost of increasing the entry block's count by one.
85   unsigned CostBlockEntryInc{0};
86 
87   /// The cost of decreasing the entry block's count by one.
88   unsigned CostBlockEntryDec{0};
89 
90   /// The cost of increasing an unknown block's count by one.
91   unsigned CostBlockUnknownInc{0};
92 
93   /// The cost of increasing a jump's count by one.
94   unsigned CostJumpInc{0};
95 
96   /// The cost of increasing a fall-through jump's count by one.
97   unsigned CostJumpFTInc{0};
98 
99   /// The cost of decreasing a jump's count by one.
100   unsigned CostJumpDec{0};
101 
102   /// The cost of decreasing a fall-through jump's count by one.
103   unsigned CostJumpFTDec{0};
104 
105   /// The cost of increasing an unknown jump's count by one.
106   unsigned CostJumpUnknownInc{0};
107 
108   /// The cost of increasing an unknown fall-through jump's count by one.
109   unsigned CostJumpUnknownFTInc{0};
110 
111   /// The cost of taking an unlikely block/jump.
112   const int64_t CostUnlikely = ((int64_t)1) << 30;
113 };
114 
115 void applyFlowInference(const ProfiParams &Params, FlowFunction &Func);
116 void applyFlowInference(FlowFunction &Func);
117 
118 /// Sample profile inference pass.
119 template <typename FT> class SampleProfileInference {
120 public:
121   using NodeRef = typename GraphTraits<FT *>::NodeRef;
122   using BasicBlockT = typename std::remove_pointer<NodeRef>::type;
123   using FunctionT = FT;
124   using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
125   using BlockWeightMap = DenseMap<const BasicBlockT *, uint64_t>;
126   using EdgeWeightMap = DenseMap<Edge, uint64_t>;
127   using BlockEdgeMap =
128       DenseMap<const BasicBlockT *, SmallVector<const BasicBlockT *, 8>>;
129 
130   SampleProfileInference(FunctionT &F, BlockEdgeMap &Successors,
131                          BlockWeightMap &SampleBlockWeights)
132       : F(F), Successors(Successors), SampleBlockWeights(SampleBlockWeights) {}
133 
134   /// Apply the profile inference algorithm for a given function
135   void apply(BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights);
136 
137 private:
138   /// Initialize flow function blocks, jumps and misc metadata.
139   FlowFunction
140   createFlowFunction(const std::vector<const BasicBlockT *> &BasicBlocks,
141                      DenseMap<const BasicBlockT *, uint64_t> &BlockIndex);
142 
143   /// Try to infer branch probabilities mimicking implementation of
144   /// BranchProbabilityInfo. Unlikely taken branches are marked so that the
145   /// inference algorithm can avoid sending flow along corresponding edges.
146   void findUnlikelyJumps(const std::vector<const BasicBlockT *> &BasicBlocks,
147                          BlockEdgeMap &Successors, FlowFunction &Func);
148 
149   /// Determine whether the block is an exit in the CFG.
150   bool isExit(const BasicBlockT *BB);
151 
152   /// Function.
153   const FunctionT &F;
154 
155   /// Successors for each basic block in the CFG.
156   BlockEdgeMap &Successors;
157 
158   /// Map basic blocks to their sampled weights.
159   BlockWeightMap &SampleBlockWeights;
160 };
161 
162 template <typename BT>
163 void SampleProfileInference<BT>::apply(BlockWeightMap &BlockWeights,
164                                        EdgeWeightMap &EdgeWeights) {
165   // Find all forwards reachable blocks which the inference algorithm will be
166   // applied on.
167   df_iterator_default_set<const BasicBlockT *> Reachable;
168   for (auto *BB : depth_first_ext(&F, Reachable))
169     (void)BB /* Mark all reachable blocks */;
170 
171   // Find all backwards reachable blocks which the inference algorithm will be
172   // applied on.
173   df_iterator_default_set<const BasicBlockT *> InverseReachable;
174   for (const auto &BB : F) {
175     // An exit block is a block without any successors.
176     if (isExit(&BB)) {
177       for (auto *RBB : inverse_depth_first_ext(&BB, InverseReachable))
178         (void)RBB;
179     }
180   }
181 
182   // Keep a stable order for reachable blocks
183   DenseMap<const BasicBlockT *, uint64_t> BlockIndex;
184   std::vector<const BasicBlockT *> BasicBlocks;
185   BlockIndex.reserve(Reachable.size());
186   BasicBlocks.reserve(Reachable.size());
187   for (const auto &BB : F) {
188     if (Reachable.count(&BB) && InverseReachable.count(&BB)) {
189       BlockIndex[&BB] = BasicBlocks.size();
190       BasicBlocks.push_back(&BB);
191     }
192   }
193 
194   BlockWeights.clear();
195   EdgeWeights.clear();
196   bool HasSamples = false;
197   for (const auto *BB : BasicBlocks) {
198     auto It = SampleBlockWeights.find(BB);
199     if (It != SampleBlockWeights.end() && It->second > 0) {
200       HasSamples = true;
201       BlockWeights[BB] = It->second;
202     }
203   }
204   // Quit early for functions with a single block or ones w/o samples
205   if (BasicBlocks.size() <= 1 || !HasSamples) {
206     return;
207   }
208 
209   // Create necessary objects
210   FlowFunction Func = createFlowFunction(BasicBlocks, BlockIndex);
211 
212   // Create and apply the inference network model.
213   applyFlowInference(Func);
214 
215   // Extract the resulting weights from the control flow
216   // All weights are increased by one to avoid propagation errors introduced by
217   // zero weights.
218   for (const auto *BB : BasicBlocks) {
219     BlockWeights[BB] = Func.Blocks[BlockIndex[BB]].Flow;
220   }
221   for (auto &Jump : Func.Jumps) {
222     Edge E = std::make_pair(BasicBlocks[Jump.Source], BasicBlocks[Jump.Target]);
223     EdgeWeights[E] = Jump.Flow;
224   }
225 
226 #ifndef NDEBUG
227   // Unreachable blocks and edges should not have a weight.
228   for (auto &I : BlockWeights) {
229     assert(Reachable.contains(I.first));
230     assert(InverseReachable.contains(I.first));
231   }
232   for (auto &I : EdgeWeights) {
233     assert(Reachable.contains(I.first.first) &&
234            Reachable.contains(I.first.second));
235     assert(InverseReachable.contains(I.first.first) &&
236            InverseReachable.contains(I.first.second));
237   }
238 #endif
239 }
240 
241 template <typename BT>
242 FlowFunction SampleProfileInference<BT>::createFlowFunction(
243     const std::vector<const BasicBlockT *> &BasicBlocks,
244     DenseMap<const BasicBlockT *, uint64_t> &BlockIndex) {
245   FlowFunction Func;
246   Func.Blocks.reserve(BasicBlocks.size());
247   // Create FlowBlocks
248   for (const auto *BB : BasicBlocks) {
249     FlowBlock Block;
250     if (SampleBlockWeights.find(BB) != SampleBlockWeights.end()) {
251       Block.HasUnknownWeight = false;
252       Block.Weight = SampleBlockWeights[BB];
253     } else {
254       Block.HasUnknownWeight = true;
255       Block.Weight = 0;
256     }
257     Block.Index = Func.Blocks.size();
258     Func.Blocks.push_back(Block);
259   }
260   // Create FlowEdges
261   for (const auto *BB : BasicBlocks) {
262     for (auto *Succ : Successors[BB]) {
263       if (!BlockIndex.count(Succ))
264         continue;
265       FlowJump Jump;
266       Jump.Source = BlockIndex[BB];
267       Jump.Target = BlockIndex[Succ];
268       Func.Jumps.push_back(Jump);
269     }
270   }
271   for (auto &Jump : Func.Jumps) {
272     uint64_t Src = Jump.Source;
273     uint64_t Dst = Jump.Target;
274     Func.Blocks[Src].SuccJumps.push_back(&Jump);
275     Func.Blocks[Dst].PredJumps.push_back(&Jump);
276   }
277 
278   // Try to infer probabilities of jumps based on the content of basic block
279   findUnlikelyJumps(BasicBlocks, Successors, Func);
280 
281   // Find the entry block
282   for (size_t I = 0; I < Func.Blocks.size(); I++) {
283     if (Func.Blocks[I].isEntry()) {
284       Func.Entry = I;
285       break;
286     }
287   }
288   assert(Func.Entry == 0 && "incorrect index of the entry block");
289 
290   // Pre-process data: make sure the entry weight is at least 1
291   auto &EntryBlock = Func.Blocks[Func.Entry];
292   if (EntryBlock.Weight == 0 && !EntryBlock.HasUnknownWeight) {
293     EntryBlock.Weight = 1;
294     EntryBlock.HasUnknownWeight = false;
295   }
296 
297   return Func;
298 }
299 
300 template <typename BT>
301 inline void SampleProfileInference<BT>::findUnlikelyJumps(
302     const std::vector<const BasicBlockT *> &BasicBlocks,
303     BlockEdgeMap &Successors, FlowFunction &Func) {}
304 
305 template <typename BT>
306 inline bool SampleProfileInference<BT>::isExit(const BasicBlockT *BB) {
307   return BB->succ_empty();
308 }
309 
310 } // end namespace llvm
311 #endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILEINFERENCE_H
312