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
21namespace llvm {
22
23struct FlowJump;
24
25/// A wrapper of a binary basic block.
26struct 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.
43struct 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.
53struct 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.
65struct 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
115void applyFlowInference(const ProfiParams &Params, FlowFunction &Func);
116void applyFlowInference(FlowFunction &Func);
117
118/// Sample profile inference pass.
119template <typename FT> class SampleProfileInference {
120public:
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
137private:
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
162template <typename BT>
163void 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
241template <typename BT>
242FlowFunction 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
300template <typename BT>
301inline void SampleProfileInference<BT>::findUnlikelyJumps(
302 const std::vector<const BasicBlockT *> &BasicBlocks,
303 BlockEdgeMap &Successors, FlowFunction &Func) {}
304
305template <typename BT>
306inline 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

source code of llvm/include/llvm/Transforms/Utils/SampleProfileInference.h