lib/Transforms/IPO/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/ADT/DenseMap.h"
  26 #include "llvm/ADT/SmallPtrSet.h"
  27 #include "llvm/ADT/SmallSet.h"
  28 #include "llvm/ADT/StringRef.h"
  29 #include "llvm/Analysis/LoopInfo.h"
  30 #include "llvm/Analysis/PostDominators.h"
  31 #include "llvm/IR/Constants.h"
  32 #include "llvm/IR/DebugInfo.h"
  33 #include "llvm/IR/DiagnosticInfo.h"
  34 #include "llvm/IR/Dominators.h"
  35 #include "llvm/IR/Function.h"
  36 #include "llvm/IR/InstIterator.h"
  37 #include "llvm/IR/Instructions.h"
  38 #include "llvm/IR/LLVMContext.h"
  39 #include "llvm/IR/MDBuilder.h"
  40 #include "llvm/IR/Metadata.h"
  41 #include "llvm/IR/Module.h"
  42 #include "llvm/Pass.h"
  43 #include "llvm/ProfileData/SampleProfReader.h"
  44 #include "llvm/Support/CommandLine.h"
  45 #include "llvm/Support/Debug.h"
  46 #include "llvm/Support/ErrorOr.h"
  47 #include "llvm/Support/raw_ostream.h"
  48 #include "llvm/Transforms/IPO.h"
  49 #include "llvm/Transforms/Utils/Cloning.h"
  50 #include <cctype>
  51
  52 using namespace llvm;
  53 using namespace sampleprof;
  54
  55 #define DEBUG_TYPE "sample-profile"
  56
  57 // Command line option to specify the file to read samples from. This is
  58 // mainly used for debugging.
  59 static cl::opt<std::string> SampleProfileFile(
  60     "sample-profile-file", cl::init(""), cl::value_desc("filename"),
  61     cl::desc("Profile file loaded by -sample-profile"), cl::Hidden);
  62 static cl::opt<unsigned> SampleProfileMaxPropagateIterations(
  63     "sample-profile-max-propagate-iterations", cl::init(100),
  64     cl::desc("Maximum number of iterations to go through when propagating "
  65              "sample block/edge weights through the CFG."));
  66
  67 namespace {
  68 typedef DenseMap<const BasicBlock *, uint64_t> BlockWeightMap;
  69 typedef DenseMap<const BasicBlock *, const BasicBlock *> EquivalenceClassMap;
  70 typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
  71 typedef DenseMap<Edge, uint64_t> EdgeWeightMap;
  72 typedef DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>
  73     BlockEdgeMap;
  74
  75 /// \brief Sample profile pass.
  76 ///
  77 /// This pass reads profile data from the file specified by
  78 /// -sample-profile-file and annotates every affected function with the
  79 /// profile information found in that file.
  80 class SampleProfileLoader : public ModulePass {
  81 public:
  82   // Class identification, replacement for typeinfo
  83   static char ID;
  84
  85   SampleProfileLoader(StringRef Name = SampleProfileFile)
  86       : ModulePass(ID), DT(nullptr), PDT(nullptr), LI(nullptr), Reader(),
  87         Samples(nullptr), Filename(Name), ProfileIsValid(false) {
  88     initializeSampleProfileLoaderPass(*PassRegistry::getPassRegistry());
  89   }
  90
  91   bool doInitialization(Module &M) override;
  92
  93   void dump() { Reader->dump(); }
  94
  95   const char *getPassName() const override { return "Sample profile pass"; }
  96
  97   bool runOnModule(Module &M) override;
  98
  99   void getAnalysisUsage(AnalysisUsage &AU) const override {
 100     AU.setPreservesCFG();
 101   }
 102
 103 protected:
 104   bool runOnFunction(Function &F);
 105   unsigned getFunctionLoc(Function &F);
 106   bool emitAnnotations(Function &F);
 107   ErrorOr<uint64_t> getInstWeight(const Instruction &I) const;
 108   ErrorOr<uint64_t> getBlockWeight(const BasicBlock *BB) const;
 109   const FunctionSamples *findCalleeFunctionSamples(const CallInst &I) const;
 110   const FunctionSamples *findFunctionSamples(const Instruction &I) const;
 111   bool inlineHotFunctions(Function &F);
 112   void printEdgeWeight(raw_ostream &OS, Edge E);
 113   void printBlockWeight(raw_ostream &OS, const BasicBlock *BB) const;
 114   void printBlockEquivalence(raw_ostream &OS, const BasicBlock *BB);
 115   bool computeBlockWeights(Function &F);
 116   void findEquivalenceClasses(Function &F);
 117   void findEquivalencesFor(BasicBlock *BB1,
 118                            SmallVector<BasicBlock *, 8> Descendants,
 119                            DominatorTreeBase<BasicBlock> *DomTree);
 120   void propagateWeights(Function &F);
 121   uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
 122   void buildEdges(Function &F);
 123   bool propagateThroughEdges(Function &F);
 124   void computeDominanceAndLoopInfo(Function &F);
 125   unsigned getOffset(unsigned L, unsigned H) const;
 126   void clearFunctionData();
 127
 128   /// \brief Map basic blocks to their computed weights.
 129   ///
 130   /// The weight of a basic block is defined to be the maximum
 131   /// of all the instruction weights in that block.
 132   BlockWeightMap BlockWeights;
 133
 134   /// \brief Map edges to their computed weights.
 135   ///
 136   /// Edge weights are computed by propagating basic block weights in
 137   /// SampleProfile::propagateWeights.
 138   EdgeWeightMap EdgeWeights;
 139
 140   /// \brief Set of visited blocks during propagation.
 141   SmallPtrSet<const BasicBlock *, 128> VisitedBlocks;
 142
 143   /// \brief Set of visited edges during propagation.
 144   SmallSet<Edge, 128> VisitedEdges;
 145
 146   /// \brief Equivalence classes for block weights.
 147   ///
 148   /// Two blocks BB1 and BB2 are in the same equivalence class if they
 149   /// dominate and post-dominate each other, and they are in the same loop
 150   /// nest. When this happens, the two blocks are guaranteed to execute
 151   /// the same number of times.
 152   EquivalenceClassMap EquivalenceClass;
 153
 154   /// \brief Dominance, post-dominance and loop information.
 155   std::unique_ptr<DominatorTree> DT;
 156   std::unique_ptr<DominatorTreeBase<BasicBlock>> PDT;
 157   std::unique_ptr<LoopInfo> LI;
 158
 159   /// \brief Predecessors for each basic block in the CFG.
 160   BlockEdgeMap Predecessors;
 161
 162   /// \brief Successors for each basic block in the CFG.
 163   BlockEdgeMap Successors;
 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 /// Clear all the per-function data used to load samples and propagate weights.
 180 void SampleProfileLoader::clearFunctionData() {
 181   BlockWeights.clear();
 182   EdgeWeights.clear();
 183   VisitedBlocks.clear();
 184   VisitedEdges.clear();
 185   EquivalenceClass.clear();
 186   DT = nullptr;
 187   PDT = nullptr;
 188   LI = nullptr;
 189   Predecessors.clear();
 190   Successors.clear();
 191 }
 192
 193 /// \brief Returns the offset of lineno \p L to head_lineno \p H
 194 ///
 195 /// \param L  Lineno
 196 /// \param H  Header lineno of the function
 197 ///
 198 /// \returns offset to the header lineno. 16 bits are used to represent offset.
 199 /// We assume that a single function will not exceed 65535 LOC.
 200 unsigned SampleProfileLoader::getOffset(unsigned L, unsigned H) const {
 201   return (L - H) & 0xffff;
 202 }
 203
 204 /// \brief Print the weight of edge \p E on stream \p OS.
 205 ///
 206 /// \param OS  Stream to emit the output to.
 207 /// \param E  Edge to print.
 208 void SampleProfileLoader::printEdgeWeight(raw_ostream &OS, Edge E) {
 209   OS << "weight[" << E.first->getName() << "->" << E.second->getName()
 210      << "]: " << EdgeWeights[E] << "\n";
 211 }
 212
 213 /// \brief Print the equivalence class of block \p BB on stream \p OS.
 214 ///
 215 /// \param OS  Stream to emit the output to.
 216 /// \param BB  Block to print.
 217 void SampleProfileLoader::printBlockEquivalence(raw_ostream &OS,
 218                                                 const BasicBlock *BB) {
 219   const BasicBlock *Equiv = EquivalenceClass[BB];
 220   OS << "equivalence[" << BB->getName()
 221      << "]: " << ((Equiv) ? EquivalenceClass[BB]->getName() : "NONE") << "\n";
 222 }
 223
 224 /// \brief Print the weight of block \p BB on stream \p OS.
 225 ///
 226 /// \param OS  Stream to emit the output to.
 227 /// \param BB  Block to print.
 228 void SampleProfileLoader::printBlockWeight(raw_ostream &OS,
 229                                            const BasicBlock *BB) const {
 230   const auto &I = BlockWeights.find(BB);
 231   uint64_t W = (I == BlockWeights.end() ? 0 : I->second);
 232   OS << "weight[" << BB->getName() << "]: " << W << "\n";
 233 }
 234
 235 /// \brief Get the weight for an instruction.
 236 ///
 237 /// The "weight" of an instruction \p Inst is the number of samples
 238 /// collected on that instruction at runtime. To retrieve it, we
 239 /// need to compute the line number of \p Inst relative to the start of its
 240 /// function. We use HeaderLineno to compute the offset. We then
 241 /// look up the samples collected for \p Inst using BodySamples.
 242 ///
 243 /// \param Inst Instruction to query.
 244 ///
 245 /// \returns the weight of \p Inst.
 246 ErrorOr<uint64_t>
 247 SampleProfileLoader::getInstWeight(const Instruction &Inst) const {
 248   DebugLoc DLoc = Inst.getDebugLoc();
 249   if (!DLoc)
 250     return std::error_code();
 251
 252   const FunctionSamples *FS = findFunctionSamples(Inst);
 253   if (!FS)
 254     return std::error_code();
 255
 256   const DILocation *DIL = DLoc;
 257   unsigned Lineno = DLoc.getLine();
 258   unsigned HeaderLineno = DIL->getScope()->getSubprogram()->getLine();
 259
 260   ErrorOr<uint64_t> R = FS->findSamplesAt(getOffset(Lineno, HeaderLineno),
 261                                           DIL->getDiscriminator());
 262   if (R)
 263     DEBUG(dbgs() << "    " << Lineno << "." << DIL->getDiscriminator() << ":"
 264                  << Inst << " (line offset: " << Lineno - HeaderLineno << "."
 265                  << DIL->getDiscriminator() << " - weight: " << R.get()
 266                  << ")\n");
 267   return R;
 268 }
 269
 270 /// \brief Compute the weight of a basic block.
 271 ///
 272 /// The weight of basic block \p BB is the maximum weight of all the
 273 /// instructions in BB.
 274 ///
 275 /// \param BB The basic block to query.
 276 ///
 277 /// \returns the weight for \p BB.
 278 ErrorOr<uint64_t>
 279 SampleProfileLoader::getBlockWeight(const BasicBlock *BB) const {
 280   bool Found = false;
 281   uint64_t Weight = 0;
 282   for (auto &I : BB->getInstList()) {
 283     const ErrorOr<uint64_t> &R = getInstWeight(I);
 284     if (R && R.get() >= Weight) {
 285       Weight = R.get();
 286       Found = true;
 287     }
 288   }
 289   if (Found)
 290     return Weight;
 291   else
 292     return std::error_code();
 293 }
 294
 295 /// \brief Compute and store the weights of every basic block.
 296 ///
 297 /// This populates the BlockWeights map by computing
 298 /// the weights of every basic block in the CFG.
 299 ///
 300 /// \param F The function to query.
 301 bool SampleProfileLoader::computeBlockWeights(Function &F) {
 302   bool Changed = false;
 303   DEBUG(dbgs() << "Block weights\n");
 304   for (const auto &BB : F) {
 305     ErrorOr<uint64_t> Weight = getBlockWeight(&BB);
 306     if (Weight) {
 307       BlockWeights[&BB] = Weight.get();
 308       VisitedBlocks.insert(&BB);
 309       Changed = true;
 310     }
 311     DEBUG(printBlockWeight(dbgs(), &BB));
 312   }
 313
 314   return Changed;
 315 }
 316
 317 /// \brief Get the FunctionSamples for a call instruction.
 318 ///
 319 /// The FunctionSamples of a call instruction \p Inst is the inlined
 320 /// instance in which that call instruction is calling to. It contains
 321 /// all samples that resides in the inlined instance. We first find the
 322 /// inlined instance in which the call instruction is from, then we
 323 /// traverse its children to find the callsite with the matching
 324 /// location and callee function name.
 325 ///
 326 /// \param Inst Call instruction to query.
 327 ///
 328 /// \returns The FunctionSamples pointer to the inlined instance.
 329 const FunctionSamples *
 330 SampleProfileLoader::findCalleeFunctionSamples(const CallInst &Inst) const {
 331   const DILocation *DIL = Inst.getDebugLoc();
 332   if (!DIL) {
 333     return nullptr;
 334   }
 335   DISubprogram *SP = DIL->getScope()->getSubprogram();
 336   if (!SP)
 337     return nullptr;
 338
 339   Function *CalleeFunc = Inst.getCalledFunction();
 340   if (!CalleeFunc) {
 341     return nullptr;
 342   }
 343
 344   StringRef CalleeName = CalleeFunc->getName();
 345   const FunctionSamples *FS = findFunctionSamples(Inst);
 346   if (FS == nullptr)
 347     return nullptr;
 348
 349   return FS->findFunctionSamplesAt(
 350       CallsiteLocation(getOffset(DIL->getLine(), SP->getLine()),
 351                        DIL->getDiscriminator(), CalleeName));
 352 }
 353
 354 /// \brief Get the FunctionSamples for an instruction.
 355 ///
 356 /// The FunctionSamples of an instruction \p Inst is the inlined instance
 357 /// in which that instruction is coming from. We traverse the inline stack
 358 /// of that instruction, and match it with the tree nodes in the profile.
 359 ///
 360 /// \param Inst Instruction to query.
 361 ///
 362 /// \returns the FunctionSamples pointer to the inlined instance.
 363 const FunctionSamples *
 364 SampleProfileLoader::findFunctionSamples(const Instruction &Inst) const {
 365   SmallVector<CallsiteLocation, 10> S;
 366   const DILocation *DIL = Inst.getDebugLoc();
 367   if (!DIL) {
 368     return Samples;
 369   }
 370   StringRef CalleeName;
 371   for (const DILocation *DIL = Inst.getDebugLoc(); DIL;
 372        DIL = DIL->getInlinedAt()) {
 373     DISubprogram *SP = DIL->getScope()->getSubprogram();
 374     if (!SP)
 375       return nullptr;
 376     if (!CalleeName.empty()) {
 377       S.push_back(CallsiteLocation(getOffset(DIL->getLine(), SP->getLine()),
 378                                    DIL->getDiscriminator(), CalleeName));
 379     }
 380     CalleeName = SP->getLinkageName();
 381   }
 382   if (S.size() == 0)
 383     return Samples;
 384   const FunctionSamples *FS = Samples;
 385   for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {
 386     FS = FS->findFunctionSamplesAt(S[i]);
 387   }
 388   return FS;
 389 }
 390
 391 /// \brief Iteratively inline hot callsites of a function.
 392 ///
 393 /// Iteratively traverse all callsites of the function \p F, and find if
 394 /// the corresponding inlined instance exists and is hot in profile. If
 395 /// it is hot enough, inline the callsites and adds new callsites of the
 396 /// callee into the caller.
 397 ///
 398 /// TODO: investigate the possibility of not invoking InlineFunction directly.
 399 ///
 400 /// \param F function to perform iterative inlining.
 401 ///
 402 /// \returns True if there is any inline happened.
 403 bool SampleProfileLoader::inlineHotFunctions(Function &F) {
 404   bool Changed = false;
 405   LLVMContext &Ctx = F.getContext();
 406   while (true) {
 407     bool LocalChanged = false;
 408     SmallVector<CallInst *, 10> CIS;
 409     for (auto &BB : F) {
 410       for (auto &I : BB.getInstList()) {
 411         CallInst *CI = dyn_cast<CallInst>(&I);
 412         if (CI) {
 413           const FunctionSamples *FS = findCalleeFunctionSamples(*CI);
 414           if (FS && FS->getTotalSamples() > 0) {
 415             CIS.push_back(CI);
 416           }
 417         }
 418       }
 419     }
 420     for (auto CI : CIS) {
 421       InlineFunctionInfo IFI;
 422       Function *CalledFunction = CI->getCalledFunction();
 423       DebugLoc DLoc = CI->getDebugLoc();
 424       uint64_t NumSamples = findCalleeFunctionSamples(*CI)->getTotalSamples();
 425       if (InlineFunction(CI, IFI)) {
 426         LocalChanged = true;
 427         emitOptimizationRemark(Ctx, DEBUG_TYPE, F, DLoc,
 428                                Twine("inlined hot callee '") +
 429                                    CalledFunction->getName() + "' with " +
 430                                    Twine(NumSamples) + " samples into '" +
 431                                    F.getName() + "'");
 432       }
 433     }
 434     if (LocalChanged) {
 435       Changed = true;
 436     } else {
 437       break;
 438     }
 439   }
 440   return Changed;
 441 }
 442
 443 /// \brief Find equivalence classes for the given block.
 444 ///
 445 /// This finds all the blocks that are guaranteed to execute the same
 446 /// number of times as \p BB1. To do this, it traverses all the
 447 /// descendants of \p BB1 in the dominator or post-dominator tree.
 448 ///
 449 /// A block BB2 will be in the same equivalence class as \p BB1 if
 450 /// the following holds:
 451 ///
 452 /// 1- \p BB1 is a descendant of BB2 in the opposite tree. So, if BB2
 453 ///    is a descendant of \p BB1 in the dominator tree, then BB2 should
 454 ///    dominate BB1 in the post-dominator tree.
 455 ///
 456 /// 2- Both BB2 and \p BB1 must be in the same loop.
 457 ///
 458 /// For every block BB2 that meets those two requirements, we set BB2's
 459 /// equivalence class to \p BB1.
 460 ///
 461 /// \param BB1  Block to check.
 462 /// \param Descendants  Descendants of \p BB1 in either the dom or pdom tree.
 463 /// \param DomTree  Opposite dominator tree. If \p Descendants is filled
 464 ///                 with blocks from \p BB1's dominator tree, then
 465 ///                 this is the post-dominator tree, and vice versa.
 466 void SampleProfileLoader::findEquivalencesFor(
 467     BasicBlock *BB1, SmallVector<BasicBlock *, 8> Descendants,
 468     DominatorTreeBase<BasicBlock> *DomTree) {
 469   const BasicBlock *EC = EquivalenceClass[BB1];
 470   uint64_t Weight = BlockWeights[EC];
 471   for (const auto *BB2 : Descendants) {
 472     bool IsDomParent = DomTree->dominates(BB2, BB1);
 473     bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
 474     if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
 475       EquivalenceClass[BB2] = EC;
 476
 477       // If BB2 is heavier than BB1, make BB2 have the same weight
 478       // as BB1.
 479       //
 480       // Note that we don't worry about the opposite situation here
 481       // (when BB2 is lighter than BB1). We will deal with this
 482       // during the propagation phase. Right now, we just want to
 483       // make sure that BB1 has the largest weight of all the
 484       // members of its equivalence set.
 485       Weight = std::max(Weight, BlockWeights[BB2]);
 486     }
 487   }
 488   BlockWeights[EC] = Weight;
 489 }
 490
 491 /// \brief Find equivalence classes.
 492 ///
 493 /// Since samples may be missing from blocks, we can fill in the gaps by setting
 494 /// the weights of all the blocks in the same equivalence class to the same
 495 /// weight. To compute the concept of equivalence, we use dominance and loop
 496 /// information. Two blocks B1 and B2 are in the same equivalence class if B1
 497 /// dominates B2, B2 post-dominates B1 and both are in the same loop.
 498 ///
 499 /// \param F The function to query.
 500 void SampleProfileLoader::findEquivalenceClasses(Function &F) {
 501   SmallVector<BasicBlock *, 8> DominatedBBs;
 502   DEBUG(dbgs() << "\nBlock equivalence classes\n");
 503   // Find equivalence sets based on dominance and post-dominance information.
 504   for (auto &BB : F) {
 505     BasicBlock *BB1 = &BB;
 506
 507     // Compute BB1's equivalence class once.
 508     if (EquivalenceClass.count(BB1)) {
 509       DEBUG(printBlockEquivalence(dbgs(), BB1));
 510       continue;
 511     }
 512
 513     // By default, blocks are in their own equivalence class.
 514     EquivalenceClass[BB1] = BB1;
 515
 516     // Traverse all the blocks dominated by BB1. We are looking for
 517     // every basic block BB2 such that:
 518     //
 519     // 1- BB1 dominates BB2.
 520     // 2- BB2 post-dominates BB1.
 521     // 3- BB1 and BB2 are in the same loop nest.
 522     //
 523     // If all those conditions hold, it means that BB2 is executed
 524     // as many times as BB1, so they are placed in the same equivalence
 525     // class by making BB2's equivalence class be BB1.
 526     DominatedBBs.clear();
 527     DT->getDescendants(BB1, DominatedBBs);
 528     findEquivalencesFor(BB1, DominatedBBs, PDT.get());
 529
 530     DEBUG(printBlockEquivalence(dbgs(), BB1));
 531   }
 532
 533   // Assign weights to equivalence classes.
 534   //
 535   // All the basic blocks in the same equivalence class will execute
 536   // the same number of times. Since we know that the head block in
 537   // each equivalence class has the largest weight, assign that weight
 538   // to all the blocks in that equivalence class.
 539   DEBUG(dbgs() << "\nAssign the same weight to all blocks in the same class\n");
 540   for (auto &BI : F) {
 541     const BasicBlock *BB = &BI;
 542     const BasicBlock *EquivBB = EquivalenceClass[BB];
 543     if (BB != EquivBB)
 544       BlockWeights[BB] = BlockWeights[EquivBB];
 545     DEBUG(printBlockWeight(dbgs(), BB));
 546   }
 547 }
 548
 549 /// \brief Visit the given edge to decide if it has a valid weight.
 550 ///
 551 /// If \p E has not been visited before, we copy to \p UnknownEdge
 552 /// and increment the count of unknown edges.
 553 ///
 554 /// \param E  Edge to visit.
 555 /// \param NumUnknownEdges  Current number of unknown edges.
 556 /// \param UnknownEdge  Set if E has not been visited before.
 557 ///
 558 /// \returns E's weight, if known. Otherwise, return 0.
 559 uint64_t SampleProfileLoader::visitEdge(Edge E, unsigned *NumUnknownEdges,
 560                                         Edge *UnknownEdge) {
 561   if (!VisitedEdges.count(E)) {
 562     (*NumUnknownEdges)++;
 563     *UnknownEdge = E;
 564     return 0;
 565   }
 566
 567   return EdgeWeights[E];
 568 }
 569
 570 /// \brief Propagate weights through incoming/outgoing edges.
 571 ///
 572 /// If the weight of a basic block is known, and there is only one edge
 573 /// with an unknown weight, we can calculate the weight of that edge.
 574 ///
 575 /// Similarly, if all the edges have a known count, we can calculate the
 576 /// count of the basic block, if needed.
 577 ///
 578 /// \param F  Function to process.
 579 ///
 580 /// \returns  True if new weights were assigned to edges or blocks.
 581 bool SampleProfileLoader::propagateThroughEdges(Function &F) {
 582   bool Changed = false;
 583   DEBUG(dbgs() << "\nPropagation through edges\n");
 584   for (const auto &BI : F) {
 585     const BasicBlock *BB = &BI;
 586     const BasicBlock *EC = EquivalenceClass[BB];
 587
 588     // Visit all the predecessor and successor edges to determine
 589     // which ones have a weight assigned already. Note that it doesn't
 590     // matter that we only keep track of a single unknown edge. The
 591     // only case we are interested in handling is when only a single
 592     // edge is unknown (see setEdgeOrBlockWeight).
 593     for (unsigned i = 0; i < 2; i++) {
 594       uint64_t TotalWeight = 0;
 595       unsigned NumUnknownEdges = 0;
 596       Edge UnknownEdge, SelfReferentialEdge;
 597
 598       if (i == 0) {
 599         // First, visit all predecessor edges.
 600         for (auto *Pred : Predecessors[BB]) {
 601           Edge E = std::make_pair(Pred, BB);
 602           TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);
 603           if (E.first == E.second)
 604             SelfReferentialEdge = E;
 605         }
 606       } else {
 607         // On the second round, visit all successor edges.
 608         for (auto *Succ : Successors[BB]) {
 609           Edge E = std::make_pair(BB, Succ);
 610           TotalWeight += visitEdge(E, &NumUnknownEdges, &UnknownEdge);
 611         }
 612       }
 613
 614       // After visiting all the edges, there are three cases that we
 615       // can handle immediately:
 616       //
 617       // - All the edge weights are known (i.e., NumUnknownEdges == 0).
 618       //   In this case, we simply check that the sum of all the edges
 619       //   is the same as BB's weight. If not, we change BB's weight
 620       //   to match. Additionally, if BB had not been visited before,
 621       //   we mark it visited.
 622       //
 623       // - Only one edge is unknown and BB has already been visited.
 624       //   In this case, we can compute the weight of the edge by
 625       //   subtracting the total block weight from all the known
 626       //   edge weights. If the edges weight more than BB, then the
 627       //   edge of the last remaining edge is set to zero.
 628       //
 629       // - There exists a self-referential edge and the weight of BB is
 630       //   known. In this case, this edge can be based on BB's weight.
 631       //   We add up all the other known edges and set the weight on
 632       //   the self-referential edge as we did in the previous case.
 633       //
 634       // In any other case, we must continue iterating. Eventually,
 635       // all edges will get a weight, or iteration will stop when
 636       // it reaches SampleProfileMaxPropagateIterations.
 637       if (NumUnknownEdges <= 1) {
 638         uint64_t &BBWeight = BlockWeights[EC];
 639         if (NumUnknownEdges == 0) {
 640           // If we already know the weight of all edges, the weight of the
 641           // basic block can be computed. It should be no larger than the sum
 642           // of all edge weights.
 643           if (TotalWeight > BBWeight) {
 644             BBWeight = TotalWeight;
 645             Changed = true;
 646             DEBUG(dbgs() << "All edge weights for " << BB->getName()
 647                          << " known. Set weight for block: ";
 648                   printBlockWeight(dbgs(), BB););
 649           }
 650           if (VisitedBlocks.insert(EC).second)
 651             Changed = true;
 652         } else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
 653           // If there is a single unknown edge and the block has been
 654           // visited, then we can compute E's weight.
 655           if (BBWeight >= TotalWeight)
 656             EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
 657           else
 658             EdgeWeights[UnknownEdge] = 0;
 659           VisitedEdges.insert(UnknownEdge);
 660           Changed = true;
 661           DEBUG(dbgs() << "Set weight for edge: ";
 662                 printEdgeWeight(dbgs(), UnknownEdge));
 663         }
 664       } else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
 665         uint64_t &BBWeight = BlockWeights[BB];
 666         // We have a self-referential edge and the weight of BB is known.
 667         if (BBWeight >= TotalWeight)
 668           EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
 669         else
 670           EdgeWeights[SelfReferentialEdge] = 0;
 671         VisitedEdges.insert(SelfReferentialEdge);
 672         Changed = true;
 673         DEBUG(dbgs() << "Set self-referential edge weight to: ";
 674               printEdgeWeight(dbgs(), SelfReferentialEdge));
 675       }
 676     }
 677   }
 678
 679   return Changed;
 680 }
 681
 682 /// \brief Build in/out edge lists for each basic block in the CFG.
 683 ///
 684 /// We are interested in unique edges. If a block B1 has multiple
 685 /// edges to another block B2, we only add a single B1->B2 edge.
 686 void SampleProfileLoader::buildEdges(Function &F) {
 687   for (auto &BI : F) {
 688     BasicBlock *B1 = &BI;
 689
 690     // Add predecessors for B1.
 691     SmallPtrSet<BasicBlock *, 16> Visited;
 692     if (!Predecessors[B1].empty())
 693       llvm_unreachable("Found a stale predecessors list in a basic block.");
 694     for (pred_iterator PI = pred_begin(B1), PE = pred_end(B1); PI != PE; ++PI) {
 695       BasicBlock *B2 = *PI;
 696       if (Visited.insert(B2).second)
 697         Predecessors[B1].push_back(B2);
 698     }
 699
 700     // Add successors for B1.
 701     Visited.clear();
 702     if (!Successors[B1].empty())
 703       llvm_unreachable("Found a stale successors list in a basic block.");
 704     for (succ_iterator SI = succ_begin(B1), SE = succ_end(B1); SI != SE; ++SI) {
 705       BasicBlock *B2 = *SI;
 706       if (Visited.insert(B2).second)
 707         Successors[B1].push_back(B2);
 708     }
 709   }
 710 }
 711
 712 /// \brief Propagate weights into edges
 713 ///
 714 /// The following rules are applied to every block BB in the CFG:
 715 ///
 716 /// - If BB has a single predecessor/successor, then the weight
 717 ///   of that edge is the weight of the block.
 718 ///
 719 /// - If all incoming or outgoing edges are known except one, and the
 720 ///   weight of the block is already known, the weight of the unknown
 721 ///   edge will be the weight of the block minus the sum of all the known
 722 ///   edges. If the sum of all the known edges is larger than BB's weight,
 723 ///   we set the unknown edge weight to zero.
 724 ///
 725 /// - If there is a self-referential edge, and the weight of the block is
 726 ///   known, the weight for that edge is set to the weight of the block
 727 ///   minus the weight of the other incoming edges to that block (if
 728 ///   known).
 729 void SampleProfileLoader::propagateWeights(Function &F) {
 730   bool Changed = true;
 731   unsigned I = 0;
 732
 733   // Add an entry count to the function using the samples gathered
 734   // at the function entry.
 735   F.setEntryCount(Samples->getHeadSamples());
 736
 737   // Before propagation starts, build, for each block, a list of
 738   // unique predecessors and successors. This is necessary to handle
 739   // identical edges in multiway branches. Since we visit all blocks and all
 740   // edges of the CFG, it is cleaner to build these lists once at the start
 741   // of the pass.
 742   buildEdges(F);
 743
 744   // Propagate until we converge or we go past the iteration limit.
 745   while (Changed && I++ < SampleProfileMaxPropagateIterations) {
 746     Changed = propagateThroughEdges(F);
 747   }
 748
 749   // Generate MD_prof metadata for every branch instruction using the
 750   // edge weights computed during propagation.
 751   DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n");
 752   LLVMContext &Ctx = F.getContext();
 753   MDBuilder MDB(Ctx);
 754   for (auto &BI : F) {
 755     BasicBlock *BB = &BI;
 756     TerminatorInst *TI = BB->getTerminator();
 757     if (TI->getNumSuccessors() == 1)
 758       continue;
 759     if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
 760       continue;
 761
 762     DEBUG(dbgs() << "\nGetting weights for branch at line "
 763                  << TI->getDebugLoc().getLine() << ".\n");
 764     SmallVector<uint32_t, 4> Weights;
 765     uint32_t MaxWeight = 0;
 766     DebugLoc MaxDestLoc;
 767     for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
 768       BasicBlock *Succ = TI->getSuccessor(I);
 769       Edge E = std::make_pair(BB, Succ);
 770       uint64_t Weight = EdgeWeights[E];
 771       DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E));
 772       // Use uint32_t saturated arithmetic to adjust the incoming weights,
 773       // if needed. Sample counts in profiles are 64-bit unsigned values,
 774       // but internally branch weights are expressed as 32-bit values.
 775       if (Weight > std::numeric_limits<uint32_t>::max()) {
 776         DEBUG(dbgs() << " (saturated due to uint32_t overflow)");
 777         Weight = std::numeric_limits<uint32_t>::max();
 778       }
 779       Weights.push_back(static_cast<uint32_t>(Weight));
 780       if (Weight != 0) {
 781         if (Weight > MaxWeight) {
 782           MaxWeight = Weight;
 783           MaxDestLoc = Succ->getFirstNonPHIOrDbgOrLifetime()->getDebugLoc();
 784         }
 785       }
 786     }
 787
 788     // Only set weights if there is at least one non-zero weight.
 789     // In any other case, let the analyzer set weights.
 790     if (MaxWeight > 0) {
 791       DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n");
 792       TI->setMetadata(llvm::LLVMContext::MD_prof,
 793                       MDB.createBranchWeights(Weights));
 794       DebugLoc BranchLoc = TI->getDebugLoc();
 795       emitOptimizationRemark(
 796           Ctx, DEBUG_TYPE, F, MaxDestLoc,
 797           Twine("most popular destination for conditional branches at ") +
 798               ((BranchLoc) ? Twine(BranchLoc->getFilename() + ":" +
 799                                    Twine(BranchLoc.getLine()) + ":" +
 800                                    Twine(BranchLoc.getCol()))
 801                            : Twine("<UNKNOWN LOCATION>")));
 802     } else {
 803       DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n");
 804     }
 805   }
 806 }
 807
 808 /// \brief Get the line number for the function header.
 809 ///
 810 /// This looks up function \p F in the current compilation unit and
 811 /// retrieves the line number where the function is defined. This is
 812 /// line 0 for all the samples read from the profile file. Every line
 813 /// number is relative to this line.
 814 ///
 815 /// \param F  Function object to query.
 816 ///
 817 /// \returns the line number where \p F is defined. If it returns 0,
 818 ///          it means that there is no debug information available for \p F.
 819 unsigned SampleProfileLoader::getFunctionLoc(Function &F) {
 820   if (DISubprogram *S = getDISubprogram(&F))
 821     return S->getLine();
 822
 823   // If the start of \p F is missing, emit a diagnostic to inform the user
 824   // about the missed opportunity.
 825   F.getContext().diagnose(DiagnosticInfoSampleProfile(
 826       "No debug information found in function " + F.getName() +
 827           ": Function profile not used",
 828       DS_Warning));
 829   return 0;
 830 }
 831
 832 void SampleProfileLoader::computeDominanceAndLoopInfo(Function &F) {
 833   DT.reset(new DominatorTree);
 834   DT->recalculate(F);
 835
 836   PDT.reset(new DominatorTreeBase<BasicBlock>(true));
 837   PDT->recalculate(F);
 838
 839   LI.reset(new LoopInfo);
 840   LI->analyze(*DT);
 841 }
 842
 843 /// \brief Generate branch weight metadata for all branches in \p F.
 844 ///
 845 /// Branch weights are computed out of instruction samples using a
 846 /// propagation heuristic. Propagation proceeds in 3 phases:
 847 ///
 848 /// 1- Assignment of block weights. All the basic blocks in the function
 849 ///    are initial assigned the same weight as their most frequently
 850 ///    executed instruction.
 851 ///
 852 /// 2- Creation of equivalence classes. Since samples may be missing from
 853 ///    blocks, we can fill in the gaps by setting the weights of all the
 854 ///    blocks in the same equivalence class to the same weight. To compute
 855 ///    the concept of equivalence, we use dominance and loop information.
 856 ///    Two blocks B1 and B2 are in the same equivalence class if B1
 857 ///    dominates B2, B2 post-dominates B1 and both are in the same loop.
 858 ///
 859 /// 3- Propagation of block weights into edges. This uses a simple
 860 ///    propagation heuristic. The following rules are applied to every
 861 ///    block BB in the CFG:
 862 ///
 863 ///    - If BB has a single predecessor/successor, then the weight
 864 ///      of that edge is the weight of the block.
 865 ///
 866 ///    - If all the edges are known except one, and the weight of the
 867 ///      block is already known, the weight of the unknown edge will
 868 ///      be the weight of the block minus the sum of all the known
 869 ///      edges. If the sum of all the known edges is larger than BB's weight,
 870 ///      we set the unknown edge weight to zero.
 871 ///
 872 ///    - If there is a self-referential edge, and the weight of the block is
 873 ///      known, the weight for that edge is set to the weight of the block
 874 ///      minus the weight of the other incoming edges to that block (if
 875 ///      known).
 876 ///
 877 /// Since this propagation is not guaranteed to finalize for every CFG, we
 878 /// only allow it to proceed for a limited number of iterations (controlled
 879 /// by -sample-profile-max-propagate-iterations).
 880 ///
 881 /// FIXME: Try to replace this propagation heuristic with a scheme
 882 /// that is guaranteed to finalize. A work-list approach similar to
 883 /// the standard value propagation algorithm used by SSA-CCP might
 884 /// work here.
 885 ///
 886 /// Once all the branch weights are computed, we emit the MD_prof
 887 /// metadata on BB using the computed values for each of its branches.
 888 ///
 889 /// \param F The function to query.
 890 ///
 891 /// \returns true if \p F was modified. Returns false, otherwise.
 892 bool SampleProfileLoader::emitAnnotations(Function &F) {
 893   bool Changed = false;
 894
 895   if (getFunctionLoc(F) == 0)
 896     return false;
 897
 898   DEBUG(dbgs() << "Line number for the first instruction in " << F.getName()
 899                << ": " << getFunctionLoc(F) << "\n");
 900
 901   Changed |= inlineHotFunctions(F);
 902
 903   // Compute basic block weights.
 904   Changed |= computeBlockWeights(F);
 905
 906   if (Changed) {
 907     // Compute dominance and loop info needed for propagation.
 908     computeDominanceAndLoopInfo(F);
 909
 910     // Find equivalence classes.
 911     findEquivalenceClasses(F);
 912
 913     // Propagate weights to all edges.
 914     propagateWeights(F);
 915   }
 916
 917   return Changed;
 918 }
 919
 920 char SampleProfileLoader::ID = 0;
 921 INITIALIZE_PASS_BEGIN(SampleProfileLoader, "sample-profile",
 922                       "Sample Profile loader", false, false)
 923 INITIALIZE_PASS_DEPENDENCY(AddDiscriminators)
 924 INITIALIZE_PASS_END(SampleProfileLoader, "sample-profile",
 925                     "Sample Profile loader", false, false)
 926
 927 bool SampleProfileLoader::doInitialization(Module &M) {
 928   auto &Ctx = M.getContext();
 929   auto ReaderOrErr = SampleProfileReader::create(Filename, Ctx);
 930   if (std::error_code EC = ReaderOrErr.getError()) {
 931     std::string Msg = "Could not open profile: " + EC.message();
 932     Ctx.diagnose(DiagnosticInfoSampleProfile(Filename.data(), Msg));
 933     return false;
 934   }
 935   Reader = std::move(ReaderOrErr.get());
 936   ProfileIsValid = (Reader->read() == sampleprof_error::success);
 937   return true;
 938 }
 939
 940 ModulePass *llvm::createSampleProfileLoaderPass() {
 941   return new SampleProfileLoader(SampleProfileFile);
 942 }
 943
 944 ModulePass *llvm::createSampleProfileLoaderPass(StringRef Name) {
 945   return new SampleProfileLoader(Name);
 946 }
 947
 948 bool SampleProfileLoader::runOnModule(Module &M) {
 949   if (!ProfileIsValid)
 950     return false;
 951
 952   bool retval = false;
 953   for (auto &F : M)
 954     if (!F.isDeclaration()) {
 955       clearFunctionData();
 956       retval |= runOnFunction(F);
 957     }
 958   return retval;
 959 }
 960
 961 bool SampleProfileLoader::runOnFunction(Function &F) {
 962   Samples = Reader->getSamplesFor(F);
 963   if (!Samples->empty())
 964     return emitAnnotations(F);
 965   return false;
 966 }