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