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;
284  Discriminator = DIL->getDiscriminator();
285  else
286  Discriminator = DIL->getBaseDiscriminator();
287 
288  ErrorOr<uint64_t> R = FS->findSamplesAt(LineOffset, Discriminator);
289  if (R) {
290  bool FirstMark =
291  CoverageTracker.markSamplesUsed(FS, LineOffset, Discriminator, R.get());
292  if (FirstMark) {
293  ORE->emit([&]() {
294  OptRemarkAnalysisT Remark(DEBUG_TYPE, "AppliedSamples", &Inst);
295  Remark << "Applied " << ore::NV("NumSamples", *R);
296  Remark << " samples from profile (offset: ";
297  Remark << ore::NV("LineOffset", LineOffset);
298  if (Discriminator) {
299  Remark << ".";
300  Remark << ore::NV("Discriminator", Discriminator);
301  }
302  Remark << ")";
303  return Remark;
304  });
305  }
306  LLVM_DEBUG(dbgs() << " " << DLoc.getLine() << "." << Discriminator << ":"
307  << Inst << " (line offset: " << LineOffset << "."
308  << Discriminator << " - weight: " << R.get() << ")\n");
309  }
310  return R;
311 }
312 
313 /// Compute the weight of a basic block.
314 ///
315 /// The weight of basic block \p BB is the maximum weight of all the
316 /// instructions in BB.
317 ///
318 /// \param BB The basic block to query.
319 ///
320 /// \returns the weight for \p BB.
321 template <typename BT>
324  uint64_t Max = 0;
325  bool HasWeight = false;
326  for (auto &I : *BB) {
327  const ErrorOr<uint64_t> &R = getInstWeight(I);
328  if (R) {
329  Max = std::max(Max, R.get());
330  HasWeight = true;
331  }
332  }
333  return HasWeight ? ErrorOr<uint64_t>(Max) : std::error_code();
334 }
335 
336 /// Compute and store the weights of every basic block.
337 ///
338 /// This populates the BlockWeights map by computing
339 /// the weights of every basic block in the CFG.
340 ///
341 /// \param F The function to query.
342 template <typename BT>
344  bool Changed = false;
345  LLVM_DEBUG(dbgs() << "Block weights\n");
346  for (const auto &BB : F) {
347  ErrorOr<uint64_t> Weight = getBlockWeight(&BB);
348  if (Weight) {
349  BlockWeights[&BB] = Weight.get();
350  VisitedBlocks.insert(&BB);
351  Changed = true;
352  }
353  LLVM_DEBUG(printBlockWeight(dbgs(), &BB));
354  }
355 
356  return Changed;
357 }
358 
359 /// Get the FunctionSamples for an instruction.
360 ///
361 /// The FunctionSamples of an instruction \p Inst is the inlined instance
362 /// in which that instruction is coming from. We traverse the inline stack
363 /// of that instruction, and match it with the tree nodes in the profile.
364 ///
365 /// \param Inst Instruction to query.
366 ///
367 /// \returns the FunctionSamples pointer to the inlined instance.
368 template <typename BT>
370  const InstructionT &Inst) const {
371  const DILocation *DIL = Inst.getDebugLoc();
372  if (!DIL)
373  return Samples;
374 
375  auto it = DILocation2SampleMap.try_emplace(DIL, nullptr);
376  if (it.second) {
377  it.first->second = Samples->findFunctionSamples(DIL, Reader->getRemapper());
378  }
379  return it.first->second;
380 }
381 
382 /// Find equivalence classes for the given block.
383 ///
384 /// This finds all the blocks that are guaranteed to execute the same
385 /// number of times as \p BB1. To do this, it traverses all the
386 /// descendants of \p BB1 in the dominator or post-dominator tree.
387 ///
388 /// A block BB2 will be in the same equivalence class as \p BB1 if
389 /// the following holds:
390 ///
391 /// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2
392 /// is a descendant of \p BB1 in the dominator tree, then BB2 should
393 /// dominate BB1 in the post-dominator tree.
394 ///
395 /// 2- Both BB2 and \p BB1 must be in the same loop.
396 ///
397 /// For every block BB2 that meets those two requirements, we set BB2's
398 /// equivalence class to \p BB1.
399 ///
400 /// \param BB1 Block to check.
401 /// \param Descendants Descendants of \p BB1 in either the dom or pdom tree.
402 /// \param DomTree Opposite dominator tree. If \p Descendants is filled
403 /// with blocks from \p BB1's dominator tree, then
404 /// this is the post-dominator tree, and vice versa.
405 template <typename BT>
407  BasicBlockT *BB1, ArrayRef<BasicBlockT *> Descendants,
408  PostDominatorTreeT *DomTree) {
409  const BasicBlockT *EC = EquivalenceClass[BB1];
410  uint64_t Weight = BlockWeights[EC];
411  for (const auto *BB2 : Descendants) {
412  bool IsDomParent = DomTree->dominates(BB2, BB1);
413  bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
414  if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
415  EquivalenceClass[BB2] = EC;
416  // If BB2 is visited, then the entire EC should be marked as visited.
417  if (VisitedBlocks.count(BB2)) {
418  VisitedBlocks.insert(EC);
419  }
420 
421  // If BB2 is heavier than BB1, make BB2 have the same weight
422  // as BB1.
423  //
424  // Note that we don't worry about the opposite situation here
425  // (when BB2 is lighter than BB1). We will deal with this
426  // during the propagation phase. Right now, we just want to
427  // make sure that BB1 has the largest weight of all the
428  // members of its equivalence set.
429  Weight = std::max(Weight, BlockWeights[BB2]);
430  }
431  }
432  const BasicBlockT *EntryBB = getEntryBB(EC->getParent());
433  if (EC == EntryBB) {
434  BlockWeights[EC] = Samples->getHeadSamples() + 1;
435  } else {
436  BlockWeights[EC] = Weight;
437  }
438 }
439 
440 /// Find equivalence classes.
441 ///
442 /// Since samples may be missing from blocks, we can fill in the gaps by setting
443 /// the weights of all the blocks in the same equivalence class to the same
444 /// weight. To compute the concept of equivalence, we use dominance and loop
445 /// information. Two blocks B1 and B2 are in the same equivalence class if B1
446 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
447 ///
448 /// \param F The function to query.
449 template <typename BT>
451  SmallVector<BasicBlockT *, 8> DominatedBBs;
452  LLVM_DEBUG(dbgs() << "\nBlock equivalence classes\n");
453  // Find equivalence sets based on dominance and post-dominance information.
454  for (auto &BB : F) {
455  BasicBlockT *BB1 = &BB;
456 
457  // Compute BB1's equivalence class once.
458  if (EquivalenceClass.count(BB1)) {
459  LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1));
460  continue;
461  }
462 
463  // By default, blocks are in their own equivalence class.
464  EquivalenceClass[BB1] = BB1;
465 
466  // Traverse all the blocks dominated by BB1. We are looking for
467  // every basic block BB2 such that:
468  //
469  // 1- BB1 dominates BB2.
470  // 2- BB2 post-dominates BB1.
471  // 3- BB1 and BB2 are in the same loop nest.
472  //
473  // If all those conditions hold, it means that BB2 is executed
474  // as many times as BB1, so they are placed in the same equivalence
475  // class by making BB2's equivalence class be BB1.
476  DominatedBBs.clear();
477  DT->getDescendants(BB1, DominatedBBs);
478  findEquivalencesFor(BB1, DominatedBBs, PDT.get());
479 
480  LLVM_DEBUG(printBlockEquivalence(dbgs(), BB1));
481  }
482 
483  // Assign weights to equivalence classes.
484  //
485  // All the basic blocks in the same equivalence class will execute
486  // the same number of times. Since we know that the head block in
487  // each equivalence class has the largest weight, assign that weight
488  // to all the blocks in that equivalence class.
489  LLVM_DEBUG(
490  dbgs() << "\nAssign the same weight to all blocks in the same class\n");
491  for (auto &BI : F) {
492  const BasicBlockT *BB = &BI;
493  const BasicBlockT *EquivBB = EquivalenceClass[BB];
494  if (BB != EquivBB)
495  BlockWeights[BB] = BlockWeights[EquivBB];
496  LLVM_DEBUG(printBlockWeight(dbgs(), BB));
497  }
498 }
499 
500 /// Visit the given edge to decide if it has a valid weight.
501 ///
502 /// If \p E has not been visited before, we copy to \p UnknownEdge
503 /// and increment the count of unknown edges.
504 ///
505 /// \param E Edge to visit.
506 /// \param NumUnknownEdges Current number of unknown edges.
507 /// \param UnknownEdge Set if E has not been visited before.
508 ///
509 /// \returns E's weight, if known. Otherwise, return 0.
510 template <typename BT>
512  unsigned *NumUnknownEdges,
513  Edge *UnknownEdge) {
514  if (!VisitedEdges.count(E)) {
515  (*NumUnknownEdges)++;
516  *UnknownEdge = E;
517  return 0;
518  }
519 
520  return EdgeWeights[E];
521 }
522 
523 /// Propagate weights through incoming/outgoing edges.
524 ///
525 /// If the weight of a basic block is known, and there is only one edge
526 /// with an unknown weight, we can calculate the weight of that edge.
527 ///
528 /// Similarly, if all the edges have a known count, we can calculate the
529 /// count of the basic block, if needed.
530 ///
531 /// \param F Function to process.
532 /// \param UpdateBlockCount Whether we should update basic block counts that
533 /// has already been annotated.
534 ///
535 /// \returns True if new weights were assigned to edges or blocks.
536 template <typename BT>
538  FunctionT &F, bool UpdateBlockCount) {
539  bool Changed = false;
540  LLVM_DEBUG(dbgs() << "\nPropagation through edges\n");
541  for (const auto &BI : F) {
542  const BasicBlockT *BB = &BI;
543  const BasicBlockT *EC = EquivalenceClass[BB];
544 
545  // Visit all the predecessor and successor edges to determine
546  // which ones have a weight assigned already. Note that it doesn't
547  // matter that we only keep track of a single unknown edge. The
548  // only case we are interested in handling is when only a single
549  // edge is unknown (see setEdgeOrBlockWeight).
550  for (unsigned i = 0; i < 2; i++) {
551  uint64_t TotalWeight = 0;
552  unsigned NumUnknownEdges = 0, NumTotalEdges = 0;
553  Edge UnknownEdge, SelfReferentialEdge, SingleEdge;
554 
555  if (i == 0) {
556  // First, visit all predecessor edges.
557  NumTotalEdges = Predecessors[BB].size();
558  for (auto *Pred : Predecessors[BB]) {
559  Edge E = std::make_pair(Pred, BB);
560  TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);
561  if (E.first == E.second)
562  SelfReferentialEdge = E;
563  }
564  if (NumTotalEdges == 1) {
565  SingleEdge = std::make_pair(Predecessors[BB][0], BB);
566  }
567  } else {
568  // On the second round, visit all successor edges.
569  NumTotalEdges = Successors[BB].size();
570  for (auto *Succ : Successors[BB]) {
571  Edge E = std::make_pair(BB, Succ);
572  TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);
573  }
574  if (NumTotalEdges == 1) {
575  SingleEdge = std::make_pair(BB, Successors[BB][0]);
576  }
577  }
578 
579  // After visiting all the edges, there are three cases that we
580  // can handle immediately:
581  //
582  // - All the edge weights are known (i.e., NumUnknownEdges == 0).
583  // In this case, we simply check that the sum of all the edges
584  // is the same as BB's weight. If not, we change BB's weight
585  // to match. Additionally, if BB had not been visited before,
586  // we mark it visited.
587  //
588  // - Only one edge is unknown and BB has already been visited.
589  // In this case, we can compute the weight of the edge by
590  // subtracting the total block weight from all the known
591  // edge weights. If the edges weight more than BB, then the
592  // edge of the last remaining edge is set to zero.
593  //
594  // - There exists a self-referential edge and the weight of BB is
595  // known. In this case, this edge can be based on BB's weight.
596  // We add up all the other known edges and set the weight on
597  // the self-referential edge as we did in the previous case.
598  //
599  // In any other case, we must continue iterating. Eventually,
600  // all edges will get a weight, or iteration will stop when
601  // it reaches SampleProfileMaxPropagateIterations.
602  if (NumUnknownEdges <= 1) {
603  uint64_t &BBWeight = BlockWeights[EC];
604  if (NumUnknownEdges == 0) {
605  if (!VisitedBlocks.count(EC)) {
606  // If we already know the weight of all edges, the weight of the
607  // basic block can be computed. It should be no larger than the sum
608  // of all edge weights.
609  if (TotalWeight > BBWeight) {
610  BBWeight = TotalWeight;
611  Changed = true;
612  LLVM_DEBUG(dbgs() << "All edge weights for " << BB->getName()
613  << " known. Set weight for block: ";
614  printBlockWeight(dbgs(), BB););
615  }
616  } else if (NumTotalEdges == 1 &&
617  EdgeWeights[SingleEdge] < BlockWeights[EC]) {
618  // If there is only one edge for the visited basic block, use the
619  // block weight to adjust edge weight if edge weight is smaller.
620  EdgeWeights[SingleEdge] = BlockWeights[EC];
621  Changed = true;
622  }
623  } else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
624  // If there is a single unknown edge and the block has been
625  // visited, then we can compute E's weight.
626  if (BBWeight >= TotalWeight)
627  EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
628  else
629  EdgeWeights[UnknownEdge] = 0;
630  const BasicBlockT *OtherEC;
631  if (i == 0)
632  OtherEC = EquivalenceClass[UnknownEdge.first];
633  else
634  OtherEC = EquivalenceClass[UnknownEdge.second];
635  // Edge weights should never exceed the BB weights it connects.
636  if (VisitedBlocks.count(OtherEC) &&
637  EdgeWeights[UnknownEdge] > BlockWeights[OtherEC])
638  EdgeWeights[UnknownEdge] = BlockWeights[OtherEC];
639  VisitedEdges.insert(UnknownEdge);
640  Changed = true;
641  LLVM_DEBUG(dbgs() << "Set weight for edge: ";
642  printEdgeWeight(dbgs(), UnknownEdge));
643  }
644  } else if (VisitedBlocks.count(EC) && BlockWeights[EC] == 0) {
645  // If a block Weights 0, all its in/out edges should weight 0.
646  if (i == 0) {
647  for (auto *Pred : Predecessors[BB]) {
648  Edge E = std::make_pair(Pred, BB);
649  EdgeWeights[E] = 0;
650  VisitedEdges.insert(E);
651  }
652  } else {
653  for (auto *Succ : Successors[BB]) {
654  Edge E = std::make_pair(BB, Succ);
655  EdgeWeights[E] = 0;
656  VisitedEdges.insert(E);
657  }
658  }
659  } else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
660  uint64_t &BBWeight = BlockWeights[BB];
661  // We have a self-referential edge and the weight of BB is known.
662  if (BBWeight >= TotalWeight)
663  EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
664  else
665  EdgeWeights[SelfReferentialEdge] = 0;
666  VisitedEdges.insert(SelfReferentialEdge);
667  Changed = true;
668  LLVM_DEBUG(dbgs() << "Set self-referential edge weight to: ";
669  printEdgeWeight(dbgs(), SelfReferentialEdge));
670  }
671  if (UpdateBlockCount && !VisitedBlocks.count(EC) && TotalWeight > 0) {
672  BlockWeights[EC] = TotalWeight;
673  VisitedBlocks.insert(EC);
674  Changed = true;
675  }
676  }
677  }
678 
679  return Changed;
680 }
681 
682 /// Build in/out edge lists for each basic block in the CFG.
683 ///
684 /// We are interested in unique edges. If a block B1 has multiple
685 /// edges to another block B2, we only add a single B1->B2 edge.
686 template <typename BT>
688  for (auto &BI : F) {
689  BasicBlockT *B1 = &BI;
690 
691  // Add predecessors for B1.
693  if (!Predecessors[B1].empty())
694  llvm_unreachable("Found a stale predecessors list in a basic block.");
695  for (BasicBlockT *B2 : predecessors(B1))
696  if (Visited.insert(B2).second)
697  Predecessors[B1].push_back(B2);
698 
699  // Add successors for B1.
700  Visited.clear();
701  if (!Successors[B1].empty())
702  llvm_unreachable("Found a stale successors list in a basic block.");
703  for (BasicBlockT *B2 : successors(B1))
704  if (Visited.insert(B2).second)
705  Successors[B1].push_back(B2);
706  }
707 }
708 
709 /// Propagate weights into edges
710 ///
711 /// The following rules are applied to every block BB in the CFG:
712 ///
713 /// - If BB has a single predecessor/successor, then the weight
714 /// of that edge is the weight of the block.
715 ///
716 /// - If all incoming or outgoing edges are known except one, and the
717 /// weight of the block is already known, the weight of the unknown
718 /// edge will be the weight of the block minus the sum of all the known
719 /// edges. If the sum of all the known edges is larger than BB's weight,
720 /// we set the unknown edge weight to zero.
721 ///
722 /// - If there is a self-referential edge, and the weight of the block is
723 /// known, the weight for that edge is set to the weight of the block
724 /// minus the weight of the other incoming edges to that block (if
725 /// known).
726 template <typename BT>
728  bool Changed = true;
729  unsigned I = 0;
730 
731  // If BB weight is larger than its corresponding loop's header BB weight,
732  // use the BB weight to replace the loop header BB weight.
733  for (auto &BI : F) {
734  BasicBlockT *BB = &BI;
735  LoopT *L = LI->getLoopFor(BB);
736  if (!L) {
737  continue;
738  }
739  BasicBlockT *Header = L->getHeader();
740  if (Header && BlockWeights[BB] > BlockWeights[Header]) {
741  BlockWeights[Header] = BlockWeights[BB];
742  }
743  }
744 
745  // Before propagation starts, build, for each block, a list of
746  // unique predecessors and successors. This is necessary to handle
747  // identical edges in multiway branches. Since we visit all blocks and all
748  // edges of the CFG, it is cleaner to build these lists once at the start
749  // of the pass.
750  buildEdges(F);
751 
752  // Propagate until we converge or we go past the iteration limit.
753  while (Changed && I++ < SampleProfileMaxPropagateIterations) {
754  Changed = propagateThroughEdges(F, false);
755  }
756 
757  // The first propagation propagates BB counts from annotated BBs to unknown
758  // BBs. The 2nd propagation pass resets edges weights, and use all BB weights
759  // to propagate edge weights.
760  VisitedEdges.clear();
761  Changed = true;
762  while (Changed && I++ < SampleProfileMaxPropagateIterations) {
763  Changed = propagateThroughEdges(F, false);
764  }
765 
766  // The 3rd propagation pass allows adjust annotated BB weights that are
767  // obviously wrong.
768  Changed = true;
769  while (Changed && I++ < SampleProfileMaxPropagateIterations) {
770  Changed = propagateThroughEdges(F, true);
771  }
772 }
773 
774 /// Generate branch weight metadata for all branches in \p F.
775 ///
776 /// Branch weights are computed out of instruction samples using a
777 /// propagation heuristic. Propagation proceeds in 3 phases:
778 ///
779 /// 1- Assignment of block weights. All the basic blocks in the function
780 /// are initial assigned the same weight as their most frequently
781 /// executed instruction.
782 ///
783 /// 2- Creation of equivalence classes. Since samples may be missing from
784 /// blocks, we can fill in the gaps by setting the weights of all the
785 /// blocks in the same equivalence class to the same weight. To compute
786 /// the concept of equivalence, we use dominance and loop information.
787 /// Two blocks B1 and B2 are in the same equivalence class if B1
788 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
789 ///
790 /// 3- Propagation of block weights into edges. This uses a simple
791 /// propagation heuristic. The following rules are applied to every
792 /// block BB in the CFG:
793 ///
794 /// - If BB has a single predecessor/successor, then the weight
795 /// of that edge is the weight of the block.
796 ///
797 /// - If all the edges are known except one, and the weight of the
798 /// block is already known, the weight of the unknown edge will
799 /// be the weight of the block minus the sum of all the known
800 /// edges. If the sum of all the known edges is larger than BB's weight,
801 /// we set the unknown edge weight to zero.
802 ///
803 /// - If there is a self-referential edge, and the weight of the block is
804 /// known, the weight for that edge is set to the weight of the block
805 /// minus the weight of the other incoming edges to that block (if
806 /// known).
807 ///
808 /// Since this propagation is not guaranteed to finalize for every CFG, we
809 /// only allow it to proceed for a limited number of iterations (controlled
810 /// by -sample-profile-max-propagate-iterations).
811 ///
812 /// FIXME: Try to replace this propagation heuristic with a scheme
813 /// that is guaranteed to finalize. A work-list approach similar to
814 /// the standard value propagation algorithm used by SSA-CCP might
815 /// work here.
816 ///
817 /// \param F The function to query.
818 ///
819 /// \returns true if \p F was modified. Returns false, otherwise.
820 template <typename BT>
822  FunctionT &F, const DenseSet<GlobalValue::GUID> &InlinedGUIDs) {
823  bool Changed = (InlinedGUIDs.size() != 0);
824 
825  // Compute basic block weights.
826  Changed |= computeBlockWeights(F);
827 
828  if (Changed) {
829  // Add an entry count to the function using the samples gathered at the
830  // function entry.
831  // Sets the GUIDs that are inlined in the profiled binary. This is used
832  // for ThinLink to make correct liveness analysis, and also make the IR
833  // match the profiled binary before annotation.
834  getFunction(F).setEntryCount(
835  ProfileCount(Samples->getHeadSamples() + 1, Function::PCT_Real),
836  &InlinedGUIDs);
837 
838  // Compute dominance and loop info needed for propagation.
839  computeDominanceAndLoopInfo(F);
840 
841  // Find equivalence classes.
842  findEquivalenceClasses(F);
843 
844  // Propagate weights to all edges.
845  propagateWeights(F);
846  }
847 
848  return Changed;
849 }
850 
851 template <typename BT>
853  // If coverage checking was requested, compute it now.
854  const Function &Func = getFunction(F);
856  unsigned Used = CoverageTracker.countUsedRecords(Samples, PSI);
857  unsigned Total = CoverageTracker.countBodyRecords(Samples, PSI);
858  unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
859  if (Coverage < SampleProfileRecordCoverage) {
860  Func.getContext().diagnose(DiagnosticInfoSampleProfile(
861  Func.getSubprogram()->getFilename(), getFunctionLoc(F),
862  Twine(Used) + " of " + Twine(Total) + " available profile records (" +
863  Twine(Coverage) + "%) were applied",
864  DS_Warning));
865  }
866  }
867 
869  uint64_t Used = CoverageTracker.getTotalUsedSamples();
870  uint64_t Total = CoverageTracker.countBodySamples(Samples, PSI);
871  unsigned Coverage = CoverageTracker.computeCoverage(Used, Total);
872  if (Coverage < SampleProfileSampleCoverage) {
873  Func.getContext().diagnose(DiagnosticInfoSampleProfile(
874  Func.getSubprogram()->getFilename(), getFunctionLoc(F),
875  Twine(Used) + " of " + Twine(Total) + " available profile samples (" +
876  Twine(Coverage) + "%) were applied",
877  DS_Warning));
878  }
879  }
880 }
881 
882 /// Get the line number for the function header.
883 ///
884 /// This looks up function \p F in the current compilation unit and
885 /// retrieves the line number where the function is defined. This is
886 /// line 0 for all the samples read from the profile file. Every line
887 /// number is relative to this line.
888 ///
889 /// \param F Function object to query.
890 ///
891 /// \returns the line number where \p F is defined. If it returns 0,
892 /// it means that there is no debug information available for \p F.
893 template <typename BT>
895  const Function &Func = getFunction(F);
896  if (DISubprogram *S = Func.getSubprogram())
897  return S->getLine();
898 
899  if (NoWarnSampleUnused)
900  return 0;
901 
902  // If the start of \p F is missing, emit a diagnostic to inform the user
903  // about the missed opportunity.
904  Func.getContext().diagnose(DiagnosticInfoSampleProfile(
905  "No debug information found in function " + Func.getName() +
906  ": Function profile not used",
907  DS_Warning));
908  return 0;
909 }
910 
911 template <typename BT>
913  FunctionT &F) {
914  DT.reset(new DominatorTreeT);
915  DT->recalculate(F);
916 
917  PDT.reset(new PostDominatorTree(F));
918 
919  LI.reset(new LoopInfoT);
920  LI->analyze(*DT);
921 }
922 
923 #undef DEBUG_TYPE
924 
925 } // namespace llvm
926 #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
---------------------— PointerInfo ------------------------------------—
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
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
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:511
llvm::Function
Definition: Function.h:61
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:255
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:181
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::EnableFSDiscriminator
cl::opt< bool > EnableFSDiscriminator
Definition: TargetPassConfig.cpp:345
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1562
DenseMap.h
Module.h
llvm::SmallSet< Edge, 32 >
llvm::SmallPtrSet< const BasicBlockT *, 32 >
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::NoWarnSampleUnused
cl::opt< bool > NoWarnSampleUnused
Definition: SampleProfileLoaderBaseUtil.h:37
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
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:180
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:163
Instruction.h
CommandLine.h
llvm::SampleProfileLoaderBaseImpl::getBlockWeight
ErrorOr< uint64_t > getBlockWeight(const BasicBlockT *BB)
Compute the weight of a basic block.
Definition: SampleProfileLoaderBaseImpl.h:323
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:537
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::X86AS::FS
@ FS
Definition: X86.h:188
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:912
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
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:369
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:852
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:894
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:821
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:343
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:549
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:35
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:450
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:71
llvm::SampleProfileLoaderBaseImpl::buildEdges
void buildEdges(FunctionT &F)
Build in/out edge lists for each basic block in the CFG.
Definition: SampleProfileLoaderBaseImpl.h:687
llvm::sampleprof::FunctionSamples::getOffset
static unsigned getOffset(const DILocation *DIL)
Returns the line offset to the start line of the subprogram.
Definition: SampleProf.cpp:201
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:1083
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:727
llvm::OptimizationRemarkAnalysis
Diagnostic information for optimization analysis remarks.
Definition: DiagnosticInfo.h:775
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:406
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:83
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:41
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:2202
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:36
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:1802
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:32