contrib/llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

   1 //===-- PGOInstrumentation.cpp - MST-based PGO Instrumentation ------------===//
   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 PGO instrumentation using a minimum spanning tree based
  11 // on the following paper:
  12 //   [1] Donald E. Knuth, Francis R. Stevenson. Optimal measurement of points
  13 //   for program frequency counts. BIT Numerical Mathematics 1973, Volume 13,
  14 //   Issue 3, pp 313-322
  15 // The idea of the algorithm based on the fact that for each node (except for
  16 // the entry and exit), the sum of incoming edge counts equals the sum of
  17 // outgoing edge counts. The count of edge on spanning tree can be derived from
  18 // those edges not on the spanning tree. Knuth proves this method instruments
  19 // the minimum number of edges.
  20 //
  21 // The minimal spanning tree here is actually a maximum weight tree -- on-tree
  22 // edges have higher frequencies (more likely to execute). The idea is to
  23 // instrument those less frequently executed edges to reduce the runtime
  24 // overhead of instrumented binaries.
  25 //
  26 // This file contains two passes:
  27 // (1) Pass PGOInstrumentationGen which instruments the IR to generate edge
  28 // count profile, and generates the instrumentation for indirect call
  29 // profiling.
  30 // (2) Pass PGOInstrumentationUse which reads the edge count profile and
  31 // annotates the branch weights. It also reads the indirect call value
  32 // profiling records and annotate the indirect call instructions.
  33 //
  34 // To get the precise counter information, These two passes need to invoke at
  35 // the same compilation point (so they see the same IR). For pass
  36 // PGOInstrumentationGen, the real work is done in instrumentOneFunc(). For
  37 // pass PGOInstrumentationUse, the real work in done in class PGOUseFunc and
  38 // the profile is opened in module level and passed to each PGOUseFunc instance.
  39 // The shared code for PGOInstrumentationGen and PGOInstrumentationUse is put
  40 // in class FuncPGOInstrumentation.
  41 //
  42 // Class PGOEdge represents a CFG edge and some auxiliary information. Class
  43 // BBInfo contains auxiliary information for each BB. These two classes are used
  44 // in pass PGOInstrumentationGen. Class PGOUseEdge and UseBBInfo are the derived
  45 // class of PGOEdge and BBInfo, respectively. They contains extra data structure
  46 // used in populating profile counters.
  47 // The MST implementation is in Class CFGMST (CFGMST.h).
  48 //
  49 //===----------------------------------------------------------------------===//
  50
  51 #include "llvm/Transforms/PGOInstrumentation.h"
  52 #include "CFGMST.h"
  53 #include "llvm/ADT/STLExtras.h"
  54 #include "llvm/ADT/SmallVector.h"
  55 #include "llvm/ADT/Statistic.h"
  56 #include "llvm/ADT/Triple.h"
  57 #include "llvm/Analysis/BlockFrequencyInfo.h"
  58 #include "llvm/Analysis/BranchProbabilityInfo.h"
  59 #include "llvm/Analysis/CFG.h"
  60 #include "llvm/Analysis/IndirectCallSiteVisitor.h"
  61 #include "llvm/IR/CallSite.h"
  62 #include "llvm/IR/DiagnosticInfo.h"
  63 #include "llvm/IR/GlobalValue.h"
  64 #include "llvm/IR/IRBuilder.h"
  65 #include "llvm/IR/InstIterator.h"
  66 #include "llvm/IR/Instructions.h"
  67 #include "llvm/IR/IntrinsicInst.h"
  68 #include "llvm/IR/MDBuilder.h"
  69 #include "llvm/IR/Module.h"
  70 #include "llvm/Pass.h"
  71 #include "llvm/ProfileData/InstrProfReader.h"
  72 #include "llvm/ProfileData/ProfileCommon.h"
  73 #include "llvm/Support/BranchProbability.h"
  74 #include "llvm/Support/Debug.h"
  75 #include "llvm/Support/JamCRC.h"
  76 #include "llvm/Transforms/Instrumentation.h"
  77 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  78 #include <algorithm>
  79 #include <string>
  80 #include <unordered_map>
  81 #include <utility>
  82 #include <vector>
  83
  84 using namespace llvm;
  85
  86 #define DEBUG_TYPE "pgo-instrumentation"
  87
  88 STATISTIC(NumOfPGOInstrument, "Number of edges instrumented.");
  89 STATISTIC(NumOfPGOSelectInsts, "Number of select instruction instrumented.");
  90 STATISTIC(NumOfPGOEdge, "Number of edges.");
  91 STATISTIC(NumOfPGOBB, "Number of basic-blocks.");
  92 STATISTIC(NumOfPGOSplit, "Number of critical edge splits.");
  93 STATISTIC(NumOfPGOFunc, "Number of functions having valid profile counts.");
  94 STATISTIC(NumOfPGOMismatch, "Number of functions having mismatch profile.");
  95 STATISTIC(NumOfPGOMissing, "Number of functions without profile.");
  96 STATISTIC(NumOfPGOICall, "Number of indirect call value instrumentations.");
  97
  98 // Command line option to specify the file to read profile from. This is
  99 // mainly used for testing.
 100 static cl::opt<std::string>
 101     PGOTestProfileFile("pgo-test-profile-file", cl::init(""), cl::Hidden,
 102                        cl::value_desc("filename"),
 103                        cl::desc("Specify the path of profile data file. This is"
 104                                 "mainly for test purpose."));
 105
 106 // Command line option to disable value profiling. The default is false:
 107 // i.e. value profiling is enabled by default. This is for debug purpose.
 108 static cl::opt<bool> DisableValueProfiling("disable-vp", cl::init(false),
 109                                            cl::Hidden,
 110                                            cl::desc("Disable Value Profiling"));
 111
 112 // Command line option to set the maximum number of VP annotations to write to
 113 // the metadata for a single indirect call callsite.
 114 static cl::opt<unsigned> MaxNumAnnotations(
 115     "icp-max-annotations", cl::init(3), cl::Hidden, cl::ZeroOrMore,
 116     cl::desc("Max number of annotations for a single indirect "
 117              "call callsite"));
 118
 119 // Command line option to control appending FunctionHash to the name of a COMDAT
 120 // function. This is to avoid the hash mismatch caused by the preinliner.
 121 static cl::opt<bool> DoComdatRenaming(
 122     "do-comdat-renaming", cl::init(true), cl::Hidden,
 123     cl::desc("Append function hash to the name of COMDAT function to avoid "
 124              "function hash mismatch due to the preinliner"));
 125
 126 // Command line option to enable/disable the warning about missing profile
 127 // information.
 128 static cl::opt<bool> PGOWarnMissing("pgo-warn-missing-function",
 129                                      cl::init(false),
 130                                      cl::Hidden);
 131
 132 // Command line option to enable/disable the warning about a hash mismatch in
 133 // the profile data.
 134 static cl::opt<bool> NoPGOWarnMismatch("no-pgo-warn-mismatch", cl::init(false),
 135                                        cl::Hidden);
 136
 137 // Command line option to enable/disable select instruction instrumentation.
 138 static cl::opt<bool> PGOInstrSelect("pgo-instr-select", cl::init(true),
 139                                     cl::Hidden);
 140 namespace {
 141
 142 /// The select instruction visitor plays three roles specified
 143 /// by the mode. In \c VM_counting mode, it simply counts the number of
 144 /// select instructions. In \c VM_instrument mode, it inserts code to count
 145 /// the number times TrueValue of select is taken. In \c VM_annotate mode,
 146 /// it reads the profile data and annotate the select instruction with metadata.
 147 enum VisitMode { VM_counting, VM_instrument, VM_annotate };
 148 class PGOUseFunc;
 149
 150 /// Instruction Visitor class to visit select instructions.
 151 struct SelectInstVisitor : public InstVisitor<SelectInstVisitor> {
 152   Function &F;
 153   unsigned NSIs = 0;             // Number of select instructions instrumented.
 154   VisitMode Mode = VM_counting;  // Visiting mode.
 155   unsigned *CurCtrIdx = nullptr; // Pointer to current counter index.
 156   unsigned TotalNumCtrs = 0;     // Total number of counters
 157   GlobalVariable *FuncNameVar = nullptr;
 158   uint64_t FuncHash = 0;
 159   PGOUseFunc *UseFunc = nullptr;
 160
 161   SelectInstVisitor(Function &Func) : F(Func) {}
 162
 163   void countSelects(Function &Func) {
 164     Mode = VM_counting;
 165     visit(Func);
 166   }
 167   // Visit the IR stream and instrument all select instructions. \p
 168   // Ind is a pointer to the counter index variable; \p TotalNC
 169   // is the total number of counters; \p FNV is the pointer to the
 170   // PGO function name var; \p FHash is the function hash.
 171   void instrumentSelects(Function &Func, unsigned *Ind, unsigned TotalNC,
 172                          GlobalVariable *FNV, uint64_t FHash) {
 173     Mode = VM_instrument;
 174     CurCtrIdx = Ind;
 175     TotalNumCtrs = TotalNC;
 176     FuncHash = FHash;
 177     FuncNameVar = FNV;
 178     visit(Func);
 179   }
 180
 181   // Visit the IR stream and annotate all select instructions.
 182   void annotateSelects(Function &Func, PGOUseFunc *UF, unsigned *Ind) {
 183     Mode = VM_annotate;
 184     UseFunc = UF;
 185     CurCtrIdx = Ind;
 186     visit(Func);
 187   }
 188
 189   void instrumentOneSelectInst(SelectInst &SI);
 190   void annotateOneSelectInst(SelectInst &SI);
 191   // Visit \p SI instruction and perform tasks according to visit mode.
 192   void visitSelectInst(SelectInst &SI);
 193   unsigned getNumOfSelectInsts() const { return NSIs; }
 194 };
 195
 196 class PGOInstrumentationGenLegacyPass : public ModulePass {
 197 public:
 198   static char ID;
 199
 200   PGOInstrumentationGenLegacyPass() : ModulePass(ID) {
 201     initializePGOInstrumentationGenLegacyPassPass(
 202         *PassRegistry::getPassRegistry());
 203   }
 204
 205   StringRef getPassName() const override { return "PGOInstrumentationGenPass"; }
 206
 207 private:
 208   bool runOnModule(Module &M) override;
 209
 210   void getAnalysisUsage(AnalysisUsage &AU) const override {
 211     AU.addRequired<BlockFrequencyInfoWrapperPass>();
 212   }
 213 };
 214
 215 class PGOInstrumentationUseLegacyPass : public ModulePass {
 216 public:
 217   static char ID;
 218
 219   // Provide the profile filename as the parameter.
 220   PGOInstrumentationUseLegacyPass(std::string Filename = "")
 221       : ModulePass(ID), ProfileFileName(std::move(Filename)) {
 222     if (!PGOTestProfileFile.empty())
 223       ProfileFileName = PGOTestProfileFile;
 224     initializePGOInstrumentationUseLegacyPassPass(
 225         *PassRegistry::getPassRegistry());
 226   }
 227
 228   StringRef getPassName() const override { return "PGOInstrumentationUsePass"; }
 229
 230 private:
 231   std::string ProfileFileName;
 232
 233   bool runOnModule(Module &M) override;
 234   void getAnalysisUsage(AnalysisUsage &AU) const override {
 235     AU.addRequired<BlockFrequencyInfoWrapperPass>();
 236   }
 237 };
 238
 239 } // end anonymous namespace
 240
 241 char PGOInstrumentationGenLegacyPass::ID = 0;
 242 INITIALIZE_PASS_BEGIN(PGOInstrumentationGenLegacyPass, "pgo-instr-gen",
 243                       "PGO instrumentation.", false, false)
 244 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 245 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
 246 INITIALIZE_PASS_END(PGOInstrumentationGenLegacyPass, "pgo-instr-gen",
 247                     "PGO instrumentation.", false, false)
 248
 249 ModulePass *llvm::createPGOInstrumentationGenLegacyPass() {
 250   return new PGOInstrumentationGenLegacyPass();
 251 }
 252
 253 char PGOInstrumentationUseLegacyPass::ID = 0;
 254 INITIALIZE_PASS_BEGIN(PGOInstrumentationUseLegacyPass, "pgo-instr-use",
 255                       "Read PGO instrumentation profile.", false, false)
 256 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 257 INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
 258 INITIALIZE_PASS_END(PGOInstrumentationUseLegacyPass, "pgo-instr-use",
 259                     "Read PGO instrumentation profile.", false, false)
 260
 261 ModulePass *llvm::createPGOInstrumentationUseLegacyPass(StringRef Filename) {
 262   return new PGOInstrumentationUseLegacyPass(Filename.str());
 263 }
 264
 265 namespace {
 266 /// \brief An MST based instrumentation for PGO
 267 ///
 268 /// Implements a Minimum Spanning Tree (MST) based instrumentation for PGO
 269 /// in the function level.
 270 struct PGOEdge {
 271   // This class implements the CFG edges. Note the CFG can be a multi-graph.
 272   // So there might be multiple edges with same SrcBB and DestBB.
 273   const BasicBlock *SrcBB;
 274   const BasicBlock *DestBB;
 275   uint64_t Weight;
 276   bool InMST;
 277   bool Removed;
 278   bool IsCritical;
 279   PGOEdge(const BasicBlock *Src, const BasicBlock *Dest, unsigned W = 1)
 280       : SrcBB(Src), DestBB(Dest), Weight(W), InMST(false), Removed(false),
 281         IsCritical(false) {}
 282   // Return the information string of an edge.
 283   const std::string infoString() const {
 284     return (Twine(Removed ? "-" : " ") + (InMST ? " " : "*") +
 285             (IsCritical ? "c" : " ") + "  W=" + Twine(Weight)).str();
 286   }
 287 };
 288
 289 // This class stores the auxiliary information for each BB.
 290 struct BBInfo {
 291   BBInfo *Group;
 292   uint32_t Index;
 293   uint32_t Rank;
 294
 295   BBInfo(unsigned IX) : Group(this), Index(IX), Rank(0) {}
 296
 297   // Return the information string of this object.
 298   const std::string infoString() const {
 299     return (Twine("Index=") + Twine(Index)).str();
 300   }
 301 };
 302
 303 // This class implements the CFG edges. Note the CFG can be a multi-graph.
 304 template <class Edge, class BBInfo> class FuncPGOInstrumentation {
 305 private:
 306   Function &F;
 307   void computeCFGHash();
 308   void renameComdatFunction();
 309   // A map that stores the Comdat group in function F.
 310   std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers;
 311
 312 public:
 313   std::vector<Instruction *> IndirectCallSites;
 314   SelectInstVisitor SIVisitor;
 315   std::string FuncName;
 316   GlobalVariable *FuncNameVar;
 317   // CFG hash value for this function.
 318   uint64_t FunctionHash;
 319
 320   // The Minimum Spanning Tree of function CFG.
 321   CFGMST<Edge, BBInfo> MST;
 322
 323   // Give an edge, find the BB that will be instrumented.
 324   // Return nullptr if there is no BB to be instrumented.
 325   BasicBlock *getInstrBB(Edge *E);
 326
 327   // Return the auxiliary BB information.
 328   BBInfo &getBBInfo(const BasicBlock *BB) const { return MST.getBBInfo(BB); }
 329
 330   // Return the auxiliary BB information if available.
 331   BBInfo *findBBInfo(const BasicBlock *BB) const { return MST.findBBInfo(BB); }
 332
 333   // Dump edges and BB information.
 334   void dumpInfo(std::string Str = "") const {
 335     MST.dumpEdges(dbgs(), Twine("Dump Function ") + FuncName + " Hash: " +
 336                               Twine(FunctionHash) + "\t" + Str);
 337   }
 338
 339   FuncPGOInstrumentation(
 340       Function &Func,
 341       std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
 342       bool CreateGlobalVar = false, BranchProbabilityInfo *BPI = nullptr,
 343       BlockFrequencyInfo *BFI = nullptr)
 344       : F(Func), ComdatMembers(ComdatMembers), SIVisitor(Func), FunctionHash(0),
 345         MST(F, BPI, BFI) {
 346
 347     // This should be done before CFG hash computation.
 348     SIVisitor.countSelects(Func);
 349     NumOfPGOSelectInsts += SIVisitor.getNumOfSelectInsts();
 350     IndirectCallSites = findIndirectCallSites(Func);
 351
 352     FuncName = getPGOFuncName(F);
 353     computeCFGHash();
 354     if (ComdatMembers.size())
 355       renameComdatFunction();
 356     DEBUG(dumpInfo("after CFGMST"));
 357
 358     NumOfPGOBB += MST.BBInfos.size();
 359     for (auto &E : MST.AllEdges) {
 360       if (E->Removed)
 361         continue;
 362       NumOfPGOEdge++;
 363       if (!E->InMST)
 364         NumOfPGOInstrument++;
 365     }
 366
 367     if (CreateGlobalVar)
 368       FuncNameVar = createPGOFuncNameVar(F, FuncName);
 369   }
 370
 371   // Return the number of profile counters needed for the function.
 372   unsigned getNumCounters() {
 373     unsigned NumCounters = 0;
 374     for (auto &E : this->MST.AllEdges) {
 375       if (!E->InMST && !E->Removed)
 376         NumCounters++;
 377     }
 378     return NumCounters + SIVisitor.getNumOfSelectInsts();
 379   }
 380 };
 381
 382 // Compute Hash value for the CFG: the lower 32 bits are CRC32 of the index
 383 // value of each BB in the CFG. The higher 32 bits record the number of edges.
 384 template <class Edge, class BBInfo>
 385 void FuncPGOInstrumentation<Edge, BBInfo>::computeCFGHash() {
 386   std::vector<char> Indexes;
 387   JamCRC JC;
 388   for (auto &BB : F) {
 389     const TerminatorInst *TI = BB.getTerminator();
 390     for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) {
 391       BasicBlock *Succ = TI->getSuccessor(I);
 392       auto BI = findBBInfo(Succ);
 393       if (BI == nullptr)
 394         continue;
 395       uint32_t Index = BI->Index;
 396       for (int J = 0; J < 4; J++)
 397         Indexes.push_back((char)(Index >> (J * 8)));
 398     }
 399   }
 400   JC.update(Indexes);
 401   FunctionHash = (uint64_t)SIVisitor.getNumOfSelectInsts() << 56 |
 402                  (uint64_t)IndirectCallSites.size() << 48 |
 403                  (uint64_t)MST.AllEdges.size() << 32 | JC.getCRC();
 404 }
 405
 406 // Check if we can safely rename this Comdat function.
 407 static bool canRenameComdat(
 408     Function &F,
 409     std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
 410   if (F.getName().empty())
 411     return false;
 412   if (!needsComdatForCounter(F, *(F.getParent())))
 413     return false;
 414   // Only safe to do if this function may be discarded if it is not used
 415   // in the compilation unit.
 416   if (!GlobalValue::isDiscardableIfUnused(F.getLinkage()))
 417     return false;
 418
 419   // For AvailableExternallyLinkage functions.
 420   if (!F.hasComdat()) {
 421     assert(F.getLinkage() == GlobalValue::AvailableExternallyLinkage);
 422     return true;
 423   }
 424
 425   // FIXME: Current only handle those Comdat groups that only containing one
 426   // function and function aliases.
 427   // (1) For a Comdat group containing multiple functions, we need to have a
 428   // unique postfix based on the hashes for each function. There is a
 429   // non-trivial code refactoring to do this efficiently.
 430   // (2) Variables can not be renamed, so we can not rename Comdat function in a
 431   // group including global vars.
 432   Comdat *C = F.getComdat();
 433   for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
 434     if (dyn_cast<GlobalAlias>(CM.second))
 435       continue;
 436     Function *FM = dyn_cast<Function>(CM.second);
 437     if (FM != &F)
 438       return false;
 439   }
 440   return true;
 441 }
 442
 443 // Append the CFGHash to the Comdat function name.
 444 template <class Edge, class BBInfo>
 445 void FuncPGOInstrumentation<Edge, BBInfo>::renameComdatFunction() {
 446   if (!canRenameComdat(F, ComdatMembers))
 447     return;
 448   std::string OrigName = F.getName().str();
 449   std::string NewFuncName =
 450       Twine(F.getName() + "." + Twine(FunctionHash)).str();
 451   F.setName(Twine(NewFuncName));
 452   GlobalAlias::create(GlobalValue::WeakAnyLinkage, OrigName, &F);
 453   FuncName = Twine(FuncName + "." + Twine(FunctionHash)).str();
 454   Comdat *NewComdat;
 455   Module *M = F.getParent();
 456   // For AvailableExternallyLinkage functions, change the linkage to
 457   // LinkOnceODR and put them into comdat. This is because after renaming, there
 458   // is no backup external copy available for the function.
 459   if (!F.hasComdat()) {
 460     assert(F.getLinkage() == GlobalValue::AvailableExternallyLinkage);
 461     NewComdat = M->getOrInsertComdat(StringRef(NewFuncName));
 462     F.setLinkage(GlobalValue::LinkOnceODRLinkage);
 463     F.setComdat(NewComdat);
 464     return;
 465   }
 466
 467   // This function belongs to a single function Comdat group.
 468   Comdat *OrigComdat = F.getComdat();
 469   std::string NewComdatName =
 470       Twine(OrigComdat->getName() + "." + Twine(FunctionHash)).str();
 471   NewComdat = M->getOrInsertComdat(StringRef(NewComdatName));
 472   NewComdat->setSelectionKind(OrigComdat->getSelectionKind());
 473
 474   for (auto &&CM : make_range(ComdatMembers.equal_range(OrigComdat))) {
 475     if (GlobalAlias *GA = dyn_cast<GlobalAlias>(CM.second)) {
 476       // For aliases, change the name directly.
 477       assert(dyn_cast<Function>(GA->getAliasee()->stripPointerCasts()) == &F);
 478       std::string OrigGAName = GA->getName().str();
 479       GA->setName(Twine(GA->getName() + "." + Twine(FunctionHash)));
 480       GlobalAlias::create(GlobalValue::WeakAnyLinkage, OrigGAName, GA);
 481       continue;
 482     }
 483     // Must be a function.
 484     Function *CF = dyn_cast<Function>(CM.second);
 485     assert(CF);
 486     CF->setComdat(NewComdat);
 487   }
 488 }
 489
 490 // Given a CFG E to be instrumented, find which BB to place the instrumented
 491 // code. The function will split the critical edge if necessary.
 492 template <class Edge, class BBInfo>
 493 BasicBlock *FuncPGOInstrumentation<Edge, BBInfo>::getInstrBB(Edge *E) {
 494   if (E->InMST || E->Removed)
 495     return nullptr;
 496
 497   BasicBlock *SrcBB = const_cast<BasicBlock *>(E->SrcBB);
 498   BasicBlock *DestBB = const_cast<BasicBlock *>(E->DestBB);
 499   // For a fake edge, instrument the real BB.
 500   if (SrcBB == nullptr)
 501     return DestBB;
 502   if (DestBB == nullptr)
 503     return SrcBB;
 504
 505   // Instrument the SrcBB if it has a single successor,
 506   // otherwise, the DestBB if this is not a critical edge.
 507   TerminatorInst *TI = SrcBB->getTerminator();
 508   if (TI->getNumSuccessors() <= 1)
 509     return SrcBB;
 510   if (!E->IsCritical)
 511     return DestBB;
 512
 513   // For a critical edge, we have to split. Instrument the newly
 514   // created BB.
 515   NumOfPGOSplit++;
 516   DEBUG(dbgs() << "Split critical edge: " << getBBInfo(SrcBB).Index << " --> "
 517                << getBBInfo(DestBB).Index << "\n");
 518   unsigned SuccNum = GetSuccessorNumber(SrcBB, DestBB);
 519   BasicBlock *InstrBB = SplitCriticalEdge(TI, SuccNum);
 520   assert(InstrBB && "Critical edge is not split");
 521
 522   E->Removed = true;
 523   return InstrBB;
 524 }
 525
 526 // Visit all edge and instrument the edges not in MST, and do value profiling.
 527 // Critical edges will be split.
 528 static void instrumentOneFunc(
 529     Function &F, Module *M, BranchProbabilityInfo *BPI, BlockFrequencyInfo *BFI,
 530     std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
 531   FuncPGOInstrumentation<PGOEdge, BBInfo> FuncInfo(F, ComdatMembers, true, BPI,
 532                                                    BFI);
 533   unsigned NumCounters = FuncInfo.getNumCounters();
 534
 535   uint32_t I = 0;
 536   Type *I8PtrTy = Type::getInt8PtrTy(M->getContext());
 537   for (auto &E : FuncInfo.MST.AllEdges) {
 538     BasicBlock *InstrBB = FuncInfo.getInstrBB(E.get());
 539     if (!InstrBB)
 540       continue;
 541
 542     IRBuilder<> Builder(InstrBB, InstrBB->getFirstInsertionPt());
 543     assert(Builder.GetInsertPoint() != InstrBB->end() &&
 544            "Cannot get the Instrumentation point");
 545     Builder.CreateCall(
 546         Intrinsic::getDeclaration(M, Intrinsic::instrprof_increment),
 547         {llvm::ConstantExpr::getBitCast(FuncInfo.FuncNameVar, I8PtrTy),
 548          Builder.getInt64(FuncInfo.FunctionHash), Builder.getInt32(NumCounters),
 549          Builder.getInt32(I++)});
 550   }
 551
 552   // Now instrument select instructions:
 553   FuncInfo.SIVisitor.instrumentSelects(F, &I, NumCounters, FuncInfo.FuncNameVar,
 554                                        FuncInfo.FunctionHash);
 555   assert(I == NumCounters);
 556
 557   if (DisableValueProfiling)
 558     return;
 559
 560   unsigned NumIndirectCallSites = 0;
 561   for (auto &I : FuncInfo.IndirectCallSites) {
 562     CallSite CS(I);
 563     Value *Callee = CS.getCalledValue();
 564     DEBUG(dbgs() << "Instrument one indirect call: CallSite Index = "
 565                  << NumIndirectCallSites << "\n");
 566     IRBuilder<> Builder(I);
 567     assert(Builder.GetInsertPoint() != I->getParent()->end() &&
 568            "Cannot get the Instrumentation point");
 569     Builder.CreateCall(
 570         Intrinsic::getDeclaration(M, Intrinsic::instrprof_value_profile),
 571         {llvm::ConstantExpr::getBitCast(FuncInfo.FuncNameVar, I8PtrTy),
 572          Builder.getInt64(FuncInfo.FunctionHash),
 573          Builder.CreatePtrToInt(Callee, Builder.getInt64Ty()),
 574          Builder.getInt32(llvm::InstrProfValueKind::IPVK_IndirectCallTarget),
 575          Builder.getInt32(NumIndirectCallSites++)});
 576   }
 577   NumOfPGOICall += NumIndirectCallSites;
 578 }
 579
 580 // This class represents a CFG edge in profile use compilation.
 581 struct PGOUseEdge : public PGOEdge {
 582   bool CountValid;
 583   uint64_t CountValue;
 584   PGOUseEdge(const BasicBlock *Src, const BasicBlock *Dest, unsigned W = 1)
 585       : PGOEdge(Src, Dest, W), CountValid(false), CountValue(0) {}
 586
 587   // Set edge count value
 588   void setEdgeCount(uint64_t Value) {
 589     CountValue = Value;
 590     CountValid = true;
 591   }
 592
 593   // Return the information string for this object.
 594   const std::string infoString() const {
 595     if (!CountValid)
 596       return PGOEdge::infoString();
 597     return (Twine(PGOEdge::infoString()) + "  Count=" + Twine(CountValue))
 598         .str();
 599   }
 600 };
 601
 602 typedef SmallVector<PGOUseEdge *, 2> DirectEdges;
 603
 604 // This class stores the auxiliary information for each BB.
 605 struct UseBBInfo : public BBInfo {
 606   uint64_t CountValue;
 607   bool CountValid;
 608   int32_t UnknownCountInEdge;
 609   int32_t UnknownCountOutEdge;
 610   DirectEdges InEdges;
 611   DirectEdges OutEdges;
 612   UseBBInfo(unsigned IX)
 613       : BBInfo(IX), CountValue(0), CountValid(false), UnknownCountInEdge(0),
 614         UnknownCountOutEdge(0) {}
 615   UseBBInfo(unsigned IX, uint64_t C)
 616       : BBInfo(IX), CountValue(C), CountValid(true), UnknownCountInEdge(0),
 617         UnknownCountOutEdge(0) {}
 618
 619   // Set the profile count value for this BB.
 620   void setBBInfoCount(uint64_t Value) {
 621     CountValue = Value;
 622     CountValid = true;
 623   }
 624
 625   // Return the information string of this object.
 626   const std::string infoString() const {
 627     if (!CountValid)
 628       return BBInfo::infoString();
 629     return (Twine(BBInfo::infoString()) + "  Count=" + Twine(CountValue)).str();
 630   }
 631 };
 632
 633 // Sum up the count values for all the edges.
 634 static uint64_t sumEdgeCount(const ArrayRef<PGOUseEdge *> Edges) {
 635   uint64_t Total = 0;
 636   for (auto &E : Edges) {
 637     if (E->Removed)
 638       continue;
 639     Total += E->CountValue;
 640   }
 641   return Total;
 642 }
 643
 644 class PGOUseFunc {
 645 public:
 646   PGOUseFunc(Function &Func, Module *Modu,
 647              std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers,
 648              BranchProbabilityInfo *BPI = nullptr,
 649              BlockFrequencyInfo *BFI = nullptr)
 650       : F(Func), M(Modu), FuncInfo(Func, ComdatMembers, false, BPI, BFI),
 651         CountPosition(0), ProfileCountSize(0), FreqAttr(FFA_Normal) {}
 652
 653   // Read counts for the instrumented BB from profile.
 654   bool readCounters(IndexedInstrProfReader *PGOReader);
 655
 656   // Populate the counts for all BBs.
 657   void populateCounters();
 658
 659   // Set the branch weights based on the count values.
 660   void setBranchWeights();
 661
 662   // Annotate the indirect call sites.
 663   void annotateIndirectCallSites();
 664
 665   // The hotness of the function from the profile count.
 666   enum FuncFreqAttr { FFA_Normal, FFA_Cold, FFA_Hot };
 667
 668   // Return the function hotness from the profile.
 669   FuncFreqAttr getFuncFreqAttr() const { return FreqAttr; }
 670
 671   // Return the function hash.
 672   uint64_t getFuncHash() const { return FuncInfo.FunctionHash; }
 673   // Return the profile record for this function;
 674   InstrProfRecord &getProfileRecord() { return ProfileRecord; }
 675
 676   // Return the auxiliary BB information.
 677   UseBBInfo &getBBInfo(const BasicBlock *BB) const {
 678     return FuncInfo.getBBInfo(BB);
 679   }
 680
 681   // Return the auxiliary BB information if available.
 682   UseBBInfo *findBBInfo(const BasicBlock *BB) const {
 683     return FuncInfo.findBBInfo(BB);
 684   }
 685
 686 private:
 687   Function &F;
 688   Module *M;
 689   // This member stores the shared information with class PGOGenFunc.
 690   FuncPGOInstrumentation<PGOUseEdge, UseBBInfo> FuncInfo;
 691
 692   // The maximum count value in the profile. This is only used in PGO use
 693   // compilation.
 694   uint64_t ProgramMaxCount;
 695
 696   // Position of counter that remains to be read.
 697   uint32_t CountPosition;
 698
 699   // Total size of the profile count for this function.
 700   uint32_t ProfileCountSize;
 701
 702   // ProfileRecord for this function.
 703   InstrProfRecord ProfileRecord;
 704
 705   // Function hotness info derived from profile.
 706   FuncFreqAttr FreqAttr;
 707
 708   // Find the Instrumented BB and set the value.
 709   void setInstrumentedCounts(const std::vector<uint64_t> &CountFromProfile);
 710
 711   // Set the edge counter value for the unknown edge -- there should be only
 712   // one unknown edge.
 713   void setEdgeCount(DirectEdges &Edges, uint64_t Value);
 714
 715   // Return FuncName string;
 716   const std::string getFuncName() const { return FuncInfo.FuncName; }
 717
 718   // Set the hot/cold inline hints based on the count values.
 719   // FIXME: This function should be removed once the functionality in
 720   // the inliner is implemented.
 721   void markFunctionAttributes(uint64_t EntryCount, uint64_t MaxCount) {
 722     if (ProgramMaxCount == 0)
 723       return;
 724     // Threshold of the hot functions.
 725     const BranchProbability HotFunctionThreshold(1, 100);
 726     // Threshold of the cold functions.
 727     const BranchProbability ColdFunctionThreshold(2, 10000);
 728     if (EntryCount >= HotFunctionThreshold.scale(ProgramMaxCount))
 729       FreqAttr = FFA_Hot;
 730     else if (MaxCount <= ColdFunctionThreshold.scale(ProgramMaxCount))
 731       FreqAttr = FFA_Cold;
 732   }
 733 };
 734
 735 // Visit all the edges and assign the count value for the instrumented
 736 // edges and the BB.
 737 void PGOUseFunc::setInstrumentedCounts(
 738     const std::vector<uint64_t> &CountFromProfile) {
 739
 740   assert(FuncInfo.getNumCounters() == CountFromProfile.size());
 741   // Use a worklist as we will update the vector during the iteration.
 742   std::vector<PGOUseEdge *> WorkList;
 743   for (auto &E : FuncInfo.MST.AllEdges)
 744     WorkList.push_back(E.get());
 745
 746   uint32_t I = 0;
 747   for (auto &E : WorkList) {
 748     BasicBlock *InstrBB = FuncInfo.getInstrBB(E);
 749     if (!InstrBB)
 750       continue;
 751     uint64_t CountValue = CountFromProfile[I++];
 752     if (!E->Removed) {
 753       getBBInfo(InstrBB).setBBInfoCount(CountValue);
 754       E->setEdgeCount(CountValue);
 755       continue;
 756     }
 757
 758     // Need to add two new edges.
 759     BasicBlock *SrcBB = const_cast<BasicBlock *>(E->SrcBB);
 760     BasicBlock *DestBB = const_cast<BasicBlock *>(E->DestBB);
 761     // Add new edge of SrcBB->InstrBB.
 762     PGOUseEdge &NewEdge = FuncInfo.MST.addEdge(SrcBB, InstrBB, 0);
 763     NewEdge.setEdgeCount(CountValue);
 764     // Add new edge of InstrBB->DestBB.
 765     PGOUseEdge &NewEdge1 = FuncInfo.MST.addEdge(InstrBB, DestBB, 0);
 766     NewEdge1.setEdgeCount(CountValue);
 767     NewEdge1.InMST = true;
 768     getBBInfo(InstrBB).setBBInfoCount(CountValue);
 769   }
 770   ProfileCountSize =  CountFromProfile.size();
 771   CountPosition = I;
 772 }
 773
 774 // Set the count value for the unknown edge. There should be one and only one
 775 // unknown edge in Edges vector.
 776 void PGOUseFunc::setEdgeCount(DirectEdges &Edges, uint64_t Value) {
 777   for (auto &E : Edges) {
 778     if (E->CountValid)
 779       continue;
 780     E->setEdgeCount(Value);
 781
 782     getBBInfo(E->SrcBB).UnknownCountOutEdge--;
 783     getBBInfo(E->DestBB).UnknownCountInEdge--;
 784     return;
 785   }
 786   llvm_unreachable("Cannot find the unknown count edge");
 787 }
 788
 789 // Read the profile from ProfileFileName and assign the value to the
 790 // instrumented BB and the edges. This function also updates ProgramMaxCount.
 791 // Return true if the profile are successfully read, and false on errors.
 792 bool PGOUseFunc::readCounters(IndexedInstrProfReader *PGOReader) {
 793   auto &Ctx = M->getContext();
 794   Expected<InstrProfRecord> Result =
 795       PGOReader->getInstrProfRecord(FuncInfo.FuncName, FuncInfo.FunctionHash);
 796   if (Error E = Result.takeError()) {
 797     handleAllErrors(std::move(E), [&](const InstrProfError &IPE) {
 798       auto Err = IPE.get();
 799       bool SkipWarning = false;
 800       if (Err == instrprof_error::unknown_function) {
 801         NumOfPGOMissing++;
 802         SkipWarning = !PGOWarnMissing;
 803       } else if (Err == instrprof_error::hash_mismatch ||
 804                  Err == instrprof_error::malformed) {
 805         NumOfPGOMismatch++;
 806         SkipWarning = NoPGOWarnMismatch;
 807       }
 808
 809       if (SkipWarning)
 810         return;
 811
 812       std::string Msg = IPE.message() + std::string(" ") + F.getName().str();
 813       Ctx.diagnose(
 814           DiagnosticInfoPGOProfile(M->getName().data(), Msg, DS_Warning));
 815     });
 816     return false;
 817   }
 818   ProfileRecord = std::move(Result.get());
 819   std::vector<uint64_t> &CountFromProfile = ProfileRecord.Counts;
 820
 821   NumOfPGOFunc++;
 822   DEBUG(dbgs() << CountFromProfile.size() << " counts\n");
 823   uint64_t ValueSum = 0;
 824   for (unsigned I = 0, S = CountFromProfile.size(); I < S; I++) {
 825     DEBUG(dbgs() << "  " << I << ": " << CountFromProfile[I] << "\n");
 826     ValueSum += CountFromProfile[I];
 827   }
 828
 829   DEBUG(dbgs() << "SUM =  " << ValueSum << "\n");
 830
 831   getBBInfo(nullptr).UnknownCountOutEdge = 2;
 832   getBBInfo(nullptr).UnknownCountInEdge = 2;
 833
 834   setInstrumentedCounts(CountFromProfile);
 835   ProgramMaxCount = PGOReader->getMaximumFunctionCount();
 836   return true;
 837 }
 838
 839 // Populate the counters from instrumented BBs to all BBs.
 840 // In the end of this operation, all BBs should have a valid count value.
 841 void PGOUseFunc::populateCounters() {
 842   // First set up Count variable for all BBs.
 843   for (auto &E : FuncInfo.MST.AllEdges) {
 844     if (E->Removed)
 845       continue;
 846
 847     const BasicBlock *SrcBB = E->SrcBB;
 848     const BasicBlock *DestBB = E->DestBB;
 849     UseBBInfo &SrcInfo = getBBInfo(SrcBB);
 850     UseBBInfo &DestInfo = getBBInfo(DestBB);
 851     SrcInfo.OutEdges.push_back(E.get());
 852     DestInfo.InEdges.push_back(E.get());
 853     SrcInfo.UnknownCountOutEdge++;
 854     DestInfo.UnknownCountInEdge++;
 855
 856     if (!E->CountValid)
 857       continue;
 858     DestInfo.UnknownCountInEdge--;
 859     SrcInfo.UnknownCountOutEdge--;
 860   }
 861
 862   bool Changes = true;
 863   unsigned NumPasses = 0;
 864   while (Changes) {
 865     NumPasses++;
 866     Changes = false;
 867
 868     // For efficient traversal, it's better to start from the end as most
 869     // of the instrumented edges are at the end.
 870     for (auto &BB : reverse(F)) {
 871       UseBBInfo *Count = findBBInfo(&BB);
 872       if (Count == nullptr)
 873         continue;
 874       if (!Count->CountValid) {
 875         if (Count->UnknownCountOutEdge == 0) {
 876           Count->CountValue = sumEdgeCount(Count->OutEdges);
 877           Count->CountValid = true;
 878           Changes = true;
 879         } else if (Count->UnknownCountInEdge == 0) {
 880           Count->CountValue = sumEdgeCount(Count->InEdges);
 881           Count->CountValid = true;
 882           Changes = true;
 883         }
 884       }
 885       if (Count->CountValid) {
 886         if (Count->UnknownCountOutEdge == 1) {
 887           uint64_t Total = 0;
 888           uint64_t OutSum = sumEdgeCount(Count->OutEdges);
 889           // If the one of the successor block can early terminate (no-return),
 890           // we can end up with situation where out edge sum count is larger as
 891           // the source BB's count is collected by a post-dominated block.
 892           if (Count->CountValue > OutSum)
 893             Total = Count->CountValue - OutSum;
 894           setEdgeCount(Count->OutEdges, Total);
 895           Changes = true;
 896         }
 897         if (Count->UnknownCountInEdge == 1) {
 898           uint64_t Total = 0;
 899           uint64_t InSum = sumEdgeCount(Count->InEdges);
 900           if (Count->CountValue > InSum)
 901             Total = Count->CountValue - InSum;
 902           setEdgeCount(Count->InEdges, Total);
 903           Changes = true;
 904         }
 905       }
 906     }
 907   }
 908
 909   DEBUG(dbgs() << "Populate counts in " << NumPasses << " passes.\n");
 910 #ifndef NDEBUG
 911   // Assert every BB has a valid counter.
 912   for (auto &BB : F) {
 913     auto BI = findBBInfo(&BB);
 914     if (BI == nullptr)
 915       continue;
 916     assert(BI->CountValid && "BB count is not valid");
 917   }
 918 #endif
 919   uint64_t FuncEntryCount = getBBInfo(&*F.begin()).CountValue;
 920   F.setEntryCount(FuncEntryCount);
 921   uint64_t FuncMaxCount = FuncEntryCount;
 922   for (auto &BB : F) {
 923     auto BI = findBBInfo(&BB);
 924     if (BI == nullptr)
 925       continue;
 926     FuncMaxCount = std::max(FuncMaxCount, BI->CountValue);
 927   }
 928   markFunctionAttributes(FuncEntryCount, FuncMaxCount);
 929
 930   // Now annotate select instructions
 931   FuncInfo.SIVisitor.annotateSelects(F, this, &CountPosition);
 932   assert(CountPosition == ProfileCountSize);
 933
 934   DEBUG(FuncInfo.dumpInfo("after reading profile."));
 935 }
 936
 937 static void setProfMetadata(Module *M, Instruction *TI,
 938                             ArrayRef<uint64_t> EdgeCounts, uint64_t MaxCount) {
 939   MDBuilder MDB(M->getContext());
 940   assert(MaxCount > 0 && "Bad max count");
 941   uint64_t Scale = calculateCountScale(MaxCount);
 942   SmallVector<unsigned, 4> Weights;
 943   for (const auto &ECI : EdgeCounts)
 944     Weights.push_back(scaleBranchCount(ECI, Scale));
 945
 946   DEBUG(dbgs() << "Weight is: ";
 947         for (const auto &W : Weights) { dbgs() << W << " "; }
 948         dbgs() << "\n";);
 949   TI->setMetadata(llvm::LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
 950 }
 951
 952 // Assign the scaled count values to the BB with multiple out edges.
 953 void PGOUseFunc::setBranchWeights() {
 954   // Generate MD_prof metadata for every branch instruction.
 955   DEBUG(dbgs() << "\nSetting branch weights.\n");
 956   for (auto &BB : F) {
 957     TerminatorInst *TI = BB.getTerminator();
 958     if (TI->getNumSuccessors() < 2)
 959       continue;
 960     if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
 961       continue;
 962     if (getBBInfo(&BB).CountValue == 0)
 963       continue;
 964
 965     // We have a non-zero Branch BB.
 966     const UseBBInfo &BBCountInfo = getBBInfo(&BB);
 967     unsigned Size = BBCountInfo.OutEdges.size();
 968     SmallVector<uint64_t, 2> EdgeCounts(Size, 0);
 969     uint64_t MaxCount = 0;
 970     for (unsigned s = 0; s < Size; s++) {
 971       const PGOUseEdge *E = BBCountInfo.OutEdges[s];
 972       const BasicBlock *SrcBB = E->SrcBB;
 973       const BasicBlock *DestBB = E->DestBB;
 974       if (DestBB == nullptr)
 975         continue;
 976       unsigned SuccNum = GetSuccessorNumber(SrcBB, DestBB);
 977       uint64_t EdgeCount = E->CountValue;
 978       if (EdgeCount > MaxCount)
 979         MaxCount = EdgeCount;
 980       EdgeCounts[SuccNum] = EdgeCount;
 981     }
 982     setProfMetadata(M, TI, EdgeCounts, MaxCount);
 983   }
 984 }
 985
 986 void SelectInstVisitor::instrumentOneSelectInst(SelectInst &SI) {
 987   Module *M = F.getParent();
 988   IRBuilder<> Builder(&SI);
 989   Type *Int64Ty = Builder.getInt64Ty();
 990   Type *I8PtrTy = Builder.getInt8PtrTy();
 991   auto *Step = Builder.CreateZExt(SI.getCondition(), Int64Ty);
 992   Builder.CreateCall(
 993       Intrinsic::getDeclaration(M, Intrinsic::instrprof_increment_step),
 994       {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
 995        Builder.getInt64(FuncHash),
 996        Builder.getInt32(TotalNumCtrs), Builder.getInt32(*CurCtrIdx), Step});
 997   ++(*CurCtrIdx);
 998 }
 999
1000 void SelectInstVisitor::annotateOneSelectInst(SelectInst &SI) {
1001   std::vector<uint64_t> &CountFromProfile = UseFunc->getProfileRecord().Counts;
1002   assert(*CurCtrIdx < CountFromProfile.size() &&
1003          "Out of bound access of counters");
1004   uint64_t SCounts[2];
1005   SCounts[0] = CountFromProfile[*CurCtrIdx]; // True count
1006   ++(*CurCtrIdx);
1007   uint64_t TotalCount = 0;
1008   auto BI = UseFunc->findBBInfo(SI.getParent());
1009   if (BI != nullptr)
1010     TotalCount = BI->CountValue;
1011   // False Count
1012   SCounts[1] = (TotalCount > SCounts[0] ? TotalCount - SCounts[0] : 0);
1013   uint64_t MaxCount = std::max(SCounts[0], SCounts[1]);
1014   if (MaxCount)
1015     setProfMetadata(F.getParent(), &SI, SCounts, MaxCount);
1016 }
1017
1018 void SelectInstVisitor::visitSelectInst(SelectInst &SI) {
1019   if (!PGOInstrSelect)
1020     return;
1021   // FIXME: do not handle this yet.
1022   if (SI.getCondition()->getType()->isVectorTy())
1023     return;
1024
1025   NSIs++;
1026   switch (Mode) {
1027   case VM_counting:
1028     return;
1029   case VM_instrument:
1030     instrumentOneSelectInst(SI);
1031     return;
1032   case VM_annotate:
1033     annotateOneSelectInst(SI);
1034     return;
1035   }
1036
1037   llvm_unreachable("Unknown visiting mode");
1038 }
1039
1040 // Traverse all the indirect callsites and annotate the instructions.
1041 void PGOUseFunc::annotateIndirectCallSites() {
1042   if (DisableValueProfiling)
1043     return;
1044
1045   // Create the PGOFuncName meta data.
1046   createPGOFuncNameMetadata(F, FuncInfo.FuncName);
1047
1048   unsigned IndirectCallSiteIndex = 0;
1049   auto &IndirectCallSites = FuncInfo.IndirectCallSites;
1050   unsigned NumValueSites =
1051       ProfileRecord.getNumValueSites(IPVK_IndirectCallTarget);
1052   if (NumValueSites != IndirectCallSites.size()) {
1053     std::string Msg =
1054         std::string("Inconsistent number of indirect call sites: ") +
1055         F.getName().str();
1056     auto &Ctx = M->getContext();
1057     Ctx.diagnose(
1058         DiagnosticInfoPGOProfile(M->getName().data(), Msg, DS_Warning));
1059     return;
1060   }
1061
1062   for (auto &I : IndirectCallSites) {
1063     DEBUG(dbgs() << "Read one indirect call instrumentation: Index="
1064                  << IndirectCallSiteIndex << " out of " << NumValueSites
1065                  << "\n");
1066     annotateValueSite(*M, *I, ProfileRecord, IPVK_IndirectCallTarget,
1067                       IndirectCallSiteIndex, MaxNumAnnotations);
1068     IndirectCallSiteIndex++;
1069   }
1070 }
1071 } // end anonymous namespace
1072
1073 // Create a COMDAT variable INSTR_PROF_RAW_VERSION_VAR to make the runtime
1074 // aware this is an ir_level profile so it can set the version flag.
1075 static void createIRLevelProfileFlagVariable(Module &M) {
1076   Type *IntTy64 = Type::getInt64Ty(M.getContext());
1077   uint64_t ProfileVersion = (INSTR_PROF_RAW_VERSION | VARIANT_MASK_IR_PROF);
1078   auto IRLevelVersionVariable = new GlobalVariable(
1079       M, IntTy64, true, GlobalVariable::ExternalLinkage,
1080       Constant::getIntegerValue(IntTy64, APInt(64, ProfileVersion)),
1081       INSTR_PROF_QUOTE(INSTR_PROF_RAW_VERSION_VAR));
1082   IRLevelVersionVariable->setVisibility(GlobalValue::DefaultVisibility);
1083   Triple TT(M.getTargetTriple());
1084   if (!TT.supportsCOMDAT())
1085     IRLevelVersionVariable->setLinkage(GlobalValue::WeakAnyLinkage);
1086   else
1087     IRLevelVersionVariable->setComdat(M.getOrInsertComdat(
1088         StringRef(INSTR_PROF_QUOTE(INSTR_PROF_RAW_VERSION_VAR))));
1089 }
1090
1091 // Collect the set of members for each Comdat in module M and store
1092 // in ComdatMembers.
1093 static void collectComdatMembers(
1094     Module &M,
1095     std::unordered_multimap<Comdat *, GlobalValue *> &ComdatMembers) {
1096   if (!DoComdatRenaming)
1097     return;
1098   for (Function &F : M)
1099     if (Comdat *C = F.getComdat())
1100       ComdatMembers.insert(std::make_pair(C, &F));
1101   for (GlobalVariable &GV : M.globals())
1102     if (Comdat *C = GV.getComdat())
1103       ComdatMembers.insert(std::make_pair(C, &GV));
1104   for (GlobalAlias &GA : M.aliases())
1105     if (Comdat *C = GA.getComdat())
1106       ComdatMembers.insert(std::make_pair(C, &GA));
1107 }
1108
1109 static bool InstrumentAllFunctions(
1110     Module &M, function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
1111     function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
1112   createIRLevelProfileFlagVariable(M);
1113   std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
1114   collectComdatMembers(M, ComdatMembers);
1115
1116   for (auto &F : M) {
1117     if (F.isDeclaration())
1118       continue;
1119     auto *BPI = LookupBPI(F);
1120     auto *BFI = LookupBFI(F);
1121     instrumentOneFunc(F, &M, BPI, BFI, ComdatMembers);
1122   }
1123   return true;
1124 }
1125
1126 bool PGOInstrumentationGenLegacyPass::runOnModule(Module &M) {
1127   if (skipModule(M))
1128     return false;
1129
1130   auto LookupBPI = [this](Function &F) {
1131     return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
1132   };
1133   auto LookupBFI = [this](Function &F) {
1134     return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
1135   };
1136   return InstrumentAllFunctions(M, LookupBPI, LookupBFI);
1137 }
1138
1139 PreservedAnalyses PGOInstrumentationGen::run(Module &M,
1140                                              ModuleAnalysisManager &AM) {
1141
1142   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1143   auto LookupBPI = [&FAM](Function &F) {
1144     return &FAM.getResult<BranchProbabilityAnalysis>(F);
1145   };
1146
1147   auto LookupBFI = [&FAM](Function &F) {
1148     return &FAM.getResult<BlockFrequencyAnalysis>(F);
1149   };
1150
1151   if (!InstrumentAllFunctions(M, LookupBPI, LookupBFI))
1152     return PreservedAnalyses::all();
1153
1154   return PreservedAnalyses::none();
1155 }
1156
1157 static bool annotateAllFunctions(
1158     Module &M, StringRef ProfileFileName,
1159     function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
1160     function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
1161   DEBUG(dbgs() << "Read in profile counters: ");
1162   auto &Ctx = M.getContext();
1163   // Read the counter array from file.
1164   auto ReaderOrErr = IndexedInstrProfReader::create(ProfileFileName);
1165   if (Error E = ReaderOrErr.takeError()) {
1166     handleAllErrors(std::move(E), [&](const ErrorInfoBase &EI) {
1167       Ctx.diagnose(
1168           DiagnosticInfoPGOProfile(ProfileFileName.data(), EI.message()));
1169     });
1170     return false;
1171   }
1172
1173   std::unique_ptr<IndexedInstrProfReader> PGOReader =
1174       std::move(ReaderOrErr.get());
1175   if (!PGOReader) {
1176     Ctx.diagnose(DiagnosticInfoPGOProfile(ProfileFileName.data(),
1177                                           StringRef("Cannot get PGOReader")));
1178     return false;
1179   }
1180   // TODO: might need to change the warning once the clang option is finalized.
1181   if (!PGOReader->isIRLevelProfile()) {
1182     Ctx.diagnose(DiagnosticInfoPGOProfile(
1183         ProfileFileName.data(), "Not an IR level instrumentation profile"));
1184     return false;
1185   }
1186
1187   std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
1188   collectComdatMembers(M, ComdatMembers);
1189   std::vector<Function *> HotFunctions;
1190   std::vector<Function *> ColdFunctions;
1191   for (auto &F : M) {
1192     if (F.isDeclaration())
1193       continue;
1194     auto *BPI = LookupBPI(F);
1195     auto *BFI = LookupBFI(F);
1196     PGOUseFunc Func(F, &M, ComdatMembers, BPI, BFI);
1197     if (!Func.readCounters(PGOReader.get()))
1198       continue;
1199     Func.populateCounters();
1200     Func.setBranchWeights();
1201     Func.annotateIndirectCallSites();
1202     PGOUseFunc::FuncFreqAttr FreqAttr = Func.getFuncFreqAttr();
1203     if (FreqAttr == PGOUseFunc::FFA_Cold)
1204       ColdFunctions.push_back(&F);
1205     else if (FreqAttr == PGOUseFunc::FFA_Hot)
1206       HotFunctions.push_back(&F);
1207   }
1208   M.setProfileSummary(PGOReader->getSummary().getMD(M.getContext()));
1209   // Set function hotness attribute from the profile.
1210   // We have to apply these attributes at the end because their presence
1211   // can affect the BranchProbabilityInfo of any callers, resulting in an
1212   // inconsistent MST between prof-gen and prof-use.
1213   for (auto &F : HotFunctions) {
1214     F->addFnAttr(llvm::Attribute::InlineHint);
1215     DEBUG(dbgs() << "Set inline attribute to function: " << F->getName()
1216                  << "\n");
1217   }
1218   for (auto &F : ColdFunctions) {
1219     F->addFnAttr(llvm::Attribute::Cold);
1220     DEBUG(dbgs() << "Set cold attribute to function: " << F->getName() << "\n");
1221   }
1222   return true;
1223 }
1224
1225 PGOInstrumentationUse::PGOInstrumentationUse(std::string Filename)
1226     : ProfileFileName(std::move(Filename)) {
1227   if (!PGOTestProfileFile.empty())
1228     ProfileFileName = PGOTestProfileFile;
1229 }
1230
1231 PreservedAnalyses PGOInstrumentationUse::run(Module &M,
1232                                              ModuleAnalysisManager &AM) {
1233
1234   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
1235   auto LookupBPI = [&FAM](Function &F) {
1236     return &FAM.getResult<BranchProbabilityAnalysis>(F);
1237   };
1238
1239   auto LookupBFI = [&FAM](Function &F) {
1240     return &FAM.getResult<BlockFrequencyAnalysis>(F);
1241   };
1242
1243   if (!annotateAllFunctions(M, ProfileFileName, LookupBPI, LookupBFI))
1244     return PreservedAnalyses::all();
1245
1246   return PreservedAnalyses::none();
1247 }
1248
1249 bool PGOInstrumentationUseLegacyPass::runOnModule(Module &M) {
1250   if (skipModule(M))
1251     return false;
1252
1253   auto LookupBPI = [this](Function &F) {
1254     return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
1255   };
1256   auto LookupBFI = [this](Function &F) {
1257     return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
1258   };
1259
1260   return annotateAllFunctions(M, ProfileFileName, LookupBPI, LookupBFI);
1261 }