1 | ////===- SampleProfileLoadBaseImpl.h - Profile loader base impl --*- 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 sampled PGO profile loader base |
11 | /// implementation. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H |
16 | #define LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H |
17 | |
18 | #include "llvm/ADT/ArrayRef.h" |
19 | #include "llvm/ADT/DenseMap.h" |
20 | #include "llvm/ADT/DenseSet.h" |
21 | #include "llvm/ADT/IntrusiveRefCntPtr.h" |
22 | #include "llvm/ADT/SmallPtrSet.h" |
23 | #include "llvm/ADT/SmallSet.h" |
24 | #include "llvm/ADT/SmallVector.h" |
25 | #include "llvm/Analysis/LoopInfo.h" |
26 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
27 | #include "llvm/Analysis/PostDominators.h" |
28 | #include "llvm/IR/BasicBlock.h" |
29 | #include "llvm/IR/CFG.h" |
30 | #include "llvm/IR/DebugInfoMetadata.h" |
31 | #include "llvm/IR/DebugLoc.h" |
32 | #include "llvm/IR/Dominators.h" |
33 | #include "llvm/IR/Function.h" |
34 | #include "llvm/IR/Instruction.h" |
35 | #include "llvm/IR/Instructions.h" |
36 | #include "llvm/IR/Module.h" |
37 | #include "llvm/IR/PseudoProbe.h" |
38 | #include "llvm/ProfileData/SampleProf.h" |
39 | #include "llvm/ProfileData/SampleProfReader.h" |
40 | #include "llvm/Support/CommandLine.h" |
41 | #include "llvm/Support/GenericDomTree.h" |
42 | #include "llvm/Support/raw_ostream.h" |
43 | #include "llvm/Transforms/Utils/SampleProfileInference.h" |
44 | #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h" |
45 | |
46 | namespace llvm { |
47 | using namespace sampleprof; |
48 | using namespace sampleprofutil; |
49 | using ProfileCount = Function::ProfileCount; |
50 | |
51 | namespace vfs { |
52 | class FileSystem; |
53 | } // namespace vfs |
54 | |
55 | #define DEBUG_TYPE "sample-profile-impl" |
56 | |
57 | namespace afdo_detail { |
58 | |
59 | template <typename BlockT> struct IRTraits; |
60 | template <> struct IRTraits<BasicBlock> { |
61 | using InstructionT = Instruction; |
62 | using BasicBlockT = BasicBlock; |
63 | using FunctionT = Function; |
64 | using BlockFrequencyInfoT = BlockFrequencyInfo; |
65 | using LoopT = Loop; |
66 | using LoopInfoPtrT = std::unique_ptr<LoopInfo>; |
67 | using DominatorTreePtrT = std::unique_ptr<DominatorTree>; |
68 | using PostDominatorTreeT = PostDominatorTree; |
69 | using PostDominatorTreePtrT = std::unique_ptr<PostDominatorTree>; |
70 | using = OptimizationRemarkEmitter; |
71 | using = OptimizationRemarkAnalysis; |
72 | using PredRangeT = pred_range; |
73 | using SuccRangeT = succ_range; |
74 | static Function &getFunction(Function &F) { return F; } |
75 | static const BasicBlock *getEntryBB(const Function *F) { |
76 | return &F->getEntryBlock(); |
77 | } |
78 | static pred_range getPredecessors(BasicBlock *BB) { return predecessors(BB); } |
79 | static succ_range getSuccessors(BasicBlock *BB) { return successors(BB); } |
80 | }; |
81 | |
82 | } // end namespace afdo_detail |
83 | |
84 | // This class serves sample counts correlation for SampleProfileLoader by |
85 | // analyzing pseudo probes and their function descriptors injected by |
86 | // SampleProfileProber. |
87 | class PseudoProbeManager { |
88 | DenseMap<uint64_t, PseudoProbeDescriptor> GUIDToProbeDescMap; |
89 | |
90 | public: |
91 | PseudoProbeManager(const Module &M) { |
92 | if (NamedMDNode *FuncInfo = |
93 | M.getNamedMetadata(Name: PseudoProbeDescMetadataName)) { |
94 | for (const auto *Operand : FuncInfo->operands()) { |
95 | const auto *MD = cast<MDNode>(Val: Operand); |
96 | auto GUID = mdconst::dyn_extract<ConstantInt>(MD: MD->getOperand(I: 0)) |
97 | ->getZExtValue(); |
98 | auto Hash = mdconst::dyn_extract<ConstantInt>(MD: MD->getOperand(I: 1)) |
99 | ->getZExtValue(); |
100 | GUIDToProbeDescMap.try_emplace(Key: GUID, Args: PseudoProbeDescriptor(GUID, Hash)); |
101 | } |
102 | } |
103 | } |
104 | |
105 | const PseudoProbeDescriptor *getDesc(uint64_t GUID) const { |
106 | auto I = GUIDToProbeDescMap.find(Val: GUID); |
107 | return I == GUIDToProbeDescMap.end() ? nullptr : &I->second; |
108 | } |
109 | |
110 | const PseudoProbeDescriptor *getDesc(StringRef FProfileName) const { |
111 | return getDesc(GUID: Function::getGUID(GlobalName: FProfileName)); |
112 | } |
113 | |
114 | const PseudoProbeDescriptor *getDesc(const Function &F) const { |
115 | return getDesc(GUID: Function::getGUID(GlobalName: FunctionSamples::getCanonicalFnName(F))); |
116 | } |
117 | |
118 | bool profileIsHashMismatched(const PseudoProbeDescriptor &FuncDesc, |
119 | const FunctionSamples &Samples) const { |
120 | return FuncDesc.getFunctionHash() != Samples.getFunctionHash(); |
121 | } |
122 | |
123 | bool moduleIsProbed(const Module &M) const { |
124 | return M.getNamedMetadata(Name: PseudoProbeDescMetadataName); |
125 | } |
126 | |
127 | bool profileIsValid(const Function &F, const FunctionSamples &Samples) const { |
128 | const auto *Desc = getDesc(F); |
129 | if (!Desc) { |
130 | LLVM_DEBUG(dbgs() << "Probe descriptor missing for Function " |
131 | << F.getName() << "\n" ); |
132 | return false; |
133 | } |
134 | if (Desc->getFunctionHash() != Samples.getFunctionHash()) { |
135 | LLVM_DEBUG(dbgs() << "Hash mismatch for Function " << F.getName() |
136 | << "\n" ); |
137 | return false; |
138 | } |
139 | return true; |
140 | } |
141 | }; |
142 | |
143 | |
144 | |
145 | extern cl::opt<bool> SampleProfileUseProfi; |
146 | |
147 | template <typename FT> class SampleProfileLoaderBaseImpl { |
148 | public: |
149 | SampleProfileLoaderBaseImpl(std::string Name, std::string RemapName, |
150 | IntrusiveRefCntPtr<vfs::FileSystem> FS) |
151 | : Filename(Name), RemappingFilename(RemapName), FS(std::move(FS)) {} |
152 | void dump() { Reader->dump(); } |
153 | |
154 | using NodeRef = typename GraphTraits<FT *>::NodeRef; |
155 | using BT = std::remove_pointer_t<NodeRef>; |
156 | using InstructionT = typename afdo_detail::IRTraits<BT>::InstructionT; |
157 | using BasicBlockT = typename afdo_detail::IRTraits<BT>::BasicBlockT; |
158 | using BlockFrequencyInfoT = |
159 | typename afdo_detail::IRTraits<BT>::BlockFrequencyInfoT; |
160 | using FunctionT = typename afdo_detail::IRTraits<BT>::FunctionT; |
161 | using LoopT = typename afdo_detail::IRTraits<BT>::LoopT; |
162 | using LoopInfoPtrT = typename afdo_detail::IRTraits<BT>::LoopInfoPtrT; |
163 | using DominatorTreePtrT = |
164 | typename afdo_detail::IRTraits<BT>::DominatorTreePtrT; |
165 | using PostDominatorTreePtrT = |
166 | typename afdo_detail::IRTraits<BT>::PostDominatorTreePtrT; |
167 | using PostDominatorTreeT = |
168 | typename afdo_detail::IRTraits<BT>::PostDominatorTreeT; |
169 | using = |
170 | typename afdo_detail::IRTraits<BT>::OptRemarkEmitterT; |
171 | using = |
172 | typename afdo_detail::IRTraits<BT>::OptRemarkAnalysisT; |
173 | using PredRangeT = typename afdo_detail::IRTraits<BT>::PredRangeT; |
174 | using SuccRangeT = typename afdo_detail::IRTraits<BT>::SuccRangeT; |
175 | |
176 | using BlockWeightMap = DenseMap<const BasicBlockT *, uint64_t>; |
177 | using EquivalenceClassMap = |
178 | DenseMap<const BasicBlockT *, const BasicBlockT *>; |
179 | using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>; |
180 | using EdgeWeightMap = DenseMap<Edge, uint64_t>; |
181 | using BlockEdgeMap = |
182 | DenseMap<const BasicBlockT *, SmallVector<const BasicBlockT *, 8>>; |
183 | |
184 | protected: |
185 | ~SampleProfileLoaderBaseImpl() = default; |
186 | friend class SampleCoverageTracker; |
187 | |
188 | Function &getFunction(FunctionT &F) { |
189 | return afdo_detail::IRTraits<BT>::getFunction(F); |
190 | } |
191 | const BasicBlockT *getEntryBB(const FunctionT *F) { |
192 | return afdo_detail::IRTraits<BT>::getEntryBB(F); |
193 | } |
194 | PredRangeT getPredecessors(BasicBlockT *BB) { |
195 | return afdo_detail::IRTraits<BT>::getPredecessors(BB); |
196 | } |
197 | SuccRangeT getSuccessors(BasicBlockT *BB) { |
198 | return afdo_detail::IRTraits<BT>::getSuccessors(BB); |
199 | } |
200 | |
201 | unsigned getFunctionLoc(FunctionT &Func); |
202 | virtual ErrorOr<uint64_t> getInstWeight(const InstructionT &Inst); |
203 | ErrorOr<uint64_t> getInstWeightImpl(const InstructionT &Inst); |
204 | virtual ErrorOr<uint64_t> getProbeWeight(const InstructionT &Inst); |
205 | ErrorOr<uint64_t> getBlockWeight(const BasicBlockT *BB); |
206 | mutable DenseMap<const DILocation *, const FunctionSamples *> |
207 | DILocation2SampleMap; |
208 | virtual const FunctionSamples * |
209 | findFunctionSamples(const InstructionT &I) const; |
210 | void printEdgeWeight(raw_ostream &OS, Edge E); |
211 | void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const; |
212 | void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB); |
213 | bool computeBlockWeights(FunctionT &F); |
214 | void findEquivalenceClasses(FunctionT &F); |
215 | void findEquivalencesFor(BasicBlockT *BB1, |
216 | ArrayRef<BasicBlockT *> Descendants, |
217 | PostDominatorTreeT *DomTree); |
218 | void propagateWeights(FunctionT &F); |
219 | void applyProfi(FunctionT &F, BlockEdgeMap &Successors, |
220 | BlockWeightMap &SampleBlockWeights, |
221 | BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights); |
222 | uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge); |
223 | void buildEdges(FunctionT &F); |
224 | bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount); |
225 | void clearFunctionData(bool ResetDT = true); |
226 | void computeDominanceAndLoopInfo(FunctionT &F); |
227 | bool |
228 | computeAndPropagateWeights(FunctionT &F, |
229 | const DenseSet<GlobalValue::GUID> &InlinedGUIDs); |
230 | void initWeightPropagation(FunctionT &F, |
231 | const DenseSet<GlobalValue::GUID> &InlinedGUIDs); |
232 | void |
233 | finalizeWeightPropagation(FunctionT &F, |
234 | const DenseSet<GlobalValue::GUID> &InlinedGUIDs); |
235 | void emitCoverageRemarks(FunctionT &F); |
236 | |
237 | /// Map basic blocks to their computed weights. |
238 | /// |
239 | /// The weight of a basic block is defined to be the maximum |
240 | /// of all the instruction weights in that block. |
241 | BlockWeightMap BlockWeights; |
242 | |
243 | /// Map edges to their computed weights. |
244 | /// |
245 | /// Edge weights are computed by propagating basic block weights in |
246 | /// SampleProfile::propagateWeights. |
247 | EdgeWeightMap EdgeWeights; |
248 | |
249 | /// Set of visited blocks during propagation. |
250 | SmallPtrSet<const BasicBlockT *, 32> VisitedBlocks; |
251 | |
252 | /// Set of visited edges during propagation. |
253 | SmallSet<Edge, 32> VisitedEdges; |
254 | |
255 | /// Equivalence classes for block weights. |
256 | /// |
257 | /// Two blocks BB1 and BB2 are in the same equivalence class if they |
258 | /// dominate and post-dominate each other, and they are in the same loop |
259 | /// nest. When this happens, the two blocks are guaranteed to execute |
260 | /// the same number of times. |
261 | EquivalenceClassMap EquivalenceClass; |
262 | |
263 | /// Dominance, post-dominance and loop information. |
264 | DominatorTreePtrT DT; |
265 | PostDominatorTreePtrT PDT; |
266 | LoopInfoPtrT LI; |
267 | |
268 | /// Predecessors for each basic block in the CFG. |
269 | BlockEdgeMap Predecessors; |
270 | |
271 | /// Successors for each basic block in the CFG. |
272 | BlockEdgeMap Successors; |
273 | |
274 | /// Profile coverage tracker. |
275 | SampleCoverageTracker CoverageTracker; |
276 | |
277 | /// Profile reader object. |
278 | std::unique_ptr<SampleProfileReader> Reader; |
279 | |
280 | /// Synthetic samples created by duplicating the samples of inlined functions |
281 | /// from the original profile as if they were top level sample profiles. |
282 | /// Use std::map because insertion may happen while its content is referenced. |
283 | std::map<SampleContext, FunctionSamples> OutlineFunctionSamples; |
284 | |
285 | // A pseudo probe helper to correlate the imported sample counts. |
286 | std::unique_ptr<PseudoProbeManager> ProbeManager; |
287 | |
288 | /// Samples collected for the body of this function. |
289 | FunctionSamples *Samples = nullptr; |
290 | |
291 | /// Name of the profile file to load. |
292 | std::string Filename; |
293 | |
294 | /// Name of the profile remapping file to load. |
295 | std::string RemappingFilename; |
296 | |
297 | /// VirtualFileSystem to load profile files from. |
298 | IntrusiveRefCntPtr<vfs::FileSystem> FS; |
299 | |
300 | /// Profile Summary Info computed from sample profile. |
301 | ProfileSummaryInfo *PSI = nullptr; |
302 | |
303 | /// Optimization Remark Emitter used to emit diagnostic remarks. |
304 | OptRemarkEmitterT *ORE = nullptr; |
305 | }; |
306 | |
307 | /// Clear all the per-function data used to load samples and propagate weights. |
308 | template <typename BT> |
309 | void SampleProfileLoaderBaseImpl<BT>::clearFunctionData(bool ResetDT) { |
310 | BlockWeights.clear(); |
311 | EdgeWeights.clear(); |
312 | VisitedBlocks.clear(); |
313 | VisitedEdges.clear(); |
314 | EquivalenceClass.clear(); |
315 | if (ResetDT) { |
316 | DT = nullptr; |
317 | PDT = nullptr; |
318 | LI = nullptr; |
319 | } |
320 | Predecessors.clear(); |
321 | Successors.clear(); |
322 | CoverageTracker.clear(); |
323 | } |
324 | |
325 | #ifndef NDEBUG |
326 | /// Print the weight of edge \p E on stream \p OS. |
327 | /// |
328 | /// \param OS Stream to emit the output to. |
329 | /// \param E Edge to print. |
330 | template <typename BT> |
331 | void SampleProfileLoaderBaseImpl<BT>::printEdgeWeight(raw_ostream &OS, Edge E) { |
332 | OS << "weight[" << E.first->getName() << "->" << E.second->getName() |
333 | << "]: " << EdgeWeights[E] << "\n" ; |
334 | } |
335 | |
336 | /// Print the equivalence class of block \p BB on stream \p OS. |
337 | /// |
338 | /// \param OS Stream to emit the output to. |
339 | /// \param BB Block to print. |
340 | template <typename BT> |
341 | void SampleProfileLoaderBaseImpl<BT>::printBlockEquivalence( |
342 | raw_ostream &OS, const BasicBlockT *BB) { |
343 | const BasicBlockT *Equiv = EquivalenceClass[BB]; |
344 | OS << "equivalence[" << BB->getName() |
345 | << "]: " << ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE" ) << "\n" ; |
346 | } |
347 | |
348 | /// Print the weight of block \p BB on stream \p OS. |
349 | /// |
350 | /// \param OS Stream to emit the output to. |
351 | /// \param BB Block to print. |
352 | template <typename BT> |
353 | void SampleProfileLoaderBaseImpl<BT>::printBlockWeight( |
354 | raw_ostream &OS, const BasicBlockT *BB) const { |
355 | const auto &I = BlockWeights.find(BB); |
356 | uint64_t W = (I == BlockWeights.end() ? 0 : I->second); |
357 | OS << "weight[" << BB->getName() << "]: " << W << "\n" ; |
358 | } |
359 | #endif |
360 | |
361 | /// Get the weight for an instruction. |
362 | /// |
363 | /// The "weight" of an instruction \p Inst is the number of samples |
364 | /// collected on that instruction at runtime. To retrieve it, we |
365 | /// need to compute the line number of \p Inst relative to the start of its |
366 | /// function. We use HeaderLineno to compute the offset. We then |
367 | /// look up the samples collected for \p Inst using BodySamples. |
368 | /// |
369 | /// \param Inst Instruction to query. |
370 | /// |
371 | /// \returns the weight of \p Inst. |
372 | template <typename BT> |
373 | ErrorOr<uint64_t> |
374 | SampleProfileLoaderBaseImpl<BT>::getInstWeight(const InstructionT &Inst) { |
375 | if (FunctionSamples::ProfileIsProbeBased) |
376 | return getProbeWeight(Inst); |
377 | return getInstWeightImpl(Inst); |
378 | } |
379 | |
380 | template <typename BT> |
381 | ErrorOr<uint64_t> |
382 | SampleProfileLoaderBaseImpl<BT>::getInstWeightImpl(const InstructionT &Inst) { |
383 | const FunctionSamples *FS = findFunctionSamples(I: Inst); |
384 | if (!FS) |
385 | return std::error_code(); |
386 | |
387 | const DebugLoc &DLoc = Inst.getDebugLoc(); |
388 | if (!DLoc) |
389 | return std::error_code(); |
390 | |
391 | const DILocation *DIL = DLoc; |
392 | uint32_t LineOffset = FunctionSamples::getOffset(DIL); |
393 | uint32_t Discriminator; |
394 | if (EnableFSDiscriminator) |
395 | Discriminator = DIL->getDiscriminator(); |
396 | else |
397 | Discriminator = DIL->getBaseDiscriminator(); |
398 | |
399 | ErrorOr<uint64_t> R = FS->findSamplesAt(LineOffset, Discriminator); |
400 | if (R) { |
401 | bool FirstMark = |
402 | CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, Samples: R.get()); |
403 | if (FirstMark) { |
404 | ORE->emit([&]() { |
405 | OptRemarkAnalysisT (DEBUG_TYPE, "AppliedSamples" , &Inst); |
406 | Remark << "Applied " << ore::NV("NumSamples" , *R); |
407 | Remark << " samples from profile (offset: " ; |
408 | Remark << ore::NV("LineOffset" , LineOffset); |
409 | if (Discriminator) { |
410 | Remark << "." ; |
411 | Remark << ore::NV("Discriminator" , Discriminator); |
412 | } |
413 | Remark << ")" ; |
414 | return Remark; |
415 | }); |
416 | } |
417 | LLVM_DEBUG(dbgs() << " " << DLoc.getLine() << "." << Discriminator << ":" |
418 | << Inst << " (line offset: " << LineOffset << "." |
419 | << Discriminator << " - weight: " << R.get() << ")\n" ); |
420 | } |
421 | return R; |
422 | } |
423 | |
424 | // Here use error_code to represent: 1) The dangling probe. 2) Ignore the weight |
425 | // of non-probe instruction. So if all instructions of the BB give error_code, |
426 | // tell the inference algorithm to infer the BB weight. |
427 | template <typename BT> |
428 | ErrorOr<uint64_t> |
429 | SampleProfileLoaderBaseImpl<BT>::getProbeWeight(const InstructionT &Inst) { |
430 | assert(FunctionSamples::ProfileIsProbeBased && |
431 | "Profile is not pseudo probe based" ); |
432 | std::optional<PseudoProbe> Probe = extractProbe(Inst); |
433 | // Ignore the non-probe instruction. If none of the instruction in the BB is |
434 | // probe, we choose to infer the BB's weight. |
435 | if (!Probe) |
436 | return std::error_code(); |
437 | |
438 | const FunctionSamples *FS = findFunctionSamples(I: Inst); |
439 | // If none of the instruction has FunctionSample, we choose to return zero |
440 | // value sample to indicate the BB is cold. This could happen when the |
441 | // instruction is from inlinee and no profile data is found. |
442 | // FIXME: This should not be affected by the source drift issue as 1) if the |
443 | // newly added function is top-level inliner, it won't match the CFG checksum |
444 | // in the function profile or 2) if it's the inlinee, the inlinee should have |
445 | // a profile, otherwise it wouldn't be inlined. For non-probe based profile, |
446 | // we can improve it by adding a switch for profile-sample-block-accurate for |
447 | // block level counts in the future. |
448 | if (!FS) |
449 | return 0; |
450 | |
451 | auto R = FS->findSamplesAt(LineOffset: Probe->Id, Discriminator: Probe->Discriminator); |
452 | if (R) { |
453 | uint64_t Samples = R.get() * Probe->Factor; |
454 | bool FirstMark = CoverageTracker.markSamplesUsed(FS, LineOffset: Probe->Id, Discriminator: 0, Samples); |
455 | if (FirstMark) { |
456 | ORE->emit([&]() { |
457 | OptRemarkAnalysisT (DEBUG_TYPE, "AppliedSamples" , &Inst); |
458 | Remark << "Applied " << ore::NV("NumSamples" , Samples); |
459 | Remark << " samples from profile (ProbeId=" ; |
460 | Remark << ore::NV("ProbeId" , Probe->Id); |
461 | if (Probe->Discriminator) { |
462 | Remark << "." ; |
463 | Remark << ore::NV("Discriminator" , Probe->Discriminator); |
464 | } |
465 | Remark << ", Factor=" ; |
466 | Remark << ore::NV("Factor" , Probe->Factor); |
467 | Remark << ", OriginalSamples=" ; |
468 | Remark << ore::NV("OriginalSamples" , R.get()); |
469 | Remark << ")" ; |
470 | return Remark; |
471 | }); |
472 | } |
473 | LLVM_DEBUG({dbgs() << " " << Probe->Id; |
474 | if (Probe->Discriminator) |
475 | dbgs() << "." << Probe->Discriminator; |
476 | dbgs() << ":" << Inst << " - weight: " << R.get() |
477 | << " - factor: " << format("%0.2f" , Probe->Factor) << ")\n" ;}); |
478 | return Samples; |
479 | } |
480 | return R; |
481 | } |
482 | |
483 | /// Compute the weight of a basic block. |
484 | /// |
485 | /// The weight of basic block \p BB is the maximum weight of all the |
486 | /// instructions in BB. |
487 | /// |
488 | /// \param BB The basic block to query. |
489 | /// |
490 | /// \returns the weight for \p BB. |
491 | template <typename BT> |
492 | ErrorOr<uint64_t> |
493 | SampleProfileLoaderBaseImpl<BT>::getBlockWeight(const BasicBlockT *BB) { |
494 | uint64_t Max = 0; |
495 | bool HasWeight = false; |
496 | for (auto &I : *BB) { |
497 | const ErrorOr<uint64_t> &R = getInstWeight(Inst: I); |
498 | if (R) { |
499 | Max = std::max(a: Max, b: R.get()); |
500 | HasWeight = true; |
501 | } |
502 | } |
503 | return HasWeight ? ErrorOr<uint64_t>(Max) : std::error_code(); |
504 | } |
505 | |
506 | /// Compute and store the weights of every basic block. |
507 | /// |
508 | /// This populates the BlockWeights map by computing |
509 | /// the weights of every basic block in the CFG. |
510 | /// |
511 | /// \param F The function to query. |
512 | template <typename BT> |
513 | bool SampleProfileLoaderBaseImpl<BT>::computeBlockWeights(FunctionT &F) { |
514 | bool Changed = false; |
515 | LLVM_DEBUG(dbgs() << "Block weights\n" ); |
516 | for (const auto &BB : F) { |
517 | ErrorOr<uint64_t> Weight = getBlockWeight(BB: &BB); |
518 | if (Weight) { |
519 | BlockWeights[&BB] = Weight.get(); |
520 | VisitedBlocks.insert(&BB); |
521 | Changed = true; |
522 | } |
523 | LLVM_DEBUG(printBlockWeight(dbgs(), &BB)); |
524 | } |
525 | |
526 | return Changed; |
527 | } |
528 | |
529 | /// Get the FunctionSamples for an instruction. |
530 | /// |
531 | /// The FunctionSamples of an instruction \p Inst is the inlined instance |
532 | /// in which that instruction is coming from. We traverse the inline stack |
533 | /// of that instruction, and match it with the tree nodes in the profile. |
534 | /// |
535 | /// \param Inst Instruction to query. |
536 | /// |
537 | /// \returns the FunctionSamples pointer to the inlined instance. |
538 | template <typename BT> |
539 | const FunctionSamples *SampleProfileLoaderBaseImpl<BT>::findFunctionSamples( |
540 | const InstructionT &Inst) const { |
541 | const DILocation *DIL = Inst.getDebugLoc(); |
542 | if (!DIL) |
543 | return Samples; |
544 | |
545 | auto it = DILocation2SampleMap.try_emplace(Key: DIL, Args: nullptr); |
546 | if (it.second) { |
547 | it.first->second = Samples->findFunctionSamples(DIL, Remapper: Reader->getRemapper()); |
548 | } |
549 | return it.first->second; |
550 | } |
551 | |
552 | /// Find equivalence classes for the given block. |
553 | /// |
554 | /// This finds all the blocks that are guaranteed to execute the same |
555 | /// number of times as \p BB1. To do this, it traverses all the |
556 | /// descendants of \p BB1 in the dominator or post-dominator tree. |
557 | /// |
558 | /// A block BB2 will be in the same equivalence class as \p BB1 if |
559 | /// the following holds: |
560 | /// |
561 | /// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2 |
562 | /// is a descendant of \p BB1 in the dominator tree, then BB2 should |
563 | /// dominate BB1 in the post-dominator tree. |
564 | /// |
565 | /// 2- Both BB2 and \p BB1 must be in the same loop. |
566 | /// |
567 | /// For every block BB2 that meets those two requirements, we set BB2's |
568 | /// equivalence class to \p BB1. |
569 | /// |
570 | /// \param BB1 Block to check. |
571 | /// \param Descendants Descendants of \p BB1 in either the dom or pdom tree. |
572 | /// \param DomTree Opposite dominator tree. If \p Descendants is filled |
573 | /// with blocks from \p BB1's dominator tree, then |
574 | /// this is the post-dominator tree, and vice versa. |
575 | template <typename BT> |
576 | void SampleProfileLoaderBaseImpl<BT>::findEquivalencesFor( |
577 | BasicBlockT *BB1, ArrayRef<BasicBlockT *> Descendants, |
578 | PostDominatorTreeT *DomTree) { |
579 | const BasicBlockT *EC = EquivalenceClass[BB1]; |
580 | uint64_t Weight = BlockWeights[EC]; |
581 | for (const auto *BB2 : Descendants) { |
582 | bool IsDomParent = DomTree->dominates(BB2, BB1); |
583 | bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2); |
584 | if (BB1 != BB2 && IsDomParent && IsInSameLoop) { |
585 | EquivalenceClass[BB2] = EC; |
586 | // If BB2 is visited, then the entire EC should be marked as visited. |
587 | if (VisitedBlocks.count(BB2)) { |
588 | VisitedBlocks.insert(EC); |
589 | } |
590 | |
591 | // If BB2 is heavier than BB1, make BB2 have the same weight |
592 | // as BB1. |
593 | // |
594 | // Note that we don't worry about the opposite situation here |
595 | // (when BB2 is lighter than BB1). We will deal with this |
596 | // during the propagation phase. Right now, we just want to |
597 | // make sure that BB1 has the largest weight of all the |
598 | // members of its equivalence set. |
599 | Weight = std::max(Weight, BlockWeights[BB2]); |
600 | } |
601 | } |
602 | const BasicBlockT *EntryBB = getEntryBB(F: EC->getParent()); |
603 | if (EC == EntryBB) { |
604 | BlockWeights[EC] = Samples->getHeadSamples() + 1; |
605 | } else { |
606 | BlockWeights[EC] = Weight; |
607 | } |
608 | } |
609 | |
610 | /// Find equivalence classes. |
611 | /// |
612 | /// Since samples may be missing from blocks, we can fill in the gaps by setting |
613 | /// the weights of all the blocks in the same equivalence class to the same |
614 | /// weight. To compute the concept of equivalence, we use dominance and loop |
615 | /// information. Two blocks B1 and B2 are in the same equivalence class if B1 |
616 | /// dominates B2, B2 post-dominates B1 and both are in the same loop. |
617 | /// |
618 | /// \param F The function to query. |
619 | template <typename BT> |
620 | void SampleProfileLoaderBaseImpl<BT>::findEquivalenceClasses(FunctionT &F) { |
621 | SmallVector<BasicBlockT *, 8> DominatedBBs; |
622 | LLVM_DEBUG(dbgs() << "\nBlock equivalence classes\n" ); |
623 | // Find equivalence sets based on dominance and post-dominance information. |
624 | for (auto &BB : F) { |
625 | BasicBlockT *BB1 = &BB; |
626 | |
627 | // Compute BB1's equivalence class once. |
628 | if (EquivalenceClass.count(BB1)) { |
629 | LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1)); |
630 | continue; |
631 | } |
632 | |
633 | // By default, blocks are in their own equivalence class. |
634 | EquivalenceClass[BB1] = BB1; |
635 | |
636 | // Traverse all the blocks dominated by BB1. We are looking for |
637 | // every basic block BB2 such that: |
638 | // |
639 | // 1- BB1 dominates BB2. |
640 | // 2- BB2 post-dominates BB1. |
641 | // 3- BB1 and BB2 are in the same loop nest. |
642 | // |
643 | // If all those conditions hold, it means that BB2 is executed |
644 | // as many times as BB1, so they are placed in the same equivalence |
645 | // class by making BB2's equivalence class be BB1. |
646 | DominatedBBs.clear(); |
647 | DT->getDescendants(BB1, DominatedBBs); |
648 | findEquivalencesFor(BB1, Descendants: DominatedBBs, DomTree: &*PDT); |
649 | |
650 | LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1)); |
651 | } |
652 | |
653 | // Assign weights to equivalence classes. |
654 | // |
655 | // All the basic blocks in the same equivalence class will execute |
656 | // the same number of times. Since we know that the head block in |
657 | // each equivalence class has the largest weight, assign that weight |
658 | // to all the blocks in that equivalence class. |
659 | LLVM_DEBUG( |
660 | dbgs() << "\nAssign the same weight to all blocks in the same class\n" ); |
661 | for (auto &BI : F) { |
662 | const BasicBlockT *BB = &BI; |
663 | const BasicBlockT *EquivBB = EquivalenceClass[BB]; |
664 | if (BB != EquivBB) |
665 | BlockWeights[BB] = BlockWeights[EquivBB]; |
666 | LLVM_DEBUG(printBlockWeight(dbgs(), BB)); |
667 | } |
668 | } |
669 | |
670 | /// Visit the given edge to decide if it has a valid weight. |
671 | /// |
672 | /// If \p E has not been visited before, we copy to \p UnknownEdge |
673 | /// and increment the count of unknown edges. |
674 | /// |
675 | /// \param E Edge to visit. |
676 | /// \param NumUnknownEdges Current number of unknown edges. |
677 | /// \param UnknownEdge Set if E has not been visited before. |
678 | /// |
679 | /// \returns E's weight, if known. Otherwise, return 0. |
680 | template <typename BT> |
681 | uint64_t SampleProfileLoaderBaseImpl<BT>::visitEdge(Edge E, |
682 | unsigned *NumUnknownEdges, |
683 | Edge *UnknownEdge) { |
684 | if (!VisitedEdges.count(E)) { |
685 | (*NumUnknownEdges)++; |
686 | *UnknownEdge = E; |
687 | return 0; |
688 | } |
689 | |
690 | return EdgeWeights[E]; |
691 | } |
692 | |
693 | /// Propagate weights through incoming/outgoing edges. |
694 | /// |
695 | /// If the weight of a basic block is known, and there is only one edge |
696 | /// with an unknown weight, we can calculate the weight of that edge. |
697 | /// |
698 | /// Similarly, if all the edges have a known count, we can calculate the |
699 | /// count of the basic block, if needed. |
700 | /// |
701 | /// \param F Function to process. |
702 | /// \param UpdateBlockCount Whether we should update basic block counts that |
703 | /// has already been annotated. |
704 | /// |
705 | /// \returns True if new weights were assigned to edges or blocks. |
706 | template <typename BT> |
707 | bool SampleProfileLoaderBaseImpl<BT>::propagateThroughEdges( |
708 | FunctionT &F, bool UpdateBlockCount) { |
709 | bool Changed = false; |
710 | LLVM_DEBUG(dbgs() << "\nPropagation through edges\n" ); |
711 | for (const auto &BI : F) { |
712 | const BasicBlockT *BB = &BI; |
713 | const BasicBlockT *EC = EquivalenceClass[BB]; |
714 | |
715 | // Visit all the predecessor and successor edges to determine |
716 | // which ones have a weight assigned already. Note that it doesn't |
717 | // matter that we only keep track of a single unknown edge. The |
718 | // only case we are interested in handling is when only a single |
719 | // edge is unknown (see setEdgeOrBlockWeight). |
720 | for (unsigned i = 0; i < 2; i++) { |
721 | uint64_t TotalWeight = 0; |
722 | unsigned NumUnknownEdges = 0, NumTotalEdges = 0; |
723 | Edge UnknownEdge, SelfReferentialEdge, SingleEdge; |
724 | |
725 | if (i == 0) { |
726 | // First, visit all predecessor edges. |
727 | NumTotalEdges = Predecessors[BB].size(); |
728 | for (auto *Pred : Predecessors[BB]) { |
729 | Edge E = std::make_pair(Pred, BB); |
730 | TotalWeight += visitEdge(E, NumUnknownEdges: &NumUnknownEdges, UnknownEdge: &UnknownEdge); |
731 | if (E.first == E.second) |
732 | SelfReferentialEdge = E; |
733 | } |
734 | if (NumTotalEdges == 1) { |
735 | SingleEdge = std::make_pair(Predecessors[BB][0], BB); |
736 | } |
737 | } else { |
738 | // On the second round, visit all successor edges. |
739 | NumTotalEdges = Successors[BB].size(); |
740 | for (auto *Succ : Successors[BB]) { |
741 | Edge E = std::make_pair(BB, Succ); |
742 | TotalWeight += visitEdge(E, NumUnknownEdges: &NumUnknownEdges, UnknownEdge: &UnknownEdge); |
743 | } |
744 | if (NumTotalEdges == 1) { |
745 | SingleEdge = std::make_pair(BB, Successors[BB][0]); |
746 | } |
747 | } |
748 | |
749 | // After visiting all the edges, there are three cases that we |
750 | // can handle immediately: |
751 | // |
752 | // - All the edge weights are known (i.e., NumUnknownEdges == 0). |
753 | // In this case, we simply check that the sum of all the edges |
754 | // is the same as BB's weight. If not, we change BB's weight |
755 | // to match. Additionally, if BB had not been visited before, |
756 | // we mark it visited. |
757 | // |
758 | // - Only one edge is unknown and BB has already been visited. |
759 | // In this case, we can compute the weight of the edge by |
760 | // subtracting the total block weight from all the known |
761 | // edge weights. If the edges weight more than BB, then the |
762 | // edge of the last remaining edge is set to zero. |
763 | // |
764 | // - There exists a self-referential edge and the weight of BB is |
765 | // known. In this case, this edge can be based on BB's weight. |
766 | // We add up all the other known edges and set the weight on |
767 | // the self-referential edge as we did in the previous case. |
768 | // |
769 | // In any other case, we must continue iterating. Eventually, |
770 | // all edges will get a weight, or iteration will stop when |
771 | // it reaches SampleProfileMaxPropagateIterations. |
772 | if (NumUnknownEdges <= 1) { |
773 | uint64_t &BBWeight = BlockWeights[EC]; |
774 | if (NumUnknownEdges == 0) { |
775 | if (!VisitedBlocks.count(EC)) { |
776 | // If we already know the weight of all edges, the weight of the |
777 | // basic block can be computed. It should be no larger than the sum |
778 | // of all edge weights. |
779 | if (TotalWeight > BBWeight) { |
780 | BBWeight = TotalWeight; |
781 | Changed = true; |
782 | LLVM_DEBUG(dbgs() << "All edge weights for " << BB->getName() |
783 | << " known. Set weight for block: " ; |
784 | printBlockWeight(dbgs(), BB);); |
785 | } |
786 | } else if (NumTotalEdges == 1 && |
787 | EdgeWeights[SingleEdge] < BlockWeights[EC]) { |
788 | // If there is only one edge for the visited basic block, use the |
789 | // block weight to adjust edge weight if edge weight is smaller. |
790 | EdgeWeights[SingleEdge] = BlockWeights[EC]; |
791 | Changed = true; |
792 | } |
793 | } else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) { |
794 | // If there is a single unknown edge and the block has been |
795 | // visited, then we can compute E's weight. |
796 | if (BBWeight >= TotalWeight) |
797 | EdgeWeights[UnknownEdge] = BBWeight - TotalWeight; |
798 | else |
799 | EdgeWeights[UnknownEdge] = 0; |
800 | const BasicBlockT *OtherEC; |
801 | if (i == 0) |
802 | OtherEC = EquivalenceClass[UnknownEdge.first]; |
803 | else |
804 | OtherEC = EquivalenceClass[UnknownEdge.second]; |
805 | // Edge weights should never exceed the BB weights it connects. |
806 | if (VisitedBlocks.count(OtherEC) && |
807 | EdgeWeights[UnknownEdge] > BlockWeights[OtherEC]) |
808 | EdgeWeights[UnknownEdge] = BlockWeights[OtherEC]; |
809 | VisitedEdges.insert(UnknownEdge); |
810 | Changed = true; |
811 | LLVM_DEBUG(dbgs() << "Set weight for edge: " ; |
812 | printEdgeWeight(dbgs(), UnknownEdge)); |
813 | } |
814 | } else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) { |
815 | // If a block Weights 0, all its in/out edges should weight 0. |
816 | if (i == 0) { |
817 | for (auto *Pred : Predecessors[BB]) { |
818 | Edge E = std::make_pair(Pred, BB); |
819 | EdgeWeights[E] = 0; |
820 | VisitedEdges.insert(E); |
821 | } |
822 | } else { |
823 | for (auto *Succ : Successors[BB]) { |
824 | Edge E = std::make_pair(BB, Succ); |
825 | EdgeWeights[E] = 0; |
826 | VisitedEdges.insert(E); |
827 | } |
828 | } |
829 | } else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) { |
830 | uint64_t &BBWeight = BlockWeights[BB]; |
831 | // We have a self-referential edge and the weight of BB is known. |
832 | if (BBWeight >= TotalWeight) |
833 | EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight; |
834 | else |
835 | EdgeWeights[SelfReferentialEdge] = 0; |
836 | VisitedEdges.insert(SelfReferentialEdge); |
837 | Changed = true; |
838 | LLVM_DEBUG(dbgs() << "Set self-referential edge weight to: " ; |
839 | printEdgeWeight(dbgs(), SelfReferentialEdge)); |
840 | } |
841 | if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) { |
842 | BlockWeights[EC] = TotalWeight; |
843 | VisitedBlocks.insert(EC); |
844 | Changed = true; |
845 | } |
846 | } |
847 | } |
848 | |
849 | return Changed; |
850 | } |
851 | |
852 | /// Build in/out edge lists for each basic block in the CFG. |
853 | /// |
854 | /// We are interested in unique edges. If a block B1 has multiple |
855 | /// edges to another block B2, we only add a single B1->B2 edge. |
856 | template <typename BT> |
857 | void SampleProfileLoaderBaseImpl<BT>::buildEdges(FunctionT &F) { |
858 | for (auto &BI : F) { |
859 | BasicBlockT *B1 = &BI; |
860 | |
861 | // Add predecessors for B1. |
862 | SmallPtrSet<BasicBlockT *, 16> Visited; |
863 | if (!Predecessors[B1].empty()) |
864 | llvm_unreachable("Found a stale predecessors list in a basic block." ); |
865 | for (auto *B2 : getPredecessors(BB: B1)) |
866 | if (Visited.insert(B2).second) |
867 | Predecessors[B1].push_back(B2); |
868 | |
869 | // Add successors for B1. |
870 | Visited.clear(); |
871 | if (!Successors[B1].empty()) |
872 | llvm_unreachable("Found a stale successors list in a basic block." ); |
873 | for (auto *B2 : getSuccessors(BB: B1)) |
874 | if (Visited.insert(B2).second) |
875 | Successors[B1].push_back(B2); |
876 | } |
877 | } |
878 | |
879 | /// Propagate weights into edges |
880 | /// |
881 | /// The following rules are applied to every block BB in the CFG: |
882 | /// |
883 | /// - If BB has a single predecessor/successor, then the weight |
884 | /// of that edge is the weight of the block. |
885 | /// |
886 | /// - If all incoming or outgoing edges are known except one, and the |
887 | /// weight of the block is already known, the weight of the unknown |
888 | /// edge will be the weight of the block minus the sum of all the known |
889 | /// edges. If the sum of all the known edges is larger than BB's weight, |
890 | /// we set the unknown edge weight to zero. |
891 | /// |
892 | /// - If there is a self-referential edge, and the weight of the block is |
893 | /// known, the weight for that edge is set to the weight of the block |
894 | /// minus the weight of the other incoming edges to that block (if |
895 | /// known). |
896 | template <typename BT> |
897 | void SampleProfileLoaderBaseImpl<BT>::propagateWeights(FunctionT &F) { |
898 | // Flow-based profile inference is only usable with BasicBlock instantiation |
899 | // of SampleProfileLoaderBaseImpl. |
900 | if (SampleProfileUseProfi) { |
901 | // Prepare block sample counts for inference. |
902 | BlockWeightMap SampleBlockWeights; |
903 | for (const auto &BI : F) { |
904 | ErrorOr<uint64_t> Weight = getBlockWeight(BB: &BI); |
905 | if (Weight) |
906 | SampleBlockWeights[&BI] = Weight.get(); |
907 | } |
908 | // Fill in BlockWeights and EdgeWeights using an inference algorithm. |
909 | applyProfi(F, Successors, SampleBlockWeights, BlockWeights, EdgeWeights); |
910 | } else { |
911 | bool Changed = true; |
912 | unsigned I = 0; |
913 | |
914 | // If BB weight is larger than its corresponding loop's header BB weight, |
915 | // use the BB weight to replace the loop header BB weight. |
916 | for (auto &BI : F) { |
917 | BasicBlockT *BB = &BI; |
918 | LoopT *L = LI->getLoopFor(BB); |
919 | if (!L) { |
920 | continue; |
921 | } |
922 | BasicBlockT * = L->getHeader(); |
923 | if (Header && BlockWeights[BB] > BlockWeights[Header]) { |
924 | BlockWeights[Header] = BlockWeights[BB]; |
925 | } |
926 | } |
927 | |
928 | // Propagate until we converge or we go past the iteration limit. |
929 | while (Changed && I++ < SampleProfileMaxPropagateIterations) { |
930 | Changed = propagateThroughEdges(F, UpdateBlockCount: false); |
931 | } |
932 | |
933 | // The first propagation propagates BB counts from annotated BBs to unknown |
934 | // BBs. The 2nd propagation pass resets edges weights, and use all BB |
935 | // weights to propagate edge weights. |
936 | VisitedEdges.clear(); |
937 | Changed = true; |
938 | while (Changed && I++ < SampleProfileMaxPropagateIterations) { |
939 | Changed = propagateThroughEdges(F, UpdateBlockCount: false); |
940 | } |
941 | |
942 | // The 3rd propagation pass allows adjust annotated BB weights that are |
943 | // obviously wrong. |
944 | Changed = true; |
945 | while (Changed && I++ < SampleProfileMaxPropagateIterations) { |
946 | Changed = propagateThroughEdges(F, UpdateBlockCount: true); |
947 | } |
948 | } |
949 | } |
950 | |
951 | template <typename FT> |
952 | void SampleProfileLoaderBaseImpl<FT>::applyProfi( |
953 | FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights, |
954 | BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights) { |
955 | auto Infer = SampleProfileInference<FT>(F, Successors, SampleBlockWeights); |
956 | Infer.apply(BlockWeights, EdgeWeights); |
957 | } |
958 | |
959 | /// Generate branch weight metadata for all branches in \p F. |
960 | /// |
961 | /// Branch weights are computed out of instruction samples using a |
962 | /// propagation heuristic. Propagation proceeds in 3 phases: |
963 | /// |
964 | /// 1- Assignment of block weights. All the basic blocks in the function |
965 | /// are initial assigned the same weight as their most frequently |
966 | /// executed instruction. |
967 | /// |
968 | /// 2- Creation of equivalence classes. Since samples may be missing from |
969 | /// blocks, we can fill in the gaps by setting the weights of all the |
970 | /// blocks in the same equivalence class to the same weight. To compute |
971 | /// the concept of equivalence, we use dominance and loop information. |
972 | /// Two blocks B1 and B2 are in the same equivalence class if B1 |
973 | /// dominates B2, B2 post-dominates B1 and both are in the same loop. |
974 | /// |
975 | /// 3- Propagation of block weights into edges. This uses a simple |
976 | /// propagation heuristic. The following rules are applied to every |
977 | /// block BB in the CFG: |
978 | /// |
979 | /// - If BB has a single predecessor/successor, then the weight |
980 | /// of that edge is the weight of the block. |
981 | /// |
982 | /// - If all the edges are known except one, and the weight of the |
983 | /// block is already known, the weight of the unknown edge will |
984 | /// be the weight of the block minus the sum of all the known |
985 | /// edges. If the sum of all the known edges is larger than BB's weight, |
986 | /// we set the unknown edge weight to zero. |
987 | /// |
988 | /// - If there is a self-referential edge, and the weight of the block is |
989 | /// known, the weight for that edge is set to the weight of the block |
990 | /// minus the weight of the other incoming edges to that block (if |
991 | /// known). |
992 | /// |
993 | /// Since this propagation is not guaranteed to finalize for every CFG, we |
994 | /// only allow it to proceed for a limited number of iterations (controlled |
995 | /// by -sample-profile-max-propagate-iterations). |
996 | /// |
997 | /// FIXME: Try to replace this propagation heuristic with a scheme |
998 | /// that is guaranteed to finalize. A work-list approach similar to |
999 | /// the standard value propagation algorithm used by SSA-CCP might |
1000 | /// work here. |
1001 | /// |
1002 | /// \param F The function to query. |
1003 | /// |
1004 | /// \returns true if \p F was modified. Returns false, otherwise. |
1005 | template <typename BT> |
1006 | bool SampleProfileLoaderBaseImpl<BT>::computeAndPropagateWeights( |
1007 | FunctionT &F, const DenseSet<GlobalValue::GUID> &InlinedGUIDs) { |
1008 | bool Changed = (InlinedGUIDs.size() != 0); |
1009 | |
1010 | // Compute basic block weights. |
1011 | Changed |= computeBlockWeights(F); |
1012 | |
1013 | if (Changed) { |
1014 | // Initialize propagation. |
1015 | initWeightPropagation(F, InlinedGUIDs); |
1016 | |
1017 | // Propagate weights to all edges. |
1018 | propagateWeights(F); |
1019 | |
1020 | // Post-process propagated weights. |
1021 | finalizeWeightPropagation(F, InlinedGUIDs); |
1022 | } |
1023 | |
1024 | return Changed; |
1025 | } |
1026 | |
1027 | template <typename BT> |
1028 | void SampleProfileLoaderBaseImpl<BT>::initWeightPropagation( |
1029 | FunctionT &F, const DenseSet<GlobalValue::GUID> &InlinedGUIDs) { |
1030 | // Add an entry count to the function using the samples gathered at the |
1031 | // function entry. |
1032 | // Sets the GUIDs that are inlined in the profiled binary. This is used |
1033 | // for ThinLink to make correct liveness analysis, and also make the IR |
1034 | // match the profiled binary before annotation. |
1035 | getFunction(F).setEntryCount( |
1036 | ProfileCount(Samples->getHeadSamples() + 1, Function::PCT_Real), |
1037 | &InlinedGUIDs); |
1038 | |
1039 | if (!SampleProfileUseProfi) { |
1040 | // Compute dominance and loop info needed for propagation. |
1041 | computeDominanceAndLoopInfo(F); |
1042 | |
1043 | // Find equivalence classes. |
1044 | findEquivalenceClasses(F); |
1045 | } |
1046 | |
1047 | // Before propagation starts, build, for each block, a list of |
1048 | // unique predecessors and successors. This is necessary to handle |
1049 | // identical edges in multiway branches. Since we visit all blocks and all |
1050 | // edges of the CFG, it is cleaner to build these lists once at the start |
1051 | // of the pass. |
1052 | buildEdges(F); |
1053 | } |
1054 | |
1055 | template <typename BT> |
1056 | void SampleProfileLoaderBaseImpl<BT>::finalizeWeightPropagation( |
1057 | FunctionT &F, const DenseSet<GlobalValue::GUID> &InlinedGUIDs) { |
1058 | // If we utilize a flow-based count inference, then we trust the computed |
1059 | // counts and set the entry count as computed by the algorithm. This is |
1060 | // primarily done to sync the counts produced by profi and BFI inference, |
1061 | // which uses the entry count for mass propagation. |
1062 | // If profi produces a zero-value for the entry count, we fallback to |
1063 | // Samples->getHeadSamples() + 1 to avoid functions with zero count. |
1064 | if (SampleProfileUseProfi) { |
1065 | const BasicBlockT *EntryBB = getEntryBB(F: &F); |
1066 | ErrorOr<uint64_t> EntryWeight = getBlockWeight(BB: EntryBB); |
1067 | if (BlockWeights[EntryBB] > 0) { |
1068 | getFunction(F).setEntryCount( |
1069 | ProfileCount(BlockWeights[EntryBB], Function::PCT_Real), |
1070 | &InlinedGUIDs); |
1071 | } |
1072 | } |
1073 | } |
1074 | |
1075 | template <typename BT> |
1076 | void SampleProfileLoaderBaseImpl<BT>::(FunctionT &F) { |
1077 | // If coverage checking was requested, compute it now. |
1078 | const Function &Func = getFunction(F); |
1079 | if (SampleProfileRecordCoverage) { |
1080 | unsigned Used = CoverageTracker.countUsedRecords(FS: Samples, PSI); |
1081 | unsigned Total = CoverageTracker.countBodyRecords(FS: Samples, PSI); |
1082 | unsigned Coverage = CoverageTracker.computeCoverage(Used, Total); |
1083 | if (Coverage < SampleProfileRecordCoverage) { |
1084 | Func.getContext().diagnose(DI: DiagnosticInfoSampleProfile( |
1085 | Func.getSubprogram()->getFilename(), getFunctionLoc(Func&: F), |
1086 | Twine(Used) + " of " + Twine(Total) + " available profile records (" + |
1087 | Twine(Coverage) + "%) were applied" , |
1088 | DS_Warning)); |
1089 | } |
1090 | } |
1091 | |
1092 | if (SampleProfileSampleCoverage) { |
1093 | uint64_t Used = CoverageTracker.getTotalUsedSamples(); |
1094 | uint64_t Total = CoverageTracker.countBodySamples(FS: Samples, PSI); |
1095 | unsigned Coverage = CoverageTracker.computeCoverage(Used, Total); |
1096 | if (Coverage < SampleProfileSampleCoverage) { |
1097 | Func.getContext().diagnose(DI: DiagnosticInfoSampleProfile( |
1098 | Func.getSubprogram()->getFilename(), getFunctionLoc(Func&: F), |
1099 | Twine(Used) + " of " + Twine(Total) + " available profile samples (" + |
1100 | Twine(Coverage) + "%) were applied" , |
1101 | DS_Warning)); |
1102 | } |
1103 | } |
1104 | } |
1105 | |
1106 | /// Get the line number for the function header. |
1107 | /// |
1108 | /// This looks up function \p F in the current compilation unit and |
1109 | /// retrieves the line number where the function is defined. This is |
1110 | /// line 0 for all the samples read from the profile file. Every line |
1111 | /// number is relative to this line. |
1112 | /// |
1113 | /// \param F Function object to query. |
1114 | /// |
1115 | /// \returns the line number where \p F is defined. If it returns 0, |
1116 | /// it means that there is no debug information available for \p F. |
1117 | template <typename BT> |
1118 | unsigned SampleProfileLoaderBaseImpl<BT>::getFunctionLoc(FunctionT &F) { |
1119 | const Function &Func = getFunction(F); |
1120 | if (DISubprogram *S = Func.getSubprogram()) |
1121 | return S->getLine(); |
1122 | |
1123 | if (NoWarnSampleUnused) |
1124 | return 0; |
1125 | |
1126 | // If the start of \p F is missing, emit a diagnostic to inform the user |
1127 | // about the missed opportunity. |
1128 | Func.getContext().diagnose(DI: DiagnosticInfoSampleProfile( |
1129 | "No debug information found in function " + Func.getName() + |
1130 | ": Function profile not used" , |
1131 | DS_Warning)); |
1132 | return 0; |
1133 | } |
1134 | |
1135 | #undef DEBUG_TYPE |
1136 | |
1137 | } // namespace llvm |
1138 | #endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H |
1139 | |