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 = std::remove_pointer_t<NodeRef>; |
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: &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(n: BasicBlocks.size()); |
247 | // Create FlowBlocks |
248 | for (const auto *BB : BasicBlocks) { |
249 | FlowBlock Block; |
250 | if (SampleBlockWeights.contains(BB)) { |
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(x: 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(x: 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(x: &Jump); |
275 | Func.Blocks[Dst].PredJumps.push_back(x: &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 | |