1 //===- MemProfiler.cpp - memory allocation and access profiler ------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file is a part of MemProfiler. Memory accesses are instrumented
10 // to increment the access count held in a shadow memory location, or
11 // alternatively to call into the runtime. Memory intrinsic calls (memmove,
12 // memcpy, memset) are changed to call the memory profiling runtime version
13 // instead.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/Transforms/Instrumentation/MemProfiler.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/ADT/Triple.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/IR/Constant.h"
24 #include "llvm/IR/DataLayout.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/IR/GlobalValue.h"
27 #include "llvm/IR/IRBuilder.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/IntrinsicInst.h"
30 #include "llvm/IR/Module.h"
31 #include "llvm/IR/Type.h"
32 #include "llvm/IR/Value.h"
33 #include "llvm/InitializePasses.h"
34 #include "llvm/Pass.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
38 #include "llvm/Transforms/Utils/ModuleUtils.h"
39 
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "memprof"
43 
44 constexpr int LLVM_MEM_PROFILER_VERSION = 1;
45 
46 // Size of memory mapped to a single shadow location.
47 constexpr uint64_t DefaultShadowGranularity = 64;
48 
49 // Scale from granularity down to shadow size.
50 constexpr uint64_t DefaultShadowScale = 3;
51 
52 constexpr char MemProfModuleCtorName[] = "memprof.module_ctor";
53 constexpr uint64_t MemProfCtorAndDtorPriority = 1;
54 // On Emscripten, the system needs more than one priorities for constructors.
55 constexpr uint64_t MemProfEmscriptenCtorAndDtorPriority = 50;
56 constexpr char MemProfInitName[] = "__memprof_init";
57 constexpr char MemProfVersionCheckNamePrefix[] =
58     "__memprof_version_mismatch_check_v";
59 
60 constexpr char MemProfShadowMemoryDynamicAddress[] =
61     "__memprof_shadow_memory_dynamic_address";
62 
63 constexpr char MemProfFilenameVar[] = "__memprof_profile_filename";
64 
65 // Command-line flags.
66 
67 static cl::opt<bool> ClInsertVersionCheck(
68     "memprof-guard-against-version-mismatch",
69     cl::desc("Guard against compiler/runtime version mismatch."), cl::Hidden,
70     cl::init(true));
71 
72 // This flag may need to be replaced with -f[no-]memprof-reads.
73 static cl::opt<bool> ClInstrumentReads("memprof-instrument-reads",
74                                        cl::desc("instrument read instructions"),
75                                        cl::Hidden, cl::init(true));
76 
77 static cl::opt<bool>
78     ClInstrumentWrites("memprof-instrument-writes",
79                        cl::desc("instrument write instructions"), cl::Hidden,
80                        cl::init(true));
81 
82 static cl::opt<bool> ClInstrumentAtomics(
83     "memprof-instrument-atomics",
84     cl::desc("instrument atomic instructions (rmw, cmpxchg)"), cl::Hidden,
85     cl::init(true));
86 
87 static cl::opt<bool> ClUseCalls(
88     "memprof-use-callbacks",
89     cl::desc("Use callbacks instead of inline instrumentation sequences."),
90     cl::Hidden, cl::init(false));
91 
92 static cl::opt<std::string>
93     ClMemoryAccessCallbackPrefix("memprof-memory-access-callback-prefix",
94                                  cl::desc("Prefix for memory access callbacks"),
95                                  cl::Hidden, cl::init("__memprof_"));
96 
97 // These flags allow to change the shadow mapping.
98 // The shadow mapping looks like
99 //    Shadow = ((Mem & mask) >> scale) + offset
100 
101 static cl::opt<int> ClMappingScale("memprof-mapping-scale",
102                                    cl::desc("scale of memprof shadow mapping"),
103                                    cl::Hidden, cl::init(DefaultShadowScale));
104 
105 static cl::opt<int>
106     ClMappingGranularity("memprof-mapping-granularity",
107                          cl::desc("granularity of memprof shadow mapping"),
108                          cl::Hidden, cl::init(DefaultShadowGranularity));
109 
110 static cl::opt<bool> ClStack("memprof-instrument-stack",
111                              cl::desc("Instrument scalar stack variables"),
112                              cl::Hidden, cl::init(false));
113 
114 // Debug flags.
115 
116 static cl::opt<int> ClDebug("memprof-debug", cl::desc("debug"), cl::Hidden,
117                             cl::init(0));
118 
119 static cl::opt<std::string> ClDebugFunc("memprof-debug-func", cl::Hidden,
120                                         cl::desc("Debug func"));
121 
122 static cl::opt<int> ClDebugMin("memprof-debug-min", cl::desc("Debug min inst"),
123                                cl::Hidden, cl::init(-1));
124 
125 static cl::opt<int> ClDebugMax("memprof-debug-max", cl::desc("Debug max inst"),
126                                cl::Hidden, cl::init(-1));
127 
128 STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
129 STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
130 STATISTIC(NumSkippedStackReads, "Number of non-instrumented stack reads");
131 STATISTIC(NumSkippedStackWrites, "Number of non-instrumented stack writes");
132 
133 namespace {
134 
135 /// This struct defines the shadow mapping using the rule:
136 ///   shadow = ((mem & mask) >> Scale) ADD DynamicShadowOffset.
137 struct ShadowMapping {
138   ShadowMapping() {
139     Scale = ClMappingScale;
140     Granularity = ClMappingGranularity;
141     Mask = ~(Granularity - 1);
142   }
143 
144   int Scale;
145   int Granularity;
146   uint64_t Mask; // Computed as ~(Granularity-1)
147 };
148 
149 static uint64_t getCtorAndDtorPriority(Triple &TargetTriple) {
150   return TargetTriple.isOSEmscripten() ? MemProfEmscriptenCtorAndDtorPriority
151                                        : MemProfCtorAndDtorPriority;
152 }
153 
154 struct InterestingMemoryAccess {
155   Value *Addr = nullptr;
156   bool IsWrite;
157   unsigned Alignment;
158   Type *AccessTy;
159   uint64_t TypeSize;
160   Value *MaybeMask = nullptr;
161 };
162 
163 /// Instrument the code in module to profile memory accesses.
164 class MemProfiler {
165 public:
166   MemProfiler(Module &M) {
167     C = &(M.getContext());
168     LongSize = M.getDataLayout().getPointerSizeInBits();
169     IntptrTy = Type::getIntNTy(*C, LongSize);
170   }
171 
172   /// If it is an interesting memory access, populate information
173   /// about the access and return a InterestingMemoryAccess struct.
174   /// Otherwise return None.
175   Optional<InterestingMemoryAccess>
176   isInterestingMemoryAccess(Instruction *I) const;
177 
178   void instrumentMop(Instruction *I, const DataLayout &DL,
179                      InterestingMemoryAccess &Access);
180   void instrumentAddress(Instruction *OrigIns, Instruction *InsertBefore,
181                          Value *Addr, uint32_t TypeSize, bool IsWrite);
182   void instrumentMaskedLoadOrStore(const DataLayout &DL, Value *Mask,
183                                    Instruction *I, Value *Addr,
184                                    unsigned Alignment, Type *AccessTy,
185                                    bool IsWrite);
186   void instrumentMemIntrinsic(MemIntrinsic *MI);
187   Value *memToShadow(Value *Shadow, IRBuilder<> &IRB);
188   bool instrumentFunction(Function &F);
189   bool maybeInsertMemProfInitAtFunctionEntry(Function &F);
190   bool insertDynamicShadowAtFunctionEntry(Function &F);
191 
192 private:
193   void initializeCallbacks(Module &M);
194 
195   LLVMContext *C;
196   int LongSize;
197   Type *IntptrTy;
198   ShadowMapping Mapping;
199 
200   // These arrays is indexed by AccessIsWrite
201   FunctionCallee MemProfMemoryAccessCallback[2];
202   FunctionCallee MemProfMemoryAccessCallbackSized[2];
203 
204   FunctionCallee MemProfMemmove, MemProfMemcpy, MemProfMemset;
205   Value *DynamicShadowOffset = nullptr;
206 };
207 
208 class MemProfilerLegacyPass : public FunctionPass {
209 public:
210   static char ID;
211 
212   explicit MemProfilerLegacyPass() : FunctionPass(ID) {
213     initializeMemProfilerLegacyPassPass(*PassRegistry::getPassRegistry());
214   }
215 
216   StringRef getPassName() const override { return "MemProfilerFunctionPass"; }
217 
218   bool runOnFunction(Function &F) override {
219     MemProfiler Profiler(*F.getParent());
220     return Profiler.instrumentFunction(F);
221   }
222 };
223 
224 class ModuleMemProfiler {
225 public:
226   ModuleMemProfiler(Module &M) { TargetTriple = Triple(M.getTargetTriple()); }
227 
228   bool instrumentModule(Module &);
229 
230 private:
231   Triple TargetTriple;
232   ShadowMapping Mapping;
233   Function *MemProfCtorFunction = nullptr;
234 };
235 
236 class ModuleMemProfilerLegacyPass : public ModulePass {
237 public:
238   static char ID;
239 
240   explicit ModuleMemProfilerLegacyPass() : ModulePass(ID) {
241     initializeModuleMemProfilerLegacyPassPass(*PassRegistry::getPassRegistry());
242   }
243 
244   StringRef getPassName() const override { return "ModuleMemProfiler"; }
245 
246   void getAnalysisUsage(AnalysisUsage &AU) const override {}
247 
248   bool runOnModule(Module &M) override {
249     ModuleMemProfiler MemProfiler(M);
250     return MemProfiler.instrumentModule(M);
251   }
252 };
253 
254 } // end anonymous namespace
255 
256 MemProfilerPass::MemProfilerPass() = default;
257 
258 PreservedAnalyses MemProfilerPass::run(Function &F,
259                                        AnalysisManager<Function> &AM) {
260   Module &M = *F.getParent();
261   MemProfiler Profiler(M);
262   if (Profiler.instrumentFunction(F))
263     return PreservedAnalyses::none();
264   return PreservedAnalyses::all();
265 }
266 
267 ModuleMemProfilerPass::ModuleMemProfilerPass() = default;
268 
269 PreservedAnalyses ModuleMemProfilerPass::run(Module &M,
270                                              AnalysisManager<Module> &AM) {
271   ModuleMemProfiler Profiler(M);
272   if (Profiler.instrumentModule(M))
273     return PreservedAnalyses::none();
274   return PreservedAnalyses::all();
275 }
276 
277 char MemProfilerLegacyPass::ID = 0;
278 
279 INITIALIZE_PASS_BEGIN(MemProfilerLegacyPass, "memprof",
280                       "MemProfiler: profile memory allocations and accesses.",
281                       false, false)
282 INITIALIZE_PASS_END(MemProfilerLegacyPass, "memprof",
283                     "MemProfiler: profile memory allocations and accesses.",
284                     false, false)
285 
286 FunctionPass *llvm::createMemProfilerFunctionPass() {
287   return new MemProfilerLegacyPass();
288 }
289 
290 char ModuleMemProfilerLegacyPass::ID = 0;
291 
292 INITIALIZE_PASS(ModuleMemProfilerLegacyPass, "memprof-module",
293                 "MemProfiler: profile memory allocations and accesses."
294                 "ModulePass",
295                 false, false)
296 
297 ModulePass *llvm::createModuleMemProfilerLegacyPassPass() {
298   return new ModuleMemProfilerLegacyPass();
299 }
300 
301 Value *MemProfiler::memToShadow(Value *Shadow, IRBuilder<> &IRB) {
302   // (Shadow & mask) >> scale
303   Shadow = IRB.CreateAnd(Shadow, Mapping.Mask);
304   Shadow = IRB.CreateLShr(Shadow, Mapping.Scale);
305   // (Shadow >> scale) | offset
306   assert(DynamicShadowOffset);
307   return IRB.CreateAdd(Shadow, DynamicShadowOffset);
308 }
309 
310 // Instrument memset/memmove/memcpy
311 void MemProfiler::instrumentMemIntrinsic(MemIntrinsic *MI) {
312   IRBuilder<> IRB(MI);
313   if (isa<MemTransferInst>(MI)) {
314     IRB.CreateCall(
315         isa<MemMoveInst>(MI) ? MemProfMemmove : MemProfMemcpy,
316         {IRB.CreatePointerCast(MI->getOperand(0), IRB.getInt8PtrTy()),
317          IRB.CreatePointerCast(MI->getOperand(1), IRB.getInt8PtrTy()),
318          IRB.CreateIntCast(MI->getOperand(2), IntptrTy, false)});
319   } else if (isa<MemSetInst>(MI)) {
320     IRB.CreateCall(
321         MemProfMemset,
322         {IRB.CreatePointerCast(MI->getOperand(0), IRB.getInt8PtrTy()),
323          IRB.CreateIntCast(MI->getOperand(1), IRB.getInt32Ty(), false),
324          IRB.CreateIntCast(MI->getOperand(2), IntptrTy, false)});
325   }
326   MI->eraseFromParent();
327 }
328 
329 Optional<InterestingMemoryAccess>
330 MemProfiler::isInterestingMemoryAccess(Instruction *I) const {
331   // Do not instrument the load fetching the dynamic shadow address.
332   if (DynamicShadowOffset == I)
333     return None;
334 
335   InterestingMemoryAccess Access;
336 
337   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
338     if (!ClInstrumentReads)
339       return None;
340     Access.IsWrite = false;
341     Access.AccessTy = LI->getType();
342     Access.Alignment = LI->getAlignment();
343     Access.Addr = LI->getPointerOperand();
344   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
345     if (!ClInstrumentWrites)
346       return None;
347     Access.IsWrite = true;
348     Access.AccessTy = SI->getValueOperand()->getType();
349     Access.Alignment = SI->getAlignment();
350     Access.Addr = SI->getPointerOperand();
351   } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
352     if (!ClInstrumentAtomics)
353       return None;
354     Access.IsWrite = true;
355     Access.AccessTy = RMW->getValOperand()->getType();
356     Access.Alignment = 0;
357     Access.Addr = RMW->getPointerOperand();
358   } else if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) {
359     if (!ClInstrumentAtomics)
360       return None;
361     Access.IsWrite = true;
362     Access.AccessTy = XCHG->getCompareOperand()->getType();
363     Access.Alignment = 0;
364     Access.Addr = XCHG->getPointerOperand();
365   } else if (auto *CI = dyn_cast<CallInst>(I)) {
366     auto *F = CI->getCalledFunction();
367     if (F && (F->getIntrinsicID() == Intrinsic::masked_load ||
368               F->getIntrinsicID() == Intrinsic::masked_store)) {
369       unsigned OpOffset = 0;
370       if (F->getIntrinsicID() == Intrinsic::masked_store) {
371         if (!ClInstrumentWrites)
372           return None;
373         // Masked store has an initial operand for the value.
374         OpOffset = 1;
375         Access.AccessTy = CI->getArgOperand(0)->getType();
376         Access.IsWrite = true;
377       } else {
378         if (!ClInstrumentReads)
379           return None;
380         Access.AccessTy = CI->getType();
381         Access.IsWrite = false;
382       }
383 
384       auto *BasePtr = CI->getOperand(0 + OpOffset);
385       if (auto *AlignmentConstant =
386               dyn_cast<ConstantInt>(CI->getOperand(1 + OpOffset)))
387         Access.Alignment = (unsigned)AlignmentConstant->getZExtValue();
388       else
389         Access.Alignment = 1; // No alignment guarantees. We probably got Undef
390       Access.MaybeMask = CI->getOperand(2 + OpOffset);
391       Access.Addr = BasePtr;
392     }
393   }
394 
395   if (!Access.Addr)
396     return None;
397 
398   // Do not instrument acesses from different address spaces; we cannot deal
399   // with them.
400   Type *PtrTy = cast<PointerType>(Access.Addr->getType()->getScalarType());
401   if (PtrTy->getPointerAddressSpace() != 0)
402     return None;
403 
404   // Ignore swifterror addresses.
405   // swifterror memory addresses are mem2reg promoted by instruction
406   // selection. As such they cannot have regular uses like an instrumentation
407   // function and it makes no sense to track them as memory.
408   if (Access.Addr->isSwiftError())
409     return None;
410 
411   const DataLayout &DL = I->getModule()->getDataLayout();
412   Access.TypeSize = DL.getTypeStoreSizeInBits(Access.AccessTy);
413   return Access;
414 }
415 
416 void MemProfiler::instrumentMaskedLoadOrStore(const DataLayout &DL, Value *Mask,
417                                               Instruction *I, Value *Addr,
418                                               unsigned Alignment,
419                                               Type *AccessTy, bool IsWrite) {
420   auto *VTy = cast<FixedVectorType>(AccessTy);
421   uint64_t ElemTypeSize = DL.getTypeStoreSizeInBits(VTy->getScalarType());
422   unsigned Num = VTy->getNumElements();
423   auto *Zero = ConstantInt::get(IntptrTy, 0);
424   for (unsigned Idx = 0; Idx < Num; ++Idx) {
425     Value *InstrumentedAddress = nullptr;
426     Instruction *InsertBefore = I;
427     if (auto *Vector = dyn_cast<ConstantVector>(Mask)) {
428       // dyn_cast as we might get UndefValue
429       if (auto *Masked = dyn_cast<ConstantInt>(Vector->getOperand(Idx))) {
430         if (Masked->isZero())
431           // Mask is constant false, so no instrumentation needed.
432           continue;
433         // If we have a true or undef value, fall through to instrumentAddress.
434         // with InsertBefore == I
435       }
436     } else {
437       IRBuilder<> IRB(I);
438       Value *MaskElem = IRB.CreateExtractElement(Mask, Idx);
439       Instruction *ThenTerm = SplitBlockAndInsertIfThen(MaskElem, I, false);
440       InsertBefore = ThenTerm;
441     }
442 
443     IRBuilder<> IRB(InsertBefore);
444     InstrumentedAddress =
445         IRB.CreateGEP(VTy, Addr, {Zero, ConstantInt::get(IntptrTy, Idx)});
446     instrumentAddress(I, InsertBefore, InstrumentedAddress, ElemTypeSize,
447                       IsWrite);
448   }
449 }
450 
451 void MemProfiler::instrumentMop(Instruction *I, const DataLayout &DL,
452                                 InterestingMemoryAccess &Access) {
453   // Skip instrumentation of stack accesses unless requested.
454   if (!ClStack && isa<AllocaInst>(getUnderlyingObject(Access.Addr))) {
455     if (Access.IsWrite)
456       ++NumSkippedStackWrites;
457     else
458       ++NumSkippedStackReads;
459     return;
460   }
461 
462   if (Access.IsWrite)
463     NumInstrumentedWrites++;
464   else
465     NumInstrumentedReads++;
466 
467   if (Access.MaybeMask) {
468     instrumentMaskedLoadOrStore(DL, Access.MaybeMask, I, Access.Addr,
469                                 Access.Alignment, Access.AccessTy,
470                                 Access.IsWrite);
471   } else {
472     // Since the access counts will be accumulated across the entire allocation,
473     // we only update the shadow access count for the first location and thus
474     // don't need to worry about alignment and type size.
475     instrumentAddress(I, I, Access.Addr, Access.TypeSize, Access.IsWrite);
476   }
477 }
478 
479 void MemProfiler::instrumentAddress(Instruction *OrigIns,
480                                     Instruction *InsertBefore, Value *Addr,
481                                     uint32_t TypeSize, bool IsWrite) {
482   IRBuilder<> IRB(InsertBefore);
483   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
484 
485   if (ClUseCalls) {
486     IRB.CreateCall(MemProfMemoryAccessCallback[IsWrite], AddrLong);
487     return;
488   }
489 
490   // Create an inline sequence to compute shadow location, and increment the
491   // value by one.
492   Type *ShadowTy = Type::getInt64Ty(*C);
493   Type *ShadowPtrTy = PointerType::get(ShadowTy, 0);
494   Value *ShadowPtr = memToShadow(AddrLong, IRB);
495   Value *ShadowAddr = IRB.CreateIntToPtr(ShadowPtr, ShadowPtrTy);
496   Value *ShadowValue = IRB.CreateLoad(ShadowTy, ShadowAddr);
497   Value *Inc = ConstantInt::get(Type::getInt64Ty(*C), 1);
498   ShadowValue = IRB.CreateAdd(ShadowValue, Inc);
499   IRB.CreateStore(ShadowValue, ShadowAddr);
500 }
501 
502 // Create the variable for the profile file name.
503 void createProfileFileNameVar(Module &M) {
504   const MDString *MemProfFilename =
505       dyn_cast_or_null<MDString>(M.getModuleFlag("MemProfProfileFilename"));
506   if (!MemProfFilename)
507     return;
508   assert(!MemProfFilename->getString().empty() &&
509          "Unexpected MemProfProfileFilename metadata with empty string");
510   Constant *ProfileNameConst = ConstantDataArray::getString(
511       M.getContext(), MemProfFilename->getString(), true);
512   GlobalVariable *ProfileNameVar = new GlobalVariable(
513       M, ProfileNameConst->getType(), /*isConstant=*/true,
514       GlobalValue::WeakAnyLinkage, ProfileNameConst, MemProfFilenameVar);
515   Triple TT(M.getTargetTriple());
516   if (TT.supportsCOMDAT()) {
517     ProfileNameVar->setLinkage(GlobalValue::ExternalLinkage);
518     ProfileNameVar->setComdat(M.getOrInsertComdat(MemProfFilenameVar));
519   }
520 }
521 
522 bool ModuleMemProfiler::instrumentModule(Module &M) {
523   // Create a module constructor.
524   std::string MemProfVersion = std::to_string(LLVM_MEM_PROFILER_VERSION);
525   std::string VersionCheckName =
526       ClInsertVersionCheck ? (MemProfVersionCheckNamePrefix + MemProfVersion)
527                            : "";
528   std::tie(MemProfCtorFunction, std::ignore) =
529       createSanitizerCtorAndInitFunctions(M, MemProfModuleCtorName,
530                                           MemProfInitName, /*InitArgTypes=*/{},
531                                           /*InitArgs=*/{}, VersionCheckName);
532 
533   const uint64_t Priority = getCtorAndDtorPriority(TargetTriple);
534   appendToGlobalCtors(M, MemProfCtorFunction, Priority);
535 
536   createProfileFileNameVar(M);
537 
538   return true;
539 }
540 
541 void MemProfiler::initializeCallbacks(Module &M) {
542   IRBuilder<> IRB(*C);
543 
544   for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) {
545     const std::string TypeStr = AccessIsWrite ? "store" : "load";
546 
547     SmallVector<Type *, 3> Args2 = {IntptrTy, IntptrTy};
548     SmallVector<Type *, 2> Args1{1, IntptrTy};
549     MemProfMemoryAccessCallbackSized[AccessIsWrite] =
550         M.getOrInsertFunction(ClMemoryAccessCallbackPrefix + TypeStr + "N",
551                               FunctionType::get(IRB.getVoidTy(), Args2, false));
552 
553     MemProfMemoryAccessCallback[AccessIsWrite] =
554         M.getOrInsertFunction(ClMemoryAccessCallbackPrefix + TypeStr,
555                               FunctionType::get(IRB.getVoidTy(), Args1, false));
556   }
557   MemProfMemmove = M.getOrInsertFunction(
558       ClMemoryAccessCallbackPrefix + "memmove", IRB.getInt8PtrTy(),
559       IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IntptrTy);
560   MemProfMemcpy = M.getOrInsertFunction(ClMemoryAccessCallbackPrefix + "memcpy",
561                                         IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
562                                         IRB.getInt8PtrTy(), IntptrTy);
563   MemProfMemset = M.getOrInsertFunction(ClMemoryAccessCallbackPrefix + "memset",
564                                         IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
565                                         IRB.getInt32Ty(), IntptrTy);
566 }
567 
568 bool MemProfiler::maybeInsertMemProfInitAtFunctionEntry(Function &F) {
569   // For each NSObject descendant having a +load method, this method is invoked
570   // by the ObjC runtime before any of the static constructors is called.
571   // Therefore we need to instrument such methods with a call to __memprof_init
572   // at the beginning in order to initialize our runtime before any access to
573   // the shadow memory.
574   // We cannot just ignore these methods, because they may call other
575   // instrumented functions.
576   if (F.getName().find(" load]") != std::string::npos) {
577     FunctionCallee MemProfInitFunction =
578         declareSanitizerInitFunction(*F.getParent(), MemProfInitName, {});
579     IRBuilder<> IRB(&F.front(), F.front().begin());
580     IRB.CreateCall(MemProfInitFunction, {});
581     return true;
582   }
583   return false;
584 }
585 
586 bool MemProfiler::insertDynamicShadowAtFunctionEntry(Function &F) {
587   IRBuilder<> IRB(&F.front().front());
588   Value *GlobalDynamicAddress = F.getParent()->getOrInsertGlobal(
589       MemProfShadowMemoryDynamicAddress, IntptrTy);
590   if (F.getParent()->getPICLevel() == PICLevel::NotPIC)
591     cast<GlobalVariable>(GlobalDynamicAddress)->setDSOLocal(true);
592   DynamicShadowOffset = IRB.CreateLoad(IntptrTy, GlobalDynamicAddress);
593   return true;
594 }
595 
596 bool MemProfiler::instrumentFunction(Function &F) {
597   if (F.getLinkage() == GlobalValue::AvailableExternallyLinkage)
598     return false;
599   if (ClDebugFunc == F.getName())
600     return false;
601   if (F.getName().startswith("__memprof_"))
602     return false;
603 
604   bool FunctionModified = false;
605 
606   // If needed, insert __memprof_init.
607   // This function needs to be called even if the function body is not
608   // instrumented.
609   if (maybeInsertMemProfInitAtFunctionEntry(F))
610     FunctionModified = true;
611 
612   LLVM_DEBUG(dbgs() << "MEMPROF instrumenting:\n" << F << "\n");
613 
614   initializeCallbacks(*F.getParent());
615 
616   FunctionModified |= insertDynamicShadowAtFunctionEntry(F);
617 
618   SmallVector<Instruction *, 16> ToInstrument;
619 
620   // Fill the set of memory operations to instrument.
621   for (auto &BB : F) {
622     for (auto &Inst : BB) {
623       if (isInterestingMemoryAccess(&Inst) || isa<MemIntrinsic>(Inst))
624         ToInstrument.push_back(&Inst);
625     }
626   }
627 
628   int NumInstrumented = 0;
629   for (auto *Inst : ToInstrument) {
630     if (ClDebugMin < 0 || ClDebugMax < 0 ||
631         (NumInstrumented >= ClDebugMin && NumInstrumented <= ClDebugMax)) {
632       Optional<InterestingMemoryAccess> Access =
633           isInterestingMemoryAccess(Inst);
634       if (Access)
635         instrumentMop(Inst, F.getParent()->getDataLayout(), *Access);
636       else
637         instrumentMemIntrinsic(cast<MemIntrinsic>(Inst));
638     }
639     NumInstrumented++;
640   }
641 
642   if (NumInstrumented > 0)
643     FunctionModified = true;
644 
645   LLVM_DEBUG(dbgs() << "MEMPROF done instrumenting: " << FunctionModified << " "
646                     << F << "\n");
647 
648   return FunctionModified;
649 }
650