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