llvm/lib/Transforms/Instrumentation/InstrProfiling.cpp - toolchain/llvm-project - Gitiles

 //===-- InstrProfiling.cpp - Frontend instrumentation based profiling -----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass lowers instrprof_* intrinsics emitted by a frontend for profiling.
 // It also builds the data structures and initialization code needed for
 // updating execution counts and emitting the profile at runtime.
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/ADT/Triple.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Transforms/InstrProfiling.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"

 using namespace llvm;

 #define DEBUG_TYPE "instrprof"

 namespace {

 cl::opt<bool> DoNameCompression("enable-name-compression",
                                 cl::desc("Enable name string compression"),
                                 cl::init(true));

 class InstrProfilingLegacyPass : public ModulePass {
   InstrProfiling InstrProf;

 public:
   static char ID;
   InstrProfilingLegacyPass() : ModulePass(ID), InstrProf() {}
   InstrProfilingLegacyPass(const InstrProfOptions &Options)
       : ModulePass(ID), InstrProf(Options) {}
   const char *getPassName() const override {
     return "Frontend instrumentation-based coverage lowering";
   }

   bool runOnModule(Module &M) override { return InstrProf.run(M); }

   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
   }
 };

 } // anonymous namespace

 PreservedAnalyses InstrProfiling::run(Module &M, AnalysisManager<Module> &AM) {
   if (!run(M))
     return PreservedAnalyses::all();

   return PreservedAnalyses::none();
 }

 char InstrProfilingLegacyPass::ID = 0;
 INITIALIZE_PASS(InstrProfilingLegacyPass, "instrprof",
                 "Frontend instrumentation-based coverage lowering.", false,
                 false)

 ModulePass *llvm::createInstrProfilingLegacyPass(const InstrProfOptions &Options) {
   return new InstrProfilingLegacyPass(Options);
 }

 bool InstrProfiling::isMachO() const {
   return Triple(M->getTargetTriple()).isOSBinFormatMachO();
 }

 /// Get the section name for the counter variables.
 StringRef InstrProfiling::getCountersSection() const {
   return getInstrProfCountersSectionName(isMachO());
 }

 /// Get the section name for the name variables.
 StringRef InstrProfiling::getNameSection() const {
   return getInstrProfNameSectionName(isMachO());
 }

 /// Get the section name for the profile data variables.
 StringRef InstrProfiling::getDataSection() const {
   return getInstrProfDataSectionName(isMachO());
 }

 /// Get the section name for the coverage mapping data.
 StringRef InstrProfiling::getCoverageSection() const {
   return getInstrProfCoverageSectionName(isMachO());
 }

 bool InstrProfiling::run(Module &M) {
   bool MadeChange = false;

   this->M = &M;
   NamesVar = nullptr;
   NamesSize = 0;
   ProfileDataMap.clear();
   UsedVars.clear();

   // We did not know how many value sites there would be inside
   // the instrumented function. This is counting the number of instrumented
   // target value sites to enter it as field in the profile data variable.
   for (Function &F : M) {
     InstrProfIncrementInst *FirstProfIncInst = nullptr;
     for (BasicBlock &BB : F)
       for (auto I = BB.begin(), E = BB.end(); I != E; I++)
         if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(I))
           computeNumValueSiteCounts(Ind);
         else if (FirstProfIncInst == nullptr)
           FirstProfIncInst = dyn_cast<InstrProfIncrementInst>(I);

     // Value profiling intrinsic lowering requires per-function profile data
     // variable to be created first.
     if (FirstProfIncInst != nullptr)
       static_cast<void>(getOrCreateRegionCounters(FirstProfIncInst));
   }

   for (Function &F : M)
     for (BasicBlock &BB : F)
       for (auto I = BB.begin(), E = BB.end(); I != E;) {
         auto Instr = I++;
         if (auto *Inc = dyn_cast<InstrProfIncrementInst>(Instr)) {
           lowerIncrement(Inc);
           MadeChange = true;
         } else if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(Instr)) {
           lowerValueProfileInst(Ind);
           MadeChange = true;
         }
       }

   if (GlobalVariable *CoverageNamesVar =
           M.getNamedGlobal(getCoverageUnusedNamesVarName())) {
     lowerCoverageData(CoverageNamesVar);
     MadeChange = true;
   }

   if (!MadeChange)
     return false;

   emitNameData();
   emitRegistration();
   emitRuntimeHook();
   emitUses();
   emitInitialization();
   return true;
 }

 static Constant *getOrInsertValueProfilingCall(Module &M) {
   LLVMContext &Ctx = M.getContext();
   auto *ReturnTy = Type::getVoidTy(M.getContext());
   Type *ParamTypes[] = {
 #define VALUE_PROF_FUNC_PARAM(ParamType, ParamName, ParamLLVMType) ParamLLVMType
 #include "llvm/ProfileData/InstrProfData.inc"
   };
   auto *ValueProfilingCallTy =
       FunctionType::get(ReturnTy, makeArrayRef(ParamTypes), false);
   return M.getOrInsertFunction(getInstrProfValueProfFuncName(),
                                ValueProfilingCallTy);
 }

 void InstrProfiling::computeNumValueSiteCounts(InstrProfValueProfileInst *Ind) {

   GlobalVariable *Name = Ind->getName();
   uint64_t ValueKind = Ind->getValueKind()->getZExtValue();
   uint64_t Index = Ind->getIndex()->getZExtValue();
   auto It = ProfileDataMap.find(Name);
   if (It == ProfileDataMap.end()) {
     PerFunctionProfileData PD;
     PD.NumValueSites[ValueKind] = Index + 1;
     ProfileDataMap[Name] = PD;
   } else if (It->second.NumValueSites[ValueKind] <= Index)
     It->second.NumValueSites[ValueKind] = Index + 1;
 }

 void InstrProfiling::lowerValueProfileInst(InstrProfValueProfileInst *Ind) {

   GlobalVariable *Name = Ind->getName();
   auto It = ProfileDataMap.find(Name);
   assert(It != ProfileDataMap.end() && It->second.DataVar &&
     "value profiling detected in function with no counter incerement");

   GlobalVariable *DataVar = It->second.DataVar;
   uint64_t ValueKind = Ind->getValueKind()->getZExtValue();
   uint64_t Index = Ind->getIndex()->getZExtValue();
   for (uint32_t Kind = IPVK_First; Kind < ValueKind; ++Kind)
     Index += It->second.NumValueSites[Kind];

   IRBuilder<> Builder(Ind);
   Value* Args[3] = {Ind->getTargetValue(),
       Builder.CreateBitCast(DataVar, Builder.getInt8PtrTy()),
       Builder.getInt32(Index)};
   Ind->replaceAllUsesWith(
       Builder.CreateCall(getOrInsertValueProfilingCall(*M), Args));
   Ind->eraseFromParent();
 }

 void InstrProfiling::lowerIncrement(InstrProfIncrementInst *Inc) {
   GlobalVariable *Counters = getOrCreateRegionCounters(Inc);

   IRBuilder<> Builder(Inc);
   uint64_t Index = Inc->getIndex()->getZExtValue();
   Value *Addr = Builder.CreateConstInBoundsGEP2_64(Counters, 0, Index);
   Value *Count = Builder.CreateLoad(Addr, "pgocount");
   Count = Builder.CreateAdd(Count, Builder.getInt64(1));
   Inc->replaceAllUsesWith(Builder.CreateStore(Count, Addr));
   Inc->eraseFromParent();
 }

 void InstrProfiling::lowerCoverageData(GlobalVariable *CoverageNamesVar) {

   ConstantArray *Names =
       cast<ConstantArray>(CoverageNamesVar->getInitializer());
   for (unsigned I = 0, E = Names->getNumOperands(); I < E; ++I) {
     Constant *NC = Names->getOperand(I);
     Value *V = NC->stripPointerCasts();
     assert(isa<GlobalVariable>(V) && "Missing reference to function name");
     GlobalVariable *Name = cast<GlobalVariable>(V);

     Name->setLinkage(GlobalValue::PrivateLinkage);
     ReferencedNames.push_back(Name);
   }
 }

 /// Get the name of a profiling variable for a particular function.
 static std::string getVarName(InstrProfIncrementInst *Inc, StringRef Prefix) {
   StringRef NamePrefix = getInstrProfNameVarPrefix();
   StringRef Name = Inc->getName()->getName().substr(NamePrefix.size());
   return (Prefix + Name).str();
 }

 static inline bool shouldRecordFunctionAddr(Function *F) {
   // Check the linkage
   if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage() &&
       !F->hasAvailableExternallyLinkage())
     return true;
   // Prohibit function address recording if the function is both internal and
   // COMDAT. This avoids the profile data variable referencing internal symbols
   // in COMDAT.
   if (F->hasLocalLinkage() && F->hasComdat())
     return false;
   // Check uses of this function for other than direct calls or invokes to it.
   return F->hasAddressTaken();
 }

 static inline bool needsComdatForCounter(Function &F, Module &M) {

   if (F.hasComdat())
     return true;

   Triple TT(M.getTargetTriple());
   if (!TT.isOSBinFormatELF())
     return false;

   // See createPGOFuncNameVar for more details. To avoid link errors, profile
   // counters for function with available_externally linkage needs to be changed
   // to linkonce linkage. On ELF based systems, this leads to weak symbols to be
   // created. Without using comdat, duplicate entries won't be removed by the
   // linker leading to increased data segement size and raw profile size. Even
   // worse, since the referenced counter from profile per-function data object
   // will be resolved to the common strong definition, the profile counts for
   // available_externally functions will end up being duplicated in raw profile
   // data. This can result in distorted profile as the counts of those dups
   // will be accumulated by the profile merger.
   GlobalValue::LinkageTypes Linkage = F.getLinkage();
   if (Linkage != GlobalValue::ExternalWeakLinkage &&
       Linkage != GlobalValue::AvailableExternallyLinkage)
     return false;

   return true;
 }

 static inline Comdat *getOrCreateProfileComdat(Module &M, Function &F,
                                                InstrProfIncrementInst *Inc) {
   if (!needsComdatForCounter(F, M))
     return nullptr;

   // COFF format requires a COMDAT section to have a key symbol with the same
   // name. The linker targeting COFF also requires that the COMDAT
   // a section is associated to must precede the associating section. For this
   // reason, we must choose the counter var's name as the name of the comdat.
   StringRef ComdatPrefix = (Triple(M.getTargetTriple()).isOSBinFormatCOFF()
                                 ? getInstrProfCountersVarPrefix()
                                 : getInstrProfComdatPrefix());
   return M.getOrInsertComdat(StringRef(getVarName(Inc, ComdatPrefix)));
 }

 GlobalVariable *
 InstrProfiling::getOrCreateRegionCounters(InstrProfIncrementInst *Inc) {
   GlobalVariable *NamePtr = Inc->getName();
   auto It = ProfileDataMap.find(NamePtr);
   PerFunctionProfileData PD;
   if (It != ProfileDataMap.end()) {
     if (It->second.RegionCounters)
       return It->second.RegionCounters;
     PD = It->second;
   }

   // Move the name variable to the right section. Place them in a COMDAT group
   // if the associated function is a COMDAT. This will make sure that
   // only one copy of counters of the COMDAT function will be emitted after
   // linking.
   Function *Fn = Inc->getParent()->getParent();
   Comdat *ProfileVarsComdat = nullptr;
   ProfileVarsComdat = getOrCreateProfileComdat(*M, *Fn, Inc);

   uint64_t NumCounters = Inc->getNumCounters()->getZExtValue();
   LLVMContext &Ctx = M->getContext();
   ArrayType *CounterTy = ArrayType::get(Type::getInt64Ty(Ctx), NumCounters);

   // Create the counters variable.
   auto *CounterPtr =
       new GlobalVariable(*M, CounterTy, false, NamePtr->getLinkage(),
                          Constant::getNullValue(CounterTy),
                          getVarName(Inc, getInstrProfCountersVarPrefix()));
   CounterPtr->setVisibility(NamePtr->getVisibility());
   CounterPtr->setSection(getCountersSection());
   CounterPtr->setAlignment(8);
   CounterPtr->setComdat(ProfileVarsComdat);

   // Create data variable.
   auto *Int8PtrTy = Type::getInt8PtrTy(Ctx);
   auto *Int16Ty = Type::getInt16Ty(Ctx);
   auto *Int16ArrayTy = ArrayType::get(Int16Ty, IPVK_Last+1);
   Type *DataTypes[] = {
     #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) LLVMType,
     #include "llvm/ProfileData/InstrProfData.inc"
   };
   auto *DataTy = StructType::get(Ctx, makeArrayRef(DataTypes));

   Constant *FunctionAddr = shouldRecordFunctionAddr(Fn) ?
                            ConstantExpr::getBitCast(Fn, Int8PtrTy) :
                            ConstantPointerNull::get(Int8PtrTy);

   Constant *Int16ArrayVals[IPVK_Last+1];
   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
     Int16ArrayVals[Kind] = ConstantInt::get(Int16Ty, PD.NumValueSites[Kind]);

   Constant *DataVals[] = {
     #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) Init,
     #include "llvm/ProfileData/InstrProfData.inc"
   };
   auto *Data = new GlobalVariable(*M, DataTy, false, NamePtr->getLinkage(),
                                   ConstantStruct::get(DataTy, DataVals),
                                   getVarName(Inc, getInstrProfDataVarPrefix()));
   Data->setVisibility(NamePtr->getVisibility());
   Data->setSection(getDataSection());
   Data->setAlignment(INSTR_PROF_DATA_ALIGNMENT);
   Data->setComdat(ProfileVarsComdat);

   PD.RegionCounters = CounterPtr;
   PD.DataVar = Data;
   ProfileDataMap[NamePtr] = PD;

   // Mark the data variable as used so that it isn't stripped out.
   UsedVars.push_back(Data);
   // Now that the linkage set by the FE has been passed to the data and counter
   // variables, reset Name variable's linkage and visibility to private so that
   // it can be removed later by the compiler.
   NamePtr->setLinkage(GlobalValue::PrivateLinkage);
   // Collect the referenced names to be used by emitNameData.
   ReferencedNames.push_back(NamePtr);

   return CounterPtr;
 }

 void InstrProfiling::emitNameData() {
   std::string UncompressedData;

   if (ReferencedNames.empty())
     return;

   std::string CompressedNameStr;
   if (auto EC = collectPGOFuncNameStrings(ReferencedNames, CompressedNameStr,
                                           DoNameCompression)) {
     llvm::report_fatal_error(EC.message(), false);
   }

   auto &Ctx = M->getContext();
   auto *NamesVal = llvm::ConstantDataArray::getString(
       Ctx, StringRef(CompressedNameStr), false);
   NamesVar = new llvm::GlobalVariable(*M, NamesVal->getType(), true,
                                       llvm::GlobalValue::PrivateLinkage,
                                       NamesVal, getInstrProfNamesVarName());
   NamesSize = CompressedNameStr.size();
   NamesVar->setSection(getNameSection());
   UsedVars.push_back(NamesVar);
 }

 void InstrProfiling::emitRegistration() {
   // Don't do this for Darwin.  compiler-rt uses linker magic.
   if (Triple(M->getTargetTriple()).isOSDarwin())
     return;

   // Use linker script magic to get data/cnts/name start/end.
   if (Triple(M->getTargetTriple()).isOSLinux() ||
       Triple(M->getTargetTriple()).isOSFreeBSD() ||
       Triple(M->getTargetTriple()).isPS4CPU())
     return;

   // Construct the function.
   auto *VoidTy = Type::getVoidTy(M->getContext());
   auto *VoidPtrTy = Type::getInt8PtrTy(M->getContext());
   auto *Int64Ty = Type::getInt64Ty(M->getContext());
   auto *RegisterFTy = FunctionType::get(VoidTy, false);
   auto *RegisterF = Function::Create(RegisterFTy, GlobalValue::InternalLinkage,
                                      getInstrProfRegFuncsName(), M);
   RegisterF->setUnnamedAddr(true);
   if (Options.NoRedZone) RegisterF->addFnAttr(Attribute::NoRedZone);

   auto *RuntimeRegisterTy = FunctionType::get(VoidTy, VoidPtrTy, false);
   auto *RuntimeRegisterF =
       Function::Create(RuntimeRegisterTy, GlobalVariable::ExternalLinkage,
                        getInstrProfRegFuncName(), M);

   IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", RegisterF));
   for (Value *Data : UsedVars)
     if (Data != NamesVar)
       IRB.CreateCall(RuntimeRegisterF, IRB.CreateBitCast(Data, VoidPtrTy));

   if (NamesVar) {
     Type *ParamTypes[] = {VoidPtrTy, Int64Ty};
     auto *NamesRegisterTy =
         FunctionType::get(VoidTy, makeArrayRef(ParamTypes), false);
     auto *NamesRegisterF =
         Function::Create(NamesRegisterTy, GlobalVariable::ExternalLinkage,
                          getInstrProfNamesRegFuncName(), M);
     IRB.CreateCall(NamesRegisterF, {IRB.CreateBitCast(NamesVar, VoidPtrTy),
                                     IRB.getInt64(NamesSize)});
   }

   IRB.CreateRetVoid();
 }

 void InstrProfiling::emitRuntimeHook() {

   // We expect the linker to be invoked with -u<hook_var> flag for linux,
   // for which case there is no need to emit the user function.
   if (Triple(M->getTargetTriple()).isOSLinux())
     return;

   // If the module's provided its own runtime, we don't need to do anything.
   if (M->getGlobalVariable(getInstrProfRuntimeHookVarName())) return;

   // Declare an external variable that will pull in the runtime initialization.
   auto *Int32Ty = Type::getInt32Ty(M->getContext());
   auto *Var =
       new GlobalVariable(*M, Int32Ty, false, GlobalValue::ExternalLinkage,
                          nullptr, getInstrProfRuntimeHookVarName());

   // Make a function that uses it.
   auto *User = Function::Create(FunctionType::get(Int32Ty, false),
                                 GlobalValue::LinkOnceODRLinkage,
                                 getInstrProfRuntimeHookVarUseFuncName(), M);
   User->addFnAttr(Attribute::NoInline);
   if (Options.NoRedZone) User->addFnAttr(Attribute::NoRedZone);
   User->setVisibility(GlobalValue::HiddenVisibility);

   IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", User));
   auto *Load = IRB.CreateLoad(Var);
   IRB.CreateRet(Load);

   // Mark the user variable as used so that it isn't stripped out.
   UsedVars.push_back(User);
 }

 void InstrProfiling::emitUses() {
   if (UsedVars.empty())
     return;

   GlobalVariable *LLVMUsed = M->getGlobalVariable("llvm.used");
   std::vector<Constant *> MergedVars;
   if (LLVMUsed) {
     // Collect the existing members of llvm.used.
     ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer());
     for (unsigned I = 0, E = Inits->getNumOperands(); I != E; ++I)
       MergedVars.push_back(Inits->getOperand(I));
     LLVMUsed->eraseFromParent();
   }

   Type *i8PTy = Type::getInt8PtrTy(M->getContext());
   // Add uses for our data.
   for (auto *Value : UsedVars)
     MergedVars.push_back(
         ConstantExpr::getBitCast(cast<Constant>(Value), i8PTy));

   // Recreate llvm.used.
   ArrayType *ATy = ArrayType::get(i8PTy, MergedVars.size());
   LLVMUsed =
       new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage,
                          ConstantArray::get(ATy, MergedVars), "llvm.used");
   LLVMUsed->setSection("llvm.metadata");
 }

 void InstrProfiling::emitInitialization() {
   std::string InstrProfileOutput = Options.InstrProfileOutput;

   Constant *RegisterF = M->getFunction(getInstrProfRegFuncsName());
   if (!RegisterF && InstrProfileOutput.empty()) return;

   // Create the initialization function.
   auto *VoidTy = Type::getVoidTy(M->getContext());
   auto *F = Function::Create(FunctionType::get(VoidTy, false),
                              GlobalValue::InternalLinkage,
                              getInstrProfInitFuncName(), M);
   F->setUnnamedAddr(true);
   F->addFnAttr(Attribute::NoInline);
   if (Options.NoRedZone) F->addFnAttr(Attribute::NoRedZone);

   // Add the basic block and the necessary calls.
   IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", F));
   if (RegisterF)
     IRB.CreateCall(RegisterF, {});
   if (!InstrProfileOutput.empty()) {
     auto *Int8PtrTy = Type::getInt8PtrTy(M->getContext());
     auto *SetNameTy = FunctionType::get(VoidTy, Int8PtrTy, false);
     auto *SetNameF = Function::Create(SetNameTy, GlobalValue::ExternalLinkage,
                                       getInstrProfFileOverriderFuncName(), M);

     // Create variable for profile name.
     Constant *ProfileNameConst =
         ConstantDataArray::getString(M->getContext(), InstrProfileOutput, true);
     GlobalVariable *ProfileName =
         new GlobalVariable(*M, ProfileNameConst->getType(), true,
                            GlobalValue::PrivateLinkage, ProfileNameConst);

     IRB.CreateCall(SetNameF, IRB.CreatePointerCast(ProfileName, Int8PtrTy));
   }
   IRB.CreateRetVoid();

   appendToGlobalCtors(*M, F, 0);
 }
	//===-- InstrProfiling.cpp - Frontend instrumentation based profiling -----===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// This pass lowers instrprof_* intrinsics emitted by a frontend for profiling.
	// It also builds the data structures and initialization code needed for
	// updating execution counts and emitting the profile at runtime.
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/ADT/Triple.h"
	#include "llvm/IR/IRBuilder.h"
	#include "llvm/IR/IntrinsicInst.h"
	#include "llvm/IR/Module.h"
	#include "llvm/ProfileData/InstrProf.h"
	#include "llvm/Transforms/InstrProfiling.h"
	#include "llvm/Transforms/Utils/ModuleUtils.h"

	using namespace llvm;

	#define DEBUG_TYPE "instrprof"

	namespace {

	cl::opt<bool> DoNameCompression("enable-name-compression",
	cl::desc("Enable name string compression"),
	cl::init(true));

	class InstrProfilingLegacyPass : public ModulePass {
	InstrProfiling InstrProf;

	public:
	static char ID;
	InstrProfilingLegacyPass() : ModulePass(ID), InstrProf() {}
	InstrProfilingLegacyPass(const InstrProfOptions &Options)
	: ModulePass(ID), InstrProf(Options) {}
	const char *getPassName() const override {
	return "Frontend instrumentation-based coverage lowering";
	}

	bool runOnModule(Module &M) override { return InstrProf.run(M); }

	void getAnalysisUsage(AnalysisUsage &AU) const override {
	AU.setPreservesCFG();
	}
	};

	} // anonymous namespace

	PreservedAnalyses InstrProfiling::run(Module &M, AnalysisManager<Module> &AM) {
	if (!run(M))
	return PreservedAnalyses::all();

	return PreservedAnalyses::none();
	}

	char InstrProfilingLegacyPass::ID = 0;
	INITIALIZE_PASS(InstrProfilingLegacyPass, "instrprof",
	"Frontend instrumentation-based coverage lowering.", false,
	false)

	ModulePass *llvm::createInstrProfilingLegacyPass(const InstrProfOptions &Options) {
	return new InstrProfilingLegacyPass(Options);
	}

	bool InstrProfiling::isMachO() const {
	return Triple(M->getTargetTriple()).isOSBinFormatMachO();
	}

	/// Get the section name for the counter variables.
	StringRef InstrProfiling::getCountersSection() const {
	return getInstrProfCountersSectionName(isMachO());
	}

	/// Get the section name for the name variables.
	StringRef InstrProfiling::getNameSection() const {
	return getInstrProfNameSectionName(isMachO());
	}

	/// Get the section name for the profile data variables.
	StringRef InstrProfiling::getDataSection() const {
	return getInstrProfDataSectionName(isMachO());
	}

	/// Get the section name for the coverage mapping data.
	StringRef InstrProfiling::getCoverageSection() const {
	return getInstrProfCoverageSectionName(isMachO());
	}

	bool InstrProfiling::run(Module &M) {
	bool MadeChange = false;

	this->M = &M;
	NamesVar = nullptr;
	NamesSize = 0;
	ProfileDataMap.clear();
	UsedVars.clear();

	// We did not know how many value sites there would be inside
	// the instrumented function. This is counting the number of instrumented
	// target value sites to enter it as field in the profile data variable.
	for (Function &F : M) {
	InstrProfIncrementInst *FirstProfIncInst = nullptr;
	for (BasicBlock &BB : F)
	for (auto I = BB.begin(), E = BB.end(); I != E; I++)
	if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(I))
	computeNumValueSiteCounts(Ind);
	else if (FirstProfIncInst == nullptr)
	FirstProfIncInst = dyn_cast<InstrProfIncrementInst>(I);

	// Value profiling intrinsic lowering requires per-function profile data
	// variable to be created first.
	if (FirstProfIncInst != nullptr)
	static_cast<void>(getOrCreateRegionCounters(FirstProfIncInst));
	}

	for (Function &F : M)
	for (BasicBlock &BB : F)
	for (auto I = BB.begin(), E = BB.end(); I != E;) {
	auto Instr = I++;
	if (auto *Inc = dyn_cast<InstrProfIncrementInst>(Instr)) {
	lowerIncrement(Inc);
	MadeChange = true;
	} else if (auto *Ind = dyn_cast<InstrProfValueProfileInst>(Instr)) {
	lowerValueProfileInst(Ind);
	MadeChange = true;
	}
	}

	if (GlobalVariable *CoverageNamesVar =
	M.getNamedGlobal(getCoverageUnusedNamesVarName())) {
	lowerCoverageData(CoverageNamesVar);
	MadeChange = true;
	}

	if (!MadeChange)
	return false;

	emitNameData();
	emitRegistration();
	emitRuntimeHook();
	emitUses();
	emitInitialization();
	return true;
	}

	static Constant *getOrInsertValueProfilingCall(Module &M) {
	LLVMContext &Ctx = M.getContext();
	auto *ReturnTy = Type::getVoidTy(M.getContext());
	Type *ParamTypes[] = {
	#define VALUE_PROF_FUNC_PARAM(ParamType, ParamName, ParamLLVMType) ParamLLVMType
	#include "llvm/ProfileData/InstrProfData.inc"
	};
	auto *ValueProfilingCallTy =
	FunctionType::get(ReturnTy, makeArrayRef(ParamTypes), false);
	return M.getOrInsertFunction(getInstrProfValueProfFuncName(),
	ValueProfilingCallTy);
	}

	void InstrProfiling::computeNumValueSiteCounts(InstrProfValueProfileInst *Ind) {

	GlobalVariable *Name = Ind->getName();
	uint64_t ValueKind = Ind->getValueKind()->getZExtValue();
	uint64_t Index = Ind->getIndex()->getZExtValue();
	auto It = ProfileDataMap.find(Name);
	if (It == ProfileDataMap.end()) {
	PerFunctionProfileData PD;
	PD.NumValueSites[ValueKind] = Index + 1;
	ProfileDataMap[Name] = PD;
	} else if (It->second.NumValueSites[ValueKind] <= Index)
	It->second.NumValueSites[ValueKind] = Index + 1;
	}

	void InstrProfiling::lowerValueProfileInst(InstrProfValueProfileInst *Ind) {

	GlobalVariable *Name = Ind->getName();
	auto It = ProfileDataMap.find(Name);
	assert(It != ProfileDataMap.end() && It->second.DataVar &&
	"value profiling detected in function with no counter incerement");

	GlobalVariable *DataVar = It->second.DataVar;
	uint64_t ValueKind = Ind->getValueKind()->getZExtValue();
	uint64_t Index = Ind->getIndex()->getZExtValue();
	for (uint32_t Kind = IPVK_First; Kind < ValueKind; ++Kind)
	Index += It->second.NumValueSites[Kind];

	IRBuilder<> Builder(Ind);
	Value* Args[3] = {Ind->getTargetValue(),
	Builder.CreateBitCast(DataVar, Builder.getInt8PtrTy()),
	Builder.getInt32(Index)};
	Ind->replaceAllUsesWith(
	Builder.CreateCall(getOrInsertValueProfilingCall(*M), Args));
	Ind->eraseFromParent();
	}

	void InstrProfiling::lowerIncrement(InstrProfIncrementInst *Inc) {
	GlobalVariable *Counters = getOrCreateRegionCounters(Inc);

	IRBuilder<> Builder(Inc);
	uint64_t Index = Inc->getIndex()->getZExtValue();
	Value *Addr = Builder.CreateConstInBoundsGEP2_64(Counters, 0, Index);
	Value *Count = Builder.CreateLoad(Addr, "pgocount");
	Count = Builder.CreateAdd(Count, Builder.getInt64(1));
	Inc->replaceAllUsesWith(Builder.CreateStore(Count, Addr));
	Inc->eraseFromParent();
	}

	void InstrProfiling::lowerCoverageData(GlobalVariable *CoverageNamesVar) {

	ConstantArray *Names =
	cast<ConstantArray>(CoverageNamesVar->getInitializer());
	for (unsigned I = 0, E = Names->getNumOperands(); I < E; ++I) {
	Constant *NC = Names->getOperand(I);
	Value *V = NC->stripPointerCasts();
	assert(isa<GlobalVariable>(V) && "Missing reference to function name");
	GlobalVariable *Name = cast<GlobalVariable>(V);

	Name->setLinkage(GlobalValue::PrivateLinkage);
	ReferencedNames.push_back(Name);
	}
	}

	/// Get the name of a profiling variable for a particular function.
	static std::string getVarName(InstrProfIncrementInst *Inc, StringRef Prefix) {
	StringRef NamePrefix = getInstrProfNameVarPrefix();
	StringRef Name = Inc->getName()->getName().substr(NamePrefix.size());
	return (Prefix + Name).str();
	}

	static inline bool shouldRecordFunctionAddr(Function *F) {
	// Check the linkage
	if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage() &&
	!F->hasAvailableExternallyLinkage())
	return true;
	// Prohibit function address recording if the function is both internal and
	// COMDAT. This avoids the profile data variable referencing internal symbols
	// in COMDAT.
	if (F->hasLocalLinkage() && F->hasComdat())
	return false;
	// Check uses of this function for other than direct calls or invokes to it.
	return F->hasAddressTaken();
	}

	static inline bool needsComdatForCounter(Function &F, Module &M) {

	if (F.hasComdat())
	return true;

	Triple TT(M.getTargetTriple());
	if (!TT.isOSBinFormatELF())
	return false;

	// See createPGOFuncNameVar for more details. To avoid link errors, profile
	// counters for function with available_externally linkage needs to be changed
	// to linkonce linkage. On ELF based systems, this leads to weak symbols to be
	// created. Without using comdat, duplicate entries won't be removed by the
	// linker leading to increased data segement size and raw profile size. Even
	// worse, since the referenced counter from profile per-function data object
	// will be resolved to the common strong definition, the profile counts for
	// available_externally functions will end up being duplicated in raw profile
	// data. This can result in distorted profile as the counts of those dups
	// will be accumulated by the profile merger.
	GlobalValue::LinkageTypes Linkage = F.getLinkage();
	if (Linkage != GlobalValue::ExternalWeakLinkage &&
	Linkage != GlobalValue::AvailableExternallyLinkage)
	return false;

	return true;
	}

	static inline Comdat *getOrCreateProfileComdat(Module &M, Function &F,
	InstrProfIncrementInst *Inc) {
	if (!needsComdatForCounter(F, M))
	return nullptr;

	// COFF format requires a COMDAT section to have a key symbol with the same
	// name. The linker targeting COFF also requires that the COMDAT
	// a section is associated to must precede the associating section. For this
	// reason, we must choose the counter var's name as the name of the comdat.
	StringRef ComdatPrefix = (Triple(M.getTargetTriple()).isOSBinFormatCOFF()
	? getInstrProfCountersVarPrefix()
	: getInstrProfComdatPrefix());
	return M.getOrInsertComdat(StringRef(getVarName(Inc, ComdatPrefix)));
	}

	GlobalVariable *
	InstrProfiling::getOrCreateRegionCounters(InstrProfIncrementInst *Inc) {
	GlobalVariable *NamePtr = Inc->getName();
	auto It = ProfileDataMap.find(NamePtr);
	PerFunctionProfileData PD;
	if (It != ProfileDataMap.end()) {
	if (It->second.RegionCounters)
	return It->second.RegionCounters;
	PD = It->second;
	}

	// Move the name variable to the right section. Place them in a COMDAT group
	// if the associated function is a COMDAT. This will make sure that
	// only one copy of counters of the COMDAT function will be emitted after
	// linking.
	Function *Fn = Inc->getParent()->getParent();
	Comdat *ProfileVarsComdat = nullptr;
	ProfileVarsComdat = getOrCreateProfileComdat(M, Fn, Inc);

	uint64_t NumCounters = Inc->getNumCounters()->getZExtValue();
	LLVMContext &Ctx = M->getContext();
	ArrayType *CounterTy = ArrayType::get(Type::getInt64Ty(Ctx), NumCounters);

	// Create the counters variable.
	auto *CounterPtr =
	new GlobalVariable(*M, CounterTy, false, NamePtr->getLinkage(),
	Constant::getNullValue(CounterTy),
	getVarName(Inc, getInstrProfCountersVarPrefix()));
	CounterPtr->setVisibility(NamePtr->getVisibility());
	CounterPtr->setSection(getCountersSection());
	CounterPtr->setAlignment(8);
	CounterPtr->setComdat(ProfileVarsComdat);

	// Create data variable.
	auto *Int8PtrTy = Type::getInt8PtrTy(Ctx);
	auto *Int16Ty = Type::getInt16Ty(Ctx);
	auto *Int16ArrayTy = ArrayType::get(Int16Ty, IPVK_Last+1);
	Type *DataTypes[] = {
	#define INSTR_PROF_DATA(Type, LLVMType, Name, Init) LLVMType,
	#include "llvm/ProfileData/InstrProfData.inc"
	};
	auto *DataTy = StructType::get(Ctx, makeArrayRef(DataTypes));

	Constant *FunctionAddr = shouldRecordFunctionAddr(Fn) ?
	ConstantExpr::getBitCast(Fn, Int8PtrTy) :
	ConstantPointerNull::get(Int8PtrTy);

	Constant *Int16ArrayVals[IPVK_Last+1];
	for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
	Int16ArrayVals[Kind] = ConstantInt::get(Int16Ty, PD.NumValueSites[Kind]);

	Constant *DataVals[] = {
	#define INSTR_PROF_DATA(Type, LLVMType, Name, Init) Init,
	#include "llvm/ProfileData/InstrProfData.inc"
	};
	auto Data = new GlobalVariable(M, DataTy, false, NamePtr->getLinkage(),
	ConstantStruct::get(DataTy, DataVals),
	getVarName(Inc, getInstrProfDataVarPrefix()));
	Data->setVisibility(NamePtr->getVisibility());
	Data->setSection(getDataSection());
	Data->setAlignment(INSTR_PROF_DATA_ALIGNMENT);
	Data->setComdat(ProfileVarsComdat);

	PD.RegionCounters = CounterPtr;
	PD.DataVar = Data;
	ProfileDataMap[NamePtr] = PD;

	// Mark the data variable as used so that it isn't stripped out.
	UsedVars.push_back(Data);
	// Now that the linkage set by the FE has been passed to the data and counter
	// variables, reset Name variable's linkage and visibility to private so that
	// it can be removed later by the compiler.
	NamePtr->setLinkage(GlobalValue::PrivateLinkage);
	// Collect the referenced names to be used by emitNameData.
	ReferencedNames.push_back(NamePtr);

	return CounterPtr;
	}

	void InstrProfiling::emitNameData() {
	std::string UncompressedData;

	if (ReferencedNames.empty())
	return;

	std::string CompressedNameStr;
	if (auto EC = collectPGOFuncNameStrings(ReferencedNames, CompressedNameStr,
	DoNameCompression)) {
	llvm::report_fatal_error(EC.message(), false);
	}

	auto &Ctx = M->getContext();
	auto *NamesVal = llvm::ConstantDataArray::getString(
	Ctx, StringRef(CompressedNameStr), false);
	NamesVar = new llvm::GlobalVariable(*M, NamesVal->getType(), true,
	llvm::GlobalValue::PrivateLinkage,
	NamesVal, getInstrProfNamesVarName());
	NamesSize = CompressedNameStr.size();
	NamesVar->setSection(getNameSection());
	UsedVars.push_back(NamesVar);
	}

	void InstrProfiling::emitRegistration() {
	// Don't do this for Darwin. compiler-rt uses linker magic.
	if (Triple(M->getTargetTriple()).isOSDarwin())
	return;

	// Use linker script magic to get data/cnts/name start/end.
	if (Triple(M->getTargetTriple()).isOSLinux() \|\|
	Triple(M->getTargetTriple()).isOSFreeBSD() \|\|
	Triple(M->getTargetTriple()).isPS4CPU())
	return;

	// Construct the function.
	auto *VoidTy = Type::getVoidTy(M->getContext());
	auto *VoidPtrTy = Type::getInt8PtrTy(M->getContext());
	auto *Int64Ty = Type::getInt64Ty(M->getContext());
	auto *RegisterFTy = FunctionType::get(VoidTy, false);
	auto *RegisterF = Function::Create(RegisterFTy, GlobalValue::InternalLinkage,
	getInstrProfRegFuncsName(), M);
	RegisterF->setUnnamedAddr(true);
	if (Options.NoRedZone) RegisterF->addFnAttr(Attribute::NoRedZone);

	auto *RuntimeRegisterTy = FunctionType::get(VoidTy, VoidPtrTy, false);
	auto *RuntimeRegisterF =
	Function::Create(RuntimeRegisterTy, GlobalVariable::ExternalLinkage,
	getInstrProfRegFuncName(), M);

	IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", RegisterF));
	for (Value *Data : UsedVars)
	if (Data != NamesVar)
	IRB.CreateCall(RuntimeRegisterF, IRB.CreateBitCast(Data, VoidPtrTy));

	if (NamesVar) {
	Type *ParamTypes[] = {VoidPtrTy, Int64Ty};
	auto *NamesRegisterTy =
	FunctionType::get(VoidTy, makeArrayRef(ParamTypes), false);
	auto *NamesRegisterF =
	Function::Create(NamesRegisterTy, GlobalVariable::ExternalLinkage,
	getInstrProfNamesRegFuncName(), M);
	IRB.CreateCall(NamesRegisterF, {IRB.CreateBitCast(NamesVar, VoidPtrTy),
	IRB.getInt64(NamesSize)});
	}

	IRB.CreateRetVoid();
	}

	void InstrProfiling::emitRuntimeHook() {

	// We expect the linker to be invoked with -u<hook_var> flag for linux,
	// for which case there is no need to emit the user function.
	if (Triple(M->getTargetTriple()).isOSLinux())
	return;

	// If the module's provided its own runtime, we don't need to do anything.
	if (M->getGlobalVariable(getInstrProfRuntimeHookVarName())) return;

	// Declare an external variable that will pull in the runtime initialization.
	auto *Int32Ty = Type::getInt32Ty(M->getContext());
	auto *Var =
	new GlobalVariable(*M, Int32Ty, false, GlobalValue::ExternalLinkage,
	nullptr, getInstrProfRuntimeHookVarName());

	// Make a function that uses it.
	auto *User = Function::Create(FunctionType::get(Int32Ty, false),
	GlobalValue::LinkOnceODRLinkage,
	getInstrProfRuntimeHookVarUseFuncName(), M);
	User->addFnAttr(Attribute::NoInline);
	if (Options.NoRedZone) User->addFnAttr(Attribute::NoRedZone);
	User->setVisibility(GlobalValue::HiddenVisibility);

	IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", User));
	auto *Load = IRB.CreateLoad(Var);
	IRB.CreateRet(Load);

	// Mark the user variable as used so that it isn't stripped out.
	UsedVars.push_back(User);
	}

	void InstrProfiling::emitUses() {
	if (UsedVars.empty())
	return;

	GlobalVariable *LLVMUsed = M->getGlobalVariable("llvm.used");
	std::vector<Constant *> MergedVars;
	if (LLVMUsed) {
	// Collect the existing members of llvm.used.
	ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer());
	for (unsigned I = 0, E = Inits->getNumOperands(); I != E; ++I)
	MergedVars.push_back(Inits->getOperand(I));
	LLVMUsed->eraseFromParent();
	}

	Type *i8PTy = Type::getInt8PtrTy(M->getContext());
	// Add uses for our data.
	for (auto *Value : UsedVars)
	MergedVars.push_back(
	ConstantExpr::getBitCast(cast<Constant>(Value), i8PTy));

	// Recreate llvm.used.
	ArrayType *ATy = ArrayType::get(i8PTy, MergedVars.size());
	LLVMUsed =
	new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage,
	ConstantArray::get(ATy, MergedVars), "llvm.used");
	LLVMUsed->setSection("llvm.metadata");
	}

	void InstrProfiling::emitInitialization() {
	std::string InstrProfileOutput = Options.InstrProfileOutput;

	Constant *RegisterF = M->getFunction(getInstrProfRegFuncsName());
	if (!RegisterF && InstrProfileOutput.empty()) return;

	// Create the initialization function.
	auto *VoidTy = Type::getVoidTy(M->getContext());
	auto *F = Function::Create(FunctionType::get(VoidTy, false),
	GlobalValue::InternalLinkage,
	getInstrProfInitFuncName(), M);
	F->setUnnamedAddr(true);
	F->addFnAttr(Attribute::NoInline);
	if (Options.NoRedZone) F->addFnAttr(Attribute::NoRedZone);

	// Add the basic block and the necessary calls.
	IRBuilder<> IRB(BasicBlock::Create(M->getContext(), "", F));
	if (RegisterF)
	IRB.CreateCall(RegisterF, {});
	if (!InstrProfileOutput.empty()) {
	auto *Int8PtrTy = Type::getInt8PtrTy(M->getContext());
	auto *SetNameTy = FunctionType::get(VoidTy, Int8PtrTy, false);
	auto *SetNameF = Function::Create(SetNameTy, GlobalValue::ExternalLinkage,
	getInstrProfFileOverriderFuncName(), M);

	// Create variable for profile name.
	Constant *ProfileNameConst =
	ConstantDataArray::getString(M->getContext(), InstrProfileOutput, true);
	GlobalVariable *ProfileName =
	new GlobalVariable(*M, ProfileNameConst->getType(), true,
	GlobalValue::PrivateLinkage, ProfileNameConst);

	IRB.CreateCall(SetNameF, IRB.CreatePointerCast(ProfileName, Int8PtrTy));
	}
	IRB.CreateRetVoid();

	appendToGlobalCtors(*M, F, 0);
	}