LLVM 19.0.0git
SampleProfileLoaderBaseImpl.h
Go to the documentation of this file.
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"
23#include "llvm/ADT/SmallSet.h"
28#include "llvm/IR/BasicBlock.h"
29#include "llvm/IR/CFG.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"
36#include "llvm/IR/Module.h"
37#include "llvm/IR/PseudoProbe.h"
45
46namespace llvm {
47using namespace sampleprof;
48using namespace sampleprofutil;
50
51namespace vfs {
52class FileSystem;
53} // namespace vfs
54
55#define DEBUG_TYPE "sample-profile-impl"
56
57namespace afdo_detail {
58
59template <typename BlockT> struct IRTraits;
60template <> struct IRTraits<BasicBlock> {
65 using LoopT = Loop;
66 using LoopInfoPtrT = std::unique_ptr<LoopInfo>;
67 using DominatorTreePtrT = std::unique_ptr<DominatorTree>;
69 using PostDominatorTreePtrT = std::unique_ptr<PostDominatorTree>;
74 static Function &getFunction(Function &F) { return F; }
75 static const BasicBlock *getEntryBB(const Function *F) {
76 return &F->getEntryBlock();
77 }
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.
89
90public:
92 if (NamedMDNode *FuncInfo =
93 M.getNamedMetadata(PseudoProbeDescMetadataName)) {
94 for (const auto *Operand : FuncInfo->operands()) {
95 const auto *MD = cast<MDNode>(Operand);
96 auto GUID = mdconst::dyn_extract<ConstantInt>(MD->getOperand(0))
97 ->getZExtValue();
98 auto Hash = mdconst::dyn_extract<ConstantInt>(MD->getOperand(1))
99 ->getZExtValue();
100 GUIDToProbeDescMap.try_emplace(GUID, PseudoProbeDescriptor(GUID, Hash));
101 }
102 }
103 }
104
106 auto I = GUIDToProbeDescMap.find(GUID);
107 return I == GUIDToProbeDescMap.end() ? nullptr : &I->second;
108 }
109
110 const PseudoProbeDescriptor *getDesc(StringRef FProfileName) const {
111 return getDesc(Function::getGUID(FProfileName));
112 }
113
116 }
117
119 const FunctionSamples &Samples) const {
120 return FuncDesc.getFunctionHash() != Samples.getFunctionHash();
121 }
122
123 bool moduleIsProbed(const Module &M) const {
124 return M.getNamedMetadata(PseudoProbeDescMetadataName);
125 }
126
127 bool profileIsValid(const Function &F, const FunctionSamples &Samples) const {
128 const auto *Desc = getDesc(F);
129 bool IsAvailableExternallyLinkage =
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("profile-checksum-mismatch");
145
146 return Desc && !profileIsHashMismatched(*Desc, Samples);
147 }
148};
149
150
151
152extern cl::opt<bool> SampleProfileUseProfi;
153
154static inline bool skipProfileForFunction(const Function &F) {
155 return F.isDeclaration() || !F.hasFnAttribute("use-sample-profile");
156}
157
158template <typename FT> class SampleProfileLoaderBaseImpl {
159public:
160 SampleProfileLoaderBaseImpl(std::string Name, std::string RemapName,
162 : Filename(Name), RemappingFilename(RemapName), FS(std::move(FS)) {}
163 void dump() { Reader->dump(); }
164
166 using BT = std::remove_pointer_t<NodeRef>;
186
190 using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
194
195protected:
198
201 }
204 }
207 }
210 }
211
212 unsigned getFunctionLoc(FunctionT &Func);
219 virtual const FunctionSamples *
227 ArrayRef<BasicBlockT *> Descendants,
228 PostDominatorTreeT *DomTree);
231 BlockWeightMap &SampleBlockWeights,
233 uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
235 bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount);
236 void clearFunctionData(bool ResetDT = true);
238 bool
240 const DenseSet<GlobalValue::GUID> &InlinedGUIDs);
242 const DenseSet<GlobalValue::GUID> &InlinedGUIDs);
243 void
245 const DenseSet<GlobalValue::GUID> &InlinedGUIDs);
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.
253
254 /// Map edges to their computed weights.
255 ///
256 /// Edge weights are computed by propagating basic block weights in
257 /// SampleProfile::propagateWeights.
259
260 /// Set of visited blocks during propagation.
262
263 /// Set of visited edges during propagation.
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.
273
274 /// Dominance, post-dominance and loop information.
278
279 /// Predecessors for each basic block in the CFG.
281
282 /// Successors for each basic block in the CFG.
284
285 /// Profile coverage tracker.
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.
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.
310
311 /// Profile Summary Info computed from sample profile.
313
314 /// Optimization Remark Emitter used to emit diagnostic remarks.
316};
317
318/// Clear all the per-function data used to load samples and propagate weights.
319template <typename BT>
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.
341template <typename BT>
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.
351template <typename BT>
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.
363template <typename BT>
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.
383template <typename BT>
387 return getProbeWeight(Inst);
388 return getInstWeightImpl(Inst);
389}
390
391template <typename BT>
394 const FunctionSamples *FS = findFunctionSamples(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;
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, R.get());
414 if (FirstMark) {
415 ORE->emit([&]() {
416 OptRemarkAnalysisT Remark(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.
438template <typename BT>
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(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(Probe->Id, Probe->Discriminator);
463 if (R) {
464 uint64_t Samples = R.get() * Probe->Factor;
465 bool FirstMark = CoverageTracker.markSamplesUsed(FS, Probe->Id, 0, Samples);
466 if (FirstMark) {
467 ORE->emit([&]() {
468 OptRemarkAnalysisT Remark(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.
502template <typename BT>
505 uint64_t Max = 0;
506 bool HasWeight = false;
507 for (auto &I : *BB) {
508 const ErrorOr<uint64_t> &R = getInstWeight(I);
509 if (R) {
510 Max = std::max(Max, 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.
523template <typename BT>
525 bool Changed = false;
526 LLVM_DEBUG(dbgs() << "Block weights\n");
527 for (const auto &BB : F) {
528 ErrorOr<uint64_t> Weight = getBlockWeight(&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.
549template <typename BT>
551 const InstructionT &Inst) const {
552 const DILocation *DIL = Inst.getDebugLoc();
553 if (!DIL)
554 return Samples;
555
556 auto it = DILocation2SampleMap.try_emplace(DIL, nullptr);
557 if (it.second) {
558 it.first->second = Samples->findFunctionSamples(DIL, 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.
586template <typename BT>
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(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.
630template <typename BT>
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, DominatedBBs, &*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.
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.
691template <typename BT>
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.
717template <typename BT>
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, &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, &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.
867template <typename BT>
869 for (auto &BI : F) {
870 BasicBlockT *B1 = &BI;
871
872 // Add predecessors for B1.
874 if (!Predecessors[B1].empty())
875 llvm_unreachable("Found a stale predecessors list in a basic block.");
876 for (auto *B2 : getPredecessors(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(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).
907template <typename BT>
909 // Flow-based profile inference is only usable with BasicBlock instantiation
910 // of SampleProfileLoaderBaseImpl.
912 // Prepare block sample counts for inference.
913 BlockWeightMap SampleBlockWeights;
914 for (const auto &BI : F) {
915 ErrorOr<uint64_t> Weight = getBlockWeight(&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 *Header = 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, 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, 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, true);
958 }
959 }
960}
961
962template <typename FT>
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.
1016template <typename BT>
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
1038template <typename BT>
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.
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
1066template <typename BT>
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.
1076 const BasicBlockT *EntryBB = getEntryBB(&F);
1077 ErrorOr<uint64_t> EntryWeight = getBlockWeight(EntryBB);
1078 if (BlockWeights[EntryBB] > 0) {
1080 ProfileCount(BlockWeights[EntryBB], Function::PCT_Real),
1081 &InlinedGUIDs);
1082 }
1083 }
1084}
1085
1086template <typename BT>
1088 // If coverage checking was requested, compute it now.
1089 const Function &Func = getFunction(F);
1091 unsigned Used = CoverageTracker.countUsedRecords(Samples, PSI);
1092 unsigned Total = CoverageTracker.countBodyRecords(Samples, PSI);
1093 unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
1094 if (Coverage < SampleProfileRecordCoverage) {
1095 Func.getContext().diagnose(DiagnosticInfoSampleProfile(
1096 Func.getSubprogram()->getFilename(), getFunctionLoc(F),
1097 Twine(Used) + " of " + Twine(Total) + " available profile records (" +
1098 Twine(Coverage) + "%) were applied",
1099 DS_Warning));
1100 }
1101 }
1102
1104 uint64_t Used = CoverageTracker.getTotalUsedSamples();
1105 uint64_t Total = CoverageTracker.countBodySamples(Samples, PSI);
1106 unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
1107 if (Coverage < SampleProfileSampleCoverage) {
1108 Func.getContext().diagnose(DiagnosticInfoSampleProfile(
1109 Func.getSubprogram()->getFilename(), getFunctionLoc(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.
1128template <typename BT>
1130 const Function &Func = getFunction(F);
1131 if (DISubprogram *S = Func.getSubprogram())
1132 return S->getLine();
1133
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(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
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
std::string Name
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:236
#define DEBUG_TYPE
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This file defines the RefCountedBase, ThreadSafeRefCountedBase, and IntrusiveRefCntPtr classes.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
static StringRef getName(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file provides the interface for the profile inference algorithm, profi.
This file provides the utility functions for the sampled PGO loader base implementation.
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Debug location.
unsigned getBaseDiscriminator() const
Returns the base discriminator stored in the discriminator.
Subprogram description.
A debug info location.
Definition: DebugLoc.h:33
unsigned getLine() const
Definition: DebugLoc.cpp:24
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:235
iterator end()
Definition: DenseMap.h:84
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Diagnostic information for the sample profiler.
Represents either an error or a value T.
Definition: ErrorOr.h:56
reference get()
Definition: ErrorOr.h:149
Class to represent profile counts.
Definition: Function.h:279
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
Definition: Function.cpp:1987
static bool isAvailableExternallyLinkage(LinkageTypes Linkage)
Definition: GlobalValue.h:378
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:594
A smart pointer to a reference-counted object that inherits from RefCountedBase or ThreadSafeRefCount...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A tuple of MDNodes.
Definition: Metadata.h:1729
Diagnostic information for optimization analysis remarks.
The optimization diagnostic interface.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Analysis providing profile information.
uint64_t getFunctionHash() const
Definition: PseudoProbe.h:114
const PseudoProbeDescriptor * getDesc(StringRef FProfileName) const
bool profileIsHashMismatched(const PseudoProbeDescriptor &FuncDesc, const FunctionSamples &Samples) const
const PseudoProbeDescriptor * getDesc(const Function &F) const
bool moduleIsProbed(const Module &M) const
bool profileIsValid(const Function &F, const FunctionSamples &Samples) const
const PseudoProbeDescriptor * getDesc(uint64_t GUID) const
Sample profile inference pass.
bool computeAndPropagateWeights(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
Generate branch weight metadata for all branches in F.
void computeDominanceAndLoopInfo(FunctionT &F)
typename afdo_detail::IRTraits< BT >::BasicBlockT BasicBlockT
IntrusiveRefCntPtr< vfs::FileSystem > FS
VirtualFileSystem to load profile files from.
typename afdo_detail::IRTraits< BT >::OptRemarkAnalysisT OptRemarkAnalysisT
typename afdo_detail::IRTraits< BT >::SuccRangeT SuccRangeT
EdgeWeightMap EdgeWeights
Map edges to their computed weights.
SmallSet< Edge, 32 > VisitedEdges
Set of visited edges during propagation.
std::map< SampleContext, FunctionSamples > OutlineFunctionSamples
Synthetic samples created by duplicating the samples of inlined functions from the original profile a...
OptRemarkEmitterT * ORE
Optimization Remark Emitter used to emit diagnostic remarks.
const BasicBlockT * getEntryBB(const FunctionT *F)
ErrorOr< uint64_t > getBlockWeight(const BasicBlockT *BB)
Compute the weight of a basic block.
unsigned getFunctionLoc(FunctionT &Func)
Get the line number for the function header.
ErrorOr< uint64_t > getInstWeightImpl(const InstructionT &Inst)
virtual ErrorOr< uint64_t > getInstWeight(const InstructionT &Inst)
Get the weight for an instruction.
SmallPtrSet< const BasicBlockT *, 32 > VisitedBlocks
Set of visited blocks during propagation.
EquivalenceClassMap EquivalenceClass
Equivalence classes for block weights.
typename afdo_detail::IRTraits< BT >::DominatorTreePtrT DominatorTreePtrT
SampleCoverageTracker CoverageTracker
Profile coverage tracker.
typename afdo_detail::IRTraits< BT >::LoopT LoopT
typename GraphTraits< FT * >::NodeRef NodeRef
std::unique_ptr< SampleProfileReader > Reader
Profile reader object.
typename afdo_detail::IRTraits< BT >::OptRemarkEmitterT OptRemarkEmitterT
void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const
Print the weight of block BB on stream OS.
DominatorTreePtrT DT
Dominance, post-dominance and loop information.
void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB)
Print the equivalence class of block BB on stream OS.
std::remove_pointer_t< NodeRef > BT
SampleProfileLoaderBaseImpl(std::string Name, std::string RemapName, IntrusiveRefCntPtr< vfs::FileSystem > FS)
std::unique_ptr< PseudoProbeManager > ProbeManager
typename afdo_detail::IRTraits< BT >::LoopInfoPtrT LoopInfoPtrT
std::string Filename
Name of the profile file to load.
bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount)
Propagate weights through incoming/outgoing edges.
typename afdo_detail::IRTraits< BT >::InstructionT InstructionT
uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge)
Visit the given edge to decide if it has a valid weight.
typename afdo_detail::IRTraits< BT >::PostDominatorTreePtrT PostDominatorTreePtrT
void initWeightPropagation(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
BlockEdgeMap Predecessors
Predecessors for each basic block in the CFG.
void finalizeWeightPropagation(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
bool computeBlockWeights(FunctionT &F)
Compute and store the weights of every basic block.
virtual const FunctionSamples * findFunctionSamples(const InstructionT &I) const
Get the FunctionSamples for an instruction.
typename afdo_detail::IRTraits< BT >::PostDominatorTreeT PostDominatorTreeT
virtual ErrorOr< uint64_t > getProbeWeight(const InstructionT &Inst)
std::string RemappingFilename
Name of the profile remapping file to load.
typename afdo_detail::IRTraits< BT >::PredRangeT PredRangeT
void applyProfi(FunctionT &F, BlockEdgeMap &Successors, BlockWeightMap &SampleBlockWeights, BlockWeightMap &BlockWeights, EdgeWeightMap &EdgeWeights)
typename afdo_detail::IRTraits< BT >::BlockFrequencyInfoT BlockFrequencyInfoT
BlockEdgeMap Successors
Successors for each basic block in the CFG.
FunctionSamples * Samples
Samples collected for the body of this function.
void findEquivalenceClasses(FunctionT &F)
Find equivalence classes.
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
ProfileSummaryInfo * PSI
Profile Summary Info computed from sample profile.
void clearFunctionData(bool ResetDT=true)
Clear all the per-function data used to load samples and propagate weights.
DenseMap< const DILocation *, const FunctionSamples * > DILocation2SampleMap
void buildEdges(FunctionT &F)
Build in/out edge lists for each basic block in the CFG.
void findEquivalencesFor(BasicBlockT *BB1, ArrayRef< BasicBlockT * > Descendants, PostDominatorTreeT *DomTree)
Find equivalence classes for the given block.
void printEdgeWeight(raw_ostream &OS, Edge E)
Print the weight of edge E on stream OS.
typename afdo_detail::IRTraits< BT >::FunctionT FunctionT
BlockWeightMap BlockWeights
Map basic blocks to their computed weights.
void propagateWeights(FunctionT &F)
Propagate weights into edges.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
size_type size() const
Definition: DenseSet.h:81
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
Representation of the samples collected for a function.
Definition: SampleProf.h:744
static StringRef getCanonicalFnName(const Function &F)
Return the canonical name for a function, taking into account suffix elision policy attributes.
Definition: SampleProf.h:1085
static unsigned getOffset(const DILocation *DIL)
Returns the line offset to the start line of the subprogram.
Definition: SampleProf.cpp:216
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Function::ProfileCount ProfileCount
auto successors(const MachineBasicBlock *BB)
cl::opt< unsigned > SampleProfileSampleCoverage
cl::opt< unsigned > SampleProfileRecordCoverage
cl::opt< unsigned > SampleProfileMaxPropagateIterations
cl::opt< bool > SampleProfileUseProfi
cl::opt< bool > EnableFSDiscriminator
std::optional< PseudoProbe > extractProbe(const Instruction &Inst)
Definition: PseudoProbe.cpp:56
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
iterator_range< succ_iterator > succ_range
Definition: CFG.h:244
cl::opt< bool > NoWarnSampleUnused
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:125
iterator_range< pred_iterator > pred_range
Definition: CFG.h:107
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1849
@ DS_Warning
static bool skipProfileForFunction(const Function &F)
auto predecessors(const MachineBasicBlock *BB)
constexpr const char * PseudoProbeDescMetadataName
Definition: PseudoProbe.h:25
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
Description of the encoding of one expression Op.
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:80
std::unique_ptr< PostDominatorTree > PostDominatorTreePtrT
static pred_range getPredecessors(BasicBlock *BB)
static succ_range getSuccessors(BasicBlock *BB)
std::unique_ptr< DominatorTree > DominatorTreePtrT
static const BasicBlock * getEntryBB(const Function *F)