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

   1 //===-- InstrProfiling.cpp - Frontend instrumentation based profiling -----===//
   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 pass lowers instrprof_* intrinsics emitted by a frontend for profiling.
  11 // It also builds the data structures and initialization code needed for
  12 // updating execution counts and emitting the profile at runtime.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/InstrProfiling.h"
  17 #include "llvm/ADT/ArrayRef.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/StringRef.h"
  20 #include "llvm/ADT/Triple.h"
  21 #include "llvm/ADT/Twine.h"
  22 #include "llvm/Analysis/LoopInfo.h"
  23 #include "llvm/Analysis/TargetLibraryInfo.h"
  24 #include "llvm/IR/Attributes.h"
  25 #include "llvm/IR/BasicBlock.h"
  26 #include "llvm/IR/Constant.h"
  27 #include "llvm/IR/Constants.h"
  28 #include "llvm/IR/DerivedTypes.h"
  29 #include "llvm/IR/Dominators.h"
  30 #include "llvm/IR/Function.h"
  31 #include "llvm/IR/GlobalValue.h"
  32 #include "llvm/IR/GlobalVariable.h"
  33 #include "llvm/IR/IRBuilder.h"
  34 #include "llvm/IR/Instruction.h"
  35 #include "llvm/IR/Instructions.h"
  36 #include "llvm/IR/IntrinsicInst.h"
  37 #include "llvm/IR/Module.h"
  38 #include "llvm/IR/Type.h"
  39 #include "llvm/Pass.h"
  40 #include "llvm/ProfileData/InstrProf.h"
  41 #include "llvm/Support/Casting.h"
  42 #include "llvm/Support/CommandLine.h"
  43 #include "llvm/Support/Error.h"
  44 #include "llvm/Support/ErrorHandling.h"
  45 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  46 #include "llvm/Transforms/Utils/LoopSimplify.h"
  47 #include "llvm/Transforms/Utils/ModuleUtils.h"
  48 #include "llvm/Transforms/Utils/SSAUpdater.h"
  49 #include <algorithm>
  50 #include <cassert>
  51 #include <cstddef>
  52 #include <cstdint>
  53 #include <string>
  54
  55 using namespace llvm;
  56
  57 #define DEBUG_TYPE "instrprof"
  58
  59 // The start and end values of precise value profile range for memory
  60 // intrinsic sizes
  61 cl::opt<std::string> MemOPSizeRange(
  62     "memop-size-range",
  63     cl::desc("Set the range of size in memory intrinsic calls to be profiled "
  64              "precisely, in a format of <start_val>:<end_val>"),
  65     cl::init(""));
  66
  67 // The value that considered to be large value in  memory intrinsic.
  68 cl::opt<unsigned> MemOPSizeLarge(
  69     "memop-size-large",
  70     cl::desc("Set large value thresthold in memory intrinsic size profiling. "
  71              "Value of 0 disables the large value profiling."),
  72     cl::init(8192));
  73
  74 namespace {
  75
  76 cl::opt<bool> DoNameCompression("enable-name-compression",
  77                                 cl::desc("Enable name string compression"),
  78                                 cl::init(true));
  79
  80 cl::opt<bool> DoHashBasedCounterSplit(
  81     "hash-based-counter-split",
  82     cl::desc("Rename counter variable of a comdat function based on cfg hash"),
  83     cl::init(true));
  84
  85 cl::opt<bool> ValueProfileStaticAlloc(
  86     "vp-static-alloc",
  87     cl::desc("Do static counter allocation for value profiler"),
  88     cl::init(true));
  89
  90 cl::opt<double> NumCountersPerValueSite(
  91     "vp-counters-per-site",
  92     cl::desc("The average number of profile counters allocated "
  93              "per value profiling site."),
  94     // This is set to a very small value because in real programs, only
  95     // a very small percentage of value sites have non-zero targets, e.g, 1/30.
  96     // For those sites with non-zero profile, the average number of targets
  97     // is usually smaller than 2.
  98     cl::init(1.0));
  99
 100 cl::opt<bool> AtomicCounterUpdatePromoted(
 101     "atomic-counter-update-promoted", cl::ZeroOrMore,
 102     cl::desc("Do counter update using atomic fetch add "
 103              " for promoted counters only"),
 104     cl::init(false));
 105
 106 // If the option is not specified, the default behavior about whether
 107 // counter promotion is done depends on how instrumentaiton lowering
 108 // pipeline is setup, i.e., the default value of true of this option
 109 // does not mean the promotion will be done by default. Explicitly
 110 // setting this option can override the default behavior.
 111 cl::opt<bool> DoCounterPromotion("do-counter-promotion", cl::ZeroOrMore,
 112                                  cl::desc("Do counter register promotion"),
 113                                  cl::init(false));
 114 cl::opt<unsigned> MaxNumOfPromotionsPerLoop(
 115     cl::ZeroOrMore, "max-counter-promotions-per-loop", cl::init(20),
 116     cl::desc("Max number counter promotions per loop to avoid"
 117              " increasing register pressure too much"));
 118
 119 // A debug option
 120 cl::opt<int>
 121     MaxNumOfPromotions(cl::ZeroOrMore, "max-counter-promotions", cl::init(-1),
 122                        cl::desc("Max number of allowed counter promotions"));
 123
 124 cl::opt<unsigned> SpeculativeCounterPromotionMaxExiting(
 125     cl::ZeroOrMore, "speculative-counter-promotion-max-exiting", cl::init(3),
 126     cl::desc("The max number of exiting blocks of a loop to allow "
 127              " speculative counter promotion"));
 128
 129 cl::opt<bool> SpeculativeCounterPromotionToLoop(
 130     cl::ZeroOrMore, "speculative-counter-promotion-to-loop", cl::init(false),
 131     cl::desc("When the option is false, if the target block is in a loop, "
 132              "the promotion will be disallowed unless the promoted counter "
 133              " update can be further/iteratively promoted into an acyclic "
 134              " region."));
 135
 136 cl::opt<bool> IterativeCounterPromotion(
 137     cl::ZeroOrMore, "iterative-counter-promotion", cl::init(true),
 138     cl::desc("Allow counter promotion across the whole loop nest."));
 139
 140 class InstrProfilingLegacyPass : public ModulePass {
 141   InstrProfiling InstrProf;
 142
 143 public:
 144   static char ID;
 145
 146   InstrProfilingLegacyPass() : ModulePass(ID) {}
 147   InstrProfilingLegacyPass(const InstrProfOptions &Options)
 148       : ModulePass(ID), InstrProf(Options) {}
 149
 150   StringRef getPassName() const override {
 151     return "Frontend instrumentation-based coverage lowering";
 152   }
 153
 154   bool runOnModule(Module &M) override {
 155     return InstrProf.run(M, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI());
 156   }
 157
 158   void getAnalysisUsage(AnalysisUsage &AU) const override {
 159     AU.setPreservesCFG();
 160     AU.addRequired<TargetLibraryInfoWrapperPass>();
 161   }
 162 };
 163
 164 ///
 165 /// A helper class to promote one counter RMW operation in the loop
 166 /// into register update.
 167 ///
 168 /// RWM update for the counter will be sinked out of the loop after
 169 /// the transformation.
 170 ///
 171 class PGOCounterPromoterHelper : public LoadAndStorePromoter {
 172 public:
 173   PGOCounterPromoterHelper(
 174       Instruction *L, Instruction *S, SSAUpdater &SSA, Value *Init,
 175       BasicBlock *PH, ArrayRef<BasicBlock *> ExitBlocks,
 176       ArrayRef<Instruction *> InsertPts,
 177       DenseMap<Loop *, SmallVector<LoadStorePair, 8>> &LoopToCands,
 178       LoopInfo &LI)
 179       : LoadAndStorePromoter({L, S}, SSA), Store(S), ExitBlocks(ExitBlocks),
 180         InsertPts(InsertPts), LoopToCandidates(LoopToCands), LI(LI) {
 181     assert(isa<LoadInst>(L));
 182     assert(isa<StoreInst>(S));
 183     SSA.AddAvailableValue(PH, Init);
 184   }
 185
 186   void doExtraRewritesBeforeFinalDeletion() const override {
 187     for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
 188       BasicBlock *ExitBlock = ExitBlocks[i];
 189       Instruction *InsertPos = InsertPts[i];
 190       // Get LiveIn value into the ExitBlock. If there are multiple
 191       // predecessors, the value is defined by a PHI node in this
 192       // block.
 193       Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
 194       Value *Addr = cast<StoreInst>(Store)->getPointerOperand();
 195       IRBuilder<> Builder(InsertPos);
 196       if (AtomicCounterUpdatePromoted)
 197         // automic update currently can only be promoted across the current
 198         // loop, not the whole loop nest.
 199         Builder.CreateAtomicRMW(AtomicRMWInst::Add, Addr, LiveInValue,
 200                                 AtomicOrdering::SequentiallyConsistent);
 201       else {
 202         LoadInst *OldVal = Builder.CreateLoad(Addr, "pgocount.promoted");
 203         auto *NewVal = Builder.CreateAdd(OldVal, LiveInValue);
 204         auto *NewStore = Builder.CreateStore(NewVal, Addr);
 205
 206         // Now update the parent loop's candidate list:
 207         if (IterativeCounterPromotion) {
 208           auto *TargetLoop = LI.getLoopFor(ExitBlock);
 209           if (TargetLoop)
 210             LoopToCandidates[TargetLoop].emplace_back(OldVal, NewStore);
 211         }
 212       }
 213     }
 214   }
 215
 216 private:
 217   Instruction *Store;
 218   ArrayRef<BasicBlock *> ExitBlocks;
 219   ArrayRef<Instruction *> InsertPts;
 220   DenseMap<Loop *, SmallVector<LoadStorePair, 8>> &LoopToCandidates;
 221   LoopInfo &LI;
 222 };
 223
 224 /// A helper class to do register promotion for all profile counter
 225 /// updates in a loop.
 226 ///
 227 class PGOCounterPromoter {
 228 public:
 229   PGOCounterPromoter(
 230       DenseMap<Loop *, SmallVector<LoadStorePair, 8>> &LoopToCands,
 231       Loop &CurLoop, LoopInfo &LI)
 232       : LoopToCandidates(LoopToCands), ExitBlocks(), InsertPts(), L(CurLoop),
 233         LI(LI) {
 234
 235     SmallVector<BasicBlock *, 8> LoopExitBlocks;
 236     SmallPtrSet<BasicBlock *, 8> BlockSet;
 237     L.getExitBlocks(LoopExitBlocks);
 238
 239     for (BasicBlock *ExitBlock : LoopExitBlocks) {
 240       if (BlockSet.insert(ExitBlock).second) {
 241         ExitBlocks.push_back(ExitBlock);
 242         InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
 243       }
 244     }
 245   }
 246
 247   bool run(int64_t *NumPromoted) {
 248     unsigned MaxProm = getMaxNumOfPromotionsInLoop(&L);
 249     if (MaxProm == 0)
 250       return false;
 251
 252     unsigned Promoted = 0;
 253     for (auto &Cand : LoopToCandidates[&L]) {
 254
 255       SmallVector<PHINode *, 4> NewPHIs;
 256       SSAUpdater SSA(&NewPHIs);
 257       Value *InitVal = ConstantInt::get(Cand.first->getType(), 0);
 258
 259       PGOCounterPromoterHelper Promoter(Cand.first, Cand.second, SSA, InitVal,
 260                                         L.getLoopPreheader(), ExitBlocks,
 261                                         InsertPts, LoopToCandidates, LI);
 262       Promoter.run(SmallVector<Instruction *, 2>({Cand.first, Cand.second}));
 263       Promoted++;
 264       if (Promoted >= MaxProm)
 265         break;
 266
 267       (*NumPromoted)++;
 268       if (MaxNumOfPromotions != -1 && *NumPromoted >= MaxNumOfPromotions)
 269         break;
 270     }
 271
 272     DEBUG(dbgs() << Promoted << " counters promoted for loop (depth="
 273                  << L.getLoopDepth() << ")\n");
 274     return Promoted != 0;
 275   }
 276
 277 private:
 278   bool allowSpeculativeCounterPromotion(Loop *LP) {
 279     SmallVector<BasicBlock *, 8> ExitingBlocks;
 280     L.getExitingBlocks(ExitingBlocks);
 281     // Not considierered speculative.
 282     if (ExitingBlocks.size() == 1)
 283       return true;
 284     if (ExitingBlocks.size() > SpeculativeCounterPromotionMaxExiting)
 285       return false;
 286     return true;
 287   }
 288
 289   // Returns the max number of Counter Promotions for LP.
 290   unsigned getMaxNumOfPromotionsInLoop(Loop *LP) {
 291     // We can't insert into a catchswitch.
 292     SmallVector<BasicBlock *, 8> LoopExitBlocks;
 293     LP->getExitBlocks(LoopExitBlocks);
 294     if (llvm::any_of(LoopExitBlocks, [](BasicBlock *Exit) {
 295           return isa<CatchSwitchInst>(Exit->getTerminator());
 296         }))
 297       return 0;
 298
 299     if (!LP->hasDedicatedExits())
 300       return 0;
 301
 302     BasicBlock *PH = LP->getLoopPreheader();
 303     if (!PH)
 304       return 0;
 305
 306     SmallVector<BasicBlock *, 8> ExitingBlocks;
 307     LP->getExitingBlocks(ExitingBlocks);
 308     // Not considierered speculative.
 309     if (ExitingBlocks.size() == 1)
 310       return MaxNumOfPromotionsPerLoop;
 311
 312     if (ExitingBlocks.size() > SpeculativeCounterPromotionMaxExiting)
 313       return 0;
 314
 315     // Whether the target block is in a loop does not matter:
 316     if (SpeculativeCounterPromotionToLoop)
 317       return MaxNumOfPromotionsPerLoop;
 318
 319     // Now check the target block:
 320     unsigned MaxProm = MaxNumOfPromotionsPerLoop;
 321     for (auto *TargetBlock : LoopExitBlocks) {
 322       auto *TargetLoop = LI.getLoopFor(TargetBlock);
 323       if (!TargetLoop)
 324         continue;
 325       unsigned MaxPromForTarget = getMaxNumOfPromotionsInLoop(TargetLoop);
 326       unsigned PendingCandsInTarget = LoopToCandidates[TargetLoop].size();
 327       MaxProm =
 328           std::min(MaxProm, std::max(MaxPromForTarget, PendingCandsInTarget) -
 329                                 PendingCandsInTarget);
 330     }
 331     return MaxProm;
 332   }
 333
 334   DenseMap<Loop *, SmallVector<LoadStorePair, 8>> &LoopToCandidates;
 335   SmallVector<BasicBlock *, 8> ExitBlocks;
 336   SmallVector<Instruction *, 8> InsertPts;
 337   Loop &L;
 338   LoopInfo &LI;
 339 };
 340
 341 } // end anonymous namespace
 342
 343 PreservedAnalyses InstrProfiling::run(Module &M, ModuleAnalysisManager &AM) {
 344   auto &TLI = AM.getResult<TargetLibraryAnalysis>(M);
 345   if (!run(M, TLI))
 346     return PreservedAnalyses::all();
 347
 348   return PreservedAnalyses::none();
 349 }
 350
 351 char InstrProfilingLegacyPass::ID = 0;
 352 INITIALIZE_PASS_BEGIN(
 353     InstrProfilingLegacyPass, "instrprof",
 354     "Frontend instrumentation-based coverage lowering.", false, false)
 355 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 356 INITIALIZE_PASS_END(
 357     InstrProfilingLegacyPass, "instrprof",
 358     "Frontend instrumentation-based coverage lowering.", false, false)
 359
 360 ModulePass *
 361 llvm::createInstrProfilingLegacyPass(const InstrProfOptions &Options) {
 362   return new InstrProfilingLegacyPass(Options);
 363 }
 364
 365 static InstrProfIncrementInst *castToIncrementInst(Instruction *Instr) {
 366   InstrProfIncrementInst *Inc = dyn_cast<InstrProfIncrementInstStep>(Instr);
 367   if (Inc)
 368     return Inc;
 369   return dyn_cast<InstrProfIncrementInst>(Instr);
 370 }
 371
 372 bool InstrProfiling::lowerIntrinsics(Function *F) {
 373   bool MadeChange = false;
 374   PromotionCandidates.clear();
 375   for (BasicBlock &BB : *F) {
 376     for (auto I = BB.begin(), E = BB.end(); I != E;) {
 377       auto Instr = I++;
 378       InstrProfIncrementInst *Inc = castToIncrementInst(&*Instr);
 379       if (Inc) {
 380         lowerIncrement(Inc);
 381         MadeChange = true;
 382       } else if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(Instr)) {
 383         lowerValueProfileInst(Ind);
 384         MadeChange = true;
 385       }
 386     }
 387   }
 388
 389   if (!MadeChange)
 390     return false;
 391
 392   promoteCounterLoadStores(F);
 393   return true;
 394 }
 395
 396 bool InstrProfiling::isCounterPromotionEnabled() const {
 397   if (DoCounterPromotion.getNumOccurrences() > 0)
 398     return DoCounterPromotion;
 399
 400   return Options.DoCounterPromotion;
 401 }
 402
 403 void InstrProfiling::promoteCounterLoadStores(Function *F) {
 404   if (!isCounterPromotionEnabled())
 405     return;
 406
 407   DominatorTree DT(*F);
 408   LoopInfo LI(DT);
 409   DenseMap<Loop *, SmallVector<LoadStorePair, 8>> LoopPromotionCandidates;
 410
 411   for (const auto &LoadStore : PromotionCandidates) {
 412     auto *CounterLoad = LoadStore.first;
 413     auto *CounterStore = LoadStore.second;
 414     BasicBlock *BB = CounterLoad->getParent();
 415     Loop *ParentLoop = LI.getLoopFor(BB);
 416     if (!ParentLoop)
 417       continue;
 418     LoopPromotionCandidates[ParentLoop].emplace_back(CounterLoad, CounterStore);
 419   }
 420
 421   SmallVector<Loop *, 4> Loops = LI.getLoopsInPreorder();
 422
 423   // Do a post-order traversal of the loops so that counter updates can be
 424   // iteratively hoisted outside the loop nest.
 425   for (auto *Loop : llvm::reverse(Loops)) {
 426     PGOCounterPromoter Promoter(LoopPromotionCandidates, *Loop, LI);
 427     Promoter.run(&TotalCountersPromoted);
 428   }
 429 }
 430
 431 bool InstrProfiling::run(Module &M, const TargetLibraryInfo &TLI) {
 432   bool MadeChange = false;
 433
 434   this->M = &M;
 435   this->TLI = &TLI;
 436   NamesVar = nullptr;
 437   NamesSize = 0;
 438   ProfileDataMap.clear();
 439   UsedVars.clear();
 440   getMemOPSizeRangeFromOption(MemOPSizeRange, MemOPSizeRangeStart,
 441                               MemOPSizeRangeLast);
 442   TT = Triple(M.getTargetTriple());
 443
 444   // We did not know how many value sites there would be inside
 445   // the instrumented function. This is counting the number of instrumented
 446   // target value sites to enter it as field in the profile data variable.
 447   for (Function &F : M) {
 448     InstrProfIncrementInst *FirstProfIncInst = nullptr;
 449     for (BasicBlock &BB : F)
 450       for (auto I = BB.begin(), E = BB.end(); I != E; I++)
 451         if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(I))
 452           computeNumValueSiteCounts(Ind);
 453         else if (FirstProfIncInst == nullptr)
 454           FirstProfIncInst = dyn_cast<InstrProfIncrementInst>(I);
 455
 456     // Value profiling intrinsic lowering requires per-function profile data
 457     // variable to be created first.
 458     if (FirstProfIncInst != nullptr)
 459       static_cast<void>(getOrCreateRegionCounters(FirstProfIncInst));
 460   }
 461
 462   for (Function &F : M)
 463     MadeChange |= lowerIntrinsics(&F);
 464
 465   if (GlobalVariable *CoverageNamesVar =
 466           M.getNamedGlobal(getCoverageUnusedNamesVarName())) {
 467     lowerCoverageData(CoverageNamesVar);
 468     MadeChange = true;
 469   }
 470
 471   if (!MadeChange)
 472     return false;
 473
 474   emitVNodes();
 475   emitNameData();
 476   emitRegistration();
 477   emitRuntimeHook();
 478   emitUses();
 479   emitInitialization();
 480   return true;
 481 }
 482
 483 static Constant *getOrInsertValueProfilingCall(Module &M,
 484                                                const TargetLibraryInfo &TLI,
 485                                                bool IsRange = false) {
 486   LLVMContext &Ctx = M.getContext();
 487   auto *ReturnTy = Type::getVoidTy(M.getContext());
 488
 489   Constant *Res;
 490   if (!IsRange) {
 491     Type *ParamTypes[] = {
 492 #define VALUE_PROF_FUNC_PARAM(ParamType, ParamName, ParamLLVMType) ParamLLVMType
 493 #include "llvm/ProfileData/InstrProfData.inc"
 494     };
 495     auto *ValueProfilingCallTy =
 496         FunctionType::get(ReturnTy, makeArrayRef(ParamTypes), false);
 497     Res = M.getOrInsertFunction(getInstrProfValueProfFuncName(),
 498                                 ValueProfilingCallTy);
 499   } else {
 500     Type *RangeParamTypes[] = {
 501 #define VALUE_RANGE_PROF 1
 502 #define VALUE_PROF_FUNC_PARAM(ParamType, ParamName, ParamLLVMType) ParamLLVMType
 503 #include "llvm/ProfileData/InstrProfData.inc"
 504 #undef VALUE_RANGE_PROF
 505     };
 506     auto *ValueRangeProfilingCallTy =
 507         FunctionType::get(ReturnTy, makeArrayRef(RangeParamTypes), false);
 508     Res = M.getOrInsertFunction(getInstrProfValueRangeProfFuncName(),
 509                                 ValueRangeProfilingCallTy);
 510   }
 511
 512   if (Function *FunRes = dyn_cast<Function>(Res)) {
 513     if (auto AK = TLI.getExtAttrForI32Param(false))
 514       FunRes->addParamAttr(2, AK);
 515   }
 516   return Res;
 517 }
 518
 519 void InstrProfiling::computeNumValueSiteCounts(InstrProfValueProfileInst *Ind) {
 520   GlobalVariable *Name = Ind->getName();
 521   uint64_t ValueKind = Ind->getValueKind()->getZExtValue();
 522   uint64_t Index = Ind->getIndex()->getZExtValue();
 523   auto It = ProfileDataMap.find(Name);
 524   if (It == ProfileDataMap.end()) {
 525     PerFunctionProfileData PD;
 526     PD.NumValueSites[ValueKind] = Index + 1;
 527     ProfileDataMap[Name] = PD;
 528   } else if (It->second.NumValueSites[ValueKind] <= Index)
 529     It->second.NumValueSites[ValueKind] = Index + 1;
 530 }
 531
 532 void InstrProfiling::lowerValueProfileInst(InstrProfValueProfileInst *Ind) {
 533   GlobalVariable *Name = Ind->getName();
 534   auto It = ProfileDataMap.find(Name);
 535   assert(It != ProfileDataMap.end() && It->second.DataVar &&
 536          "value profiling detected in function with no counter incerement");
 537
 538   GlobalVariable *DataVar = It->second.DataVar;
 539   uint64_t ValueKind = Ind->getValueKind()->getZExtValue();
 540   uint64_t Index = Ind->getIndex()->getZExtValue();
 541   for (uint32_t Kind = IPVK_First; Kind < ValueKind; ++Kind)
 542     Index += It->second.NumValueSites[Kind];
 543
 544   IRBuilder<> Builder(Ind);
 545   bool IsRange = (Ind->getValueKind()->getZExtValue() ==
 546                   llvm::InstrProfValueKind::IPVK_MemOPSize);
 547   CallInst *Call = nullptr;
 548   if (!IsRange) {
 549     Value *Args[3] = {Ind->getTargetValue(),
 550                       Builder.CreateBitCast(DataVar, Builder.getInt8PtrTy()),
 551                       Builder.getInt32(Index)};
 552     Call = Builder.CreateCall(getOrInsertValueProfilingCall(*M, *TLI), Args);
 553   } else {
 554     Value *Args[6] = {
 555         Ind->getTargetValue(),
 556         Builder.CreateBitCast(DataVar, Builder.getInt8PtrTy()),
 557         Builder.getInt32(Index),
 558         Builder.getInt64(MemOPSizeRangeStart),
 559         Builder.getInt64(MemOPSizeRangeLast),
 560         Builder.getInt64(MemOPSizeLarge == 0 ? INT64_MIN : MemOPSizeLarge)};
 561     Call =
 562         Builder.CreateCall(getOrInsertValueProfilingCall(*M, *TLI, true), Args);
 563   }
 564   if (auto AK = TLI->getExtAttrForI32Param(false))
 565     Call->addParamAttr(2, AK);
 566   Ind->replaceAllUsesWith(Call);
 567   Ind->eraseFromParent();
 568 }
 569
 570 void InstrProfiling::lowerIncrement(InstrProfIncrementInst *Inc) {
 571   GlobalVariable *Counters = getOrCreateRegionCounters(Inc);
 572
 573   IRBuilder<> Builder(Inc);
 574   uint64_t Index = Inc->getIndex()->getZExtValue();
 575   Value *Addr = Builder.CreateConstInBoundsGEP2_64(Counters, 0, Index);
 576   Value *Load = Builder.CreateLoad(Addr, "pgocount");
 577   auto *Count = Builder.CreateAdd(Load, Inc->getStep());
 578   auto *Store = Builder.CreateStore(Count, Addr);
 579   Inc->replaceAllUsesWith(Store);
 580   if (isCounterPromotionEnabled())
 581     PromotionCandidates.emplace_back(cast<Instruction>(Load), Store);
 582   Inc->eraseFromParent();
 583 }
 584
 585 void InstrProfiling::lowerCoverageData(GlobalVariable *CoverageNamesVar) {
 586   ConstantArray *Names =
 587       cast<ConstantArray>(CoverageNamesVar->getInitializer());
 588   for (unsigned I = 0, E = Names->getNumOperands(); I < E; ++I) {
 589     Constant *NC = Names->getOperand(I);
 590     Value *V = NC->stripPointerCasts();
 591     assert(isa<GlobalVariable>(V) && "Missing reference to function name");
 592     GlobalVariable *Name = cast<GlobalVariable>(V);
 593
 594     Name->setLinkage(GlobalValue::PrivateLinkage);
 595     ReferencedNames.push_back(Name);
 596     NC->dropAllReferences();
 597   }
 598   CoverageNamesVar->eraseFromParent();
 599 }
 600
 601 /// Get the name of a profiling variable for a particular function.
 602 static std::string getVarName(InstrProfIncrementInst *Inc, StringRef Prefix) {
 603   StringRef NamePrefix = getInstrProfNameVarPrefix();
 604   StringRef Name = Inc->getName()->getName().substr(NamePrefix.size());
 605   Function *F = Inc->getParent()->getParent();
 606   Module *M = F->getParent();
 607   if (!DoHashBasedCounterSplit || !isIRPGOFlagSet(M) ||
 608       !canRenameComdatFunc(*F))
 609     return (Prefix + Name).str();
 610   uint64_t FuncHash = Inc->getHash()->getZExtValue();
 611   SmallVector<char, 24> HashPostfix;
 612   if (Name.endswith((Twine(".") + Twine(FuncHash)).toStringRef(HashPostfix)))
 613     return (Prefix + Name).str();
 614   return (Prefix + Name + "." + Twine(FuncHash)).str();
 615 }
 616
 617 static inline bool shouldRecordFunctionAddr(Function *F) {
 618   // Check the linkage
 619   bool HasAvailableExternallyLinkage = F->hasAvailableExternallyLinkage();
 620   if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage() &&
 621       !HasAvailableExternallyLinkage)
 622     return true;
 623
 624   // A function marked 'alwaysinline' with available_externally linkage can't
 625   // have its address taken. Doing so would create an undefined external ref to
 626   // the function, which would fail to link.
 627   if (HasAvailableExternallyLinkage &&
 628       F->hasFnAttribute(Attribute::AlwaysInline))
 629     return false;
 630
 631   // Prohibit function address recording if the function is both internal and
 632   // COMDAT. This avoids the profile data variable referencing internal symbols
 633   // in COMDAT.
 634   if (F->hasLocalLinkage() && F->hasComdat())
 635     return false;
 636
 637   // Check uses of this function for other than direct calls or invokes to it.
 638   // Inline virtual functions have linkeOnceODR linkage. When a key method
 639   // exists, the vtable will only be emitted in the TU where the key method
 640   // is defined. In a TU where vtable is not available, the function won't
 641   // be 'addresstaken'. If its address is not recorded here, the profile data
 642   // with missing address may be picked by the linker leading  to missing
 643   // indirect call target info.
 644   return F->hasAddressTaken() || F->hasLinkOnceLinkage();
 645 }
 646
 647 static inline Comdat *getOrCreateProfileComdat(Module &M, Function &F,
 648                                                InstrProfIncrementInst *Inc) {
 649   if (!needsComdatForCounter(F, M))
 650     return nullptr;
 651
 652   // COFF format requires a COMDAT section to have a key symbol with the same
 653   // name. The linker targeting COFF also requires that the COMDAT
 654   // a section is associated to must precede the associating section. For this
 655   // reason, we must choose the counter var's name as the name of the comdat.
 656   StringRef ComdatPrefix = (Triple(M.getTargetTriple()).isOSBinFormatCOFF()
 657                                 ? getInstrProfCountersVarPrefix()
 658                                 : getInstrProfComdatPrefix());
 659   return M.getOrInsertComdat(StringRef(getVarName(Inc, ComdatPrefix)));
 660 }
 661
 662 static bool needsRuntimeRegistrationOfSectionRange(const Module &M) {
 663   // Don't do this for Darwin.  compiler-rt uses linker magic.
 664   if (Triple(M.getTargetTriple()).isOSDarwin())
 665     return false;
 666
 667   // Use linker script magic to get data/cnts/name start/end.
 668   if (Triple(M.getTargetTriple()).isOSLinux() ||
 669       Triple(M.getTargetTriple()).isOSFreeBSD() ||
 670       Triple(M.getTargetTriple()).isPS4CPU())
 671     return false;
 672
 673   return true;
 674 }
 675
 676 GlobalVariable *
 677 InstrProfiling::getOrCreateRegionCounters(InstrProfIncrementInst *Inc) {
 678   GlobalVariable *NamePtr = Inc->getName();
 679   auto It = ProfileDataMap.find(NamePtr);
 680   PerFunctionProfileData PD;
 681   if (It != ProfileDataMap.end()) {
 682     if (It->second.RegionCounters)
 683       return It->second.RegionCounters;
 684     PD = It->second;
 685   }
 686
 687   // Move the name variable to the right section. Place them in a COMDAT group
 688   // if the associated function is a COMDAT. This will make sure that
 689   // only one copy of counters of the COMDAT function will be emitted after
 690   // linking.
 691   Function *Fn = Inc->getParent()->getParent();
 692   Comdat *ProfileVarsComdat = nullptr;
 693   ProfileVarsComdat = getOrCreateProfileComdat(*M, *Fn, Inc);
 694
 695   uint64_t NumCounters = Inc->getNumCounters()->getZExtValue();
 696   LLVMContext &Ctx = M->getContext();
 697   ArrayType *CounterTy = ArrayType::get(Type::getInt64Ty(Ctx), NumCounters);
 698
 699   // Create the counters variable.
 700   auto *CounterPtr =
 701       new GlobalVariable(*M, CounterTy, false, NamePtr->getLinkage(),
 702                          Constant::getNullValue(CounterTy),
 703                          getVarName(Inc, getInstrProfCountersVarPrefix()));
 704   CounterPtr->setVisibility(NamePtr->getVisibility());
 705   CounterPtr->setSection(
 706       getInstrProfSectionName(IPSK_cnts, TT.getObjectFormat()));
 707   CounterPtr->setAlignment(8);
 708   CounterPtr->setComdat(ProfileVarsComdat);
 709
 710   auto *Int8PtrTy = Type::getInt8PtrTy(Ctx);
 711   // Allocate statically the array of pointers to value profile nodes for
 712   // the current function.
 713   Constant *ValuesPtrExpr = ConstantPointerNull::get(Int8PtrTy);
 714   if (ValueProfileStaticAlloc && !needsRuntimeRegistrationOfSectionRange(*M)) {
 715     uint64_t NS = 0;
 716     for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 717       NS += PD.NumValueSites[Kind];
 718     if (NS) {
 719       ArrayType *ValuesTy = ArrayType::get(Type::getInt64Ty(Ctx), NS);
 720
 721       auto *ValuesVar =
 722           new GlobalVariable(*M, ValuesTy, false, NamePtr->getLinkage(),
 723                              Constant::getNullValue(ValuesTy),
 724                              getVarName(Inc, getInstrProfValuesVarPrefix()));
 725       ValuesVar->setVisibility(NamePtr->getVisibility());
 726       ValuesVar->setSection(
 727           getInstrProfSectionName(IPSK_vals, TT.getObjectFormat()));
 728       ValuesVar->setAlignment(8);
 729       ValuesVar->setComdat(ProfileVarsComdat);
 730       ValuesPtrExpr =
 731           ConstantExpr::getBitCast(ValuesVar, Type::getInt8PtrTy(Ctx));
 732     }
 733   }
 734
 735   // Create data variable.
 736   auto *Int16Ty = Type::getInt16Ty(Ctx);
 737   auto *Int16ArrayTy = ArrayType::get(Int16Ty, IPVK_Last + 1);
 738   Type *DataTypes[] = {
 739 #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) LLVMType,
 740 #include "llvm/ProfileData/InstrProfData.inc"
 741   };
 742   auto *DataTy = StructType::get(Ctx, makeArrayRef(DataTypes));
 743
 744   Constant *FunctionAddr = shouldRecordFunctionAddr(Fn)
 745                                ? ConstantExpr::getBitCast(Fn, Int8PtrTy)
 746                                : ConstantPointerNull::get(Int8PtrTy);
 747
 748   Constant *Int16ArrayVals[IPVK_Last + 1];
 749   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 750     Int16ArrayVals[Kind] = ConstantInt::get(Int16Ty, PD.NumValueSites[Kind]);
 751
 752   Constant *DataVals[] = {
 753 #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) Init,
 754 #include "llvm/ProfileData/InstrProfData.inc"
 755   };
 756   auto *Data = new GlobalVariable(*M, DataTy, false, NamePtr->getLinkage(),
 757                                   ConstantStruct::get(DataTy, DataVals),
 758                                   getVarName(Inc, getInstrProfDataVarPrefix()));
 759   Data->setVisibility(NamePtr->getVisibility());
 760   Data->setSection(getInstrProfSectionName(IPSK_data, TT.getObjectFormat()));
 761   Data->setAlignment(INSTR_PROF_DATA_ALIGNMENT);
 762   Data->setComdat(ProfileVarsComdat);
 763
 764   PD.RegionCounters = CounterPtr;
 765   PD.DataVar = Data;
 766   ProfileDataMap[NamePtr] = PD;
 767
 768   // Mark the data variable as used so that it isn't stripped out.
 769   UsedVars.push_back(Data);
 770   // Now that the linkage set by the FE has been passed to the data and counter
 771   // variables, reset Name variable's linkage and visibility to private so that
 772   // it can be removed later by the compiler.
 773   NamePtr->setLinkage(GlobalValue::PrivateLinkage);
 774   // Collect the referenced names to be used by emitNameData.
 775   ReferencedNames.push_back(NamePtr);
 776
 777   return CounterPtr;
 778 }
 779
 780 void InstrProfiling::emitVNodes() {
 781   if (!ValueProfileStaticAlloc)
 782     return;
 783
 784   // For now only support this on platforms that do
 785   // not require runtime registration to discover
 786   // named section start/end.
 787   if (needsRuntimeRegistrationOfSectionRange(*M))
 788     return;
 789
 790   size_t TotalNS = 0;
 791   for (auto &PD : ProfileDataMap) {
 792     for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 793       TotalNS += PD.second.NumValueSites[Kind];
 794   }
 795
 796   if (!TotalNS)
 797     return;
 798
 799   uint64_t NumCounters = TotalNS * NumCountersPerValueSite;
 800 // Heuristic for small programs with very few total value sites.
 801 // The default value of vp-counters-per-site is chosen based on
 802 // the observation that large apps usually have a low percentage
 803 // of value sites that actually have any profile data, and thus
 804 // the average number of counters per site is low. For small
 805 // apps with very few sites, this may not be true. Bump up the
 806 // number of counters in this case.
 807 #define INSTR_PROF_MIN_VAL_COUNTS 10
 808   if (NumCounters < INSTR_PROF_MIN_VAL_COUNTS)
 809     NumCounters = std::max(INSTR_PROF_MIN_VAL_COUNTS, (int)NumCounters * 2);
 810
 811   auto &Ctx = M->getContext();
 812   Type *VNodeTypes[] = {
 813 #define INSTR_PROF_VALUE_NODE(Type, LLVMType, Name, Init) LLVMType,
 814 #include "llvm/ProfileData/InstrProfData.inc"
 815   };
 816   auto *VNodeTy = StructType::get(Ctx, makeArrayRef(VNodeTypes));
 817
 818   ArrayType *VNodesTy = ArrayType::get(VNodeTy, NumCounters);
 819   auto *VNodesVar = new GlobalVariable(
 820       *M, VNodesTy, false, GlobalValue::PrivateLinkage,
 821       Constant::getNullValue(VNodesTy), getInstrProfVNodesVarName());
 822   VNodesVar->setSection(
 823       getInstrProfSectionName(IPSK_vnodes, TT.getObjectFormat()));
 824   UsedVars.push_back(VNodesVar);
 825 }
 826
 827 void InstrProfiling::emitNameData() {
 828   std::string UncompressedData;
 829
 830   if (ReferencedNames.empty())
 831     return;
 832
 833   std::string CompressedNameStr;
 834   if (Error E = collectPGOFuncNameStrings(ReferencedNames, CompressedNameStr,
 835                                           DoNameCompression)) {
 836     report_fatal_error(toString(std::move(E)), false);
 837   }
 838
 839   auto &Ctx = M->getContext();
 840   auto *NamesVal = ConstantDataArray::getString(
 841       Ctx, StringRef(CompressedNameStr), false);
 842   NamesVar = new GlobalVariable(*M, NamesVal->getType(), true,
 843                                 GlobalValue::PrivateLinkage, NamesVal,
 844                                 getInstrProfNamesVarName());
 845   NamesSize = CompressedNameStr.size();
 846   NamesVar->setSection(
 847       getInstrProfSectionName(IPSK_name, TT.getObjectFormat()));
 848   UsedVars.push_back(NamesVar);
 849
 850   for (auto *NamePtr : ReferencedNames)
 851     NamePtr->eraseFromParent();
 852 }
 853
 854 void InstrProfiling::emitRegistration() {
 855   if (!needsRuntimeRegistrationOfSectionRange(*M))
 856     return;
 857
 858   // Construct the function.
 859   auto *VoidTy = Type::getVoidTy(M->getContext());
 860   auto *VoidPtrTy = Type::getInt8PtrTy(M->getContext());
 861   auto *Int64Ty = Type::getInt64Ty(M->getContext());
 862   auto *RegisterFTy = FunctionType::get(VoidTy, false);
 863   auto *RegisterF = Function::Create(RegisterFTy, GlobalValue::InternalLinkage,
 864                                      getInstrProfRegFuncsName(), M);
 865   RegisterF->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 866   if (Options.NoRedZone)
 867     RegisterF->addFnAttr(Attribute::NoRedZone);
 868
 869   auto *RuntimeRegisterTy = FunctionType::get(VoidTy, VoidPtrTy, false);
 870   auto *RuntimeRegisterF =
 871       Function::Create(RuntimeRegisterTy, GlobalVariable::ExternalLinkage,
 872                        getInstrProfRegFuncName(), M);
 873
 874   IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", RegisterF));
 875   for (Value *Data : UsedVars)
 876     if (Data != NamesVar)
 877       IRB.CreateCall(RuntimeRegisterF, IRB.CreateBitCast(Data, VoidPtrTy));
 878
 879   if (NamesVar) {
 880     Type *ParamTypes[] = {VoidPtrTy, Int64Ty};
 881     auto *NamesRegisterTy =
 882         FunctionType::get(VoidTy, makeArrayRef(ParamTypes), false);
 883     auto *NamesRegisterF =
 884         Function::Create(NamesRegisterTy, GlobalVariable::ExternalLinkage,
 885                          getInstrProfNamesRegFuncName(), M);
 886     IRB.CreateCall(NamesRegisterF, {IRB.CreateBitCast(NamesVar, VoidPtrTy),
 887                                     IRB.getInt64(NamesSize)});
 888   }
 889
 890   IRB.CreateRetVoid();
 891 }
 892
 893 void InstrProfiling::emitRuntimeHook() {
 894   // We expect the linker to be invoked with -u<hook_var> flag for linux,
 895   // for which case there is no need to emit the user function.
 896   if (Triple(M->getTargetTriple()).isOSLinux())
 897     return;
 898
 899   // If the module's provided its own runtime, we don't need to do anything.
 900   if (M->getGlobalVariable(getInstrProfRuntimeHookVarName()))
 901     return;
 902
 903   // Declare an external variable that will pull in the runtime initialization.
 904   auto *Int32Ty = Type::getInt32Ty(M->getContext());
 905   auto *Var =
 906       new GlobalVariable(*M, Int32Ty, false, GlobalValue::ExternalLinkage,
 907                          nullptr, getInstrProfRuntimeHookVarName());
 908
 909   // Make a function that uses it.
 910   auto *User = Function::Create(FunctionType::get(Int32Ty, false),
 911                                 GlobalValue::LinkOnceODRLinkage,
 912                                 getInstrProfRuntimeHookVarUseFuncName(), M);
 913   User->addFnAttr(Attribute::NoInline);
 914   if (Options.NoRedZone)
 915     User->addFnAttr(Attribute::NoRedZone);
 916   User->setVisibility(GlobalValue::HiddenVisibility);
 917   if (Triple(M->getTargetTriple()).supportsCOMDAT())
 918     User->setComdat(M->getOrInsertComdat(User->getName()));
 919
 920   IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", User));
 921   auto *Load = IRB.CreateLoad(Var);
 922   IRB.CreateRet(Load);
 923
 924   // Mark the user variable as used so that it isn't stripped out.
 925   UsedVars.push_back(User);
 926 }
 927
 928 void InstrProfiling::emitUses() {
 929   if (!UsedVars.empty())
 930     appendToUsed(*M, UsedVars);
 931 }
 932
 933 void InstrProfiling::emitInitialization() {
 934   StringRef InstrProfileOutput = Options.InstrProfileOutput;
 935
 936   if (!InstrProfileOutput.empty()) {
 937     // Create variable for profile name.
 938     Constant *ProfileNameConst =
 939         ConstantDataArray::getString(M->getContext(), InstrProfileOutput, true);
 940     GlobalVariable *ProfileNameVar = new GlobalVariable(
 941         *M, ProfileNameConst->getType(), true, GlobalValue::WeakAnyLinkage,
 942         ProfileNameConst, INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_NAME_VAR));
 943     if (TT.supportsCOMDAT()) {
 944       ProfileNameVar->setLinkage(GlobalValue::ExternalLinkage);
 945       ProfileNameVar->setComdat(M->getOrInsertComdat(
 946           StringRef(INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_NAME_VAR))));
 947     }
 948   }
 949
 950   Constant *RegisterF = M->getFunction(getInstrProfRegFuncsName());
 951   if (!RegisterF)
 952     return;
 953
 954   // Create the initialization function.
 955   auto *VoidTy = Type::getVoidTy(M->getContext());
 956   auto *F = Function::Create(FunctionType::get(VoidTy, false),
 957                              GlobalValue::InternalLinkage,
 958                              getInstrProfInitFuncName(), M);
 959   F->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
 960   F->addFnAttr(Attribute::NoInline);
 961   if (Options.NoRedZone)
 962     F->addFnAttr(Attribute::NoRedZone);
 963
 964   // Add the basic block and the necessary calls.
 965   IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", F));
 966   if (RegisterF)
 967     IRB.CreateCall(RegisterF, {});
 968   IRB.CreateRetVoid();
 969
 970   appendToGlobalCtors(*M, F, 0);
 971 }