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