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