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