LLVM  13.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"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/Analysis/LoopInfo.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/CFG.h"
30 #include "llvm/IR/DebugLoc.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/Instruction.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/Module.h"
42 
43 namespace llvm {
44 using namespace sampleprof;
45 using namespace sampleprofutil;
47 
48 #define DEBUG_TYPE "sample-profile-impl"
49 
50 namespace afdo_detail {
51 
52 template <typename BlockT> struct IRTraits;
53 template <> struct IRTraits<BasicBlock> {
58  using LoopT = Loop;
64  static Function &getFunction(Function &F) { return F; }
65  static const BasicBlock *getEntryBB(const Function *F) {
66  return &F->getEntryBlock();
67  }
68 };
69 
70 } // end namespace afdo_detail
71 
72 extern cl::opt<unsigned> SampleProfileMaxPropagateIterations;
73 extern cl::opt<unsigned> SampleProfileRecordCoverage;
74 extern cl::opt<unsigned> SampleProfileSampleCoverage;
75 extern cl::opt<bool> NoWarnSampleUnused;
76 
77 template <typename BT> class SampleProfileLoaderBaseImpl {
78 public:
79  SampleProfileLoaderBaseImpl(std::string Name) : Filename(Name) {}
80  void dump() { Reader->dump(); }
81 
84  using BlockFrequencyInfoT =
89  using OptRemarkEmitterT =
91  using OptRemarkAnalysisT =
94  using PostDominatorTreeT =
96 
98  using EquivalenceClassMap =
100  using Edge = std::pair<const BasicBlockT *, const BasicBlockT *>;
102  using BlockEdgeMap =
104 
105 protected:
106  ~SampleProfileLoaderBaseImpl() = default;
107  friend class SampleCoverageTracker;
108 
111  }
114  }
115 
116  unsigned getFunctionLoc(FunctionT &Func);
117  virtual ErrorOr<uint64_t> getInstWeight(const InstructionT &Inst);
118  ErrorOr<uint64_t> getInstWeightImpl(const InstructionT &Inst);
119  ErrorOr<uint64_t> getBlockWeight(const BasicBlockT *BB);
122  virtual const FunctionSamples *
123  findFunctionSamples(const InstructionT &I) const;
124  void printEdgeWeight(raw_ostream &OS, Edge E);
125  void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const;
126  void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB);
127  bool computeBlockWeights(FunctionT &F);
128  void findEquivalenceClasses(FunctionT &F);
129  void findEquivalencesFor(BasicBlockT *BB1,
130  ArrayRef<BasicBlockT *> Descendants,
131  PostDominatorTreeT *DomTree);
132 
133  void propagateWeights(FunctionT &F);
134  uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
135  void buildEdges(FunctionT &F);
136  bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount);
137  void clearFunctionData();
138  void computeDominanceAndLoopInfo(FunctionT &F);
139  bool
140  computeAndPropagateWeights(FunctionT &F,
141  const DenseSet<GlobalValue::GUID> &InlinedGUIDs);
142  void emitCoverageRemarks(FunctionT &F);
143 
144  /// Map basic blocks to their computed weights.
145  ///
146  /// The weight of a basic block is defined to be the maximum
147  /// of all the instruction weights in that block.
149 
150  /// Map edges to their computed weights.
151  ///
152  /// Edge weights are computed by propagating basic block weights in
153  /// SampleProfile::propagateWeights.
155 
156  /// Set of visited blocks during propagation.
158 
159  /// Set of visited edges during propagation.
161 
162  /// Equivalence classes for block weights.
163  ///
164  /// Two blocks BB1 and BB2 are in the same equivalence class if they
165  /// dominate and post-dominate each other, and they are in the same loop
166  /// nest. When this happens, the two blocks are guaranteed to execute
167  /// the same number of times.
169 
170  /// Dominance, post-dominance and loop information.
171  std::unique_ptr<DominatorTreeT> DT;
172  std::unique_ptr<PostDominatorTreeT> PDT;
173  std::unique_ptr<LoopInfoT> LI;
174 
175  /// Predecessors for each basic block in the CFG.
177 
178  /// Successors for each basic block in the CFG.
180 
181  /// Profile coverage tracker.
183 
184  /// Profile reader object.
185  std::unique_ptr<SampleProfileReader> Reader;
186 
187  /// Samples collected for the body of this function.
188  FunctionSamples *Samples = nullptr;
189 
190  /// Name of the profile file to load.
191  std::string Filename;
192 
193  /// Profile Summary Info computed from sample profile.
194  ProfileSummaryInfo *PSI = nullptr;
195 
196  /// Optimization Remark Emitter used to emit diagnostic remarks.
197  OptRemarkEmitterT *ORE = nullptr;
198 };
199 
200 /// Clear all the per-function data used to load samples and propagate weights.
201 template <typename BT>
203  BlockWeights.clear();
204  EdgeWeights.clear();
205  VisitedBlocks.clear();
206  VisitedEdges.clear();
207  EquivalenceClass.clear();
208  DT = nullptr;
209  PDT = nullptr;
210  LI = nullptr;
211  Predecessors.clear();
212  Successors.clear();
213  CoverageTracker.clear();
214 }
215 
216 #ifndef NDEBUG
217 /// Print the weight of edge \p E on stream \p OS.
218 ///
219 /// \param OS Stream to emit the output to.
220 /// \param E Edge to print.
221 template <typename BT>
223  OS << "weight[" << E.first->getName() << "->" << E.second->getName()
224  << "]: " << EdgeWeights[E] << "\n";
225 }
226 
227 /// Print the equivalence class of block \p BB on stream \p OS.
228 ///
229 /// \param OS Stream to emit the output to.
230 /// \param BB Block to print.
231 template <typename BT>
233  raw_ostream &OS, const BasicBlockT *BB) {
234  const BasicBlockT *Equiv = EquivalenceClass[BB];
235  OS << "equivalence[" << BB->getName()
236  << "]: " << ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE") << "\n";
237 }
238 
239 /// Print the weight of block \p BB on stream \p OS.
240 ///
241 /// \param OS Stream to emit the output to.
242 /// \param BB Block to print.
243 template <typename BT>
245  raw_ostream &OS, const BasicBlockT *BB) const {
246  const auto &I = BlockWeights.find(BB);
247  uint64_t W = (I == BlockWeights.end() ? 0 : I->second);
248  OS << "weight[" << BB->getName() << "]: " << W << "\n";
249 }
250 #endif
251 
252 /// Get the weight for an instruction.
253 ///
254 /// The "weight" of an instruction \p Inst is the number of samples
255 /// collected on that instruction at runtime. To retrieve it, we
256 /// need to compute the line number of \p Inst relative to the start of its
257 /// function. We use HeaderLineno to compute the offset. We then
258 /// look up the samples collected for \p Inst using BodySamples.
259 ///
260 /// \param Inst Instruction to query.
261 ///
262 /// \returns the weight of \p Inst.
263 template <typename BT>
266  return getInstWeightImpl(Inst);
267 }
268 
269 template <typename BT>
272  const FunctionSamples *FS = findFunctionSamples(Inst);
273  if (!FS)
274  return std::error_code();
275 
276  const DebugLoc &DLoc = Inst.getDebugLoc();
277  if (!DLoc)
278  return std::error_code();
279 
280  const DILocation *DIL = DLoc;
281  uint32_t LineOffset = FunctionSamples::getOffset(DIL);
282  uint32_t Discriminator = DIL->getBaseDiscriminator();
283  ErrorOr<uint64_t> R = FS->findSamplesAt(LineOffset, Discriminator);
284  if (R) {
285  bool FirstMark =
286  CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());
287  if (FirstMark) {
288  ORE->emit([&]() {
289  OptRemarkAnalysisT Remark(DEBUG_TYPE, "AppliedSamples", &Inst);
290  Remark << "Applied " << ore::NV("NumSamples", *R);
291  Remark << " samples from profile (offset: ";
292  Remark << ore::NV("LineOffset", LineOffset);
293  if (Discriminator) {
294  Remark << ".";
295  Remark << ore::NV("Discriminator", Discriminator);
296  }
297  Remark << ")";
298  return Remark;
299  });
300  }
301  LLVM_DEBUG(dbgs() << " " << DLoc.getLine() << "."
302  << DIL->getBaseDiscriminator() << ":" << Inst
303  << " (line offset: " << LineOffset << "."
304  << DIL->getBaseDiscriminator() << " - weight: " << R.get()
305  << ")\n");
306  }
307  return R;
308 }
309 
310 /// Compute the weight of a basic block.
311 ///
312 /// The weight of basic block \p BB is the maximum weight of all the
313 /// instructions in BB.
314 ///
315 /// \param BB The basic block to query.
316 ///
317 /// \returns the weight for \p BB.
318 template <typename BT>
321  uint64_t Max = 0;
322  bool HasWeight = false;
323  for (auto &I : *BB) {
324  const ErrorOr<uint64_t> &R = getInstWeight(I);
325  if (R) {
326  Max = std::max(Max, R.get());
327  HasWeight = true;
328  }
329  }
330  return HasWeight ? ErrorOr<uint64_t>(Max) : std::error_code();
331 }
332 
333 /// Compute and store the weights of every basic block.
334 ///
335 /// This populates the BlockWeights map by computing
336 /// the weights of every basic block in the CFG.
337 ///
338 /// \param F The function to query.
339 template <typename BT>
341  bool Changed = false;
342  LLVM_DEBUG(dbgs() << "Block weights\n");
343  for (const auto &BB : F) {
344  ErrorOr<uint64_t> Weight = getBlockWeight(&BB);
345  if (Weight) {
346  BlockWeights[&BB] = Weight.get();
347  VisitedBlocks.insert(&BB);
348  Changed = true;
349  }
350  LLVM_DEBUG(printBlockWeight(dbgs(), &BB));
351  }
352 
353  return Changed;
354 }
355 
356 /// Get the FunctionSamples for an instruction.
357 ///
358 /// The FunctionSamples of an instruction \p Inst is the inlined instance
359 /// in which that instruction is coming from. We traverse the inline stack
360 /// of that instruction, and match it with the tree nodes in the profile.
361 ///
362 /// \param Inst Instruction to query.
363 ///
364 /// \returns the FunctionSamples pointer to the inlined instance.
365 template <typename BT>
367  const InstructionT &Inst) const {
368  const DILocation *DIL = Inst.getDebugLoc();
369  if (!DIL)
370  return Samples;
371 
372  auto it = DILocation2SampleMap.try_emplace(DIL, nullptr);
373  if (it.second) {
374  it.first->second = Samples->findFunctionSamples(DIL, Reader->getRemapper());
375  }
376  return it.first->second;
377 }
378 
379 /// Find equivalence classes for the given block.
380 ///
381 /// This finds all the blocks that are guaranteed to execute the same
382 /// number of times as \p BB1. To do this, it traverses all the
383 /// descendants of \p BB1 in the dominator or post-dominator tree.
384 ///
385 /// A block BB2 will be in the same equivalence class as \p BB1 if
386 /// the following holds:
387 ///
388 /// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2
389 /// is a descendant of \p BB1 in the dominator tree, then BB2 should
390 /// dominate BB1 in the post-dominator tree.
391 ///
392 /// 2- Both BB2 and \p BB1 must be in the same loop.
393 ///
394 /// For every block BB2 that meets those two requirements, we set BB2's
395 /// equivalence class to \p BB1.
396 ///
397 /// \param BB1 Block to check.
398 /// \param Descendants Descendants of \p BB1 in either the dom or pdom tree.
399 /// \param DomTree Opposite dominator tree. If \p Descendants is filled
400 /// with blocks from \p BB1's dominator tree, then
401 /// this is the post-dominator tree, and vice versa.
402 template <typename BT>
404  BasicBlockT *BB1, ArrayRef<BasicBlockT *> Descendants,
405  PostDominatorTreeT *DomTree) {
406  const BasicBlockT *EC = EquivalenceClass[BB1];
407  uint64_t Weight = BlockWeights[EC];
408  for (const auto *BB2 : Descendants) {
409  bool IsDomParent = DomTree->dominates(BB2, BB1);
410  bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
411  if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
412  EquivalenceClass[BB2] = EC;
413  // If BB2 is visited, then the entire EC should be marked as visited.
414  if (VisitedBlocks.count(BB2)) {
415  VisitedBlocks.insert(EC);
416  }
417 
418  // If BB2 is heavier than BB1, make BB2 have the same weight
419  // as BB1.
420  //
421  // Note that we don't worry about the opposite situation here
422  // (when BB2 is lighter than BB1). We will deal with this
423  // during the propagation phase. Right now, we just want to
424  // make sure that BB1 has the largest weight of all the
425  // members of its equivalence set.
426  Weight = std::max(Weight, BlockWeights[BB2]);
427  }
428  }
429  const BasicBlockT *EntryBB = getEntryBB(EC->getParent());
430  if (EC == EntryBB) {
431  BlockWeights[EC] = Samples->getHeadSamples() + 1;
432  } else {
433  BlockWeights[EC] = Weight;
434  }
435 }
436 
437 /// Find equivalence classes.
438 ///
439 /// Since samples may be missing from blocks, we can fill in the gaps by setting
440 /// the weights of all the blocks in the same equivalence class to the same
441 /// weight. To compute the concept of equivalence, we use dominance and loop
442 /// information. Two blocks B1 and B2 are in the same equivalence class if B1
443 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
444 ///
445 /// \param F The function to query.
446 template <typename BT>
448  SmallVector<BasicBlockT *, 8> DominatedBBs;
449  LLVM_DEBUG(dbgs() << "\nBlock equivalence classes\n");
450  // Find equivalence sets based on dominance and post-dominance information.
451  for (auto &BB : F) {
452  BasicBlockT *BB1 = &BB;
453 
454  // Compute BB1's equivalence class once.
455  if (EquivalenceClass.count(BB1)) {
456  LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1));
457  continue;
458  }
459 
460  // By default, blocks are in their own equivalence class.
461  EquivalenceClass[BB1] = BB1;
462 
463  // Traverse all the blocks dominated by BB1. We are looking for
464  // every basic block BB2 such that:
465  //
466  // 1- BB1 dominates BB2.
467  // 2- BB2 post-dominates BB1.
468  // 3- BB1 and BB2 are in the same loop nest.
469  //
470  // If all those conditions hold, it means that BB2 is executed
471  // as many times as BB1, so they are placed in the same equivalence
472  // class by making BB2's equivalence class be BB1.
473  DominatedBBs.clear();
474  DT->getDescendants(BB1, DominatedBBs);
475  findEquivalencesFor(BB1, DominatedBBs, PDT.get());
476 
477  LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1));
478  }
479 
480  // Assign weights to equivalence classes.
481  //
482  // All the basic blocks in the same equivalence class will execute
483  // the same number of times. Since we know that the head block in
484  // each equivalence class has the largest weight, assign that weight
485  // to all the blocks in that equivalence class.
486  LLVM_DEBUG(
487  dbgs() << "\nAssign the same weight to all blocks in the same class\n");
488  for (auto &BI : F) {
489  const BasicBlockT *BB = &BI;
490  const BasicBlockT *EquivBB = EquivalenceClass[BB];
491  if (BB != EquivBB)
492  BlockWeights[BB] = BlockWeights[EquivBB];
493  LLVM_DEBUG(printBlockWeight(dbgs(), BB));
494  }
495 }
496 
497 /// Visit the given edge to decide if it has a valid weight.
498 ///
499 /// If \p E has not been visited before, we copy to \p UnknownEdge
500 /// and increment the count of unknown edges.
501 ///
502 /// \param E Edge to visit.
503 /// \param NumUnknownEdges Current number of unknown edges.
504 /// \param UnknownEdge Set if E has not been visited before.
505 ///
506 /// \returns E's weight, if known. Otherwise, return 0.
507 template <typename BT>
509  unsigned *NumUnknownEdges,
510  Edge *UnknownEdge) {
511  if (!VisitedEdges.count(E)) {
512  (*NumUnknownEdges)++;
513  *UnknownEdge = E;
514  return 0;
515  }
516 
517  return EdgeWeights[E];
518 }
519 
520 /// Propagate weights through incoming/outgoing edges.
521 ///
522 /// If the weight of a basic block is known, and there is only one edge
523 /// with an unknown weight, we can calculate the weight of that edge.
524 ///
525 /// Similarly, if all the edges have a known count, we can calculate the
526 /// count of the basic block, if needed.
527 ///
528 /// \param F Function to process.
529 /// \param UpdateBlockCount Whether we should update basic block counts that
530 /// has already been annotated.
531 ///
532 /// \returns True if new weights were assigned to edges or blocks.
533 template <typename BT>
535  FunctionT &F, bool UpdateBlockCount) {
536  bool Changed = false;
537  LLVM_DEBUG(dbgs() << "\nPropagation through edges\n");
538  for (const auto &BI : F) {
539  const BasicBlockT *BB = &BI;
540  const BasicBlockT *EC = EquivalenceClass[BB];
541 
542  // Visit all the predecessor and successor edges to determine
543  // which ones have a weight assigned already. Note that it doesn't
544  // matter that we only keep track of a single unknown edge. The
545  // only case we are interested in handling is when only a single
546  // edge is unknown (see setEdgeOrBlockWeight).
547  for (unsigned i = 0; i < 2; i++) {
548  uint64_t TotalWeight = 0;
549  unsigned NumUnknownEdges = 0, NumTotalEdges = 0;
550  Edge UnknownEdge, SelfReferentialEdge, SingleEdge;
551 
552  if (i == 0) {
553  // First, visit all predecessor edges.
554  NumTotalEdges = Predecessors[BB].size();
555  for (auto *Pred : Predecessors[BB]) {
556  Edge E = std::make_pair(Pred, BB);
557  TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);
558  if (E.first == E.second)
559  SelfReferentialEdge = E;
560  }
561  if (NumTotalEdges == 1) {
562  SingleEdge = std::make_pair(Predecessors[BB][0], BB);
563  }
564  } else {
565  // On the second round, visit all successor edges.
566  NumTotalEdges = Successors[BB].size();
567  for (auto *Succ : Successors[BB]) {
568  Edge E = std::make_pair(BB, Succ);
569  TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);
570  }
571  if (NumTotalEdges == 1) {
572  SingleEdge = std::make_pair(BB, Successors[BB][0]);
573  }
574  }
575 
576  // After visiting all the edges, there are three cases that we
577  // can handle immediately:
578  //
579  // - All the edge weights are known (i.e., NumUnknownEdges == 0).
580  // In this case, we simply check that the sum of all the edges
581  // is the same as BB's weight. If not, we change BB's weight
582  // to match. Additionally, if BB had not been visited before,
583  // we mark it visited.
584  //
585  // - Only one edge is unknown and BB has already been visited.
586  // In this case, we can compute the weight of the edge by
587  // subtracting the total block weight from all the known
588  // edge weights. If the edges weight more than BB, then the
589  // edge of the last remaining edge is set to zero.
590  //
591  // - There exists a self-referential edge and the weight of BB is
592  // known. In this case, this edge can be based on BB's weight.
593  // We add up all the other known edges and set the weight on
594  // the self-referential edge as we did in the previous case.
595  //
596  // In any other case, we must continue iterating. Eventually,
597  // all edges will get a weight, or iteration will stop when
598  // it reaches SampleProfileMaxPropagateIterations.
599  if (NumUnknownEdges <= 1) {
600  uint64_t &BBWeight = BlockWeights[EC];
601  if (NumUnknownEdges == 0) {
602  if (!VisitedBlocks.count(EC)) {
603  // If we already know the weight of all edges, the weight of the
604  // basic block can be computed. It should be no larger than the sum
605  // of all edge weights.
606  if (TotalWeight > BBWeight) {
607  BBWeight = TotalWeight;
608  Changed = true;
609  LLVM_DEBUG(dbgs() << "All edge weights for " << BB->getName()
610  << " known. Set weight for block: ";
611  printBlockWeight(dbgs(), BB););
612  }
613  } else if (NumTotalEdges == 1 &&
614  EdgeWeights[SingleEdge] < BlockWeights[EC]) {
615  // If there is only one edge for the visited basic block, use the
616  // block weight to adjust edge weight if edge weight is smaller.
617  EdgeWeights[SingleEdge] = BlockWeights[EC];
618  Changed = true;
619  }
620  } else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
621  // If there is a single unknown edge and the block has been
622  // visited, then we can compute E's weight.
623  if (BBWeight >= TotalWeight)
624  EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
625  else
626  EdgeWeights[UnknownEdge] = 0;
627  const BasicBlockT *OtherEC;
628  if (i == 0)
629  OtherEC = EquivalenceClass[UnknownEdge.first];
630  else
631  OtherEC = EquivalenceClass[UnknownEdge.second];
632  // Edge weights should never exceed the BB weights it connects.
633  if (VisitedBlocks.count(OtherEC) &&
634  EdgeWeights[UnknownEdge] > BlockWeights[OtherEC])
635  EdgeWeights[UnknownEdge] = BlockWeights[OtherEC];
636  VisitedEdges.insert(UnknownEdge);
637  Changed = true;
638  LLVM_DEBUG(dbgs() << "Set weight for edge: ";
639  printEdgeWeight(dbgs(), UnknownEdge));
640  }
641  } else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) {
642  // If a block Weights 0, all its in/out edges should weight 0.
643  if (i == 0) {
644  for (auto *Pred : Predecessors[BB]) {
645  Edge E = std::make_pair(Pred, BB);
646  EdgeWeights[E] = 0;
647  VisitedEdges.insert(E);
648  }
649  } else {
650  for (auto *Succ : Successors[BB]) {
651  Edge E = std::make_pair(BB, Succ);
652  EdgeWeights[E] = 0;
653  VisitedEdges.insert(E);
654  }
655  }
656  } else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
657  uint64_t &BBWeight = BlockWeights[BB];
658  // We have a self-referential edge and the weight of BB is known.
659  if (BBWeight >= TotalWeight)
660  EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
661  else
662  EdgeWeights[SelfReferentialEdge] = 0;
663  VisitedEdges.insert(SelfReferentialEdge);
664  Changed = true;
665  LLVM_DEBUG(dbgs() << "Set self-referential edge weight to: ";
666  printEdgeWeight(dbgs(), SelfReferentialEdge));
667  }
668  if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) {
669  BlockWeights[EC] = TotalWeight;
670  VisitedBlocks.insert(EC);
671  Changed = true;
672  }
673  }
674  }
675 
676  return Changed;
677 }
678 
679 /// Build in/out edge lists for each basic block in the CFG.
680 ///
681 /// We are interested in unique edges. If a block B1 has multiple
682 /// edges to another block B2, we only add a single B1->B2 edge.
683 template <typename BT>
685  for (auto &BI : F) {
686  BasicBlockT *B1 = &BI;
687 
688  // Add predecessors for B1.
690  if (!Predecessors[B1].empty())
691  llvm_unreachable("Found a stale predecessors list in a basic block.");
692  for (BasicBlockT *B2 : predecessors(B1))
693  if (Visited.insert(B2).second)
694  Predecessors[B1].push_back(B2);
695 
696  // Add successors for B1.
697  Visited.clear();
698  if (!Successors[B1].empty())
699  llvm_unreachable("Found a stale successors list in a basic block.");
700  for (BasicBlockT *B2 : successors(B1))
701  if (Visited.insert(B2).second)
702  Successors[B1].push_back(B2);
703  }
704 }
705 
706 /// Propagate weights into edges
707 ///
708 /// The following rules are applied to every block BB in the CFG:
709 ///
710 /// - If BB has a single predecessor/successor, then the weight
711 /// of that edge is the weight of the block.
712 ///
713 /// - If all incoming or outgoing edges are known except one, and the
714 /// weight of the block is already known, the weight of the unknown
715 /// edge will be the weight of the block minus the sum of all the known
716 /// edges. If the sum of all the known edges is larger than BB's weight,
717 /// we set the unknown edge weight to zero.
718 ///
719 /// - If there is a self-referential edge, and the weight of the block is
720 /// known, the weight for that edge is set to the weight of the block
721 /// minus the weight of the other incoming edges to that block (if
722 /// known).
723 template <typename BT>
725  bool Changed = true;
726  unsigned I = 0;
727 
728  // If BB weight is larger than its corresponding loop's header BB weight,
729  // use the BB weight to replace the loop header BB weight.
730  for (auto &BI : F) {
731  BasicBlockT *BB = &BI;
732  LoopT *L = LI->getLoopFor(BB);
733  if (!L) {
734  continue;
735  }
736  BasicBlockT *Header = L->getHeader();
737  if (Header && BlockWeights[BB] > BlockWeights[Header]) {
738  BlockWeights[Header] = BlockWeights[BB];
739  }
740  }
741 
742  // Before propagation starts, build, for each block, a list of
743  // unique predecessors and successors. This is necessary to handle
744  // identical edges in multiway branches. Since we visit all blocks and all
745  // edges of the CFG, it is cleaner to build these lists once at the start
746  // of the pass.
747  buildEdges(F);
748 
749  // Propagate until we converge or we go past the iteration limit.
750  while (Changed && I++ < SampleProfileMaxPropagateIterations) {
751  Changed = propagateThroughEdges(F, false);
752  }
753 
754  // The first propagation propagates BB counts from annotated BBs to unknown
755  // BBs. The 2nd propagation pass resets edges weights, and use all BB weights
756  // to propagate edge weights.
757  VisitedEdges.clear();
758  Changed = true;
759  while (Changed && I++ < SampleProfileMaxPropagateIterations) {
760  Changed = propagateThroughEdges(F, false);
761  }
762 
763  // The 3rd propagation pass allows adjust annotated BB weights that are
764  // obviously wrong.
765  Changed = true;
766  while (Changed && I++ < SampleProfileMaxPropagateIterations) {
767  Changed = propagateThroughEdges(F, true);
768  }
769 }
770 
771 /// Generate branch weight metadata for all branches in \p F.
772 ///
773 /// Branch weights are computed out of instruction samples using a
774 /// propagation heuristic. Propagation proceeds in 3 phases:
775 ///
776 /// 1- Assignment of block weights. All the basic blocks in the function
777 /// are initial assigned the same weight as their most frequently
778 /// executed instruction.
779 ///
780 /// 2- Creation of equivalence classes. Since samples may be missing from
781 /// blocks, we can fill in the gaps by setting the weights of all the
782 /// blocks in the same equivalence class to the same weight. To compute
783 /// the concept of equivalence, we use dominance and loop information.
784 /// Two blocks B1 and B2 are in the same equivalence class if B1
785 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
786 ///
787 /// 3- Propagation of block weights into edges. This uses a simple
788 /// propagation heuristic. The following rules are applied to every
789 /// block BB in the CFG:
790 ///
791 /// - If BB has a single predecessor/successor, then the weight
792 /// of that edge is the weight of the block.
793 ///
794 /// - If all the edges are known except one, and the weight of the
795 /// block is already known, the weight of the unknown edge will
796 /// be the weight of the block minus the sum of all the known
797 /// edges. If the sum of all the known edges is larger than BB's weight,
798 /// we set the unknown edge weight to zero.
799 ///
800 /// - If there is a self-referential edge, and the weight of the block is
801 /// known, the weight for that edge is set to the weight of the block
802 /// minus the weight of the other incoming edges to that block (if
803 /// known).
804 ///
805 /// Since this propagation is not guaranteed to finalize for every CFG, we
806 /// only allow it to proceed for a limited number of iterations (controlled
807 /// by -sample-profile-max-propagate-iterations).
808 ///
809 /// FIXME: Try to replace this propagation heuristic with a scheme
810 /// that is guaranteed to finalize. A work-list approach similar to
811 /// the standard value propagation algorithm used by SSA-CCP might
812 /// work here.
813 ///
814 /// \param F The function to query.
815 ///
816 /// \returns true if \p F was modified. Returns false, otherwise.
817 template <typename BT>
819  FunctionT &F, const DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
820  bool Changed = (InlinedGUIDs.size() != 0);
821 
822  // Compute basic block weights.
823  Changed |= computeBlockWeights(F);
824 
825  if (Changed) {
826  // Add an entry count to the function using the samples gathered at the
827  // function entry.
828  // Sets the GUIDs that are inlined in the profiled binary. This is used
829  // for ThinLink to make correct liveness analysis, and also make the IR
830  // match the profiled binary before annotation.
831  getFunction(F).setEntryCount(
832  ProfileCount(Samples->getHeadSamples() + 1, Function::PCT_Real),
833  &InlinedGUIDs);
834 
835  // Compute dominance and loop info needed for propagation.
836  computeDominanceAndLoopInfo(F);
837 
838  // Find equivalence classes.
839  findEquivalenceClasses(F);
840 
841  // Propagate weights to all edges.
842  propagateWeights(F);
843  }
844 
845  return Changed;
846 }
847 
848 template <typename BT>
850  // If coverage checking was requested, compute it now.
851  const Function &Func = getFunction(F);
853  unsigned Used = CoverageTracker.countUsedRecords(Samples, PSI);
854  unsigned Total = CoverageTracker.countBodyRecords(Samples, PSI);
855  unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
856  if (Coverage < SampleProfileRecordCoverage) {
857  Func.getContext().diagnose(DiagnosticInfoSampleProfile(
858  Func.getSubprogram()->getFilename(), getFunctionLoc(F),
859  Twine(Used) + " of " + Twine(Total) + " available profile records (" +
860  Twine(Coverage) + "%) were applied",
861  DS_Warning));
862  }
863  }
864 
866  uint64_t Used = CoverageTracker.getTotalUsedSamples();
867  uint64_t Total = CoverageTracker.countBodySamples(Samples, PSI);
868  unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
869  if (Coverage < SampleProfileSampleCoverage) {
870  Func.getContext().diagnose(DiagnosticInfoSampleProfile(
871  Func.getSubprogram()->getFilename(), getFunctionLoc(F),
872  Twine(Used) + " of " + Twine(Total) + " available profile samples (" +
873  Twine(Coverage) + "%) were applied",
874  DS_Warning));
875  }
876  }
877 }
878 
879 /// Get the line number for the function header.
880 ///
881 /// This looks up function \p F in the current compilation unit and
882 /// retrieves the line number where the function is defined. This is
883 /// line 0 for all the samples read from the profile file. Every line
884 /// number is relative to this line.
885 ///
886 /// \param F Function object to query.
887 ///
888 /// \returns the line number where \p F is defined. If it returns 0,
889 /// it means that there is no debug information available for \p F.
890 template <typename BT>
892  const Function &Func = getFunction(F);
893  if (DISubprogram *S = Func.getSubprogram())
894  return S->getLine();
895 
896  if (NoWarnSampleUnused)
897  return 0;
898 
899  // If the start of \p F is missing, emit a diagnostic to inform the user
900  // about the missed opportunity.
901  Func.getContext().diagnose(DiagnosticInfoSampleProfile(
902  "No debug information found in function " + Func.getName() +
903  ": Function profile not used",
904  DS_Warning));
905  return 0;
906 }
907 
908 template <typename BT>
910  FunctionT &F) {
911  DT.reset(new DominatorTreeT);
912  DT->recalculate(F);
913 
914  PDT.reset(new PostDominatorTree(F));
915 
916  LI.reset(new LoopInfoT);
917  LI->analyze(*DT);
918 }
919 
920 #undef DEBUG_TYPE
921 
922 } // namespace llvm
923 #endif // LLVM_TRANSFORMS_UTILS_SAMPLEPROFILELOADERBASEIMPL_H
llvm::SampleProfileLoaderBaseImpl::getEntryBB
const BasicBlockT * getEntryBB(const FunctionT *F)
Definition: SampleProfileLoaderBaseImpl.h:112
i
i
Definition: README.txt:29
llvm::SampleProfileLoaderBaseImpl::clearFunctionData
void clearFunctionData()
Clear all the per-function data used to load samples and propagate weights.
Definition: SampleProfileLoaderBaseImpl.h:202
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
B1
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:42
llvm
Definition: AllocatorList.h:23
llvm::SampleProfileLoaderBaseImpl::PDT
std::unique_ptr< PostDominatorTreeT > PDT
Definition: SampleProfileLoaderBaseImpl.h:172
llvm::SampleProfileLoaderBaseImpl::OptRemarkAnalysisT
typename afdo_detail::IRTraits< BT >::OptRemarkAnalysisT OptRemarkAnalysisT
Definition: SampleProfileLoaderBaseImpl.h:92
llvm::SampleProfileLoaderBaseImpl::getFunction
Function & getFunction(FunctionT &F)
Definition: SampleProfileLoaderBaseImpl.h:109
DebugInfoMetadata.h
llvm::SampleProfileLoaderBaseImpl::visitEdge
uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge)
Visit the given edge to decide if it has a valid weight.
Definition: SampleProfileLoaderBaseImpl.h:508
llvm::Function
Definition: Function.h:61
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:253
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
it
Reference model for inliner Oz decision policy Note this model is also referenced by test Transforms Inline ML tests if replacing it
Definition: README.txt:3
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:134
llvm::SampleProfileLoaderBaseImpl
Definition: SampleProfileLoaderBaseImpl.h:77
llvm::SampleProfileLoaderBaseImpl::Predecessors
BlockEdgeMap Predecessors
Predecessors for each basic block in the CFG.
Definition: SampleProfileLoaderBaseImpl.h:176
OptimizationRemarkEmitter.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::SampleProfileLoaderBaseImpl::Successors
BlockEdgeMap Successors
Successors for each basic block in the CFG.
Definition: SampleProfileLoaderBaseImpl.h:179
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1558
DenseMap.h
Module.h
llvm::SmallSet< Edge, 32 >
llvm::SmallPtrSet< const BasicBlockT *, 32 >
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:128
llvm::NoWarnSampleUnused
cl::opt< bool > NoWarnSampleUnused
Definition: SampleProfileLoaderBaseUtil.h:35
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::X86AS::FS
@ FS
Definition: X86.h:183
llvm::SampleProfileLoaderBaseImpl::BlockFrequencyInfoT
typename afdo_detail::IRTraits< BT >::BlockFrequencyInfoT BlockFrequencyInfoT
Definition: SampleProfileLoaderBaseImpl.h:85
llvm::SampleProfileLoaderBaseImpl::LoopInfoT
typename afdo_detail::IRTraits< BT >::LoopInfoT LoopInfoT
Definition: SampleProfileLoaderBaseImpl.h:88
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:133
llvm::afdo_detail::IRTraits< BasicBlock >::getFunction
static Function & getFunction(Function &F)
Definition: SampleProfileLoaderBaseImpl.h:64
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Instruction.h
CommandLine.h
llvm::SampleProfileLoaderBaseImpl::getBlockWeight
ErrorOr< uint64_t > getBlockWeight(const BasicBlockT *BB)
Compute the weight of a basic block.
Definition: SampleProfileLoaderBaseImpl.h:320
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::SampleProfileLoaderBaseImpl::propagateThroughEdges
bool propagateThroughEdges(FunctionT &F, bool UpdateBlockCount)
Propagate weights through incoming/outgoing edges.
Definition: SampleProfileLoaderBaseImpl.h:534
llvm::SampleProfileLoaderBaseImpl::printBlockEquivalence
void printBlockEquivalence(raw_ostream &OS, const BasicBlockT *BB)
Print the equivalence class of block BB on stream OS.
Definition: SampleProfileLoaderBaseImpl.h:232
PostDominators.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::DS_Warning
@ DS_Warning
Definition: DiagnosticInfo.h:46
llvm::afdo_detail::IRTraits< BasicBlock >::getEntryBB
static const BasicBlock * getEntryBB(const Function *F)
Definition: SampleProfileLoaderBaseImpl.h:65
llvm::SampleProfileLoaderBaseImpl::BlockWeights
BlockWeightMap BlockWeights
Map basic blocks to their computed weights.
Definition: SampleProfileLoaderBaseImpl.h:148
DenseSet.h
SampleProf.h
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::Instruction
Definition: Instruction.h:45
llvm::SampleProfileLoaderBaseImpl::Filename
std::string Filename
Name of the profile file to load.
Definition: SampleProfileLoaderBaseImpl.h:191
llvm::SampleProfileLoaderBaseImpl::computeDominanceAndLoopInfo
void computeDominanceAndLoopInfo(FunctionT &F)
Definition: SampleProfileLoaderBaseImpl.h:909
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::SampleProfileLoaderBaseImpl::printEdgeWeight
void printEdgeWeight(raw_ostream &OS, Edge E)
Print the weight of edge E on stream OS.
Definition: SampleProfileLoaderBaseImpl.h:222
DebugLoc.h
SmallPtrSet.h
llvm::Function::PCT_Real
@ PCT_Real
Definition: Function.h:287
SampleProfileLoaderBaseUtil.h
llvm::SampleProfileLoaderBaseImpl::PostDominatorTreeT
typename afdo_detail::IRTraits< BT >::PostDominatorTreeT PostDominatorTreeT
Definition: SampleProfileLoaderBaseImpl.h:95
llvm::SampleProfileLoaderBaseImpl::findFunctionSamples
virtual const FunctionSamples * findFunctionSamples(const InstructionT &I) const
Get the FunctionSamples for an instruction.
Definition: SampleProfileLoaderBaseImpl.h:366
llvm::SampleProfileLoaderBaseImpl::getInstWeight
virtual ErrorOr< uint64_t > getInstWeight(const InstructionT &Inst)
Get the weight for an instruction.
Definition: SampleProfileLoaderBaseImpl.h:265
llvm::SampleProfileLoaderBaseImpl::Reader
std::unique_ptr< SampleProfileReader > Reader
Profile reader object.
Definition: SampleProfileLoaderBaseImpl.h:185
CFG.h
LoopInfo.h
llvm::SampleProfileLoaderBaseImpl::emitCoverageRemarks
void emitCoverageRemarks(FunctionT &F)
Definition: SampleProfileLoaderBaseImpl.h:849
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::SampleProfileLoaderBaseImpl::getFunctionLoc
unsigned getFunctionLoc(FunctionT &Func)
Get the line number for the function header.
Definition: SampleProfileLoaderBaseImpl.h:891
llvm::DenseSet< GlobalValue::GUID >
llvm::HighlightColor::Remark
@ Remark
BasicBlock.h
llvm::SampleProfileLoaderBaseImpl::computeAndPropagateWeights
bool computeAndPropagateWeights(FunctionT &F, const DenseSet< GlobalValue::GUID > &InlinedGUIDs)
Generate branch weight metadata for all branches in F.
Definition: SampleProfileLoaderBaseImpl.h:818
llvm::ProfileCount
Function::ProfileCount ProfileCount
Definition: SampleProfileLoaderBaseImpl.h:46
llvm::SampleProfileLoaderBaseImpl::computeBlockWeights
bool computeBlockWeights(FunctionT &F)
Compute and store the weights of every basic block.
Definition: SampleProfileLoaderBaseImpl.h:340
llvm::SampleProfileLoaderBaseImpl::LI
std::unique_ptr< LoopInfoT > LI
Definition: SampleProfileLoaderBaseImpl.h:173
llvm::SampleProfileLoaderBaseImpl::DominatorTreeT
typename afdo_detail::IRTraits< BT >::DominatorTreeT DominatorTreeT
Definition: SampleProfileLoaderBaseImpl.h:93
llvm::sampleprof::FunctionSamples
Representation of the samples collected for a function.
Definition: SampleProf.h:530
llvm::SampleProfileLoaderBaseImpl::InstructionT
typename afdo_detail::IRTraits< BT >::InstructionT InstructionT
Definition: SampleProfileLoaderBaseImpl.h:82
llvm::SampleProfileLoaderBaseImpl::CoverageTracker
SampleCoverageTracker CoverageTracker
Profile coverage tracker.
Definition: SampleProfileLoaderBaseImpl.h:182
llvm::SampleProfileLoaderBaseImpl::getInstWeightImpl
ErrorOr< uint64_t > getInstWeightImpl(const InstructionT &Inst)
Definition: SampleProfileLoaderBaseImpl.h:271
llvm::SampleProfileRecordCoverage
cl::opt< unsigned > SampleProfileRecordCoverage
Definition: SampleProfileLoaderBaseUtil.h:33
llvm::DenseMap< const BasicBlockT *, uint64_t >
I
#define I(x, y, z)
Definition: MD5.cpp:59
SampleProfReader.h
llvm::SampleProfileLoaderBaseImpl::DT
std::unique_ptr< DominatorTreeT > DT
Dominance, post-dominance and loop information.
Definition: SampleProfileLoaderBaseImpl.h:171
llvm::SampleProfileLoaderBaseImpl::findEquivalenceClasses
void findEquivalenceClasses(FunctionT &F)
Find equivalence classes.
Definition: SampleProfileLoaderBaseImpl.h:447
ArrayRef.h
DEBUG_TYPE
#define DEBUG_TYPE
Definition: SampleProfileLoaderBaseImpl.h:48
llvm::SampleProfileLoaderBaseImpl::EquivalenceClass
EquivalenceClassMap EquivalenceClass
Equivalence classes for block weights.
Definition: SampleProfileLoaderBaseImpl.h:168
llvm::SampleProfileLoaderBaseImpl::VisitedBlocks
SmallPtrSet< const BasicBlockT *, 32 > VisitedBlocks
Set of visited blocks during propagation.
Definition: SampleProfileLoaderBaseImpl.h:157
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:64
llvm::SampleProfileLoaderBaseImpl::buildEdges
void buildEdges(FunctionT &F)
Build in/out edge lists for each basic block in the CFG.
Definition: SampleProfileLoaderBaseImpl.h:684
llvm::sampleprof::FunctionSamples::getOffset
static unsigned getOffset(const DILocation *DIL)
Returns the line offset to the start line of the subprogram.
Definition: SampleProf.cpp:209
llvm::DiagnosticInfoSampleProfile
Diagnostic information for the sample profiler.
Definition: DiagnosticInfo.h:285
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::SampleProfileLoaderBaseImpl::LoopT
typename afdo_detail::IRTraits< BT >::LoopT LoopT
Definition: SampleProfileLoaderBaseImpl.h:87
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::SampleProfileLoaderBaseImpl::BasicBlockT
typename afdo_detail::IRTraits< BT >::BasicBlockT BasicBlockT
Definition: SampleProfileLoaderBaseImpl.h:83
uint32_t
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::SampleProfileLoaderBaseImpl::propagateWeights
void propagateWeights(FunctionT &F)
Propagate weights into edges.
Definition: SampleProfileLoaderBaseImpl.h:724
llvm::OptimizationRemarkAnalysis
Diagnostic information for optimization analysis remarks.
Definition: DiagnosticInfo.h:770
llvm::SampleProfileLoaderBaseImpl::printBlockWeight
void printBlockWeight(raw_ostream &OS, const BasicBlockT *BB) const
Print the weight of block BB on stream OS.
Definition: SampleProfileLoaderBaseImpl.h:244
llvm::SampleProfileLoaderBaseImpl::findEquivalencesFor
void findEquivalencesFor(BasicBlockT *BB1, ArrayRef< BasicBlockT * > Descendants, PostDominatorTreeT *DomTree)
Find equivalence classes for the given block.
Definition: SampleProfileLoaderBaseImpl.h:403
llvm::SampleProfileLoaderBaseImpl::dump
void dump()
Definition: SampleProfileLoaderBaseImpl.h:80
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:254
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
GenericDomTree.h
llvm::SampleProfileLoaderBaseImpl::VisitedEdges
SmallSet< Edge, 32 > VisitedEdges
Set of visited edges during propagation.
Definition: SampleProfileLoaderBaseImpl.h:160
Function.h
llvm::sampleprofutil::SampleCoverageTracker
Definition: SampleProfileLoaderBaseUtil.h:39
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::DebugLoc::getLine
unsigned getLine() const
Definition: DebugLoc.cpp:25
llvm::DILocation::getBaseDiscriminator
unsigned getBaseDiscriminator() const
Returns the base discriminator stored in the discriminator.
Definition: DebugInfoMetadata.h:2215
Instructions.h
llvm::SampleProfileLoaderBaseImpl::Edge
std::pair< const BasicBlockT *, const BasicBlockT * > Edge
Definition: SampleProfileLoaderBaseImpl.h:100
SmallVector.h
llvm::SampleProfileSampleCoverage
cl::opt< unsigned > SampleProfileSampleCoverage
Definition: SampleProfileLoaderBaseUtil.h:34
llvm::ErrorOr::get
reference get()
Definition: ErrorOr.h:150
Dominators.h
llvm::afdo_detail::IRTraits
Definition: SampleProfileLoaderBaseImpl.h:52
llvm::ErrorOr
Represents either an error or a value T.
Definition: ErrorOr.h:56
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::SampleProfileLoaderBaseImpl::EdgeWeights
EdgeWeightMap EdgeWeights
Map edges to their computed weights.
Definition: SampleProfileLoaderBaseImpl.h:154
llvm::SampleProfileLoaderBaseImpl::FunctionT
typename afdo_detail::IRTraits< BT >::FunctionT FunctionT
Definition: SampleProfileLoaderBaseImpl.h:86
llvm::DISubprogram
Subprogram description.
Definition: DebugInfoMetadata.h:1815
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::Function::ProfileCount
Class to represent profile counts.
Definition: Function.h:292
llvm::SampleProfileLoaderBaseImpl::OptRemarkEmitterT
typename afdo_detail::IRTraits< BT >::OptRemarkEmitterT OptRemarkEmitterT
Definition: SampleProfileLoaderBaseImpl.h:90
raw_ostream.h
llvm::SampleProfileLoaderBaseImpl::DILocation2SampleMap
DenseMap< const DILocation *, const FunctionSamples * > DILocation2SampleMap
Definition: SampleProfileLoaderBaseImpl.h:121
SmallSet.h
llvm::SmallPtrSetImpl::insert
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:364
llvm::SampleProfileLoaderBaseImpl::SampleProfileLoaderBaseImpl
SampleProfileLoaderBaseImpl(std::string Name)
Definition: SampleProfileLoaderBaseImpl.h:79
llvm::SampleProfileMaxPropagateIterations
cl::opt< unsigned > SampleProfileMaxPropagateIterations
Definition: SampleProfileLoaderBaseUtil.h:30