contrib/llvm/tools/clang/lib/CodeGen/CodeGenPGO.cpp

   1 //===--- CodeGenPGO.cpp - PGO Instrumentation for LLVM CodeGen --*- C++ -*-===//
   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 // Instrumentation-based profile-guided optimization
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "CodeGenPGO.h"
  15 #include "CodeGenFunction.h"
  16 #include "CoverageMappingGen.h"
  17 #include "clang/AST/RecursiveASTVisitor.h"
  18 #include "clang/AST/StmtVisitor.h"
  19 #include "llvm/IR/Intrinsics.h"
  20 #include "llvm/IR/MDBuilder.h"
  21 #include "llvm/Support/Endian.h"
  22 #include "llvm/Support/FileSystem.h"
  23 #include "llvm/Support/MD5.h"
  24
  25 static llvm::cl::opt<bool> EnableValueProfiling(
  26   "enable-value-profiling", llvm::cl::ZeroOrMore,
  27   llvm::cl::desc("Enable value profiling"), llvm::cl::init(false));
  28
  29 using namespace clang;
  30 using namespace CodeGen;
  31
  32 void CodeGenPGO::setFuncName(StringRef Name,
  33                              llvm::GlobalValue::LinkageTypes Linkage) {
  34   llvm::IndexedInstrProfReader *PGOReader = CGM.getPGOReader();
  35   FuncName = llvm::getPGOFuncName(
  36       Name, Linkage, CGM.getCodeGenOpts().MainFileName,
  37       PGOReader ? PGOReader->getVersion() : llvm::IndexedInstrProf::Version);
  38
  39   // If we're generating a profile, create a variable for the name.
  40   if (CGM.getCodeGenOpts().hasProfileClangInstr())
  41     FuncNameVar = llvm::createPGOFuncNameVar(CGM.getModule(), Linkage, FuncName);
  42 }
  43
  44 void CodeGenPGO::setFuncName(llvm::Function *Fn) {
  45   setFuncName(Fn->getName(), Fn->getLinkage());
  46   // Create PGOFuncName meta data.
  47   llvm::createPGOFuncNameMetadata(*Fn, FuncName);
  48 }
  49
  50 namespace {
  51 /// \brief Stable hasher for PGO region counters.
  52 ///
  53 /// PGOHash produces a stable hash of a given function's control flow.
  54 ///
  55 /// Changing the output of this hash will invalidate all previously generated
  56 /// profiles -- i.e., don't do it.
  57 ///
  58 /// \note  When this hash does eventually change (years?), we still need to
  59 /// support old hashes.  We'll need to pull in the version number from the
  60 /// profile data format and use the matching hash function.
  61 class PGOHash {
  62   uint64_t Working;
  63   unsigned Count;
  64   llvm::MD5 MD5;
  65
  66   static const int NumBitsPerType = 6;
  67   static const unsigned NumTypesPerWord = sizeof(uint64_t) * 8 / NumBitsPerType;
  68   static const unsigned TooBig = 1u << NumBitsPerType;
  69
  70 public:
  71   /// \brief Hash values for AST nodes.
  72   ///
  73   /// Distinct values for AST nodes that have region counters attached.
  74   ///
  75   /// These values must be stable.  All new members must be added at the end,
  76   /// and no members should be removed.  Changing the enumeration value for an
  77   /// AST node will affect the hash of every function that contains that node.
  78   enum HashType : unsigned char {
  79     None = 0,
  80     LabelStmt = 1,
  81     WhileStmt,
  82     DoStmt,
  83     ForStmt,
  84     CXXForRangeStmt,
  85     ObjCForCollectionStmt,
  86     SwitchStmt,
  87     CaseStmt,
  88     DefaultStmt,
  89     IfStmt,
  90     CXXTryStmt,
  91     CXXCatchStmt,
  92     ConditionalOperator,
  93     BinaryOperatorLAnd,
  94     BinaryOperatorLOr,
  95     BinaryConditionalOperator,
  96
  97     // Keep this last.  It's for the static assert that follows.
  98     LastHashType
  99   };
 100   static_assert(LastHashType <= TooBig, "Too many types in HashType");
 101
 102   // TODO: When this format changes, take in a version number here, and use the
 103   // old hash calculation for file formats that used the old hash.
 104   PGOHash() : Working(0), Count(0) {}
 105   void combine(HashType Type);
 106   uint64_t finalize();
 107 };
 108 const int PGOHash::NumBitsPerType;
 109 const unsigned PGOHash::NumTypesPerWord;
 110 const unsigned PGOHash::TooBig;
 111
 112 /// A RecursiveASTVisitor that fills a map of statements to PGO counters.
 113 struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> {
 114   /// The next counter value to assign.
 115   unsigned NextCounter;
 116   /// The function hash.
 117   PGOHash Hash;
 118   /// The map of statements to counters.
 119   llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
 120
 121   MapRegionCounters(llvm::DenseMap<const Stmt *, unsigned> &CounterMap)
 122       : NextCounter(0), CounterMap(CounterMap) {}
 123
 124   // Blocks and lambdas are handled as separate functions, so we need not
 125   // traverse them in the parent context.
 126   bool TraverseBlockExpr(BlockExpr *BE) { return true; }
 127   bool TraverseLambdaBody(LambdaExpr *LE) { return true; }
 128   bool TraverseCapturedStmt(CapturedStmt *CS) { return true; }
 129
 130   bool VisitDecl(const Decl *D) {
 131     switch (D->getKind()) {
 132     default:
 133       break;
 134     case Decl::Function:
 135     case Decl::CXXMethod:
 136     case Decl::CXXConstructor:
 137     case Decl::CXXDestructor:
 138     case Decl::CXXConversion:
 139     case Decl::ObjCMethod:
 140     case Decl::Block:
 141     case Decl::Captured:
 142       CounterMap[D->getBody()] = NextCounter++;
 143       break;
 144     }
 145     return true;
 146   }
 147
 148   bool VisitStmt(const Stmt *S) {
 149     auto Type = getHashType(S);
 150     if (Type == PGOHash::None)
 151       return true;
 152
 153     CounterMap[S] = NextCounter++;
 154     Hash.combine(Type);
 155     return true;
 156   }
 157   PGOHash::HashType getHashType(const Stmt *S) {
 158     switch (S->getStmtClass()) {
 159     default:
 160       break;
 161     case Stmt::LabelStmtClass:
 162       return PGOHash::LabelStmt;
 163     case Stmt::WhileStmtClass:
 164       return PGOHash::WhileStmt;
 165     case Stmt::DoStmtClass:
 166       return PGOHash::DoStmt;
 167     case Stmt::ForStmtClass:
 168       return PGOHash::ForStmt;
 169     case Stmt::CXXForRangeStmtClass:
 170       return PGOHash::CXXForRangeStmt;
 171     case Stmt::ObjCForCollectionStmtClass:
 172       return PGOHash::ObjCForCollectionStmt;
 173     case Stmt::SwitchStmtClass:
 174       return PGOHash::SwitchStmt;
 175     case Stmt::CaseStmtClass:
 176       return PGOHash::CaseStmt;
 177     case Stmt::DefaultStmtClass:
 178       return PGOHash::DefaultStmt;
 179     case Stmt::IfStmtClass:
 180       return PGOHash::IfStmt;
 181     case Stmt::CXXTryStmtClass:
 182       return PGOHash::CXXTryStmt;
 183     case Stmt::CXXCatchStmtClass:
 184       return PGOHash::CXXCatchStmt;
 185     case Stmt::ConditionalOperatorClass:
 186       return PGOHash::ConditionalOperator;
 187     case Stmt::BinaryConditionalOperatorClass:
 188       return PGOHash::BinaryConditionalOperator;
 189     case Stmt::BinaryOperatorClass: {
 190       const BinaryOperator *BO = cast<BinaryOperator>(S);
 191       if (BO->getOpcode() == BO_LAnd)
 192         return PGOHash::BinaryOperatorLAnd;
 193       if (BO->getOpcode() == BO_LOr)
 194         return PGOHash::BinaryOperatorLOr;
 195       break;
 196     }
 197     }
 198     return PGOHash::None;
 199   }
 200 };
 201
 202 /// A StmtVisitor that propagates the raw counts through the AST and
 203 /// records the count at statements where the value may change.
 204 struct ComputeRegionCounts : public ConstStmtVisitor<ComputeRegionCounts> {
 205   /// PGO state.
 206   CodeGenPGO &PGO;
 207
 208   /// A flag that is set when the current count should be recorded on the
 209   /// next statement, such as at the exit of a loop.
 210   bool RecordNextStmtCount;
 211
 212   /// The count at the current location in the traversal.
 213   uint64_t CurrentCount;
 214
 215   /// The map of statements to count values.
 216   llvm::DenseMap<const Stmt *, uint64_t> &CountMap;
 217
 218   /// BreakContinueStack - Keep counts of breaks and continues inside loops.
 219   struct BreakContinue {
 220     uint64_t BreakCount;
 221     uint64_t ContinueCount;
 222     BreakContinue() : BreakCount(0), ContinueCount(0) {}
 223   };
 224   SmallVector<BreakContinue, 8> BreakContinueStack;
 225
 226   ComputeRegionCounts(llvm::DenseMap<const Stmt *, uint64_t> &CountMap,
 227                       CodeGenPGO &PGO)
 228       : PGO(PGO), RecordNextStmtCount(false), CountMap(CountMap) {}
 229
 230   void RecordStmtCount(const Stmt *S) {
 231     if (RecordNextStmtCount) {
 232       CountMap[S] = CurrentCount;
 233       RecordNextStmtCount = false;
 234     }
 235   }
 236
 237   /// Set and return the current count.
 238   uint64_t setCount(uint64_t Count) {
 239     CurrentCount = Count;
 240     return Count;
 241   }
 242
 243   void VisitStmt(const Stmt *S) {
 244     RecordStmtCount(S);
 245     for (const Stmt *Child : S->children())
 246       if (Child)
 247         this->Visit(Child);
 248   }
 249
 250   void VisitFunctionDecl(const FunctionDecl *D) {
 251     // Counter tracks entry to the function body.
 252     uint64_t BodyCount = setCount(PGO.getRegionCount(D->getBody()));
 253     CountMap[D->getBody()] = BodyCount;
 254     Visit(D->getBody());
 255   }
 256
 257   // Skip lambda expressions. We visit these as FunctionDecls when we're
 258   // generating them and aren't interested in the body when generating a
 259   // parent context.
 260   void VisitLambdaExpr(const LambdaExpr *LE) {}
 261
 262   void VisitCapturedDecl(const CapturedDecl *D) {
 263     // Counter tracks entry to the capture body.
 264     uint64_t BodyCount = setCount(PGO.getRegionCount(D->getBody()));
 265     CountMap[D->getBody()] = BodyCount;
 266     Visit(D->getBody());
 267   }
 268
 269   void VisitObjCMethodDecl(const ObjCMethodDecl *D) {
 270     // Counter tracks entry to the method body.
 271     uint64_t BodyCount = setCount(PGO.getRegionCount(D->getBody()));
 272     CountMap[D->getBody()] = BodyCount;
 273     Visit(D->getBody());
 274   }
 275
 276   void VisitBlockDecl(const BlockDecl *D) {
 277     // Counter tracks entry to the block body.
 278     uint64_t BodyCount = setCount(PGO.getRegionCount(D->getBody()));
 279     CountMap[D->getBody()] = BodyCount;
 280     Visit(D->getBody());
 281   }
 282
 283   void VisitReturnStmt(const ReturnStmt *S) {
 284     RecordStmtCount(S);
 285     if (S->getRetValue())
 286       Visit(S->getRetValue());
 287     CurrentCount = 0;
 288     RecordNextStmtCount = true;
 289   }
 290
 291   void VisitCXXThrowExpr(const CXXThrowExpr *E) {
 292     RecordStmtCount(E);
 293     if (E->getSubExpr())
 294       Visit(E->getSubExpr());
 295     CurrentCount = 0;
 296     RecordNextStmtCount = true;
 297   }
 298
 299   void VisitGotoStmt(const GotoStmt *S) {
 300     RecordStmtCount(S);
 301     CurrentCount = 0;
 302     RecordNextStmtCount = true;
 303   }
 304
 305   void VisitLabelStmt(const LabelStmt *S) {
 306     RecordNextStmtCount = false;
 307     // Counter tracks the block following the label.
 308     uint64_t BlockCount = setCount(PGO.getRegionCount(S));
 309     CountMap[S] = BlockCount;
 310     Visit(S->getSubStmt());
 311   }
 312
 313   void VisitBreakStmt(const BreakStmt *S) {
 314     RecordStmtCount(S);
 315     assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
 316     BreakContinueStack.back().BreakCount += CurrentCount;
 317     CurrentCount = 0;
 318     RecordNextStmtCount = true;
 319   }
 320
 321   void VisitContinueStmt(const ContinueStmt *S) {
 322     RecordStmtCount(S);
 323     assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
 324     BreakContinueStack.back().ContinueCount += CurrentCount;
 325     CurrentCount = 0;
 326     RecordNextStmtCount = true;
 327   }
 328
 329   void VisitWhileStmt(const WhileStmt *S) {
 330     RecordStmtCount(S);
 331     uint64_t ParentCount = CurrentCount;
 332
 333     BreakContinueStack.push_back(BreakContinue());
 334     // Visit the body region first so the break/continue adjustments can be
 335     // included when visiting the condition.
 336     uint64_t BodyCount = setCount(PGO.getRegionCount(S));
 337     CountMap[S->getBody()] = CurrentCount;
 338     Visit(S->getBody());
 339     uint64_t BackedgeCount = CurrentCount;
 340
 341     // ...then go back and propagate counts through the condition. The count
 342     // at the start of the condition is the sum of the incoming edges,
 343     // the backedge from the end of the loop body, and the edges from
 344     // continue statements.
 345     BreakContinue BC = BreakContinueStack.pop_back_val();
 346     uint64_t CondCount =
 347         setCount(ParentCount + BackedgeCount + BC.ContinueCount);
 348     CountMap[S->getCond()] = CondCount;
 349     Visit(S->getCond());
 350     setCount(BC.BreakCount + CondCount - BodyCount);
 351     RecordNextStmtCount = true;
 352   }
 353
 354   void VisitDoStmt(const DoStmt *S) {
 355     RecordStmtCount(S);
 356     uint64_t LoopCount = PGO.getRegionCount(S);
 357
 358     BreakContinueStack.push_back(BreakContinue());
 359     // The count doesn't include the fallthrough from the parent scope. Add it.
 360     uint64_t BodyCount = setCount(LoopCount + CurrentCount);
 361     CountMap[S->getBody()] = BodyCount;
 362     Visit(S->getBody());
 363     uint64_t BackedgeCount = CurrentCount;
 364
 365     BreakContinue BC = BreakContinueStack.pop_back_val();
 366     // The count at the start of the condition is equal to the count at the
 367     // end of the body, plus any continues.
 368     uint64_t CondCount = setCount(BackedgeCount + BC.ContinueCount);
 369     CountMap[S->getCond()] = CondCount;
 370     Visit(S->getCond());
 371     setCount(BC.BreakCount + CondCount - LoopCount);
 372     RecordNextStmtCount = true;
 373   }
 374
 375   void VisitForStmt(const ForStmt *S) {
 376     RecordStmtCount(S);
 377     if (S->getInit())
 378       Visit(S->getInit());
 379
 380     uint64_t ParentCount = CurrentCount;
 381
 382     BreakContinueStack.push_back(BreakContinue());
 383     // Visit the body region first. (This is basically the same as a while
 384     // loop; see further comments in VisitWhileStmt.)
 385     uint64_t BodyCount = setCount(PGO.getRegionCount(S));
 386     CountMap[S->getBody()] = BodyCount;
 387     Visit(S->getBody());
 388     uint64_t BackedgeCount = CurrentCount;
 389     BreakContinue BC = BreakContinueStack.pop_back_val();
 390
 391     // The increment is essentially part of the body but it needs to include
 392     // the count for all the continue statements.
 393     if (S->getInc()) {
 394       uint64_t IncCount = setCount(BackedgeCount + BC.ContinueCount);
 395       CountMap[S->getInc()] = IncCount;
 396       Visit(S->getInc());
 397     }
 398
 399     // ...then go back and propagate counts through the condition.
 400     uint64_t CondCount =
 401         setCount(ParentCount + BackedgeCount + BC.ContinueCount);
 402     if (S->getCond()) {
 403       CountMap[S->getCond()] = CondCount;
 404       Visit(S->getCond());
 405     }
 406     setCount(BC.BreakCount + CondCount - BodyCount);
 407     RecordNextStmtCount = true;
 408   }
 409
 410   void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
 411     RecordStmtCount(S);
 412     Visit(S->getLoopVarStmt());
 413     Visit(S->getRangeStmt());
 414     Visit(S->getBeginStmt());
 415     Visit(S->getEndStmt());
 416
 417     uint64_t ParentCount = CurrentCount;
 418     BreakContinueStack.push_back(BreakContinue());
 419     // Visit the body region first. (This is basically the same as a while
 420     // loop; see further comments in VisitWhileStmt.)
 421     uint64_t BodyCount = setCount(PGO.getRegionCount(S));
 422     CountMap[S->getBody()] = BodyCount;
 423     Visit(S->getBody());
 424     uint64_t BackedgeCount = CurrentCount;
 425     BreakContinue BC = BreakContinueStack.pop_back_val();
 426
 427     // The increment is essentially part of the body but it needs to include
 428     // the count for all the continue statements.
 429     uint64_t IncCount = setCount(BackedgeCount + BC.ContinueCount);
 430     CountMap[S->getInc()] = IncCount;
 431     Visit(S->getInc());
 432
 433     // ...then go back and propagate counts through the condition.
 434     uint64_t CondCount =
 435         setCount(ParentCount + BackedgeCount + BC.ContinueCount);
 436     CountMap[S->getCond()] = CondCount;
 437     Visit(S->getCond());
 438     setCount(BC.BreakCount + CondCount - BodyCount);
 439     RecordNextStmtCount = true;
 440   }
 441
 442   void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
 443     RecordStmtCount(S);
 444     Visit(S->getElement());
 445     uint64_t ParentCount = CurrentCount;
 446     BreakContinueStack.push_back(BreakContinue());
 447     // Counter tracks the body of the loop.
 448     uint64_t BodyCount = setCount(PGO.getRegionCount(S));
 449     CountMap[S->getBody()] = BodyCount;
 450     Visit(S->getBody());
 451     uint64_t BackedgeCount = CurrentCount;
 452     BreakContinue BC = BreakContinueStack.pop_back_val();
 453
 454     setCount(BC.BreakCount + ParentCount + BackedgeCount + BC.ContinueCount -
 455              BodyCount);
 456     RecordNextStmtCount = true;
 457   }
 458
 459   void VisitSwitchStmt(const SwitchStmt *S) {
 460     RecordStmtCount(S);
 461     if (S->getInit())
 462       Visit(S->getInit());
 463     Visit(S->getCond());
 464     CurrentCount = 0;
 465     BreakContinueStack.push_back(BreakContinue());
 466     Visit(S->getBody());
 467     // If the switch is inside a loop, add the continue counts.
 468     BreakContinue BC = BreakContinueStack.pop_back_val();
 469     if (!BreakContinueStack.empty())
 470       BreakContinueStack.back().ContinueCount += BC.ContinueCount;
 471     // Counter tracks the exit block of the switch.
 472     setCount(PGO.getRegionCount(S));
 473     RecordNextStmtCount = true;
 474   }
 475
 476   void VisitSwitchCase(const SwitchCase *S) {
 477     RecordNextStmtCount = false;
 478     // Counter for this particular case. This counts only jumps from the
 479     // switch header and does not include fallthrough from the case before
 480     // this one.
 481     uint64_t CaseCount = PGO.getRegionCount(S);
 482     setCount(CurrentCount + CaseCount);
 483     // We need the count without fallthrough in the mapping, so it's more useful
 484     // for branch probabilities.
 485     CountMap[S] = CaseCount;
 486     RecordNextStmtCount = true;
 487     Visit(S->getSubStmt());
 488   }
 489
 490   void VisitIfStmt(const IfStmt *S) {
 491     RecordStmtCount(S);
 492     uint64_t ParentCount = CurrentCount;
 493     if (S->getInit())
 494       Visit(S->getInit());
 495     Visit(S->getCond());
 496
 497     // Counter tracks the "then" part of an if statement. The count for
 498     // the "else" part, if it exists, will be calculated from this counter.
 499     uint64_t ThenCount = setCount(PGO.getRegionCount(S));
 500     CountMap[S->getThen()] = ThenCount;
 501     Visit(S->getThen());
 502     uint64_t OutCount = CurrentCount;
 503
 504     uint64_t ElseCount = ParentCount - ThenCount;
 505     if (S->getElse()) {
 506       setCount(ElseCount);
 507       CountMap[S->getElse()] = ElseCount;
 508       Visit(S->getElse());
 509       OutCount += CurrentCount;
 510     } else
 511       OutCount += ElseCount;
 512     setCount(OutCount);
 513     RecordNextStmtCount = true;
 514   }
 515
 516   void VisitCXXTryStmt(const CXXTryStmt *S) {
 517     RecordStmtCount(S);
 518     Visit(S->getTryBlock());
 519     for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I)
 520       Visit(S->getHandler(I));
 521     // Counter tracks the continuation block of the try statement.
 522     setCount(PGO.getRegionCount(S));
 523     RecordNextStmtCount = true;
 524   }
 525
 526   void VisitCXXCatchStmt(const CXXCatchStmt *S) {
 527     RecordNextStmtCount = false;
 528     // Counter tracks the catch statement's handler block.
 529     uint64_t CatchCount = setCount(PGO.getRegionCount(S));
 530     CountMap[S] = CatchCount;
 531     Visit(S->getHandlerBlock());
 532   }
 533
 534   void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
 535     RecordStmtCount(E);
 536     uint64_t ParentCount = CurrentCount;
 537     Visit(E->getCond());
 538
 539     // Counter tracks the "true" part of a conditional operator. The
 540     // count in the "false" part will be calculated from this counter.
 541     uint64_t TrueCount = setCount(PGO.getRegionCount(E));
 542     CountMap[E->getTrueExpr()] = TrueCount;
 543     Visit(E->getTrueExpr());
 544     uint64_t OutCount = CurrentCount;
 545
 546     uint64_t FalseCount = setCount(ParentCount - TrueCount);
 547     CountMap[E->getFalseExpr()] = FalseCount;
 548     Visit(E->getFalseExpr());
 549     OutCount += CurrentCount;
 550
 551     setCount(OutCount);
 552     RecordNextStmtCount = true;
 553   }
 554
 555   void VisitBinLAnd(const BinaryOperator *E) {
 556     RecordStmtCount(E);
 557     uint64_t ParentCount = CurrentCount;
 558     Visit(E->getLHS());
 559     // Counter tracks the right hand side of a logical and operator.
 560     uint64_t RHSCount = setCount(PGO.getRegionCount(E));
 561     CountMap[E->getRHS()] = RHSCount;
 562     Visit(E->getRHS());
 563     setCount(ParentCount + RHSCount - CurrentCount);
 564     RecordNextStmtCount = true;
 565   }
 566
 567   void VisitBinLOr(const BinaryOperator *E) {
 568     RecordStmtCount(E);
 569     uint64_t ParentCount = CurrentCount;
 570     Visit(E->getLHS());
 571     // Counter tracks the right hand side of a logical or operator.
 572     uint64_t RHSCount = setCount(PGO.getRegionCount(E));
 573     CountMap[E->getRHS()] = RHSCount;
 574     Visit(E->getRHS());
 575     setCount(ParentCount + RHSCount - CurrentCount);
 576     RecordNextStmtCount = true;
 577   }
 578 };
 579 } // end anonymous namespace
 580
 581 void PGOHash::combine(HashType Type) {
 582   // Check that we never combine 0 and only have six bits.
 583   assert(Type && "Hash is invalid: unexpected type 0");
 584   assert(unsigned(Type) < TooBig && "Hash is invalid: too many types");
 585
 586   // Pass through MD5 if enough work has built up.
 587   if (Count && Count % NumTypesPerWord == 0) {
 588     using namespace llvm::support;
 589     uint64_t Swapped = endian::byte_swap<uint64_t, little>(Working);
 590     MD5.update(llvm::makeArrayRef((uint8_t *)&Swapped, sizeof(Swapped)));
 591     Working = 0;
 592   }
 593
 594   // Accumulate the current type.
 595   ++Count;
 596   Working = Working << NumBitsPerType | Type;
 597 }
 598
 599 uint64_t PGOHash::finalize() {
 600   // Use Working as the hash directly if we never used MD5.
 601   if (Count <= NumTypesPerWord)
 602     // No need to byte swap here, since none of the math was endian-dependent.
 603     // This number will be byte-swapped as required on endianness transitions,
 604     // so we will see the same value on the other side.
 605     return Working;
 606
 607   // Check for remaining work in Working.
 608   if (Working)
 609     MD5.update(Working);
 610
 611   // Finalize the MD5 and return the hash.
 612   llvm::MD5::MD5Result Result;
 613   MD5.final(Result);
 614   using namespace llvm::support;
 615   return endian::read<uint64_t, little, unaligned>(Result);
 616 }
 617
 618 void CodeGenPGO::assignRegionCounters(GlobalDecl GD, llvm::Function *Fn) {
 619   const Decl *D = GD.getDecl();
 620   bool InstrumentRegions = CGM.getCodeGenOpts().hasProfileClangInstr();
 621   llvm::IndexedInstrProfReader *PGOReader = CGM.getPGOReader();
 622   if (!InstrumentRegions && !PGOReader)
 623     return;
 624   if (D->isImplicit())
 625     return;
 626   // Constructors and destructors may be represented by several functions in IR.
 627   // If so, instrument only base variant, others are implemented by delegation
 628   // to the base one, it would be counted twice otherwise.
 629   if (CGM.getTarget().getCXXABI().hasConstructorVariants() &&
 630       ((isa<CXXConstructorDecl>(GD.getDecl()) &&
 631         GD.getCtorType() != Ctor_Base) ||
 632        (isa<CXXDestructorDecl>(GD.getDecl()) &&
 633         GD.getDtorType() != Dtor_Base))) {
 634       return;
 635   }
 636   CGM.ClearUnusedCoverageMapping(D);
 637   setFuncName(Fn);
 638
 639   mapRegionCounters(D);
 640   if (CGM.getCodeGenOpts().CoverageMapping)
 641     emitCounterRegionMapping(D);
 642   if (PGOReader) {
 643     SourceManager &SM = CGM.getContext().getSourceManager();
 644     loadRegionCounts(PGOReader, SM.isInMainFile(D->getLocation()));
 645     computeRegionCounts(D);
 646     applyFunctionAttributes(PGOReader, Fn);
 647   }
 648 }
 649
 650 void CodeGenPGO::mapRegionCounters(const Decl *D) {
 651   RegionCounterMap.reset(new llvm::DenseMap<const Stmt *, unsigned>);
 652   MapRegionCounters Walker(*RegionCounterMap);
 653   if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D))
 654     Walker.TraverseDecl(const_cast<FunctionDecl *>(FD));
 655   else if (const ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(D))
 656     Walker.TraverseDecl(const_cast<ObjCMethodDecl *>(MD));
 657   else if (const BlockDecl *BD = dyn_cast_or_null<BlockDecl>(D))
 658     Walker.TraverseDecl(const_cast<BlockDecl *>(BD));
 659   else if (const CapturedDecl *CD = dyn_cast_or_null<CapturedDecl>(D))
 660     Walker.TraverseDecl(const_cast<CapturedDecl *>(CD));
 661   assert(Walker.NextCounter > 0 && "no entry counter mapped for decl");
 662   NumRegionCounters = Walker.NextCounter;
 663   FunctionHash = Walker.Hash.finalize();
 664 }
 665
 666 bool CodeGenPGO::skipRegionMappingForDecl(const Decl *D) {
 667   if (SkipCoverageMapping)
 668     return true;
 669
 670   // Don't map the functions in system headers.
 671   const auto &SM = CGM.getContext().getSourceManager();
 672   auto Loc = D->getBody()->getLocStart();
 673   return SM.isInSystemHeader(Loc);
 674 }
 675
 676 void CodeGenPGO::emitCounterRegionMapping(const Decl *D) {
 677   if (skipRegionMappingForDecl(D))
 678     return;
 679
 680   std::string CoverageMapping;
 681   llvm::raw_string_ostream OS(CoverageMapping);
 682   CoverageMappingGen MappingGen(*CGM.getCoverageMapping(),
 683                                 CGM.getContext().getSourceManager(),
 684                                 CGM.getLangOpts(), RegionCounterMap.get());
 685   MappingGen.emitCounterMapping(D, OS);
 686   OS.flush();
 687
 688   if (CoverageMapping.empty())
 689     return;
 690
 691   CGM.getCoverageMapping()->addFunctionMappingRecord(
 692       FuncNameVar, FuncName, FunctionHash, CoverageMapping);
 693 }
 694
 695 void
 696 CodeGenPGO::emitEmptyCounterMapping(const Decl *D, StringRef Name,
 697                                     llvm::GlobalValue::LinkageTypes Linkage) {
 698   if (skipRegionMappingForDecl(D))
 699     return;
 700
 701   std::string CoverageMapping;
 702   llvm::raw_string_ostream OS(CoverageMapping);
 703   CoverageMappingGen MappingGen(*CGM.getCoverageMapping(),
 704                                 CGM.getContext().getSourceManager(),
 705                                 CGM.getLangOpts());
 706   MappingGen.emitEmptyMapping(D, OS);
 707   OS.flush();
 708
 709   if (CoverageMapping.empty())
 710     return;
 711
 712   setFuncName(Name, Linkage);
 713   CGM.getCoverageMapping()->addFunctionMappingRecord(
 714       FuncNameVar, FuncName, FunctionHash, CoverageMapping, false);
 715 }
 716
 717 void CodeGenPGO::computeRegionCounts(const Decl *D) {
 718   StmtCountMap.reset(new llvm::DenseMap<const Stmt *, uint64_t>);
 719   ComputeRegionCounts Walker(*StmtCountMap, *this);
 720   if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D))
 721     Walker.VisitFunctionDecl(FD);
 722   else if (const ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(D))
 723     Walker.VisitObjCMethodDecl(MD);
 724   else if (const BlockDecl *BD = dyn_cast_or_null<BlockDecl>(D))
 725     Walker.VisitBlockDecl(BD);
 726   else if (const CapturedDecl *CD = dyn_cast_or_null<CapturedDecl>(D))
 727     Walker.VisitCapturedDecl(const_cast<CapturedDecl *>(CD));
 728 }
 729
 730 void
 731 CodeGenPGO::applyFunctionAttributes(llvm::IndexedInstrProfReader *PGOReader,
 732                                     llvm::Function *Fn) {
 733   if (!haveRegionCounts())
 734     return;
 735
 736   uint64_t FunctionCount = getRegionCount(nullptr);
 737   Fn->setEntryCount(FunctionCount);
 738 }
 739
 740 void CodeGenPGO::emitCounterIncrement(CGBuilderTy &Builder, const Stmt *S) {
 741   if (!CGM.getCodeGenOpts().hasProfileClangInstr() || !RegionCounterMap)
 742     return;
 743   if (!Builder.GetInsertBlock())
 744     return;
 745
 746   unsigned Counter = (*RegionCounterMap)[S];
 747   auto *I8PtrTy = llvm::Type::getInt8PtrTy(CGM.getLLVMContext());
 748   Builder.CreateCall(CGM.getIntrinsic(llvm::Intrinsic::instrprof_increment),
 749                      {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy),
 750                       Builder.getInt64(FunctionHash),
 751                       Builder.getInt32(NumRegionCounters),
 752                       Builder.getInt32(Counter)});
 753 }
 754
 755 // This method either inserts a call to the profile run-time during
 756 // instrumentation or puts profile data into metadata for PGO use.
 757 void CodeGenPGO::valueProfile(CGBuilderTy &Builder, uint32_t ValueKind,
 758     llvm::Instruction *ValueSite, llvm::Value *ValuePtr) {
 759
 760   if (!EnableValueProfiling)
 761     return;
 762
 763   if (!ValuePtr || !ValueSite || !Builder.GetInsertBlock())
 764     return;
 765
 766   if (isa<llvm::Constant>(ValuePtr))
 767     return;
 768
 769   bool InstrumentValueSites = CGM.getCodeGenOpts().hasProfileClangInstr();
 770   if (InstrumentValueSites && RegionCounterMap) {
 771     auto BuilderInsertPoint = Builder.saveIP();
 772     Builder.SetInsertPoint(ValueSite);
 773     llvm::Value *Args[5] = {
 774         llvm::ConstantExpr::getBitCast(FuncNameVar, Builder.getInt8PtrTy()),
 775         Builder.getInt64(FunctionHash),
 776         Builder.CreatePtrToInt(ValuePtr, Builder.getInt64Ty()),
 777         Builder.getInt32(ValueKind),
 778         Builder.getInt32(NumValueSites[ValueKind]++)
 779     };
 780     Builder.CreateCall(
 781         CGM.getIntrinsic(llvm::Intrinsic::instrprof_value_profile), Args);
 782     Builder.restoreIP(BuilderInsertPoint);
 783     return;
 784   }
 785
 786   llvm::IndexedInstrProfReader *PGOReader = CGM.getPGOReader();
 787   if (PGOReader && haveRegionCounts()) {
 788     // We record the top most called three functions at each call site.
 789     // Profile metadata contains "VP" string identifying this metadata
 790     // as value profiling data, then a uint32_t value for the value profiling
 791     // kind, a uint64_t value for the total number of times the call is
 792     // executed, followed by the function hash and execution count (uint64_t)
 793     // pairs for each function.
 794     if (NumValueSites[ValueKind] >= ProfRecord->getNumValueSites(ValueKind))
 795       return;
 796
 797     llvm::annotateValueSite(CGM.getModule(), *ValueSite, *ProfRecord,
 798                             (llvm::InstrProfValueKind)ValueKind,
 799                             NumValueSites[ValueKind]);
 800
 801     NumValueSites[ValueKind]++;
 802   }
 803 }
 804
 805 void CodeGenPGO::loadRegionCounts(llvm::IndexedInstrProfReader *PGOReader,
 806                                   bool IsInMainFile) {
 807   CGM.getPGOStats().addVisited(IsInMainFile);
 808   RegionCounts.clear();
 809   llvm::Expected<llvm::InstrProfRecord> RecordExpected =
 810       PGOReader->getInstrProfRecord(FuncName, FunctionHash);
 811   if (auto E = RecordExpected.takeError()) {
 812     auto IPE = llvm::InstrProfError::take(std::move(E));
 813     if (IPE == llvm::instrprof_error::unknown_function)
 814       CGM.getPGOStats().addMissing(IsInMainFile);
 815     else if (IPE == llvm::instrprof_error::hash_mismatch)
 816       CGM.getPGOStats().addMismatched(IsInMainFile);
 817     else if (IPE == llvm::instrprof_error::malformed)
 818       // TODO: Consider a more specific warning for this case.
 819       CGM.getPGOStats().addMismatched(IsInMainFile);
 820     return;
 821   }
 822   ProfRecord =
 823       llvm::make_unique<llvm::InstrProfRecord>(std::move(RecordExpected.get()));
 824   RegionCounts = ProfRecord->Counts;
 825 }
 826
 827 /// \brief Calculate what to divide by to scale weights.
 828 ///
 829 /// Given the maximum weight, calculate a divisor that will scale all the
 830 /// weights to strictly less than UINT32_MAX.
 831 static uint64_t calculateWeightScale(uint64_t MaxWeight) {
 832   return MaxWeight < UINT32_MAX ? 1 : MaxWeight / UINT32_MAX + 1;
 833 }
 834
 835 /// \brief Scale an individual branch weight (and add 1).
 836 ///
 837 /// Scale a 64-bit weight down to 32-bits using \c Scale.
 838 ///
 839 /// According to Laplace's Rule of Succession, it is better to compute the
 840 /// weight based on the count plus 1, so universally add 1 to the value.
 841 ///
 842 /// \pre \c Scale was calculated by \a calculateWeightScale() with a weight no
 843 /// greater than \c Weight.
 844 static uint32_t scaleBranchWeight(uint64_t Weight, uint64_t Scale) {
 845   assert(Scale && "scale by 0?");
 846   uint64_t Scaled = Weight / Scale + 1;
 847   assert(Scaled <= UINT32_MAX && "overflow 32-bits");
 848   return Scaled;
 849 }
 850
 851 llvm::MDNode *CodeGenFunction::createProfileWeights(uint64_t TrueCount,
 852                                                     uint64_t FalseCount) {
 853   // Check for empty weights.
 854   if (!TrueCount && !FalseCount)
 855     return nullptr;
 856
 857   // Calculate how to scale down to 32-bits.
 858   uint64_t Scale = calculateWeightScale(std::max(TrueCount, FalseCount));
 859
 860   llvm::MDBuilder MDHelper(CGM.getLLVMContext());
 861   return MDHelper.createBranchWeights(scaleBranchWeight(TrueCount, Scale),
 862                                       scaleBranchWeight(FalseCount, Scale));
 863 }
 864
 865 llvm::MDNode *
 866 CodeGenFunction::createProfileWeights(ArrayRef<uint64_t> Weights) {
 867   // We need at least two elements to create meaningful weights.
 868   if (Weights.size() < 2)
 869     return nullptr;
 870
 871   // Check for empty weights.
 872   uint64_t MaxWeight = *std::max_element(Weights.begin(), Weights.end());
 873   if (MaxWeight == 0)
 874     return nullptr;
 875
 876   // Calculate how to scale down to 32-bits.
 877   uint64_t Scale = calculateWeightScale(MaxWeight);
 878
 879   SmallVector<uint32_t, 16> ScaledWeights;
 880   ScaledWeights.reserve(Weights.size());
 881   for (uint64_t W : Weights)
 882     ScaledWeights.push_back(scaleBranchWeight(W, Scale));
 883
 884   llvm::MDBuilder MDHelper(CGM.getLLVMContext());
 885   return MDHelper.createBranchWeights(ScaledWeights);
 886 }
 887
 888 llvm::MDNode *CodeGenFunction::createProfileWeightsForLoop(const Stmt *Cond,
 889                                                            uint64_t LoopCount) {
 890   if (!PGO.haveRegionCounts())
 891     return nullptr;
 892   Optional<uint64_t> CondCount = PGO.getStmtCount(Cond);
 893   assert(CondCount.hasValue() && "missing expected loop condition count");
 894   if (*CondCount == 0)
 895     return nullptr;
 896   return createProfileWeights(LoopCount,
 897                               std::max(*CondCount, LoopCount) - LoopCount);
 898 }