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/ADT/Triple.h"
17#include "llvm/IR/IRBuilder.h"
18#include "llvm/IR/IntrinsicInst.h"
19#include "llvm/IR/Module.h"
20#include "llvm/ProfileData/InstrProf.h"
21#include "llvm/Transforms/Instrumentation.h"
22#include "llvm/Transforms/Utils/ModuleUtils.h"
23
24using namespace llvm;
25
26#define DEBUG_TYPE "instrprof"
27
28namespace {
29
30class InstrProfiling : public ModulePass {
31public:
32  static char ID;
33
34  InstrProfiling() : ModulePass(ID) {}
35
36  InstrProfiling(const InstrProfOptions &Options)
37      : ModulePass(ID), Options(Options) {}
38
39  const char *getPassName() const override {
40    return "Frontend instrumentation-based coverage lowering";
41  }
42
43  bool runOnModule(Module &M) override;
44
45  void getAnalysisUsage(AnalysisUsage &AU) const override {
46    AU.setPreservesCFG();
47  }
48
49private:
50  InstrProfOptions Options;
51  Module *M;
52  typedef struct PerFunctionProfileData {
53    uint32_t NumValueSites[IPVK_Last+1];
54    GlobalVariable* RegionCounters;
55    GlobalVariable* DataVar;
56    PerFunctionProfileData() : RegionCounters(nullptr), DataVar(nullptr) {
57      memset(NumValueSites, 0, sizeof(uint32_t) * (IPVK_Last+1));
58    }
59  } PerFunctionProfileData;
60  DenseMap<GlobalVariable *, PerFunctionProfileData> ProfileDataMap;
61  std::vector<Value *> UsedVars;
62
63  bool isMachO() const {
64    return Triple(M->getTargetTriple()).isOSBinFormatMachO();
65  }
66
67  /// Get the section name for the counter variables.
68  StringRef getCountersSection() const {
69    return getInstrProfCountersSectionName(isMachO());
70  }
71
72  /// Get the section name for the name variables.
73  StringRef getNameSection() const {
74    return getInstrProfNameSectionName(isMachO());
75  }
76
77  /// Get the section name for the profile data variables.
78  StringRef getDataSection() const {
79    return getInstrProfDataSectionName(isMachO());
80  }
81
82  /// Get the section name for the coverage mapping data.
83  StringRef getCoverageSection() const {
84    return getInstrProfCoverageSectionName(isMachO());
85  }
86
87  /// Count the number of instrumented value sites for the function.
88  void computeNumValueSiteCounts(InstrProfValueProfileInst *Ins);
89
90  /// Replace instrprof_value_profile with a call to runtime library.
91  void lowerValueProfileInst(InstrProfValueProfileInst *Ins);
92
93  /// Replace instrprof_increment with an increment of the appropriate value.
94  void lowerIncrement(InstrProfIncrementInst *Inc);
95
96  /// Set up the section and uses for coverage data and its references.
97  void lowerCoverageData(GlobalVariable *CoverageData);
98
99  /// Get the region counters for an increment, creating them if necessary.
100  ///
101  /// If the counter array doesn't yet exist, the profile data variables
102  /// referring to them will also be created.
103  GlobalVariable *getOrCreateRegionCounters(InstrProfIncrementInst *Inc);
104
105  /// Emit runtime registration functions for each profile data variable.
106  void emitRegistration();
107
108  /// Emit the necessary plumbing to pull in the runtime initialization.
109  void emitRuntimeHook();
110
111  /// Add uses of our data variables and runtime hook.
112  void emitUses();
113
114  /// Create a static initializer for our data, on platforms that need it,
115  /// and for any profile output file that was specified.
116  void emitInitialization();
117};
118
119} // anonymous namespace
120
121char InstrProfiling::ID = 0;
122INITIALIZE_PASS(InstrProfiling, "instrprof",
123                "Frontend instrumentation-based coverage lowering.", false,
124                false)
125
126ModulePass *llvm::createInstrProfilingPass(const InstrProfOptions &Options) {
127  return new InstrProfiling(Options);
128}
129
130bool InstrProfiling::runOnModule(Module &M) {
131  bool MadeChange = false;
132
133  this->M = &M;
134  ProfileDataMap.clear();
135  UsedVars.clear();
136
137  // We did not know how many value sites there would be inside
138  // the instrumented function. This is counting the number of instrumented
139  // target value sites to enter it as field in the profile data variable.
140  for (Function &F : M)
141    for (BasicBlock &BB : F)
142      for (auto I = BB.begin(), E = BB.end(); I != E;)
143        if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(I++))
144          computeNumValueSiteCounts(Ind);
145
146  for (Function &F : M)
147    for (BasicBlock &BB : F)
148      for (auto I = BB.begin(), E = BB.end(); I != E;) {
149        auto Instr = I++;
150        if (auto *Inc = dyn_cast<InstrProfIncrementInst>(Instr)) {
151          lowerIncrement(Inc);
152          MadeChange = true;
153        } else if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(Instr)) {
154          lowerValueProfileInst(Ind);
155          MadeChange = true;
156        }
157      }
158
159  if (GlobalVariable *Coverage =
160          M.getNamedGlobal(getCoverageMappingVarName())) {
161    lowerCoverageData(Coverage);
162    MadeChange = true;
163  }
164
165  if (!MadeChange)
166    return false;
167
168  emitRegistration();
169  emitRuntimeHook();
170  emitUses();
171  emitInitialization();
172  return true;
173}
174
175static Constant *getOrInsertValueProfilingCall(Module &M) {
176  LLVMContext &Ctx = M.getContext();
177  auto *ReturnTy = Type::getVoidTy(M.getContext());
178  Type *ParamTypes[] = {
179#define VALUE_PROF_FUNC_PARAM(ParamType, ParamName, ParamLLVMType) ParamLLVMType
180#include "llvm/ProfileData/InstrProfData.inc"
181  };
182  auto *ValueProfilingCallTy =
183      FunctionType::get(ReturnTy, makeArrayRef(ParamTypes), false);
184  return M.getOrInsertFunction(getInstrProfValueProfFuncName(),
185                               ValueProfilingCallTy);
186}
187
188void InstrProfiling::computeNumValueSiteCounts(InstrProfValueProfileInst *Ind) {
189
190  GlobalVariable *Name = Ind->getName();
191  uint64_t ValueKind = Ind->getValueKind()->getZExtValue();
192  uint64_t Index = Ind->getIndex()->getZExtValue();
193  auto It = ProfileDataMap.find(Name);
194  if (It == ProfileDataMap.end()) {
195    PerFunctionProfileData PD;
196    PD.NumValueSites[ValueKind] = Index + 1;
197    ProfileDataMap[Name] = PD;
198  } else if (It->second.NumValueSites[ValueKind] <= Index)
199    It->second.NumValueSites[ValueKind] = Index + 1;
200}
201
202void InstrProfiling::lowerValueProfileInst(InstrProfValueProfileInst *Ind) {
203
204  GlobalVariable *Name = Ind->getName();
205  auto It = ProfileDataMap.find(Name);
206  assert(It != ProfileDataMap.end() && It->second.DataVar &&
207    "value profiling detected in function with no counter incerement");
208
209  GlobalVariable *DataVar = It->second.DataVar;
210  uint64_t ValueKind = Ind->getValueKind()->getZExtValue();
211  uint64_t Index = Ind->getIndex()->getZExtValue();
212  for (uint32_t Kind = IPVK_First; Kind < ValueKind; ++Kind)
213    Index += It->second.NumValueSites[Kind];
214
215  IRBuilder<> Builder(Ind);
216  Value* Args[3] = {Ind->getTargetValue(),
217      Builder.CreateBitCast(DataVar, Builder.getInt8PtrTy()),
218      Builder.getInt32(Index)};
219  Ind->replaceAllUsesWith(
220      Builder.CreateCall(getOrInsertValueProfilingCall(*M), Args));
221  Ind->eraseFromParent();
222}
223
224void InstrProfiling::lowerIncrement(InstrProfIncrementInst *Inc) {
225  GlobalVariable *Counters = getOrCreateRegionCounters(Inc);
226
227  IRBuilder<> Builder(Inc);
228  uint64_t Index = Inc->getIndex()->getZExtValue();
229  Value *Addr = Builder.CreateConstInBoundsGEP2_64(Counters, 0, Index);
230  Value *Count = Builder.CreateLoad(Addr, "pgocount");
231  Count = Builder.CreateAdd(Count, Builder.getInt64(1));
232  Inc->replaceAllUsesWith(Builder.CreateStore(Count, Addr));
233  Inc->eraseFromParent();
234}
235
236void InstrProfiling::lowerCoverageData(GlobalVariable *CoverageData) {
237  CoverageData->setSection(getCoverageSection());
238  CoverageData->setAlignment(8);
239
240  Constant *Init = CoverageData->getInitializer();
241  // We're expecting { i32, i32, i32, i32, [n x { i8*, i32, i32 }], [m x i8] }
242  // for some C. If not, the frontend's given us something broken.
243  assert(Init->getNumOperands() == 6 && "bad number of fields in coverage map");
244  assert(isa<ConstantArray>(Init->getAggregateElement(4)) &&
245         "invalid function list in coverage map");
246  ConstantArray *Records = cast<ConstantArray>(Init->getAggregateElement(4));
247  for (unsigned I = 0, E = Records->getNumOperands(); I < E; ++I) {
248    Constant *Record = Records->getOperand(I);
249    Value *V = const_cast<Value *>(Record->getOperand(0))->stripPointerCasts();
250
251    assert(isa<GlobalVariable>(V) && "Missing reference to function name");
252    GlobalVariable *Name = cast<GlobalVariable>(V);
253
254    // If we have region counters for this name, we've already handled it.
255    auto It = ProfileDataMap.find(Name);
256    if (It != ProfileDataMap.end())
257      if (It->second.RegionCounters)
258        continue;
259
260    // Move the name variable to the right section.
261    Name->setSection(getNameSection());
262    Name->setAlignment(1);
263  }
264}
265
266/// Get the name of a profiling variable for a particular function.
267static std::string getVarName(InstrProfIncrementInst *Inc, StringRef Prefix) {
268  StringRef NamePrefix = getInstrProfNameVarPrefix();
269  StringRef Name = Inc->getName()->getName().substr(NamePrefix.size());
270  return (Prefix + Name).str();
271}
272
273static inline bool shouldRecordFunctionAddr(Function *F) {
274  // Check the linkage
275  if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage() &&
276      !F->hasAvailableExternallyLinkage())
277    return true;
278  // Check uses of this function for other than direct calls or invokes to it.
279  return F->hasAddressTaken();
280}
281
282static inline Comdat *getOrCreateProfileComdat(Module &M,
283                                               InstrProfIncrementInst *Inc) {
284  // COFF format requires a COMDAT section to have a key symbol with the same
285  // name. The linker targeting COFF also requires that the COMDAT section
286  // a section is associated to must precede the associating section. For this
287  // reason, we must choose the name var's name as the name of the comdat.
288  StringRef ComdatPrefix = (Triple(M.getTargetTriple()).isOSBinFormatCOFF()
289                                ? getInstrProfNameVarPrefix()
290                                : getInstrProfComdatPrefix());
291  return M.getOrInsertComdat(StringRef(getVarName(Inc, ComdatPrefix)));
292}
293
294GlobalVariable *
295InstrProfiling::getOrCreateRegionCounters(InstrProfIncrementInst *Inc) {
296  GlobalVariable *NamePtr = Inc->getName();
297  auto It = ProfileDataMap.find(NamePtr);
298  PerFunctionProfileData PD;
299  if (It != ProfileDataMap.end()) {
300    if (It->second.RegionCounters)
301      return It->second.RegionCounters;
302    PD = It->second;
303  }
304
305  // Move the name variable to the right section. Place them in a COMDAT group
306  // if the associated function is a COMDAT. This will make sure that
307  // only one copy of counters of the COMDAT function will be emitted after
308  // linking.
309  Function *Fn = Inc->getParent()->getParent();
310  Comdat *ProfileVarsComdat = nullptr;
311  if (Fn->hasComdat())
312    ProfileVarsComdat = getOrCreateProfileComdat(*M, Inc);
313  NamePtr->setSection(getNameSection());
314  NamePtr->setAlignment(1);
315  NamePtr->setComdat(ProfileVarsComdat);
316
317  uint64_t NumCounters = Inc->getNumCounters()->getZExtValue();
318  LLVMContext &Ctx = M->getContext();
319  ArrayType *CounterTy = ArrayType::get(Type::getInt64Ty(Ctx), NumCounters);
320
321  // Create the counters variable.
322  auto *CounterPtr =
323      new GlobalVariable(*M, CounterTy, false, NamePtr->getLinkage(),
324                         Constant::getNullValue(CounterTy),
325                         getVarName(Inc, getInstrProfCountersVarPrefix()));
326  CounterPtr->setVisibility(NamePtr->getVisibility());
327  CounterPtr->setSection(getCountersSection());
328  CounterPtr->setAlignment(8);
329  CounterPtr->setComdat(ProfileVarsComdat);
330
331  // Create data variable.
332  auto *Int8PtrTy = Type::getInt8PtrTy(Ctx);
333  auto *Int16Ty = Type::getInt16Ty(Ctx);
334  auto *Int16ArrayTy = ArrayType::get(Int16Ty, IPVK_Last+1);
335  Type *DataTypes[] = {
336    #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) LLVMType,
337    #include "llvm/ProfileData/InstrProfData.inc"
338  };
339  auto *DataTy = StructType::get(Ctx, makeArrayRef(DataTypes));
340
341  Constant *FunctionAddr = shouldRecordFunctionAddr(Fn) ?
342                           ConstantExpr::getBitCast(Fn, Int8PtrTy) :
343                           ConstantPointerNull::get(Int8PtrTy);
344
345  Constant *Int16ArrayVals[IPVK_Last+1];
346  for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
347    Int16ArrayVals[Kind] = ConstantInt::get(Int16Ty, PD.NumValueSites[Kind]);
348
349  Constant *DataVals[] = {
350    #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) Init,
351    #include "llvm/ProfileData/InstrProfData.inc"
352  };
353  auto *Data = new GlobalVariable(*M, DataTy, false, NamePtr->getLinkage(),
354                                  ConstantStruct::get(DataTy, DataVals),
355                                  getVarName(Inc, getInstrProfDataVarPrefix()));
356  Data->setVisibility(NamePtr->getVisibility());
357  Data->setSection(getDataSection());
358  Data->setAlignment(INSTR_PROF_DATA_ALIGNMENT);
359  Data->setComdat(ProfileVarsComdat);
360
361  PD.RegionCounters = CounterPtr;
362  PD.DataVar = Data;
363  ProfileDataMap[NamePtr] = PD;
364
365  // Mark the data variable as used so that it isn't stripped out.
366  UsedVars.push_back(Data);
367
368  return CounterPtr;
369}
370
371void InstrProfiling::emitRegistration() {
372  // Don't do this for Darwin.  compiler-rt uses linker magic.
373  if (Triple(M->getTargetTriple()).isOSDarwin())
374    return;
375
376  // Use linker script magic to get data/cnts/name start/end.
377  if (Triple(M->getTargetTriple()).isOSLinux() ||
378      Triple(M->getTargetTriple()).isOSFreeBSD())
379    return;
380
381  // Construct the function.
382  auto *VoidTy = Type::getVoidTy(M->getContext());
383  auto *VoidPtrTy = Type::getInt8PtrTy(M->getContext());
384  auto *RegisterFTy = FunctionType::get(VoidTy, false);
385  auto *RegisterF = Function::Create(RegisterFTy, GlobalValue::InternalLinkage,
386                                     getInstrProfRegFuncsName(), M);
387  RegisterF->setUnnamedAddr(true);
388  if (Options.NoRedZone) RegisterF->addFnAttr(Attribute::NoRedZone);
389
390  auto *RuntimeRegisterTy = FunctionType::get(VoidTy, VoidPtrTy, false);
391  auto *RuntimeRegisterF =
392      Function::Create(RuntimeRegisterTy, GlobalVariable::ExternalLinkage,
393                       getInstrProfRegFuncName(), M);
394
395  IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", RegisterF));
396  for (Value *Data : UsedVars)
397    IRB.CreateCall(RuntimeRegisterF, IRB.CreateBitCast(Data, VoidPtrTy));
398  IRB.CreateRetVoid();
399}
400
401void InstrProfiling::emitRuntimeHook() {
402
403  // We expect the linker to be invoked with -u<hook_var> flag for linux,
404  // for which case there is no need to emit the user function.
405  if (Triple(M->getTargetTriple()).isOSLinux())
406    return;
407
408  // If the module's provided its own runtime, we don't need to do anything.
409  if (M->getGlobalVariable(getInstrProfRuntimeHookVarName())) return;
410
411  // Declare an external variable that will pull in the runtime initialization.
412  auto *Int32Ty = Type::getInt32Ty(M->getContext());
413  auto *Var =
414      new GlobalVariable(*M, Int32Ty, false, GlobalValue::ExternalLinkage,
415                         nullptr, getInstrProfRuntimeHookVarName());
416
417  // Make a function that uses it.
418  auto *User = Function::Create(FunctionType::get(Int32Ty, false),
419                                GlobalValue::LinkOnceODRLinkage,
420                                getInstrProfRuntimeHookVarUseFuncName(), M);
421  User->addFnAttr(Attribute::NoInline);
422  if (Options.NoRedZone) User->addFnAttr(Attribute::NoRedZone);
423  User->setVisibility(GlobalValue::HiddenVisibility);
424
425  IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", User));
426  auto *Load = IRB.CreateLoad(Var);
427  IRB.CreateRet(Load);
428
429  // Mark the user variable as used so that it isn't stripped out.
430  UsedVars.push_back(User);
431}
432
433void InstrProfiling::emitUses() {
434  if (UsedVars.empty())
435    return;
436
437  GlobalVariable *LLVMUsed = M->getGlobalVariable("llvm.used");
438  std::vector<Constant *> MergedVars;
439  if (LLVMUsed) {
440    // Collect the existing members of llvm.used.
441    ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer());
442    for (unsigned I = 0, E = Inits->getNumOperands(); I != E; ++I)
443      MergedVars.push_back(Inits->getOperand(I));
444    LLVMUsed->eraseFromParent();
445  }
446
447  Type *i8PTy = Type::getInt8PtrTy(M->getContext());
448  // Add uses for our data.
449  for (auto *Value : UsedVars)
450    MergedVars.push_back(
451        ConstantExpr::getBitCast(cast<Constant>(Value), i8PTy));
452
453  // Recreate llvm.used.
454  ArrayType *ATy = ArrayType::get(i8PTy, MergedVars.size());
455  LLVMUsed =
456      new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage,
457                         ConstantArray::get(ATy, MergedVars), "llvm.used");
458  LLVMUsed->setSection("llvm.metadata");
459}
460
461void InstrProfiling::emitInitialization() {
462  std::string InstrProfileOutput = Options.InstrProfileOutput;
463
464  Constant *RegisterF = M->getFunction(getInstrProfRegFuncsName());
465  if (!RegisterF && InstrProfileOutput.empty()) return;
466
467  // Create the initialization function.
468  auto *VoidTy = Type::getVoidTy(M->getContext());
469  auto *F = Function::Create(FunctionType::get(VoidTy, false),
470                             GlobalValue::InternalLinkage,
471                             getInstrProfInitFuncName(), M);
472  F->setUnnamedAddr(true);
473  F->addFnAttr(Attribute::NoInline);
474  if (Options.NoRedZone) F->addFnAttr(Attribute::NoRedZone);
475
476  // Add the basic block and the necessary calls.
477  IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", F));
478  if (RegisterF)
479    IRB.CreateCall(RegisterF, {});
480  if (!InstrProfileOutput.empty()) {
481    auto *Int8PtrTy = Type::getInt8PtrTy(M->getContext());
482    auto *SetNameTy = FunctionType::get(VoidTy, Int8PtrTy, false);
483    auto *SetNameF = Function::Create(SetNameTy, GlobalValue::ExternalLinkage,
484                                      getInstrProfFileOverriderFuncName(), M);
485
486    // Create variable for profile name.
487    Constant *ProfileNameConst =
488        ConstantDataArray::getString(M->getContext(), InstrProfileOutput, true);
489    GlobalVariable *ProfileName =
490        new GlobalVariable(*M, ProfileNameConst->getType(), true,
491                           GlobalValue::PrivateLinkage, ProfileNameConst);
492
493    IRB.CreateCall(SetNameF, IRB.CreatePointerCast(ProfileName, Int8PtrTy));
494  }
495  IRB.CreateRetVoid();
496
497  appendToGlobalCtors(*M, F, 0);
498}
499