lib/Transforms/Scalar/SampleProfile.cpp

   1 //===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===//
   2 //
   3 //                      The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the SampleProfileLoader transformation. This pass
  11 // reads a profile file generated by a sampling profiler (e.g. Linux Perf -
  12 // http://perf.wiki.kernel.org/) and generates IR metadata to reflect the
  13 // profile information in the given profile.
  14 //
  15 // This pass generates branch weight annotations on the IR:
  16 //
  17 // - prof: Represents branch weights. This annotation is added to branches
  18 //      to indicate the weights of each edge coming out of the branch.
  19 //      The weight of each edge is the weight of the target block for
  20 //      that edge. The weight of a block B is computed as the maximum
  21 //      number of samples found in B.
  22 //
  23 //===----------------------------------------------------------------------===//
  24
  25 #include "llvm/Transforms/Scalar.h"
  26 #include "llvm/ADT/DenseMap.h"
  27 #include "llvm/ADT/SmallPtrSet.h"
  28 #include "llvm/ADT/SmallSet.h"
  29 #include "llvm/ADT/StringRef.h"
  30 #include "llvm/Analysis/LoopInfo.h"
  31 #include "llvm/Analysis/PostDominators.h"
  32 #include "llvm/IR/Constants.h"
  33 #include "llvm/IR/DebugInfo.h"
  34 #include "llvm/IR/DiagnosticInfo.h"
  35 #include "llvm/IR/Dominators.h"
  36 #include "llvm/IR/Function.h"
  37 #include "llvm/IR/InstIterator.h"
  38 #include "llvm/IR/Instructions.h"
  39 #include "llvm/IR/LLVMContext.h"
  40 #include "llvm/IR/MDBuilder.h"
  41 #include "llvm/IR/Metadata.h"
  42 #include "llvm/IR/Module.h"
  43 #include "llvm/Pass.h"
  44 #include "llvm/ProfileData/SampleProfReader.h"
  45 #include "llvm/Support/CommandLine.h"
  46 #include "llvm/Support/Debug.h"
  47 #include "llvm/Support/raw_ostream.h"
  48 #include <cctype>
  49
  50 using namespace llvm;
  51 using namespace sampleprof;
  52
  53 #define DEBUG_TYPE "sample-profile"
  54
  55 // Command line option to specify the file to read samples from. This is
  56 // mainly used for debugging.
  57 static cl::opt<std::string> SampleProfileFile(
  58     "sample-profile-file", cl::init(""), cl::value_desc("filename"),
  59     cl::desc("Profile file loaded by -sample-profile"), cl::Hidden);
  60 static cl::opt<unsigned> SampleProfileMaxPropagateIterations(
  61     "sample-profile-max-propagate-iterations", cl::init(100),
  62     cl::desc("Maximum number of iterations to go through when propagating "
  63              "sample block/edge weights through the CFG."));
  64
  65 namespace {
  66 typedef DenseMap<BasicBlock *, unsigned> BlockWeightMap;
  67 typedef DenseMap<BasicBlock *, BasicBlock *> EquivalenceClassMap;
  68 typedef std::pair<BasicBlock *, BasicBlock *> Edge;
  69 typedef DenseMap<Edge, unsigned> EdgeWeightMap;
  70 typedef DenseMap<BasicBlock *, SmallVector<BasicBlock *, 8>> BlockEdgeMap;
  71
  72 /// \brief Sample profile pass.
  73 ///
  74 /// This pass reads profile data from the file specified by
  75 /// -sample-profile-file and annotates every affected function with the
  76 /// profile information found in that file.
  77 class SampleProfileLoader : public FunctionPass {
  78 public:
  79   // Class identification, replacement for typeinfo
  80   static char ID;
  81
  82   SampleProfileLoader(StringRef Name = SampleProfileFile)
  83       : FunctionPass(ID), DT(nullptr), PDT(nullptr), LI(nullptr), Ctx(nullptr),
  84         Reader(), Samples(nullptr), Filename(Name), ProfileIsValid(false) {
  85     initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry());
  86   }
  87
  88   bool doInitialization(Module &M) override;
  89
  90   void dump() { Reader->dump(); }
  91
  92   const char *getPassName() const override { return "Sample profile pass"; }
  93
  94   bool runOnFunction(Function &F) override;
  95
  96   void getAnalysisUsage(AnalysisUsage &AU) const override {
  97     AU.setPreservesCFG();
  98     AU.addRequired<LoopInfo>();
  99     AU.addRequired<DominatorTreeWrapperPass>();
 100     AU.addRequired<PostDominatorTree>();
 101   }
 102
 103 protected:
 104   unsigned getFunctionLoc(Function &F);
 105   bool emitAnnotations(Function &F);
 106   unsigned getInstWeight(Instruction &I);
 107   unsigned getBlockWeight(BasicBlock *B);
 108   void printEdgeWeight(raw_ostream &OS, Edge E);
 109   void printBlockWeight(raw_ostream &OS, BasicBlock *BB);
 110   void printBlockEquivalence(raw_ostream &OS, BasicBlock *BB);
 111   bool computeBlockWeights(Function &F);
 112   void findEquivalenceClasses(Function &F);
 113   void findEquivalencesFor(BasicBlock *BB1,
 114                            SmallVector<BasicBlock *, 8> Descendants,
 115                            DominatorTreeBase<BasicBlock> *DomTree);
 116   void propagateWeights(Function &F);
 117   unsigned visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
 118   void buildEdges(Function &F);
 119   bool propagateThroughEdges(Function &F);
 120
 121   /// \brief Line number for the function header. Used to compute absolute
 122   /// line numbers from the relative line numbers found in the profile.
 123   unsigned HeaderLineno;
 124
 125   /// \brief Map basic blocks to their computed weights.
 126   ///
 127   /// The weight of a basic block is defined to be the maximum
 128   /// of all the instruction weights in that block.
 129   BlockWeightMap BlockWeights;
 130
 131   /// \brief Map edges to their computed weights.
 132   ///
 133   /// Edge weights are computed by propagating basic block weights in
 134   /// SampleProfile::propagateWeights.
 135   EdgeWeightMap EdgeWeights;
 136
 137   /// \brief Set of visited blocks during propagation.
 138   SmallPtrSet<BasicBlock *, 128> VisitedBlocks;
 139
 140   /// \brief Set of visited edges during propagation.
 141   SmallSet<Edge, 128> VisitedEdges;
 142
 143   /// \brief Equivalence classes for block weights.
 144   ///
 145   /// Two blocks BB1 and BB2 are in the same equivalence class if they
 146   /// dominate and post-dominate each other, and they are in the same loop
 147   /// nest. When this happens, the two blocks are guaranteed to execute
 148   /// the same number of times.
 149   EquivalenceClassMap EquivalenceClass;
 150
 151   /// \brief Dominance, post-dominance and loop information.
 152   DominatorTree *DT;
 153   PostDominatorTree *PDT;
 154   LoopInfo *LI;
 155
 156   /// \brief Predecessors for each basic block in the CFG.
 157   BlockEdgeMap Predecessors;
 158
 159   /// \brief Successors for each basic block in the CFG.
 160   BlockEdgeMap Successors;
 161
 162   /// \brief LLVM context holding the debug data we need.
 163   LLVMContext *Ctx;
 164
 165   /// \brief Profile reader object.
 166   std::unique_ptr<SampleProfileReader> Reader;
 167
 168   /// \brief Samples collected for the body of this function.
 169   FunctionSamples *Samples;
 170
 171   /// \brief Name of the profile file to load.
 172   StringRef Filename;
 173
 174   /// \brief Flag indicating whether the profile input loaded successfully.
 175   bool ProfileIsValid;
 176 };
 177 }
 178
 179 /// \brief Print the weight of edge \p E on stream \p OS.
 180 ///
 181 /// \param OS  Stream to emit the output to.
 182 /// \param E  Edge to print.
 183 void SampleProfileLoader::printEdgeWeight(raw_ostream &OS, Edge E) {
 184   OS << "weight[" << E.first->getName() << "->" << E.second->getName()
 185      << "]: " << EdgeWeights[E] << "\n";
 186 }
 187
 188 /// \brief Print the equivalence class of block \p BB on stream \p OS.
 189 ///
 190 /// \param OS  Stream to emit the output to.
 191 /// \param BB  Block to print.
 192 void SampleProfileLoader::printBlockEquivalence(raw_ostream &OS,
 193                                                 BasicBlock *BB) {
 194   BasicBlock *Equiv = EquivalenceClass[BB];
 195   OS << "equivalence[" << BB->getName()
 196      << "]: " << ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE") << "\n";
 197 }
 198
 199 /// \brief Print the weight of block \p BB on stream \p OS.
 200 ///
 201 /// \param OS  Stream to emit the output to.
 202 /// \param BB  Block to print.
 203 void SampleProfileLoader::printBlockWeight(raw_ostream &OS, BasicBlock *BB) {
 204   OS << "weight[" << BB->getName() << "]: " << BlockWeights[BB] << "\n";
 205 }
 206
 207 /// \brief Get the weight for an instruction.
 208 ///
 209 /// The "weight" of an instruction \p Inst is the number of samples
 210 /// collected on that instruction at runtime. To retrieve it, we
 211 /// need to compute the line number of \p Inst relative to the start of its
 212 /// function. We use HeaderLineno to compute the offset. We then
 213 /// look up the samples collected for \p Inst using BodySamples.
 214 ///
 215 /// \param Inst Instruction to query.
 216 ///
 217 /// \returns The profiled weight of I.
 218 unsigned SampleProfileLoader::getInstWeight(Instruction &Inst) {
 219   DebugLoc DLoc = Inst.getDebugLoc();
 220   unsigned Lineno = DLoc.getLine();
 221   if (Lineno < HeaderLineno)
 222     return 0;
 223
 224   DILocation DIL(DLoc.getAsMDNode(*Ctx));
 225   int LOffset = Lineno - HeaderLineno;
 226   unsigned Discriminator = DIL.getDiscriminator();
 227   unsigned Weight = Samples->samplesAt(LOffset, Discriminator);
 228   DEBUG(dbgs() << "    " << Lineno << "." << Discriminator << ":" << Inst
 229                << " (line offset: " << LOffset << "." << Discriminator
 230                << " - weight: " << Weight << ")\n");
 231   return Weight;
 232 }
 233
 234 /// \brief Compute the weight of a basic block.
 235 ///
 236 /// The weight of basic block \p B is the maximum weight of all the
 237 /// instructions in B. The weight of \p B is computed and cached in
 238 /// the BlockWeights map.
 239 ///
 240 /// \param B The basic block to query.
 241 ///
 242 /// \returns The computed weight of B.
 243 unsigned SampleProfileLoader::getBlockWeight(BasicBlock *B) {
 244   // If we've computed B's weight before, return it.
 245   std::pair<BlockWeightMap::iterator, bool> Entry =
 246       BlockWeights.insert(std::make_pair(B, 0));
 247   if (!Entry.second)
 248     return Entry.first->second;
 249
 250   // Otherwise, compute and cache B's weight.
 251   unsigned Weight = 0;
 252   for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
 253     unsigned InstWeight = getInstWeight(*I);
 254     if (InstWeight > Weight)
 255       Weight = InstWeight;
 256   }
 257   Entry.first->second = Weight;
 258   return Weight;
 259 }
 260
 261 /// \brief Compute and store the weights of every basic block.
 262 ///
 263 /// This populates the BlockWeights map by computing
 264 /// the weights of every basic block in the CFG.
 265 ///
 266 /// \param F The function to query.
 267 bool SampleProfileLoader::computeBlockWeights(Function &F) {
 268   bool Changed = false;
 269   DEBUG(dbgs() << "Block weights\n");
 270   for (Function::iterator B = F.begin(), E = F.end(); B != E; ++B) {
 271     unsigned Weight = getBlockWeight(B);
 272     Changed |= (Weight > 0);
 273     DEBUG(printBlockWeight(dbgs(), B));
 274   }
 275
 276   return Changed;
 277 }
 278
 279 /// \brief Find equivalence classes for the given block.
 280 ///
 281 /// This finds all the blocks that are guaranteed to execute the same
 282 /// number of times as \p BB1. To do this, it traverses all the the
 283 /// descendants of \p BB1 in the dominator or post-dominator tree.
 284 ///
 285 /// A block BB2 will be in the same equivalence class as \p BB1 if
 286 /// the following holds:
 287 ///
 288 /// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2
 289 ///    is a descendant of \p BB1 in the dominator tree, then BB2 should
 290 ///    dominate BB1 in the post-dominator tree.
 291 ///
 292 /// 2- Both BB2 and \p BB1 must be in the same loop.
 293 ///
 294 /// For every block BB2 that meets those two requirements, we set BB2's
 295 /// equivalence class to \p BB1.
 296 ///
 297 /// \param BB1  Block to check.
 298 /// \param Descendants  Descendants of \p BB1 in either the dom or pdom tree.
 299 /// \param DomTree  Opposite dominator tree. If \p Descendants is filled
 300 ///                 with blocks from \p BB1's dominator tree, then
 301 ///                 this is the post-dominator tree, and vice versa.
 302 void SampleProfileLoader::findEquivalencesFor(
 303     BasicBlock *BB1, SmallVector<BasicBlock *, 8> Descendants,
 304     DominatorTreeBase<BasicBlock> *DomTree) {
 305   for (SmallVectorImpl<BasicBlock *>::iterator I = Descendants.begin(),
 306                                                E = Descendants.end();
 307        I != E; ++I) {
 308     BasicBlock *BB2 = *I;
 309     bool IsDomParent = DomTree->dominates(BB2, BB1);
 310     bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
 311     if (BB1 != BB2 && VisitedBlocks.insert(BB2) && IsDomParent &&
 312         IsInSameLoop) {
 313       EquivalenceClass[BB2] = BB1;
 314
 315       // If BB2 is heavier than BB1, make BB2 have the same weight
 316       // as BB1.
 317       //
 318       // Note that we don't worry about the opposite situation here
 319       // (when BB2 is lighter than BB1). We will deal with this
 320       // during the propagation phase. Right now, we just want to
 321       // make sure that BB1 has the largest weight of all the
 322       // members of its equivalence set.
 323       unsigned &BB1Weight = BlockWeights[BB1];
 324       unsigned &BB2Weight = BlockWeights[BB2];
 325       BB1Weight = std::max(BB1Weight, BB2Weight);
 326     }
 327   }
 328 }
 329
 330 /// \brief Find equivalence classes.
 331 ///
 332 /// Since samples may be missing from blocks, we can fill in the gaps by setting
 333 /// the weights of all the blocks in the same equivalence class to the same
 334 /// weight. To compute the concept of equivalence, we use dominance and loop
 335 /// information. Two blocks B1 and B2 are in the same equivalence class if B1
 336 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
 337 ///
 338 /// \param F The function to query.
 339 void SampleProfileLoader::findEquivalenceClasses(Function &F) {
 340   SmallVector<BasicBlock *, 8> DominatedBBs;
 341   DEBUG(dbgs() << "\nBlock equivalence classes\n");
 342   // Find equivalence sets based on dominance and post-dominance information.
 343   for (Function::iterator B = F.begin(), E = F.end(); B != E; ++B) {
 344     BasicBlock *BB1 = B;
 345
 346     // Compute BB1's equivalence class once.
 347     if (EquivalenceClass.count(BB1)) {
 348       DEBUG(printBlockEquivalence(dbgs(), BB1));
 349       continue;
 350     }
 351
 352     // By default, blocks are in their own equivalence class.
 353     EquivalenceClass[BB1] = BB1;
 354
 355     // Traverse all the blocks dominated by BB1. We are looking for
 356     // every basic block BB2 such that:
 357     //
 358     // 1- BB1 dominates BB2.
 359     // 2- BB2 post-dominates BB1.
 360     // 3- BB1 and BB2 are in the same loop nest.
 361     //
 362     // If all those conditions hold, it means that BB2 is executed
 363     // as many times as BB1, so they are placed in the same equivalence
 364     // class by making BB2's equivalence class be BB1.
 365     DominatedBBs.clear();
 366     DT->getDescendants(BB1, DominatedBBs);
 367     findEquivalencesFor(BB1, DominatedBBs, PDT->DT);
 368
 369     // Repeat the same logic for all the blocks post-dominated by BB1.
 370     // We are looking for every basic block BB2 such that:
 371     //
 372     // 1- BB1 post-dominates BB2.
 373     // 2- BB2 dominates BB1.
 374     // 3- BB1 and BB2 are in the same loop nest.
 375     //
 376     // If all those conditions hold, BB2's equivalence class is BB1.
 377     DominatedBBs.clear();
 378     PDT->getDescendants(BB1, DominatedBBs);
 379     findEquivalencesFor(BB1, DominatedBBs, DT);
 380
 381     DEBUG(printBlockEquivalence(dbgs(), BB1));
 382   }
 383
 384   // Assign weights to equivalence classes.
 385   //
 386   // All the basic blocks in the same equivalence class will execute
 387   // the same number of times. Since we know that the head block in
 388   // each equivalence class has the largest weight, assign that weight
 389   // to all the blocks in that equivalence class.
 390   DEBUG(dbgs() << "\nAssign the same weight to all blocks in the same class\n");
 391   for (Function::iterator B = F.begin(), E = F.end(); B != E; ++B) {
 392     BasicBlock *BB = B;
 393     BasicBlock *EquivBB = EquivalenceClass[BB];
 394     if (BB != EquivBB)
 395       BlockWeights[BB] = BlockWeights[EquivBB];
 396     DEBUG(printBlockWeight(dbgs(), BB));
 397   }
 398 }
 399
 400 /// \brief Visit the given edge to decide if it has a valid weight.
 401 ///
 402 /// If \p E has not been visited before, we copy to \p UnknownEdge
 403 /// and increment the count of unknown edges.
 404 ///
 405 /// \param E  Edge to visit.
 406 /// \param NumUnknownEdges  Current number of unknown edges.
 407 /// \param UnknownEdge  Set if E has not been visited before.
 408 ///
 409 /// \returns E's weight, if known. Otherwise, return 0.
 410 unsigned SampleProfileLoader::visitEdge(Edge E, unsigned *NumUnknownEdges,
 411                                         Edge *UnknownEdge) {
 412   if (!VisitedEdges.count(E)) {
 413     (*NumUnknownEdges)++;
 414     *UnknownEdge = E;
 415     return 0;
 416   }
 417
 418   return EdgeWeights[E];
 419 }
 420
 421 /// \brief Propagate weights through incoming/outgoing edges.
 422 ///
 423 /// If the weight of a basic block is known, and there is only one edge
 424 /// with an unknown weight, we can calculate the weight of that edge.
 425 ///
 426 /// Similarly, if all the edges have a known count, we can calculate the
 427 /// count of the basic block, if needed.
 428 ///
 429 /// \param F  Function to process.
 430 ///
 431 /// \returns  True if new weights were assigned to edges or blocks.
 432 bool SampleProfileLoader::propagateThroughEdges(Function &F) {
 433   bool Changed = false;
 434   DEBUG(dbgs() << "\nPropagation through edges\n");
 435   for (Function::iterator BI = F.begin(), EI = F.end(); BI != EI; ++BI) {
 436     BasicBlock *BB = BI;
 437
 438     // Visit all the predecessor and successor edges to determine
 439     // which ones have a weight assigned already. Note that it doesn't
 440     // matter that we only keep track of a single unknown edge. The
 441     // only case we are interested in handling is when only a single
 442     // edge is unknown (see setEdgeOrBlockWeight).
 443     for (unsigned i = 0; i < 2; i++) {
 444       unsigned TotalWeight = 0;
 445       unsigned NumUnknownEdges = 0;
 446       Edge UnknownEdge, SelfReferentialEdge;
 447
 448       if (i == 0) {
 449         // First, visit all predecessor edges.
 450         for (size_t I = 0; I < Predecessors[BB].size(); I++) {
 451           Edge E = std::make_pair(Predecessors[BB][I], BB);
 452           TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);
 453           if (E.first == E.second)
 454             SelfReferentialEdge = E;
 455         }
 456       } else {
 457         // On the second round, visit all successor edges.
 458         for (size_t I = 0; I < Successors[BB].size(); I++) {
 459           Edge E = std::make_pair(BB, Successors[BB][I]);
 460           TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);
 461         }
 462       }
 463
 464       // After visiting all the edges, there are three cases that we
 465       // can handle immediately:
 466       //
 467       // - All the edge weights are known (i.e., NumUnknownEdges == 0).
 468       //   In this case, we simply check that the sum of all the edges
 469       //   is the same as BB's weight. If not, we change BB's weight
 470       //   to match. Additionally, if BB had not been visited before,
 471       //   we mark it visited.
 472       //
 473       // - Only one edge is unknown and BB has already been visited.
 474       //   In this case, we can compute the weight of the edge by
 475       //   subtracting the total block weight from all the known
 476       //   edge weights. If the edges weight more than BB, then the
 477       //   edge of the last remaining edge is set to zero.
 478       //
 479       // - There exists a self-referential edge and the weight of BB is
 480       //   known. In this case, this edge can be based on BB's weight.
 481       //   We add up all the other known edges and set the weight on
 482       //   the self-referential edge as we did in the previous case.
 483       //
 484       // In any other case, we must continue iterating. Eventually,
 485       // all edges will get a weight, or iteration will stop when
 486       // it reaches SampleProfileMaxPropagateIterations.
 487       if (NumUnknownEdges <= 1) {
 488         unsigned &BBWeight = BlockWeights[BB];
 489         if (NumUnknownEdges == 0) {
 490           // If we already know the weight of all edges, the weight of the
 491           // basic block can be computed. It should be no larger than the sum
 492           // of all edge weights.
 493           if (TotalWeight > BBWeight) {
 494             BBWeight = TotalWeight;
 495             Changed = true;
 496             DEBUG(dbgs() << "All edge weights for " << BB->getName()
 497                          << " known. Set weight for block: ";
 498                   printBlockWeight(dbgs(), BB););
 499           }
 500           if (VisitedBlocks.insert(BB))
 501             Changed = true;
 502         } else if (NumUnknownEdges == 1 && VisitedBlocks.count(BB)) {
 503           // If there is a single unknown edge and the block has been
 504           // visited, then we can compute E's weight.
 505           if (BBWeight >= TotalWeight)
 506             EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
 507           else
 508             EdgeWeights[UnknownEdge] = 0;
 509           VisitedEdges.insert(UnknownEdge);
 510           Changed = true;
 511           DEBUG(dbgs() << "Set weight for edge: ";
 512                 printEdgeWeight(dbgs(), UnknownEdge));
 513         }
 514       } else if (SelfReferentialEdge.first && VisitedBlocks.count(BB)) {
 515         unsigned &BBWeight = BlockWeights[BB];
 516         // We have a self-referential edge and the weight of BB is known.
 517         if (BBWeight >= TotalWeight)
 518           EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
 519         else
 520           EdgeWeights[SelfReferentialEdge] = 0;
 521         VisitedEdges.insert(SelfReferentialEdge);
 522         Changed = true;
 523         DEBUG(dbgs() << "Set self-referential edge weight to: ";
 524               printEdgeWeight(dbgs(), SelfReferentialEdge));
 525       }
 526     }
 527   }
 528
 529   return Changed;
 530 }
 531
 532 /// \brief Build in/out edge lists for each basic block in the CFG.
 533 ///
 534 /// We are interested in unique edges. If a block B1 has multiple
 535 /// edges to another block B2, we only add a single B1->B2 edge.
 536 void SampleProfileLoader::buildEdges(Function &F) {
 537   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 538     BasicBlock *B1 = I;
 539
 540     // Add predecessors for B1.
 541     SmallPtrSet<BasicBlock *, 16> Visited;
 542     if (!Predecessors[B1].empty())
 543       llvm_unreachable("Found a stale predecessors list in a basic block.");
 544     for (pred_iterator PI = pred_begin(B1), PE = pred_end(B1); PI != PE; ++PI) {
 545       BasicBlock *B2 = *PI;
 546       if (Visited.insert(B2))
 547         Predecessors[B1].push_back(B2);
 548     }
 549
 550     // Add successors for B1.
 551     Visited.clear();
 552     if (!Successors[B1].empty())
 553       llvm_unreachable("Found a stale successors list in a basic block.");
 554     for (succ_iterator SI = succ_begin(B1), SE = succ_end(B1); SI != SE; ++SI) {
 555       BasicBlock *B2 = *SI;
 556       if (Visited.insert(B2))
 557         Successors[B1].push_back(B2);
 558     }
 559   }
 560 }
 561
 562 /// \brief Propagate weights into edges
 563 ///
 564 /// The following rules are applied to every block B in the CFG:
 565 ///
 566 /// - If B has a single predecessor/successor, then the weight
 567 ///   of that edge is the weight of the block.
 568 ///
 569 /// - If all incoming or outgoing edges are known except one, and the
 570 ///   weight of the block is already known, the weight of the unknown
 571 ///   edge will be the weight of the block minus the sum of all the known
 572 ///   edges. If the sum of all the known edges is larger than B's weight,
 573 ///   we set the unknown edge weight to zero.
 574 ///
 575 /// - If there is a self-referential edge, and the weight of the block is
 576 ///   known, the weight for that edge is set to the weight of the block
 577 ///   minus the weight of the other incoming edges to that block (if
 578 ///   known).
 579 void SampleProfileLoader::propagateWeights(Function &F) {
 580   bool Changed = true;
 581   unsigned i = 0;
 582
 583   // Before propagation starts, build, for each block, a list of
 584   // unique predecessors and successors. This is necessary to handle
 585   // identical edges in multiway branches. Since we visit all blocks and all
 586   // edges of the CFG, it is cleaner to build these lists once at the start
 587   // of the pass.
 588   buildEdges(F);
 589
 590   // Propagate until we converge or we go past the iteration limit.
 591   while (Changed && i++ < SampleProfileMaxPropagateIterations) {
 592     Changed = propagateThroughEdges(F);
 593   }
 594
 595   // Generate MD_prof metadata for every branch instruction using the
 596   // edge weights computed during propagation.
 597   DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n");
 598   MDBuilder MDB(F.getContext());
 599   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 600     BasicBlock *B = I;
 601     TerminatorInst *TI = B->getTerminator();
 602     if (TI->getNumSuccessors() == 1)
 603       continue;
 604     if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
 605       continue;
 606
 607     DEBUG(dbgs() << "\nGetting weights for branch at line "
 608                  << TI->getDebugLoc().getLine() << ".\n");
 609     SmallVector<unsigned, 4> Weights;
 610     bool AllWeightsZero = true;
 611     for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
 612       BasicBlock *Succ = TI->getSuccessor(I);
 613       Edge E = std::make_pair(B, Succ);
 614       unsigned Weight = EdgeWeights[E];
 615       DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E));
 616       Weights.push_back(Weight);
 617       if (Weight != 0)
 618         AllWeightsZero = false;
 619     }
 620
 621     // Only set weights if there is at least one non-zero weight.
 622     // In any other case, let the analyzer set weights.
 623     if (!AllWeightsZero) {
 624       DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n");
 625       TI->setMetadata(llvm::LLVMContext::MD_prof,
 626                       MDB.createBranchWeights(Weights));
 627     } else {
 628       DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
 629     }
 630   }
 631 }
 632
 633 /// \brief Locate the DISubprogram for F.
 634 ///
 635 /// We look for the first instruction that has a debug annotation
 636 /// leading back to \p F.
 637 ///
 638 /// \returns a valid DISubprogram, if found. Otherwise, it returns an empty
 639 /// DISubprogram.
 640 static const DISubprogram getDISubprogram(Function &F, const LLVMContext &Ctx) {
 641   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 642     BasicBlock *B = I;
 643     for (BasicBlock::iterator BI = B->begin(), BE = B->end(); BI != BE; ++BI) {
 644       Instruction &Inst = *BI;
 645       DebugLoc DLoc = Inst.getDebugLoc();
 646       if (DLoc.isUnknown())
 647         continue;
 648       const MDNode *Scope = DLoc.getScopeNode(Ctx);
 649       DISubprogram Subprogram = getDISubprogram(Scope);
 650       return Subprogram.describes(&F) ? Subprogram : DISubprogram();
 651     }
 652   }
 653
 654   return DISubprogram();
 655 }
 656
 657 /// \brief Get the line number for the function header.
 658 ///
 659 /// This looks up function \p F in the current compilation unit and
 660 /// retrieves the line number where the function is defined. This is
 661 /// line 0 for all the samples read from the profile file. Every line
 662 /// number is relative to this line.
 663 ///
 664 /// \param F  Function object to query.
 665 ///
 666 /// \returns the line number where \p F is defined. If it returns 0,
 667 ///          it means that there is no debug information available for \p F.
 668 unsigned SampleProfileLoader::getFunctionLoc(Function &F) {
 669   const DISubprogram &S = getDISubprogram(F, *Ctx);
 670   if (S.isSubprogram())
 671     return S.getLineNumber();
 672
 673   // If could not find the start of \p F, emit a diagnostic to inform the user
 674   // about the missed opportunity.
 675   F.getContext().diagnose(DiagnosticInfoSampleProfile(
 676       "No debug information found in function " + F.getName()));
 677   return 0;
 678 }
 679
 680 /// \brief Generate branch weight metadata for all branches in \p F.
 681 ///
 682 /// Branch weights are computed out of instruction samples using a
 683 /// propagation heuristic. Propagation proceeds in 3 phases:
 684 ///
 685 /// 1- Assignment of block weights. All the basic blocks in the function
 686 ///    are initial assigned the same weight as their most frequently
 687 ///    executed instruction.
 688 ///
 689 /// 2- Creation of equivalence classes. Since samples may be missing from
 690 ///    blocks, we can fill in the gaps by setting the weights of all the
 691 ///    blocks in the same equivalence class to the same weight. To compute
 692 ///    the concept of equivalence, we use dominance and loop information.
 693 ///    Two blocks B1 and B2 are in the same equivalence class if B1
 694 ///    dominates B2, B2 post-dominates B1 and both are in the same loop.
 695 ///
 696 /// 3- Propagation of block weights into edges. This uses a simple
 697 ///    propagation heuristic. The following rules are applied to every
 698 ///    block B in the CFG:
 699 ///
 700 ///    - If B has a single predecessor/successor, then the weight
 701 ///      of that edge is the weight of the block.
 702 ///
 703 ///    - If all the edges are known except one, and the weight of the
 704 ///      block is already known, the weight of the unknown edge will
 705 ///      be the weight of the block minus the sum of all the known
 706 ///      edges. If the sum of all the known edges is larger than B's weight,
 707 ///      we set the unknown edge weight to zero.
 708 ///
 709 ///    - If there is a self-referential edge, and the weight of the block is
 710 ///      known, the weight for that edge is set to the weight of the block
 711 ///      minus the weight of the other incoming edges to that block (if
 712 ///      known).
 713 ///
 714 /// Since this propagation is not guaranteed to finalize for every CFG, we
 715 /// only allow it to proceed for a limited number of iterations (controlled
 716 /// by -sample-profile-max-propagate-iterations).
 717 ///
 718 /// FIXME: Try to replace this propagation heuristic with a scheme
 719 /// that is guaranteed to finalize. A work-list approach similar to
 720 /// the standard value propagation algorithm used by SSA-CCP might
 721 /// work here.
 722 ///
 723 /// Once all the branch weights are computed, we emit the MD_prof
 724 /// metadata on B using the computed values for each of its branches.
 725 ///
 726 /// \param F The function to query.
 727 ///
 728 /// \returns true if \p F was modified. Returns false, otherwise.
 729 bool SampleProfileLoader::emitAnnotations(Function &F) {
 730   bool Changed = false;
 731
 732   // Initialize invariants used during computation and propagation.
 733   HeaderLineno = getFunctionLoc(F);
 734   if (HeaderLineno == 0)
 735     return false;
 736
 737   DEBUG(dbgs() << "Line number for the first instruction in " << F.getName()
 738                << ": " << HeaderLineno << "\n");
 739
 740   // Compute basic block weights.
 741   Changed |= computeBlockWeights(F);
 742
 743   if (Changed) {
 744     // Find equivalence classes.
 745     findEquivalenceClasses(F);
 746
 747     // Propagate weights to all edges.
 748     propagateWeights(F);
 749   }
 750
 751   return Changed;
 752 }
 753
 754 char SampleProfileLoader::ID = 0;
 755 INITIALIZE_PASS_BEGIN(SampleProfileLoader, "sample-profile",
 756                       "Sample Profile loader", false, false)
 757 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 758 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
 759 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
 760 INITIALIZE_PASS_DEPENDENCY(AddDiscriminators)
 761 INITIALIZE_PASS_END(SampleProfileLoader, "sample-profile",
 762                     "Sample Profile loader", false, false)
 763
 764 bool SampleProfileLoader::doInitialization(Module &M) {
 765   Reader.reset(new SampleProfileReader(M, Filename));
 766   ProfileIsValid = Reader->load();
 767   return true;
 768 }
 769
 770 FunctionPass *llvm::createSampleProfileLoaderPass() {
 771   return new SampleProfileLoader(SampleProfileFile);
 772 }
 773
 774 FunctionPass *llvm::createSampleProfileLoaderPass(StringRef Name) {
 775   return new SampleProfileLoader(Name);
 776 }
 777
 778 bool SampleProfileLoader::runOnFunction(Function &F) {
 779   if (!ProfileIsValid)
 780     return false;
 781
 782   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 783   PDT = &getAnalysis<PostDominatorTree>();
 784   LI = &getAnalysis<LoopInfo>();
 785   Ctx = &F.getParent()->getContext();
 786   Samples = Reader->getSamplesFor(F);
 787   if (!Samples->empty())
 788     return emitAnnotations(F);
 789   return false;
 790 }