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