lib/Transforms/Instrumentation/MemorySanitizer.cpp

   1 //===-- MemorySanitizer.cpp - detector of uninitialized reads -------------===//
   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 /// \file
  10 /// This file is a part of MemorySanitizer, a detector of uninitialized
  11 /// reads.
  12 ///
  13 /// The algorithm of the tool is similar to Memcheck
  14 /// (http://goo.gl/QKbem). We associate a few shadow bits with every
  15 /// byte of the application memory, poison the shadow of the malloc-ed
  16 /// or alloca-ed memory, load the shadow bits on every memory read,
  17 /// propagate the shadow bits through some of the arithmetic
  18 /// instruction (including MOV), store the shadow bits on every memory
  19 /// write, report a bug on some other instructions (e.g. JMP) if the
  20 /// associated shadow is poisoned.
  21 ///
  22 /// But there are differences too. The first and the major one:
  23 /// compiler instrumentation instead of binary instrumentation. This
  24 /// gives us much better register allocation, possible compiler
  25 /// optimizations and a fast start-up. But this brings the major issue
  26 /// as well: msan needs to see all program events, including system
  27 /// calls and reads/writes in system libraries, so we either need to
  28 /// compile *everything* with msan or use a binary translation
  29 /// component (e.g. DynamoRIO) to instrument pre-built libraries.
  30 /// Another difference from Memcheck is that we use 8 shadow bits per
  31 /// byte of application memory and use a direct shadow mapping. This
  32 /// greatly simplifies the instrumentation code and avoids races on
  33 /// shadow updates (Memcheck is single-threaded so races are not a
  34 /// concern there. Memcheck uses 2 shadow bits per byte with a slow
  35 /// path storage that uses 8 bits per byte).
  36 ///
  37 /// The default value of shadow is 0, which means "clean" (not poisoned).
  38 ///
  39 /// Every module initializer should call __msan_init to ensure that the
  40 /// shadow memory is ready. On error, __msan_warning is called. Since
  41 /// parameters and return values may be passed via registers, we have a
  42 /// specialized thread-local shadow for return values
  43 /// (__msan_retval_tls) and parameters (__msan_param_tls).
  44 ///
  45 ///                           Origin tracking.
  46 ///
  47 /// MemorySanitizer can track origins (allocation points) of all uninitialized
  48 /// values. This behavior is controlled with a flag (msan-track-origins) and is
  49 /// disabled by default.
  50 ///
  51 /// Origins are 4-byte values created and interpreted by the runtime library.
  52 /// They are stored in a second shadow mapping, one 4-byte value for 4 bytes
  53 /// of application memory. Propagation of origins is basically a bunch of
  54 /// "select" instructions that pick the origin of a dirty argument, if an
  55 /// instruction has one.
  56 ///
  57 /// Every 4 aligned, consecutive bytes of application memory have one origin
  58 /// value associated with them. If these bytes contain uninitialized data
  59 /// coming from 2 different allocations, the last store wins. Because of this,
  60 /// MemorySanitizer reports can show unrelated origins, but this is unlikely in
  61 /// practice.
  62 ///
  63 /// Origins are meaningless for fully initialized values, so MemorySanitizer
  64 /// avoids storing origin to memory when a fully initialized value is stored.
  65 /// This way it avoids needless overwritting origin of the 4-byte region on
  66 /// a short (i.e. 1 byte) clean store, and it is also good for performance.
  67 ///
  68 ///                            Atomic handling.
  69 ///
  70 /// Ideally, every atomic store of application value should update the
  71 /// corresponding shadow location in an atomic way. Unfortunately, atomic store
  72 /// of two disjoint locations can not be done without severe slowdown.
  73 ///
  74 /// Therefore, we implement an approximation that may err on the safe side.
  75 /// In this implementation, every atomically accessed location in the program
  76 /// may only change from (partially) uninitialized to fully initialized, but
  77 /// not the other way around. We load the shadow _after_ the application load,
  78 /// and we store the shadow _before_ the app store. Also, we always store clean
  79 /// shadow (if the application store is atomic). This way, if the store-load
  80 /// pair constitutes a happens-before arc, shadow store and load are correctly
  81 /// ordered such that the load will get either the value that was stored, or
  82 /// some later value (which is always clean).
  83 ///
  84 /// This does not work very well with Compare-And-Swap (CAS) and
  85 /// Read-Modify-Write (RMW) operations. To follow the above logic, CAS and RMW
  86 /// must store the new shadow before the app operation, and load the shadow
  87 /// after the app operation. Computers don't work this way. Current
  88 /// implementation ignores the load aspect of CAS/RMW, always returning a clean
  89 /// value. It implements the store part as a simple atomic store by storing a
  90 /// clean shadow.
  91
  92 //===----------------------------------------------------------------------===//
  93
  94 #include "llvm/Transforms/Instrumentation.h"
  95 #include "llvm/ADT/DepthFirstIterator.h"
  96 #include "llvm/ADT/SmallString.h"
  97 #include "llvm/ADT/SmallVector.h"
  98 #include "llvm/ADT/StringExtras.h"
  99 #include "llvm/ADT/Triple.h"
 100 #include "llvm/IR/DataLayout.h"
 101 #include "llvm/IR/Function.h"
 102 #include "llvm/IR/IRBuilder.h"
 103 #include "llvm/IR/InlineAsm.h"
 104 #include "llvm/IR/InstVisitor.h"
 105 #include "llvm/IR/IntrinsicInst.h"
 106 #include "llvm/IR/LLVMContext.h"
 107 #include "llvm/IR/MDBuilder.h"
 108 #include "llvm/IR/Module.h"
 109 #include "llvm/IR/Type.h"
 110 #include "llvm/IR/ValueMap.h"
 111 #include "llvm/Support/CommandLine.h"
 112 #include "llvm/Support/Compiler.h"
 113 #include "llvm/Support/Debug.h"
 114 #include "llvm/Support/raw_ostream.h"
 115 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 116 #include "llvm/Transforms/Utils/Local.h"
 117 #include "llvm/Transforms/Utils/ModuleUtils.h"
 118
 119 using namespace llvm;
 120
 121 #define DEBUG_TYPE "msan"
 122
 123 static const unsigned kOriginSize = 4;
 124 static const unsigned kMinOriginAlignment = 4;
 125 static const unsigned kShadowTLSAlignment = 8;
 126
 127 // These constants must be kept in sync with the ones in msan.h.
 128 static const unsigned kParamTLSSize = 800;
 129 static const unsigned kRetvalTLSSize = 800;
 130
 131 // Accesses sizes are powers of two: 1, 2, 4, 8.
 132 static const size_t kNumberOfAccessSizes = 4;
 133
 134 /// \brief Track origins of uninitialized values.
 135 ///
 136 /// Adds a section to MemorySanitizer report that points to the allocation
 137 /// (stack or heap) the uninitialized bits came from originally.
 138 static cl::opt<int> ClTrackOrigins("msan-track-origins",
 139        cl::desc("Track origins (allocation sites) of poisoned memory"),
 140        cl::Hidden, cl::init(0));
 141 static cl::opt<bool> ClKeepGoing("msan-keep-going",
 142        cl::desc("keep going after reporting a UMR"),
 143        cl::Hidden, cl::init(false));
 144 static cl::opt<bool> ClPoisonStack("msan-poison-stack",
 145        cl::desc("poison uninitialized stack variables"),
 146        cl::Hidden, cl::init(true));
 147 static cl::opt<bool> ClPoisonStackWithCall("msan-poison-stack-with-call",
 148        cl::desc("poison uninitialized stack variables with a call"),
 149        cl::Hidden, cl::init(false));
 150 static cl::opt<int> ClPoisonStackPattern("msan-poison-stack-pattern",
 151        cl::desc("poison uninitialized stack variables with the given patter"),
 152        cl::Hidden, cl::init(0xff));
 153 static cl::opt<bool> ClPoisonUndef("msan-poison-undef",
 154        cl::desc("poison undef temps"),
 155        cl::Hidden, cl::init(true));
 156
 157 static cl::opt<bool> ClHandleICmp("msan-handle-icmp",
 158        cl::desc("propagate shadow through ICmpEQ and ICmpNE"),
 159        cl::Hidden, cl::init(true));
 160
 161 static cl::opt<bool> ClHandleICmpExact("msan-handle-icmp-exact",
 162        cl::desc("exact handling of relational integer ICmp"),
 163        cl::Hidden, cl::init(false));
 164
 165 // This flag controls whether we check the shadow of the address
 166 // operand of load or store. Such bugs are very rare, since load from
 167 // a garbage address typically results in SEGV, but still happen
 168 // (e.g. only lower bits of address are garbage, or the access happens
 169 // early at program startup where malloc-ed memory is more likely to
 170 // be zeroed. As of 2012-08-28 this flag adds 20% slowdown.
 171 static cl::opt<bool> ClCheckAccessAddress("msan-check-access-address",
 172        cl::desc("report accesses through a pointer which has poisoned shadow"),
 173        cl::Hidden, cl::init(true));
 174
 175 static cl::opt<bool> ClDumpStrictInstructions("msan-dump-strict-instructions",
 176        cl::desc("print out instructions with default strict semantics"),
 177        cl::Hidden, cl::init(false));
 178
 179 static cl::opt<int> ClInstrumentationWithCallThreshold(
 180     "msan-instrumentation-with-call-threshold",
 181     cl::desc(
 182         "If the function being instrumented requires more than "
 183         "this number of checks and origin stores, use callbacks instead of "
 184         "inline checks (-1 means never use callbacks)."),
 185     cl::Hidden, cl::init(3500));
 186
 187 // This is an experiment to enable handling of cases where shadow is a non-zero
 188 // compile-time constant. For some unexplainable reason they were silently
 189 // ignored in the instrumentation.
 190 static cl::opt<bool> ClCheckConstantShadow("msan-check-constant-shadow",
 191        cl::desc("Insert checks for constant shadow values"),
 192        cl::Hidden, cl::init(false));
 193
 194 static const char *const kMsanModuleCtorName = "msan.module_ctor";
 195 static const char *const kMsanInitName = "__msan_init";
 196
 197 namespace {
 198
 199 // Memory map parameters used in application-to-shadow address calculation.
 200 // Offset = (Addr & ~AndMask) ^ XorMask
 201 // Shadow = ShadowBase + Offset
 202 // Origin = OriginBase + Offset
 203 struct MemoryMapParams {
 204   uint64_t AndMask;
 205   uint64_t XorMask;
 206   uint64_t ShadowBase;
 207   uint64_t OriginBase;
 208 };
 209
 210 struct PlatformMemoryMapParams {
 211   const MemoryMapParams *bits32;
 212   const MemoryMapParams *bits64;
 213 };
 214
 215 // i386 Linux
 216 static const MemoryMapParams Linux_I386_MemoryMapParams = {
 217   0x000080000000,  // AndMask
 218   0,               // XorMask (not used)
 219   0,               // ShadowBase (not used)
 220   0x000040000000,  // OriginBase
 221 };
 222
 223 // x86_64 Linux
 224 static const MemoryMapParams Linux_X86_64_MemoryMapParams = {
 225   0x400000000000,  // AndMask
 226   0,               // XorMask (not used)
 227   0,               // ShadowBase (not used)
 228   0x200000000000,  // OriginBase
 229 };
 230
 231 // mips64 Linux
 232 static const MemoryMapParams Linux_MIPS64_MemoryMapParams = {
 233   0x004000000000,  // AndMask
 234   0,               // XorMask (not used)
 235   0,               // ShadowBase (not used)
 236   0x002000000000,  // OriginBase
 237 };
 238
 239 // i386 FreeBSD
 240 static const MemoryMapParams FreeBSD_I386_MemoryMapParams = {
 241   0x000180000000,  // AndMask
 242   0x000040000000,  // XorMask
 243   0x000020000000,  // ShadowBase
 244   0x000700000000,  // OriginBase
 245 };
 246
 247 // x86_64 FreeBSD
 248 static const MemoryMapParams FreeBSD_X86_64_MemoryMapParams = {
 249   0xc00000000000,  // AndMask
 250   0x200000000000,  // XorMask
 251   0x100000000000,  // ShadowBase
 252   0x380000000000,  // OriginBase
 253 };
 254
 255 static const PlatformMemoryMapParams Linux_X86_MemoryMapParams = {
 256   &Linux_I386_MemoryMapParams,
 257   &Linux_X86_64_MemoryMapParams,
 258 };
 259
 260 static const PlatformMemoryMapParams Linux_MIPS_MemoryMapParams = {
 261   NULL,
 262   &Linux_MIPS64_MemoryMapParams,
 263 };
 264
 265 static const PlatformMemoryMapParams FreeBSD_X86_MemoryMapParams = {
 266   &FreeBSD_I386_MemoryMapParams,
 267   &FreeBSD_X86_64_MemoryMapParams,
 268 };
 269
 270 /// \brief An instrumentation pass implementing detection of uninitialized
 271 /// reads.
 272 ///
 273 /// MemorySanitizer: instrument the code in module to find
 274 /// uninitialized reads.
 275 class MemorySanitizer : public FunctionPass {
 276  public:
 277   MemorySanitizer(int TrackOrigins = 0)
 278       : FunctionPass(ID),
 279         TrackOrigins(std::max(TrackOrigins, (int)ClTrackOrigins)),
 280         WarningFn(nullptr) {}
 281   const char *getPassName() const override { return "MemorySanitizer"; }
 282   bool runOnFunction(Function &F) override;
 283   bool doInitialization(Module &M) override;
 284   static char ID;  // Pass identification, replacement for typeid.
 285
 286  private:
 287   void initializeCallbacks(Module &M);
 288
 289   /// \brief Track origins (allocation points) of uninitialized values.
 290   int TrackOrigins;
 291
 292   LLVMContext *C;
 293   Type *IntptrTy;
 294   Type *OriginTy;
 295   /// \brief Thread-local shadow storage for function parameters.
 296   GlobalVariable *ParamTLS;
 297   /// \brief Thread-local origin storage for function parameters.
 298   GlobalVariable *ParamOriginTLS;
 299   /// \brief Thread-local shadow storage for function return value.
 300   GlobalVariable *RetvalTLS;
 301   /// \brief Thread-local origin storage for function return value.
 302   GlobalVariable *RetvalOriginTLS;
 303   /// \brief Thread-local shadow storage for in-register va_arg function
 304   /// parameters (x86_64-specific).
 305   GlobalVariable *VAArgTLS;
 306   /// \brief Thread-local shadow storage for va_arg overflow area
 307   /// (x86_64-specific).
 308   GlobalVariable *VAArgOverflowSizeTLS;
 309   /// \brief Thread-local space used to pass origin value to the UMR reporting
 310   /// function.
 311   GlobalVariable *OriginTLS;
 312
 313   /// \brief The run-time callback to print a warning.
 314   Value *WarningFn;
 315   // These arrays are indexed by log2(AccessSize).
 316   Value *MaybeWarningFn[kNumberOfAccessSizes];
 317   Value *MaybeStoreOriginFn[kNumberOfAccessSizes];
 318
 319   /// \brief Run-time helper that generates a new origin value for a stack
 320   /// allocation.
 321   Value *MsanSetAllocaOrigin4Fn;
 322   /// \brief Run-time helper that poisons stack on function entry.
 323   Value *MsanPoisonStackFn;
 324   /// \brief Run-time helper that records a store (or any event) of an
 325   /// uninitialized value and returns an updated origin id encoding this info.
 326   Value *MsanChainOriginFn;
 327   /// \brief MSan runtime replacements for memmove, memcpy and memset.
 328   Value *MemmoveFn, *MemcpyFn, *MemsetFn;
 329
 330   /// \brief Memory map parameters used in application-to-shadow calculation.
 331   const MemoryMapParams *MapParams;
 332
 333   MDNode *ColdCallWeights;
 334   /// \brief Branch weights for origin store.
 335   MDNode *OriginStoreWeights;
 336   /// \brief An empty volatile inline asm that prevents callback merge.
 337   InlineAsm *EmptyAsm;
 338   Function *MsanCtorFunction;
 339
 340   friend struct MemorySanitizerVisitor;
 341   friend struct VarArgAMD64Helper;
 342   friend struct VarArgMIPS64Helper;
 343 };
 344 }  // namespace
 345
 346 char MemorySanitizer::ID = 0;
 347 INITIALIZE_PASS(MemorySanitizer, "msan",
 348                 "MemorySanitizer: detects uninitialized reads.",
 349                 false, false)
 350
 351 FunctionPass *llvm::createMemorySanitizerPass(int TrackOrigins) {
 352   return new MemorySanitizer(TrackOrigins);
 353 }
 354
 355 /// \brief Create a non-const global initialized with the given string.
 356 ///
 357 /// Creates a writable global for Str so that we can pass it to the
 358 /// run-time lib. Runtime uses first 4 bytes of the string to store the
 359 /// frame ID, so the string needs to be mutable.
 360 static GlobalVariable *createPrivateNonConstGlobalForString(Module &M,
 361                                                             StringRef Str) {
 362   Constant *StrConst = ConstantDataArray::getString(M.getContext(), Str);
 363   return new GlobalVariable(M, StrConst->getType(), /*isConstant=*/false,
 364                             GlobalValue::PrivateLinkage, StrConst, "");
 365 }
 366
 367
 368 /// \brief Insert extern declaration of runtime-provided functions and globals.
 369 void MemorySanitizer::initializeCallbacks(Module &M) {
 370   // Only do this once.
 371   if (WarningFn)
 372     return;
 373
 374   IRBuilder<> IRB(*C);
 375   // Create the callback.
 376   // FIXME: this function should have "Cold" calling conv,
 377   // which is not yet implemented.
 378   StringRef WarningFnName = ClKeepGoing ? "__msan_warning"
 379                                         : "__msan_warning_noreturn";
 380   WarningFn = M.getOrInsertFunction(WarningFnName, IRB.getVoidTy(), nullptr);
 381
 382   for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
 383        AccessSizeIndex++) {
 384     unsigned AccessSize = 1 << AccessSizeIndex;
 385     std::string FunctionName = "__msan_maybe_warning_" + itostr(AccessSize);
 386     MaybeWarningFn[AccessSizeIndex] = M.getOrInsertFunction(
 387         FunctionName, IRB.getVoidTy(), IRB.getIntNTy(AccessSize * 8),
 388         IRB.getInt32Ty(), nullptr);
 389
 390     FunctionName = "__msan_maybe_store_origin_" + itostr(AccessSize);
 391     MaybeStoreOriginFn[AccessSizeIndex] = M.getOrInsertFunction(
 392         FunctionName, IRB.getVoidTy(), IRB.getIntNTy(AccessSize * 8),
 393         IRB.getInt8PtrTy(), IRB.getInt32Ty(), nullptr);
 394   }
 395
 396   MsanSetAllocaOrigin4Fn = M.getOrInsertFunction(
 397     "__msan_set_alloca_origin4", IRB.getVoidTy(), IRB.getInt8PtrTy(), IntptrTy,
 398     IRB.getInt8PtrTy(), IntptrTy, nullptr);
 399   MsanPoisonStackFn =
 400       M.getOrInsertFunction("__msan_poison_stack", IRB.getVoidTy(),
 401                             IRB.getInt8PtrTy(), IntptrTy, nullptr);
 402   MsanChainOriginFn = M.getOrInsertFunction(
 403     "__msan_chain_origin", IRB.getInt32Ty(), IRB.getInt32Ty(), nullptr);
 404   MemmoveFn = M.getOrInsertFunction(
 405     "__msan_memmove", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
 406     IRB.getInt8PtrTy(), IntptrTy, nullptr);
 407   MemcpyFn = M.getOrInsertFunction(
 408     "__msan_memcpy", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
 409     IntptrTy, nullptr);
 410   MemsetFn = M.getOrInsertFunction(
 411     "__msan_memset", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt32Ty(),
 412     IntptrTy, nullptr);
 413
 414   // Create globals.
 415   RetvalTLS = new GlobalVariable(
 416     M, ArrayType::get(IRB.getInt64Ty(), kRetvalTLSSize / 8), false,
 417     GlobalVariable::ExternalLinkage, nullptr, "__msan_retval_tls", nullptr,
 418     GlobalVariable::InitialExecTLSModel);
 419   RetvalOriginTLS = new GlobalVariable(
 420     M, OriginTy, false, GlobalVariable::ExternalLinkage, nullptr,
 421     "__msan_retval_origin_tls", nullptr, GlobalVariable::InitialExecTLSModel);
 422
 423   ParamTLS = new GlobalVariable(
 424     M, ArrayType::get(IRB.getInt64Ty(), kParamTLSSize / 8), false,
 425     GlobalVariable::ExternalLinkage, nullptr, "__msan_param_tls", nullptr,
 426     GlobalVariable::InitialExecTLSModel);
 427   ParamOriginTLS = new GlobalVariable(
 428     M, ArrayType::get(OriginTy, kParamTLSSize / 4), false,
 429     GlobalVariable::ExternalLinkage, nullptr, "__msan_param_origin_tls",
 430     nullptr, GlobalVariable::InitialExecTLSModel);
 431
 432   VAArgTLS = new GlobalVariable(
 433     M, ArrayType::get(IRB.getInt64Ty(), kParamTLSSize / 8), false,
 434     GlobalVariable::ExternalLinkage, nullptr, "__msan_va_arg_tls", nullptr,
 435     GlobalVariable::InitialExecTLSModel);
 436   VAArgOverflowSizeTLS = new GlobalVariable(
 437     M, IRB.getInt64Ty(), false, GlobalVariable::ExternalLinkage, nullptr,
 438     "__msan_va_arg_overflow_size_tls", nullptr,
 439     GlobalVariable::InitialExecTLSModel);
 440   OriginTLS = new GlobalVariable(
 441     M, IRB.getInt32Ty(), false, GlobalVariable::ExternalLinkage, nullptr,
 442     "__msan_origin_tls", nullptr, GlobalVariable::InitialExecTLSModel);
 443
 444   // We insert an empty inline asm after __msan_report* to avoid callback merge.
 445   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
 446                             StringRef(""), StringRef(""),
 447                             /*hasSideEffects=*/true);
 448 }
 449
 450 /// \brief Module-level initialization.
 451 ///
 452 /// inserts a call to __msan_init to the module's constructor list.
 453 bool MemorySanitizer::doInitialization(Module &M) {
 454   auto &DL = M.getDataLayout();
 455
 456   Triple TargetTriple(M.getTargetTriple());
 457   switch (TargetTriple.getOS()) {
 458     case Triple::FreeBSD:
 459       switch (TargetTriple.getArch()) {
 460         case Triple::x86_64:
 461           MapParams = FreeBSD_X86_MemoryMapParams.bits64;
 462           break;
 463         case Triple::x86:
 464           MapParams = FreeBSD_X86_MemoryMapParams.bits32;
 465           break;
 466         default:
 467           report_fatal_error("unsupported architecture");
 468       }
 469       break;
 470     case Triple::Linux:
 471       switch (TargetTriple.getArch()) {
 472         case Triple::x86_64:
 473           MapParams = Linux_X86_MemoryMapParams.bits64;
 474           break;
 475         case Triple::x86:
 476           MapParams = Linux_X86_MemoryMapParams.bits32;
 477           break;
 478         case Triple::mips64:
 479         case Triple::mips64el:
 480           MapParams = Linux_MIPS_MemoryMapParams.bits64;
 481           break;
 482         default:
 483           report_fatal_error("unsupported architecture");
 484       }
 485       break;
 486     default:
 487       report_fatal_error("unsupported operating system");
 488   }
 489
 490   C = &(M.getContext());
 491   IRBuilder<> IRB(*C);
 492   IntptrTy = IRB.getIntPtrTy(DL);
 493   OriginTy = IRB.getInt32Ty();
 494
 495   ColdCallWeights = MDBuilder(*C).createBranchWeights(1, 1000);
 496   OriginStoreWeights = MDBuilder(*C).createBranchWeights(1, 1000);
 497
 498   std::tie(MsanCtorFunction, std::ignore) =
 499       createSanitizerCtorAndInitFunctions(M, kMsanModuleCtorName, kMsanInitName,
 500                                           /*InitArgTypes=*/{},
 501                                           /*InitArgs=*/{});
 502
 503   appendToGlobalCtors(M, MsanCtorFunction, 0);
 504
 505   if (TrackOrigins)
 506     new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage,
 507                        IRB.getInt32(TrackOrigins), "__msan_track_origins");
 508
 509   if (ClKeepGoing)
 510     new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage,
 511                        IRB.getInt32(ClKeepGoing), "__msan_keep_going");
 512
 513   return true;
 514 }
 515
 516 namespace {
 517
 518 /// \brief A helper class that handles instrumentation of VarArg
 519 /// functions on a particular platform.
 520 ///
 521 /// Implementations are expected to insert the instrumentation
 522 /// necessary to propagate argument shadow through VarArg function
 523 /// calls. Visit* methods are called during an InstVisitor pass over
 524 /// the function, and should avoid creating new basic blocks. A new
 525 /// instance of this class is created for each instrumented function.
 526 struct VarArgHelper {
 527   /// \brief Visit a CallSite.
 528   virtual void visitCallSite(CallSite &CS, IRBuilder<> &IRB) = 0;
 529
 530   /// \brief Visit a va_start call.
 531   virtual void visitVAStartInst(VAStartInst &I) = 0;
 532
 533   /// \brief Visit a va_copy call.
 534   virtual void visitVACopyInst(VACopyInst &I) = 0;
 535
 536   /// \brief Finalize function instrumentation.
 537   ///
 538   /// This method is called after visiting all interesting (see above)
 539   /// instructions in a function.
 540   virtual void finalizeInstrumentation() = 0;
 541
 542   virtual ~VarArgHelper() {}
 543 };
 544
 545 struct MemorySanitizerVisitor;
 546
 547 VarArgHelper*
 548 CreateVarArgHelper(Function &Func, MemorySanitizer &Msan,
 549                    MemorySanitizerVisitor &Visitor);
 550
 551 unsigned TypeSizeToSizeIndex(unsigned TypeSize) {
 552   if (TypeSize <= 8) return 0;
 553   return Log2_32_Ceil(TypeSize / 8);
 554 }
 555
 556 /// This class does all the work for a given function. Store and Load
 557 /// instructions store and load corresponding shadow and origin
 558 /// values. Most instructions propagate shadow from arguments to their
 559 /// return values. Certain instructions (most importantly, BranchInst)
 560 /// test their argument shadow and print reports (with a runtime call) if it's
 561 /// non-zero.
 562 struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> {
 563   Function &F;
 564   MemorySanitizer &MS;
 565   SmallVector<PHINode *, 16> ShadowPHINodes, OriginPHINodes;
 566   ValueMap<Value*, Value*> ShadowMap, OriginMap;
 567   std::unique_ptr<VarArgHelper> VAHelper;
 568
 569   // The following flags disable parts of MSan instrumentation based on
 570   // blacklist contents and command-line options.
 571   bool InsertChecks;
 572   bool PropagateShadow;
 573   bool PoisonStack;
 574   bool PoisonUndef;
 575   bool CheckReturnValue;
 576
 577   struct ShadowOriginAndInsertPoint {
 578     Value *Shadow;
 579     Value *Origin;
 580     Instruction *OrigIns;
 581     ShadowOriginAndInsertPoint(Value *S, Value *O, Instruction *I)
 582       : Shadow(S), Origin(O), OrigIns(I) { }
 583   };
 584   SmallVector<ShadowOriginAndInsertPoint, 16> InstrumentationList;
 585   SmallVector<Instruction*, 16> StoreList;
 586
 587   MemorySanitizerVisitor(Function &F, MemorySanitizer &MS)
 588       : F(F), MS(MS), VAHelper(CreateVarArgHelper(F, MS, *this)) {
 589     bool SanitizeFunction = F.hasFnAttribute(Attribute::SanitizeMemory);
 590     InsertChecks = SanitizeFunction;
 591     PropagateShadow = SanitizeFunction;
 592     PoisonStack = SanitizeFunction && ClPoisonStack;
 593     PoisonUndef = SanitizeFunction && ClPoisonUndef;
 594     // FIXME: Consider using SpecialCaseList to specify a list of functions that
 595     // must always return fully initialized values. For now, we hardcode "main".
 596     CheckReturnValue = SanitizeFunction && (F.getName() == "main");
 597
 598     DEBUG(if (!InsertChecks)
 599           dbgs() << "MemorySanitizer is not inserting checks into '"
 600                  << F.getName() << "'\n");
 601   }
 602
 603   Value *updateOrigin(Value *V, IRBuilder<> &IRB) {
 604     if (MS.TrackOrigins <= 1) return V;
 605     return IRB.CreateCall(MS.MsanChainOriginFn, V);
 606   }
 607
 608   Value *originToIntptr(IRBuilder<> &IRB, Value *Origin) {
 609     const DataLayout &DL = F.getParent()->getDataLayout();
 610     unsigned IntptrSize = DL.getTypeStoreSize(MS.IntptrTy);
 611     if (IntptrSize == kOriginSize) return Origin;
 612     assert(IntptrSize == kOriginSize * 2);
 613     Origin = IRB.CreateIntCast(Origin, MS.IntptrTy, /* isSigned */ false);
 614     return IRB.CreateOr(Origin, IRB.CreateShl(Origin, kOriginSize * 8));
 615   }
 616
 617   /// \brief Fill memory range with the given origin value.
 618   void paintOrigin(IRBuilder<> &IRB, Value *Origin, Value *OriginPtr,
 619                    unsigned Size, unsigned Alignment) {
 620     const DataLayout &DL = F.getParent()->getDataLayout();
 621     unsigned IntptrAlignment = DL.getABITypeAlignment(MS.IntptrTy);
 622     unsigned IntptrSize = DL.getTypeStoreSize(MS.IntptrTy);
 623     assert(IntptrAlignment >= kMinOriginAlignment);
 624     assert(IntptrSize >= kOriginSize);
 625
 626     unsigned Ofs = 0;
 627     unsigned CurrentAlignment = Alignment;
 628     if (Alignment >= IntptrAlignment && IntptrSize > kOriginSize) {
 629       Value *IntptrOrigin = originToIntptr(IRB, Origin);
 630       Value *IntptrOriginPtr =
 631           IRB.CreatePointerCast(OriginPtr, PointerType::get(MS.IntptrTy, 0));
 632       for (unsigned i = 0; i < Size / IntptrSize; ++i) {
 633         Value *Ptr = i ? IRB.CreateConstGEP1_32(MS.IntptrTy, IntptrOriginPtr, i)
 634                        : IntptrOriginPtr;
 635         IRB.CreateAlignedStore(IntptrOrigin, Ptr, CurrentAlignment);
 636         Ofs += IntptrSize / kOriginSize;
 637         CurrentAlignment = IntptrAlignment;
 638       }
 639     }
 640
 641     for (unsigned i = Ofs; i < (Size + kOriginSize - 1) / kOriginSize; ++i) {
 642       Value *GEP =
 643           i ? IRB.CreateConstGEP1_32(nullptr, OriginPtr, i) : OriginPtr;
 644       IRB.CreateAlignedStore(Origin, GEP, CurrentAlignment);
 645       CurrentAlignment = kMinOriginAlignment;
 646     }
 647   }
 648
 649   void storeOrigin(IRBuilder<> &IRB, Value *Addr, Value *Shadow, Value *Origin,
 650                    unsigned Alignment, bool AsCall) {
 651     const DataLayout &DL = F.getParent()->getDataLayout();
 652     unsigned OriginAlignment = std::max(kMinOriginAlignment, Alignment);
 653     unsigned StoreSize = DL.getTypeStoreSize(Shadow->getType());
 654     if (isa<StructType>(Shadow->getType())) {
 655       paintOrigin(IRB, updateOrigin(Origin, IRB),
 656                   getOriginPtr(Addr, IRB, Alignment), StoreSize,
 657                   OriginAlignment);
 658     } else {
 659       Value *ConvertedShadow = convertToShadowTyNoVec(Shadow, IRB);
 660       Constant *ConstantShadow = dyn_cast_or_null<Constant>(ConvertedShadow);
 661       if (ConstantShadow) {
 662         if (ClCheckConstantShadow && !ConstantShadow->isZeroValue())
 663           paintOrigin(IRB, updateOrigin(Origin, IRB),
 664                       getOriginPtr(Addr, IRB, Alignment), StoreSize,
 665                       OriginAlignment);
 666         return;
 667       }
 668
 669       unsigned TypeSizeInBits =
 670           DL.getTypeSizeInBits(ConvertedShadow->getType());
 671       unsigned SizeIndex = TypeSizeToSizeIndex(TypeSizeInBits);
 672       if (AsCall && SizeIndex < kNumberOfAccessSizes) {
 673         Value *Fn = MS.MaybeStoreOriginFn[SizeIndex];
 674         Value *ConvertedShadow2 = IRB.CreateZExt(
 675             ConvertedShadow, IRB.getIntNTy(8 * (1 << SizeIndex)));
 676         IRB.CreateCall(Fn, {ConvertedShadow2,
 677                             IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
 678                             Origin});
 679       } else {
 680         Value *Cmp = IRB.CreateICmpNE(
 681             ConvertedShadow, getCleanShadow(ConvertedShadow), "_mscmp");
 682         Instruction *CheckTerm = SplitBlockAndInsertIfThen(
 683             Cmp, IRB.GetInsertPoint(), false, MS.OriginStoreWeights);
 684         IRBuilder<> IRBNew(CheckTerm);
 685         paintOrigin(IRBNew, updateOrigin(Origin, IRBNew),
 686                     getOriginPtr(Addr, IRBNew, Alignment), StoreSize,
 687                     OriginAlignment);
 688       }
 689     }
 690   }
 691
 692   void materializeStores(bool InstrumentWithCalls) {
 693     for (auto Inst : StoreList) {
 694       StoreInst &SI = *dyn_cast<StoreInst>(Inst);
 695
 696       IRBuilder<> IRB(&SI);
 697       Value *Val = SI.getValueOperand();
 698       Value *Addr = SI.getPointerOperand();
 699       Value *Shadow = SI.isAtomic() ? getCleanShadow(Val) : getShadow(Val);
 700       Value *ShadowPtr = getShadowPtr(Addr, Shadow->getType(), IRB);
 701
 702       StoreInst *NewSI =
 703           IRB.CreateAlignedStore(Shadow, ShadowPtr, SI.getAlignment());
 704       DEBUG(dbgs() << "  STORE: " << *NewSI << "\n");
 705       (void)NewSI;
 706
 707       if (ClCheckAccessAddress) insertShadowCheck(Addr, &SI);
 708
 709       if (SI.isAtomic()) SI.setOrdering(addReleaseOrdering(SI.getOrdering()));
 710
 711       if (MS.TrackOrigins && !SI.isAtomic())
 712         storeOrigin(IRB, Addr, Shadow, getOrigin(Val), SI.getAlignment(),
 713                     InstrumentWithCalls);
 714     }
 715   }
 716
 717   void materializeOneCheck(Instruction *OrigIns, Value *Shadow, Value *Origin,
 718                            bool AsCall) {
 719     IRBuilder<> IRB(OrigIns);
 720     DEBUG(dbgs() << "  SHAD0 : " << *Shadow << "\n");
 721     Value *ConvertedShadow = convertToShadowTyNoVec(Shadow, IRB);
 722     DEBUG(dbgs() << "  SHAD1 : " << *ConvertedShadow << "\n");
 723
 724     Constant *ConstantShadow = dyn_cast_or_null<Constant>(ConvertedShadow);
 725     if (ConstantShadow) {
 726       if (ClCheckConstantShadow && !ConstantShadow->isZeroValue()) {
 727         if (MS.TrackOrigins) {
 728           IRB.CreateStore(Origin ? (Value *)Origin : (Value *)IRB.getInt32(0),
 729                           MS.OriginTLS);
 730         }
 731         IRB.CreateCall(MS.WarningFn, {});
 732         IRB.CreateCall(MS.EmptyAsm, {});
 733         // FIXME: Insert UnreachableInst if !ClKeepGoing?
 734         // This may invalidate some of the following checks and needs to be done
 735         // at the very end.
 736       }
 737       return;
 738     }
 739
 740     const DataLayout &DL = OrigIns->getModule()->getDataLayout();
 741
 742     unsigned TypeSizeInBits = DL.getTypeSizeInBits(ConvertedShadow->getType());
 743     unsigned SizeIndex = TypeSizeToSizeIndex(TypeSizeInBits);
 744     if (AsCall && SizeIndex < kNumberOfAccessSizes) {
 745       Value *Fn = MS.MaybeWarningFn[SizeIndex];
 746       Value *ConvertedShadow2 =
 747           IRB.CreateZExt(ConvertedShadow, IRB.getIntNTy(8 * (1 << SizeIndex)));
 748       IRB.CreateCall(Fn, {ConvertedShadow2, MS.TrackOrigins && Origin
 749                                                 ? Origin
 750                                                 : (Value *)IRB.getInt32(0)});
 751     } else {
 752       Value *Cmp = IRB.CreateICmpNE(ConvertedShadow,
 753                                     getCleanShadow(ConvertedShadow), "_mscmp");
 754       Instruction *CheckTerm = SplitBlockAndInsertIfThen(
 755           Cmp, OrigIns,
 756           /* Unreachable */ !ClKeepGoing, MS.ColdCallWeights);
 757
 758       IRB.SetInsertPoint(CheckTerm);
 759       if (MS.TrackOrigins) {
 760         IRB.CreateStore(Origin ? (Value *)Origin : (Value *)IRB.getInt32(0),
 761                         MS.OriginTLS);
 762       }
 763       IRB.CreateCall(MS.WarningFn, {});
 764       IRB.CreateCall(MS.EmptyAsm, {});
 765       DEBUG(dbgs() << "  CHECK: " << *Cmp << "\n");
 766     }
 767   }
 768
 769   void materializeChecks(bool InstrumentWithCalls) {
 770     for (const auto &ShadowData : InstrumentationList) {
 771       Instruction *OrigIns = ShadowData.OrigIns;
 772       Value *Shadow = ShadowData.Shadow;
 773       Value *Origin = ShadowData.Origin;
 774       materializeOneCheck(OrigIns, Shadow, Origin, InstrumentWithCalls);
 775     }
 776     DEBUG(dbgs() << "DONE:\n" << F);
 777   }
 778
 779   /// \brief Add MemorySanitizer instrumentation to a function.
 780   bool runOnFunction() {
 781     MS.initializeCallbacks(*F.getParent());
 782
 783     // In the presence of unreachable blocks, we may see Phi nodes with
 784     // incoming nodes from such blocks. Since InstVisitor skips unreachable
 785     // blocks, such nodes will not have any shadow value associated with them.
 786     // It's easier to remove unreachable blocks than deal with missing shadow.
 787     removeUnreachableBlocks(F);
 788
 789     // Iterate all BBs in depth-first order and create shadow instructions
 790     // for all instructions (where applicable).
 791     // For PHI nodes we create dummy shadow PHIs which will be finalized later.
 792     for (BasicBlock *BB : depth_first(&F.getEntryBlock()))
 793       visit(*BB);
 794
 795
 796     // Finalize PHI nodes.
 797     for (PHINode *PN : ShadowPHINodes) {
 798       PHINode *PNS = cast<PHINode>(getShadow(PN));
 799       PHINode *PNO = MS.TrackOrigins ? cast<PHINode>(getOrigin(PN)) : nullptr;
 800       size_t NumValues = PN->getNumIncomingValues();
 801       for (size_t v = 0; v < NumValues; v++) {
 802         PNS->addIncoming(getShadow(PN, v), PN->getIncomingBlock(v));
 803         if (PNO) PNO->addIncoming(getOrigin(PN, v), PN->getIncomingBlock(v));
 804       }
 805     }
 806
 807     VAHelper->finalizeInstrumentation();
 808
 809     bool InstrumentWithCalls = ClInstrumentationWithCallThreshold >= 0 &&
 810                                InstrumentationList.size() + StoreList.size() >
 811                                    (unsigned)ClInstrumentationWithCallThreshold;
 812
 813     // Delayed instrumentation of StoreInst.
 814     // This may add new checks to be inserted later.
 815     materializeStores(InstrumentWithCalls);
 816
 817     // Insert shadow value checks.
 818     materializeChecks(InstrumentWithCalls);
 819
 820     return true;
 821   }
 822
 823   /// \brief Compute the shadow type that corresponds to a given Value.
 824   Type *getShadowTy(Value *V) {
 825     return getShadowTy(V->getType());
 826   }
 827
 828   /// \brief Compute the shadow type that corresponds to a given Type.
 829   Type *getShadowTy(Type *OrigTy) {
 830     if (!OrigTy->isSized()) {
 831       return nullptr;
 832     }
 833     // For integer type, shadow is the same as the original type.
 834     // This may return weird-sized types like i1.
 835     if (IntegerType *IT = dyn_cast<IntegerType>(OrigTy))
 836       return IT;
 837     const DataLayout &DL = F.getParent()->getDataLayout();
 838     if (VectorType *VT = dyn_cast<VectorType>(OrigTy)) {
 839       uint32_t EltSize = DL.getTypeSizeInBits(VT->getElementType());
 840       return VectorType::get(IntegerType::get(*MS.C, EltSize),
 841                              VT->getNumElements());
 842     }
 843     if (ArrayType *AT = dyn_cast<ArrayType>(OrigTy)) {
 844       return ArrayType::get(getShadowTy(AT->getElementType()),
 845                             AT->getNumElements());
 846     }
 847     if (StructType *ST = dyn_cast<StructType>(OrigTy)) {
 848       SmallVector<Type*, 4> Elements;
 849       for (unsigned i = 0, n = ST->getNumElements(); i < n; i++)
 850         Elements.push_back(getShadowTy(ST->getElementType(i)));
 851       StructType *Res = StructType::get(*MS.C, Elements, ST->isPacked());
 852       DEBUG(dbgs() << "getShadowTy: " << *ST << " ===> " << *Res << "\n");
 853       return Res;
 854     }
 855     uint32_t TypeSize = DL.getTypeSizeInBits(OrigTy);
 856     return IntegerType::get(*MS.C, TypeSize);
 857   }
 858
 859   /// \brief Flatten a vector type.
 860   Type *getShadowTyNoVec(Type *ty) {
 861     if (VectorType *vt = dyn_cast<VectorType>(ty))
 862       return IntegerType::get(*MS.C, vt->getBitWidth());
 863     return ty;
 864   }
 865
 866   /// \brief Convert a shadow value to it's flattened variant.
 867   Value *convertToShadowTyNoVec(Value *V, IRBuilder<> &IRB) {
 868     Type *Ty = V->getType();
 869     Type *NoVecTy = getShadowTyNoVec(Ty);
 870     if (Ty == NoVecTy) return V;
 871     return IRB.CreateBitCast(V, NoVecTy);
 872   }
 873
 874   /// \brief Compute the integer shadow offset that corresponds to a given
 875   /// application address.
 876   ///
 877   /// Offset = (Addr & ~AndMask) ^ XorMask
 878   Value *getShadowPtrOffset(Value *Addr, IRBuilder<> &IRB) {
 879     uint64_t AndMask = MS.MapParams->AndMask;
 880     assert(AndMask != 0 && "AndMask shall be specified");
 881     Value *OffsetLong =
 882       IRB.CreateAnd(IRB.CreatePointerCast(Addr, MS.IntptrTy),
 883                     ConstantInt::get(MS.IntptrTy, ~AndMask));
 884
 885     uint64_t XorMask = MS.MapParams->XorMask;
 886     if (XorMask != 0)
 887       OffsetLong = IRB.CreateXor(OffsetLong,
 888                                  ConstantInt::get(MS.IntptrTy, XorMask));
 889     return OffsetLong;
 890   }
 891
 892   /// \brief Compute the shadow address that corresponds to a given application
 893   /// address.
 894   ///
 895   /// Shadow = ShadowBase + Offset
 896   Value *getShadowPtr(Value *Addr, Type *ShadowTy,
 897                       IRBuilder<> &IRB) {
 898     Value *ShadowLong = getShadowPtrOffset(Addr, IRB);
 899     uint64_t ShadowBase = MS.MapParams->ShadowBase;
 900     if (ShadowBase != 0)
 901       ShadowLong =
 902         IRB.CreateAdd(ShadowLong,
 903                       ConstantInt::get(MS.IntptrTy, ShadowBase));
 904     return IRB.CreateIntToPtr(ShadowLong, PointerType::get(ShadowTy, 0));
 905   }
 906
 907   /// \brief Compute the origin address that corresponds to a given application
 908   /// address.
 909   ///
 910   /// OriginAddr = (OriginBase + Offset) & ~3ULL
 911   Value *getOriginPtr(Value *Addr, IRBuilder<> &IRB, unsigned Alignment) {
 912     Value *OriginLong = getShadowPtrOffset(Addr, IRB);
 913     uint64_t OriginBase = MS.MapParams->OriginBase;
 914     if (OriginBase != 0)
 915       OriginLong =
 916         IRB.CreateAdd(OriginLong,
 917                       ConstantInt::get(MS.IntptrTy, OriginBase));
 918     if (Alignment < kMinOriginAlignment) {
 919       uint64_t Mask = kMinOriginAlignment - 1;
 920       OriginLong = IRB.CreateAnd(OriginLong,
 921                                  ConstantInt::get(MS.IntptrTy, ~Mask));
 922     }
 923     return IRB.CreateIntToPtr(OriginLong,
 924                               PointerType::get(IRB.getInt32Ty(), 0));
 925   }
 926
 927   /// \brief Compute the shadow address for a given function argument.
 928   ///
 929   /// Shadow = ParamTLS+ArgOffset.
 930   Value *getShadowPtrForArgument(Value *A, IRBuilder<> &IRB,
 931                                  int ArgOffset) {
 932     Value *Base = IRB.CreatePointerCast(MS.ParamTLS, MS.IntptrTy);
 933     Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset));
 934     return IRB.CreateIntToPtr(Base, PointerType::get(getShadowTy(A), 0),
 935                               "_msarg");
 936   }
 937
 938   /// \brief Compute the origin address for a given function argument.
 939   Value *getOriginPtrForArgument(Value *A, IRBuilder<> &IRB,
 940                                  int ArgOffset) {
 941     if (!MS.TrackOrigins) return nullptr;
 942     Value *Base = IRB.CreatePointerCast(MS.ParamOriginTLS, MS.IntptrTy);
 943     Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset));
 944     return IRB.CreateIntToPtr(Base, PointerType::get(MS.OriginTy, 0),
 945                               "_msarg_o");
 946   }
 947
 948   /// \brief Compute the shadow address for a retval.
 949   Value *getShadowPtrForRetval(Value *A, IRBuilder<> &IRB) {
 950     Value *Base = IRB.CreatePointerCast(MS.RetvalTLS, MS.IntptrTy);
 951     return IRB.CreateIntToPtr(Base, PointerType::get(getShadowTy(A), 0),
 952                               "_msret");
 953   }
 954
 955   /// \brief Compute the origin address for a retval.
 956   Value *getOriginPtrForRetval(IRBuilder<> &IRB) {
 957     // We keep a single origin for the entire retval. Might be too optimistic.
 958     return MS.RetvalOriginTLS;
 959   }
 960
 961   /// \brief Set SV to be the shadow value for V.
 962   void setShadow(Value *V, Value *SV) {
 963     assert(!ShadowMap.count(V) && "Values may only have one shadow");
 964     ShadowMap[V] = PropagateShadow ? SV : getCleanShadow(V);
 965   }
 966
 967   /// \brief Set Origin to be the origin value for V.
 968   void setOrigin(Value *V, Value *Origin) {
 969     if (!MS.TrackOrigins) return;
 970     assert(!OriginMap.count(V) && "Values may only have one origin");
 971     DEBUG(dbgs() << "ORIGIN: " << *V << "  ==> " << *Origin << "\n");
 972     OriginMap[V] = Origin;
 973   }
 974
 975   /// \brief Create a clean shadow value for a given value.
 976   ///
 977   /// Clean shadow (all zeroes) means all bits of the value are defined
 978   /// (initialized).
 979   Constant *getCleanShadow(Value *V) {
 980     Type *ShadowTy = getShadowTy(V);
 981     if (!ShadowTy)
 982       return nullptr;
 983     return Constant::getNullValue(ShadowTy);
 984   }
 985
 986   /// \brief Create a dirty shadow of a given shadow type.
 987   Constant *getPoisonedShadow(Type *ShadowTy) {
 988     assert(ShadowTy);
 989     if (isa<IntegerType>(ShadowTy) || isa<VectorType>(ShadowTy))
 990       return Constant::getAllOnesValue(ShadowTy);
 991     if (ArrayType *AT = dyn_cast<ArrayType>(ShadowTy)) {
 992       SmallVector<Constant *, 4> Vals(AT->getNumElements(),
 993                                       getPoisonedShadow(AT->getElementType()));
 994       return ConstantArray::get(AT, Vals);
 995     }
 996     if (StructType *ST = dyn_cast<StructType>(ShadowTy)) {
 997       SmallVector<Constant *, 4> Vals;
 998       for (unsigned i = 0, n = ST->getNumElements(); i < n; i++)
 999         Vals.push_back(getPoisonedShadow(ST->getElementType(i)));
1000       return ConstantStruct::get(ST, Vals);
1001     }
1002     llvm_unreachable("Unexpected shadow type");
1003   }
1004
1005   /// \brief Create a dirty shadow for a given value.
1006   Constant *getPoisonedShadow(Value *V) {
1007     Type *ShadowTy = getShadowTy(V);
1008     if (!ShadowTy)
1009       return nullptr;
1010     return getPoisonedShadow(ShadowTy);
1011   }
1012
1013   /// \brief Create a clean (zero) origin.
1014   Value *getCleanOrigin() {
1015     return Constant::getNullValue(MS.OriginTy);
1016   }
1017
1018   /// \brief Get the shadow value for a given Value.
1019   ///
1020   /// This function either returns the value set earlier with setShadow,
1021   /// or extracts if from ParamTLS (for function arguments).
1022   Value *getShadow(Value *V) {
1023     if (!PropagateShadow) return getCleanShadow(V);
1024     if (Instruction *I = dyn_cast<Instruction>(V)) {
1025       // For instructions the shadow is already stored in the map.
1026       Value *Shadow = ShadowMap[V];
1027       if (!Shadow) {
1028         DEBUG(dbgs() << "No shadow: " << *V << "\n" << *(I->getParent()));
1029         (void)I;
1030         assert(Shadow && "No shadow for a value");
1031       }
1032       return Shadow;
1033     }
1034     if (UndefValue *U = dyn_cast<UndefValue>(V)) {
1035       Value *AllOnes = PoisonUndef ? getPoisonedShadow(V) : getCleanShadow(V);
1036       DEBUG(dbgs() << "Undef: " << *U << " ==> " << *AllOnes << "\n");
1037       (void)U;
1038       return AllOnes;
1039     }
1040     if (Argument *A = dyn_cast<Argument>(V)) {
1041       // For arguments we compute the shadow on demand and store it in the map.
1042       Value **ShadowPtr = &ShadowMap[V];
1043       if (*ShadowPtr)
1044         return *ShadowPtr;
1045       Function *F = A->getParent();
1046       IRBuilder<> EntryIRB(F->getEntryBlock().getFirstNonPHI());
1047       unsigned ArgOffset = 0;
1048       const DataLayout &DL = F->getParent()->getDataLayout();
1049       for (auto &FArg : F->args()) {
1050         if (!FArg.getType()->isSized()) {
1051           DEBUG(dbgs() << "Arg is not sized\n");
1052           continue;
1053         }
1054         unsigned Size =
1055             FArg.hasByValAttr()
1056                 ? DL.getTypeAllocSize(FArg.getType()->getPointerElementType())
1057                 : DL.getTypeAllocSize(FArg.getType());
1058         if (A == &FArg) {
1059           bool Overflow = ArgOffset + Size > kParamTLSSize;
1060           Value *Base = getShadowPtrForArgument(&FArg, EntryIRB, ArgOffset);
1061           if (FArg.hasByValAttr()) {
1062             // ByVal pointer itself has clean shadow. We copy the actual
1063             // argument shadow to the underlying memory.
1064             // Figure out maximal valid memcpy alignment.
1065             unsigned ArgAlign = FArg.getParamAlignment();
1066             if (ArgAlign == 0) {
1067               Type *EltType = A->getType()->getPointerElementType();
1068               ArgAlign = DL.getABITypeAlignment(EltType);
1069             }
1070             if (Overflow) {
1071               // ParamTLS overflow.
1072               EntryIRB.CreateMemSet(
1073                   getShadowPtr(V, EntryIRB.getInt8Ty(), EntryIRB),
1074                   Constant::getNullValue(EntryIRB.getInt8Ty()), Size, ArgAlign);
1075             } else {
1076               unsigned CopyAlign = std::min(ArgAlign, kShadowTLSAlignment);
1077               Value *Cpy = EntryIRB.CreateMemCpy(
1078                   getShadowPtr(V, EntryIRB.getInt8Ty(), EntryIRB), Base, Size,
1079                   CopyAlign);
1080               DEBUG(dbgs() << "  ByValCpy: " << *Cpy << "\n");
1081               (void)Cpy;
1082             }
1083             *ShadowPtr = getCleanShadow(V);
1084           } else {
1085             if (Overflow) {
1086               // ParamTLS overflow.
1087               *ShadowPtr = getCleanShadow(V);
1088             } else {
1089               *ShadowPtr =
1090                   EntryIRB.CreateAlignedLoad(Base, kShadowTLSAlignment);
1091             }
1092           }
1093           DEBUG(dbgs() << "  ARG:    "  << FArg << " ==> " <<
1094                 **ShadowPtr << "\n");
1095           if (MS.TrackOrigins && !Overflow) {
1096             Value *OriginPtr =
1097                 getOriginPtrForArgument(&FArg, EntryIRB, ArgOffset);
1098             setOrigin(A, EntryIRB.CreateLoad(OriginPtr));
1099           } else {
1100             setOrigin(A, getCleanOrigin());
1101           }
1102         }
1103         ArgOffset += RoundUpToAlignment(Size, kShadowTLSAlignment);
1104       }
1105       assert(*ShadowPtr && "Could not find shadow for an argument");
1106       return *ShadowPtr;
1107     }
1108     // For everything else the shadow is zero.
1109     return getCleanShadow(V);
1110   }
1111
1112   /// \brief Get the shadow for i-th argument of the instruction I.
1113   Value *getShadow(Instruction *I, int i) {
1114     return getShadow(I->getOperand(i));
1115   }
1116
1117   /// \brief Get the origin for a value.
1118   Value *getOrigin(Value *V) {
1119     if (!MS.TrackOrigins) return nullptr;
1120     if (!PropagateShadow) return getCleanOrigin();
1121     if (isa<Constant>(V)) return getCleanOrigin();
1122     assert((isa<Instruction>(V) || isa<Argument>(V)) &&
1123            "Unexpected value type in getOrigin()");
1124     Value *Origin = OriginMap[V];
1125     assert(Origin && "Missing origin");
1126     return Origin;
1127   }
1128
1129   /// \brief Get the origin for i-th argument of the instruction I.
1130   Value *getOrigin(Instruction *I, int i) {
1131     return getOrigin(I->getOperand(i));
1132   }
1133
1134   /// \brief Remember the place where a shadow check should be inserted.
1135   ///
1136   /// This location will be later instrumented with a check that will print a
1137   /// UMR warning in runtime if the shadow value is not 0.
1138   void insertShadowCheck(Value *Shadow, Value *Origin, Instruction *OrigIns) {
1139     assert(Shadow);
1140     if (!InsertChecks) return;
1141 #ifndef NDEBUG
1142     Type *ShadowTy = Shadow->getType();
1143     assert((isa<IntegerType>(ShadowTy) || isa<VectorType>(ShadowTy)) &&
1144            "Can only insert checks for integer and vector shadow types");
1145 #endif
1146     InstrumentationList.push_back(
1147         ShadowOriginAndInsertPoint(Shadow, Origin, OrigIns));
1148   }
1149
1150   /// \brief Remember the place where a shadow check should be inserted.
1151   ///
1152   /// This location will be later instrumented with a check that will print a
1153   /// UMR warning in runtime if the value is not fully defined.
1154   void insertShadowCheck(Value *Val, Instruction *OrigIns) {
1155     assert(Val);
1156     Value *Shadow, *Origin;
1157     if (ClCheckConstantShadow) {
1158       Shadow = getShadow(Val);
1159       if (!Shadow) return;
1160       Origin = getOrigin(Val);
1161     } else {
1162       Shadow = dyn_cast_or_null<Instruction>(getShadow(Val));
1163       if (!Shadow) return;
1164       Origin = dyn_cast_or_null<Instruction>(getOrigin(Val));
1165     }
1166     insertShadowCheck(Shadow, Origin, OrigIns);
1167   }
1168
1169   AtomicOrdering addReleaseOrdering(AtomicOrdering a) {
1170     switch (a) {
1171       case NotAtomic:
1172         return NotAtomic;
1173       case Unordered:
1174       case Monotonic:
1175       case Release:
1176         return Release;
1177       case Acquire:
1178       case AcquireRelease:
1179         return AcquireRelease;
1180       case SequentiallyConsistent:
1181         return SequentiallyConsistent;
1182     }
1183     llvm_unreachable("Unknown ordering");
1184   }
1185
1186   AtomicOrdering addAcquireOrdering(AtomicOrdering a) {
1187     switch (a) {
1188       case NotAtomic:
1189         return NotAtomic;
1190       case Unordered:
1191       case Monotonic:
1192       case Acquire:
1193         return Acquire;
1194       case Release:
1195       case AcquireRelease:
1196         return AcquireRelease;
1197       case SequentiallyConsistent:
1198         return SequentiallyConsistent;
1199     }
1200     llvm_unreachable("Unknown ordering");
1201   }
1202
1203   // ------------------- Visitors.
1204
1205   /// \brief Instrument LoadInst
1206   ///
1207   /// Loads the corresponding shadow and (optionally) origin.
1208   /// Optionally, checks that the load address is fully defined.
1209   void visitLoadInst(LoadInst &I) {
1210     assert(I.getType()->isSized() && "Load type must have size");
1211     IRBuilder<> IRB(I.getNextNode());
1212     Type *ShadowTy = getShadowTy(&I);
1213     Value *Addr = I.getPointerOperand();
1214     if (PropagateShadow && !I.getMetadata("nosanitize")) {
1215       Value *ShadowPtr = getShadowPtr(Addr, ShadowTy, IRB);
1216       setShadow(&I,
1217                 IRB.CreateAlignedLoad(ShadowPtr, I.getAlignment(), "_msld"));
1218     } else {
1219       setShadow(&I, getCleanShadow(&I));
1220     }
1221
1222     if (ClCheckAccessAddress)
1223       insertShadowCheck(I.getPointerOperand(), &I);
1224
1225     if (I.isAtomic())
1226       I.setOrdering(addAcquireOrdering(I.getOrdering()));
1227
1228     if (MS.TrackOrigins) {
1229       if (PropagateShadow) {
1230         unsigned Alignment = I.getAlignment();
1231         unsigned OriginAlignment = std::max(kMinOriginAlignment, Alignment);
1232         setOrigin(&I, IRB.CreateAlignedLoad(getOriginPtr(Addr, IRB, Alignment),
1233                                             OriginAlignment));
1234       } else {
1235         setOrigin(&I, getCleanOrigin());
1236       }
1237     }
1238   }
1239
1240   /// \brief Instrument StoreInst
1241   ///
1242   /// Stores the corresponding shadow and (optionally) origin.
1243   /// Optionally, checks that the store address is fully defined.
1244   void visitStoreInst(StoreInst &I) {
1245     StoreList.push_back(&I);
1246   }
1247
1248   void handleCASOrRMW(Instruction &I) {
1249     assert(isa<AtomicRMWInst>(I) || isa<AtomicCmpXchgInst>(I));
1250
1251     IRBuilder<> IRB(&I);
1252     Value *Addr = I.getOperand(0);
1253     Value *ShadowPtr = getShadowPtr(Addr, I.getType(), IRB);
1254
1255     if (ClCheckAccessAddress)
1256       insertShadowCheck(Addr, &I);
1257
1258     // Only test the conditional argument of cmpxchg instruction.
1259     // The other argument can potentially be uninitialized, but we can not
1260     // detect this situation reliably without possible false positives.
1261     if (isa<AtomicCmpXchgInst>(I))
1262       insertShadowCheck(I.getOperand(1), &I);
1263
1264     IRB.CreateStore(getCleanShadow(&I), ShadowPtr);
1265
1266     setShadow(&I, getCleanShadow(&I));
1267     setOrigin(&I, getCleanOrigin());
1268   }
1269
1270   void visitAtomicRMWInst(AtomicRMWInst &I) {
1271     handleCASOrRMW(I);
1272     I.setOrdering(addReleaseOrdering(I.getOrdering()));
1273   }
1274
1275   void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) {
1276     handleCASOrRMW(I);
1277     I.setSuccessOrdering(addReleaseOrdering(I.getSuccessOrdering()));
1278   }
1279
1280   // Vector manipulation.
1281   void visitExtractElementInst(ExtractElementInst &I) {
1282     insertShadowCheck(I.getOperand(1), &I);
1283     IRBuilder<> IRB(&I);
1284     setShadow(&I, IRB.CreateExtractElement(getShadow(&I, 0), I.getOperand(1),
1285               "_msprop"));
1286     setOrigin(&I, getOrigin(&I, 0));
1287   }
1288
1289   void visitInsertElementInst(InsertElementInst &I) {
1290     insertShadowCheck(I.getOperand(2), &I);
1291     IRBuilder<> IRB(&I);
1292     setShadow(&I, IRB.CreateInsertElement(getShadow(&I, 0), getShadow(&I, 1),
1293               I.getOperand(2), "_msprop"));
1294     setOriginForNaryOp(I);
1295   }
1296
1297   void visitShuffleVectorInst(ShuffleVectorInst &I) {
1298     insertShadowCheck(I.getOperand(2), &I);
1299     IRBuilder<> IRB(&I);
1300     setShadow(&I, IRB.CreateShuffleVector(getShadow(&I, 0), getShadow(&I, 1),
1301               I.getOperand(2), "_msprop"));
1302     setOriginForNaryOp(I);
1303   }
1304
1305   // Casts.
1306   void visitSExtInst(SExtInst &I) {
1307     IRBuilder<> IRB(&I);
1308     setShadow(&I, IRB.CreateSExt(getShadow(&I, 0), I.getType(), "_msprop"));
1309     setOrigin(&I, getOrigin(&I, 0));
1310   }
1311
1312   void visitZExtInst(ZExtInst &I) {
1313     IRBuilder<> IRB(&I);
1314     setShadow(&I, IRB.CreateZExt(getShadow(&I, 0), I.getType(), "_msprop"));
1315     setOrigin(&I, getOrigin(&I, 0));
1316   }
1317
1318   void visitTruncInst(TruncInst &I) {
1319     IRBuilder<> IRB(&I);
1320     setShadow(&I, IRB.CreateTrunc(getShadow(&I, 0), I.getType(), "_msprop"));
1321     setOrigin(&I, getOrigin(&I, 0));
1322   }
1323
1324   void visitBitCastInst(BitCastInst &I) {
1325     IRBuilder<> IRB(&I);
1326     setShadow(&I, IRB.CreateBitCast(getShadow(&I, 0), getShadowTy(&I)));
1327     setOrigin(&I, getOrigin(&I, 0));
1328   }
1329
1330   void visitPtrToIntInst(PtrToIntInst &I) {
1331     IRBuilder<> IRB(&I);
1332     setShadow(&I, IRB.CreateIntCast(getShadow(&I, 0), getShadowTy(&I), false,
1333              "_msprop_ptrtoint"));
1334     setOrigin(&I, getOrigin(&I, 0));
1335   }
1336
1337   void visitIntToPtrInst(IntToPtrInst &I) {
1338     IRBuilder<> IRB(&I);
1339     setShadow(&I, IRB.CreateIntCast(getShadow(&I, 0), getShadowTy(&I), false,
1340              "_msprop_inttoptr"));
1341     setOrigin(&I, getOrigin(&I, 0));
1342   }
1343
1344   void visitFPToSIInst(CastInst& I) { handleShadowOr(I); }
1345   void visitFPToUIInst(CastInst& I) { handleShadowOr(I); }
1346   void visitSIToFPInst(CastInst& I) { handleShadowOr(I); }
1347   void visitUIToFPInst(CastInst& I) { handleShadowOr(I); }
1348   void visitFPExtInst(CastInst& I) { handleShadowOr(I); }
1349   void visitFPTruncInst(CastInst& I) { handleShadowOr(I); }
1350
1351   /// \brief Propagate shadow for bitwise AND.
1352   ///
1353   /// This code is exact, i.e. if, for example, a bit in the left argument
1354   /// is defined and 0, then neither the value not definedness of the
1355   /// corresponding bit in B don't affect the resulting shadow.
1356   void visitAnd(BinaryOperator &I) {
1357     IRBuilder<> IRB(&I);
1358     //  "And" of 0 and a poisoned value results in unpoisoned value.
1359     //  1&1 => 1;     0&1 => 0;     p&1 => p;
1360     //  1&0 => 0;     0&0 => 0;     p&0 => 0;
1361     //  1&p => p;     0&p => 0;     p&p => p;
1362     //  S = (S1 & S2) | (V1 & S2) | (S1 & V2)
1363     Value *S1 = getShadow(&I, 0);
1364     Value *S2 = getShadow(&I, 1);
1365     Value *V1 = I.getOperand(0);
1366     Value *V2 = I.getOperand(1);
1367     if (V1->getType() != S1->getType()) {
1368       V1 = IRB.CreateIntCast(V1, S1->getType(), false);
1369       V2 = IRB.CreateIntCast(V2, S2->getType(), false);
1370     }
1371     Value *S1S2 = IRB.CreateAnd(S1, S2);
1372     Value *V1S2 = IRB.CreateAnd(V1, S2);
1373     Value *S1V2 = IRB.CreateAnd(S1, V2);
1374     setShadow(&I, IRB.CreateOr(S1S2, IRB.CreateOr(V1S2, S1V2)));
1375     setOriginForNaryOp(I);
1376   }
1377
1378   void visitOr(BinaryOperator &I) {
1379     IRBuilder<> IRB(&I);
1380     //  "Or" of 1 and a poisoned value results in unpoisoned value.
1381     //  1|1 => 1;     0|1 => 1;     p|1 => 1;
1382     //  1|0 => 1;     0|0 => 0;     p|0 => p;
1383     //  1|p => 1;     0|p => p;     p|p => p;
1384     //  S = (S1 & S2) | (~V1 & S2) | (S1 & ~V2)
1385     Value *S1 = getShadow(&I, 0);
1386     Value *S2 = getShadow(&I, 1);
1387     Value *V1 = IRB.CreateNot(I.getOperand(0));
1388     Value *V2 = IRB.CreateNot(I.getOperand(1));
1389     if (V1->getType() != S1->getType()) {
1390       V1 = IRB.CreateIntCast(V1, S1->getType(), false);
1391       V2 = IRB.CreateIntCast(V2, S2->getType(), false);
1392     }
1393     Value *S1S2 = IRB.CreateAnd(S1, S2);
1394     Value *V1S2 = IRB.CreateAnd(V1, S2);
1395     Value *S1V2 = IRB.CreateAnd(S1, V2);
1396     setShadow(&I, IRB.CreateOr(S1S2, IRB.CreateOr(V1S2, S1V2)));
1397     setOriginForNaryOp(I);
1398   }
1399
1400   /// \brief Default propagation of shadow and/or origin.
1401   ///
1402   /// This class implements the general case of shadow propagation, used in all
1403   /// cases where we don't know and/or don't care about what the operation
1404   /// actually does. It converts all input shadow values to a common type
1405   /// (extending or truncating as necessary), and bitwise OR's them.
1406   ///
1407   /// This is much cheaper than inserting checks (i.e. requiring inputs to be
1408   /// fully initialized), and less prone to false positives.
1409   ///
1410   /// This class also implements the general case of origin propagation. For a
1411   /// Nary operation, result origin is set to the origin of an argument that is
1412   /// not entirely initialized. If there is more than one such arguments, the
1413   /// rightmost of them is picked. It does not matter which one is picked if all
1414   /// arguments are initialized.
1415   template <bool CombineShadow>
1416   class Combiner {
1417     Value *Shadow;
1418     Value *Origin;
1419     IRBuilder<> &IRB;
1420     MemorySanitizerVisitor *MSV;
1421
1422   public:
1423     Combiner(MemorySanitizerVisitor *MSV, IRBuilder<> &IRB) :
1424       Shadow(nullptr), Origin(nullptr), IRB(IRB), MSV(MSV) {}
1425
1426     /// \brief Add a pair of shadow and origin values to the mix.
1427     Combiner &Add(Value *OpShadow, Value *OpOrigin) {
1428       if (CombineShadow) {
1429         assert(OpShadow);
1430         if (!Shadow)
1431           Shadow = OpShadow;
1432         else {
1433           OpShadow = MSV->CreateShadowCast(IRB, OpShadow, Shadow->getType());
1434           Shadow = IRB.CreateOr(Shadow, OpShadow, "_msprop");
1435         }
1436       }
1437
1438       if (MSV->MS.TrackOrigins) {
1439         assert(OpOrigin);
1440         if (!Origin) {
1441           Origin = OpOrigin;
1442         } else {
1443           Constant *ConstOrigin = dyn_cast<Constant>(OpOrigin);
1444           // No point in adding something that might result in 0 origin value.
1445           if (!ConstOrigin || !ConstOrigin->isNullValue()) {
1446             Value *FlatShadow = MSV->convertToShadowTyNoVec(OpShadow, IRB);
1447             Value *Cond =
1448                 IRB.CreateICmpNE(FlatShadow, MSV->getCleanShadow(FlatShadow));
1449             Origin = IRB.CreateSelect(Cond, OpOrigin, Origin);
1450           }
1451         }
1452       }
1453       return *this;
1454     }
1455
1456     /// \brief Add an application value to the mix.
1457     Combiner &Add(Value *V) {
1458       Value *OpShadow = MSV->getShadow(V);
1459       Value *OpOrigin = MSV->MS.TrackOrigins ? MSV->getOrigin(V) : nullptr;
1460       return Add(OpShadow, OpOrigin);
1461     }
1462
1463     /// \brief Set the current combined values as the given instruction's shadow
1464     /// and origin.
1465     void Done(Instruction *I) {
1466       if (CombineShadow) {
1467         assert(Shadow);
1468         Shadow = MSV->CreateShadowCast(IRB, Shadow, MSV->getShadowTy(I));
1469         MSV->setShadow(I, Shadow);
1470       }
1471       if (MSV->MS.TrackOrigins) {
1472         assert(Origin);
1473         MSV->setOrigin(I, Origin);
1474       }
1475     }
1476   };
1477
1478   typedef Combiner<true> ShadowAndOriginCombiner;
1479   typedef Combiner<false> OriginCombiner;
1480
1481   /// \brief Propagate origin for arbitrary operation.
1482   void setOriginForNaryOp(Instruction &I) {
1483     if (!MS.TrackOrigins) return;
1484     IRBuilder<> IRB(&I);
1485     OriginCombiner OC(this, IRB);
1486     for (Instruction::op_iterator OI = I.op_begin(); OI != I.op_end(); ++OI)
1487       OC.Add(OI->get());
1488     OC.Done(&I);
1489   }
1490
1491   size_t VectorOrPrimitiveTypeSizeInBits(Type *Ty) {
1492     assert(!(Ty->isVectorTy() && Ty->getScalarType()->isPointerTy()) &&
1493            "Vector of pointers is not a valid shadow type");
1494     return Ty->isVectorTy() ?
1495       Ty->getVectorNumElements() * Ty->getScalarSizeInBits() :
1496       Ty->getPrimitiveSizeInBits();
1497   }
1498
1499   /// \brief Cast between two shadow types, extending or truncating as
1500   /// necessary.
1501   Value *CreateShadowCast(IRBuilder<> &IRB, Value *V, Type *dstTy,
1502                           bool Signed = false) {
1503     Type *srcTy = V->getType();
1504     if (dstTy->isIntegerTy() && srcTy->isIntegerTy())
1505       return IRB.CreateIntCast(V, dstTy, Signed);
1506     if (dstTy->isVectorTy() && srcTy->isVectorTy() &&
1507         dstTy->getVectorNumElements() == srcTy->getVectorNumElements())
1508       return IRB.CreateIntCast(V, dstTy, Signed);
1509     size_t srcSizeInBits = VectorOrPrimitiveTypeSizeInBits(srcTy);
1510     size_t dstSizeInBits = VectorOrPrimitiveTypeSizeInBits(dstTy);
1511     Value *V1 = IRB.CreateBitCast(V, Type::getIntNTy(*MS.C, srcSizeInBits));
1512     Value *V2 =
1513       IRB.CreateIntCast(V1, Type::getIntNTy(*MS.C, dstSizeInBits), Signed);
1514     return IRB.CreateBitCast(V2, dstTy);
1515     // TODO: handle struct types.
1516   }
1517
1518   /// \brief Cast an application value to the type of its own shadow.
1519   Value *CreateAppToShadowCast(IRBuilder<> &IRB, Value *V) {
1520     Type *ShadowTy = getShadowTy(V);
1521     if (V->getType() == ShadowTy)
1522       return V;
1523     if (V->getType()->isPtrOrPtrVectorTy())
1524       return IRB.CreatePtrToInt(V, ShadowTy);
1525     else
1526       return IRB.CreateBitCast(V, ShadowTy);
1527   }
1528
1529   /// \brief Propagate shadow for arbitrary operation.
1530   void handleShadowOr(Instruction &I) {
1531     IRBuilder<> IRB(&I);
1532     ShadowAndOriginCombiner SC(this, IRB);
1533     for (Instruction::op_iterator OI = I.op_begin(); OI != I.op_end(); ++OI)
1534       SC.Add(OI->get());
1535     SC.Done(&I);
1536   }
1537
1538   // \brief Handle multiplication by constant.
1539   //
1540   // Handle a special case of multiplication by constant that may have one or
1541   // more zeros in the lower bits. This makes corresponding number of lower bits
1542   // of the result zero as well. We model it by shifting the other operand
1543   // shadow left by the required number of bits. Effectively, we transform
1544   // (X * (A * 2**B)) to ((X << B) * A) and instrument (X << B) as (Sx << B).
1545   // We use multiplication by 2**N instead of shift to cover the case of
1546   // multiplication by 0, which may occur in some elements of a vector operand.
1547   void handleMulByConstant(BinaryOperator &I, Constant *ConstArg,
1548                            Value *OtherArg) {
1549     Constant *ShadowMul;
1550     Type *Ty = ConstArg->getType();
1551     if (Ty->isVectorTy()) {
1552       unsigned NumElements = Ty->getVectorNumElements();
1553       Type *EltTy = Ty->getSequentialElementType();
1554       SmallVector<Constant *, 16> Elements;
1555       for (unsigned Idx = 0; Idx < NumElements; ++Idx) {
1556         ConstantInt *Elt =
1557             dyn_cast<ConstantInt>(ConstArg->getAggregateElement(Idx));
1558         APInt V = Elt->getValue();
1559         APInt V2 = APInt(V.getBitWidth(), 1) << V.countTrailingZeros();
1560         Elements.push_back(ConstantInt::get(EltTy, V2));
1561       }
1562       ShadowMul = ConstantVector::get(Elements);
1563     } else {
1564       ConstantInt *Elt = dyn_cast<ConstantInt>(ConstArg);
1565       APInt V = Elt->getValue();
1566       APInt V2 = APInt(V.getBitWidth(), 1) << V.countTrailingZeros();
1567       ShadowMul = ConstantInt::get(Elt->getType(), V2);
1568     }
1569
1570     IRBuilder<> IRB(&I);
1571     setShadow(&I,
1572               IRB.CreateMul(getShadow(OtherArg), ShadowMul, "msprop_mul_cst"));
1573     setOrigin(&I, getOrigin(OtherArg));
1574   }
1575
1576   void visitMul(BinaryOperator &I) {
1577     Constant *constOp0 = dyn_cast<Constant>(I.getOperand(0));
1578     Constant *constOp1 = dyn_cast<Constant>(I.getOperand(1));
1579     if (constOp0 && !constOp1)
1580       handleMulByConstant(I, constOp0, I.getOperand(1));
1581     else if (constOp1 && !constOp0)
1582       handleMulByConstant(I, constOp1, I.getOperand(0));
1583     else
1584       handleShadowOr(I);
1585   }
1586
1587   void visitFAdd(BinaryOperator &I) { handleShadowOr(I); }
1588   void visitFSub(BinaryOperator &I) { handleShadowOr(I); }
1589   void visitFMul(BinaryOperator &I) { handleShadowOr(I); }
1590   void visitAdd(BinaryOperator &I) { handleShadowOr(I); }
1591   void visitSub(BinaryOperator &I) { handleShadowOr(I); }
1592   void visitXor(BinaryOperator &I) { handleShadowOr(I); }
1593
1594   void handleDiv(Instruction &I) {
1595     IRBuilder<> IRB(&I);
1596     // Strict on the second argument.
1597     insertShadowCheck(I.getOperand(1), &I);
1598     setShadow(&I, getShadow(&I, 0));
1599     setOrigin(&I, getOrigin(&I, 0));
1600   }
1601
1602   void visitUDiv(BinaryOperator &I) { handleDiv(I); }
1603   void visitSDiv(BinaryOperator &I) { handleDiv(I); }
1604   void visitFDiv(BinaryOperator &I) { handleDiv(I); }
1605   void visitURem(BinaryOperator &I) { handleDiv(I); }
1606   void visitSRem(BinaryOperator &I) { handleDiv(I); }
1607   void visitFRem(BinaryOperator &I) { handleDiv(I); }
1608
1609   /// \brief Instrument == and != comparisons.
1610   ///
1611   /// Sometimes the comparison result is known even if some of the bits of the
1612   /// arguments are not.
1613   void handleEqualityComparison(ICmpInst &I) {
1614     IRBuilder<> IRB(&I);
1615     Value *A = I.getOperand(0);
1616     Value *B = I.getOperand(1);
1617     Value *Sa = getShadow(A);
1618     Value *Sb = getShadow(B);
1619
1620     // Get rid of pointers and vectors of pointers.
1621     // For ints (and vectors of ints), types of A and Sa match,
1622     // and this is a no-op.
1623     A = IRB.CreatePointerCast(A, Sa->getType());
1624     B = IRB.CreatePointerCast(B, Sb->getType());
1625
1626     // A == B  <==>  (C = A^B) == 0
1627     // A != B  <==>  (C = A^B) != 0
1628     // Sc = Sa | Sb
1629     Value *C = IRB.CreateXor(A, B);
1630     Value *Sc = IRB.CreateOr(Sa, Sb);
1631     // Now dealing with i = (C == 0) comparison (or C != 0, does not matter now)
1632     // Result is defined if one of the following is true
1633     // * there is a defined 1 bit in C
1634     // * C is fully defined
1635     // Si = !(C & ~Sc) && Sc
1636     Value *Zero = Constant::getNullValue(Sc->getType());
1637     Value *MinusOne = Constant::getAllOnesValue(Sc->getType());
1638     Value *Si =
1639       IRB.CreateAnd(IRB.CreateICmpNE(Sc, Zero),
1640                     IRB.CreateICmpEQ(
1641                       IRB.CreateAnd(IRB.CreateXor(Sc, MinusOne), C), Zero));
1642     Si->setName("_msprop_icmp");
1643     setShadow(&I, Si);
1644     setOriginForNaryOp(I);
1645   }
1646
1647   /// \brief Build the lowest possible value of V, taking into account V's
1648   ///        uninitialized bits.
1649   Value *getLowestPossibleValue(IRBuilder<> &IRB, Value *A, Value *Sa,
1650                                 bool isSigned) {
1651     if (isSigned) {
1652       // Split shadow into sign bit and other bits.
1653       Value *SaOtherBits = IRB.CreateLShr(IRB.CreateShl(Sa, 1), 1);
1654       Value *SaSignBit = IRB.CreateXor(Sa, SaOtherBits);
1655       // Maximise the undefined shadow bit, minimize other undefined bits.
1656       return
1657         IRB.CreateOr(IRB.CreateAnd(A, IRB.CreateNot(SaOtherBits)), SaSignBit);
1658     } else {
1659       // Minimize undefined bits.
1660       return IRB.CreateAnd(A, IRB.CreateNot(Sa));
1661     }
1662   }
1663
1664   /// \brief Build the highest possible value of V, taking into account V's
1665   ///        uninitialized bits.
1666   Value *getHighestPossibleValue(IRBuilder<> &IRB, Value *A, Value *Sa,
1667                                 bool isSigned) {
1668     if (isSigned) {
1669       // Split shadow into sign bit and other bits.
1670       Value *SaOtherBits = IRB.CreateLShr(IRB.CreateShl(Sa, 1), 1);
1671       Value *SaSignBit = IRB.CreateXor(Sa, SaOtherBits);
1672       // Minimise the undefined shadow bit, maximise other undefined bits.
1673       return
1674         IRB.CreateOr(IRB.CreateAnd(A, IRB.CreateNot(SaSignBit)), SaOtherBits);
1675     } else {
1676       // Maximize undefined bits.
1677       return IRB.CreateOr(A, Sa);
1678     }
1679   }
1680
1681   /// \brief Instrument relational comparisons.
1682   ///
1683   /// This function does exact shadow propagation for all relational
1684   /// comparisons of integers, pointers and vectors of those.
1685   /// FIXME: output seems suboptimal when one of the operands is a constant
1686   void handleRelationalComparisonExact(ICmpInst &I) {
1687     IRBuilder<> IRB(&I);
1688     Value *A = I.getOperand(0);
1689     Value *B = I.getOperand(1);
1690     Value *Sa = getShadow(A);
1691     Value *Sb = getShadow(B);
1692
1693     // Get rid of pointers and vectors of pointers.
1694     // For ints (and vectors of ints), types of A and Sa match,
1695     // and this is a no-op.
1696     A = IRB.CreatePointerCast(A, Sa->getType());
1697     B = IRB.CreatePointerCast(B, Sb->getType());
1698
1699     // Let [a0, a1] be the interval of possible values of A, taking into account
1700     // its undefined bits. Let [b0, b1] be the interval of possible values of B.
1701     // Then (A cmp B) is defined iff (a0 cmp b1) == (a1 cmp b0).
1702     bool IsSigned = I.isSigned();
1703     Value *S1 = IRB.CreateICmp(I.getPredicate(),
1704                                getLowestPossibleValue(IRB, A, Sa, IsSigned),
1705                                getHighestPossibleValue(IRB, B, Sb, IsSigned));
1706     Value *S2 = IRB.CreateICmp(I.getPredicate(),
1707                                getHighestPossibleValue(IRB, A, Sa, IsSigned),
1708                                getLowestPossibleValue(IRB, B, Sb, IsSigned));
1709     Value *Si = IRB.CreateXor(S1, S2);
1710     setShadow(&I, Si);
1711     setOriginForNaryOp(I);
1712   }
1713
1714   /// \brief Instrument signed relational comparisons.
1715   ///
1716   /// Handle (x<0) and (x>=0) comparisons (essentially, sign bit tests) by
1717   /// propagating the highest bit of the shadow. Everything else is delegated
1718   /// to handleShadowOr().
1719   void handleSignedRelationalComparison(ICmpInst &I) {
1720     Constant *constOp0 = dyn_cast<Constant>(I.getOperand(0));
1721     Constant *constOp1 = dyn_cast<Constant>(I.getOperand(1));
1722     Value* op = nullptr;
1723     CmpInst::Predicate pre = I.getPredicate();
1724     if (constOp0 && constOp0->isNullValue() &&
1725         (pre == CmpInst::ICMP_SGT || pre == CmpInst::ICMP_SLE)) {
1726       op = I.getOperand(1);
1727     } else if (constOp1 && constOp1->isNullValue() &&
1728                (pre == CmpInst::ICMP_SLT || pre == CmpInst::ICMP_SGE)) {
1729       op = I.getOperand(0);
1730     }
1731     if (op) {
1732       IRBuilder<> IRB(&I);
1733       Value* Shadow =
1734         IRB.CreateICmpSLT(getShadow(op), getCleanShadow(op), "_msprop_icmpslt");
1735       setShadow(&I, Shadow);
1736       setOrigin(&I, getOrigin(op));
1737     } else {
1738       handleShadowOr(I);
1739     }
1740   }
1741
1742   void visitICmpInst(ICmpInst &I) {
1743     if (!ClHandleICmp) {
1744       handleShadowOr(I);
1745       return;
1746     }
1747     if (I.isEquality()) {
1748       handleEqualityComparison(I);
1749       return;
1750     }
1751
1752     assert(I.isRelational());
1753     if (ClHandleICmpExact) {
1754       handleRelationalComparisonExact(I);
1755       return;
1756     }
1757     if (I.isSigned()) {
1758       handleSignedRelationalComparison(I);
1759       return;
1760     }
1761
1762     assert(I.isUnsigned());
1763     if ((isa<Constant>(I.getOperand(0)) || isa<Constant>(I.getOperand(1)))) {
1764       handleRelationalComparisonExact(I);
1765       return;
1766     }
1767
1768     handleShadowOr(I);
1769   }
1770
1771   void visitFCmpInst(FCmpInst &I) {
1772     handleShadowOr(I);
1773   }
1774
1775   void handleShift(BinaryOperator &I) {
1776     IRBuilder<> IRB(&I);
1777     // If any of the S2 bits are poisoned, the whole thing is poisoned.
1778     // Otherwise perform the same shift on S1.
1779     Value *S1 = getShadow(&I, 0);
1780     Value *S2 = getShadow(&I, 1);
1781     Value *S2Conv = IRB.CreateSExt(IRB.CreateICmpNE(S2, getCleanShadow(S2)),
1782                                    S2->getType());
1783     Value *V2 = I.getOperand(1);
1784     Value *Shift = IRB.CreateBinOp(I.getOpcode(), S1, V2);
1785     setShadow(&I, IRB.CreateOr(Shift, S2Conv));
1786     setOriginForNaryOp(I);
1787   }
1788
1789   void visitShl(BinaryOperator &I) { handleShift(I); }
1790   void visitAShr(BinaryOperator &I) { handleShift(I); }
1791   void visitLShr(BinaryOperator &I) { handleShift(I); }
1792
1793   /// \brief Instrument llvm.memmove
1794   ///
1795   /// At this point we don't know if llvm.memmove will be inlined or not.
1796   /// If we don't instrument it and it gets inlined,
1797   /// our interceptor will not kick in and we will lose the memmove.
1798   /// If we instrument the call here, but it does not get inlined,
1799   /// we will memove the shadow twice: which is bad in case
1800   /// of overlapping regions. So, we simply lower the intrinsic to a call.
1801   ///
1802   /// Similar situation exists for memcpy and memset.
1803   void visitMemMoveInst(MemMoveInst &I) {
1804     IRBuilder<> IRB(&I);
1805     IRB.CreateCall(
1806         MS.MemmoveFn,
1807         {IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()),
1808          IRB.CreatePointerCast(I.getArgOperand(1), IRB.getInt8PtrTy()),
1809          IRB.CreateIntCast(I.getArgOperand(2), MS.IntptrTy, false)});
1810     I.eraseFromParent();
1811   }
1812
1813   // Similar to memmove: avoid copying shadow twice.
1814   // This is somewhat unfortunate as it may slowdown small constant memcpys.
1815   // FIXME: consider doing manual inline for small constant sizes and proper
1816   // alignment.
1817   void visitMemCpyInst(MemCpyInst &I) {
1818     IRBuilder<> IRB(&I);
1819     IRB.CreateCall(
1820         MS.MemcpyFn,
1821         {IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()),
1822          IRB.CreatePointerCast(I.getArgOperand(1), IRB.getInt8PtrTy()),
1823          IRB.CreateIntCast(I.getArgOperand(2), MS.IntptrTy, false)});
1824     I.eraseFromParent();
1825   }
1826
1827   // Same as memcpy.
1828   void visitMemSetInst(MemSetInst &I) {
1829     IRBuilder<> IRB(&I);
1830     IRB.CreateCall(
1831         MS.MemsetFn,
1832         {IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()),
1833          IRB.CreateIntCast(I.getArgOperand(1), IRB.getInt32Ty(), false),
1834          IRB.CreateIntCast(I.getArgOperand(2), MS.IntptrTy, false)});
1835     I.eraseFromParent();
1836   }
1837
1838   void visitVAStartInst(VAStartInst &I) {
1839     VAHelper->visitVAStartInst(I);
1840   }
1841
1842   void visitVACopyInst(VACopyInst &I) {
1843     VAHelper->visitVACopyInst(I);
1844   }
1845
1846   enum IntrinsicKind {
1847     IK_DoesNotAccessMemory,
1848     IK_OnlyReadsMemory,
1849     IK_WritesMemory
1850   };
1851
1852   static IntrinsicKind getIntrinsicKind(Intrinsic::ID iid) {
1853     const int DoesNotAccessMemory = IK_DoesNotAccessMemory;
1854     const int OnlyReadsArgumentPointees = IK_OnlyReadsMemory;
1855     const int OnlyReadsMemory = IK_OnlyReadsMemory;
1856     const int OnlyAccessesArgumentPointees = IK_WritesMemory;
1857     const int UnknownModRefBehavior = IK_WritesMemory;
1858 #define GET_INTRINSIC_MODREF_BEHAVIOR
1859 #define ModRefBehavior IntrinsicKind
1860 #include "llvm/IR/Intrinsics.gen"
1861 #undef ModRefBehavior
1862 #undef GET_INTRINSIC_MODREF_BEHAVIOR
1863   }
1864
1865   /// \brief Handle vector store-like intrinsics.
1866   ///
1867   /// Instrument intrinsics that look like a simple SIMD store: writes memory,
1868   /// has 1 pointer argument and 1 vector argument, returns void.
1869   bool handleVectorStoreIntrinsic(IntrinsicInst &I) {
1870     IRBuilder<> IRB(&I);
1871     Value* Addr = I.getArgOperand(0);
1872     Value *Shadow = getShadow(&I, 1);
1873     Value *ShadowPtr = getShadowPtr(Addr, Shadow->getType(), IRB);
1874
1875     // We don't know the pointer alignment (could be unaligned SSE store!).
1876     // Have to assume to worst case.
1877     IRB.CreateAlignedStore(Shadow, ShadowPtr, 1);
1878
1879     if (ClCheckAccessAddress)
1880       insertShadowCheck(Addr, &I);
1881
1882     // FIXME: use ClStoreCleanOrigin
1883     // FIXME: factor out common code from materializeStores
1884     if (MS.TrackOrigins)
1885       IRB.CreateStore(getOrigin(&I, 1), getOriginPtr(Addr, IRB, 1));
1886     return true;
1887   }
1888
1889   /// \brief Handle vector load-like intrinsics.
1890   ///
1891   /// Instrument intrinsics that look like a simple SIMD load: reads memory,
1892   /// has 1 pointer argument, returns a vector.
1893   bool handleVectorLoadIntrinsic(IntrinsicInst &I) {
1894     IRBuilder<> IRB(&I);
1895     Value *Addr = I.getArgOperand(0);
1896
1897     Type *ShadowTy = getShadowTy(&I);
1898     if (PropagateShadow) {
1899       Value *ShadowPtr = getShadowPtr(Addr, ShadowTy, IRB);
1900       // We don't know the pointer alignment (could be unaligned SSE load!).
1901       // Have to assume to worst case.
1902       setShadow(&I, IRB.CreateAlignedLoad(ShadowPtr, 1, "_msld"));
1903     } else {
1904       setShadow(&I, getCleanShadow(&I));
1905     }
1906
1907     if (ClCheckAccessAddress)
1908       insertShadowCheck(Addr, &I);
1909
1910     if (MS.TrackOrigins) {
1911       if (PropagateShadow)
1912         setOrigin(&I, IRB.CreateLoad(getOriginPtr(Addr, IRB, 1)));
1913       else
1914         setOrigin(&I, getCleanOrigin());
1915     }
1916     return true;
1917   }
1918
1919   /// \brief Handle (SIMD arithmetic)-like intrinsics.
1920   ///
1921   /// Instrument intrinsics with any number of arguments of the same type,
1922   /// equal to the return type. The type should be simple (no aggregates or
1923   /// pointers; vectors are fine).
1924   /// Caller guarantees that this intrinsic does not access memory.
1925   bool maybeHandleSimpleNomemIntrinsic(IntrinsicInst &I) {
1926     Type *RetTy = I.getType();
1927     if (!(RetTy->isIntOrIntVectorTy() ||
1928           RetTy->isFPOrFPVectorTy() ||
1929           RetTy->isX86_MMXTy()))
1930       return false;
1931
1932     unsigned NumArgOperands = I.getNumArgOperands();
1933
1934     for (unsigned i = 0; i < NumArgOperands; ++i) {
1935       Type *Ty = I.getArgOperand(i)->getType();
1936       if (Ty != RetTy)
1937         return false;
1938     }
1939
1940     IRBuilder<> IRB(&I);
1941     ShadowAndOriginCombiner SC(this, IRB);
1942     for (unsigned i = 0; i < NumArgOperands; ++i)
1943       SC.Add(I.getArgOperand(i));
1944     SC.Done(&I);
1945
1946     return true;
1947   }
1948
1949   /// \brief Heuristically instrument unknown intrinsics.
1950   ///
1951   /// The main purpose of this code is to do something reasonable with all
1952   /// random intrinsics we might encounter, most importantly - SIMD intrinsics.
1953   /// We recognize several classes of intrinsics by their argument types and
1954   /// ModRefBehaviour and apply special intrumentation when we are reasonably
1955   /// sure that we know what the intrinsic does.
1956   ///
1957   /// We special-case intrinsics where this approach fails. See llvm.bswap
1958   /// handling as an example of that.
1959   bool handleUnknownIntrinsic(IntrinsicInst &I) {
1960     unsigned NumArgOperands = I.getNumArgOperands();
1961     if (NumArgOperands == 0)
1962       return false;
1963
1964     Intrinsic::ID iid = I.getIntrinsicID();
1965     IntrinsicKind IK = getIntrinsicKind(iid);
1966     bool OnlyReadsMemory = IK == IK_OnlyReadsMemory;
1967     bool WritesMemory = IK == IK_WritesMemory;
1968     assert(!(OnlyReadsMemory && WritesMemory));
1969
1970     if (NumArgOperands == 2 &&
1971         I.getArgOperand(0)->getType()->isPointerTy() &&
1972         I.getArgOperand(1)->getType()->isVectorTy() &&
1973         I.getType()->isVoidTy() &&
1974         WritesMemory) {
1975       // This looks like a vector store.
1976       return handleVectorStoreIntrinsic(I);
1977     }
1978
1979     if (NumArgOperands == 1 &&
1980         I.getArgOperand(0)->getType()->isPointerTy() &&
1981         I.getType()->isVectorTy() &&
1982         OnlyReadsMemory) {
1983       // This looks like a vector load.
1984       return handleVectorLoadIntrinsic(I);
1985     }
1986
1987     if (!OnlyReadsMemory && !WritesMemory)
1988       if (maybeHandleSimpleNomemIntrinsic(I))
1989         return true;
1990
1991     // FIXME: detect and handle SSE maskstore/maskload
1992     return false;
1993   }
1994
1995   void handleBswap(IntrinsicInst &I) {
1996     IRBuilder<> IRB(&I);
1997     Value *Op = I.getArgOperand(0);
1998     Type *OpType = Op->getType();
1999     Function *BswapFunc = Intrinsic::getDeclaration(
2000       F.getParent(), Intrinsic::bswap, makeArrayRef(&OpType, 1));
2001     setShadow(&I, IRB.CreateCall(BswapFunc, getShadow(Op)));
2002     setOrigin(&I, getOrigin(Op));
2003   }
2004
2005   // \brief Instrument vector convert instrinsic.
2006   //
2007   // This function instruments intrinsics like cvtsi2ss:
2008   // %Out = int_xxx_cvtyyy(%ConvertOp)
2009   // or
2010   // %Out = int_xxx_cvtyyy(%CopyOp, %ConvertOp)
2011   // Intrinsic converts \p NumUsedElements elements of \p ConvertOp to the same
2012   // number \p Out elements, and (if has 2 arguments) copies the rest of the
2013   // elements from \p CopyOp.
2014   // In most cases conversion involves floating-point value which may trigger a
2015   // hardware exception when not fully initialized. For this reason we require
2016   // \p ConvertOp[0:NumUsedElements] to be fully initialized and trap otherwise.
2017   // We copy the shadow of \p CopyOp[NumUsedElements:] to \p
2018   // Out[NumUsedElements:]. This means that intrinsics without \p CopyOp always
2019   // return a fully initialized value.
2020   void handleVectorConvertIntrinsic(IntrinsicInst &I, int NumUsedElements) {
2021     IRBuilder<> IRB(&I);
2022     Value *CopyOp, *ConvertOp;
2023
2024     switch (I.getNumArgOperands()) {
2025     case 2:
2026       CopyOp = I.getArgOperand(0);
2027       ConvertOp = I.getArgOperand(1);
2028       break;
2029     case 1:
2030       ConvertOp = I.getArgOperand(0);
2031       CopyOp = nullptr;
2032       break;
2033     default:
2034       llvm_unreachable("Cvt intrinsic with unsupported number of arguments.");
2035     }
2036
2037     // The first *NumUsedElements* elements of ConvertOp are converted to the
2038     // same number of output elements. The rest of the output is copied from
2039     // CopyOp, or (if not available) filled with zeroes.
2040     // Combine shadow for elements of ConvertOp that are used in this operation,
2041     // and insert a check.
2042     // FIXME: consider propagating shadow of ConvertOp, at least in the case of
2043     // int->any conversion.
2044     Value *ConvertShadow = getShadow(ConvertOp);
2045     Value *AggShadow = nullptr;
2046     if (ConvertOp->getType()->isVectorTy()) {
2047       AggShadow = IRB.CreateExtractElement(
2048           ConvertShadow, ConstantInt::get(IRB.getInt32Ty(), 0));
2049       for (int i = 1; i < NumUsedElements; ++i) {
2050         Value *MoreShadow = IRB.CreateExtractElement(
2051             ConvertShadow, ConstantInt::get(IRB.getInt32Ty(), i));
2052         AggShadow = IRB.CreateOr(AggShadow, MoreShadow);
2053       }
2054     } else {
2055       AggShadow = ConvertShadow;
2056     }
2057     assert(AggShadow->getType()->isIntegerTy());
2058     insertShadowCheck(AggShadow, getOrigin(ConvertOp), &I);
2059
2060     // Build result shadow by zero-filling parts of CopyOp shadow that come from
2061     // ConvertOp.
2062     if (CopyOp) {
2063       assert(CopyOp->getType() == I.getType());
2064       assert(CopyOp->getType()->isVectorTy());
2065       Value *ResultShadow = getShadow(CopyOp);
2066       Type *EltTy = ResultShadow->getType()->getVectorElementType();
2067       for (int i = 0; i < NumUsedElements; ++i) {
2068         ResultShadow = IRB.CreateInsertElement(
2069             ResultShadow, ConstantInt::getNullValue(EltTy),
2070             ConstantInt::get(IRB.getInt32Ty(), i));
2071       }
2072       setShadow(&I, ResultShadow);
2073       setOrigin(&I, getOrigin(CopyOp));
2074     } else {
2075       setShadow(&I, getCleanShadow(&I));
2076       setOrigin(&I, getCleanOrigin());
2077     }
2078   }
2079
2080   // Given a scalar or vector, extract lower 64 bits (or less), and return all
2081   // zeroes if it is zero, and all ones otherwise.
2082   Value *Lower64ShadowExtend(IRBuilder<> &IRB, Value *S, Type *T) {
2083     if (S->getType()->isVectorTy())
2084       S = CreateShadowCast(IRB, S, IRB.getInt64Ty(), /* Signed */ true);
2085     assert(S->getType()->getPrimitiveSizeInBits() <= 64);
2086     Value *S2 = IRB.CreateICmpNE(S, getCleanShadow(S));
2087     return CreateShadowCast(IRB, S2, T, /* Signed */ true);
2088   }
2089
2090   Value *VariableShadowExtend(IRBuilder<> &IRB, Value *S) {
2091     Type *T = S->getType();
2092     assert(T->isVectorTy());
2093     Value *S2 = IRB.CreateICmpNE(S, getCleanShadow(S));
2094     return IRB.CreateSExt(S2, T);
2095   }
2096
2097   // \brief Instrument vector shift instrinsic.
2098   //
2099   // This function instruments intrinsics like int_x86_avx2_psll_w.
2100   // Intrinsic shifts %In by %ShiftSize bits.
2101   // %ShiftSize may be a vector. In that case the lower 64 bits determine shift
2102   // size, and the rest is ignored. Behavior is defined even if shift size is
2103   // greater than register (or field) width.
2104   void handleVectorShiftIntrinsic(IntrinsicInst &I, bool Variable) {
2105     assert(I.getNumArgOperands() == 2);
2106     IRBuilder<> IRB(&I);
2107     // If any of the S2 bits are poisoned, the whole thing is poisoned.
2108     // Otherwise perform the same shift on S1.
2109     Value *S1 = getShadow(&I, 0);
2110     Value *S2 = getShadow(&I, 1);
2111     Value *S2Conv = Variable ? VariableShadowExtend(IRB, S2)
2112                              : Lower64ShadowExtend(IRB, S2, getShadowTy(&I));
2113     Value *V1 = I.getOperand(0);
2114     Value *V2 = I.getOperand(1);
2115     Value *Shift = IRB.CreateCall(I.getCalledValue(),
2116                                   {IRB.CreateBitCast(S1, V1->getType()), V2});
2117     Shift = IRB.CreateBitCast(Shift, getShadowTy(&I));
2118     setShadow(&I, IRB.CreateOr(Shift, S2Conv));
2119     setOriginForNaryOp(I);
2120   }
2121
2122   // \brief Get an X86_MMX-sized vector type.
2123   Type *getMMXVectorTy(unsigned EltSizeInBits) {
2124     const unsigned X86_MMXSizeInBits = 64;
2125     return VectorType::get(IntegerType::get(*MS.C, EltSizeInBits),
2126                            X86_MMXSizeInBits / EltSizeInBits);
2127   }
2128
2129   // \brief Returns a signed counterpart for an (un)signed-saturate-and-pack
2130   // intrinsic.
2131   Intrinsic::ID getSignedPackIntrinsic(Intrinsic::ID id) {
2132     switch (id) {
2133       case llvm::Intrinsic::x86_sse2_packsswb_128:
2134       case llvm::Intrinsic::x86_sse2_packuswb_128:
2135         return llvm::Intrinsic::x86_sse2_packsswb_128;
2136
2137       case llvm::Intrinsic::x86_sse2_packssdw_128:
2138       case llvm::Intrinsic::x86_sse41_packusdw:
2139         return llvm::Intrinsic::x86_sse2_packssdw_128;
2140
2141       case llvm::Intrinsic::x86_avx2_packsswb:
2142       case llvm::Intrinsic::x86_avx2_packuswb:
2143         return llvm::Intrinsic::x86_avx2_packsswb;
2144
2145       case llvm::Intrinsic::x86_avx2_packssdw:
2146       case llvm::Intrinsic::x86_avx2_packusdw:
2147         return llvm::Intrinsic::x86_avx2_packssdw;
2148
2149       case llvm::Intrinsic::x86_mmx_packsswb:
2150       case llvm::Intrinsic::x86_mmx_packuswb:
2151         return llvm::Intrinsic::x86_mmx_packsswb;
2152
2153       case llvm::Intrinsic::x86_mmx_packssdw:
2154         return llvm::Intrinsic::x86_mmx_packssdw;
2155       default:
2156         llvm_unreachable("unexpected intrinsic id");
2157     }
2158   }
2159
2160   // \brief Instrument vector pack instrinsic.
2161   //
2162   // This function instruments intrinsics like x86_mmx_packsswb, that
2163   // packs elements of 2 input vectors into half as many bits with saturation.
2164   // Shadow is propagated with the signed variant of the same intrinsic applied
2165   // to sext(Sa != zeroinitializer), sext(Sb != zeroinitializer).
2166   // EltSizeInBits is used only for x86mmx arguments.
2167   void handleVectorPackIntrinsic(IntrinsicInst &I, unsigned EltSizeInBits = 0) {
2168     assert(I.getNumArgOperands() == 2);
2169     bool isX86_MMX = I.getOperand(0)->getType()->isX86_MMXTy();
2170     IRBuilder<> IRB(&I);
2171     Value *S1 = getShadow(&I, 0);
2172     Value *S2 = getShadow(&I, 1);
2173     assert(isX86_MMX || S1->getType()->isVectorTy());
2174
2175     // SExt and ICmpNE below must apply to individual elements of input vectors.
2176     // In case of x86mmx arguments, cast them to appropriate vector types and
2177     // back.
2178     Type *T = isX86_MMX ? getMMXVectorTy(EltSizeInBits) : S1->getType();
2179     if (isX86_MMX) {
2180       S1 = IRB.CreateBitCast(S1, T);
2181       S2 = IRB.CreateBitCast(S2, T);
2182     }
2183     Value *S1_ext = IRB.CreateSExt(
2184         IRB.CreateICmpNE(S1, llvm::Constant::getNullValue(T)), T);
2185     Value *S2_ext = IRB.CreateSExt(
2186         IRB.CreateICmpNE(S2, llvm::Constant::getNullValue(T)), T);
2187     if (isX86_MMX) {
2188       Type *X86_MMXTy = Type::getX86_MMXTy(*MS.C);
2189       S1_ext = IRB.CreateBitCast(S1_ext, X86_MMXTy);
2190       S2_ext = IRB.CreateBitCast(S2_ext, X86_MMXTy);
2191     }
2192
2193     Function *ShadowFn = Intrinsic::getDeclaration(
2194         F.getParent(), getSignedPackIntrinsic(I.getIntrinsicID()));
2195
2196     Value *S =
2197         IRB.CreateCall(ShadowFn, {S1_ext, S2_ext}, "_msprop_vector_pack");
2198     if (isX86_MMX) S = IRB.CreateBitCast(S, getShadowTy(&I));
2199     setShadow(&I, S);
2200     setOriginForNaryOp(I);
2201   }
2202
2203   // \brief Instrument sum-of-absolute-differencies intrinsic.
2204   void handleVectorSadIntrinsic(IntrinsicInst &I) {
2205     const unsigned SignificantBitsPerResultElement = 16;
2206     bool isX86_MMX = I.getOperand(0)->getType()->isX86_MMXTy();
2207     Type *ResTy = isX86_MMX ? IntegerType::get(*MS.C, 64) : I.getType();
2208     unsigned ZeroBitsPerResultElement =
2209         ResTy->getScalarSizeInBits() - SignificantBitsPerResultElement;
2210
2211     IRBuilder<> IRB(&I);
2212     Value *S = IRB.CreateOr(getShadow(&I, 0), getShadow(&I, 1));
2213     S = IRB.CreateBitCast(S, ResTy);
2214     S = IRB.CreateSExt(IRB.CreateICmpNE(S, Constant::getNullValue(ResTy)),
2215                        ResTy);
2216     S = IRB.CreateLShr(S, ZeroBitsPerResultElement);
2217     S = IRB.CreateBitCast(S, getShadowTy(&I));
2218     setShadow(&I, S);
2219     setOriginForNaryOp(I);
2220   }
2221
2222   // \brief Instrument multiply-add intrinsic.
2223   void handleVectorPmaddIntrinsic(IntrinsicInst &I,
2224                                   unsigned EltSizeInBits = 0) {
2225     bool isX86_MMX = I.getOperand(0)->getType()->isX86_MMXTy();
2226     Type *ResTy = isX86_MMX ? getMMXVectorTy(EltSizeInBits * 2) : I.getType();
2227     IRBuilder<> IRB(&I);
2228     Value *S = IRB.CreateOr(getShadow(&I, 0), getShadow(&I, 1));
2229     S = IRB.CreateBitCast(S, ResTy);
2230     S = IRB.CreateSExt(IRB.CreateICmpNE(S, Constant::getNullValue(ResTy)),
2231                        ResTy);
2232     S = IRB.CreateBitCast(S, getShadowTy(&I));
2233     setShadow(&I, S);
2234     setOriginForNaryOp(I);
2235   }
2236
2237   void visitIntrinsicInst(IntrinsicInst &I) {
2238     switch (I.getIntrinsicID()) {
2239     case llvm::Intrinsic::bswap:
2240       handleBswap(I);
2241       break;
2242     case llvm::Intrinsic::x86_avx512_cvtsd2usi64:
2243     case llvm::Intrinsic::x86_avx512_cvtsd2usi:
2244     case llvm::Intrinsic::x86_avx512_cvtss2usi64:
2245     case llvm::Intrinsic::x86_avx512_cvtss2usi:
2246     case llvm::Intrinsic::x86_avx512_cvttss2usi64:
2247     case llvm::Intrinsic::x86_avx512_cvttss2usi:
2248     case llvm::Intrinsic::x86_avx512_cvttsd2usi64:
2249     case llvm::Intrinsic::x86_avx512_cvttsd2usi:
2250     case llvm::Intrinsic::x86_avx512_cvtusi2sd:
2251     case llvm::Intrinsic::x86_avx512_cvtusi2ss:
2252     case llvm::Intrinsic::x86_avx512_cvtusi642sd:
2253     case llvm::Intrinsic::x86_avx512_cvtusi642ss:
2254     case llvm::Intrinsic::x86_sse2_cvtsd2si64:
2255     case llvm::Intrinsic::x86_sse2_cvtsd2si:
2256     case llvm::Intrinsic::x86_sse2_cvtsd2ss:
2257     case llvm::Intrinsic::x86_sse2_cvtsi2sd:
2258     case llvm::Intrinsic::x86_sse2_cvtsi642sd:
2259     case llvm::Intrinsic::x86_sse2_cvtss2sd:
2260     case llvm::Intrinsic::x86_sse2_cvttsd2si64:
2261     case llvm::Intrinsic::x86_sse2_cvttsd2si:
2262     case llvm::Intrinsic::x86_sse_cvtsi2ss:
2263     case llvm::Intrinsic::x86_sse_cvtsi642ss:
2264     case llvm::Intrinsic::x86_sse_cvtss2si64:
2265     case llvm::Intrinsic::x86_sse_cvtss2si:
2266     case llvm::Intrinsic::x86_sse_cvttss2si64:
2267     case llvm::Intrinsic::x86_sse_cvttss2si:
2268       handleVectorConvertIntrinsic(I, 1);
2269       break;
2270     case llvm::Intrinsic::x86_sse2_cvtdq2pd:
2271     case llvm::Intrinsic::x86_sse2_cvtps2pd:
2272     case llvm::Intrinsic::x86_sse_cvtps2pi:
2273     case llvm::Intrinsic::x86_sse_cvttps2pi:
2274       handleVectorConvertIntrinsic(I, 2);
2275       break;
2276     case llvm::Intrinsic::x86_avx2_psll_w:
2277     case llvm::Intrinsic::x86_avx2_psll_d:
2278     case llvm::Intrinsic::x86_avx2_psll_q:
2279     case llvm::Intrinsic::x86_avx2_pslli_w:
2280     case llvm::Intrinsic::x86_avx2_pslli_d:
2281     case llvm::Intrinsic::x86_avx2_pslli_q:
2282     case llvm::Intrinsic::x86_avx2_psrl_w:
2283     case llvm::Intrinsic::x86_avx2_psrl_d:
2284     case llvm::Intrinsic::x86_avx2_psrl_q:
2285     case llvm::Intrinsic::x86_avx2_psra_w:
2286     case llvm::Intrinsic::x86_avx2_psra_d:
2287     case llvm::Intrinsic::x86_avx2_psrli_w:
2288     case llvm::Intrinsic::x86_avx2_psrli_d:
2289     case llvm::Intrinsic::x86_avx2_psrli_q:
2290     case llvm::Intrinsic::x86_avx2_psrai_w:
2291     case llvm::Intrinsic::x86_avx2_psrai_d:
2292     case llvm::Intrinsic::x86_sse2_psll_w:
2293     case llvm::Intrinsic::x86_sse2_psll_d:
2294     case llvm::Intrinsic::x86_sse2_psll_q:
2295     case llvm::Intrinsic::x86_sse2_pslli_w:
2296     case llvm::Intrinsic::x86_sse2_pslli_d:
2297     case llvm::Intrinsic::x86_sse2_pslli_q:
2298     case llvm::Intrinsic::x86_sse2_psrl_w:
2299     case llvm::Intrinsic::x86_sse2_psrl_d:
2300     case llvm::Intrinsic::x86_sse2_psrl_q:
2301     case llvm::Intrinsic::x86_sse2_psra_w:
2302     case llvm::Intrinsic::x86_sse2_psra_d:
2303     case llvm::Intrinsic::x86_sse2_psrli_w:
2304     case llvm::Intrinsic::x86_sse2_psrli_d:
2305     case llvm::Intrinsic::x86_sse2_psrli_q:
2306     case llvm::Intrinsic::x86_sse2_psrai_w:
2307     case llvm::Intrinsic::x86_sse2_psrai_d:
2308     case llvm::Intrinsic::x86_mmx_psll_w:
2309     case llvm::Intrinsic::x86_mmx_psll_d:
2310     case llvm::Intrinsic::x86_mmx_psll_q:
2311     case llvm::Intrinsic::x86_mmx_pslli_w:
2312     case llvm::Intrinsic::x86_mmx_pslli_d:
2313     case llvm::Intrinsic::x86_mmx_pslli_q:
2314     case llvm::Intrinsic::x86_mmx_psrl_w:
2315     case llvm::Intrinsic::x86_mmx_psrl_d:
2316     case llvm::Intrinsic::x86_mmx_psrl_q:
2317     case llvm::Intrinsic::x86_mmx_psra_w:
2318     case llvm::Intrinsic::x86_mmx_psra_d:
2319     case llvm::Intrinsic::x86_mmx_psrli_w:
2320     case llvm::Intrinsic::x86_mmx_psrli_d:
2321     case llvm::Intrinsic::x86_mmx_psrli_q:
2322     case llvm::Intrinsic::x86_mmx_psrai_w:
2323     case llvm::Intrinsic::x86_mmx_psrai_d:
2324       handleVectorShiftIntrinsic(I, /* Variable */ false);
2325       break;
2326     case llvm::Intrinsic::x86_avx2_psllv_d:
2327     case llvm::Intrinsic::x86_avx2_psllv_d_256:
2328     case llvm::Intrinsic::x86_avx2_psllv_q:
2329     case llvm::Intrinsic::x86_avx2_psllv_q_256:
2330     case llvm::Intrinsic::x86_avx2_psrlv_d:
2331     case llvm::Intrinsic::x86_avx2_psrlv_d_256:
2332     case llvm::Intrinsic::x86_avx2_psrlv_q:
2333     case llvm::Intrinsic::x86_avx2_psrlv_q_256:
2334     case llvm::Intrinsic::x86_avx2_psrav_d:
2335     case llvm::Intrinsic::x86_avx2_psrav_d_256:
2336       handleVectorShiftIntrinsic(I, /* Variable */ true);
2337       break;
2338
2339     case llvm::Intrinsic::x86_sse2_packsswb_128:
2340     case llvm::Intrinsic::x86_sse2_packssdw_128:
2341     case llvm::Intrinsic::x86_sse2_packuswb_128:
2342     case llvm::Intrinsic::x86_sse41_packusdw:
2343     case llvm::Intrinsic::x86_avx2_packsswb:
2344     case llvm::Intrinsic::x86_avx2_packssdw:
2345     case llvm::Intrinsic::x86_avx2_packuswb:
2346     case llvm::Intrinsic::x86_avx2_packusdw:
2347       handleVectorPackIntrinsic(I);
2348       break;
2349
2350     case llvm::Intrinsic::x86_mmx_packsswb:
2351     case llvm::Intrinsic::x86_mmx_packuswb:
2352       handleVectorPackIntrinsic(I, 16);
2353       break;
2354
2355     case llvm::Intrinsic::x86_mmx_packssdw:
2356       handleVectorPackIntrinsic(I, 32);
2357       break;
2358
2359     case llvm::Intrinsic::x86_mmx_psad_bw:
2360     case llvm::Intrinsic::x86_sse2_psad_bw:
2361     case llvm::Intrinsic::x86_avx2_psad_bw:
2362       handleVectorSadIntrinsic(I);
2363       break;
2364
2365     case llvm::Intrinsic::x86_sse2_pmadd_wd:
2366     case llvm::Intrinsic::x86_avx2_pmadd_wd:
2367     case llvm::Intrinsic::x86_ssse3_pmadd_ub_sw_128:
2368     case llvm::Intrinsic::x86_avx2_pmadd_ub_sw:
2369       handleVectorPmaddIntrinsic(I);
2370       break;
2371
2372     case llvm::Intrinsic::x86_ssse3_pmadd_ub_sw:
2373       handleVectorPmaddIntrinsic(I, 8);
2374       break;
2375
2376     case llvm::Intrinsic::x86_mmx_pmadd_wd:
2377       handleVectorPmaddIntrinsic(I, 16);
2378       break;
2379
2380     default:
2381       if (!handleUnknownIntrinsic(I))
2382         visitInstruction(I);
2383       break;
2384     }
2385   }
2386
2387   void visitCallSite(CallSite CS) {
2388     Instruction &I = *CS.getInstruction();
2389     assert((CS.isCall() || CS.isInvoke()) && "Unknown type of CallSite");
2390     if (CS.isCall()) {
2391       CallInst *Call = cast<CallInst>(&I);
2392
2393       // For inline asm, do the usual thing: check argument shadow and mark all
2394       // outputs as clean. Note that any side effects of the inline asm that are
2395       // not immediately visible in its constraints are not handled.
2396       if (Call->isInlineAsm()) {
2397         visitInstruction(I);
2398         return;
2399       }
2400
2401       assert(!isa<IntrinsicInst>(&I) && "intrinsics are handled elsewhere");
2402
2403       // We are going to insert code that relies on the fact that the callee
2404       // will become a non-readonly function after it is instrumented by us. To
2405       // prevent this code from being optimized out, mark that function
2406       // non-readonly in advance.
2407       if (Function *Func = Call->getCalledFunction()) {
2408         // Clear out readonly/readnone attributes.
2409         AttrBuilder B;
2410         B.addAttribute(Attribute::ReadOnly)
2411           .addAttribute(Attribute::ReadNone);
2412         Func->removeAttributes(AttributeSet::FunctionIndex,
2413                                AttributeSet::get(Func->getContext(),
2414                                                  AttributeSet::FunctionIndex,
2415                                                  B));
2416       }
2417     }
2418     IRBuilder<> IRB(&I);
2419
2420     unsigned ArgOffset = 0;
2421     DEBUG(dbgs() << "  CallSite: " << I << "\n");
2422     for (CallSite::arg_iterator ArgIt = CS.arg_begin(), End = CS.arg_end();
2423          ArgIt != End; ++ArgIt) {
2424       Value *A = *ArgIt;
2425       unsigned i = ArgIt - CS.arg_begin();
2426       if (!A->getType()->isSized()) {
2427         DEBUG(dbgs() << "Arg " << i << " is not sized: " << I << "\n");
2428         continue;
2429       }
2430       unsigned Size = 0;
2431       Value *Store = nullptr;
2432       // Compute the Shadow for arg even if it is ByVal, because
2433       // in that case getShadow() will copy the actual arg shadow to
2434       // __msan_param_tls.
2435       Value *ArgShadow = getShadow(A);
2436       Value *ArgShadowBase = getShadowPtrForArgument(A, IRB, ArgOffset);
2437       DEBUG(dbgs() << "  Arg#" << i << ": " << *A <<
2438             " Shadow: " << *ArgShadow << "\n");
2439       bool ArgIsInitialized = false;
2440       const DataLayout &DL = F.getParent()->getDataLayout();
2441       if (CS.paramHasAttr(i + 1, Attribute::ByVal)) {
2442         assert(A->getType()->isPointerTy() &&
2443                "ByVal argument is not a pointer!");
2444         Size = DL.getTypeAllocSize(A->getType()->getPointerElementType());
2445         if (ArgOffset + Size > kParamTLSSize) break;
2446         unsigned ParamAlignment = CS.getParamAlignment(i + 1);
2447         unsigned Alignment = std::min(ParamAlignment, kShadowTLSAlignment);
2448         Store = IRB.CreateMemCpy(ArgShadowBase,
2449                                  getShadowPtr(A, Type::getInt8Ty(*MS.C), IRB),
2450                                  Size, Alignment);
2451       } else {
2452         Size = DL.getTypeAllocSize(A->getType());
2453         if (ArgOffset + Size > kParamTLSSize) break;
2454         Store = IRB.CreateAlignedStore(ArgShadow, ArgShadowBase,
2455                                        kShadowTLSAlignment);
2456         Constant *Cst = dyn_cast<Constant>(ArgShadow);
2457         if (Cst && Cst->isNullValue()) ArgIsInitialized = true;
2458       }
2459       if (MS.TrackOrigins && !ArgIsInitialized)
2460         IRB.CreateStore(getOrigin(A),
2461                         getOriginPtrForArgument(A, IRB, ArgOffset));
2462       (void)Store;
2463       assert(Size != 0 && Store != nullptr);
2464       DEBUG(dbgs() << "  Param:" << *Store << "\n");
2465       ArgOffset += RoundUpToAlignment(Size, 8);
2466     }
2467     DEBUG(dbgs() << "  done with call args\n");
2468
2469     FunctionType *FT =
2470       cast<FunctionType>(CS.getCalledValue()->getType()->getContainedType(0));
2471     if (FT->isVarArg()) {
2472       VAHelper->visitCallSite(CS, IRB);
2473     }
2474
2475     // Now, get the shadow for the RetVal.
2476     if (!I.getType()->isSized()) return;
2477     IRBuilder<> IRBBefore(&I);
2478     // Until we have full dynamic coverage, make sure the retval shadow is 0.
2479     Value *Base = getShadowPtrForRetval(&I, IRBBefore);
2480     IRBBefore.CreateAlignedStore(getCleanShadow(&I), Base, kShadowTLSAlignment);
2481     Instruction *NextInsn = nullptr;
2482     if (CS.isCall()) {
2483       NextInsn = I.getNextNode();
2484     } else {
2485       BasicBlock *NormalDest = cast<InvokeInst>(&I)->getNormalDest();
2486       if (!NormalDest->getSinglePredecessor()) {
2487         // FIXME: this case is tricky, so we are just conservative here.
2488         // Perhaps we need to split the edge between this BB and NormalDest,
2489         // but a naive attempt to use SplitEdge leads to a crash.
2490         setShadow(&I, getCleanShadow(&I));
2491         setOrigin(&I, getCleanOrigin());
2492         return;
2493       }
2494       NextInsn = NormalDest->getFirstInsertionPt();
2495       assert(NextInsn &&
2496              "Could not find insertion point for retval shadow load");
2497     }
2498     IRBuilder<> IRBAfter(NextInsn);
2499     Value *RetvalShadow =
2500       IRBAfter.CreateAlignedLoad(getShadowPtrForRetval(&I, IRBAfter),
2501                                  kShadowTLSAlignment, "_msret");
2502     setShadow(&I, RetvalShadow);
2503     if (MS.TrackOrigins)
2504       setOrigin(&I, IRBAfter.CreateLoad(getOriginPtrForRetval(IRBAfter)));
2505   }
2506
2507   void visitReturnInst(ReturnInst &I) {
2508     IRBuilder<> IRB(&I);
2509     Value *RetVal = I.getReturnValue();
2510     if (!RetVal) return;
2511     Value *ShadowPtr = getShadowPtrForRetval(RetVal, IRB);
2512     if (CheckReturnValue) {
2513       insertShadowCheck(RetVal, &I);
2514       Value *Shadow = getCleanShadow(RetVal);
2515       IRB.CreateAlignedStore(Shadow, ShadowPtr, kShadowTLSAlignment);
2516     } else {
2517       Value *Shadow = getShadow(RetVal);
2518       IRB.CreateAlignedStore(Shadow, ShadowPtr, kShadowTLSAlignment);
2519       // FIXME: make it conditional if ClStoreCleanOrigin==0
2520       if (MS.TrackOrigins)
2521         IRB.CreateStore(getOrigin(RetVal), getOriginPtrForRetval(IRB));
2522     }
2523   }
2524
2525   void visitPHINode(PHINode &I) {
2526     IRBuilder<> IRB(&I);
2527     if (!PropagateShadow) {
2528       setShadow(&I, getCleanShadow(&I));
2529       setOrigin(&I, getCleanOrigin());
2530       return;
2531     }
2532
2533     ShadowPHINodes.push_back(&I);
2534     setShadow(&I, IRB.CreatePHI(getShadowTy(&I), I.getNumIncomingValues(),
2535                                 "_msphi_s"));
2536     if (MS.TrackOrigins)
2537       setOrigin(&I, IRB.CreatePHI(MS.OriginTy, I.getNumIncomingValues(),
2538                                   "_msphi_o"));
2539   }
2540
2541   void visitAllocaInst(AllocaInst &I) {
2542     setShadow(&I, getCleanShadow(&I));
2543     setOrigin(&I, getCleanOrigin());
2544     IRBuilder<> IRB(I.getNextNode());
2545     const DataLayout &DL = F.getParent()->getDataLayout();
2546     uint64_t Size = DL.getTypeAllocSize(I.getAllocatedType());
2547     if (PoisonStack && ClPoisonStackWithCall) {
2548       IRB.CreateCall(MS.MsanPoisonStackFn,
2549                      {IRB.CreatePointerCast(&I, IRB.getInt8PtrTy()),
2550                       ConstantInt::get(MS.IntptrTy, Size)});
2551     } else {
2552       Value *ShadowBase = getShadowPtr(&I, Type::getInt8PtrTy(*MS.C), IRB);
2553       Value *PoisonValue = IRB.getInt8(PoisonStack ? ClPoisonStackPattern : 0);
2554       IRB.CreateMemSet(ShadowBase, PoisonValue, Size, I.getAlignment());
2555     }
2556
2557     if (PoisonStack && MS.TrackOrigins) {
2558       SmallString<2048> StackDescriptionStorage;
2559       raw_svector_ostream StackDescription(StackDescriptionStorage);
2560       // We create a string with a description of the stack allocation and
2561       // pass it into __msan_set_alloca_origin.
2562       // It will be printed by the run-time if stack-originated UMR is found.
2563       // The first 4 bytes of the string are set to '----' and will be replaced
2564       // by __msan_va_arg_overflow_size_tls at the first call.
2565       StackDescription << "----" << I.getName() << "@" << F.getName();
2566       Value *Descr =
2567           createPrivateNonConstGlobalForString(*F.getParent(),
2568                                                StackDescription.str());
2569
2570       IRB.CreateCall(MS.MsanSetAllocaOrigin4Fn,
2571                      {IRB.CreatePointerCast(&I, IRB.getInt8PtrTy()),
2572                       ConstantInt::get(MS.IntptrTy, Size),
2573                       IRB.CreatePointerCast(Descr, IRB.getInt8PtrTy()),
2574                       IRB.CreatePointerCast(&F, MS.IntptrTy)});
2575     }
2576   }
2577
2578   void visitSelectInst(SelectInst& I) {
2579     IRBuilder<> IRB(&I);
2580     // a = select b, c, d
2581     Value *B = I.getCondition();
2582     Value *C = I.getTrueValue();
2583     Value *D = I.getFalseValue();
2584     Value *Sb = getShadow(B);
2585     Value *Sc = getShadow(C);
2586     Value *Sd = getShadow(D);
2587
2588     // Result shadow if condition shadow is 0.
2589     Value *Sa0 = IRB.CreateSelect(B, Sc, Sd);
2590     Value *Sa1;
2591     if (I.getType()->isAggregateType()) {
2592       // To avoid "sign extending" i1 to an arbitrary aggregate type, we just do
2593       // an extra "select". This results in much more compact IR.
2594       // Sa = select Sb, poisoned, (select b, Sc, Sd)
2595       Sa1 = getPoisonedShadow(getShadowTy(I.getType()));
2596     } else {
2597       // Sa = select Sb, [ (c^d) | Sc | Sd ], [ b ? Sc : Sd ]
2598       // If Sb (condition is poisoned), look for bits in c and d that are equal
2599       // and both unpoisoned.
2600       // If !Sb (condition is unpoisoned), simply pick one of Sc and Sd.
2601
2602       // Cast arguments to shadow-compatible type.
2603       C = CreateAppToShadowCast(IRB, C);
2604       D = CreateAppToShadowCast(IRB, D);
2605
2606       // Result shadow if condition shadow is 1.
2607       Sa1 = IRB.CreateOr(IRB.CreateXor(C, D), IRB.CreateOr(Sc, Sd));
2608     }
2609     Value *Sa = IRB.CreateSelect(Sb, Sa1, Sa0, "_msprop_select");
2610     setShadow(&I, Sa);
2611     if (MS.TrackOrigins) {
2612       // Origins are always i32, so any vector conditions must be flattened.
2613       // FIXME: consider tracking vector origins for app vectors?
2614       if (B->getType()->isVectorTy()) {
2615         Type *FlatTy = getShadowTyNoVec(B->getType());
2616         B = IRB.CreateICmpNE(IRB.CreateBitCast(B, FlatTy),
2617                                 ConstantInt::getNullValue(FlatTy));
2618         Sb = IRB.CreateICmpNE(IRB.CreateBitCast(Sb, FlatTy),
2619                                       ConstantInt::getNullValue(FlatTy));
2620       }
2621       // a = select b, c, d
2622       // Oa = Sb ? Ob : (b ? Oc : Od)
2623       setOrigin(
2624           &I, IRB.CreateSelect(Sb, getOrigin(I.getCondition()),
2625                                IRB.CreateSelect(B, getOrigin(I.getTrueValue()),
2626                                                 getOrigin(I.getFalseValue()))));
2627     }
2628   }
2629
2630   void visitLandingPadInst(LandingPadInst &I) {
2631     // Do nothing.
2632     // See http://code.google.com/p/memory-sanitizer/issues/detail?id=1
2633     setShadow(&I, getCleanShadow(&I));
2634     setOrigin(&I, getCleanOrigin());
2635   }
2636
2637   void visitGetElementPtrInst(GetElementPtrInst &I) {
2638     handleShadowOr(I);
2639   }
2640
2641   void visitExtractValueInst(ExtractValueInst &I) {
2642     IRBuilder<> IRB(&I);
2643     Value *Agg = I.getAggregateOperand();
2644     DEBUG(dbgs() << "ExtractValue:  " << I << "\n");
2645     Value *AggShadow = getShadow(Agg);
2646     DEBUG(dbgs() << "   AggShadow:  " << *AggShadow << "\n");
2647     Value *ResShadow = IRB.CreateExtractValue(AggShadow, I.getIndices());
2648     DEBUG(dbgs() << "   ResShadow:  " << *ResShadow << "\n");
2649     setShadow(&I, ResShadow);
2650     setOriginForNaryOp(I);
2651   }
2652
2653   void visitInsertValueInst(InsertValueInst &I) {
2654     IRBuilder<> IRB(&I);
2655     DEBUG(dbgs() << "InsertValue:  " << I << "\n");
2656     Value *AggShadow = getShadow(I.getAggregateOperand());
2657     Value *InsShadow = getShadow(I.getInsertedValueOperand());
2658     DEBUG(dbgs() << "   AggShadow:  " << *AggShadow << "\n");
2659     DEBUG(dbgs() << "   InsShadow:  " << *InsShadow << "\n");
2660     Value *Res = IRB.CreateInsertValue(AggShadow, InsShadow, I.getIndices());
2661     DEBUG(dbgs() << "   Res:        " << *Res << "\n");
2662     setShadow(&I, Res);
2663     setOriginForNaryOp(I);
2664   }
2665
2666   void dumpInst(Instruction &I) {
2667     if (CallInst *CI = dyn_cast<CallInst>(&I)) {
2668       errs() << "ZZZ call " << CI->getCalledFunction()->getName() << "\n";
2669     } else {
2670       errs() << "ZZZ " << I.getOpcodeName() << "\n";
2671     }
2672     errs() << "QQQ " << I << "\n";
2673   }
2674
2675   void visitResumeInst(ResumeInst &I) {
2676     DEBUG(dbgs() << "Resume: " << I << "\n");
2677     // Nothing to do here.
2678   }
2679
2680   void visitInstruction(Instruction &I) {
2681     // Everything else: stop propagating and check for poisoned shadow.
2682     if (ClDumpStrictInstructions)
2683       dumpInst(I);
2684     DEBUG(dbgs() << "DEFAULT: " << I << "\n");
2685     for (size_t i = 0, n = I.getNumOperands(); i < n; i++)
2686       insertShadowCheck(I.getOperand(i), &I);
2687     setShadow(&I, getCleanShadow(&I));
2688     setOrigin(&I, getCleanOrigin());
2689   }
2690 };
2691
2692 /// \brief AMD64-specific implementation of VarArgHelper.
2693 struct VarArgAMD64Helper : public VarArgHelper {
2694   // An unfortunate workaround for asymmetric lowering of va_arg stuff.
2695   // See a comment in visitCallSite for more details.
2696   static const unsigned AMD64GpEndOffset = 48;  // AMD64 ABI Draft 0.99.6 p3.5.7
2697   static const unsigned AMD64FpEndOffset = 176;
2698
2699   Function &F;
2700   MemorySanitizer &MS;
2701   MemorySanitizerVisitor &MSV;
2702   Value *VAArgTLSCopy;
2703   Value *VAArgOverflowSize;
2704
2705   SmallVector<CallInst*, 16> VAStartInstrumentationList;
2706
2707   VarArgAMD64Helper(Function &F, MemorySanitizer &MS,
2708                     MemorySanitizerVisitor &MSV)
2709     : F(F), MS(MS), MSV(MSV), VAArgTLSCopy(nullptr),
2710       VAArgOverflowSize(nullptr) {}
2711
2712   enum ArgKind { AK_GeneralPurpose, AK_FloatingPoint, AK_Memory };
2713
2714   ArgKind classifyArgument(Value* arg) {
2715     // A very rough approximation of X86_64 argument classification rules.
2716     Type *T = arg->getType();
2717     if (T->isFPOrFPVectorTy() || T->isX86_MMXTy())
2718       return AK_FloatingPoint;
2719     if (T->isIntegerTy() && T->getPrimitiveSizeInBits() <= 64)
2720       return AK_GeneralPurpose;
2721     if (T->isPointerTy())
2722       return AK_GeneralPurpose;
2723     return AK_Memory;
2724   }
2725
2726   // For VarArg functions, store the argument shadow in an ABI-specific format
2727   // that corresponds to va_list layout.
2728   // We do this because Clang lowers va_arg in the frontend, and this pass
2729   // only sees the low level code that deals with va_list internals.
2730   // A much easier alternative (provided that Clang emits va_arg instructions)
2731   // would have been to associate each live instance of va_list with a copy of
2732   // MSanParamTLS, and extract shadow on va_arg() call in the argument list
2733   // order.
2734   void visitCallSite(CallSite &CS, IRBuilder<> &IRB) override {
2735     unsigned GpOffset = 0;
2736     unsigned FpOffset = AMD64GpEndOffset;
2737     unsigned OverflowOffset = AMD64FpEndOffset;
2738     const DataLayout &DL = F.getParent()->getDataLayout();
2739     for (CallSite::arg_iterator ArgIt = CS.arg_begin(), End = CS.arg_end();
2740          ArgIt != End; ++ArgIt) {
2741       Value *A = *ArgIt;
2742       unsigned ArgNo = CS.getArgumentNo(ArgIt);
2743       bool IsByVal = CS.paramHasAttr(ArgNo + 1, Attribute::ByVal);
2744       if (IsByVal) {
2745         // ByVal arguments always go to the overflow area.
2746         assert(A->getType()->isPointerTy());
2747         Type *RealTy = A->getType()->getPointerElementType();
2748         uint64_t ArgSize = DL.getTypeAllocSize(RealTy);
2749         Value *Base = getShadowPtrForVAArgument(RealTy, IRB, OverflowOffset);
2750         OverflowOffset += RoundUpToAlignment(ArgSize, 8);
2751         IRB.CreateMemCpy(Base, MSV.getShadowPtr(A, IRB.getInt8Ty(), IRB),
2752                          ArgSize, kShadowTLSAlignment);
2753       } else {
2754         ArgKind AK = classifyArgument(A);
2755         if (AK == AK_GeneralPurpose && GpOffset >= AMD64GpEndOffset)
2756           AK = AK_Memory;
2757         if (AK == AK_FloatingPoint && FpOffset >= AMD64FpEndOffset)
2758           AK = AK_Memory;
2759         Value *Base;
2760         switch (AK) {
2761           case AK_GeneralPurpose:
2762             Base = getShadowPtrForVAArgument(A->getType(), IRB, GpOffset);
2763             GpOffset += 8;
2764             break;
2765           case AK_FloatingPoint:
2766             Base = getShadowPtrForVAArgument(A->getType(), IRB, FpOffset);
2767             FpOffset += 16;
2768             break;
2769           case AK_Memory:
2770             uint64_t ArgSize = DL.getTypeAllocSize(A->getType());
2771             Base = getShadowPtrForVAArgument(A->getType(), IRB, OverflowOffset);
2772             OverflowOffset += RoundUpToAlignment(ArgSize, 8);
2773         }
2774         IRB.CreateAlignedStore(MSV.getShadow(A), Base, kShadowTLSAlignment);
2775       }
2776     }
2777     Constant *OverflowSize =
2778       ConstantInt::get(IRB.getInt64Ty(), OverflowOffset - AMD64FpEndOffset);
2779     IRB.CreateStore(OverflowSize, MS.VAArgOverflowSizeTLS);
2780   }
2781
2782   /// \brief Compute the shadow address for a given va_arg.
2783   Value *getShadowPtrForVAArgument(Type *Ty, IRBuilder<> &IRB,
2784                                    int ArgOffset) {
2785     Value *Base = IRB.CreatePointerCast(MS.VAArgTLS, MS.IntptrTy);
2786     Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset));
2787     return IRB.CreateIntToPtr(Base, PointerType::get(MSV.getShadowTy(Ty), 0),
2788                               "_msarg");
2789   }
2790
2791   void visitVAStartInst(VAStartInst &I) override {
2792     IRBuilder<> IRB(&I);
2793     VAStartInstrumentationList.push_back(&I);
2794     Value *VAListTag = I.getArgOperand(0);
2795     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
2796
2797     // Unpoison the whole __va_list_tag.
2798     // FIXME: magic ABI constants.
2799     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
2800                      /* size */24, /* alignment */8, false);
2801   }
2802
2803   void visitVACopyInst(VACopyInst &I) override {
2804     IRBuilder<> IRB(&I);
2805     Value *VAListTag = I.getArgOperand(0);
2806     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
2807
2808     // Unpoison the whole __va_list_tag.
2809     // FIXME: magic ABI constants.
2810     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
2811                      /* size */24, /* alignment */8, false);
2812   }
2813
2814   void finalizeInstrumentation() override {
2815     assert(!VAArgOverflowSize && !VAArgTLSCopy &&
2816            "finalizeInstrumentation called twice");
2817     if (!VAStartInstrumentationList.empty()) {
2818       // If there is a va_start in this function, make a backup copy of
2819       // va_arg_tls somewhere in the function entry block.
2820       IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
2821       VAArgOverflowSize = IRB.CreateLoad(MS.VAArgOverflowSizeTLS);
2822       Value *CopySize =
2823         IRB.CreateAdd(ConstantInt::get(MS.IntptrTy, AMD64FpEndOffset),
2824                       VAArgOverflowSize);
2825       VAArgTLSCopy = IRB.CreateAlloca(Type::getInt8Ty(*MS.C), CopySize);
2826       IRB.CreateMemCpy(VAArgTLSCopy, MS.VAArgTLS, CopySize, 8);
2827     }
2828
2829     // Instrument va_start.
2830     // Copy va_list shadow from the backup copy of the TLS contents.
2831     for (size_t i = 0, n = VAStartInstrumentationList.size(); i < n; i++) {
2832       CallInst *OrigInst = VAStartInstrumentationList[i];
2833       IRBuilder<> IRB(OrigInst->getNextNode());
2834       Value *VAListTag = OrigInst->getArgOperand(0);
2835
2836       Value *RegSaveAreaPtrPtr =
2837         IRB.CreateIntToPtr(
2838           IRB.CreateAdd(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy),
2839                         ConstantInt::get(MS.IntptrTy, 16)),
2840           Type::getInt64PtrTy(*MS.C));
2841       Value *RegSaveAreaPtr = IRB.CreateLoad(RegSaveAreaPtrPtr);
2842       Value *RegSaveAreaShadowPtr =
2843         MSV.getShadowPtr(RegSaveAreaPtr, IRB.getInt8Ty(), IRB);
2844       IRB.CreateMemCpy(RegSaveAreaShadowPtr, VAArgTLSCopy,
2845                        AMD64FpEndOffset, 16);
2846
2847       Value *OverflowArgAreaPtrPtr =
2848         IRB.CreateIntToPtr(
2849           IRB.CreateAdd(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy),
2850                         ConstantInt::get(MS.IntptrTy, 8)),
2851           Type::getInt64PtrTy(*MS.C));
2852       Value *OverflowArgAreaPtr = IRB.CreateLoad(OverflowArgAreaPtrPtr);
2853       Value *OverflowArgAreaShadowPtr =
2854         MSV.getShadowPtr(OverflowArgAreaPtr, IRB.getInt8Ty(), IRB);
2855       Value *SrcPtr = IRB.CreateConstGEP1_32(IRB.getInt8Ty(), VAArgTLSCopy,
2856                                              AMD64FpEndOffset);
2857       IRB.CreateMemCpy(OverflowArgAreaShadowPtr, SrcPtr, VAArgOverflowSize, 16);
2858     }
2859   }
2860 };
2861
2862 /// \brief MIPS64-specific implementation of VarArgHelper.
2863 struct VarArgMIPS64Helper : public VarArgHelper {
2864   Function &F;
2865   MemorySanitizer &MS;
2866   MemorySanitizerVisitor &MSV;
2867   Value *VAArgTLSCopy;
2868   Value *VAArgSize;
2869
2870   SmallVector<CallInst*, 16> VAStartInstrumentationList;
2871
2872   VarArgMIPS64Helper(Function &F, MemorySanitizer &MS,
2873                     MemorySanitizerVisitor &MSV)
2874     : F(F), MS(MS), MSV(MSV), VAArgTLSCopy(nullptr),
2875       VAArgSize(nullptr) {}
2876
2877   void visitCallSite(CallSite &CS, IRBuilder<> &IRB) override {
2878     unsigned VAArgOffset = 0;
2879     const DataLayout &DL = F.getParent()->getDataLayout();
2880     for (CallSite::arg_iterator ArgIt = CS.arg_begin() + 1, End = CS.arg_end();
2881          ArgIt != End; ++ArgIt) {
2882       Value *A = *ArgIt;
2883       Value *Base;
2884       uint64_t ArgSize = DL.getTypeAllocSize(A->getType());
2885 #if defined(__MIPSEB__) || defined(MIPSEB)
2886       // Adjusting the shadow for argument with size < 8 to match the placement
2887       // of bits in big endian system
2888       if (ArgSize < 8)
2889         VAArgOffset += (8 - ArgSize);
2890 #endif
2891       Base = getShadowPtrForVAArgument(A->getType(), IRB, VAArgOffset);
2892       VAArgOffset += ArgSize;
2893       VAArgOffset = RoundUpToAlignment(VAArgOffset, 8);
2894       IRB.CreateAlignedStore(MSV.getShadow(A), Base, kShadowTLSAlignment);
2895     }
2896
2897     Constant *TotalVAArgSize = ConstantInt::get(IRB.getInt64Ty(), VAArgOffset);
2898     // Here using VAArgOverflowSizeTLS as VAArgSizeTLS to avoid creation of
2899     // a new class member i.e. it is the total size of all VarArgs.
2900     IRB.CreateStore(TotalVAArgSize, MS.VAArgOverflowSizeTLS);
2901   }
2902
2903   /// \brief Compute the shadow address for a given va_arg.
2904   Value *getShadowPtrForVAArgument(Type *Ty, IRBuilder<> &IRB,
2905                                    int ArgOffset) {
2906     Value *Base = IRB.CreatePointerCast(MS.VAArgTLS, MS.IntptrTy);
2907     Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset));
2908     return IRB.CreateIntToPtr(Base, PointerType::get(MSV.getShadowTy(Ty), 0),
2909                               "_msarg");
2910   }
2911
2912   void visitVAStartInst(VAStartInst &I) override {
2913     IRBuilder<> IRB(&I);
2914     VAStartInstrumentationList.push_back(&I);
2915     Value *VAListTag = I.getArgOperand(0);
2916     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
2917     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
2918                      /* size */8, /* alignment */8, false);
2919   }
2920
2921   void visitVACopyInst(VACopyInst &I) override {
2922     IRBuilder<> IRB(&I);
2923     Value *VAListTag = I.getArgOperand(0);
2924     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
2925     // Unpoison the whole __va_list_tag.
2926     // FIXME: magic ABI constants.
2927     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
2928                      /* size */8, /* alignment */8, false);
2929   }
2930
2931   void finalizeInstrumentation() override {
2932     assert(!VAArgSize && !VAArgTLSCopy &&
2933            "finalizeInstrumentation called twice");
2934     IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
2935     VAArgSize = IRB.CreateLoad(MS.VAArgOverflowSizeTLS);
2936     Value *CopySize = IRB.CreateAdd(ConstantInt::get(MS.IntptrTy, 0),
2937                                     VAArgSize);
2938
2939     if (!VAStartInstrumentationList.empty()) {
2940       // If there is a va_start in this function, make a backup copy of
2941       // va_arg_tls somewhere in the function entry block.
2942       VAArgTLSCopy = IRB.CreateAlloca(Type::getInt8Ty(*MS.C), CopySize);
2943       IRB.CreateMemCpy(VAArgTLSCopy, MS.VAArgTLS, CopySize, 8);
2944     }
2945
2946     // Instrument va_start.
2947     // Copy va_list shadow from the backup copy of the TLS contents.
2948     for (size_t i = 0, n = VAStartInstrumentationList.size(); i < n; i++) {
2949       CallInst *OrigInst = VAStartInstrumentationList[i];
2950       IRBuilder<> IRB(OrigInst->getNextNode());
2951       Value *VAListTag = OrigInst->getArgOperand(0);
2952       Value *RegSaveAreaPtrPtr =
2953         IRB.CreateIntToPtr(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy),
2954                         Type::getInt64PtrTy(*MS.C));
2955       Value *RegSaveAreaPtr = IRB.CreateLoad(RegSaveAreaPtrPtr);
2956       Value *RegSaveAreaShadowPtr =
2957       MSV.getShadowPtr(RegSaveAreaPtr, IRB.getInt8Ty(), IRB);
2958       IRB.CreateMemCpy(RegSaveAreaShadowPtr, VAArgTLSCopy, CopySize, 8);
2959     }
2960   }
2961 };
2962
2963 /// \brief A no-op implementation of VarArgHelper.
2964 struct VarArgNoOpHelper : public VarArgHelper {
2965   VarArgNoOpHelper(Function &F, MemorySanitizer &MS,
2966                    MemorySanitizerVisitor &MSV) {}
2967
2968   void visitCallSite(CallSite &CS, IRBuilder<> &IRB) override {}
2969
2970   void visitVAStartInst(VAStartInst &I) override {}
2971
2972   void visitVACopyInst(VACopyInst &I) override {}
2973
2974   void finalizeInstrumentation() override {}
2975 };
2976
2977 VarArgHelper *CreateVarArgHelper(Function &Func, MemorySanitizer &Msan,
2978                                  MemorySanitizerVisitor &Visitor) {
2979   // VarArg handling is only implemented on AMD64. False positives are possible
2980   // on other platforms.
2981   llvm::Triple TargetTriple(Func.getParent()->getTargetTriple());
2982   if (TargetTriple.getArch() == llvm::Triple::x86_64)
2983     return new VarArgAMD64Helper(Func, Msan, Visitor);
2984   else if (TargetTriple.getArch() == llvm::Triple::mips64 ||
2985            TargetTriple.getArch() == llvm::Triple::mips64el)
2986     return new VarArgMIPS64Helper(Func, Msan, Visitor);
2987   else
2988     return new VarArgNoOpHelper(Func, Msan, Visitor);
2989 }
2990
2991 }  // namespace
2992
2993 bool MemorySanitizer::runOnFunction(Function &F) {
2994   if (&F == MsanCtorFunction)
2995     return false;
2996   MemorySanitizerVisitor Visitor(F, *this);
2997
2998   // Clear out readonly/readnone attributes.
2999   AttrBuilder B;
3000   B.addAttribute(Attribute::ReadOnly)
3001     .addAttribute(Attribute::ReadNone);
3002   F.removeAttributes(AttributeSet::FunctionIndex,
3003                      AttributeSet::get(F.getContext(),
3004                                        AttributeSet::FunctionIndex, B));
3005
3006   return Visitor.runOnFunction();
3007 }