1 //===-- AddressSanitizer.cpp - memory error detector ------------*- C++ -*-===//
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 file is a part of AddressSanitizer, an address sanity checker.
11 // Details of the algorithm:
12 //  http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerAlgorithm
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/DepthFirstIterator.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/ADT/StringExtras.h"
24 #include "llvm/ADT/Triple.h"
25 #include "llvm/Analysis/MemoryBuiltins.h"
26 #include "llvm/Analysis/TargetLibraryInfo.h"
27 #include "llvm/Analysis/ValueTracking.h"
28 #include "llvm/IR/CallSite.h"
29 #include "llvm/IR/DIBuilder.h"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/IR/Dominators.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/IRBuilder.h"
34 #include "llvm/IR/InlineAsm.h"
35 #include "llvm/IR/InstVisitor.h"
36 #include "llvm/IR/IntrinsicInst.h"
37 #include "llvm/IR/LLVMContext.h"
38 #include "llvm/IR/MDBuilder.h"
39 #include "llvm/IR/Module.h"
40 #include "llvm/IR/Type.h"
41 #include "llvm/MC/MCSectionMachO.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/DataTypes.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/Endian.h"
46 #include "llvm/Support/SwapByteOrder.h"
47 #include "llvm/Support/raw_ostream.h"
48 #include "llvm/Transforms/Instrumentation.h"
49 #include "llvm/Transforms/Scalar.h"
50 #include "llvm/Transforms/Utils/ASanStackFrameLayout.h"
51 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
52 #include "llvm/Transforms/Utils/Cloning.h"
53 #include "llvm/Transforms/Utils/Local.h"
54 #include "llvm/Transforms/Utils/ModuleUtils.h"
55 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
56 #include <algorithm>
57 #include <iomanip>
58 #include <limits>
59 #include <sstream>
60 #include <string>
61 #include <system_error>
62 
63 using namespace llvm;
64 
65 #define DEBUG_TYPE "asan"
66 
67 static const uint64_t kDefaultShadowScale = 3;
68 static const uint64_t kDefaultShadowOffset32 = 1ULL << 29;
69 static const uint64_t kDefaultShadowOffset64 = 1ULL << 44;
70 static const uint64_t kDynamicShadowSentinel = ~(uint64_t)0;
71 static const uint64_t kIOSShadowOffset32 = 1ULL << 30;
72 static const uint64_t kIOSSimShadowOffset32 = 1ULL << 30;
73 static const uint64_t kIOSSimShadowOffset64 = kDefaultShadowOffset64;
74 static const uint64_t kSmallX86_64ShadowOffset = 0x7FFF8000;  // < 2G.
75 static const uint64_t kLinuxKasan_ShadowOffset64 = 0xdffffc0000000000;
76 static const uint64_t kPPC64_ShadowOffset64 = 1ULL << 41;
77 static const uint64_t kSystemZ_ShadowOffset64 = 1ULL << 52;
78 static const uint64_t kMIPS32_ShadowOffset32 = 0x0aaa0000;
79 static const uint64_t kMIPS64_ShadowOffset64 = 1ULL << 37;
80 static const uint64_t kAArch64_ShadowOffset64 = 1ULL << 36;
81 static const uint64_t kFreeBSD_ShadowOffset32 = 1ULL << 30;
82 static const uint64_t kFreeBSD_ShadowOffset64 = 1ULL << 46;
83 static const uint64_t kWindowsShadowOffset32 = 3ULL << 28;
84 // The shadow memory space is dynamically allocated.
85 static const uint64_t kWindowsShadowOffset64 = kDynamicShadowSentinel;
86 
87 static const size_t kMinStackMallocSize = 1 << 6;   // 64B
88 static const size_t kMaxStackMallocSize = 1 << 16;  // 64K
89 static const uintptr_t kCurrentStackFrameMagic = 0x41B58AB3;
90 static const uintptr_t kRetiredStackFrameMagic = 0x45E0360E;
91 
92 static const char *const kAsanModuleCtorName = "asan.module_ctor";
93 static const char *const kAsanModuleDtorName = "asan.module_dtor";
94 static const uint64_t kAsanCtorAndDtorPriority = 1;
95 static const char *const kAsanReportErrorTemplate = "__asan_report_";
96 static const char *const kAsanRegisterGlobalsName = "__asan_register_globals";
97 static const char *const kAsanUnregisterGlobalsName =
98     "__asan_unregister_globals";
99 static const char *const kAsanRegisterImageGlobalsName =
100   "__asan_register_image_globals";
101 static const char *const kAsanUnregisterImageGlobalsName =
102   "__asan_unregister_image_globals";
103 static const char *const kAsanPoisonGlobalsName = "__asan_before_dynamic_init";
104 static const char *const kAsanUnpoisonGlobalsName = "__asan_after_dynamic_init";
105 static const char *const kAsanInitName = "__asan_init";
106 static const char *const kAsanVersionCheckName =
107     "__asan_version_mismatch_check_v8";
108 static const char *const kAsanPtrCmp = "__sanitizer_ptr_cmp";
109 static const char *const kAsanPtrSub = "__sanitizer_ptr_sub";
110 static const char *const kAsanHandleNoReturnName = "__asan_handle_no_return";
111 static const int kMaxAsanStackMallocSizeClass = 10;
112 static const char *const kAsanStackMallocNameTemplate = "__asan_stack_malloc_";
113 static const char *const kAsanStackFreeNameTemplate = "__asan_stack_free_";
114 static const char *const kAsanGenPrefix = "__asan_gen_";
115 static const char *const kODRGenPrefix = "__odr_asan_gen_";
116 static const char *const kSanCovGenPrefix = "__sancov_gen_";
117 static const char *const kAsanSetShadowPrefix = "__asan_set_shadow_";
118 static const char *const kAsanPoisonStackMemoryName =
119     "__asan_poison_stack_memory";
120 static const char *const kAsanUnpoisonStackMemoryName =
121     "__asan_unpoison_stack_memory";
122 static const char *const kAsanGlobalsRegisteredFlagName =
123     "__asan_globals_registered";
124 
125 static const char *const kAsanOptionDetectUseAfterReturn =
126     "__asan_option_detect_stack_use_after_return";
127 
128 static const char *const kAsanShadowMemoryDynamicAddress =
129     "__asan_shadow_memory_dynamic_address";
130 
131 static const char *const kAsanAllocaPoison = "__asan_alloca_poison";
132 static const char *const kAsanAllocasUnpoison = "__asan_allocas_unpoison";
133 
134 // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
135 static const size_t kNumberOfAccessSizes = 5;
136 
137 static const unsigned kAllocaRzSize = 32;
138 
139 // Command-line flags.
140 static cl::opt<bool> ClEnableKasan(
141     "asan-kernel", cl::desc("Enable KernelAddressSanitizer instrumentation"),
142     cl::Hidden, cl::init(false));
143 static cl::opt<bool> ClRecover(
144     "asan-recover",
145     cl::desc("Enable recovery mode (continue-after-error)."),
146     cl::Hidden, cl::init(false));
147 
148 // This flag may need to be replaced with -f[no-]asan-reads.
149 static cl::opt<bool> ClInstrumentReads("asan-instrument-reads",
150                                        cl::desc("instrument read instructions"),
151                                        cl::Hidden, cl::init(true));
152 static cl::opt<bool> ClInstrumentWrites(
153     "asan-instrument-writes", cl::desc("instrument write instructions"),
154     cl::Hidden, cl::init(true));
155 static cl::opt<bool> ClInstrumentAtomics(
156     "asan-instrument-atomics",
157     cl::desc("instrument atomic instructions (rmw, cmpxchg)"), cl::Hidden,
158     cl::init(true));
159 static cl::opt<bool> ClAlwaysSlowPath(
160     "asan-always-slow-path",
161     cl::desc("use instrumentation with slow path for all accesses"), cl::Hidden,
162     cl::init(false));
163 static cl::opt<bool> ClForceDynamicShadow(
164     "asan-force-dynamic-shadow",
165     cl::desc("Load shadow address into a local variable for each function"),
166     cl::Hidden, cl::init(false));
167 
168 // This flag limits the number of instructions to be instrumented
169 // in any given BB. Normally, this should be set to unlimited (INT_MAX),
170 // but due to http://llvm.org/bugs/show_bug.cgi?id=12652 we temporary
171 // set it to 10000.
172 static cl::opt<int> ClMaxInsnsToInstrumentPerBB(
173     "asan-max-ins-per-bb", cl::init(10000),
174     cl::desc("maximal number of instructions to instrument in any given BB"),
175     cl::Hidden);
176 // This flag may need to be replaced with -f[no]asan-stack.
177 static cl::opt<bool> ClStack("asan-stack", cl::desc("Handle stack memory"),
178                              cl::Hidden, cl::init(true));
179 static cl::opt<uint32_t> ClMaxInlinePoisoningSize(
180     "asan-max-inline-poisoning-size",
181     cl::desc(
182         "Inline shadow poisoning for blocks up to the given size in bytes."),
183     cl::Hidden, cl::init(64));
184 static cl::opt<bool> ClUseAfterReturn("asan-use-after-return",
185                                       cl::desc("Check stack-use-after-return"),
186                                       cl::Hidden, cl::init(true));
187 static cl::opt<bool> ClUseAfterScope("asan-use-after-scope",
188                                      cl::desc("Check stack-use-after-scope"),
189                                      cl::Hidden, cl::init(false));
190 // This flag may need to be replaced with -f[no]asan-globals.
191 static cl::opt<bool> ClGlobals("asan-globals",
192                                cl::desc("Handle global objects"), cl::Hidden,
193                                cl::init(true));
194 static cl::opt<bool> ClInitializers("asan-initialization-order",
195                                     cl::desc("Handle C++ initializer order"),
196                                     cl::Hidden, cl::init(true));
197 static cl::opt<bool> ClInvalidPointerPairs(
198     "asan-detect-invalid-pointer-pair",
199     cl::desc("Instrument <, <=, >, >=, - with pointer operands"), cl::Hidden,
200     cl::init(false));
201 static cl::opt<unsigned> ClRealignStack(
202     "asan-realign-stack",
203     cl::desc("Realign stack to the value of this flag (power of two)"),
204     cl::Hidden, cl::init(32));
205 static cl::opt<int> ClInstrumentationWithCallsThreshold(
206     "asan-instrumentation-with-call-threshold",
207     cl::desc(
208         "If the function being instrumented contains more than "
209         "this number of memory accesses, use callbacks instead of "
210         "inline checks (-1 means never use callbacks)."),
211     cl::Hidden, cl::init(7000));
212 static cl::opt<std::string> ClMemoryAccessCallbackPrefix(
213     "asan-memory-access-callback-prefix",
214     cl::desc("Prefix for memory access callbacks"), cl::Hidden,
215     cl::init("__asan_"));
216 static cl::opt<bool>
217     ClInstrumentDynamicAllocas("asan-instrument-dynamic-allocas",
218                                cl::desc("instrument dynamic allocas"),
219                                cl::Hidden, cl::init(true));
220 static cl::opt<bool> ClSkipPromotableAllocas(
221     "asan-skip-promotable-allocas",
222     cl::desc("Do not instrument promotable allocas"), cl::Hidden,
223     cl::init(true));
224 
225 // These flags allow to change the shadow mapping.
226 // The shadow mapping looks like
227 //    Shadow = (Mem >> scale) + offset
228 static cl::opt<int> ClMappingScale("asan-mapping-scale",
229                                    cl::desc("scale of asan shadow mapping"),
230                                    cl::Hidden, cl::init(0));
231 static cl::opt<unsigned long long> ClMappingOffset(
232     "asan-mapping-offset",
233     cl::desc("offset of asan shadow mapping [EXPERIMENTAL]"), cl::Hidden,
234     cl::init(0));
235 
236 // Optimization flags. Not user visible, used mostly for testing
237 // and benchmarking the tool.
238 static cl::opt<bool> ClOpt("asan-opt", cl::desc("Optimize instrumentation"),
239                            cl::Hidden, cl::init(true));
240 static cl::opt<bool> ClOptSameTemp(
241     "asan-opt-same-temp", cl::desc("Instrument the same temp just once"),
242     cl::Hidden, cl::init(true));
243 static cl::opt<bool> ClOptGlobals("asan-opt-globals",
244                                   cl::desc("Don't instrument scalar globals"),
245                                   cl::Hidden, cl::init(true));
246 static cl::opt<bool> ClOptStack(
247     "asan-opt-stack", cl::desc("Don't instrument scalar stack variables"),
248     cl::Hidden, cl::init(false));
249 
250 static cl::opt<bool> ClDynamicAllocaStack(
251     "asan-stack-dynamic-alloca",
252     cl::desc("Use dynamic alloca to represent stack variables"), cl::Hidden,
253     cl::init(true));
254 
255 static cl::opt<uint32_t> ClForceExperiment(
256     "asan-force-experiment",
257     cl::desc("Force optimization experiment (for testing)"), cl::Hidden,
258     cl::init(0));
259 
260 static cl::opt<bool>
261     ClUsePrivateAliasForGlobals("asan-use-private-alias",
262                                 cl::desc("Use private aliases for global"
263                                          " variables"),
264                                 cl::Hidden, cl::init(false));
265 
266 static cl::opt<bool>
267     ClUseMachOGlobalsSection("asan-globals-live-support",
268                              cl::desc("Use linker features to support dead "
269                                       "code stripping of globals "
270                                       "(Mach-O only)"),
271                              cl::Hidden, cl::init(false));
272 
273 // Debug flags.
274 static cl::opt<int> ClDebug("asan-debug", cl::desc("debug"), cl::Hidden,
275                             cl::init(0));
276 static cl::opt<int> ClDebugStack("asan-debug-stack", cl::desc("debug stack"),
277                                  cl::Hidden, cl::init(0));
278 static cl::opt<std::string> ClDebugFunc("asan-debug-func", cl::Hidden,
279                                         cl::desc("Debug func"));
280 static cl::opt<int> ClDebugMin("asan-debug-min", cl::desc("Debug min inst"),
281                                cl::Hidden, cl::init(-1));
282 static cl::opt<int> ClDebugMax("asan-debug-max", cl::desc("Debug max inst"),
283                                cl::Hidden, cl::init(-1));
284 
285 STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
286 STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
287 STATISTIC(NumOptimizedAccessesToGlobalVar,
288           "Number of optimized accesses to global vars");
289 STATISTIC(NumOptimizedAccessesToStackVar,
290           "Number of optimized accesses to stack vars");
291 
292 namespace {
293 /// Frontend-provided metadata for source location.
294 struct LocationMetadata {
295   StringRef Filename;
296   int LineNo;
297   int ColumnNo;
298 
299   LocationMetadata() : Filename(), LineNo(0), ColumnNo(0) {}
300 
301   bool empty() const { return Filename.empty(); }
302 
303   void parse(MDNode *MDN) {
304     assert(MDN->getNumOperands() == 3);
305     MDString *DIFilename = cast<MDString>(MDN->getOperand(0));
306     Filename = DIFilename->getString();
307     LineNo =
308         mdconst::extract<ConstantInt>(MDN->getOperand(1))->getLimitedValue();
309     ColumnNo =
310         mdconst::extract<ConstantInt>(MDN->getOperand(2))->getLimitedValue();
311   }
312 };
313 
314 /// Frontend-provided metadata for global variables.
315 class GlobalsMetadata {
316  public:
317   struct Entry {
318     Entry() : SourceLoc(), Name(), IsDynInit(false), IsBlacklisted(false) {}
319     LocationMetadata SourceLoc;
320     StringRef Name;
321     bool IsDynInit;
322     bool IsBlacklisted;
323   };
324 
325   GlobalsMetadata() : inited_(false) {}
326 
327   void reset() {
328     inited_ = false;
329     Entries.clear();
330   }
331 
332   void init(Module &M) {
333     assert(!inited_);
334     inited_ = true;
335     NamedMDNode *Globals = M.getNamedMetadata("llvm.asan.globals");
336     if (!Globals) return;
337     for (auto MDN : Globals->operands()) {
338       // Metadata node contains the global and the fields of "Entry".
339       assert(MDN->getNumOperands() == 5);
340       auto *GV = mdconst::extract_or_null<GlobalVariable>(MDN->getOperand(0));
341       // The optimizer may optimize away a global entirely.
342       if (!GV) continue;
343       // We can already have an entry for GV if it was merged with another
344       // global.
345       Entry &E = Entries[GV];
346       if (auto *Loc = cast_or_null<MDNode>(MDN->getOperand(1)))
347         E.SourceLoc.parse(Loc);
348       if (auto *Name = cast_or_null<MDString>(MDN->getOperand(2)))
349         E.Name = Name->getString();
350       ConstantInt *IsDynInit =
351           mdconst::extract<ConstantInt>(MDN->getOperand(3));
352       E.IsDynInit |= IsDynInit->isOne();
353       ConstantInt *IsBlacklisted =
354           mdconst::extract<ConstantInt>(MDN->getOperand(4));
355       E.IsBlacklisted |= IsBlacklisted->isOne();
356     }
357   }
358 
359   /// Returns metadata entry for a given global.
360   Entry get(GlobalVariable *G) const {
361     auto Pos = Entries.find(G);
362     return (Pos != Entries.end()) ? Pos->second : Entry();
363   }
364 
365  private:
366   bool inited_;
367   DenseMap<GlobalVariable *, Entry> Entries;
368 };
369 
370 /// This struct defines the shadow mapping using the rule:
371 ///   shadow = (mem >> Scale) ADD-or-OR Offset.
372 struct ShadowMapping {
373   int Scale;
374   uint64_t Offset;
375   bool OrShadowOffset;
376 };
377 
378 static ShadowMapping getShadowMapping(Triple &TargetTriple, int LongSize,
379                                       bool IsKasan) {
380   bool IsAndroid = TargetTriple.isAndroid();
381   bool IsIOS = TargetTriple.isiOS() || TargetTriple.isWatchOS();
382   bool IsFreeBSD = TargetTriple.isOSFreeBSD();
383   bool IsLinux = TargetTriple.isOSLinux();
384   bool IsPPC64 = TargetTriple.getArch() == llvm::Triple::ppc64 ||
385                  TargetTriple.getArch() == llvm::Triple::ppc64le;
386   bool IsSystemZ = TargetTriple.getArch() == llvm::Triple::systemz;
387   bool IsX86 = TargetTriple.getArch() == llvm::Triple::x86;
388   bool IsX86_64 = TargetTriple.getArch() == llvm::Triple::x86_64;
389   bool IsMIPS32 = TargetTriple.getArch() == llvm::Triple::mips ||
390                   TargetTriple.getArch() == llvm::Triple::mipsel;
391   bool IsMIPS64 = TargetTriple.getArch() == llvm::Triple::mips64 ||
392                   TargetTriple.getArch() == llvm::Triple::mips64el;
393   bool IsAArch64 = TargetTriple.getArch() == llvm::Triple::aarch64;
394   bool IsWindows = TargetTriple.isOSWindows();
395 
396   ShadowMapping Mapping;
397 
398   if (LongSize == 32) {
399     // Android is always PIE, which means that the beginning of the address
400     // space is always available.
401     if (IsAndroid)
402       Mapping.Offset = 0;
403     else if (IsMIPS32)
404       Mapping.Offset = kMIPS32_ShadowOffset32;
405     else if (IsFreeBSD)
406       Mapping.Offset = kFreeBSD_ShadowOffset32;
407     else if (IsIOS)
408       // If we're targeting iOS and x86, the binary is built for iOS simulator.
409       Mapping.Offset = IsX86 ? kIOSSimShadowOffset32 : kIOSShadowOffset32;
410     else if (IsWindows)
411       Mapping.Offset = kWindowsShadowOffset32;
412     else
413       Mapping.Offset = kDefaultShadowOffset32;
414   } else {  // LongSize == 64
415     if (IsPPC64)
416       Mapping.Offset = kPPC64_ShadowOffset64;
417     else if (IsSystemZ)
418       Mapping.Offset = kSystemZ_ShadowOffset64;
419     else if (IsFreeBSD)
420       Mapping.Offset = kFreeBSD_ShadowOffset64;
421     else if (IsLinux && IsX86_64) {
422       if (IsKasan)
423         Mapping.Offset = kLinuxKasan_ShadowOffset64;
424       else
425         Mapping.Offset = kSmallX86_64ShadowOffset;
426     } else if (IsWindows && IsX86_64) {
427       Mapping.Offset = kWindowsShadowOffset64;
428     } else if (IsMIPS64)
429       Mapping.Offset = kMIPS64_ShadowOffset64;
430     else if (IsIOS)
431       // If we're targeting iOS and x86, the binary is built for iOS simulator.
432       // We are using dynamic shadow offset on the 64-bit devices.
433       Mapping.Offset =
434         IsX86_64 ? kIOSSimShadowOffset64 : kDynamicShadowSentinel;
435     else if (IsAArch64)
436       Mapping.Offset = kAArch64_ShadowOffset64;
437     else
438       Mapping.Offset = kDefaultShadowOffset64;
439   }
440 
441   if (ClForceDynamicShadow) {
442     Mapping.Offset = kDynamicShadowSentinel;
443   }
444 
445   Mapping.Scale = kDefaultShadowScale;
446   if (ClMappingScale.getNumOccurrences() > 0) {
447     Mapping.Scale = ClMappingScale;
448   }
449 
450   if (ClMappingOffset.getNumOccurrences() > 0) {
451     Mapping.Offset = ClMappingOffset;
452   }
453 
454   // OR-ing shadow offset if more efficient (at least on x86) if the offset
455   // is a power of two, but on ppc64 we have to use add since the shadow
456   // offset is not necessary 1/8-th of the address space.  On SystemZ,
457   // we could OR the constant in a single instruction, but it's more
458   // efficient to load it once and use indexed addressing.
459   Mapping.OrShadowOffset = !IsAArch64 && !IsPPC64 && !IsSystemZ
460                            && !(Mapping.Offset & (Mapping.Offset - 1))
461                            && Mapping.Offset != kDynamicShadowSentinel;
462 
463   return Mapping;
464 }
465 
466 static size_t RedzoneSizeForScale(int MappingScale) {
467   // Redzone used for stack and globals is at least 32 bytes.
468   // For scales 6 and 7, the redzone has to be 64 and 128 bytes respectively.
469   return std::max(32U, 1U << MappingScale);
470 }
471 
472 /// AddressSanitizer: instrument the code in module to find memory bugs.
473 struct AddressSanitizer : public FunctionPass {
474   explicit AddressSanitizer(bool CompileKernel = false, bool Recover = false,
475                             bool UseAfterScope = false)
476       : FunctionPass(ID), CompileKernel(CompileKernel || ClEnableKasan),
477         Recover(Recover || ClRecover),
478         UseAfterScope(UseAfterScope || ClUseAfterScope),
479         LocalDynamicShadow(nullptr) {
480     initializeAddressSanitizerPass(*PassRegistry::getPassRegistry());
481   }
482   StringRef getPassName() const override {
483     return "AddressSanitizerFunctionPass";
484   }
485   void getAnalysisUsage(AnalysisUsage &AU) const override {
486     AU.addRequired<DominatorTreeWrapperPass>();
487     AU.addRequired<TargetLibraryInfoWrapperPass>();
488   }
489   uint64_t getAllocaSizeInBytes(const AllocaInst &AI) const {
490     uint64_t ArraySize = 1;
491     if (AI.isArrayAllocation()) {
492       const ConstantInt *CI = dyn_cast<ConstantInt>(AI.getArraySize());
493       assert(CI && "non-constant array size");
494       ArraySize = CI->getZExtValue();
495     }
496     Type *Ty = AI.getAllocatedType();
497     uint64_t SizeInBytes =
498         AI.getModule()->getDataLayout().getTypeAllocSize(Ty);
499     return SizeInBytes * ArraySize;
500   }
501   /// Check if we want (and can) handle this alloca.
502   bool isInterestingAlloca(const AllocaInst &AI);
503 
504   /// If it is an interesting memory access, return the PointerOperand
505   /// and set IsWrite/Alignment. Otherwise return nullptr.
506   Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite,
507                                    uint64_t *TypeSize, unsigned *Alignment);
508   void instrumentMop(ObjectSizeOffsetVisitor &ObjSizeVis, Instruction *I,
509                      bool UseCalls, const DataLayout &DL);
510   void instrumentPointerComparisonOrSubtraction(Instruction *I);
511   void instrumentAddress(Instruction *OrigIns, Instruction *InsertBefore,
512                          Value *Addr, uint32_t TypeSize, bool IsWrite,
513                          Value *SizeArgument, bool UseCalls, uint32_t Exp);
514   void instrumentUnusualSizeOrAlignment(Instruction *I, Value *Addr,
515                                         uint32_t TypeSize, bool IsWrite,
516                                         Value *SizeArgument, bool UseCalls,
517                                         uint32_t Exp);
518   Value *createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong,
519                            Value *ShadowValue, uint32_t TypeSize);
520   Instruction *generateCrashCode(Instruction *InsertBefore, Value *Addr,
521                                  bool IsWrite, size_t AccessSizeIndex,
522                                  Value *SizeArgument, uint32_t Exp);
523   void instrumentMemIntrinsic(MemIntrinsic *MI);
524   Value *memToShadow(Value *Shadow, IRBuilder<> &IRB);
525   bool runOnFunction(Function &F) override;
526   bool maybeInsertAsanInitAtFunctionEntry(Function &F);
527   void maybeInsertDynamicShadowAtFunctionEntry(Function &F);
528   void markEscapedLocalAllocas(Function &F);
529   bool doInitialization(Module &M) override;
530   bool doFinalization(Module &M) override;
531   static char ID;  // Pass identification, replacement for typeid
532 
533   DominatorTree &getDominatorTree() const { return *DT; }
534 
535  private:
536   void initializeCallbacks(Module &M);
537 
538   bool LooksLikeCodeInBug11395(Instruction *I);
539   bool GlobalIsLinkerInitialized(GlobalVariable *G);
540   bool isSafeAccess(ObjectSizeOffsetVisitor &ObjSizeVis, Value *Addr,
541                     uint64_t TypeSize) const;
542 
543   /// Helper to cleanup per-function state.
544   struct FunctionStateRAII {
545     AddressSanitizer *Pass;
546     FunctionStateRAII(AddressSanitizer *Pass) : Pass(Pass) {
547       assert(Pass->ProcessedAllocas.empty() &&
548              "last pass forgot to clear cache");
549       assert(!Pass->LocalDynamicShadow);
550     }
551     ~FunctionStateRAII() {
552       Pass->LocalDynamicShadow = nullptr;
553       Pass->ProcessedAllocas.clear();
554     }
555   };
556 
557   LLVMContext *C;
558   Triple TargetTriple;
559   int LongSize;
560   bool CompileKernel;
561   bool Recover;
562   bool UseAfterScope;
563   Type *IntptrTy;
564   ShadowMapping Mapping;
565   DominatorTree *DT;
566   Function *AsanCtorFunction = nullptr;
567   Function *AsanInitFunction = nullptr;
568   Function *AsanHandleNoReturnFunc;
569   Function *AsanPtrCmpFunction, *AsanPtrSubFunction;
570   // This array is indexed by AccessIsWrite, Experiment and log2(AccessSize).
571   Function *AsanErrorCallback[2][2][kNumberOfAccessSizes];
572   Function *AsanMemoryAccessCallback[2][2][kNumberOfAccessSizes];
573   // This array is indexed by AccessIsWrite and Experiment.
574   Function *AsanErrorCallbackSized[2][2];
575   Function *AsanMemoryAccessCallbackSized[2][2];
576   Function *AsanMemmove, *AsanMemcpy, *AsanMemset;
577   InlineAsm *EmptyAsm;
578   Value *LocalDynamicShadow;
579   GlobalsMetadata GlobalsMD;
580   DenseMap<const AllocaInst *, bool> ProcessedAllocas;
581 
582   friend struct FunctionStackPoisoner;
583 };
584 
585 class AddressSanitizerModule : public ModulePass {
586  public:
587   explicit AddressSanitizerModule(bool CompileKernel = false,
588                                   bool Recover = false)
589       : ModulePass(ID), CompileKernel(CompileKernel || ClEnableKasan),
590         Recover(Recover || ClRecover) {}
591   bool runOnModule(Module &M) override;
592   static char ID;  // Pass identification, replacement for typeid
593   StringRef getPassName() const override { return "AddressSanitizerModule"; }
594 
595 private:
596   void initializeCallbacks(Module &M);
597 
598   bool InstrumentGlobals(IRBuilder<> &IRB, Module &M);
599   bool ShouldInstrumentGlobal(GlobalVariable *G);
600   bool ShouldUseMachOGlobalsSection() const;
601   void poisonOneInitializer(Function &GlobalInit, GlobalValue *ModuleName);
602   void createInitializerPoisonCalls(Module &M, GlobalValue *ModuleName);
603   size_t MinRedzoneSizeForGlobal() const {
604     return RedzoneSizeForScale(Mapping.Scale);
605   }
606 
607   GlobalsMetadata GlobalsMD;
608   bool CompileKernel;
609   bool Recover;
610   Type *IntptrTy;
611   LLVMContext *C;
612   Triple TargetTriple;
613   ShadowMapping Mapping;
614   Function *AsanPoisonGlobals;
615   Function *AsanUnpoisonGlobals;
616   Function *AsanRegisterGlobals;
617   Function *AsanUnregisterGlobals;
618   Function *AsanRegisterImageGlobals;
619   Function *AsanUnregisterImageGlobals;
620 };
621 
622 // Stack poisoning does not play well with exception handling.
623 // When an exception is thrown, we essentially bypass the code
624 // that unpoisones the stack. This is why the run-time library has
625 // to intercept __cxa_throw (as well as longjmp, etc) and unpoison the entire
626 // stack in the interceptor. This however does not work inside the
627 // actual function which catches the exception. Most likely because the
628 // compiler hoists the load of the shadow value somewhere too high.
629 // This causes asan to report a non-existing bug on 453.povray.
630 // It sounds like an LLVM bug.
631 struct FunctionStackPoisoner : public InstVisitor<FunctionStackPoisoner> {
632   Function &F;
633   AddressSanitizer &ASan;
634   DIBuilder DIB;
635   LLVMContext *C;
636   Type *IntptrTy;
637   Type *IntptrPtrTy;
638   ShadowMapping Mapping;
639 
640   SmallVector<AllocaInst *, 16> AllocaVec;
641   SmallVector<AllocaInst *, 16> StaticAllocasToMoveUp;
642   SmallVector<Instruction *, 8> RetVec;
643   unsigned StackAlignment;
644 
645   Function *AsanStackMallocFunc[kMaxAsanStackMallocSizeClass + 1],
646       *AsanStackFreeFunc[kMaxAsanStackMallocSizeClass + 1];
647   Function *AsanSetShadowFunc[0x100] = {};
648   Function *AsanPoisonStackMemoryFunc, *AsanUnpoisonStackMemoryFunc;
649   Function *AsanAllocaPoisonFunc, *AsanAllocasUnpoisonFunc;
650 
651   // Stores a place and arguments of poisoning/unpoisoning call for alloca.
652   struct AllocaPoisonCall {
653     IntrinsicInst *InsBefore;
654     AllocaInst *AI;
655     uint64_t Size;
656     bool DoPoison;
657   };
658   SmallVector<AllocaPoisonCall, 8> DynamicAllocaPoisonCallVec;
659   SmallVector<AllocaPoisonCall, 8> StaticAllocaPoisonCallVec;
660 
661   SmallVector<AllocaInst *, 1> DynamicAllocaVec;
662   SmallVector<IntrinsicInst *, 1> StackRestoreVec;
663   AllocaInst *DynamicAllocaLayout = nullptr;
664   IntrinsicInst *LocalEscapeCall = nullptr;
665 
666   // Maps Value to an AllocaInst from which the Value is originated.
667   typedef DenseMap<Value *, AllocaInst *> AllocaForValueMapTy;
668   AllocaForValueMapTy AllocaForValue;
669 
670   bool HasNonEmptyInlineAsm = false;
671   bool HasReturnsTwiceCall = false;
672   std::unique_ptr<CallInst> EmptyInlineAsm;
673 
674   FunctionStackPoisoner(Function &F, AddressSanitizer &ASan)
675       : F(F),
676         ASan(ASan),
677         DIB(*F.getParent(), /*AllowUnresolved*/ false),
678         C(ASan.C),
679         IntptrTy(ASan.IntptrTy),
680         IntptrPtrTy(PointerType::get(IntptrTy, 0)),
681         Mapping(ASan.Mapping),
682         StackAlignment(1 << Mapping.Scale),
683         EmptyInlineAsm(CallInst::Create(ASan.EmptyAsm)) {}
684 
685   bool runOnFunction() {
686     if (!ClStack) return false;
687     // Collect alloca, ret, lifetime instructions etc.
688     for (BasicBlock *BB : depth_first(&F.getEntryBlock())) visit(*BB);
689 
690     if (AllocaVec.empty() && DynamicAllocaVec.empty()) return false;
691 
692     initializeCallbacks(*F.getParent());
693 
694     processDynamicAllocas();
695     processStaticAllocas();
696 
697     if (ClDebugStack) {
698       DEBUG(dbgs() << F);
699     }
700     return true;
701   }
702 
703   // Finds all Alloca instructions and puts
704   // poisoned red zones around all of them.
705   // Then unpoison everything back before the function returns.
706   void processStaticAllocas();
707   void processDynamicAllocas();
708 
709   void createDynamicAllocasInitStorage();
710 
711   // ----------------------- Visitors.
712   /// \brief Collect all Ret instructions.
713   void visitReturnInst(ReturnInst &RI) { RetVec.push_back(&RI); }
714 
715   /// \brief Collect all Resume instructions.
716   void visitResumeInst(ResumeInst &RI) { RetVec.push_back(&RI); }
717 
718   /// \brief Collect all CatchReturnInst instructions.
719   void visitCleanupReturnInst(CleanupReturnInst &CRI) { RetVec.push_back(&CRI); }
720 
721   void unpoisonDynamicAllocasBeforeInst(Instruction *InstBefore,
722                                         Value *SavedStack) {
723     IRBuilder<> IRB(InstBefore);
724     Value *DynamicAreaPtr = IRB.CreatePtrToInt(SavedStack, IntptrTy);
725     // When we insert _asan_allocas_unpoison before @llvm.stackrestore, we
726     // need to adjust extracted SP to compute the address of the most recent
727     // alloca. We have a special @llvm.get.dynamic.area.offset intrinsic for
728     // this purpose.
729     if (!isa<ReturnInst>(InstBefore)) {
730       Function *DynamicAreaOffsetFunc = Intrinsic::getDeclaration(
731           InstBefore->getModule(), Intrinsic::get_dynamic_area_offset,
732           {IntptrTy});
733 
734       Value *DynamicAreaOffset = IRB.CreateCall(DynamicAreaOffsetFunc, {});
735 
736       DynamicAreaPtr = IRB.CreateAdd(IRB.CreatePtrToInt(SavedStack, IntptrTy),
737                                      DynamicAreaOffset);
738     }
739 
740     IRB.CreateCall(AsanAllocasUnpoisonFunc,
741                    {IRB.CreateLoad(DynamicAllocaLayout), DynamicAreaPtr});
742   }
743 
744   // Unpoison dynamic allocas redzones.
745   void unpoisonDynamicAllocas() {
746     for (auto &Ret : RetVec)
747       unpoisonDynamicAllocasBeforeInst(Ret, DynamicAllocaLayout);
748 
749     for (auto &StackRestoreInst : StackRestoreVec)
750       unpoisonDynamicAllocasBeforeInst(StackRestoreInst,
751                                        StackRestoreInst->getOperand(0));
752   }
753 
754   // Deploy and poison redzones around dynamic alloca call. To do this, we
755   // should replace this call with another one with changed parameters and
756   // replace all its uses with new address, so
757   //   addr = alloca type, old_size, align
758   // is replaced by
759   //   new_size = (old_size + additional_size) * sizeof(type)
760   //   tmp = alloca i8, new_size, max(align, 32)
761   //   addr = tmp + 32 (first 32 bytes are for the left redzone).
762   // Additional_size is added to make new memory allocation contain not only
763   // requested memory, but also left, partial and right redzones.
764   void handleDynamicAllocaCall(AllocaInst *AI);
765 
766   /// \brief Collect Alloca instructions we want (and can) handle.
767   void visitAllocaInst(AllocaInst &AI) {
768     if (!ASan.isInterestingAlloca(AI)) {
769       if (AI.isStaticAlloca()) {
770         // Skip over allocas that are present *before* the first instrumented
771         // alloca, we don't want to move those around.
772         if (AllocaVec.empty())
773           return;
774 
775         StaticAllocasToMoveUp.push_back(&AI);
776       }
777       return;
778     }
779 
780     StackAlignment = std::max(StackAlignment, AI.getAlignment());
781     if (!AI.isStaticAlloca())
782       DynamicAllocaVec.push_back(&AI);
783     else
784       AllocaVec.push_back(&AI);
785   }
786 
787   /// \brief Collect lifetime intrinsic calls to check for use-after-scope
788   /// errors.
789   void visitIntrinsicInst(IntrinsicInst &II) {
790     Intrinsic::ID ID = II.getIntrinsicID();
791     if (ID == Intrinsic::stackrestore) StackRestoreVec.push_back(&II);
792     if (ID == Intrinsic::localescape) LocalEscapeCall = &II;
793     if (!ASan.UseAfterScope)
794       return;
795     if (ID != Intrinsic::lifetime_start && ID != Intrinsic::lifetime_end)
796       return;
797     // Found lifetime intrinsic, add ASan instrumentation if necessary.
798     ConstantInt *Size = dyn_cast<ConstantInt>(II.getArgOperand(0));
799     // If size argument is undefined, don't do anything.
800     if (Size->isMinusOne()) return;
801     // Check that size doesn't saturate uint64_t and can
802     // be stored in IntptrTy.
803     const uint64_t SizeValue = Size->getValue().getLimitedValue();
804     if (SizeValue == ~0ULL ||
805         !ConstantInt::isValueValidForType(IntptrTy, SizeValue))
806       return;
807     // Find alloca instruction that corresponds to llvm.lifetime argument.
808     AllocaInst *AI = findAllocaForValue(II.getArgOperand(1));
809     if (!AI || !ASan.isInterestingAlloca(*AI))
810       return;
811     bool DoPoison = (ID == Intrinsic::lifetime_end);
812     AllocaPoisonCall APC = {&II, AI, SizeValue, DoPoison};
813     if (AI->isStaticAlloca())
814       StaticAllocaPoisonCallVec.push_back(APC);
815     else if (ClInstrumentDynamicAllocas)
816       DynamicAllocaPoisonCallVec.push_back(APC);
817   }
818 
819   void visitCallSite(CallSite CS) {
820     Instruction *I = CS.getInstruction();
821     if (CallInst *CI = dyn_cast<CallInst>(I)) {
822       HasNonEmptyInlineAsm |=
823           CI->isInlineAsm() && !CI->isIdenticalTo(EmptyInlineAsm.get());
824       HasReturnsTwiceCall |= CI->canReturnTwice();
825     }
826   }
827 
828   // ---------------------- Helpers.
829   void initializeCallbacks(Module &M);
830 
831   bool doesDominateAllExits(const Instruction *I) const {
832     for (auto Ret : RetVec) {
833       if (!ASan.getDominatorTree().dominates(I, Ret)) return false;
834     }
835     return true;
836   }
837 
838   /// Finds alloca where the value comes from.
839   AllocaInst *findAllocaForValue(Value *V);
840 
841   // Copies bytes from ShadowBytes into shadow memory for indexes where
842   // ShadowMask is not zero. If ShadowMask[i] is zero, we assume that
843   // ShadowBytes[i] is constantly zero and doesn't need to be overwritten.
844   void copyToShadow(ArrayRef<uint8_t> ShadowMask, ArrayRef<uint8_t> ShadowBytes,
845                     IRBuilder<> &IRB, Value *ShadowBase);
846   void copyToShadow(ArrayRef<uint8_t> ShadowMask, ArrayRef<uint8_t> ShadowBytes,
847                     size_t Begin, size_t End, IRBuilder<> &IRB,
848                     Value *ShadowBase);
849   void copyToShadowInline(ArrayRef<uint8_t> ShadowMask,
850                           ArrayRef<uint8_t> ShadowBytes, size_t Begin,
851                           size_t End, IRBuilder<> &IRB, Value *ShadowBase);
852 
853   void poisonAlloca(Value *V, uint64_t Size, IRBuilder<> &IRB, bool DoPoison);
854 
855   Value *createAllocaForLayout(IRBuilder<> &IRB, const ASanStackFrameLayout &L,
856                                bool Dynamic);
857   PHINode *createPHI(IRBuilder<> &IRB, Value *Cond, Value *ValueIfTrue,
858                      Instruction *ThenTerm, Value *ValueIfFalse);
859 };
860 
861 } // anonymous namespace
862 
863 char AddressSanitizer::ID = 0;
864 INITIALIZE_PASS_BEGIN(
865     AddressSanitizer, "asan",
866     "AddressSanitizer: detects use-after-free and out-of-bounds bugs.", false,
867     false)
868 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
869 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
870 INITIALIZE_PASS_END(
871     AddressSanitizer, "asan",
872     "AddressSanitizer: detects use-after-free and out-of-bounds bugs.", false,
873     false)
874 FunctionPass *llvm::createAddressSanitizerFunctionPass(bool CompileKernel,
875                                                        bool Recover,
876                                                        bool UseAfterScope) {
877   assert(!CompileKernel || Recover);
878   return new AddressSanitizer(CompileKernel, Recover, UseAfterScope);
879 }
880 
881 char AddressSanitizerModule::ID = 0;
882 INITIALIZE_PASS(
883     AddressSanitizerModule, "asan-module",
884     "AddressSanitizer: detects use-after-free and out-of-bounds bugs."
885     "ModulePass",
886     false, false)
887 ModulePass *llvm::createAddressSanitizerModulePass(bool CompileKernel,
888                                                    bool Recover) {
889   assert(!CompileKernel || Recover);
890   return new AddressSanitizerModule(CompileKernel, Recover);
891 }
892 
893 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
894   size_t Res = countTrailingZeros(TypeSize / 8);
895   assert(Res < kNumberOfAccessSizes);
896   return Res;
897 }
898 
899 // \brief Create a constant for Str so that we can pass it to the run-time lib.
900 static GlobalVariable *createPrivateGlobalForString(Module &M, StringRef Str,
901                                                     bool AllowMerging) {
902   Constant *StrConst = ConstantDataArray::getString(M.getContext(), Str);
903   // We use private linkage for module-local strings. If they can be merged
904   // with another one, we set the unnamed_addr attribute.
905   GlobalVariable *GV =
906       new GlobalVariable(M, StrConst->getType(), true,
907                          GlobalValue::PrivateLinkage, StrConst, kAsanGenPrefix);
908   if (AllowMerging) GV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
909   GV->setAlignment(1);  // Strings may not be merged w/o setting align 1.
910   return GV;
911 }
912 
913 /// \brief Create a global describing a source location.
914 static GlobalVariable *createPrivateGlobalForSourceLoc(Module &M,
915                                                        LocationMetadata MD) {
916   Constant *LocData[] = {
917       createPrivateGlobalForString(M, MD.Filename, true),
918       ConstantInt::get(Type::getInt32Ty(M.getContext()), MD.LineNo),
919       ConstantInt::get(Type::getInt32Ty(M.getContext()), MD.ColumnNo),
920   };
921   auto LocStruct = ConstantStruct::getAnon(LocData);
922   auto GV = new GlobalVariable(M, LocStruct->getType(), true,
923                                GlobalValue::PrivateLinkage, LocStruct,
924                                kAsanGenPrefix);
925   GV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
926   return GV;
927 }
928 
929 /// \brief Check if \p G has been created by a trusted compiler pass.
930 static bool GlobalWasGeneratedByCompiler(GlobalVariable *G) {
931   // Do not instrument asan globals.
932   if (G->getName().startswith(kAsanGenPrefix) ||
933       G->getName().startswith(kSanCovGenPrefix) ||
934       G->getName().startswith(kODRGenPrefix))
935     return true;
936 
937   // Do not instrument gcov counter arrays.
938   if (G->getName() == "__llvm_gcov_ctr")
939     return true;
940 
941   return false;
942 }
943 
944 Value *AddressSanitizer::memToShadow(Value *Shadow, IRBuilder<> &IRB) {
945   // Shadow >> scale
946   Shadow = IRB.CreateLShr(Shadow, Mapping.Scale);
947   if (Mapping.Offset == 0) return Shadow;
948   // (Shadow >> scale) | offset
949   Value *ShadowBase;
950   if (LocalDynamicShadow)
951     ShadowBase = LocalDynamicShadow;
952   else
953     ShadowBase = ConstantInt::get(IntptrTy, Mapping.Offset);
954   if (Mapping.OrShadowOffset)
955     return IRB.CreateOr(Shadow, ShadowBase);
956   else
957     return IRB.CreateAdd(Shadow, ShadowBase);
958 }
959 
960 // Instrument memset/memmove/memcpy
961 void AddressSanitizer::instrumentMemIntrinsic(MemIntrinsic *MI) {
962   IRBuilder<> IRB(MI);
963   if (isa<MemTransferInst>(MI)) {
964     IRB.CreateCall(
965         isa<MemMoveInst>(MI) ? AsanMemmove : AsanMemcpy,
966         {IRB.CreatePointerCast(MI->getOperand(0), IRB.getInt8PtrTy()),
967          IRB.CreatePointerCast(MI->getOperand(1), IRB.getInt8PtrTy()),
968          IRB.CreateIntCast(MI->getOperand(2), IntptrTy, false)});
969   } else if (isa<MemSetInst>(MI)) {
970     IRB.CreateCall(
971         AsanMemset,
972         {IRB.CreatePointerCast(MI->getOperand(0), IRB.getInt8PtrTy()),
973          IRB.CreateIntCast(MI->getOperand(1), IRB.getInt32Ty(), false),
974          IRB.CreateIntCast(MI->getOperand(2), IntptrTy, false)});
975   }
976   MI->eraseFromParent();
977 }
978 
979 /// Check if we want (and can) handle this alloca.
980 bool AddressSanitizer::isInterestingAlloca(const AllocaInst &AI) {
981   auto PreviouslySeenAllocaInfo = ProcessedAllocas.find(&AI);
982 
983   if (PreviouslySeenAllocaInfo != ProcessedAllocas.end())
984     return PreviouslySeenAllocaInfo->getSecond();
985 
986   bool IsInteresting =
987       (AI.getAllocatedType()->isSized() &&
988        // alloca() may be called with 0 size, ignore it.
989        ((!AI.isStaticAlloca()) || getAllocaSizeInBytes(AI) > 0) &&
990        // We are only interested in allocas not promotable to registers.
991        // Promotable allocas are common under -O0.
992        (!ClSkipPromotableAllocas || !isAllocaPromotable(&AI)) &&
993        // inalloca allocas are not treated as static, and we don't want
994        // dynamic alloca instrumentation for them as well.
995        !AI.isUsedWithInAlloca());
996 
997   ProcessedAllocas[&AI] = IsInteresting;
998   return IsInteresting;
999 }
1000 
1001 /// If I is an interesting memory access, return the PointerOperand
1002 /// and set IsWrite/Alignment. Otherwise return nullptr.
1003 Value *AddressSanitizer::isInterestingMemoryAccess(Instruction *I,
1004                                                    bool *IsWrite,
1005                                                    uint64_t *TypeSize,
1006                                                    unsigned *Alignment) {
1007   // Skip memory accesses inserted by another instrumentation.
1008   if (I->getMetadata("nosanitize")) return nullptr;
1009 
1010   // Do not instrument the load fetching the dynamic shadow address.
1011   if (LocalDynamicShadow == I)
1012     return nullptr;
1013 
1014   Value *PtrOperand = nullptr;
1015   const DataLayout &DL = I->getModule()->getDataLayout();
1016   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
1017     if (!ClInstrumentReads) return nullptr;
1018     *IsWrite = false;
1019     *TypeSize = DL.getTypeStoreSizeInBits(LI->getType());
1020     *Alignment = LI->getAlignment();
1021     PtrOperand = LI->getPointerOperand();
1022   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
1023     if (!ClInstrumentWrites) return nullptr;
1024     *IsWrite = true;
1025     *TypeSize = DL.getTypeStoreSizeInBits(SI->getValueOperand()->getType());
1026     *Alignment = SI->getAlignment();
1027     PtrOperand = SI->getPointerOperand();
1028   } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
1029     if (!ClInstrumentAtomics) return nullptr;
1030     *IsWrite = true;
1031     *TypeSize = DL.getTypeStoreSizeInBits(RMW->getValOperand()->getType());
1032     *Alignment = 0;
1033     PtrOperand = RMW->getPointerOperand();
1034   } else if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) {
1035     if (!ClInstrumentAtomics) return nullptr;
1036     *IsWrite = true;
1037     *TypeSize = DL.getTypeStoreSizeInBits(XCHG->getCompareOperand()->getType());
1038     *Alignment = 0;
1039     PtrOperand = XCHG->getPointerOperand();
1040   }
1041 
1042   // Do not instrument acesses from different address spaces; we cannot deal
1043   // with them.
1044   if (PtrOperand) {
1045     Type *PtrTy = cast<PointerType>(PtrOperand->getType()->getScalarType());
1046     if (PtrTy->getPointerAddressSpace() != 0)
1047       return nullptr;
1048   }
1049 
1050   // Treat memory accesses to promotable allocas as non-interesting since they
1051   // will not cause memory violations. This greatly speeds up the instrumented
1052   // executable at -O0.
1053   if (ClSkipPromotableAllocas)
1054     if (auto AI = dyn_cast_or_null<AllocaInst>(PtrOperand))
1055       return isInterestingAlloca(*AI) ? AI : nullptr;
1056 
1057   return PtrOperand;
1058 }
1059 
1060 static bool isPointerOperand(Value *V) {
1061   return V->getType()->isPointerTy() || isa<PtrToIntInst>(V);
1062 }
1063 
1064 // This is a rough heuristic; it may cause both false positives and
1065 // false negatives. The proper implementation requires cooperation with
1066 // the frontend.
1067 static bool isInterestingPointerComparisonOrSubtraction(Instruction *I) {
1068   if (ICmpInst *Cmp = dyn_cast<ICmpInst>(I)) {
1069     if (!Cmp->isRelational()) return false;
1070   } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1071     if (BO->getOpcode() != Instruction::Sub) return false;
1072   } else {
1073     return false;
1074   }
1075   return isPointerOperand(I->getOperand(0)) &&
1076          isPointerOperand(I->getOperand(1));
1077 }
1078 
1079 bool AddressSanitizer::GlobalIsLinkerInitialized(GlobalVariable *G) {
1080   // If a global variable does not have dynamic initialization we don't
1081   // have to instrument it.  However, if a global does not have initializer
1082   // at all, we assume it has dynamic initializer (in other TU).
1083   return G->hasInitializer() && !GlobalsMD.get(G).IsDynInit;
1084 }
1085 
1086 void AddressSanitizer::instrumentPointerComparisonOrSubtraction(
1087     Instruction *I) {
1088   IRBuilder<> IRB(I);
1089   Function *F = isa<ICmpInst>(I) ? AsanPtrCmpFunction : AsanPtrSubFunction;
1090   Value *Param[2] = {I->getOperand(0), I->getOperand(1)};
1091   for (Value *&i : Param) {
1092     if (i->getType()->isPointerTy())
1093       i = IRB.CreatePointerCast(i, IntptrTy);
1094   }
1095   IRB.CreateCall(F, Param);
1096 }
1097 
1098 void AddressSanitizer::instrumentMop(ObjectSizeOffsetVisitor &ObjSizeVis,
1099                                      Instruction *I, bool UseCalls,
1100                                      const DataLayout &DL) {
1101   bool IsWrite = false;
1102   unsigned Alignment = 0;
1103   uint64_t TypeSize = 0;
1104   Value *Addr = isInterestingMemoryAccess(I, &IsWrite, &TypeSize, &Alignment);
1105   assert(Addr);
1106 
1107   // Optimization experiments.
1108   // The experiments can be used to evaluate potential optimizations that remove
1109   // instrumentation (assess false negatives). Instead of completely removing
1110   // some instrumentation, you set Exp to a non-zero value (mask of optimization
1111   // experiments that want to remove instrumentation of this instruction).
1112   // If Exp is non-zero, this pass will emit special calls into runtime
1113   // (e.g. __asan_report_exp_load1 instead of __asan_report_load1). These calls
1114   // make runtime terminate the program in a special way (with a different
1115   // exit status). Then you run the new compiler on a buggy corpus, collect
1116   // the special terminations (ideally, you don't see them at all -- no false
1117   // negatives) and make the decision on the optimization.
1118   uint32_t Exp = ClForceExperiment;
1119 
1120   if (ClOpt && ClOptGlobals) {
1121     // If initialization order checking is disabled, a simple access to a
1122     // dynamically initialized global is always valid.
1123     GlobalVariable *G = dyn_cast<GlobalVariable>(GetUnderlyingObject(Addr, DL));
1124     if (G && (!ClInitializers || GlobalIsLinkerInitialized(G)) &&
1125         isSafeAccess(ObjSizeVis, Addr, TypeSize)) {
1126       NumOptimizedAccessesToGlobalVar++;
1127       return;
1128     }
1129   }
1130 
1131   if (ClOpt && ClOptStack) {
1132     // A direct inbounds access to a stack variable is always valid.
1133     if (isa<AllocaInst>(GetUnderlyingObject(Addr, DL)) &&
1134         isSafeAccess(ObjSizeVis, Addr, TypeSize)) {
1135       NumOptimizedAccessesToStackVar++;
1136       return;
1137     }
1138   }
1139 
1140   if (IsWrite)
1141     NumInstrumentedWrites++;
1142   else
1143     NumInstrumentedReads++;
1144 
1145   unsigned Granularity = 1 << Mapping.Scale;
1146   // Instrument a 1-, 2-, 4-, 8-, or 16- byte access with one check
1147   // if the data is properly aligned.
1148   if ((TypeSize == 8 || TypeSize == 16 || TypeSize == 32 || TypeSize == 64 ||
1149        TypeSize == 128) &&
1150       (Alignment >= Granularity || Alignment == 0 || Alignment >= TypeSize / 8))
1151     return instrumentAddress(I, I, Addr, TypeSize, IsWrite, nullptr, UseCalls,
1152                              Exp);
1153   instrumentUnusualSizeOrAlignment(I, Addr, TypeSize, IsWrite, nullptr,
1154                                    UseCalls, Exp);
1155 }
1156 
1157 Instruction *AddressSanitizer::generateCrashCode(Instruction *InsertBefore,
1158                                                  Value *Addr, bool IsWrite,
1159                                                  size_t AccessSizeIndex,
1160                                                  Value *SizeArgument,
1161                                                  uint32_t Exp) {
1162   IRBuilder<> IRB(InsertBefore);
1163   Value *ExpVal = Exp == 0 ? nullptr : ConstantInt::get(IRB.getInt32Ty(), Exp);
1164   CallInst *Call = nullptr;
1165   if (SizeArgument) {
1166     if (Exp == 0)
1167       Call = IRB.CreateCall(AsanErrorCallbackSized[IsWrite][0],
1168                             {Addr, SizeArgument});
1169     else
1170       Call = IRB.CreateCall(AsanErrorCallbackSized[IsWrite][1],
1171                             {Addr, SizeArgument, ExpVal});
1172   } else {
1173     if (Exp == 0)
1174       Call =
1175           IRB.CreateCall(AsanErrorCallback[IsWrite][0][AccessSizeIndex], Addr);
1176     else
1177       Call = IRB.CreateCall(AsanErrorCallback[IsWrite][1][AccessSizeIndex],
1178                             {Addr, ExpVal});
1179   }
1180 
1181   // We don't do Call->setDoesNotReturn() because the BB already has
1182   // UnreachableInst at the end.
1183   // This EmptyAsm is required to avoid callback merge.
1184   IRB.CreateCall(EmptyAsm, {});
1185   return Call;
1186 }
1187 
1188 Value *AddressSanitizer::createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong,
1189                                            Value *ShadowValue,
1190                                            uint32_t TypeSize) {
1191   size_t Granularity = static_cast<size_t>(1) << Mapping.Scale;
1192   // Addr & (Granularity - 1)
1193   Value *LastAccessedByte =
1194       IRB.CreateAnd(AddrLong, ConstantInt::get(IntptrTy, Granularity - 1));
1195   // (Addr & (Granularity - 1)) + size - 1
1196   if (TypeSize / 8 > 1)
1197     LastAccessedByte = IRB.CreateAdd(
1198         LastAccessedByte, ConstantInt::get(IntptrTy, TypeSize / 8 - 1));
1199   // (uint8_t) ((Addr & (Granularity-1)) + size - 1)
1200   LastAccessedByte =
1201       IRB.CreateIntCast(LastAccessedByte, ShadowValue->getType(), false);
1202   // ((uint8_t) ((Addr & (Granularity-1)) + size - 1)) >= ShadowValue
1203   return IRB.CreateICmpSGE(LastAccessedByte, ShadowValue);
1204 }
1205 
1206 void AddressSanitizer::instrumentAddress(Instruction *OrigIns,
1207                                          Instruction *InsertBefore, Value *Addr,
1208                                          uint32_t TypeSize, bool IsWrite,
1209                                          Value *SizeArgument, bool UseCalls,
1210                                          uint32_t Exp) {
1211   IRBuilder<> IRB(InsertBefore);
1212   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
1213   size_t AccessSizeIndex = TypeSizeToSizeIndex(TypeSize);
1214 
1215   if (UseCalls) {
1216     if (Exp == 0)
1217       IRB.CreateCall(AsanMemoryAccessCallback[IsWrite][0][AccessSizeIndex],
1218                      AddrLong);
1219     else
1220       IRB.CreateCall(AsanMemoryAccessCallback[IsWrite][1][AccessSizeIndex],
1221                      {AddrLong, ConstantInt::get(IRB.getInt32Ty(), Exp)});
1222     return;
1223   }
1224 
1225   Type *ShadowTy =
1226       IntegerType::get(*C, std::max(8U, TypeSize >> Mapping.Scale));
1227   Type *ShadowPtrTy = PointerType::get(ShadowTy, 0);
1228   Value *ShadowPtr = memToShadow(AddrLong, IRB);
1229   Value *CmpVal = Constant::getNullValue(ShadowTy);
1230   Value *ShadowValue =
1231       IRB.CreateLoad(IRB.CreateIntToPtr(ShadowPtr, ShadowPtrTy));
1232 
1233   Value *Cmp = IRB.CreateICmpNE(ShadowValue, CmpVal);
1234   size_t Granularity = 1ULL << Mapping.Scale;
1235   TerminatorInst *CrashTerm = nullptr;
1236 
1237   if (ClAlwaysSlowPath || (TypeSize < 8 * Granularity)) {
1238     // We use branch weights for the slow path check, to indicate that the slow
1239     // path is rarely taken. This seems to be the case for SPEC benchmarks.
1240     TerminatorInst *CheckTerm = SplitBlockAndInsertIfThen(
1241         Cmp, InsertBefore, false, MDBuilder(*C).createBranchWeights(1, 100000));
1242     assert(cast<BranchInst>(CheckTerm)->isUnconditional());
1243     BasicBlock *NextBB = CheckTerm->getSuccessor(0);
1244     IRB.SetInsertPoint(CheckTerm);
1245     Value *Cmp2 = createSlowPathCmp(IRB, AddrLong, ShadowValue, TypeSize);
1246     if (Recover) {
1247       CrashTerm = SplitBlockAndInsertIfThen(Cmp2, CheckTerm, false);
1248     } else {
1249       BasicBlock *CrashBlock =
1250         BasicBlock::Create(*C, "", NextBB->getParent(), NextBB);
1251       CrashTerm = new UnreachableInst(*C, CrashBlock);
1252       BranchInst *NewTerm = BranchInst::Create(CrashBlock, NextBB, Cmp2);
1253       ReplaceInstWithInst(CheckTerm, NewTerm);
1254     }
1255   } else {
1256     CrashTerm = SplitBlockAndInsertIfThen(Cmp, InsertBefore, !Recover);
1257   }
1258 
1259   Instruction *Crash = generateCrashCode(CrashTerm, AddrLong, IsWrite,
1260                                          AccessSizeIndex, SizeArgument, Exp);
1261   Crash->setDebugLoc(OrigIns->getDebugLoc());
1262 }
1263 
1264 // Instrument unusual size or unusual alignment.
1265 // We can not do it with a single check, so we do 1-byte check for the first
1266 // and the last bytes. We call __asan_report_*_n(addr, real_size) to be able
1267 // to report the actual access size.
1268 void AddressSanitizer::instrumentUnusualSizeOrAlignment(
1269     Instruction *I, Value *Addr, uint32_t TypeSize, bool IsWrite,
1270     Value *SizeArgument, bool UseCalls, uint32_t Exp) {
1271   IRBuilder<> IRB(I);
1272   Value *Size = ConstantInt::get(IntptrTy, TypeSize / 8);
1273   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
1274   if (UseCalls) {
1275     if (Exp == 0)
1276       IRB.CreateCall(AsanMemoryAccessCallbackSized[IsWrite][0],
1277                      {AddrLong, Size});
1278     else
1279       IRB.CreateCall(AsanMemoryAccessCallbackSized[IsWrite][1],
1280                      {AddrLong, Size, ConstantInt::get(IRB.getInt32Ty(), Exp)});
1281   } else {
1282     Value *LastByte = IRB.CreateIntToPtr(
1283         IRB.CreateAdd(AddrLong, ConstantInt::get(IntptrTy, TypeSize / 8 - 1)),
1284         Addr->getType());
1285     instrumentAddress(I, I, Addr, 8, IsWrite, Size, false, Exp);
1286     instrumentAddress(I, I, LastByte, 8, IsWrite, Size, false, Exp);
1287   }
1288 }
1289 
1290 void AddressSanitizerModule::poisonOneInitializer(Function &GlobalInit,
1291                                                   GlobalValue *ModuleName) {
1292   // Set up the arguments to our poison/unpoison functions.
1293   IRBuilder<> IRB(&GlobalInit.front(),
1294                   GlobalInit.front().getFirstInsertionPt());
1295 
1296   // Add a call to poison all external globals before the given function starts.
1297   Value *ModuleNameAddr = ConstantExpr::getPointerCast(ModuleName, IntptrTy);
1298   IRB.CreateCall(AsanPoisonGlobals, ModuleNameAddr);
1299 
1300   // Add calls to unpoison all globals before each return instruction.
1301   for (auto &BB : GlobalInit.getBasicBlockList())
1302     if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
1303       CallInst::Create(AsanUnpoisonGlobals, "", RI);
1304 }
1305 
1306 void AddressSanitizerModule::createInitializerPoisonCalls(
1307     Module &M, GlobalValue *ModuleName) {
1308   GlobalVariable *GV = M.getGlobalVariable("llvm.global_ctors");
1309 
1310   ConstantArray *CA = cast<ConstantArray>(GV->getInitializer());
1311   for (Use &OP : CA->operands()) {
1312     if (isa<ConstantAggregateZero>(OP)) continue;
1313     ConstantStruct *CS = cast<ConstantStruct>(OP);
1314 
1315     // Must have a function or null ptr.
1316     if (Function *F = dyn_cast<Function>(CS->getOperand(1))) {
1317       if (F->getName() == kAsanModuleCtorName) continue;
1318       ConstantInt *Priority = dyn_cast<ConstantInt>(CS->getOperand(0));
1319       // Don't instrument CTORs that will run before asan.module_ctor.
1320       if (Priority->getLimitedValue() <= kAsanCtorAndDtorPriority) continue;
1321       poisonOneInitializer(*F, ModuleName);
1322     }
1323   }
1324 }
1325 
1326 bool AddressSanitizerModule::ShouldInstrumentGlobal(GlobalVariable *G) {
1327   Type *Ty = G->getValueType();
1328   DEBUG(dbgs() << "GLOBAL: " << *G << "\n");
1329 
1330   if (GlobalsMD.get(G).IsBlacklisted) return false;
1331   if (!Ty->isSized()) return false;
1332   if (!G->hasInitializer()) return false;
1333   if (GlobalWasGeneratedByCompiler(G)) return false; // Our own globals.
1334   // Touch only those globals that will not be defined in other modules.
1335   // Don't handle ODR linkage types and COMDATs since other modules may be built
1336   // without ASan.
1337   if (G->getLinkage() != GlobalVariable::ExternalLinkage &&
1338       G->getLinkage() != GlobalVariable::PrivateLinkage &&
1339       G->getLinkage() != GlobalVariable::InternalLinkage)
1340     return false;
1341   if (G->hasComdat()) return false;
1342   // Two problems with thread-locals:
1343   //   - The address of the main thread's copy can't be computed at link-time.
1344   //   - Need to poison all copies, not just the main thread's one.
1345   if (G->isThreadLocal()) return false;
1346   // For now, just ignore this Global if the alignment is large.
1347   if (G->getAlignment() > MinRedzoneSizeForGlobal()) return false;
1348 
1349   if (G->hasSection()) {
1350     StringRef Section = G->getSection();
1351 
1352     // Globals from llvm.metadata aren't emitted, do not instrument them.
1353     if (Section == "llvm.metadata") return false;
1354     // Do not instrument globals from special LLVM sections.
1355     if (Section.find("__llvm") != StringRef::npos || Section.find("__LLVM") != StringRef::npos) return false;
1356 
1357     // Do not instrument function pointers to initialization and termination
1358     // routines: dynamic linker will not properly handle redzones.
1359     if (Section.startswith(".preinit_array") ||
1360         Section.startswith(".init_array") ||
1361         Section.startswith(".fini_array")) {
1362       return false;
1363     }
1364 
1365     // Callbacks put into the CRT initializer/terminator sections
1366     // should not be instrumented.
1367     // See https://code.google.com/p/address-sanitizer/issues/detail?id=305
1368     // and http://msdn.microsoft.com/en-US/en-en/library/bb918180(v=vs.120).aspx
1369     if (Section.startswith(".CRT")) {
1370       DEBUG(dbgs() << "Ignoring a global initializer callback: " << *G << "\n");
1371       return false;
1372     }
1373 
1374     if (TargetTriple.isOSBinFormatMachO()) {
1375       StringRef ParsedSegment, ParsedSection;
1376       unsigned TAA = 0, StubSize = 0;
1377       bool TAAParsed;
1378       std::string ErrorCode = MCSectionMachO::ParseSectionSpecifier(
1379           Section, ParsedSegment, ParsedSection, TAA, TAAParsed, StubSize);
1380       assert(ErrorCode.empty() && "Invalid section specifier.");
1381 
1382       // Ignore the globals from the __OBJC section. The ObjC runtime assumes
1383       // those conform to /usr/lib/objc/runtime.h, so we can't add redzones to
1384       // them.
1385       if (ParsedSegment == "__OBJC" ||
1386           (ParsedSegment == "__DATA" && ParsedSection.startswith("__objc_"))) {
1387         DEBUG(dbgs() << "Ignoring ObjC runtime global: " << *G << "\n");
1388         return false;
1389       }
1390       // See http://code.google.com/p/address-sanitizer/issues/detail?id=32
1391       // Constant CFString instances are compiled in the following way:
1392       //  -- the string buffer is emitted into
1393       //     __TEXT,__cstring,cstring_literals
1394       //  -- the constant NSConstantString structure referencing that buffer
1395       //     is placed into __DATA,__cfstring
1396       // Therefore there's no point in placing redzones into __DATA,__cfstring.
1397       // Moreover, it causes the linker to crash on OS X 10.7
1398       if (ParsedSegment == "__DATA" && ParsedSection == "__cfstring") {
1399         DEBUG(dbgs() << "Ignoring CFString: " << *G << "\n");
1400         return false;
1401       }
1402       // The linker merges the contents of cstring_literals and removes the
1403       // trailing zeroes.
1404       if (ParsedSegment == "__TEXT" && (TAA & MachO::S_CSTRING_LITERALS)) {
1405         DEBUG(dbgs() << "Ignoring a cstring literal: " << *G << "\n");
1406         return false;
1407       }
1408     }
1409   }
1410 
1411   return true;
1412 }
1413 
1414 // On Mach-O platforms, we emit global metadata in a separate section of the
1415 // binary in order to allow the linker to properly dead strip. This is only
1416 // supported on recent versions of ld64.
1417 bool AddressSanitizerModule::ShouldUseMachOGlobalsSection() const {
1418   if (!ClUseMachOGlobalsSection)
1419     return false;
1420 
1421   if (!TargetTriple.isOSBinFormatMachO())
1422     return false;
1423 
1424   if (TargetTriple.isMacOSX() && !TargetTriple.isMacOSXVersionLT(10, 11))
1425     return true;
1426   if (TargetTriple.isiOS() /* or tvOS */ && !TargetTriple.isOSVersionLT(9))
1427     return true;
1428   if (TargetTriple.isWatchOS() && !TargetTriple.isOSVersionLT(2))
1429     return true;
1430 
1431   return false;
1432 }
1433 
1434 void AddressSanitizerModule::initializeCallbacks(Module &M) {
1435   IRBuilder<> IRB(*C);
1436 
1437   // Declare our poisoning and unpoisoning functions.
1438   AsanPoisonGlobals = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1439       kAsanPoisonGlobalsName, IRB.getVoidTy(), IntptrTy, nullptr));
1440   AsanPoisonGlobals->setLinkage(Function::ExternalLinkage);
1441   AsanUnpoisonGlobals = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1442       kAsanUnpoisonGlobalsName, IRB.getVoidTy(), nullptr));
1443   AsanUnpoisonGlobals->setLinkage(Function::ExternalLinkage);
1444 
1445   // Declare functions that register/unregister globals.
1446   AsanRegisterGlobals = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1447       kAsanRegisterGlobalsName, IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
1448   AsanRegisterGlobals->setLinkage(Function::ExternalLinkage);
1449   AsanUnregisterGlobals = checkSanitizerInterfaceFunction(
1450       M.getOrInsertFunction(kAsanUnregisterGlobalsName, IRB.getVoidTy(),
1451                             IntptrTy, IntptrTy, nullptr));
1452   AsanUnregisterGlobals->setLinkage(Function::ExternalLinkage);
1453 
1454   // Declare the functions that find globals in a shared object and then invoke
1455   // the (un)register function on them.
1456   AsanRegisterImageGlobals = checkSanitizerInterfaceFunction(
1457       M.getOrInsertFunction(kAsanRegisterImageGlobalsName,
1458       IRB.getVoidTy(), IntptrTy, nullptr));
1459   AsanRegisterImageGlobals->setLinkage(Function::ExternalLinkage);
1460 
1461   AsanUnregisterImageGlobals = checkSanitizerInterfaceFunction(
1462       M.getOrInsertFunction(kAsanUnregisterImageGlobalsName,
1463       IRB.getVoidTy(), IntptrTy, nullptr));
1464   AsanUnregisterImageGlobals->setLinkage(Function::ExternalLinkage);
1465 }
1466 
1467 // This function replaces all global variables with new variables that have
1468 // trailing redzones. It also creates a function that poisons
1469 // redzones and inserts this function into llvm.global_ctors.
1470 bool AddressSanitizerModule::InstrumentGlobals(IRBuilder<> &IRB, Module &M) {
1471   GlobalsMD.init(M);
1472 
1473   SmallVector<GlobalVariable *, 16> GlobalsToChange;
1474 
1475   for (auto &G : M.globals()) {
1476     if (ShouldInstrumentGlobal(&G)) GlobalsToChange.push_back(&G);
1477   }
1478 
1479   size_t n = GlobalsToChange.size();
1480   if (n == 0) return false;
1481 
1482   // A global is described by a structure
1483   //   size_t beg;
1484   //   size_t size;
1485   //   size_t size_with_redzone;
1486   //   const char *name;
1487   //   const char *module_name;
1488   //   size_t has_dynamic_init;
1489   //   void *source_location;
1490   //   size_t odr_indicator;
1491   // We initialize an array of such structures and pass it to a run-time call.
1492   StructType *GlobalStructTy =
1493       StructType::get(IntptrTy, IntptrTy, IntptrTy, IntptrTy, IntptrTy,
1494                       IntptrTy, IntptrTy, IntptrTy, nullptr);
1495   SmallVector<Constant *, 16> Initializers(n);
1496 
1497   bool HasDynamicallyInitializedGlobals = false;
1498 
1499   // We shouldn't merge same module names, as this string serves as unique
1500   // module ID in runtime.
1501   GlobalVariable *ModuleName = createPrivateGlobalForString(
1502       M, M.getModuleIdentifier(), /*AllowMerging*/ false);
1503 
1504   auto &DL = M.getDataLayout();
1505   for (size_t i = 0; i < n; i++) {
1506     static const uint64_t kMaxGlobalRedzone = 1 << 18;
1507     GlobalVariable *G = GlobalsToChange[i];
1508 
1509     auto MD = GlobalsMD.get(G);
1510     StringRef NameForGlobal = G->getName();
1511     // Create string holding the global name (use global name from metadata
1512     // if it's available, otherwise just write the name of global variable).
1513     GlobalVariable *Name = createPrivateGlobalForString(
1514         M, MD.Name.empty() ? NameForGlobal : MD.Name,
1515         /*AllowMerging*/ true);
1516 
1517     Type *Ty = G->getValueType();
1518     uint64_t SizeInBytes = DL.getTypeAllocSize(Ty);
1519     uint64_t MinRZ = MinRedzoneSizeForGlobal();
1520     // MinRZ <= RZ <= kMaxGlobalRedzone
1521     // and trying to make RZ to be ~ 1/4 of SizeInBytes.
1522     uint64_t RZ = std::max(
1523         MinRZ, std::min(kMaxGlobalRedzone, (SizeInBytes / MinRZ / 4) * MinRZ));
1524     uint64_t RightRedzoneSize = RZ;
1525     // Round up to MinRZ
1526     if (SizeInBytes % MinRZ) RightRedzoneSize += MinRZ - (SizeInBytes % MinRZ);
1527     assert(((RightRedzoneSize + SizeInBytes) % MinRZ) == 0);
1528     Type *RightRedZoneTy = ArrayType::get(IRB.getInt8Ty(), RightRedzoneSize);
1529 
1530     StructType *NewTy = StructType::get(Ty, RightRedZoneTy, nullptr);
1531     Constant *NewInitializer =
1532         ConstantStruct::get(NewTy, G->getInitializer(),
1533                             Constant::getNullValue(RightRedZoneTy), nullptr);
1534 
1535     // Create a new global variable with enough space for a redzone.
1536     GlobalValue::LinkageTypes Linkage = G->getLinkage();
1537     if (G->isConstant() && Linkage == GlobalValue::PrivateLinkage)
1538       Linkage = GlobalValue::InternalLinkage;
1539     GlobalVariable *NewGlobal =
1540         new GlobalVariable(M, NewTy, G->isConstant(), Linkage, NewInitializer,
1541                            "", G, G->getThreadLocalMode());
1542     NewGlobal->copyAttributesFrom(G);
1543     NewGlobal->setAlignment(MinRZ);
1544 
1545     // Move null-terminated C strings to "__asan_cstring" section on Darwin.
1546     if (TargetTriple.isOSBinFormatMachO() && !G->hasSection() &&
1547         G->isConstant()) {
1548       auto Seq = dyn_cast<ConstantDataSequential>(G->getInitializer());
1549       if (Seq && Seq->isCString())
1550         NewGlobal->setSection("__TEXT,__asan_cstring,regular");
1551     }
1552 
1553     // Transfer the debug info.  The payload starts at offset zero so we can
1554     // copy the debug info over as is.
1555     SmallVector<DIGlobalVariable *, 1> GVs;
1556     G->getDebugInfo(GVs);
1557     for (auto *GV : GVs)
1558       NewGlobal->addDebugInfo(GV);
1559 
1560     Value *Indices2[2];
1561     Indices2[0] = IRB.getInt32(0);
1562     Indices2[1] = IRB.getInt32(0);
1563 
1564     G->replaceAllUsesWith(
1565         ConstantExpr::getGetElementPtr(NewTy, NewGlobal, Indices2, true));
1566     NewGlobal->takeName(G);
1567     G->eraseFromParent();
1568 
1569     Constant *SourceLoc;
1570     if (!MD.SourceLoc.empty()) {
1571       auto SourceLocGlobal = createPrivateGlobalForSourceLoc(M, MD.SourceLoc);
1572       SourceLoc = ConstantExpr::getPointerCast(SourceLocGlobal, IntptrTy);
1573     } else {
1574       SourceLoc = ConstantInt::get(IntptrTy, 0);
1575     }
1576 
1577     Constant *ODRIndicator = ConstantExpr::getNullValue(IRB.getInt8PtrTy());
1578     GlobalValue *InstrumentedGlobal = NewGlobal;
1579 
1580     bool CanUsePrivateAliases =
1581         TargetTriple.isOSBinFormatELF() || TargetTriple.isOSBinFormatMachO();
1582     if (CanUsePrivateAliases && ClUsePrivateAliasForGlobals) {
1583       // Create local alias for NewGlobal to avoid crash on ODR between
1584       // instrumented and non-instrumented libraries.
1585       auto *GA = GlobalAlias::create(GlobalValue::InternalLinkage,
1586                                      NameForGlobal + M.getName(), NewGlobal);
1587 
1588       // With local aliases, we need to provide another externally visible
1589       // symbol __odr_asan_XXX to detect ODR violation.
1590       auto *ODRIndicatorSym =
1591           new GlobalVariable(M, IRB.getInt8Ty(), false, Linkage,
1592                              Constant::getNullValue(IRB.getInt8Ty()),
1593                              kODRGenPrefix + NameForGlobal, nullptr,
1594                              NewGlobal->getThreadLocalMode());
1595 
1596       // Set meaningful attributes for indicator symbol.
1597       ODRIndicatorSym->setVisibility(NewGlobal->getVisibility());
1598       ODRIndicatorSym->setDLLStorageClass(NewGlobal->getDLLStorageClass());
1599       ODRIndicatorSym->setAlignment(1);
1600       ODRIndicator = ODRIndicatorSym;
1601       InstrumentedGlobal = GA;
1602     }
1603 
1604     Initializers[i] = ConstantStruct::get(
1605         GlobalStructTy,
1606         ConstantExpr::getPointerCast(InstrumentedGlobal, IntptrTy),
1607         ConstantInt::get(IntptrTy, SizeInBytes),
1608         ConstantInt::get(IntptrTy, SizeInBytes + RightRedzoneSize),
1609         ConstantExpr::getPointerCast(Name, IntptrTy),
1610         ConstantExpr::getPointerCast(ModuleName, IntptrTy),
1611         ConstantInt::get(IntptrTy, MD.IsDynInit), SourceLoc,
1612         ConstantExpr::getPointerCast(ODRIndicator, IntptrTy), nullptr);
1613 
1614     if (ClInitializers && MD.IsDynInit) HasDynamicallyInitializedGlobals = true;
1615 
1616     DEBUG(dbgs() << "NEW GLOBAL: " << *NewGlobal << "\n");
1617   }
1618 
1619 
1620   GlobalVariable *AllGlobals = nullptr;
1621   GlobalVariable *RegisteredFlag = nullptr;
1622 
1623   // On recent Mach-O platforms, we emit the global metadata in a way that
1624   // allows the linker to properly strip dead globals.
1625   if (ShouldUseMachOGlobalsSection()) {
1626     // RegisteredFlag serves two purposes. First, we can pass it to dladdr()
1627     // to look up the loaded image that contains it. Second, we can store in it
1628     // whether registration has already occurred, to prevent duplicate
1629     // registration.
1630     //
1631     // Common linkage allows us to coalesce needles defined in each object
1632     // file so that there's only one per shared library.
1633     RegisteredFlag = new GlobalVariable(
1634         M, IntptrTy, false, GlobalVariable::CommonLinkage,
1635         ConstantInt::get(IntptrTy, 0), kAsanGlobalsRegisteredFlagName);
1636 
1637     // We also emit a structure which binds the liveness of the global
1638     // variable to the metadata struct.
1639     StructType *LivenessTy = StructType::get(IntptrTy, IntptrTy, nullptr);
1640 
1641     // Keep the list of "Liveness" GV created to be added to llvm.compiler.used
1642     SmallVector<GlobalValue *, 16> LivenessGlobals;
1643     LivenessGlobals.reserve(n);
1644 
1645     for (size_t i = 0; i < n; i++) {
1646       GlobalVariable *Metadata = new GlobalVariable(
1647           M, GlobalStructTy, false, GlobalVariable::InternalLinkage,
1648           Initializers[i], "");
1649       Metadata->setSection("__DATA,__asan_globals,regular");
1650       Metadata->setAlignment(1); // don't leave padding in between
1651 
1652       auto LivenessBinder = ConstantStruct::get(LivenessTy,
1653           Initializers[i]->getAggregateElement(0u),
1654           ConstantExpr::getPointerCast(Metadata, IntptrTy),
1655           nullptr);
1656 
1657       // Recover the name of the variable this global is pointing to
1658       StringRef GVName =
1659           Initializers[i]->getAggregateElement(0u)->getOperand(0)->getName();
1660 
1661       GlobalVariable *Liveness = new GlobalVariable(
1662           M, LivenessTy, false, GlobalVariable::InternalLinkage, LivenessBinder,
1663           Twine("__asan_binder_") + GVName);
1664       Liveness->setSection("__DATA,__asan_liveness,regular,live_support");
1665       LivenessGlobals.push_back(Liveness);
1666     }
1667 
1668     // Update llvm.compiler.used, adding the new liveness globals. This is
1669     // needed so that during LTO these variables stay alive. The alternative
1670     // would be to have the linker handling the LTO symbols, but libLTO
1671     // current API does not expose access to the section for each symbol.
1672     if (!LivenessGlobals.empty())
1673       appendToCompilerUsed(M, LivenessGlobals);
1674   } else {
1675     // On all other platfoms, we just emit an array of global metadata
1676     // structures.
1677     ArrayType *ArrayOfGlobalStructTy = ArrayType::get(GlobalStructTy, n);
1678     AllGlobals = new GlobalVariable(
1679         M, ArrayOfGlobalStructTy, false, GlobalVariable::InternalLinkage,
1680         ConstantArray::get(ArrayOfGlobalStructTy, Initializers), "");
1681   }
1682 
1683   // Create calls for poisoning before initializers run and unpoisoning after.
1684   if (HasDynamicallyInitializedGlobals)
1685     createInitializerPoisonCalls(M, ModuleName);
1686 
1687   // Create a call to register the globals with the runtime.
1688   if (ShouldUseMachOGlobalsSection()) {
1689     IRB.CreateCall(AsanRegisterImageGlobals,
1690                    {IRB.CreatePointerCast(RegisteredFlag, IntptrTy)});
1691   } else {
1692     IRB.CreateCall(AsanRegisterGlobals,
1693                    {IRB.CreatePointerCast(AllGlobals, IntptrTy),
1694                     ConstantInt::get(IntptrTy, n)});
1695   }
1696 
1697   // We also need to unregister globals at the end, e.g., when a shared library
1698   // gets closed.
1699   Function *AsanDtorFunction =
1700       Function::Create(FunctionType::get(Type::getVoidTy(*C), false),
1701                        GlobalValue::InternalLinkage, kAsanModuleDtorName, &M);
1702   BasicBlock *AsanDtorBB = BasicBlock::Create(*C, "", AsanDtorFunction);
1703   IRBuilder<> IRB_Dtor(ReturnInst::Create(*C, AsanDtorBB));
1704 
1705   if (ShouldUseMachOGlobalsSection()) {
1706     IRB_Dtor.CreateCall(AsanUnregisterImageGlobals,
1707                         {IRB.CreatePointerCast(RegisteredFlag, IntptrTy)});
1708   } else {
1709     IRB_Dtor.CreateCall(AsanUnregisterGlobals,
1710                         {IRB.CreatePointerCast(AllGlobals, IntptrTy),
1711                          ConstantInt::get(IntptrTy, n)});
1712   }
1713 
1714   appendToGlobalDtors(M, AsanDtorFunction, kAsanCtorAndDtorPriority);
1715 
1716   DEBUG(dbgs() << M);
1717   return true;
1718 }
1719 
1720 bool AddressSanitizerModule::runOnModule(Module &M) {
1721   C = &(M.getContext());
1722   int LongSize = M.getDataLayout().getPointerSizeInBits();
1723   IntptrTy = Type::getIntNTy(*C, LongSize);
1724   TargetTriple = Triple(M.getTargetTriple());
1725   Mapping = getShadowMapping(TargetTriple, LongSize, CompileKernel);
1726   initializeCallbacks(M);
1727 
1728   bool Changed = false;
1729 
1730   // TODO(glider): temporarily disabled globals instrumentation for KASan.
1731   if (ClGlobals && !CompileKernel) {
1732     Function *CtorFunc = M.getFunction(kAsanModuleCtorName);
1733     assert(CtorFunc);
1734     IRBuilder<> IRB(CtorFunc->getEntryBlock().getTerminator());
1735     Changed |= InstrumentGlobals(IRB, M);
1736   }
1737 
1738   return Changed;
1739 }
1740 
1741 void AddressSanitizer::initializeCallbacks(Module &M) {
1742   IRBuilder<> IRB(*C);
1743   // Create __asan_report* callbacks.
1744   // IsWrite, TypeSize and Exp are encoded in the function name.
1745   for (int Exp = 0; Exp < 2; Exp++) {
1746     for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) {
1747       const std::string TypeStr = AccessIsWrite ? "store" : "load";
1748       const std::string ExpStr = Exp ? "exp_" : "";
1749       const std::string SuffixStr = CompileKernel ? "N" : "_n";
1750       const std::string EndingStr = Recover ? "_noabort" : "";
1751       Type *ExpType = Exp ? Type::getInt32Ty(*C) : nullptr;
1752       AsanErrorCallbackSized[AccessIsWrite][Exp] =
1753           checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1754               kAsanReportErrorTemplate + ExpStr + TypeStr + SuffixStr + EndingStr,
1755               IRB.getVoidTy(), IntptrTy, IntptrTy, ExpType, nullptr));
1756       AsanMemoryAccessCallbackSized[AccessIsWrite][Exp] =
1757           checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1758               ClMemoryAccessCallbackPrefix + ExpStr + TypeStr + "N" + EndingStr,
1759               IRB.getVoidTy(), IntptrTy, IntptrTy, ExpType, nullptr));
1760       for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
1761            AccessSizeIndex++) {
1762         const std::string Suffix = TypeStr + itostr(1ULL << AccessSizeIndex);
1763         AsanErrorCallback[AccessIsWrite][Exp][AccessSizeIndex] =
1764             checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1765                 kAsanReportErrorTemplate + ExpStr + Suffix + EndingStr,
1766                 IRB.getVoidTy(), IntptrTy, ExpType, nullptr));
1767         AsanMemoryAccessCallback[AccessIsWrite][Exp][AccessSizeIndex] =
1768             checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1769                 ClMemoryAccessCallbackPrefix + ExpStr + Suffix + EndingStr,
1770                 IRB.getVoidTy(), IntptrTy, ExpType, nullptr));
1771       }
1772     }
1773   }
1774 
1775   const std::string MemIntrinCallbackPrefix =
1776       CompileKernel ? std::string("") : ClMemoryAccessCallbackPrefix;
1777   AsanMemmove = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1778       MemIntrinCallbackPrefix + "memmove", IRB.getInt8PtrTy(),
1779       IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IntptrTy, nullptr));
1780   AsanMemcpy = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1781       MemIntrinCallbackPrefix + "memcpy", IRB.getInt8PtrTy(),
1782       IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IntptrTy, nullptr));
1783   AsanMemset = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1784       MemIntrinCallbackPrefix + "memset", IRB.getInt8PtrTy(),
1785       IRB.getInt8PtrTy(), IRB.getInt32Ty(), IntptrTy, nullptr));
1786 
1787   AsanHandleNoReturnFunc = checkSanitizerInterfaceFunction(
1788       M.getOrInsertFunction(kAsanHandleNoReturnName, IRB.getVoidTy(), nullptr));
1789 
1790   AsanPtrCmpFunction = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1791       kAsanPtrCmp, IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
1792   AsanPtrSubFunction = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
1793       kAsanPtrSub, IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
1794   // We insert an empty inline asm after __asan_report* to avoid callback merge.
1795   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
1796                             StringRef(""), StringRef(""),
1797                             /*hasSideEffects=*/true);
1798 }
1799 
1800 // virtual
1801 bool AddressSanitizer::doInitialization(Module &M) {
1802   // Initialize the private fields. No one has accessed them before.
1803 
1804   GlobalsMD.init(M);
1805 
1806   C = &(M.getContext());
1807   LongSize = M.getDataLayout().getPointerSizeInBits();
1808   IntptrTy = Type::getIntNTy(*C, LongSize);
1809   TargetTriple = Triple(M.getTargetTriple());
1810 
1811   if (!CompileKernel) {
1812     std::tie(AsanCtorFunction, AsanInitFunction) =
1813         createSanitizerCtorAndInitFunctions(
1814             M, kAsanModuleCtorName, kAsanInitName,
1815             /*InitArgTypes=*/{}, /*InitArgs=*/{}, kAsanVersionCheckName);
1816     appendToGlobalCtors(M, AsanCtorFunction, kAsanCtorAndDtorPriority);
1817   }
1818   Mapping = getShadowMapping(TargetTriple, LongSize, CompileKernel);
1819   return true;
1820 }
1821 
1822 bool AddressSanitizer::doFinalization(Module &M) {
1823   GlobalsMD.reset();
1824   return false;
1825 }
1826 
1827 bool AddressSanitizer::maybeInsertAsanInitAtFunctionEntry(Function &F) {
1828   // For each NSObject descendant having a +load method, this method is invoked
1829   // by the ObjC runtime before any of the static constructors is called.
1830   // Therefore we need to instrument such methods with a call to __asan_init
1831   // at the beginning in order to initialize our runtime before any access to
1832   // the shadow memory.
1833   // We cannot just ignore these methods, because they may call other
1834   // instrumented functions.
1835   if (F.getName().find(" load]") != std::string::npos) {
1836     IRBuilder<> IRB(&F.front(), F.front().begin());
1837     IRB.CreateCall(AsanInitFunction, {});
1838     return true;
1839   }
1840   return false;
1841 }
1842 
1843 void AddressSanitizer::maybeInsertDynamicShadowAtFunctionEntry(Function &F) {
1844   // Generate code only when dynamic addressing is needed.
1845   if (Mapping.Offset != kDynamicShadowSentinel)
1846     return;
1847 
1848   IRBuilder<> IRB(&F.front().front());
1849   Value *GlobalDynamicAddress = F.getParent()->getOrInsertGlobal(
1850       kAsanShadowMemoryDynamicAddress, IntptrTy);
1851   LocalDynamicShadow = IRB.CreateLoad(GlobalDynamicAddress);
1852 }
1853 
1854 void AddressSanitizer::markEscapedLocalAllocas(Function &F) {
1855   // Find the one possible call to llvm.localescape and pre-mark allocas passed
1856   // to it as uninteresting. This assumes we haven't started processing allocas
1857   // yet. This check is done up front because iterating the use list in
1858   // isInterestingAlloca would be algorithmically slower.
1859   assert(ProcessedAllocas.empty() && "must process localescape before allocas");
1860 
1861   // Try to get the declaration of llvm.localescape. If it's not in the module,
1862   // we can exit early.
1863   if (!F.getParent()->getFunction("llvm.localescape")) return;
1864 
1865   // Look for a call to llvm.localescape call in the entry block. It can't be in
1866   // any other block.
1867   for (Instruction &I : F.getEntryBlock()) {
1868     IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I);
1869     if (II && II->getIntrinsicID() == Intrinsic::localescape) {
1870       // We found a call. Mark all the allocas passed in as uninteresting.
1871       for (Value *Arg : II->arg_operands()) {
1872         AllocaInst *AI = dyn_cast<AllocaInst>(Arg->stripPointerCasts());
1873         assert(AI && AI->isStaticAlloca() &&
1874                "non-static alloca arg to localescape");
1875         ProcessedAllocas[AI] = false;
1876       }
1877       break;
1878     }
1879   }
1880 }
1881 
1882 bool AddressSanitizer::runOnFunction(Function &F) {
1883   if (&F == AsanCtorFunction) return false;
1884   if (F.getLinkage() == GlobalValue::AvailableExternallyLinkage) return false;
1885   if (!ClDebugFunc.empty() && ClDebugFunc == F.getName()) return false;
1886   if (F.getName().startswith("__asan_")) return false;
1887 
1888   bool FunctionModified = false;
1889 
1890   // If needed, insert __asan_init before checking for SanitizeAddress attr.
1891   // This function needs to be called even if the function body is not
1892   // instrumented.
1893   if (maybeInsertAsanInitAtFunctionEntry(F))
1894     FunctionModified = true;
1895 
1896   // Leave if the function doesn't need instrumentation.
1897   if (!F.hasFnAttribute(Attribute::SanitizeAddress)) return FunctionModified;
1898 
1899   DEBUG(dbgs() << "ASAN instrumenting:\n" << F << "\n");
1900 
1901   initializeCallbacks(*F.getParent());
1902   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1903 
1904   FunctionStateRAII CleanupObj(this);
1905 
1906   maybeInsertDynamicShadowAtFunctionEntry(F);
1907 
1908   // We can't instrument allocas used with llvm.localescape. Only static allocas
1909   // can be passed to that intrinsic.
1910   markEscapedLocalAllocas(F);
1911 
1912   // We want to instrument every address only once per basic block (unless there
1913   // are calls between uses).
1914   SmallSet<Value *, 16> TempsToInstrument;
1915   SmallVector<Instruction *, 16> ToInstrument;
1916   SmallVector<Instruction *, 8> NoReturnCalls;
1917   SmallVector<BasicBlock *, 16> AllBlocks;
1918   SmallVector<Instruction *, 16> PointerComparisonsOrSubtracts;
1919   int NumAllocas = 0;
1920   bool IsWrite;
1921   unsigned Alignment;
1922   uint64_t TypeSize;
1923   const TargetLibraryInfo *TLI =
1924       &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1925 
1926   // Fill the set of memory operations to instrument.
1927   for (auto &BB : F) {
1928     AllBlocks.push_back(&BB);
1929     TempsToInstrument.clear();
1930     int NumInsnsPerBB = 0;
1931     for (auto &Inst : BB) {
1932       if (LooksLikeCodeInBug11395(&Inst)) return false;
1933       if (Value *Addr = isInterestingMemoryAccess(&Inst, &IsWrite, &TypeSize,
1934                                                   &Alignment)) {
1935         if (ClOpt && ClOptSameTemp) {
1936           if (!TempsToInstrument.insert(Addr).second)
1937             continue;  // We've seen this temp in the current BB.
1938         }
1939       } else if (ClInvalidPointerPairs &&
1940                  isInterestingPointerComparisonOrSubtraction(&Inst)) {
1941         PointerComparisonsOrSubtracts.push_back(&Inst);
1942         continue;
1943       } else if (isa<MemIntrinsic>(Inst)) {
1944         // ok, take it.
1945       } else {
1946         if (isa<AllocaInst>(Inst)) NumAllocas++;
1947         CallSite CS(&Inst);
1948         if (CS) {
1949           // A call inside BB.
1950           TempsToInstrument.clear();
1951           if (CS.doesNotReturn()) NoReturnCalls.push_back(CS.getInstruction());
1952         }
1953         if (CallInst *CI = dyn_cast<CallInst>(&Inst))
1954           maybeMarkSanitizerLibraryCallNoBuiltin(CI, TLI);
1955         continue;
1956       }
1957       ToInstrument.push_back(&Inst);
1958       NumInsnsPerBB++;
1959       if (NumInsnsPerBB >= ClMaxInsnsToInstrumentPerBB) break;
1960     }
1961   }
1962 
1963   bool UseCalls =
1964       CompileKernel ||
1965       (ClInstrumentationWithCallsThreshold >= 0 &&
1966        ToInstrument.size() > (unsigned)ClInstrumentationWithCallsThreshold);
1967   const DataLayout &DL = F.getParent()->getDataLayout();
1968   ObjectSizeOffsetVisitor ObjSizeVis(DL, TLI, F.getContext(),
1969                                      /*RoundToAlign=*/true);
1970 
1971   // Instrument.
1972   int NumInstrumented = 0;
1973   for (auto Inst : ToInstrument) {
1974     if (ClDebugMin < 0 || ClDebugMax < 0 ||
1975         (NumInstrumented >= ClDebugMin && NumInstrumented <= ClDebugMax)) {
1976       if (isInterestingMemoryAccess(Inst, &IsWrite, &TypeSize, &Alignment))
1977         instrumentMop(ObjSizeVis, Inst, UseCalls,
1978                       F.getParent()->getDataLayout());
1979       else
1980         instrumentMemIntrinsic(cast<MemIntrinsic>(Inst));
1981     }
1982     NumInstrumented++;
1983   }
1984 
1985   FunctionStackPoisoner FSP(F, *this);
1986   bool ChangedStack = FSP.runOnFunction();
1987 
1988   // We must unpoison the stack before every NoReturn call (throw, _exit, etc).
1989   // See e.g. http://code.google.com/p/address-sanitizer/issues/detail?id=37
1990   for (auto CI : NoReturnCalls) {
1991     IRBuilder<> IRB(CI);
1992     IRB.CreateCall(AsanHandleNoReturnFunc, {});
1993   }
1994 
1995   for (auto Inst : PointerComparisonsOrSubtracts) {
1996     instrumentPointerComparisonOrSubtraction(Inst);
1997     NumInstrumented++;
1998   }
1999 
2000   if (NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty())
2001     FunctionModified = true;
2002 
2003   DEBUG(dbgs() << "ASAN done instrumenting: " << FunctionModified << " "
2004                << F << "\n");
2005 
2006   return FunctionModified;
2007 }
2008 
2009 // Workaround for bug 11395: we don't want to instrument stack in functions
2010 // with large assembly blobs (32-bit only), otherwise reg alloc may crash.
2011 // FIXME: remove once the bug 11395 is fixed.
2012 bool AddressSanitizer::LooksLikeCodeInBug11395(Instruction *I) {
2013   if (LongSize != 32) return false;
2014   CallInst *CI = dyn_cast<CallInst>(I);
2015   if (!CI || !CI->isInlineAsm()) return false;
2016   if (CI->getNumArgOperands() <= 5) return false;
2017   // We have inline assembly with quite a few arguments.
2018   return true;
2019 }
2020 
2021 void FunctionStackPoisoner::initializeCallbacks(Module &M) {
2022   IRBuilder<> IRB(*C);
2023   for (int i = 0; i <= kMaxAsanStackMallocSizeClass; i++) {
2024     std::string Suffix = itostr(i);
2025     AsanStackMallocFunc[i] = checkSanitizerInterfaceFunction(
2026         M.getOrInsertFunction(kAsanStackMallocNameTemplate + Suffix, IntptrTy,
2027                               IntptrTy, nullptr));
2028     AsanStackFreeFunc[i] = checkSanitizerInterfaceFunction(
2029         M.getOrInsertFunction(kAsanStackFreeNameTemplate + Suffix,
2030                               IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
2031   }
2032   if (ASan.UseAfterScope) {
2033     AsanPoisonStackMemoryFunc = checkSanitizerInterfaceFunction(
2034         M.getOrInsertFunction(kAsanPoisonStackMemoryName, IRB.getVoidTy(),
2035                               IntptrTy, IntptrTy, nullptr));
2036     AsanUnpoisonStackMemoryFunc = checkSanitizerInterfaceFunction(
2037         M.getOrInsertFunction(kAsanUnpoisonStackMemoryName, IRB.getVoidTy(),
2038                               IntptrTy, IntptrTy, nullptr));
2039   }
2040 
2041   for (size_t Val : {0x00, 0xf1, 0xf2, 0xf3, 0xf5, 0xf8}) {
2042     std::ostringstream Name;
2043     Name << kAsanSetShadowPrefix;
2044     Name << std::setw(2) << std::setfill('0') << std::hex << Val;
2045     AsanSetShadowFunc[Val] =
2046         checkSanitizerInterfaceFunction(M.getOrInsertFunction(
2047             Name.str(), IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
2048   }
2049 
2050   AsanAllocaPoisonFunc = checkSanitizerInterfaceFunction(M.getOrInsertFunction(
2051       kAsanAllocaPoison, IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
2052   AsanAllocasUnpoisonFunc =
2053       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
2054           kAsanAllocasUnpoison, IRB.getVoidTy(), IntptrTy, IntptrTy, nullptr));
2055 }
2056 
2057 void FunctionStackPoisoner::copyToShadowInline(ArrayRef<uint8_t> ShadowMask,
2058                                                ArrayRef<uint8_t> ShadowBytes,
2059                                                size_t Begin, size_t End,
2060                                                IRBuilder<> &IRB,
2061                                                Value *ShadowBase) {
2062   if (Begin >= End)
2063     return;
2064 
2065   const size_t LargestStoreSizeInBytes =
2066       std::min<size_t>(sizeof(uint64_t), ASan.LongSize / 8);
2067 
2068   const bool IsLittleEndian = F.getParent()->getDataLayout().isLittleEndian();
2069 
2070   // Poison given range in shadow using larges store size with out leading and
2071   // trailing zeros in ShadowMask. Zeros never change, so they need neither
2072   // poisoning nor up-poisoning. Still we don't mind if some of them get into a
2073   // middle of a store.
2074   for (size_t i = Begin; i < End;) {
2075     if (!ShadowMask[i]) {
2076       assert(!ShadowBytes[i]);
2077       ++i;
2078       continue;
2079     }
2080 
2081     size_t StoreSizeInBytes = LargestStoreSizeInBytes;
2082     // Fit store size into the range.
2083     while (StoreSizeInBytes > End - i)
2084       StoreSizeInBytes /= 2;
2085 
2086     // Minimize store size by trimming trailing zeros.
2087     for (size_t j = StoreSizeInBytes - 1; j && !ShadowMask[i + j]; --j) {
2088       while (j <= StoreSizeInBytes / 2)
2089         StoreSizeInBytes /= 2;
2090     }
2091 
2092     uint64_t Val = 0;
2093     for (size_t j = 0; j < StoreSizeInBytes; j++) {
2094       if (IsLittleEndian)
2095         Val |= (uint64_t)ShadowBytes[i + j] << (8 * j);
2096       else
2097         Val = (Val << 8) | ShadowBytes[i + j];
2098     }
2099 
2100     Value *Ptr = IRB.CreateAdd(ShadowBase, ConstantInt::get(IntptrTy, i));
2101     Value *Poison = IRB.getIntN(StoreSizeInBytes * 8, Val);
2102     IRB.CreateAlignedStore(
2103         Poison, IRB.CreateIntToPtr(Ptr, Poison->getType()->getPointerTo()), 1);
2104 
2105     i += StoreSizeInBytes;
2106   }
2107 }
2108 
2109 void FunctionStackPoisoner::copyToShadow(ArrayRef<uint8_t> ShadowMask,
2110                                          ArrayRef<uint8_t> ShadowBytes,
2111                                          IRBuilder<> &IRB, Value *ShadowBase) {
2112   copyToShadow(ShadowMask, ShadowBytes, 0, ShadowMask.size(), IRB, ShadowBase);
2113 }
2114 
2115 void FunctionStackPoisoner::copyToShadow(ArrayRef<uint8_t> ShadowMask,
2116                                          ArrayRef<uint8_t> ShadowBytes,
2117                                          size_t Begin, size_t End,
2118                                          IRBuilder<> &IRB, Value *ShadowBase) {
2119   assert(ShadowMask.size() == ShadowBytes.size());
2120   size_t Done = Begin;
2121   for (size_t i = Begin, j = Begin + 1; i < End; i = j++) {
2122     if (!ShadowMask[i]) {
2123       assert(!ShadowBytes[i]);
2124       continue;
2125     }
2126     uint8_t Val = ShadowBytes[i];
2127     if (!AsanSetShadowFunc[Val])
2128       continue;
2129 
2130     // Skip same values.
2131     for (; j < End && ShadowMask[j] && Val == ShadowBytes[j]; ++j) {
2132     }
2133 
2134     if (j - i >= ClMaxInlinePoisoningSize) {
2135       copyToShadowInline(ShadowMask, ShadowBytes, Done, i, IRB, ShadowBase);
2136       IRB.CreateCall(AsanSetShadowFunc[Val],
2137                      {IRB.CreateAdd(ShadowBase, ConstantInt::get(IntptrTy, i)),
2138                       ConstantInt::get(IntptrTy, j - i)});
2139       Done = j;
2140     }
2141   }
2142 
2143   copyToShadowInline(ShadowMask, ShadowBytes, Done, End, IRB, ShadowBase);
2144 }
2145 
2146 // Fake stack allocator (asan_fake_stack.h) has 11 size classes
2147 // for every power of 2 from kMinStackMallocSize to kMaxAsanStackMallocSizeClass
2148 static int StackMallocSizeClass(uint64_t LocalStackSize) {
2149   assert(LocalStackSize <= kMaxStackMallocSize);
2150   uint64_t MaxSize = kMinStackMallocSize;
2151   for (int i = 0;; i++, MaxSize *= 2)
2152     if (LocalStackSize <= MaxSize) return i;
2153   llvm_unreachable("impossible LocalStackSize");
2154 }
2155 
2156 PHINode *FunctionStackPoisoner::createPHI(IRBuilder<> &IRB, Value *Cond,
2157                                           Value *ValueIfTrue,
2158                                           Instruction *ThenTerm,
2159                                           Value *ValueIfFalse) {
2160   PHINode *PHI = IRB.CreatePHI(IntptrTy, 2);
2161   BasicBlock *CondBlock = cast<Instruction>(Cond)->getParent();
2162   PHI->addIncoming(ValueIfFalse, CondBlock);
2163   BasicBlock *ThenBlock = ThenTerm->getParent();
2164   PHI->addIncoming(ValueIfTrue, ThenBlock);
2165   return PHI;
2166 }
2167 
2168 Value *FunctionStackPoisoner::createAllocaForLayout(
2169     IRBuilder<> &IRB, const ASanStackFrameLayout &L, bool Dynamic) {
2170   AllocaInst *Alloca;
2171   if (Dynamic) {
2172     Alloca = IRB.CreateAlloca(IRB.getInt8Ty(),
2173                               ConstantInt::get(IRB.getInt64Ty(), L.FrameSize),
2174                               "MyAlloca");
2175   } else {
2176     Alloca = IRB.CreateAlloca(ArrayType::get(IRB.getInt8Ty(), L.FrameSize),
2177                               nullptr, "MyAlloca");
2178     assert(Alloca->isStaticAlloca());
2179   }
2180   assert((ClRealignStack & (ClRealignStack - 1)) == 0);
2181   size_t FrameAlignment = std::max(L.FrameAlignment, (size_t)ClRealignStack);
2182   Alloca->setAlignment(FrameAlignment);
2183   return IRB.CreatePointerCast(Alloca, IntptrTy);
2184 }
2185 
2186 void FunctionStackPoisoner::createDynamicAllocasInitStorage() {
2187   BasicBlock &FirstBB = *F.begin();
2188   IRBuilder<> IRB(dyn_cast<Instruction>(FirstBB.begin()));
2189   DynamicAllocaLayout = IRB.CreateAlloca(IntptrTy, nullptr);
2190   IRB.CreateStore(Constant::getNullValue(IntptrTy), DynamicAllocaLayout);
2191   DynamicAllocaLayout->setAlignment(32);
2192 }
2193 
2194 void FunctionStackPoisoner::processDynamicAllocas() {
2195   if (!ClInstrumentDynamicAllocas || DynamicAllocaVec.empty()) {
2196     assert(DynamicAllocaPoisonCallVec.empty());
2197     return;
2198   }
2199 
2200   // Insert poison calls for lifetime intrinsics for dynamic allocas.
2201   for (const auto &APC : DynamicAllocaPoisonCallVec) {
2202     assert(APC.InsBefore);
2203     assert(APC.AI);
2204     assert(ASan.isInterestingAlloca(*APC.AI));
2205     assert(!APC.AI->isStaticAlloca());
2206 
2207     IRBuilder<> IRB(APC.InsBefore);
2208     poisonAlloca(APC.AI, APC.Size, IRB, APC.DoPoison);
2209     // Dynamic allocas will be unpoisoned unconditionally below in
2210     // unpoisonDynamicAllocas.
2211     // Flag that we need unpoison static allocas.
2212   }
2213 
2214   // Handle dynamic allocas.
2215   createDynamicAllocasInitStorage();
2216   for (auto &AI : DynamicAllocaVec)
2217     handleDynamicAllocaCall(AI);
2218   unpoisonDynamicAllocas();
2219 }
2220 
2221 void FunctionStackPoisoner::processStaticAllocas() {
2222   if (AllocaVec.empty()) {
2223     assert(StaticAllocaPoisonCallVec.empty());
2224     return;
2225   }
2226 
2227   int StackMallocIdx = -1;
2228   DebugLoc EntryDebugLocation;
2229   if (auto SP = F.getSubprogram())
2230     EntryDebugLocation = DebugLoc::get(SP->getScopeLine(), 0, SP);
2231 
2232   Instruction *InsBefore = AllocaVec[0];
2233   IRBuilder<> IRB(InsBefore);
2234   IRB.SetCurrentDebugLocation(EntryDebugLocation);
2235 
2236   // Make sure non-instrumented allocas stay in the entry block. Otherwise,
2237   // debug info is broken, because only entry-block allocas are treated as
2238   // regular stack slots.
2239   auto InsBeforeB = InsBefore->getParent();
2240   assert(InsBeforeB == &F.getEntryBlock());
2241   for (auto *AI : StaticAllocasToMoveUp)
2242     if (AI->getParent() == InsBeforeB)
2243       AI->moveBefore(InsBefore);
2244 
2245   // If we have a call to llvm.localescape, keep it in the entry block.
2246   if (LocalEscapeCall) LocalEscapeCall->moveBefore(InsBefore);
2247 
2248   SmallVector<ASanStackVariableDescription, 16> SVD;
2249   SVD.reserve(AllocaVec.size());
2250   for (AllocaInst *AI : AllocaVec) {
2251     ASanStackVariableDescription D = {AI->getName().data(),
2252                                       ASan.getAllocaSizeInBytes(*AI),
2253                                       0,
2254                                       AI->getAlignment(),
2255                                       AI,
2256                                       0,
2257                                       0};
2258     SVD.push_back(D);
2259   }
2260 
2261   // Minimal header size (left redzone) is 4 pointers,
2262   // i.e. 32 bytes on 64-bit platforms and 16 bytes in 32-bit platforms.
2263   size_t MinHeaderSize = ASan.LongSize / 2;
2264   const ASanStackFrameLayout &L =
2265       ComputeASanStackFrameLayout(SVD, 1ULL << Mapping.Scale, MinHeaderSize);
2266 
2267   // Build AllocaToSVDMap for ASanStackVariableDescription lookup.
2268   DenseMap<const AllocaInst *, ASanStackVariableDescription *> AllocaToSVDMap;
2269   for (auto &Desc : SVD)
2270     AllocaToSVDMap[Desc.AI] = &Desc;
2271 
2272   // Update SVD with information from lifetime intrinsics.
2273   for (const auto &APC : StaticAllocaPoisonCallVec) {
2274     assert(APC.InsBefore);
2275     assert(APC.AI);
2276     assert(ASan.isInterestingAlloca(*APC.AI));
2277     assert(APC.AI->isStaticAlloca());
2278 
2279     ASanStackVariableDescription &Desc = *AllocaToSVDMap[APC.AI];
2280     Desc.LifetimeSize = Desc.Size;
2281     if (const DILocation *FnLoc = EntryDebugLocation.get()) {
2282       if (const DILocation *LifetimeLoc = APC.InsBefore->getDebugLoc().get()) {
2283         if (LifetimeLoc->getFile() == FnLoc->getFile())
2284           if (unsigned Line = LifetimeLoc->getLine())
2285             Desc.Line = std::min(Desc.Line ? Desc.Line : Line, Line);
2286       }
2287     }
2288   }
2289 
2290   auto DescriptionString = ComputeASanStackFrameDescription(SVD);
2291   DEBUG(dbgs() << DescriptionString << " --- " << L.FrameSize << "\n");
2292   uint64_t LocalStackSize = L.FrameSize;
2293   bool DoStackMalloc = ClUseAfterReturn && !ASan.CompileKernel &&
2294                        LocalStackSize <= kMaxStackMallocSize;
2295   bool DoDynamicAlloca = ClDynamicAllocaStack;
2296   // Don't do dynamic alloca or stack malloc if:
2297   // 1) There is inline asm: too often it makes assumptions on which registers
2298   //    are available.
2299   // 2) There is a returns_twice call (typically setjmp), which is
2300   //    optimization-hostile, and doesn't play well with introduced indirect
2301   //    register-relative calculation of local variable addresses.
2302   DoDynamicAlloca &= !HasNonEmptyInlineAsm && !HasReturnsTwiceCall;
2303   DoStackMalloc &= !HasNonEmptyInlineAsm && !HasReturnsTwiceCall;
2304 
2305   Value *StaticAlloca =
2306       DoDynamicAlloca ? nullptr : createAllocaForLayout(IRB, L, false);
2307 
2308   Value *FakeStack;
2309   Value *LocalStackBase;
2310 
2311   if (DoStackMalloc) {
2312     // void *FakeStack = __asan_option_detect_stack_use_after_return
2313     //     ? __asan_stack_malloc_N(LocalStackSize)
2314     //     : nullptr;
2315     // void *LocalStackBase = (FakeStack) ? FakeStack : alloca(LocalStackSize);
2316     Constant *OptionDetectUseAfterReturn = F.getParent()->getOrInsertGlobal(
2317         kAsanOptionDetectUseAfterReturn, IRB.getInt32Ty());
2318     Value *UseAfterReturnIsEnabled =
2319         IRB.CreateICmpNE(IRB.CreateLoad(OptionDetectUseAfterReturn),
2320                          Constant::getNullValue(IRB.getInt32Ty()));
2321     Instruction *Term =
2322         SplitBlockAndInsertIfThen(UseAfterReturnIsEnabled, InsBefore, false);
2323     IRBuilder<> IRBIf(Term);
2324     IRBIf.SetCurrentDebugLocation(EntryDebugLocation);
2325     StackMallocIdx = StackMallocSizeClass(LocalStackSize);
2326     assert(StackMallocIdx <= kMaxAsanStackMallocSizeClass);
2327     Value *FakeStackValue =
2328         IRBIf.CreateCall(AsanStackMallocFunc[StackMallocIdx],
2329                          ConstantInt::get(IntptrTy, LocalStackSize));
2330     IRB.SetInsertPoint(InsBefore);
2331     IRB.SetCurrentDebugLocation(EntryDebugLocation);
2332     FakeStack = createPHI(IRB, UseAfterReturnIsEnabled, FakeStackValue, Term,
2333                           ConstantInt::get(IntptrTy, 0));
2334 
2335     Value *NoFakeStack =
2336         IRB.CreateICmpEQ(FakeStack, Constant::getNullValue(IntptrTy));
2337     Term = SplitBlockAndInsertIfThen(NoFakeStack, InsBefore, false);
2338     IRBIf.SetInsertPoint(Term);
2339     IRBIf.SetCurrentDebugLocation(EntryDebugLocation);
2340     Value *AllocaValue =
2341         DoDynamicAlloca ? createAllocaForLayout(IRBIf, L, true) : StaticAlloca;
2342     IRB.SetInsertPoint(InsBefore);
2343     IRB.SetCurrentDebugLocation(EntryDebugLocation);
2344     LocalStackBase = createPHI(IRB, NoFakeStack, AllocaValue, Term, FakeStack);
2345   } else {
2346     // void *FakeStack = nullptr;
2347     // void *LocalStackBase = alloca(LocalStackSize);
2348     FakeStack = ConstantInt::get(IntptrTy, 0);
2349     LocalStackBase =
2350         DoDynamicAlloca ? createAllocaForLayout(IRB, L, true) : StaticAlloca;
2351   }
2352 
2353   // Replace Alloca instructions with base+offset.
2354   for (const auto &Desc : SVD) {
2355     AllocaInst *AI = Desc.AI;
2356     Value *NewAllocaPtr = IRB.CreateIntToPtr(
2357         IRB.CreateAdd(LocalStackBase, ConstantInt::get(IntptrTy, Desc.Offset)),
2358         AI->getType());
2359     replaceDbgDeclareForAlloca(AI, NewAllocaPtr, DIB, /*Deref=*/true);
2360     AI->replaceAllUsesWith(NewAllocaPtr);
2361   }
2362 
2363   // The left-most redzone has enough space for at least 4 pointers.
2364   // Write the Magic value to redzone[0].
2365   Value *BasePlus0 = IRB.CreateIntToPtr(LocalStackBase, IntptrPtrTy);
2366   IRB.CreateStore(ConstantInt::get(IntptrTy, kCurrentStackFrameMagic),
2367                   BasePlus0);
2368   // Write the frame description constant to redzone[1].
2369   Value *BasePlus1 = IRB.CreateIntToPtr(
2370       IRB.CreateAdd(LocalStackBase,
2371                     ConstantInt::get(IntptrTy, ASan.LongSize / 8)),
2372       IntptrPtrTy);
2373   GlobalVariable *StackDescriptionGlobal =
2374       createPrivateGlobalForString(*F.getParent(), DescriptionString,
2375                                    /*AllowMerging*/ true);
2376   Value *Description = IRB.CreatePointerCast(StackDescriptionGlobal, IntptrTy);
2377   IRB.CreateStore(Description, BasePlus1);
2378   // Write the PC to redzone[2].
2379   Value *BasePlus2 = IRB.CreateIntToPtr(
2380       IRB.CreateAdd(LocalStackBase,
2381                     ConstantInt::get(IntptrTy, 2 * ASan.LongSize / 8)),
2382       IntptrPtrTy);
2383   IRB.CreateStore(IRB.CreatePointerCast(&F, IntptrTy), BasePlus2);
2384 
2385   const auto &ShadowAfterScope = GetShadowBytesAfterScope(SVD, L);
2386 
2387   // Poison the stack red zones at the entry.
2388   Value *ShadowBase = ASan.memToShadow(LocalStackBase, IRB);
2389   // As mask we must use most poisoned case: red zones and after scope.
2390   // As bytes we can use either the same or just red zones only.
2391   copyToShadow(ShadowAfterScope, ShadowAfterScope, IRB, ShadowBase);
2392 
2393   if (!StaticAllocaPoisonCallVec.empty()) {
2394     const auto &ShadowInScope = GetShadowBytes(SVD, L);
2395 
2396     // Poison static allocas near lifetime intrinsics.
2397     for (const auto &APC : StaticAllocaPoisonCallVec) {
2398       const ASanStackVariableDescription &Desc = *AllocaToSVDMap[APC.AI];
2399       assert(Desc.Offset % L.Granularity == 0);
2400       size_t Begin = Desc.Offset / L.Granularity;
2401       size_t End = Begin + (APC.Size + L.Granularity - 1) / L.Granularity;
2402 
2403       IRBuilder<> IRB(APC.InsBefore);
2404       copyToShadow(ShadowAfterScope,
2405                    APC.DoPoison ? ShadowAfterScope : ShadowInScope, Begin, End,
2406                    IRB, ShadowBase);
2407     }
2408   }
2409 
2410   SmallVector<uint8_t, 64> ShadowClean(ShadowAfterScope.size(), 0);
2411   SmallVector<uint8_t, 64> ShadowAfterReturn;
2412 
2413   // (Un)poison the stack before all ret instructions.
2414   for (auto Ret : RetVec) {
2415     IRBuilder<> IRBRet(Ret);
2416     // Mark the current frame as retired.
2417     IRBRet.CreateStore(ConstantInt::get(IntptrTy, kRetiredStackFrameMagic),
2418                        BasePlus0);
2419     if (DoStackMalloc) {
2420       assert(StackMallocIdx >= 0);
2421       // if FakeStack != 0  // LocalStackBase == FakeStack
2422       //     // In use-after-return mode, poison the whole stack frame.
2423       //     if StackMallocIdx <= 4
2424       //         // For small sizes inline the whole thing:
2425       //         memset(ShadowBase, kAsanStackAfterReturnMagic, ShadowSize);
2426       //         **SavedFlagPtr(FakeStack) = 0
2427       //     else
2428       //         __asan_stack_free_N(FakeStack, LocalStackSize)
2429       // else
2430       //     <This is not a fake stack; unpoison the redzones>
2431       Value *Cmp =
2432           IRBRet.CreateICmpNE(FakeStack, Constant::getNullValue(IntptrTy));
2433       TerminatorInst *ThenTerm, *ElseTerm;
2434       SplitBlockAndInsertIfThenElse(Cmp, Ret, &ThenTerm, &ElseTerm);
2435 
2436       IRBuilder<> IRBPoison(ThenTerm);
2437       if (StackMallocIdx <= 4) {
2438         int ClassSize = kMinStackMallocSize << StackMallocIdx;
2439         ShadowAfterReturn.resize(ClassSize / L.Granularity,
2440                                  kAsanStackUseAfterReturnMagic);
2441         copyToShadow(ShadowAfterReturn, ShadowAfterReturn, IRBPoison,
2442                      ShadowBase);
2443         Value *SavedFlagPtrPtr = IRBPoison.CreateAdd(
2444             FakeStack,
2445             ConstantInt::get(IntptrTy, ClassSize - ASan.LongSize / 8));
2446         Value *SavedFlagPtr = IRBPoison.CreateLoad(
2447             IRBPoison.CreateIntToPtr(SavedFlagPtrPtr, IntptrPtrTy));
2448         IRBPoison.CreateStore(
2449             Constant::getNullValue(IRBPoison.getInt8Ty()),
2450             IRBPoison.CreateIntToPtr(SavedFlagPtr, IRBPoison.getInt8PtrTy()));
2451       } else {
2452         // For larger frames call __asan_stack_free_*.
2453         IRBPoison.CreateCall(
2454             AsanStackFreeFunc[StackMallocIdx],
2455             {FakeStack, ConstantInt::get(IntptrTy, LocalStackSize)});
2456       }
2457 
2458       IRBuilder<> IRBElse(ElseTerm);
2459       copyToShadow(ShadowAfterScope, ShadowClean, IRBElse, ShadowBase);
2460     } else {
2461       copyToShadow(ShadowAfterScope, ShadowClean, IRBRet, ShadowBase);
2462     }
2463   }
2464 
2465   // We are done. Remove the old unused alloca instructions.
2466   for (auto AI : AllocaVec) AI->eraseFromParent();
2467 }
2468 
2469 void FunctionStackPoisoner::poisonAlloca(Value *V, uint64_t Size,
2470                                          IRBuilder<> &IRB, bool DoPoison) {
2471   // For now just insert the call to ASan runtime.
2472   Value *AddrArg = IRB.CreatePointerCast(V, IntptrTy);
2473   Value *SizeArg = ConstantInt::get(IntptrTy, Size);
2474   IRB.CreateCall(
2475       DoPoison ? AsanPoisonStackMemoryFunc : AsanUnpoisonStackMemoryFunc,
2476       {AddrArg, SizeArg});
2477 }
2478 
2479 // Handling llvm.lifetime intrinsics for a given %alloca:
2480 // (1) collect all llvm.lifetime.xxx(%size, %value) describing the alloca.
2481 // (2) if %size is constant, poison memory for llvm.lifetime.end (to detect
2482 //     invalid accesses) and unpoison it for llvm.lifetime.start (the memory
2483 //     could be poisoned by previous llvm.lifetime.end instruction, as the
2484 //     variable may go in and out of scope several times, e.g. in loops).
2485 // (3) if we poisoned at least one %alloca in a function,
2486 //     unpoison the whole stack frame at function exit.
2487 
2488 AllocaInst *FunctionStackPoisoner::findAllocaForValue(Value *V) {
2489   if (AllocaInst *AI = dyn_cast<AllocaInst>(V))
2490     // We're interested only in allocas we can handle.
2491     return ASan.isInterestingAlloca(*AI) ? AI : nullptr;
2492   // See if we've already calculated (or started to calculate) alloca for a
2493   // given value.
2494   AllocaForValueMapTy::iterator I = AllocaForValue.find(V);
2495   if (I != AllocaForValue.end()) return I->second;
2496   // Store 0 while we're calculating alloca for value V to avoid
2497   // infinite recursion if the value references itself.
2498   AllocaForValue[V] = nullptr;
2499   AllocaInst *Res = nullptr;
2500   if (CastInst *CI = dyn_cast<CastInst>(V))
2501     Res = findAllocaForValue(CI->getOperand(0));
2502   else if (PHINode *PN = dyn_cast<PHINode>(V)) {
2503     for (Value *IncValue : PN->incoming_values()) {
2504       // Allow self-referencing phi-nodes.
2505       if (IncValue == PN) continue;
2506       AllocaInst *IncValueAI = findAllocaForValue(IncValue);
2507       // AI for incoming values should exist and should all be equal.
2508       if (IncValueAI == nullptr || (Res != nullptr && IncValueAI != Res))
2509         return nullptr;
2510       Res = IncValueAI;
2511     }
2512   } else if (GetElementPtrInst *EP = dyn_cast<GetElementPtrInst>(V)) {
2513     Res = findAllocaForValue(EP->getPointerOperand());
2514   } else {
2515     DEBUG(dbgs() << "Alloca search canceled on unknown instruction: " << *V << "\n");
2516   }
2517   if (Res) AllocaForValue[V] = Res;
2518   return Res;
2519 }
2520 
2521 void FunctionStackPoisoner::handleDynamicAllocaCall(AllocaInst *AI) {
2522   IRBuilder<> IRB(AI);
2523 
2524   const unsigned Align = std::max(kAllocaRzSize, AI->getAlignment());
2525   const uint64_t AllocaRedzoneMask = kAllocaRzSize - 1;
2526 
2527   Value *Zero = Constant::getNullValue(IntptrTy);
2528   Value *AllocaRzSize = ConstantInt::get(IntptrTy, kAllocaRzSize);
2529   Value *AllocaRzMask = ConstantInt::get(IntptrTy, AllocaRedzoneMask);
2530 
2531   // Since we need to extend alloca with additional memory to locate
2532   // redzones, and OldSize is number of allocated blocks with
2533   // ElementSize size, get allocated memory size in bytes by
2534   // OldSize * ElementSize.
2535   const unsigned ElementSize =
2536       F.getParent()->getDataLayout().getTypeAllocSize(AI->getAllocatedType());
2537   Value *OldSize =
2538       IRB.CreateMul(IRB.CreateIntCast(AI->getArraySize(), IntptrTy, false),
2539                     ConstantInt::get(IntptrTy, ElementSize));
2540 
2541   // PartialSize = OldSize % 32
2542   Value *PartialSize = IRB.CreateAnd(OldSize, AllocaRzMask);
2543 
2544   // Misalign = kAllocaRzSize - PartialSize;
2545   Value *Misalign = IRB.CreateSub(AllocaRzSize, PartialSize);
2546 
2547   // PartialPadding = Misalign != kAllocaRzSize ? Misalign : 0;
2548   Value *Cond = IRB.CreateICmpNE(Misalign, AllocaRzSize);
2549   Value *PartialPadding = IRB.CreateSelect(Cond, Misalign, Zero);
2550 
2551   // AdditionalChunkSize = Align + PartialPadding + kAllocaRzSize
2552   // Align is added to locate left redzone, PartialPadding for possible
2553   // partial redzone and kAllocaRzSize for right redzone respectively.
2554   Value *AdditionalChunkSize = IRB.CreateAdd(
2555       ConstantInt::get(IntptrTy, Align + kAllocaRzSize), PartialPadding);
2556 
2557   Value *NewSize = IRB.CreateAdd(OldSize, AdditionalChunkSize);
2558 
2559   // Insert new alloca with new NewSize and Align params.
2560   AllocaInst *NewAlloca = IRB.CreateAlloca(IRB.getInt8Ty(), NewSize);
2561   NewAlloca->setAlignment(Align);
2562 
2563   // NewAddress = Address + Align
2564   Value *NewAddress = IRB.CreateAdd(IRB.CreatePtrToInt(NewAlloca, IntptrTy),
2565                                     ConstantInt::get(IntptrTy, Align));
2566 
2567   // Insert __asan_alloca_poison call for new created alloca.
2568   IRB.CreateCall(AsanAllocaPoisonFunc, {NewAddress, OldSize});
2569 
2570   // Store the last alloca's address to DynamicAllocaLayout. We'll need this
2571   // for unpoisoning stuff.
2572   IRB.CreateStore(IRB.CreatePtrToInt(NewAlloca, IntptrTy), DynamicAllocaLayout);
2573 
2574   Value *NewAddressPtr = IRB.CreateIntToPtr(NewAddress, AI->getType());
2575 
2576   // Replace all uses of AddessReturnedByAlloca with NewAddressPtr.
2577   AI->replaceAllUsesWith(NewAddressPtr);
2578 
2579   // We are done. Erase old alloca from parent.
2580   AI->eraseFromParent();
2581 }
2582 
2583 // isSafeAccess returns true if Addr is always inbounds with respect to its
2584 // base object. For example, it is a field access or an array access with
2585 // constant inbounds index.
2586 bool AddressSanitizer::isSafeAccess(ObjectSizeOffsetVisitor &ObjSizeVis,
2587                                     Value *Addr, uint64_t TypeSize) const {
2588   SizeOffsetType SizeOffset = ObjSizeVis.compute(Addr);
2589   if (!ObjSizeVis.bothKnown(SizeOffset)) return false;
2590   uint64_t Size = SizeOffset.first.getZExtValue();
2591   int64_t Offset = SizeOffset.second.getSExtValue();
2592   // Three checks are required to ensure safety:
2593   // . Offset >= 0  (since the offset is given from the base ptr)
2594   // . Size >= Offset  (unsigned)
2595   // . Size - Offset >= NeededSize  (unsigned)
2596   return Offset >= 0 && Size >= uint64_t(Offset) &&
2597          Size - uint64_t(Offset) >= TypeSize / 8;
2598 }
2599