lib/Transforms/Instrumentation/AddressSanitizer.cpp

   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 #define DEBUG_TYPE "asan"
  17
  18 #include "FunctionBlackList.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/IRBuilder.h"
  21 #include "llvm/InlineAsm.h"
  22 #include "llvm/IntrinsicInst.h"
  23 #include "llvm/LLVMContext.h"
  24 #include "llvm/Module.h"
  25 #include "llvm/Type.h"
  26 #include "llvm/ADT/ArrayRef.h"
  27 #include "llvm/ADT/OwningPtr.h"
  28 #include "llvm/ADT/SmallSet.h"
  29 #include "llvm/ADT/SmallString.h"
  30 #include "llvm/ADT/SmallVector.h"
  31 #include "llvm/ADT/StringExtras.h"
  32 #include "llvm/ADT/Triple.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/DataTypes.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/raw_ostream.h"
  37 #include "llvm/Support/system_error.h"
  38 #include "llvm/Target/TargetData.h"
  39 #include "llvm/Target/TargetMachine.h"
  40 #include "llvm/Transforms/Instrumentation.h"
  41 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  42 #include "llvm/Transforms/Utils/ModuleUtils.h"
  43
  44 #include <string>
  45 #include <algorithm>
  46
  47 using namespace llvm;
  48
  49 static const uint64_t kDefaultShadowScale = 3;
  50 static const uint64_t kDefaultShadowOffset32 = 1ULL << 29;
  51 static const uint64_t kDefaultShadowOffset64 = 1ULL << 44;
  52 static const uint64_t kDefaultShadowOffsetAndroid = 0;
  53
  54 static const size_t kMaxStackMallocSize = 1 << 16;  // 64K
  55 static const uintptr_t kCurrentStackFrameMagic = 0x41B58AB3;
  56 static const uintptr_t kRetiredStackFrameMagic = 0x45E0360E;
  57
  58 static const char *kAsanModuleCtorName = "asan.module_ctor";
  59 static const char *kAsanModuleDtorName = "asan.module_dtor";
  60 static const int   kAsanCtorAndCtorPriority = 1;
  61 static const char *kAsanReportErrorTemplate = "__asan_report_";
  62 static const char *kAsanRegisterGlobalsName = "__asan_register_globals";
  63 static const char *kAsanUnregisterGlobalsName = "__asan_unregister_globals";
  64 static const char *kAsanInitName = "__asan_init";
  65 static const char *kAsanHandleNoReturnName = "__asan_handle_no_return";
  66 static const char *kAsanMappingOffsetName = "__asan_mapping_offset";
  67 static const char *kAsanMappingScaleName = "__asan_mapping_scale";
  68 static const char *kAsanStackMallocName = "__asan_stack_malloc";
  69 static const char *kAsanStackFreeName = "__asan_stack_free";
  70
  71 static const int kAsanStackLeftRedzoneMagic = 0xf1;
  72 static const int kAsanStackMidRedzoneMagic = 0xf2;
  73 static const int kAsanStackRightRedzoneMagic = 0xf3;
  74 static const int kAsanStackPartialRedzoneMagic = 0xf4;
  75
  76 // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
  77 static const size_t kNumberOfAccessSizes = 5;
  78
  79 // Command-line flags.
  80
  81 // This flag may need to be replaced with -f[no-]asan-reads.
  82 static cl::opt<bool> ClInstrumentReads("asan-instrument-reads",
  83        cl::desc("instrument read instructions"), cl::Hidden, cl::init(true));
  84 static cl::opt<bool> ClInstrumentWrites("asan-instrument-writes",
  85        cl::desc("instrument write instructions"), cl::Hidden, cl::init(true));
  86 static cl::opt<bool> ClInstrumentAtomics("asan-instrument-atomics",
  87        cl::desc("instrument atomic instructions (rmw, cmpxchg)"),
  88        cl::Hidden, cl::init(true));
  89 static cl::opt<bool> ClAlwaysSlowPath("asan-always-slow-path",
  90        cl::desc("use instrumentation with slow path for all accesses"),
  91        cl::Hidden, cl::init(false));
  92 // This flag limits the number of instructions to be instrumented
  93 // in any given BB. Normally, this should be set to unlimited (INT_MAX),
  94 // but due to http://llvm.org/bugs/show_bug.cgi?id=12652 we temporary
  95 // set it to 10000.
  96 static cl::opt<int> ClMaxInsnsToInstrumentPerBB("asan-max-ins-per-bb",
  97        cl::init(10000),
  98        cl::desc("maximal number of instructions to instrument in any given BB"),
  99        cl::Hidden);
 100 // This flag may need to be replaced with -f[no]asan-stack.
 101 static cl::opt<bool> ClStack("asan-stack",
 102        cl::desc("Handle stack memory"), cl::Hidden, cl::init(true));
 103 // This flag may need to be replaced with -f[no]asan-use-after-return.
 104 static cl::opt<bool> ClUseAfterReturn("asan-use-after-return",
 105        cl::desc("Check return-after-free"), cl::Hidden, cl::init(false));
 106 // This flag may need to be replaced with -f[no]asan-globals.
 107 static cl::opt<bool> ClGlobals("asan-globals",
 108        cl::desc("Handle global objects"), cl::Hidden, cl::init(true));
 109 static cl::opt<bool> ClMemIntrin("asan-memintrin",
 110        cl::desc("Handle memset/memcpy/memmove"), cl::Hidden, cl::init(true));
 111 // This flag may need to be replaced with -fasan-blacklist.
 112 static cl::opt<std::string>  ClBlackListFile("asan-blacklist",
 113        cl::desc("File containing the list of functions to ignore "
 114                 "during instrumentation"), cl::Hidden);
 115
 116 // These flags allow to change the shadow mapping.
 117 // The shadow mapping looks like
 118 //    Shadow = (Mem >> scale) + (1 << offset_log)
 119 static cl::opt<int> ClMappingScale("asan-mapping-scale",
 120        cl::desc("scale of asan shadow mapping"), cl::Hidden, cl::init(0));
 121 static cl::opt<int> ClMappingOffsetLog("asan-mapping-offset-log",
 122        cl::desc("offset of asan shadow mapping"), cl::Hidden, cl::init(-1));
 123
 124 // Optimization flags. Not user visible, used mostly for testing
 125 // and benchmarking the tool.
 126 static cl::opt<bool> ClOpt("asan-opt",
 127        cl::desc("Optimize instrumentation"), cl::Hidden, cl::init(true));
 128 static cl::opt<bool> ClOptSameTemp("asan-opt-same-temp",
 129        cl::desc("Instrument the same temp just once"), cl::Hidden,
 130        cl::init(true));
 131 static cl::opt<bool> ClOptGlobals("asan-opt-globals",
 132        cl::desc("Don't instrument scalar globals"), cl::Hidden, cl::init(true));
 133
 134 // Debug flags.
 135 static cl::opt<int> ClDebug("asan-debug", cl::desc("debug"), cl::Hidden,
 136                             cl::init(0));
 137 static cl::opt<int> ClDebugStack("asan-debug-stack", cl::desc("debug stack"),
 138                                  cl::Hidden, cl::init(0));
 139 static cl::opt<std::string> ClDebugFunc("asan-debug-func",
 140                                         cl::Hidden, cl::desc("Debug func"));
 141 static cl::opt<int> ClDebugMin("asan-debug-min", cl::desc("Debug min inst"),
 142                                cl::Hidden, cl::init(-1));
 143 static cl::opt<int> ClDebugMax("asan-debug-max", cl::desc("Debug man inst"),
 144                                cl::Hidden, cl::init(-1));
 145
 146 namespace {
 147
 148 /// An object of this type is created while instrumenting every function.
 149 struct AsanFunctionContext {
 150   AsanFunctionContext(Function &Function) : F(Function) { }
 151
 152   Function &F;
 153 };
 154
 155 /// AddressSanitizer: instrument the code in module to find memory bugs.
 156 struct AddressSanitizer : public ModulePass {
 157   AddressSanitizer();
 158   virtual const char *getPassName() const;
 159   void instrumentMop(AsanFunctionContext &AFC, Instruction *I);
 160   void instrumentAddress(AsanFunctionContext &AFC,
 161                          Instruction *OrigIns, IRBuilder<> &IRB,
 162                          Value *Addr, uint32_t TypeSize, bool IsWrite);
 163   Value *createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong,
 164                            Value *ShadowValue, uint32_t TypeSize);
 165   Instruction *generateCrashCode(Instruction *InsertBefore, Value *Addr,
 166                                  bool IsWrite, size_t AccessSizeIndex);
 167   bool instrumentMemIntrinsic(AsanFunctionContext &AFC, MemIntrinsic *MI);
 168   void instrumentMemIntrinsicParam(AsanFunctionContext &AFC,
 169                                    Instruction *OrigIns, Value *Addr,
 170                                    Value *Size,
 171                                    Instruction *InsertBefore, bool IsWrite);
 172   Value *memToShadow(Value *Shadow, IRBuilder<> &IRB);
 173   bool handleFunction(Module &M, Function &F);
 174   bool maybeInsertAsanInitAtFunctionEntry(Function &F);
 175   bool poisonStackInFunction(Module &M, Function &F);
 176   virtual bool runOnModule(Module &M);
 177   bool insertGlobalRedzones(Module &M);
 178   static char ID;  // Pass identification, replacement for typeid
 179
 180  private:
 181
 182   uint64_t getAllocaSizeInBytes(AllocaInst *AI) {
 183     Type *Ty = AI->getAllocatedType();
 184     uint64_t SizeInBytes = TD->getTypeAllocSize(Ty);
 185     return SizeInBytes;
 186   }
 187   uint64_t getAlignedSize(uint64_t SizeInBytes) {
 188     return ((SizeInBytes + RedzoneSize - 1)
 189             / RedzoneSize) * RedzoneSize;
 190   }
 191   uint64_t getAlignedAllocaSize(AllocaInst *AI) {
 192     uint64_t SizeInBytes = getAllocaSizeInBytes(AI);
 193     return getAlignedSize(SizeInBytes);
 194   }
 195
 196   Function *checkInterfaceFunction(Constant *FuncOrBitcast);
 197   void PoisonStack(const ArrayRef<AllocaInst*> &AllocaVec, IRBuilder<> IRB,
 198                    Value *ShadowBase, bool DoPoison);
 199   bool LooksLikeCodeInBug11395(Instruction *I);
 200
 201   LLVMContext *C;
 202   TargetData *TD;
 203   uint64_t MappingOffset;
 204   int MappingScale;
 205   size_t RedzoneSize;
 206   int LongSize;
 207   Type *IntptrTy;
 208   Type *IntptrPtrTy;
 209   Function *AsanCtorFunction;
 210   Function *AsanInitFunction;
 211   Instruction *CtorInsertBefore;
 212   OwningPtr<FunctionBlackList> BL;
 213   // This array is indexed by AccessIsWrite and log2(AccessSize).
 214   Function *AsanErrorCallback[2][kNumberOfAccessSizes];
 215   InlineAsm *EmptyAsm;
 216 };
 217
 218 }  // namespace
 219
 220 char AddressSanitizer::ID = 0;
 221 INITIALIZE_PASS(AddressSanitizer, "asan",
 222     "AddressSanitizer: detects use-after-free and out-of-bounds bugs.",
 223     false, false)
 224 AddressSanitizer::AddressSanitizer() : ModulePass(ID) { }
 225 ModulePass *llvm::createAddressSanitizerPass() {
 226   return new AddressSanitizer();
 227 }
 228
 229 const char *AddressSanitizer::getPassName() const {
 230   return "AddressSanitizer";
 231 }
 232
 233 static size_t TypeSizeToSizeIndex(uint32_t TypeSize) {
 234   size_t Res = CountTrailingZeros_32(TypeSize / 8);
 235   assert(Res < kNumberOfAccessSizes);
 236   return Res;
 237 }
 238
 239 // Create a constant for Str so that we can pass it to the run-time lib.
 240 static GlobalVariable *createPrivateGlobalForString(Module &M, StringRef Str) {
 241   Constant *StrConst = ConstantDataArray::getString(M.getContext(), Str);
 242   return new GlobalVariable(M, StrConst->getType(), true,
 243                             GlobalValue::PrivateLinkage, StrConst, "");
 244 }
 245
 246 // Split the basic block and insert an if-then code.
 247 // Before:
 248 //   Head
 249 //   Cmp
 250 //   Tail
 251 // After:
 252 //   Head
 253 //   if (Cmp)
 254 //     ThenBlock
 255 //   Tail
 256 //
 257 // ThenBlock block is created and its terminator is returned.
 258 // If Unreachable, ThenBlock is terminated with UnreachableInst, otherwise
 259 // it is terminated with BranchInst to Tail.
 260 static TerminatorInst *splitBlockAndInsertIfThen(Value *Cmp, bool Unreachable) {
 261   Instruction *SplitBefore = cast<Instruction>(Cmp)->getNextNode();
 262   BasicBlock *Head = SplitBefore->getParent();
 263   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);
 264   TerminatorInst *HeadOldTerm = Head->getTerminator();
 265   LLVMContext &C = Head->getParent()->getParent()->getContext();
 266   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
 267   TerminatorInst *CheckTerm;
 268   if (Unreachable)
 269     CheckTerm = new UnreachableInst(C, ThenBlock);
 270   else
 271     CheckTerm = BranchInst::Create(Tail, ThenBlock);
 272   BranchInst *HeadNewTerm =
 273     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cmp);
 274   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
 275   return CheckTerm;
 276 }
 277
 278 Value *AddressSanitizer::memToShadow(Value *Shadow, IRBuilder<> &IRB) {
 279   // Shadow >> scale
 280   Shadow = IRB.CreateLShr(Shadow, MappingScale);
 281   if (MappingOffset == 0)
 282     return Shadow;
 283   // (Shadow >> scale) | offset
 284   return IRB.CreateOr(Shadow, ConstantInt::get(IntptrTy,
 285                                                MappingOffset));
 286 }
 287
 288 void AddressSanitizer::instrumentMemIntrinsicParam(
 289     AsanFunctionContext &AFC, Instruction *OrigIns,
 290     Value *Addr, Value *Size, Instruction *InsertBefore, bool IsWrite) {
 291   // Check the first byte.
 292   {
 293     IRBuilder<> IRB(InsertBefore);
 294     instrumentAddress(AFC, OrigIns, IRB, Addr, 8, IsWrite);
 295   }
 296   // Check the last byte.
 297   {
 298     IRBuilder<> IRB(InsertBefore);
 299     Value *SizeMinusOne = IRB.CreateSub(
 300         Size, ConstantInt::get(Size->getType(), 1));
 301     SizeMinusOne = IRB.CreateIntCast(SizeMinusOne, IntptrTy, false);
 302     Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
 303     Value *AddrPlusSizeMinisOne = IRB.CreateAdd(AddrLong, SizeMinusOne);
 304     instrumentAddress(AFC, OrigIns, IRB, AddrPlusSizeMinisOne, 8, IsWrite);
 305   }
 306 }
 307
 308 // Instrument memset/memmove/memcpy
 309 bool AddressSanitizer::instrumentMemIntrinsic(AsanFunctionContext &AFC,
 310                                               MemIntrinsic *MI) {
 311   Value *Dst = MI->getDest();
 312   MemTransferInst *MemTran = dyn_cast<MemTransferInst>(MI);
 313   Value *Src = MemTran ? MemTran->getSource() : 0;
 314   Value *Length = MI->getLength();
 315
 316   Constant *ConstLength = dyn_cast<Constant>(Length);
 317   Instruction *InsertBefore = MI;
 318   if (ConstLength) {
 319     if (ConstLength->isNullValue()) return false;
 320   } else {
 321     // The size is not a constant so it could be zero -- check at run-time.
 322     IRBuilder<> IRB(InsertBefore);
 323
 324     Value *Cmp = IRB.CreateICmpNE(Length,
 325                                   Constant::getNullValue(Length->getType()));
 326     InsertBefore = splitBlockAndInsertIfThen(Cmp, false);
 327   }
 328
 329   instrumentMemIntrinsicParam(AFC, MI, Dst, Length, InsertBefore, true);
 330   if (Src)
 331     instrumentMemIntrinsicParam(AFC, MI, Src, Length, InsertBefore, false);
 332   return true;
 333 }
 334
 335 // If I is an interesting memory access, return the PointerOperand
 336 // and set IsWrite. Otherwise return NULL.
 337 static Value *isInterestingMemoryAccess(Instruction *I, bool *IsWrite) {
 338   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 339     if (!ClInstrumentReads) return NULL;
 340     *IsWrite = false;
 341     return LI->getPointerOperand();
 342   }
 343   if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 344     if (!ClInstrumentWrites) return NULL;
 345     *IsWrite = true;
 346     return SI->getPointerOperand();
 347   }
 348   if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
 349     if (!ClInstrumentAtomics) return NULL;
 350     *IsWrite = true;
 351     return RMW->getPointerOperand();
 352   }
 353   if (AtomicCmpXchgInst *XCHG = dyn_cast<AtomicCmpXchgInst>(I)) {
 354     if (!ClInstrumentAtomics) return NULL;
 355     *IsWrite = true;
 356     return XCHG->getPointerOperand();
 357   }
 358   return NULL;
 359 }
 360
 361 void AddressSanitizer::instrumentMop(AsanFunctionContext &AFC, Instruction *I) {
 362   bool IsWrite;
 363   Value *Addr = isInterestingMemoryAccess(I, &IsWrite);
 364   assert(Addr);
 365   if (ClOpt && ClOptGlobals && isa<GlobalVariable>(Addr)) {
 366     // We are accessing a global scalar variable. Nothing to catch here.
 367     return;
 368   }
 369   Type *OrigPtrTy = Addr->getType();
 370   Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
 371
 372   assert(OrigTy->isSized());
 373   uint32_t TypeSize = TD->getTypeStoreSizeInBits(OrigTy);
 374
 375   if (TypeSize != 8  && TypeSize != 16 &&
 376       TypeSize != 32 && TypeSize != 64 && TypeSize != 128) {
 377     // Ignore all unusual sizes.
 378     return;
 379   }
 380
 381   IRBuilder<> IRB(I);
 382   instrumentAddress(AFC, I, IRB, Addr, TypeSize, IsWrite);
 383 }
 384
 385 // Validate the result of Module::getOrInsertFunction called for an interface
 386 // function of AddressSanitizer. If the instrumented module defines a function
 387 // with the same name, their prototypes must match, otherwise
 388 // getOrInsertFunction returns a bitcast.
 389 Function *AddressSanitizer::checkInterfaceFunction(Constant *FuncOrBitcast) {
 390   if (isa<Function>(FuncOrBitcast)) return cast<Function>(FuncOrBitcast);
 391   FuncOrBitcast->dump();
 392   report_fatal_error("trying to redefine an AddressSanitizer "
 393                      "interface function");
 394 }
 395
 396 Instruction *AddressSanitizer::generateCrashCode(
 397     Instruction *InsertBefore, Value *Addr,
 398     bool IsWrite, size_t AccessSizeIndex) {
 399   IRBuilder<> IRB(InsertBefore);
 400   CallInst *Call = IRB.CreateCall(AsanErrorCallback[IsWrite][AccessSizeIndex],
 401                                   Addr);
 402   // We don't do Call->setDoesNotReturn() because the BB already has
 403   // UnreachableInst at the end.
 404   // This EmptyAsm is required to avoid callback merge.
 405   IRB.CreateCall(EmptyAsm);
 406   return Call;
 407 }
 408
 409 Value *AddressSanitizer::createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong,
 410                                             Value *ShadowValue,
 411                                             uint32_t TypeSize) {
 412   size_t Granularity = 1 << MappingScale;
 413   // Addr & (Granularity - 1)
 414   Value *LastAccessedByte = IRB.CreateAnd(
 415       AddrLong, ConstantInt::get(IntptrTy, Granularity - 1));
 416   // (Addr & (Granularity - 1)) + size - 1
 417   if (TypeSize / 8 > 1)
 418     LastAccessedByte = IRB.CreateAdd(
 419         LastAccessedByte, ConstantInt::get(IntptrTy, TypeSize / 8 - 1));
 420   // (uint8_t) ((Addr & (Granularity-1)) + size - 1)
 421   LastAccessedByte = IRB.CreateIntCast(
 422       LastAccessedByte, ShadowValue->getType(), false);
 423   // ((uint8_t) ((Addr & (Granularity-1)) + size - 1)) >= ShadowValue
 424   return IRB.CreateICmpSGE(LastAccessedByte, ShadowValue);
 425 }
 426
 427 void AddressSanitizer::instrumentAddress(AsanFunctionContext &AFC,
 428                                          Instruction *OrigIns,
 429                                          IRBuilder<> &IRB, Value *Addr,
 430                                          uint32_t TypeSize, bool IsWrite) {
 431   Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);
 432
 433   Type *ShadowTy  = IntegerType::get(
 434       *C, std::max(8U, TypeSize >> MappingScale));
 435   Type *ShadowPtrTy = PointerType::get(ShadowTy, 0);
 436   Value *ShadowPtr = memToShadow(AddrLong, IRB);
 437   Value *CmpVal = Constant::getNullValue(ShadowTy);
 438   Value *ShadowValue = IRB.CreateLoad(
 439       IRB.CreateIntToPtr(ShadowPtr, ShadowPtrTy));
 440
 441   Value *Cmp = IRB.CreateICmpNE(ShadowValue, CmpVal);
 442   size_t AccessSizeIndex = TypeSizeToSizeIndex(TypeSize);
 443   size_t Granularity = 1 << MappingScale;
 444   TerminatorInst *CrashTerm = 0;
 445
 446   if (ClAlwaysSlowPath || (TypeSize < 8 * Granularity)) {
 447     TerminatorInst *CheckTerm = splitBlockAndInsertIfThen(Cmp, false);
 448     assert(dyn_cast<BranchInst>(CheckTerm)->isUnconditional());
 449     BasicBlock *NextBB = CheckTerm->getSuccessor(0);
 450     IRB.SetInsertPoint(CheckTerm);
 451     Value *Cmp2 = createSlowPathCmp(IRB, AddrLong, ShadowValue, TypeSize);
 452     BasicBlock *CrashBlock = BasicBlock::Create(*C, "", &AFC.F, NextBB);
 453     CrashTerm = new UnreachableInst(*C, CrashBlock);
 454     BranchInst *NewTerm = BranchInst::Create(CrashBlock, NextBB, Cmp2);
 455     ReplaceInstWithInst(CheckTerm, NewTerm);
 456   } else {
 457     CrashTerm = splitBlockAndInsertIfThen(Cmp, true);
 458   }
 459
 460   Instruction *Crash =
 461       generateCrashCode(CrashTerm, AddrLong, IsWrite, AccessSizeIndex);
 462   Crash->setDebugLoc(OrigIns->getDebugLoc());
 463 }
 464
 465 // This function replaces all global variables with new variables that have
 466 // trailing redzones. It also creates a function that poisons
 467 // redzones and inserts this function into llvm.global_ctors.
 468 bool AddressSanitizer::insertGlobalRedzones(Module &M) {
 469   SmallVector<GlobalVariable *, 16> GlobalsToChange;
 470
 471   for (Module::GlobalListType::iterator G = M.getGlobalList().begin(),
 472        E = M.getGlobalList().end(); G != E; ++G) {
 473     Type *Ty = cast<PointerType>(G->getType())->getElementType();
 474     DEBUG(dbgs() << "GLOBAL: " << *G);
 475
 476     if (!Ty->isSized()) continue;
 477     if (!G->hasInitializer()) continue;
 478     // Touch only those globals that will not be defined in other modules.
 479     // Don't handle ODR type linkages since other modules may be built w/o asan.
 480     if (G->getLinkage() != GlobalVariable::ExternalLinkage &&
 481         G->getLinkage() != GlobalVariable::PrivateLinkage &&
 482         G->getLinkage() != GlobalVariable::InternalLinkage)
 483       continue;
 484     // Two problems with thread-locals:
 485     //   - The address of the main thread's copy can't be computed at link-time.
 486     //   - Need to poison all copies, not just the main thread's one.
 487     if (G->isThreadLocal())
 488       continue;
 489     // For now, just ignore this Alloca if the alignment is large.
 490     if (G->getAlignment() > RedzoneSize) continue;
 491
 492     // Ignore all the globals with the names starting with "\01L_OBJC_".
 493     // Many of those are put into the .cstring section. The linker compresses
 494     // that section by removing the spare \0s after the string terminator, so
 495     // our redzones get broken.
 496     if ((G->getName().find("\01L_OBJC_") == 0) ||
 497         (G->getName().find("\01l_OBJC_") == 0)) {
 498       DEBUG(dbgs() << "Ignoring \\01L_OBJC_* global: " << *G);
 499       continue;
 500     }
 501
 502     if (G->hasSection()) {
 503       StringRef Section(G->getSection());
 504       // Ignore the globals from the __OBJC section. The ObjC runtime assumes
 505       // those conform to /usr/lib/objc/runtime.h, so we can't add redzones to
 506       // them.
 507       if ((Section.find("__OBJC,") == 0) ||
 508           (Section.find("__DATA, __objc_") == 0)) {
 509         DEBUG(dbgs() << "Ignoring ObjC runtime global: " << *G);
 510         continue;
 511       }
 512       // See http://code.google.com/p/address-sanitizer/issues/detail?id=32
 513       // Constant CFString instances are compiled in the following way:
 514       //  -- the string buffer is emitted into
 515       //     __TEXT,__cstring,cstring_literals
 516       //  -- the constant NSConstantString structure referencing that buffer
 517       //     is placed into __DATA,__cfstring
 518       // Therefore there's no point in placing redzones into __DATA,__cfstring.
 519       // Moreover, it causes the linker to crash on OS X 10.7
 520       if (Section.find("__DATA,__cfstring") == 0) {
 521         DEBUG(dbgs() << "Ignoring CFString: " << *G);
 522         continue;
 523       }
 524     }
 525
 526     GlobalsToChange.push_back(G);
 527   }
 528
 529   size_t n = GlobalsToChange.size();
 530   if (n == 0) return false;
 531
 532   // A global is described by a structure
 533   //   size_t beg;
 534   //   size_t size;
 535   //   size_t size_with_redzone;
 536   //   const char *name;
 537   // We initialize an array of such structures and pass it to a run-time call.
 538   StructType *GlobalStructTy = StructType::get(IntptrTy, IntptrTy,
 539                                                IntptrTy, IntptrTy, NULL);
 540   SmallVector<Constant *, 16> Initializers(n);
 541
 542   IRBuilder<> IRB(CtorInsertBefore);
 543
 544   for (size_t i = 0; i < n; i++) {
 545     GlobalVariable *G = GlobalsToChange[i];
 546     PointerType *PtrTy = cast<PointerType>(G->getType());
 547     Type *Ty = PtrTy->getElementType();
 548     uint64_t SizeInBytes = TD->getTypeAllocSize(Ty);
 549     uint64_t RightRedzoneSize = RedzoneSize +
 550         (RedzoneSize - (SizeInBytes % RedzoneSize));
 551     Type *RightRedZoneTy = ArrayType::get(IRB.getInt8Ty(), RightRedzoneSize);
 552
 553     StructType *NewTy = StructType::get(Ty, RightRedZoneTy, NULL);
 554     Constant *NewInitializer = ConstantStruct::get(
 555         NewTy, G->getInitializer(),
 556         Constant::getNullValue(RightRedZoneTy), NULL);
 557
 558     SmallString<2048> DescriptionOfGlobal = G->getName();
 559     DescriptionOfGlobal += " (";
 560     DescriptionOfGlobal += M.getModuleIdentifier();
 561     DescriptionOfGlobal += ")";
 562     GlobalVariable *Name = createPrivateGlobalForString(M, DescriptionOfGlobal);
 563
 564     // Create a new global variable with enough space for a redzone.
 565     GlobalVariable *NewGlobal = new GlobalVariable(
 566         M, NewTy, G->isConstant(), G->getLinkage(),
 567         NewInitializer, "", G, G->getThreadLocalMode());
 568     NewGlobal->copyAttributesFrom(G);
 569     NewGlobal->setAlignment(RedzoneSize);
 570
 571     Value *Indices2[2];
 572     Indices2[0] = IRB.getInt32(0);
 573     Indices2[1] = IRB.getInt32(0);
 574
 575     G->replaceAllUsesWith(
 576         ConstantExpr::getGetElementPtr(NewGlobal, Indices2, true));
 577     NewGlobal->takeName(G);
 578     G->eraseFromParent();
 579
 580     Initializers[i] = ConstantStruct::get(
 581         GlobalStructTy,
 582         ConstantExpr::getPointerCast(NewGlobal, IntptrTy),
 583         ConstantInt::get(IntptrTy, SizeInBytes),
 584         ConstantInt::get(IntptrTy, SizeInBytes + RightRedzoneSize),
 585         ConstantExpr::getPointerCast(Name, IntptrTy),
 586         NULL);
 587     DEBUG(dbgs() << "NEW GLOBAL:\n" << *NewGlobal);
 588   }
 589
 590   ArrayType *ArrayOfGlobalStructTy = ArrayType::get(GlobalStructTy, n);
 591   GlobalVariable *AllGlobals = new GlobalVariable(
 592       M, ArrayOfGlobalStructTy, false, GlobalVariable::PrivateLinkage,
 593       ConstantArray::get(ArrayOfGlobalStructTy, Initializers), "");
 594
 595   Function *AsanRegisterGlobals = checkInterfaceFunction(M.getOrInsertFunction(
 596       kAsanRegisterGlobalsName, IRB.getVoidTy(), IntptrTy, IntptrTy, NULL));
 597   AsanRegisterGlobals->setLinkage(Function::ExternalLinkage);
 598
 599   IRB.CreateCall2(AsanRegisterGlobals,
 600                   IRB.CreatePointerCast(AllGlobals, IntptrTy),
 601                   ConstantInt::get(IntptrTy, n));
 602
 603   // We also need to unregister globals at the end, e.g. when a shared library
 604   // gets closed.
 605   Function *AsanDtorFunction = Function::Create(
 606       FunctionType::get(Type::getVoidTy(*C), false),
 607       GlobalValue::InternalLinkage, kAsanModuleDtorName, &M);
 608   BasicBlock *AsanDtorBB = BasicBlock::Create(*C, "", AsanDtorFunction);
 609   IRBuilder<> IRB_Dtor(ReturnInst::Create(*C, AsanDtorBB));
 610   Function *AsanUnregisterGlobals =
 611       checkInterfaceFunction(M.getOrInsertFunction(
 612           kAsanUnregisterGlobalsName,
 613           IRB.getVoidTy(), IntptrTy, IntptrTy, NULL));
 614   AsanUnregisterGlobals->setLinkage(Function::ExternalLinkage);
 615
 616   IRB_Dtor.CreateCall2(AsanUnregisterGlobals,
 617                        IRB.CreatePointerCast(AllGlobals, IntptrTy),
 618                        ConstantInt::get(IntptrTy, n));
 619   appendToGlobalDtors(M, AsanDtorFunction, kAsanCtorAndCtorPriority);
 620
 621   DEBUG(dbgs() << M);
 622   return true;
 623 }
 624
 625 // virtual
 626 bool AddressSanitizer::runOnModule(Module &M) {
 627   // Initialize the private fields. No one has accessed them before.
 628   TD = getAnalysisIfAvailable<TargetData>();
 629   if (!TD)
 630     return false;
 631   BL.reset(new FunctionBlackList(ClBlackListFile));
 632
 633   C = &(M.getContext());
 634   LongSize = TD->getPointerSizeInBits();
 635   IntptrTy = Type::getIntNTy(*C, LongSize);
 636   IntptrPtrTy = PointerType::get(IntptrTy, 0);
 637
 638   AsanCtorFunction = Function::Create(
 639       FunctionType::get(Type::getVoidTy(*C), false),
 640       GlobalValue::InternalLinkage, kAsanModuleCtorName, &M);
 641   BasicBlock *AsanCtorBB = BasicBlock::Create(*C, "", AsanCtorFunction);
 642   CtorInsertBefore = ReturnInst::Create(*C, AsanCtorBB);
 643
 644   // call __asan_init in the module ctor.
 645   IRBuilder<> IRB(CtorInsertBefore);
 646   AsanInitFunction = checkInterfaceFunction(
 647       M.getOrInsertFunction(kAsanInitName, IRB.getVoidTy(), NULL));
 648   AsanInitFunction->setLinkage(Function::ExternalLinkage);
 649   IRB.CreateCall(AsanInitFunction);
 650
 651   // Create __asan_report* callbacks.
 652   for (size_t AccessIsWrite = 0; AccessIsWrite <= 1; AccessIsWrite++) {
 653     for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
 654          AccessSizeIndex++) {
 655       // IsWrite and TypeSize are encoded in the function name.
 656       std::string FunctionName = std::string(kAsanReportErrorTemplate) +
 657           (AccessIsWrite ? "store" : "load") + itostr(1 << AccessSizeIndex);
 658       // If we are merging crash callbacks, they have two parameters.
 659       AsanErrorCallback[AccessIsWrite][AccessSizeIndex] = cast<Function>(
 660           M.getOrInsertFunction(FunctionName, IRB.getVoidTy(), IntptrTy, NULL));
 661     }
 662   }
 663   // We insert an empty inline asm after __asan_report* to avoid callback merge.
 664   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
 665                             StringRef(""), StringRef(""),
 666                             /*hasSideEffects=*/true);
 667
 668   llvm::Triple targetTriple(M.getTargetTriple());
 669   bool isAndroid = targetTriple.getEnvironment() == llvm::Triple::ANDROIDEABI;
 670
 671   MappingOffset = isAndroid ? kDefaultShadowOffsetAndroid :
 672     (LongSize == 32 ? kDefaultShadowOffset32 : kDefaultShadowOffset64);
 673   if (ClMappingOffsetLog >= 0) {
 674     if (ClMappingOffsetLog == 0) {
 675       // special case
 676       MappingOffset = 0;
 677     } else {
 678       MappingOffset = 1ULL << ClMappingOffsetLog;
 679     }
 680   }
 681   MappingScale = kDefaultShadowScale;
 682   if (ClMappingScale) {
 683     MappingScale = ClMappingScale;
 684   }
 685   // Redzone used for stack and globals is at least 32 bytes.
 686   // For scales 6 and 7, the redzone has to be 64 and 128 bytes respectively.
 687   RedzoneSize = std::max(32, (int)(1 << MappingScale));
 688
 689   bool Res = false;
 690
 691   if (ClGlobals)
 692     Res |= insertGlobalRedzones(M);
 693
 694   if (ClMappingOffsetLog >= 0) {
 695     // Tell the run-time the current values of mapping offset and scale.
 696     GlobalValue *asan_mapping_offset =
 697         new GlobalVariable(M, IntptrTy, true, GlobalValue::LinkOnceODRLinkage,
 698                        ConstantInt::get(IntptrTy, MappingOffset),
 699                        kAsanMappingOffsetName);
 700     // Read the global, otherwise it may be optimized away.
 701     IRB.CreateLoad(asan_mapping_offset, true);
 702   }
 703   if (ClMappingScale) {
 704     GlobalValue *asan_mapping_scale =
 705         new GlobalVariable(M, IntptrTy, true, GlobalValue::LinkOnceODRLinkage,
 706                            ConstantInt::get(IntptrTy, MappingScale),
 707                            kAsanMappingScaleName);
 708     // Read the global, otherwise it may be optimized away.
 709     IRB.CreateLoad(asan_mapping_scale, true);
 710   }
 711
 712
 713   for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 714     if (F->isDeclaration()) continue;
 715     Res |= handleFunction(M, *F);
 716   }
 717
 718   appendToGlobalCtors(M, AsanCtorFunction, kAsanCtorAndCtorPriority);
 719
 720   return Res;
 721 }
 722
 723 bool AddressSanitizer::maybeInsertAsanInitAtFunctionEntry(Function &F) {
 724   // For each NSObject descendant having a +load method, this method is invoked
 725   // by the ObjC runtime before any of the static constructors is called.
 726   // Therefore we need to instrument such methods with a call to __asan_init
 727   // at the beginning in order to initialize our runtime before any access to
 728   // the shadow memory.
 729   // We cannot just ignore these methods, because they may call other
 730   // instrumented functions.
 731   if (F.getName().find(" load]") != std::string::npos) {
 732     IRBuilder<> IRB(F.begin()->begin());
 733     IRB.CreateCall(AsanInitFunction);
 734     return true;
 735   }
 736   return false;
 737 }
 738
 739 bool AddressSanitizer::handleFunction(Module &M, Function &F) {
 740   if (BL->isIn(F)) return false;
 741   if (&F == AsanCtorFunction) return false;
 742
 743   // If needed, insert __asan_init before checking for AddressSafety attr.
 744   maybeInsertAsanInitAtFunctionEntry(F);
 745
 746   if (!F.hasFnAttr(Attribute::AddressSafety)) return false;
 747
 748   if (!ClDebugFunc.empty() && ClDebugFunc != F.getName())
 749     return false;
 750   // We want to instrument every address only once per basic block
 751   // (unless there are calls between uses).
 752   SmallSet<Value*, 16> TempsToInstrument;
 753   SmallVector<Instruction*, 16> ToInstrument;
 754   SmallVector<Instruction*, 8> NoReturnCalls;
 755   bool IsWrite;
 756
 757   // Fill the set of memory operations to instrument.
 758   for (Function::iterator FI = F.begin(), FE = F.end();
 759        FI != FE; ++FI) {
 760     TempsToInstrument.clear();
 761     int NumInsnsPerBB = 0;
 762     for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
 763          BI != BE; ++BI) {
 764       if (LooksLikeCodeInBug11395(BI)) return false;
 765       if (Value *Addr = isInterestingMemoryAccess(BI, &IsWrite)) {
 766         if (ClOpt && ClOptSameTemp) {
 767           if (!TempsToInstrument.insert(Addr))
 768             continue;  // We've seen this temp in the current BB.
 769         }
 770       } else if (isa<MemIntrinsic>(BI) && ClMemIntrin) {
 771         // ok, take it.
 772       } else {
 773         if (CallInst *CI = dyn_cast<CallInst>(BI)) {
 774           // A call inside BB.
 775           TempsToInstrument.clear();
 776           if (CI->doesNotReturn()) {
 777             NoReturnCalls.push_back(CI);
 778           }
 779         }
 780         continue;
 781       }
 782       ToInstrument.push_back(BI);
 783       NumInsnsPerBB++;
 784       if (NumInsnsPerBB >= ClMaxInsnsToInstrumentPerBB)
 785         break;
 786     }
 787   }
 788
 789   AsanFunctionContext AFC(F);
 790
 791   // Instrument.
 792   int NumInstrumented = 0;
 793   for (size_t i = 0, n = ToInstrument.size(); i != n; i++) {
 794     Instruction *Inst = ToInstrument[i];
 795     if (ClDebugMin < 0 || ClDebugMax < 0 ||
 796         (NumInstrumented >= ClDebugMin && NumInstrumented <= ClDebugMax)) {
 797       if (isInterestingMemoryAccess(Inst, &IsWrite))
 798         instrumentMop(AFC, Inst);
 799       else
 800         instrumentMemIntrinsic(AFC, cast<MemIntrinsic>(Inst));
 801     }
 802     NumInstrumented++;
 803   }
 804
 805   DEBUG(dbgs() << F);
 806
 807   bool ChangedStack = poisonStackInFunction(M, F);
 808
 809   // We must unpoison the stack before every NoReturn call (throw, _exit, etc).
 810   // See e.g. http://code.google.com/p/address-sanitizer/issues/detail?id=37
 811   for (size_t i = 0, n = NoReturnCalls.size(); i != n; i++) {
 812     Instruction *CI = NoReturnCalls[i];
 813     IRBuilder<> IRB(CI);
 814     IRB.CreateCall(M.getOrInsertFunction(kAsanHandleNoReturnName,
 815                                          IRB.getVoidTy(), NULL));
 816   }
 817
 818   return NumInstrumented > 0 || ChangedStack || !NoReturnCalls.empty();
 819 }
 820
 821 static uint64_t ValueForPoison(uint64_t PoisonByte, size_t ShadowRedzoneSize) {
 822   if (ShadowRedzoneSize == 1) return PoisonByte;
 823   if (ShadowRedzoneSize == 2) return (PoisonByte << 8) + PoisonByte;
 824   if (ShadowRedzoneSize == 4)
 825     return (PoisonByte << 24) + (PoisonByte << 16) +
 826         (PoisonByte << 8) + (PoisonByte);
 827   llvm_unreachable("ShadowRedzoneSize is either 1, 2 or 4");
 828 }
 829
 830 static void PoisonShadowPartialRightRedzone(uint8_t *Shadow,
 831                                             size_t Size,
 832                                             size_t RedzoneSize,
 833                                             size_t ShadowGranularity,
 834                                             uint8_t Magic) {
 835   for (size_t i = 0; i < RedzoneSize;
 836        i+= ShadowGranularity, Shadow++) {
 837     if (i + ShadowGranularity <= Size) {
 838       *Shadow = 0;  // fully addressable
 839     } else if (i >= Size) {
 840       *Shadow = Magic;  // unaddressable
 841     } else {
 842       *Shadow = Size - i;  // first Size-i bytes are addressable
 843     }
 844   }
 845 }
 846
 847 void AddressSanitizer::PoisonStack(const ArrayRef<AllocaInst*> &AllocaVec,
 848                                    IRBuilder<> IRB,
 849                                    Value *ShadowBase, bool DoPoison) {
 850   size_t ShadowRZSize = RedzoneSize >> MappingScale;
 851   assert(ShadowRZSize >= 1 && ShadowRZSize <= 4);
 852   Type *RZTy = Type::getIntNTy(*C, ShadowRZSize * 8);
 853   Type *RZPtrTy = PointerType::get(RZTy, 0);
 854
 855   Value *PoisonLeft  = ConstantInt::get(RZTy,
 856     ValueForPoison(DoPoison ? kAsanStackLeftRedzoneMagic : 0LL, ShadowRZSize));
 857   Value *PoisonMid   = ConstantInt::get(RZTy,
 858     ValueForPoison(DoPoison ? kAsanStackMidRedzoneMagic : 0LL, ShadowRZSize));
 859   Value *PoisonRight = ConstantInt::get(RZTy,
 860     ValueForPoison(DoPoison ? kAsanStackRightRedzoneMagic : 0LL, ShadowRZSize));
 861
 862   // poison the first red zone.
 863   IRB.CreateStore(PoisonLeft, IRB.CreateIntToPtr(ShadowBase, RZPtrTy));
 864
 865   // poison all other red zones.
 866   uint64_t Pos = RedzoneSize;
 867   for (size_t i = 0, n = AllocaVec.size(); i < n; i++) {
 868     AllocaInst *AI = AllocaVec[i];
 869     uint64_t SizeInBytes = getAllocaSizeInBytes(AI);
 870     uint64_t AlignedSize = getAlignedAllocaSize(AI);
 871     assert(AlignedSize - SizeInBytes < RedzoneSize);
 872     Value *Ptr = NULL;
 873
 874     Pos += AlignedSize;
 875
 876     assert(ShadowBase->getType() == IntptrTy);
 877     if (SizeInBytes < AlignedSize) {
 878       // Poison the partial redzone at right
 879       Ptr = IRB.CreateAdd(
 880           ShadowBase, ConstantInt::get(IntptrTy,
 881                                        (Pos >> MappingScale) - ShadowRZSize));
 882       size_t AddressableBytes = RedzoneSize - (AlignedSize - SizeInBytes);
 883       uint32_t Poison = 0;
 884       if (DoPoison) {
 885         PoisonShadowPartialRightRedzone((uint8_t*)&Poison, AddressableBytes,
 886                                         RedzoneSize,
 887                                         1ULL << MappingScale,
 888                                         kAsanStackPartialRedzoneMagic);
 889       }
 890       Value *PartialPoison = ConstantInt::get(RZTy, Poison);
 891       IRB.CreateStore(PartialPoison, IRB.CreateIntToPtr(Ptr, RZPtrTy));
 892     }
 893
 894     // Poison the full redzone at right.
 895     Ptr = IRB.CreateAdd(ShadowBase,
 896                         ConstantInt::get(IntptrTy, Pos >> MappingScale));
 897     Value *Poison = i == AllocaVec.size() - 1 ? PoisonRight : PoisonMid;
 898     IRB.CreateStore(Poison, IRB.CreateIntToPtr(Ptr, RZPtrTy));
 899
 900     Pos += RedzoneSize;
 901   }
 902 }
 903
 904 // Workaround for bug 11395: we don't want to instrument stack in functions
 905 // with large assembly blobs (32-bit only), otherwise reg alloc may crash.
 906 // FIXME: remove once the bug 11395 is fixed.
 907 bool AddressSanitizer::LooksLikeCodeInBug11395(Instruction *I) {
 908   if (LongSize != 32) return false;
 909   CallInst *CI = dyn_cast<CallInst>(I);
 910   if (!CI || !CI->isInlineAsm()) return false;
 911   if (CI->getNumArgOperands() <= 5) return false;
 912   // We have inline assembly with quite a few arguments.
 913   return true;
 914 }
 915
 916 // Find all static Alloca instructions and put
 917 // poisoned red zones around all of them.
 918 // Then unpoison everything back before the function returns.
 919 //
 920 // Stack poisoning does not play well with exception handling.
 921 // When an exception is thrown, we essentially bypass the code
 922 // that unpoisones the stack. This is why the run-time library has
 923 // to intercept __cxa_throw (as well as longjmp, etc) and unpoison the entire
 924 // stack in the interceptor. This however does not work inside the
 925 // actual function which catches the exception. Most likely because the
 926 // compiler hoists the load of the shadow value somewhere too high.
 927 // This causes asan to report a non-existing bug on 453.povray.
 928 // It sounds like an LLVM bug.
 929 bool AddressSanitizer::poisonStackInFunction(Module &M, Function &F) {
 930   if (!ClStack) return false;
 931   SmallVector<AllocaInst*, 16> AllocaVec;
 932   SmallVector<Instruction*, 8> RetVec;
 933   uint64_t TotalSize = 0;
 934
 935   // Filter out Alloca instructions we want (and can) handle.
 936   // Collect Ret instructions.
 937   for (Function::iterator FI = F.begin(), FE = F.end();
 938        FI != FE; ++FI) {
 939     BasicBlock &BB = *FI;
 940     for (BasicBlock::iterator BI = BB.begin(), BE = BB.end();
 941          BI != BE; ++BI) {
 942       if (isa<ReturnInst>(BI)) {
 943           RetVec.push_back(BI);
 944           continue;
 945       }
 946
 947       AllocaInst *AI = dyn_cast<AllocaInst>(BI);
 948       if (!AI) continue;
 949       if (AI->isArrayAllocation()) continue;
 950       if (!AI->isStaticAlloca()) continue;
 951       if (!AI->getAllocatedType()->isSized()) continue;
 952       if (AI->getAlignment() > RedzoneSize) continue;
 953       AllocaVec.push_back(AI);
 954       uint64_t AlignedSize =  getAlignedAllocaSize(AI);
 955       TotalSize += AlignedSize;
 956     }
 957   }
 958
 959   if (AllocaVec.empty()) return false;
 960
 961   uint64_t LocalStackSize = TotalSize + (AllocaVec.size() + 1) * RedzoneSize;
 962
 963   bool DoStackMalloc = ClUseAfterReturn
 964       && LocalStackSize <= kMaxStackMallocSize;
 965
 966   Instruction *InsBefore = AllocaVec[0];
 967   IRBuilder<> IRB(InsBefore);
 968
 969
 970   Type *ByteArrayTy = ArrayType::get(IRB.getInt8Ty(), LocalStackSize);
 971   AllocaInst *MyAlloca =
 972       new AllocaInst(ByteArrayTy, "MyAlloca", InsBefore);
 973   MyAlloca->setAlignment(RedzoneSize);
 974   assert(MyAlloca->isStaticAlloca());
 975   Value *OrigStackBase = IRB.CreatePointerCast(MyAlloca, IntptrTy);
 976   Value *LocalStackBase = OrigStackBase;
 977
 978   if (DoStackMalloc) {
 979     Value *AsanStackMallocFunc = M.getOrInsertFunction(
 980         kAsanStackMallocName, IntptrTy, IntptrTy, IntptrTy, NULL);
 981     LocalStackBase = IRB.CreateCall2(AsanStackMallocFunc,
 982         ConstantInt::get(IntptrTy, LocalStackSize), OrigStackBase);
 983   }
 984
 985   // This string will be parsed by the run-time (DescribeStackAddress).
 986   SmallString<2048> StackDescriptionStorage;
 987   raw_svector_ostream StackDescription(StackDescriptionStorage);
 988   StackDescription << F.getName() << " " << AllocaVec.size() << " ";
 989
 990   uint64_t Pos = RedzoneSize;
 991   // Replace Alloca instructions with base+offset.
 992   for (size_t i = 0, n = AllocaVec.size(); i < n; i++) {
 993     AllocaInst *AI = AllocaVec[i];
 994     uint64_t SizeInBytes = getAllocaSizeInBytes(AI);
 995     StringRef Name = AI->getName();
 996     StackDescription << Pos << " " << SizeInBytes << " "
 997                      << Name.size() << " " << Name << " ";
 998     uint64_t AlignedSize = getAlignedAllocaSize(AI);
 999     assert((AlignedSize % RedzoneSize) == 0);
1000     AI->replaceAllUsesWith(
1001         IRB.CreateIntToPtr(
1002             IRB.CreateAdd(LocalStackBase, ConstantInt::get(IntptrTy, Pos)),
1003             AI->getType()));
1004     Pos += AlignedSize + RedzoneSize;
1005   }
1006   assert(Pos == LocalStackSize);
1007
1008   // Write the Magic value and the frame description constant to the redzone.
1009   Value *BasePlus0 = IRB.CreateIntToPtr(LocalStackBase, IntptrPtrTy);
1010   IRB.CreateStore(ConstantInt::get(IntptrTy, kCurrentStackFrameMagic),
1011                   BasePlus0);
1012   Value *BasePlus1 = IRB.CreateAdd(LocalStackBase,
1013                                    ConstantInt::get(IntptrTy, LongSize/8));
1014   BasePlus1 = IRB.CreateIntToPtr(BasePlus1, IntptrPtrTy);
1015   Value *Description = IRB.CreatePointerCast(
1016       createPrivateGlobalForString(M, StackDescription.str()),
1017       IntptrTy);
1018   IRB.CreateStore(Description, BasePlus1);
1019
1020   // Poison the stack redzones at the entry.
1021   Value *ShadowBase = memToShadow(LocalStackBase, IRB);
1022   PoisonStack(ArrayRef<AllocaInst*>(AllocaVec), IRB, ShadowBase, true);
1023
1024   Value *AsanStackFreeFunc = NULL;
1025   if (DoStackMalloc) {
1026     AsanStackFreeFunc = M.getOrInsertFunction(
1027         kAsanStackFreeName, IRB.getVoidTy(),
1028         IntptrTy, IntptrTy, IntptrTy, NULL);
1029   }
1030
1031   // Unpoison the stack before all ret instructions.
1032   for (size_t i = 0, n = RetVec.size(); i < n; i++) {
1033     Instruction *Ret = RetVec[i];
1034     IRBuilder<> IRBRet(Ret);
1035
1036     // Mark the current frame as retired.
1037     IRBRet.CreateStore(ConstantInt::get(IntptrTy, kRetiredStackFrameMagic),
1038                        BasePlus0);
1039     // Unpoison the stack.
1040     PoisonStack(ArrayRef<AllocaInst*>(AllocaVec), IRBRet, ShadowBase, false);
1041
1042     if (DoStackMalloc) {
1043       IRBRet.CreateCall3(AsanStackFreeFunc, LocalStackBase,
1044                          ConstantInt::get(IntptrTy, LocalStackSize),
1045                          OrigStackBase);
1046     }
1047   }
1048
1049   if (ClDebugStack) {
1050     DEBUG(dbgs() << F);
1051   }
1052
1053   return true;
1054 }