LLVM  mainline
MemorySanitizer.cpp
Go to the documentation of this file.
00001 //===-- MemorySanitizer.cpp - detector of uninitialized reads -------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 /// \file
00010 /// This file is a part of MemorySanitizer, a detector of uninitialized
00011 /// reads.
00012 ///
00013 /// The algorithm of the tool is similar to Memcheck
00014 /// (http://goo.gl/QKbem). We associate a few shadow bits with every
00015 /// byte of the application memory, poison the shadow of the malloc-ed
00016 /// or alloca-ed memory, load the shadow bits on every memory read,
00017 /// propagate the shadow bits through some of the arithmetic
00018 /// instruction (including MOV), store the shadow bits on every memory
00019 /// write, report a bug on some other instructions (e.g. JMP) if the
00020 /// associated shadow is poisoned.
00021 ///
00022 /// But there are differences too. The first and the major one:
00023 /// compiler instrumentation instead of binary instrumentation. This
00024 /// gives us much better register allocation, possible compiler
00025 /// optimizations and a fast start-up. But this brings the major issue
00026 /// as well: msan needs to see all program events, including system
00027 /// calls and reads/writes in system libraries, so we either need to
00028 /// compile *everything* with msan or use a binary translation
00029 /// component (e.g. DynamoRIO) to instrument pre-built libraries.
00030 /// Another difference from Memcheck is that we use 8 shadow bits per
00031 /// byte of application memory and use a direct shadow mapping. This
00032 /// greatly simplifies the instrumentation code and avoids races on
00033 /// shadow updates (Memcheck is single-threaded so races are not a
00034 /// concern there. Memcheck uses 2 shadow bits per byte with a slow
00035 /// path storage that uses 8 bits per byte).
00036 ///
00037 /// The default value of shadow is 0, which means "clean" (not poisoned).
00038 ///
00039 /// Every module initializer should call __msan_init to ensure that the
00040 /// shadow memory is ready. On error, __msan_warning is called. Since
00041 /// parameters and return values may be passed via registers, we have a
00042 /// specialized thread-local shadow for return values
00043 /// (__msan_retval_tls) and parameters (__msan_param_tls).
00044 ///
00045 ///                           Origin tracking.
00046 ///
00047 /// MemorySanitizer can track origins (allocation points) of all uninitialized
00048 /// values. This behavior is controlled with a flag (msan-track-origins) and is
00049 /// disabled by default.
00050 ///
00051 /// Origins are 4-byte values created and interpreted by the runtime library.
00052 /// They are stored in a second shadow mapping, one 4-byte value for 4 bytes
00053 /// of application memory. Propagation of origins is basically a bunch of
00054 /// "select" instructions that pick the origin of a dirty argument, if an
00055 /// instruction has one.
00056 ///
00057 /// Every 4 aligned, consecutive bytes of application memory have one origin
00058 /// value associated with them. If these bytes contain uninitialized data
00059 /// coming from 2 different allocations, the last store wins. Because of this,
00060 /// MemorySanitizer reports can show unrelated origins, but this is unlikely in
00061 /// practice.
00062 ///
00063 /// Origins are meaningless for fully initialized values, so MemorySanitizer
00064 /// avoids storing origin to memory when a fully initialized value is stored.
00065 /// This way it avoids needless overwritting origin of the 4-byte region on
00066 /// a short (i.e. 1 byte) clean store, and it is also good for performance.
00067 ///
00068 ///                            Atomic handling.
00069 ///
00070 /// Ideally, every atomic store of application value should update the
00071 /// corresponding shadow location in an atomic way. Unfortunately, atomic store
00072 /// of two disjoint locations can not be done without severe slowdown.
00073 ///
00074 /// Therefore, we implement an approximation that may err on the safe side.
00075 /// In this implementation, every atomically accessed location in the program
00076 /// may only change from (partially) uninitialized to fully initialized, but
00077 /// not the other way around. We load the shadow _after_ the application load,
00078 /// and we store the shadow _before_ the app store. Also, we always store clean
00079 /// shadow (if the application store is atomic). This way, if the store-load
00080 /// pair constitutes a happens-before arc, shadow store and load are correctly
00081 /// ordered such that the load will get either the value that was stored, or
00082 /// some later value (which is always clean).
00083 ///
00084 /// This does not work very well with Compare-And-Swap (CAS) and
00085 /// Read-Modify-Write (RMW) operations. To follow the above logic, CAS and RMW
00086 /// must store the new shadow before the app operation, and load the shadow
00087 /// after the app operation. Computers don't work this way. Current
00088 /// implementation ignores the load aspect of CAS/RMW, always returning a clean
00089 /// value. It implements the store part as a simple atomic store by storing a
00090 /// clean shadow.
00091 
00092 //===----------------------------------------------------------------------===//
00093 
00094 #include "llvm/Transforms/Instrumentation.h"
00095 #include "llvm/ADT/DepthFirstIterator.h"
00096 #include "llvm/ADT/SmallString.h"
00097 #include "llvm/ADT/SmallVector.h"
00098 #include "llvm/ADT/StringExtras.h"
00099 #include "llvm/ADT/Triple.h"
00100 #include "llvm/IR/DataLayout.h"
00101 #include "llvm/IR/Function.h"
00102 #include "llvm/IR/IRBuilder.h"
00103 #include "llvm/IR/InlineAsm.h"
00104 #include "llvm/IR/InstVisitor.h"
00105 #include "llvm/IR/IntrinsicInst.h"
00106 #include "llvm/IR/LLVMContext.h"
00107 #include "llvm/IR/MDBuilder.h"
00108 #include "llvm/IR/Module.h"
00109 #include "llvm/IR/Type.h"
00110 #include "llvm/IR/ValueMap.h"
00111 #include "llvm/Support/CommandLine.h"
00112 #include "llvm/Support/Compiler.h"
00113 #include "llvm/Support/Debug.h"
00114 #include "llvm/Support/raw_ostream.h"
00115 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00116 #include "llvm/Transforms/Utils/Local.h"
00117 #include "llvm/Transforms/Utils/ModuleUtils.h"
00118 
00119 using namespace llvm;
00120 
00121 #define DEBUG_TYPE "msan"
00122 
00123 static const unsigned kOriginSize = 4;
00124 static const unsigned kMinOriginAlignment = 4;
00125 static const unsigned kShadowTLSAlignment = 8;
00126 
00127 // These constants must be kept in sync with the ones in msan.h.
00128 static const unsigned kParamTLSSize = 800;
00129 static const unsigned kRetvalTLSSize = 800;
00130 
00131 // Accesses sizes are powers of two: 1, 2, 4, 8.
00132 static const size_t kNumberOfAccessSizes = 4;
00133 
00134 /// \brief Track origins of uninitialized values.
00135 ///
00136 /// Adds a section to MemorySanitizer report that points to the allocation
00137 /// (stack or heap) the uninitialized bits came from originally.
00138 static cl::opt<int> ClTrackOrigins("msan-track-origins",
00139        cl::desc("Track origins (allocation sites) of poisoned memory"),
00140        cl::Hidden, cl::init(0));
00141 static cl::opt<bool> ClKeepGoing("msan-keep-going",
00142        cl::desc("keep going after reporting a UMR"),
00143        cl::Hidden, cl::init(false));
00144 static cl::opt<bool> ClPoisonStack("msan-poison-stack",
00145        cl::desc("poison uninitialized stack variables"),
00146        cl::Hidden, cl::init(true));
00147 static cl::opt<bool> ClPoisonStackWithCall("msan-poison-stack-with-call",
00148        cl::desc("poison uninitialized stack variables with a call"),
00149        cl::Hidden, cl::init(false));
00150 static cl::opt<int> ClPoisonStackPattern("msan-poison-stack-pattern",
00151        cl::desc("poison uninitialized stack variables with the given pattern"),
00152        cl::Hidden, cl::init(0xff));
00153 static cl::opt<bool> ClPoisonUndef("msan-poison-undef",
00154        cl::desc("poison undef temps"),
00155        cl::Hidden, cl::init(true));
00156 
00157 static cl::opt<bool> ClHandleICmp("msan-handle-icmp",
00158        cl::desc("propagate shadow through ICmpEQ and ICmpNE"),
00159        cl::Hidden, cl::init(true));
00160 
00161 static cl::opt<bool> ClHandleICmpExact("msan-handle-icmp-exact",
00162        cl::desc("exact handling of relational integer ICmp"),
00163        cl::Hidden, cl::init(false));
00164 
00165 // This flag controls whether we check the shadow of the address
00166 // operand of load or store. Such bugs are very rare, since load from
00167 // a garbage address typically results in SEGV, but still happen
00168 // (e.g. only lower bits of address are garbage, or the access happens
00169 // early at program startup where malloc-ed memory is more likely to
00170 // be zeroed. As of 2012-08-28 this flag adds 20% slowdown.
00171 static cl::opt<bool> ClCheckAccessAddress("msan-check-access-address",
00172        cl::desc("report accesses through a pointer which has poisoned shadow"),
00173        cl::Hidden, cl::init(true));
00174 
00175 static cl::opt<bool> ClDumpStrictInstructions("msan-dump-strict-instructions",
00176        cl::desc("print out instructions with default strict semantics"),
00177        cl::Hidden, cl::init(false));
00178 
00179 static cl::opt<int> ClInstrumentationWithCallThreshold(
00180     "msan-instrumentation-with-call-threshold",
00181     cl::desc(
00182         "If the function being instrumented requires more than "
00183         "this number of checks and origin stores, use callbacks instead of "
00184         "inline checks (-1 means never use callbacks)."),
00185     cl::Hidden, cl::init(3500));
00186 
00187 // This is an experiment to enable handling of cases where shadow is a non-zero
00188 // compile-time constant. For some unexplainable reason they were silently
00189 // ignored in the instrumentation.
00190 static cl::opt<bool> ClCheckConstantShadow("msan-check-constant-shadow",
00191        cl::desc("Insert checks for constant shadow values"),
00192        cl::Hidden, cl::init(false));
00193 
00194 static const char *const kMsanModuleCtorName = "msan.module_ctor";
00195 static const char *const kMsanInitName = "__msan_init";
00196 
00197 namespace {
00198 
00199 // Memory map parameters used in application-to-shadow address calculation.
00200 // Offset = (Addr & ~AndMask) ^ XorMask
00201 // Shadow = ShadowBase + Offset
00202 // Origin = OriginBase + Offset
00203 struct MemoryMapParams {
00204   uint64_t AndMask;
00205   uint64_t XorMask;
00206   uint64_t ShadowBase;
00207   uint64_t OriginBase;
00208 };
00209 
00210 struct PlatformMemoryMapParams {
00211   const MemoryMapParams *bits32;
00212   const MemoryMapParams *bits64;
00213 };
00214 
00215 // i386 Linux
00216 static const MemoryMapParams Linux_I386_MemoryMapParams = {
00217   0x000080000000,  // AndMask
00218   0,               // XorMask (not used)
00219   0,               // ShadowBase (not used)
00220   0x000040000000,  // OriginBase
00221 };
00222 
00223 // x86_64 Linux
00224 static const MemoryMapParams Linux_X86_64_MemoryMapParams = {
00225 #ifdef MSAN_LINUX_X86_64_OLD_MAPPING
00226   0x400000000000,  // AndMask
00227   0,               // XorMask (not used)
00228   0,               // ShadowBase (not used)
00229   0x200000000000,  // OriginBase
00230 #else
00231   0,               // AndMask (not used)
00232   0x500000000000,  // XorMask
00233   0,               // ShadowBase (not used)
00234   0x100000000000,  // OriginBase
00235 #endif
00236 };
00237 
00238 // mips64 Linux
00239 static const MemoryMapParams Linux_MIPS64_MemoryMapParams = {
00240   0x004000000000,  // AndMask
00241   0,               // XorMask (not used)
00242   0,               // ShadowBase (not used)
00243   0x002000000000,  // OriginBase
00244 };
00245 
00246 // ppc64 Linux
00247 static const MemoryMapParams Linux_PowerPC64_MemoryMapParams = {
00248   0x200000000000,  // AndMask
00249   0x100000000000,  // XorMask
00250   0x080000000000,  // ShadowBase
00251   0x1C0000000000,  // OriginBase
00252 };
00253 
00254 // aarch64 Linux
00255 static const MemoryMapParams Linux_AArch64_MemoryMapParams = {
00256   0,               // AndMask (not used)
00257   0x06000000000,   // XorMask
00258   0,               // ShadowBase (not used)
00259   0x01000000000,   // OriginBase
00260 };
00261 
00262 // i386 FreeBSD
00263 static const MemoryMapParams FreeBSD_I386_MemoryMapParams = {
00264   0x000180000000,  // AndMask
00265   0x000040000000,  // XorMask
00266   0x000020000000,  // ShadowBase
00267   0x000700000000,  // OriginBase
00268 };
00269 
00270 // x86_64 FreeBSD
00271 static const MemoryMapParams FreeBSD_X86_64_MemoryMapParams = {
00272   0xc00000000000,  // AndMask
00273   0x200000000000,  // XorMask
00274   0x100000000000,  // ShadowBase
00275   0x380000000000,  // OriginBase
00276 };
00277 
00278 static const PlatformMemoryMapParams Linux_X86_MemoryMapParams = {
00279   &Linux_I386_MemoryMapParams,
00280   &Linux_X86_64_MemoryMapParams,
00281 };
00282 
00283 static const PlatformMemoryMapParams Linux_MIPS_MemoryMapParams = {
00284   nullptr,
00285   &Linux_MIPS64_MemoryMapParams,
00286 };
00287 
00288 static const PlatformMemoryMapParams Linux_PowerPC_MemoryMapParams = {
00289   nullptr,
00290   &Linux_PowerPC64_MemoryMapParams,
00291 };
00292 
00293 static const PlatformMemoryMapParams Linux_ARM_MemoryMapParams = {
00294   nullptr,
00295   &Linux_AArch64_MemoryMapParams,
00296 };
00297 
00298 static const PlatformMemoryMapParams FreeBSD_X86_MemoryMapParams = {
00299   &FreeBSD_I386_MemoryMapParams,
00300   &FreeBSD_X86_64_MemoryMapParams,
00301 };
00302 
00303 /// \brief An instrumentation pass implementing detection of uninitialized
00304 /// reads.
00305 ///
00306 /// MemorySanitizer: instrument the code in module to find
00307 /// uninitialized reads.
00308 class MemorySanitizer : public FunctionPass {
00309  public:
00310   MemorySanitizer(int TrackOrigins = 0)
00311       : FunctionPass(ID),
00312         TrackOrigins(std::max(TrackOrigins, (int)ClTrackOrigins)),
00313         WarningFn(nullptr) {}
00314   const char *getPassName() const override { return "MemorySanitizer"; }
00315   bool runOnFunction(Function &F) override;
00316   bool doInitialization(Module &M) override;
00317   static char ID;  // Pass identification, replacement for typeid.
00318 
00319  private:
00320   void initializeCallbacks(Module &M);
00321 
00322   /// \brief Track origins (allocation points) of uninitialized values.
00323   int TrackOrigins;
00324 
00325   LLVMContext *C;
00326   Type *IntptrTy;
00327   Type *OriginTy;
00328   /// \brief Thread-local shadow storage for function parameters.
00329   GlobalVariable *ParamTLS;
00330   /// \brief Thread-local origin storage for function parameters.
00331   GlobalVariable *ParamOriginTLS;
00332   /// \brief Thread-local shadow storage for function return value.
00333   GlobalVariable *RetvalTLS;
00334   /// \brief Thread-local origin storage for function return value.
00335   GlobalVariable *RetvalOriginTLS;
00336   /// \brief Thread-local shadow storage for in-register va_arg function
00337   /// parameters (x86_64-specific).
00338   GlobalVariable *VAArgTLS;
00339   /// \brief Thread-local shadow storage for va_arg overflow area
00340   /// (x86_64-specific).
00341   GlobalVariable *VAArgOverflowSizeTLS;
00342   /// \brief Thread-local space used to pass origin value to the UMR reporting
00343   /// function.
00344   GlobalVariable *OriginTLS;
00345 
00346   /// \brief The run-time callback to print a warning.
00347   Value *WarningFn;
00348   // These arrays are indexed by log2(AccessSize).
00349   Value *MaybeWarningFn[kNumberOfAccessSizes];
00350   Value *MaybeStoreOriginFn[kNumberOfAccessSizes];
00351 
00352   /// \brief Run-time helper that generates a new origin value for a stack
00353   /// allocation.
00354   Value *MsanSetAllocaOrigin4Fn;
00355   /// \brief Run-time helper that poisons stack on function entry.
00356   Value *MsanPoisonStackFn;
00357   /// \brief Run-time helper that records a store (or any event) of an
00358   /// uninitialized value and returns an updated origin id encoding this info.
00359   Value *MsanChainOriginFn;
00360   /// \brief MSan runtime replacements for memmove, memcpy and memset.
00361   Value *MemmoveFn, *MemcpyFn, *MemsetFn;
00362 
00363   /// \brief Memory map parameters used in application-to-shadow calculation.
00364   const MemoryMapParams *MapParams;
00365 
00366   MDNode *ColdCallWeights;
00367   /// \brief Branch weights for origin store.
00368   MDNode *OriginStoreWeights;
00369   /// \brief An empty volatile inline asm that prevents callback merge.
00370   InlineAsm *EmptyAsm;
00371   Function *MsanCtorFunction;
00372 
00373   friend struct MemorySanitizerVisitor;
00374   friend struct VarArgAMD64Helper;
00375   friend struct VarArgMIPS64Helper;
00376   friend struct VarArgAArch64Helper;
00377 };
00378 } // anonymous namespace
00379 
00380 char MemorySanitizer::ID = 0;
00381 INITIALIZE_PASS(MemorySanitizer, "msan",
00382                 "MemorySanitizer: detects uninitialized reads.",
00383                 false, false)
00384 
00385 FunctionPass *llvm::createMemorySanitizerPass(int TrackOrigins) {
00386   return new MemorySanitizer(TrackOrigins);
00387 }
00388 
00389 /// \brief Create a non-const global initialized with the given string.
00390 ///
00391 /// Creates a writable global for Str so that we can pass it to the
00392 /// run-time lib. Runtime uses first 4 bytes of the string to store the
00393 /// frame ID, so the string needs to be mutable.
00394 static GlobalVariable *createPrivateNonConstGlobalForString(Module &M,
00395                                                             StringRef Str) {
00396   Constant *StrConst = ConstantDataArray::getString(M.getContext(), Str);
00397   return new GlobalVariable(M, StrConst->getType(), /*isConstant=*/false,
00398                             GlobalValue::PrivateLinkage, StrConst, "");
00399 }
00400 
00401 /// \brief Insert extern declaration of runtime-provided functions and globals.
00402 void MemorySanitizer::initializeCallbacks(Module &M) {
00403   // Only do this once.
00404   if (WarningFn)
00405     return;
00406 
00407   IRBuilder<> IRB(*C);
00408   // Create the callback.
00409   // FIXME: this function should have "Cold" calling conv,
00410   // which is not yet implemented.
00411   StringRef WarningFnName = ClKeepGoing ? "__msan_warning"
00412                                         : "__msan_warning_noreturn";
00413   WarningFn = M.getOrInsertFunction(WarningFnName, IRB.getVoidTy(), nullptr);
00414 
00415   for (size_t AccessSizeIndex = 0; AccessSizeIndex < kNumberOfAccessSizes;
00416        AccessSizeIndex++) {
00417     unsigned AccessSize = 1 << AccessSizeIndex;
00418     std::string FunctionName = "__msan_maybe_warning_" + itostr(AccessSize);
00419     MaybeWarningFn[AccessSizeIndex] = M.getOrInsertFunction(
00420         FunctionName, IRB.getVoidTy(), IRB.getIntNTy(AccessSize * 8),
00421         IRB.getInt32Ty(), nullptr);
00422 
00423     FunctionName = "__msan_maybe_store_origin_" + itostr(AccessSize);
00424     MaybeStoreOriginFn[AccessSizeIndex] = M.getOrInsertFunction(
00425         FunctionName, IRB.getVoidTy(), IRB.getIntNTy(AccessSize * 8),
00426         IRB.getInt8PtrTy(), IRB.getInt32Ty(), nullptr);
00427   }
00428 
00429   MsanSetAllocaOrigin4Fn = M.getOrInsertFunction(
00430     "__msan_set_alloca_origin4", IRB.getVoidTy(), IRB.getInt8PtrTy(), IntptrTy,
00431     IRB.getInt8PtrTy(), IntptrTy, nullptr);
00432   MsanPoisonStackFn =
00433       M.getOrInsertFunction("__msan_poison_stack", IRB.getVoidTy(),
00434                             IRB.getInt8PtrTy(), IntptrTy, nullptr);
00435   MsanChainOriginFn = M.getOrInsertFunction(
00436     "__msan_chain_origin", IRB.getInt32Ty(), IRB.getInt32Ty(), nullptr);
00437   MemmoveFn = M.getOrInsertFunction(
00438     "__msan_memmove", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
00439     IRB.getInt8PtrTy(), IntptrTy, nullptr);
00440   MemcpyFn = M.getOrInsertFunction(
00441     "__msan_memcpy", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
00442     IntptrTy, nullptr);
00443   MemsetFn = M.getOrInsertFunction(
00444     "__msan_memset", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt32Ty(),
00445     IntptrTy, nullptr);
00446 
00447   // Create globals.
00448   RetvalTLS = new GlobalVariable(
00449     M, ArrayType::get(IRB.getInt64Ty(), kRetvalTLSSize / 8), false,
00450     GlobalVariable::ExternalLinkage, nullptr, "__msan_retval_tls", nullptr,
00451     GlobalVariable::InitialExecTLSModel);
00452   RetvalOriginTLS = new GlobalVariable(
00453     M, OriginTy, false, GlobalVariable::ExternalLinkage, nullptr,
00454     "__msan_retval_origin_tls", nullptr, GlobalVariable::InitialExecTLSModel);
00455 
00456   ParamTLS = new GlobalVariable(
00457     M, ArrayType::get(IRB.getInt64Ty(), kParamTLSSize / 8), false,
00458     GlobalVariable::ExternalLinkage, nullptr, "__msan_param_tls", nullptr,
00459     GlobalVariable::InitialExecTLSModel);
00460   ParamOriginTLS = new GlobalVariable(
00461     M, ArrayType::get(OriginTy, kParamTLSSize / 4), false,
00462     GlobalVariable::ExternalLinkage, nullptr, "__msan_param_origin_tls",
00463     nullptr, GlobalVariable::InitialExecTLSModel);
00464 
00465   VAArgTLS = new GlobalVariable(
00466     M, ArrayType::get(IRB.getInt64Ty(), kParamTLSSize / 8), false,
00467     GlobalVariable::ExternalLinkage, nullptr, "__msan_va_arg_tls", nullptr,
00468     GlobalVariable::InitialExecTLSModel);
00469   VAArgOverflowSizeTLS = new GlobalVariable(
00470     M, IRB.getInt64Ty(), false, GlobalVariable::ExternalLinkage, nullptr,
00471     "__msan_va_arg_overflow_size_tls", nullptr,
00472     GlobalVariable::InitialExecTLSModel);
00473   OriginTLS = new GlobalVariable(
00474     M, IRB.getInt32Ty(), false, GlobalVariable::ExternalLinkage, nullptr,
00475     "__msan_origin_tls", nullptr, GlobalVariable::InitialExecTLSModel);
00476 
00477   // We insert an empty inline asm after __msan_report* to avoid callback merge.
00478   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
00479                             StringRef(""), StringRef(""),
00480                             /*hasSideEffects=*/true);
00481 }
00482 
00483 /// \brief Module-level initialization.
00484 ///
00485 /// inserts a call to __msan_init to the module's constructor list.
00486 bool MemorySanitizer::doInitialization(Module &M) {
00487   auto &DL = M.getDataLayout();
00488 
00489   Triple TargetTriple(M.getTargetTriple());
00490   switch (TargetTriple.getOS()) {
00491     case Triple::FreeBSD:
00492       switch (TargetTriple.getArch()) {
00493         case Triple::x86_64:
00494           MapParams = FreeBSD_X86_MemoryMapParams.bits64;
00495           break;
00496         case Triple::x86:
00497           MapParams = FreeBSD_X86_MemoryMapParams.bits32;
00498           break;
00499         default:
00500           report_fatal_error("unsupported architecture");
00501       }
00502       break;
00503     case Triple::Linux:
00504       switch (TargetTriple.getArch()) {
00505         case Triple::x86_64:
00506           MapParams = Linux_X86_MemoryMapParams.bits64;
00507           break;
00508         case Triple::x86:
00509           MapParams = Linux_X86_MemoryMapParams.bits32;
00510           break;
00511         case Triple::mips64:
00512         case Triple::mips64el:
00513           MapParams = Linux_MIPS_MemoryMapParams.bits64;
00514           break;
00515         case Triple::ppc64:
00516         case Triple::ppc64le:
00517           MapParams = Linux_PowerPC_MemoryMapParams.bits64;
00518           break;
00519         case Triple::aarch64:
00520         case Triple::aarch64_be:
00521           MapParams = Linux_ARM_MemoryMapParams.bits64;
00522           break;
00523         default:
00524           report_fatal_error("unsupported architecture");
00525       }
00526       break;
00527     default:
00528       report_fatal_error("unsupported operating system");
00529   }
00530 
00531   C = &(M.getContext());
00532   IRBuilder<> IRB(*C);
00533   IntptrTy = IRB.getIntPtrTy(DL);
00534   OriginTy = IRB.getInt32Ty();
00535 
00536   ColdCallWeights = MDBuilder(*C).createBranchWeights(1, 1000);
00537   OriginStoreWeights = MDBuilder(*C).createBranchWeights(1, 1000);
00538 
00539   std::tie(MsanCtorFunction, std::ignore) =
00540       createSanitizerCtorAndInitFunctions(M, kMsanModuleCtorName, kMsanInitName,
00541                                           /*InitArgTypes=*/{},
00542                                           /*InitArgs=*/{});
00543 
00544   appendToGlobalCtors(M, MsanCtorFunction, 0);
00545 
00546   if (TrackOrigins)
00547     new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage,
00548                        IRB.getInt32(TrackOrigins), "__msan_track_origins");
00549 
00550   if (ClKeepGoing)
00551     new GlobalVariable(M, IRB.getInt32Ty(), true, GlobalValue::WeakODRLinkage,
00552                        IRB.getInt32(ClKeepGoing), "__msan_keep_going");
00553 
00554   return true;
00555 }
00556 
00557 namespace {
00558 
00559 /// \brief A helper class that handles instrumentation of VarArg
00560 /// functions on a particular platform.
00561 ///
00562 /// Implementations are expected to insert the instrumentation
00563 /// necessary to propagate argument shadow through VarArg function
00564 /// calls. Visit* methods are called during an InstVisitor pass over
00565 /// the function, and should avoid creating new basic blocks. A new
00566 /// instance of this class is created for each instrumented function.
00567 struct VarArgHelper {
00568   /// \brief Visit a CallSite.
00569   virtual void visitCallSite(CallSite &CS, IRBuilder<> &IRB) = 0;
00570 
00571   /// \brief Visit a va_start call.
00572   virtual void visitVAStartInst(VAStartInst &I) = 0;
00573 
00574   /// \brief Visit a va_copy call.
00575   virtual void visitVACopyInst(VACopyInst &I) = 0;
00576 
00577   /// \brief Finalize function instrumentation.
00578   ///
00579   /// This method is called after visiting all interesting (see above)
00580   /// instructions in a function.
00581   virtual void finalizeInstrumentation() = 0;
00582 
00583   virtual ~VarArgHelper() {}
00584 };
00585 
00586 struct MemorySanitizerVisitor;
00587 
00588 VarArgHelper*
00589 CreateVarArgHelper(Function &Func, MemorySanitizer &Msan,
00590                    MemorySanitizerVisitor &Visitor);
00591 
00592 unsigned TypeSizeToSizeIndex(unsigned TypeSize) {
00593   if (TypeSize <= 8) return 0;
00594   return Log2_32_Ceil(TypeSize / 8);
00595 }
00596 
00597 /// This class does all the work for a given function. Store and Load
00598 /// instructions store and load corresponding shadow and origin
00599 /// values. Most instructions propagate shadow from arguments to their
00600 /// return values. Certain instructions (most importantly, BranchInst)
00601 /// test their argument shadow and print reports (with a runtime call) if it's
00602 /// non-zero.
00603 struct MemorySanitizerVisitor : public InstVisitor<MemorySanitizerVisitor> {
00604   Function &F;
00605   MemorySanitizer &MS;
00606   SmallVector<PHINode *, 16> ShadowPHINodes, OriginPHINodes;
00607   ValueMap<Value*, Value*> ShadowMap, OriginMap;
00608   std::unique_ptr<VarArgHelper> VAHelper;
00609 
00610   // The following flags disable parts of MSan instrumentation based on
00611   // blacklist contents and command-line options.
00612   bool InsertChecks;
00613   bool PropagateShadow;
00614   bool PoisonStack;
00615   bool PoisonUndef;
00616   bool CheckReturnValue;
00617 
00618   struct ShadowOriginAndInsertPoint {
00619     Value *Shadow;
00620     Value *Origin;
00621     Instruction *OrigIns;
00622     ShadowOriginAndInsertPoint(Value *S, Value *O, Instruction *I)
00623       : Shadow(S), Origin(O), OrigIns(I) { }
00624   };
00625   SmallVector<ShadowOriginAndInsertPoint, 16> InstrumentationList;
00626   SmallVector<Instruction*, 16> StoreList;
00627 
00628   MemorySanitizerVisitor(Function &F, MemorySanitizer &MS)
00629       : F(F), MS(MS), VAHelper(CreateVarArgHelper(F, MS, *this)) {
00630     bool SanitizeFunction = F.hasFnAttribute(Attribute::SanitizeMemory);
00631     InsertChecks = SanitizeFunction;
00632     PropagateShadow = SanitizeFunction;
00633     PoisonStack = SanitizeFunction && ClPoisonStack;
00634     PoisonUndef = SanitizeFunction && ClPoisonUndef;
00635     // FIXME: Consider using SpecialCaseList to specify a list of functions that
00636     // must always return fully initialized values. For now, we hardcode "main".
00637     CheckReturnValue = SanitizeFunction && (F.getName() == "main");
00638 
00639     DEBUG(if (!InsertChecks)
00640           dbgs() << "MemorySanitizer is not inserting checks into '"
00641                  << F.getName() << "'\n");
00642   }
00643 
00644   Value *updateOrigin(Value *V, IRBuilder<> &IRB) {
00645     if (MS.TrackOrigins <= 1) return V;
00646     return IRB.CreateCall(MS.MsanChainOriginFn, V);
00647   }
00648 
00649   Value *originToIntptr(IRBuilder<> &IRB, Value *Origin) {
00650     const DataLayout &DL = F.getParent()->getDataLayout();
00651     unsigned IntptrSize = DL.getTypeStoreSize(MS.IntptrTy);
00652     if (IntptrSize == kOriginSize) return Origin;
00653     assert(IntptrSize == kOriginSize * 2);
00654     Origin = IRB.CreateIntCast(Origin, MS.IntptrTy, /* isSigned */ false);
00655     return IRB.CreateOr(Origin, IRB.CreateShl(Origin, kOriginSize * 8));
00656   }
00657 
00658   /// \brief Fill memory range with the given origin value.
00659   void paintOrigin(IRBuilder<> &IRB, Value *Origin, Value *OriginPtr,
00660                    unsigned Size, unsigned Alignment) {
00661     const DataLayout &DL = F.getParent()->getDataLayout();
00662     unsigned IntptrAlignment = DL.getABITypeAlignment(MS.IntptrTy);
00663     unsigned IntptrSize = DL.getTypeStoreSize(MS.IntptrTy);
00664     assert(IntptrAlignment >= kMinOriginAlignment);
00665     assert(IntptrSize >= kOriginSize);
00666 
00667     unsigned Ofs = 0;
00668     unsigned CurrentAlignment = Alignment;
00669     if (Alignment >= IntptrAlignment && IntptrSize > kOriginSize) {
00670       Value *IntptrOrigin = originToIntptr(IRB, Origin);
00671       Value *IntptrOriginPtr =
00672           IRB.CreatePointerCast(OriginPtr, PointerType::get(MS.IntptrTy, 0));
00673       for (unsigned i = 0; i < Size / IntptrSize; ++i) {
00674         Value *Ptr = i ? IRB.CreateConstGEP1_32(MS.IntptrTy, IntptrOriginPtr, i)
00675                        : IntptrOriginPtr;
00676         IRB.CreateAlignedStore(IntptrOrigin, Ptr, CurrentAlignment);
00677         Ofs += IntptrSize / kOriginSize;
00678         CurrentAlignment = IntptrAlignment;
00679       }
00680     }
00681 
00682     for (unsigned i = Ofs; i < (Size + kOriginSize - 1) / kOriginSize; ++i) {
00683       Value *GEP =
00684           i ? IRB.CreateConstGEP1_32(nullptr, OriginPtr, i) : OriginPtr;
00685       IRB.CreateAlignedStore(Origin, GEP, CurrentAlignment);
00686       CurrentAlignment = kMinOriginAlignment;
00687     }
00688   }
00689 
00690   void storeOrigin(IRBuilder<> &IRB, Value *Addr, Value *Shadow, Value *Origin,
00691                    unsigned Alignment, bool AsCall) {
00692     const DataLayout &DL = F.getParent()->getDataLayout();
00693     unsigned OriginAlignment = std::max(kMinOriginAlignment, Alignment);
00694     unsigned StoreSize = DL.getTypeStoreSize(Shadow->getType());
00695     if (Shadow->getType()->isAggregateType()) {
00696       paintOrigin(IRB, updateOrigin(Origin, IRB),
00697                   getOriginPtr(Addr, IRB, Alignment), StoreSize,
00698                   OriginAlignment);
00699     } else {
00700       Value *ConvertedShadow = convertToShadowTyNoVec(Shadow, IRB);
00701       Constant *ConstantShadow = dyn_cast_or_null<Constant>(ConvertedShadow);
00702       if (ConstantShadow) {
00703         if (ClCheckConstantShadow && !ConstantShadow->isZeroValue())
00704           paintOrigin(IRB, updateOrigin(Origin, IRB),
00705                       getOriginPtr(Addr, IRB, Alignment), StoreSize,
00706                       OriginAlignment);
00707         return;
00708       }
00709 
00710       unsigned TypeSizeInBits =
00711           DL.getTypeSizeInBits(ConvertedShadow->getType());
00712       unsigned SizeIndex = TypeSizeToSizeIndex(TypeSizeInBits);
00713       if (AsCall && SizeIndex < kNumberOfAccessSizes) {
00714         Value *Fn = MS.MaybeStoreOriginFn[SizeIndex];
00715         Value *ConvertedShadow2 = IRB.CreateZExt(
00716             ConvertedShadow, IRB.getIntNTy(8 * (1 << SizeIndex)));
00717         IRB.CreateCall(Fn, {ConvertedShadow2,
00718                             IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
00719                             Origin});
00720       } else {
00721         Value *Cmp = IRB.CreateICmpNE(
00722             ConvertedShadow, getCleanShadow(ConvertedShadow), "_mscmp");
00723         Instruction *CheckTerm = SplitBlockAndInsertIfThen(
00724             Cmp, &*IRB.GetInsertPoint(), false, MS.OriginStoreWeights);
00725         IRBuilder<> IRBNew(CheckTerm);
00726         paintOrigin(IRBNew, updateOrigin(Origin, IRBNew),
00727                     getOriginPtr(Addr, IRBNew, Alignment), StoreSize,
00728                     OriginAlignment);
00729       }
00730     }
00731   }
00732 
00733   void materializeStores(bool InstrumentWithCalls) {
00734     for (auto Inst : StoreList) {
00735       StoreInst &SI = *dyn_cast<StoreInst>(Inst);
00736 
00737       IRBuilder<> IRB(&SI);
00738       Value *Val = SI.getValueOperand();
00739       Value *Addr = SI.getPointerOperand();
00740       Value *Shadow = SI.isAtomic() ? getCleanShadow(Val) : getShadow(Val);
00741       Value *ShadowPtr = getShadowPtr(Addr, Shadow->getType(), IRB);
00742 
00743       StoreInst *NewSI =
00744           IRB.CreateAlignedStore(Shadow, ShadowPtr, SI.getAlignment());
00745       DEBUG(dbgs() << "  STORE: " << *NewSI << "\n");
00746       (void)NewSI;
00747 
00748       if (ClCheckAccessAddress) insertShadowCheck(Addr, &SI);
00749 
00750       if (SI.isAtomic()) SI.setOrdering(addReleaseOrdering(SI.getOrdering()));
00751 
00752       if (MS.TrackOrigins && !SI.isAtomic())
00753         storeOrigin(IRB, Addr, Shadow, getOrigin(Val), SI.getAlignment(),
00754                     InstrumentWithCalls);
00755     }
00756   }
00757 
00758   void materializeOneCheck(Instruction *OrigIns, Value *Shadow, Value *Origin,
00759                            bool AsCall) {
00760     IRBuilder<> IRB(OrigIns);
00761     DEBUG(dbgs() << "  SHAD0 : " << *Shadow << "\n");
00762     Value *ConvertedShadow = convertToShadowTyNoVec(Shadow, IRB);
00763     DEBUG(dbgs() << "  SHAD1 : " << *ConvertedShadow << "\n");
00764 
00765     Constant *ConstantShadow = dyn_cast_or_null<Constant>(ConvertedShadow);
00766     if (ConstantShadow) {
00767       if (ClCheckConstantShadow && !ConstantShadow->isZeroValue()) {
00768         if (MS.TrackOrigins) {
00769           IRB.CreateStore(Origin ? (Value *)Origin : (Value *)IRB.getInt32(0),
00770                           MS.OriginTLS);
00771         }
00772         IRB.CreateCall(MS.WarningFn, {});
00773         IRB.CreateCall(MS.EmptyAsm, {});
00774         // FIXME: Insert UnreachableInst if !ClKeepGoing?
00775         // This may invalidate some of the following checks and needs to be done
00776         // at the very end.
00777       }
00778       return;
00779     }
00780 
00781     const DataLayout &DL = OrigIns->getModule()->getDataLayout();
00782 
00783     unsigned TypeSizeInBits = DL.getTypeSizeInBits(ConvertedShadow->getType());
00784     unsigned SizeIndex = TypeSizeToSizeIndex(TypeSizeInBits);
00785     if (AsCall && SizeIndex < kNumberOfAccessSizes) {
00786       Value *Fn = MS.MaybeWarningFn[SizeIndex];
00787       Value *ConvertedShadow2 =
00788           IRB.CreateZExt(ConvertedShadow, IRB.getIntNTy(8 * (1 << SizeIndex)));
00789       IRB.CreateCall(Fn, {ConvertedShadow2, MS.TrackOrigins && Origin
00790                                                 ? Origin
00791                                                 : (Value *)IRB.getInt32(0)});
00792     } else {
00793       Value *Cmp = IRB.CreateICmpNE(ConvertedShadow,
00794                                     getCleanShadow(ConvertedShadow), "_mscmp");
00795       Instruction *CheckTerm = SplitBlockAndInsertIfThen(
00796           Cmp, OrigIns,
00797           /* Unreachable */ !ClKeepGoing, MS.ColdCallWeights);
00798 
00799       IRB.SetInsertPoint(CheckTerm);
00800       if (MS.TrackOrigins) {
00801         IRB.CreateStore(Origin ? (Value *)Origin : (Value *)IRB.getInt32(0),
00802                         MS.OriginTLS);
00803       }
00804       IRB.CreateCall(MS.WarningFn, {});
00805       IRB.CreateCall(MS.EmptyAsm, {});
00806       DEBUG(dbgs() << "  CHECK: " << *Cmp << "\n");
00807     }
00808   }
00809 
00810   void materializeChecks(bool InstrumentWithCalls) {
00811     for (const auto &ShadowData : InstrumentationList) {
00812       Instruction *OrigIns = ShadowData.OrigIns;
00813       Value *Shadow = ShadowData.Shadow;
00814       Value *Origin = ShadowData.Origin;
00815       materializeOneCheck(OrigIns, Shadow, Origin, InstrumentWithCalls);
00816     }
00817     DEBUG(dbgs() << "DONE:\n" << F);
00818   }
00819 
00820   /// \brief Add MemorySanitizer instrumentation to a function.
00821   bool runOnFunction() {
00822     MS.initializeCallbacks(*F.getParent());
00823 
00824     // In the presence of unreachable blocks, we may see Phi nodes with
00825     // incoming nodes from such blocks. Since InstVisitor skips unreachable
00826     // blocks, such nodes will not have any shadow value associated with them.
00827     // It's easier to remove unreachable blocks than deal with missing shadow.
00828     removeUnreachableBlocks(F);
00829 
00830     // Iterate all BBs in depth-first order and create shadow instructions
00831     // for all instructions (where applicable).
00832     // For PHI nodes we create dummy shadow PHIs which will be finalized later.
00833     for (BasicBlock *BB : depth_first(&F.getEntryBlock()))
00834       visit(*BB);
00835 
00836 
00837     // Finalize PHI nodes.
00838     for (PHINode *PN : ShadowPHINodes) {
00839       PHINode *PNS = cast<PHINode>(getShadow(PN));
00840       PHINode *PNO = MS.TrackOrigins ? cast<PHINode>(getOrigin(PN)) : nullptr;
00841       size_t NumValues = PN->getNumIncomingValues();
00842       for (size_t v = 0; v < NumValues; v++) {
00843         PNS->addIncoming(getShadow(PN, v), PN->getIncomingBlock(v));
00844         if (PNO) PNO->addIncoming(getOrigin(PN, v), PN->getIncomingBlock(v));
00845       }
00846     }
00847 
00848     VAHelper->finalizeInstrumentation();
00849 
00850     bool InstrumentWithCalls = ClInstrumentationWithCallThreshold >= 0 &&
00851                                InstrumentationList.size() + StoreList.size() >
00852                                    (unsigned)ClInstrumentationWithCallThreshold;
00853 
00854     // Delayed instrumentation of StoreInst.
00855     // This may add new checks to be inserted later.
00856     materializeStores(InstrumentWithCalls);
00857 
00858     // Insert shadow value checks.
00859     materializeChecks(InstrumentWithCalls);
00860 
00861     return true;
00862   }
00863 
00864   /// \brief Compute the shadow type that corresponds to a given Value.
00865   Type *getShadowTy(Value *V) {
00866     return getShadowTy(V->getType());
00867   }
00868 
00869   /// \brief Compute the shadow type that corresponds to a given Type.
00870   Type *getShadowTy(Type *OrigTy) {
00871     if (!OrigTy->isSized()) {
00872       return nullptr;
00873     }
00874     // For integer type, shadow is the same as the original type.
00875     // This may return weird-sized types like i1.
00876     if (IntegerType *IT = dyn_cast<IntegerType>(OrigTy))
00877       return IT;
00878     const DataLayout &DL = F.getParent()->getDataLayout();
00879     if (VectorType *VT = dyn_cast<VectorType>(OrigTy)) {
00880       uint32_t EltSize = DL.getTypeSizeInBits(VT->getElementType());
00881       return VectorType::get(IntegerType::get(*MS.C, EltSize),
00882                              VT->getNumElements());
00883     }
00884     if (ArrayType *AT = dyn_cast<ArrayType>(OrigTy)) {
00885       return ArrayType::get(getShadowTy(AT->getElementType()),
00886                             AT->getNumElements());
00887     }
00888     if (StructType *ST = dyn_cast<StructType>(OrigTy)) {
00889       SmallVector<Type*, 4> Elements;
00890       for (unsigned i = 0, n = ST->getNumElements(); i < n; i++)
00891         Elements.push_back(getShadowTy(ST->getElementType(i)));
00892       StructType *Res = StructType::get(*MS.C, Elements, ST->isPacked());
00893       DEBUG(dbgs() << "getShadowTy: " << *ST << " ===> " << *Res << "\n");
00894       return Res;
00895     }
00896     uint32_t TypeSize = DL.getTypeSizeInBits(OrigTy);
00897     return IntegerType::get(*MS.C, TypeSize);
00898   }
00899 
00900   /// \brief Flatten a vector type.
00901   Type *getShadowTyNoVec(Type *ty) {
00902     if (VectorType *vt = dyn_cast<VectorType>(ty))
00903       return IntegerType::get(*MS.C, vt->getBitWidth());
00904     return ty;
00905   }
00906 
00907   /// \brief Convert a shadow value to it's flattened variant.
00908   Value *convertToShadowTyNoVec(Value *V, IRBuilder<> &IRB) {
00909     Type *Ty = V->getType();
00910     Type *NoVecTy = getShadowTyNoVec(Ty);
00911     if (Ty == NoVecTy) return V;
00912     return IRB.CreateBitCast(V, NoVecTy);
00913   }
00914 
00915   /// \brief Compute the integer shadow offset that corresponds to a given
00916   /// application address.
00917   ///
00918   /// Offset = (Addr & ~AndMask) ^ XorMask
00919   Value *getShadowPtrOffset(Value *Addr, IRBuilder<> &IRB) {
00920     Value *OffsetLong = IRB.CreatePointerCast(Addr, MS.IntptrTy);
00921 
00922     uint64_t AndMask = MS.MapParams->AndMask;
00923     if (AndMask)
00924       OffsetLong =
00925           IRB.CreateAnd(OffsetLong, ConstantInt::get(MS.IntptrTy, ~AndMask));
00926 
00927     uint64_t XorMask = MS.MapParams->XorMask;
00928     if (XorMask)
00929       OffsetLong =
00930           IRB.CreateXor(OffsetLong, ConstantInt::get(MS.IntptrTy, XorMask));
00931     return OffsetLong;
00932   }
00933 
00934   /// \brief Compute the shadow address that corresponds to a given application
00935   /// address.
00936   ///
00937   /// Shadow = ShadowBase + Offset
00938   Value *getShadowPtr(Value *Addr, Type *ShadowTy,
00939                       IRBuilder<> &IRB) {
00940     Value *ShadowLong = getShadowPtrOffset(Addr, IRB);
00941     uint64_t ShadowBase = MS.MapParams->ShadowBase;
00942     if (ShadowBase != 0)
00943       ShadowLong =
00944         IRB.CreateAdd(ShadowLong,
00945                       ConstantInt::get(MS.IntptrTy, ShadowBase));
00946     return IRB.CreateIntToPtr(ShadowLong, PointerType::get(ShadowTy, 0));
00947   }
00948 
00949   /// \brief Compute the origin address that corresponds to a given application
00950   /// address.
00951   ///
00952   /// OriginAddr = (OriginBase + Offset) & ~3ULL
00953   Value *getOriginPtr(Value *Addr, IRBuilder<> &IRB, unsigned Alignment) {
00954     Value *OriginLong = getShadowPtrOffset(Addr, IRB);
00955     uint64_t OriginBase = MS.MapParams->OriginBase;
00956     if (OriginBase != 0)
00957       OriginLong =
00958         IRB.CreateAdd(OriginLong,
00959                       ConstantInt::get(MS.IntptrTy, OriginBase));
00960     if (Alignment < kMinOriginAlignment) {
00961       uint64_t Mask = kMinOriginAlignment - 1;
00962       OriginLong = IRB.CreateAnd(OriginLong,
00963                                  ConstantInt::get(MS.IntptrTy, ~Mask));
00964     }
00965     return IRB.CreateIntToPtr(OriginLong,
00966                               PointerType::get(IRB.getInt32Ty(), 0));
00967   }
00968 
00969   /// \brief Compute the shadow address for a given function argument.
00970   ///
00971   /// Shadow = ParamTLS+ArgOffset.
00972   Value *getShadowPtrForArgument(Value *A, IRBuilder<> &IRB,
00973                                  int ArgOffset) {
00974     Value *Base = IRB.CreatePointerCast(MS.ParamTLS, MS.IntptrTy);
00975     Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset));
00976     return IRB.CreateIntToPtr(Base, PointerType::get(getShadowTy(A), 0),
00977                               "_msarg");
00978   }
00979 
00980   /// \brief Compute the origin address for a given function argument.
00981   Value *getOriginPtrForArgument(Value *A, IRBuilder<> &IRB,
00982                                  int ArgOffset) {
00983     if (!MS.TrackOrigins) return nullptr;
00984     Value *Base = IRB.CreatePointerCast(MS.ParamOriginTLS, MS.IntptrTy);
00985     Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset));
00986     return IRB.CreateIntToPtr(Base, PointerType::get(MS.OriginTy, 0),
00987                               "_msarg_o");
00988   }
00989 
00990   /// \brief Compute the shadow address for a retval.
00991   Value *getShadowPtrForRetval(Value *A, IRBuilder<> &IRB) {
00992     Value *Base = IRB.CreatePointerCast(MS.RetvalTLS, MS.IntptrTy);
00993     return IRB.CreateIntToPtr(Base, PointerType::get(getShadowTy(A), 0),
00994                               "_msret");
00995   }
00996 
00997   /// \brief Compute the origin address for a retval.
00998   Value *getOriginPtrForRetval(IRBuilder<> &IRB) {
00999     // We keep a single origin for the entire retval. Might be too optimistic.
01000     return MS.RetvalOriginTLS;
01001   }
01002 
01003   /// \brief Set SV to be the shadow value for V.
01004   void setShadow(Value *V, Value *SV) {
01005     assert(!ShadowMap.count(V) && "Values may only have one shadow");
01006     ShadowMap[V] = PropagateShadow ? SV : getCleanShadow(V);
01007   }
01008 
01009   /// \brief Set Origin to be the origin value for V.
01010   void setOrigin(Value *V, Value *Origin) {
01011     if (!MS.TrackOrigins) return;
01012     assert(!OriginMap.count(V) && "Values may only have one origin");
01013     DEBUG(dbgs() << "ORIGIN: " << *V << "  ==> " << *Origin << "\n");
01014     OriginMap[V] = Origin;
01015   }
01016 
01017   /// \brief Create a clean shadow value for a given value.
01018   ///
01019   /// Clean shadow (all zeroes) means all bits of the value are defined
01020   /// (initialized).
01021   Constant *getCleanShadow(Value *V) {
01022     Type *ShadowTy = getShadowTy(V);
01023     if (!ShadowTy)
01024       return nullptr;
01025     return Constant::getNullValue(ShadowTy);
01026   }
01027 
01028   /// \brief Create a dirty shadow of a given shadow type.
01029   Constant *getPoisonedShadow(Type *ShadowTy) {
01030     assert(ShadowTy);
01031     if (isa<IntegerType>(ShadowTy) || isa<VectorType>(ShadowTy))
01032       return Constant::getAllOnesValue(ShadowTy);
01033     if (ArrayType *AT = dyn_cast<ArrayType>(ShadowTy)) {
01034       SmallVector<Constant *, 4> Vals(AT->getNumElements(),
01035                                       getPoisonedShadow(AT->getElementType()));
01036       return ConstantArray::get(AT, Vals);
01037     }
01038     if (StructType *ST = dyn_cast<StructType>(ShadowTy)) {
01039       SmallVector<Constant *, 4> Vals;
01040       for (unsigned i = 0, n = ST->getNumElements(); i < n; i++)
01041         Vals.push_back(getPoisonedShadow(ST->getElementType(i)));
01042       return ConstantStruct::get(ST, Vals);
01043     }
01044     llvm_unreachable("Unexpected shadow type");
01045   }
01046 
01047   /// \brief Create a dirty shadow for a given value.
01048   Constant *getPoisonedShadow(Value *V) {
01049     Type *ShadowTy = getShadowTy(V);
01050     if (!ShadowTy)
01051       return nullptr;
01052     return getPoisonedShadow(ShadowTy);
01053   }
01054 
01055   /// \brief Create a clean (zero) origin.
01056   Value *getCleanOrigin() {
01057     return Constant::getNullValue(MS.OriginTy);
01058   }
01059 
01060   /// \brief Get the shadow value for a given Value.
01061   ///
01062   /// This function either returns the value set earlier with setShadow,
01063   /// or extracts if from ParamTLS (for function arguments).
01064   Value *getShadow(Value *V) {
01065     if (!PropagateShadow) return getCleanShadow(V);
01066     if (Instruction *I = dyn_cast<Instruction>(V)) {
01067       // For instructions the shadow is already stored in the map.
01068       Value *Shadow = ShadowMap[V];
01069       if (!Shadow) {
01070         DEBUG(dbgs() << "No shadow: " << *V << "\n" << *(I->getParent()));
01071         (void)I;
01072         assert(Shadow && "No shadow for a value");
01073       }
01074       return Shadow;
01075     }
01076     if (UndefValue *U = dyn_cast<UndefValue>(V)) {
01077       Value *AllOnes = PoisonUndef ? getPoisonedShadow(V) : getCleanShadow(V);
01078       DEBUG(dbgs() << "Undef: " << *U << " ==> " << *AllOnes << "\n");
01079       (void)U;
01080       return AllOnes;
01081     }
01082     if (Argument *A = dyn_cast<Argument>(V)) {
01083       // For arguments we compute the shadow on demand and store it in the map.
01084       Value **ShadowPtr = &ShadowMap[V];
01085       if (*ShadowPtr)
01086         return *ShadowPtr;
01087       Function *F = A->getParent();
01088       IRBuilder<> EntryIRB(F->getEntryBlock().getFirstNonPHI());
01089       unsigned ArgOffset = 0;
01090       const DataLayout &DL = F->getParent()->getDataLayout();
01091       for (auto &FArg : F->args()) {
01092         if (!FArg.getType()->isSized()) {
01093           DEBUG(dbgs() << "Arg is not sized\n");
01094           continue;
01095         }
01096         unsigned Size =
01097             FArg.hasByValAttr()
01098                 ? DL.getTypeAllocSize(FArg.getType()->getPointerElementType())
01099                 : DL.getTypeAllocSize(FArg.getType());
01100         if (A == &FArg) {
01101           bool Overflow = ArgOffset + Size > kParamTLSSize;
01102           Value *Base = getShadowPtrForArgument(&FArg, EntryIRB, ArgOffset);
01103           if (FArg.hasByValAttr()) {
01104             // ByVal pointer itself has clean shadow. We copy the actual
01105             // argument shadow to the underlying memory.
01106             // Figure out maximal valid memcpy alignment.
01107             unsigned ArgAlign = FArg.getParamAlignment();
01108             if (ArgAlign == 0) {
01109               Type *EltType = A->getType()->getPointerElementType();
01110               ArgAlign = DL.getABITypeAlignment(EltType);
01111             }
01112             if (Overflow) {
01113               // ParamTLS overflow.
01114               EntryIRB.CreateMemSet(
01115                   getShadowPtr(V, EntryIRB.getInt8Ty(), EntryIRB),
01116                   Constant::getNullValue(EntryIRB.getInt8Ty()), Size, ArgAlign);
01117             } else {
01118               unsigned CopyAlign = std::min(ArgAlign, kShadowTLSAlignment);
01119               Value *Cpy = EntryIRB.CreateMemCpy(
01120                   getShadowPtr(V, EntryIRB.getInt8Ty(), EntryIRB), Base, Size,
01121                   CopyAlign);
01122               DEBUG(dbgs() << "  ByValCpy: " << *Cpy << "\n");
01123               (void)Cpy;
01124             }
01125             *ShadowPtr = getCleanShadow(V);
01126           } else {
01127             if (Overflow) {
01128               // ParamTLS overflow.
01129               *ShadowPtr = getCleanShadow(V);
01130             } else {
01131               *ShadowPtr =
01132                   EntryIRB.CreateAlignedLoad(Base, kShadowTLSAlignment);
01133             }
01134           }
01135           DEBUG(dbgs() << "  ARG:    "  << FArg << " ==> " <<
01136                 **ShadowPtr << "\n");
01137           if (MS.TrackOrigins && !Overflow) {
01138             Value *OriginPtr =
01139                 getOriginPtrForArgument(&FArg, EntryIRB, ArgOffset);
01140             setOrigin(A, EntryIRB.CreateLoad(OriginPtr));
01141           } else {
01142             setOrigin(A, getCleanOrigin());
01143           }
01144         }
01145         ArgOffset += alignTo(Size, kShadowTLSAlignment);
01146       }
01147       assert(*ShadowPtr && "Could not find shadow for an argument");
01148       return *ShadowPtr;
01149     }
01150     // For everything else the shadow is zero.
01151     return getCleanShadow(V);
01152   }
01153 
01154   /// \brief Get the shadow for i-th argument of the instruction I.
01155   Value *getShadow(Instruction *I, int i) {
01156     return getShadow(I->getOperand(i));
01157   }
01158 
01159   /// \brief Get the origin for a value.
01160   Value *getOrigin(Value *V) {
01161     if (!MS.TrackOrigins) return nullptr;
01162     if (!PropagateShadow) return getCleanOrigin();
01163     if (isa<Constant>(V)) return getCleanOrigin();
01164     assert((isa<Instruction>(V) || isa<Argument>(V)) &&
01165            "Unexpected value type in getOrigin()");
01166     Value *Origin = OriginMap[V];
01167     assert(Origin && "Missing origin");
01168     return Origin;
01169   }
01170 
01171   /// \brief Get the origin for i-th argument of the instruction I.
01172   Value *getOrigin(Instruction *I, int i) {
01173     return getOrigin(I->getOperand(i));
01174   }
01175 
01176   /// \brief Remember the place where a shadow check should be inserted.
01177   ///
01178   /// This location will be later instrumented with a check that will print a
01179   /// UMR warning in runtime if the shadow value is not 0.
01180   void insertShadowCheck(Value *Shadow, Value *Origin, Instruction *OrigIns) {
01181     assert(Shadow);
01182     if (!InsertChecks) return;
01183 #ifndef NDEBUG
01184     Type *ShadowTy = Shadow->getType();
01185     assert((isa<IntegerType>(ShadowTy) || isa<VectorType>(ShadowTy)) &&
01186            "Can only insert checks for integer and vector shadow types");
01187 #endif
01188     InstrumentationList.push_back(
01189         ShadowOriginAndInsertPoint(Shadow, Origin, OrigIns));
01190   }
01191 
01192   /// \brief Remember the place where a shadow check should be inserted.
01193   ///
01194   /// This location will be later instrumented with a check that will print a
01195   /// UMR warning in runtime if the value is not fully defined.
01196   void insertShadowCheck(Value *Val, Instruction *OrigIns) {
01197     assert(Val);
01198     Value *Shadow, *Origin;
01199     if (ClCheckConstantShadow) {
01200       Shadow = getShadow(Val);
01201       if (!Shadow) return;
01202       Origin = getOrigin(Val);
01203     } else {
01204       Shadow = dyn_cast_or_null<Instruction>(getShadow(Val));
01205       if (!Shadow) return;
01206       Origin = dyn_cast_or_null<Instruction>(getOrigin(Val));
01207     }
01208     insertShadowCheck(Shadow, Origin, OrigIns);
01209   }
01210 
01211   AtomicOrdering addReleaseOrdering(AtomicOrdering a) {
01212     switch (a) {
01213       case NotAtomic:
01214         return NotAtomic;
01215       case Unordered:
01216       case Monotonic:
01217       case Release:
01218         return Release;
01219       case Acquire:
01220       case AcquireRelease:
01221         return AcquireRelease;
01222       case SequentiallyConsistent:
01223         return SequentiallyConsistent;
01224     }
01225     llvm_unreachable("Unknown ordering");
01226   }
01227 
01228   AtomicOrdering addAcquireOrdering(AtomicOrdering a) {
01229     switch (a) {
01230       case NotAtomic:
01231         return NotAtomic;
01232       case Unordered:
01233       case Monotonic:
01234       case Acquire:
01235         return Acquire;
01236       case Release:
01237       case AcquireRelease:
01238         return AcquireRelease;
01239       case SequentiallyConsistent:
01240         return SequentiallyConsistent;
01241     }
01242     llvm_unreachable("Unknown ordering");
01243   }
01244 
01245   // ------------------- Visitors.
01246 
01247   /// \brief Instrument LoadInst
01248   ///
01249   /// Loads the corresponding shadow and (optionally) origin.
01250   /// Optionally, checks that the load address is fully defined.
01251   void visitLoadInst(LoadInst &I) {
01252     assert(I.getType()->isSized() && "Load type must have size");
01253     IRBuilder<> IRB(I.getNextNode());
01254     Type *ShadowTy = getShadowTy(&I);
01255     Value *Addr = I.getPointerOperand();
01256     if (PropagateShadow && !I.getMetadata("nosanitize")) {
01257       Value *ShadowPtr = getShadowPtr(Addr, ShadowTy, IRB);
01258       setShadow(&I,
01259                 IRB.CreateAlignedLoad(ShadowPtr, I.getAlignment(), "_msld"));
01260     } else {
01261       setShadow(&I, getCleanShadow(&I));
01262     }
01263 
01264     if (ClCheckAccessAddress)
01265       insertShadowCheck(I.getPointerOperand(), &I);
01266 
01267     if (I.isAtomic())
01268       I.setOrdering(addAcquireOrdering(I.getOrdering()));
01269 
01270     if (MS.TrackOrigins) {
01271       if (PropagateShadow) {
01272         unsigned Alignment = I.getAlignment();
01273         unsigned OriginAlignment = std::max(kMinOriginAlignment, Alignment);
01274         setOrigin(&I, IRB.CreateAlignedLoad(getOriginPtr(Addr, IRB, Alignment),
01275                                             OriginAlignment));
01276       } else {
01277         setOrigin(&I, getCleanOrigin());
01278       }
01279     }
01280   }
01281 
01282   /// \brief Instrument StoreInst
01283   ///
01284   /// Stores the corresponding shadow and (optionally) origin.
01285   /// Optionally, checks that the store address is fully defined.
01286   void visitStoreInst(StoreInst &I) {
01287     StoreList.push_back(&I);
01288   }
01289 
01290   void handleCASOrRMW(Instruction &I) {
01291     assert(isa<AtomicRMWInst>(I) || isa<AtomicCmpXchgInst>(I));
01292 
01293     IRBuilder<> IRB(&I);
01294     Value *Addr = I.getOperand(0);
01295     Value *ShadowPtr = getShadowPtr(Addr, I.getType(), IRB);
01296 
01297     if (ClCheckAccessAddress)
01298       insertShadowCheck(Addr, &I);
01299 
01300     // Only test the conditional argument of cmpxchg instruction.
01301     // The other argument can potentially be uninitialized, but we can not
01302     // detect this situation reliably without possible false positives.
01303     if (isa<AtomicCmpXchgInst>(I))
01304       insertShadowCheck(I.getOperand(1), &I);
01305 
01306     IRB.CreateStore(getCleanShadow(&I), ShadowPtr);
01307 
01308     setShadow(&I, getCleanShadow(&I));
01309     setOrigin(&I, getCleanOrigin());
01310   }
01311 
01312   void visitAtomicRMWInst(AtomicRMWInst &I) {
01313     handleCASOrRMW(I);
01314     I.setOrdering(addReleaseOrdering(I.getOrdering()));
01315   }
01316 
01317   void visitAtomicCmpXchgInst(AtomicCmpXchgInst &I) {
01318     handleCASOrRMW(I);
01319     I.setSuccessOrdering(addReleaseOrdering(I.getSuccessOrdering()));
01320   }
01321 
01322   // Vector manipulation.
01323   void visitExtractElementInst(ExtractElementInst &I) {
01324     insertShadowCheck(I.getOperand(1), &I);
01325     IRBuilder<> IRB(&I);
01326     setShadow(&I, IRB.CreateExtractElement(getShadow(&I, 0), I.getOperand(1),
01327               "_msprop"));
01328     setOrigin(&I, getOrigin(&I, 0));
01329   }
01330 
01331   void visitInsertElementInst(InsertElementInst &I) {
01332     insertShadowCheck(I.getOperand(2), &I);
01333     IRBuilder<> IRB(&I);
01334     setShadow(&I, IRB.CreateInsertElement(getShadow(&I, 0), getShadow(&I, 1),
01335               I.getOperand(2), "_msprop"));
01336     setOriginForNaryOp(I);
01337   }
01338 
01339   void visitShuffleVectorInst(ShuffleVectorInst &I) {
01340     insertShadowCheck(I.getOperand(2), &I);
01341     IRBuilder<> IRB(&I);
01342     setShadow(&I, IRB.CreateShuffleVector(getShadow(&I, 0), getShadow(&I, 1),
01343               I.getOperand(2), "_msprop"));
01344     setOriginForNaryOp(I);
01345   }
01346 
01347   // Casts.
01348   void visitSExtInst(SExtInst &I) {
01349     IRBuilder<> IRB(&I);
01350     setShadow(&I, IRB.CreateSExt(getShadow(&I, 0), I.getType(), "_msprop"));
01351     setOrigin(&I, getOrigin(&I, 0));
01352   }
01353 
01354   void visitZExtInst(ZExtInst &I) {
01355     IRBuilder<> IRB(&I);
01356     setShadow(&I, IRB.CreateZExt(getShadow(&I, 0), I.getType(), "_msprop"));
01357     setOrigin(&I, getOrigin(&I, 0));
01358   }
01359 
01360   void visitTruncInst(TruncInst &I) {
01361     IRBuilder<> IRB(&I);
01362     setShadow(&I, IRB.CreateTrunc(getShadow(&I, 0), I.getType(), "_msprop"));
01363     setOrigin(&I, getOrigin(&I, 0));
01364   }
01365 
01366   void visitBitCastInst(BitCastInst &I) {
01367     // Special case: if this is the bitcast (there is exactly 1 allowed) between
01368     // a musttail call and a ret, don't instrument. New instructions are not
01369     // allowed after a musttail call.
01370     if (auto *CI = dyn_cast<CallInst>(I.getOperand(0)))
01371       if (CI->isMustTailCall())
01372         return;
01373     IRBuilder<> IRB(&I);
01374     setShadow(&I, IRB.CreateBitCast(getShadow(&I, 0), getShadowTy(&I)));
01375     setOrigin(&I, getOrigin(&I, 0));
01376   }
01377 
01378   void visitPtrToIntInst(PtrToIntInst &I) {
01379     IRBuilder<> IRB(&I);
01380     setShadow(&I, IRB.CreateIntCast(getShadow(&I, 0), getShadowTy(&I), false,
01381              "_msprop_ptrtoint"));
01382     setOrigin(&I, getOrigin(&I, 0));
01383   }
01384 
01385   void visitIntToPtrInst(IntToPtrInst &I) {
01386     IRBuilder<> IRB(&I);
01387     setShadow(&I, IRB.CreateIntCast(getShadow(&I, 0), getShadowTy(&I), false,
01388              "_msprop_inttoptr"));
01389     setOrigin(&I, getOrigin(&I, 0));
01390   }
01391 
01392   void visitFPToSIInst(CastInst& I) { handleShadowOr(I); }
01393   void visitFPToUIInst(CastInst& I) { handleShadowOr(I); }
01394   void visitSIToFPInst(CastInst& I) { handleShadowOr(I); }
01395   void visitUIToFPInst(CastInst& I) { handleShadowOr(I); }
01396   void visitFPExtInst(CastInst& I) { handleShadowOr(I); }
01397   void visitFPTruncInst(CastInst& I) { handleShadowOr(I); }
01398 
01399   /// \brief Propagate shadow for bitwise AND.
01400   ///
01401   /// This code is exact, i.e. if, for example, a bit in the left argument
01402   /// is defined and 0, then neither the value not definedness of the
01403   /// corresponding bit in B don't affect the resulting shadow.
01404   void visitAnd(BinaryOperator &I) {
01405     IRBuilder<> IRB(&I);
01406     //  "And" of 0 and a poisoned value results in unpoisoned value.
01407     //  1&1 => 1;     0&1 => 0;     p&1 => p;
01408     //  1&0 => 0;     0&0 => 0;     p&0 => 0;
01409     //  1&p => p;     0&p => 0;     p&p => p;
01410     //  S = (S1 & S2) | (V1 & S2) | (S1 & V2)
01411     Value *S1 = getShadow(&I, 0);
01412     Value *S2 = getShadow(&I, 1);
01413     Value *V1 = I.getOperand(0);
01414     Value *V2 = I.getOperand(1);
01415     if (V1->getType() != S1->getType()) {
01416       V1 = IRB.CreateIntCast(V1, S1->getType(), false);
01417       V2 = IRB.CreateIntCast(V2, S2->getType(), false);
01418     }
01419     Value *S1S2 = IRB.CreateAnd(S1, S2);
01420     Value *V1S2 = IRB.CreateAnd(V1, S2);
01421     Value *S1V2 = IRB.CreateAnd(S1, V2);
01422     setShadow(&I, IRB.CreateOr(S1S2, IRB.CreateOr(V1S2, S1V2)));
01423     setOriginForNaryOp(I);
01424   }
01425 
01426   void visitOr(BinaryOperator &I) {
01427     IRBuilder<> IRB(&I);
01428     //  "Or" of 1 and a poisoned value results in unpoisoned value.
01429     //  1|1 => 1;     0|1 => 1;     p|1 => 1;
01430     //  1|0 => 1;     0|0 => 0;     p|0 => p;
01431     //  1|p => 1;     0|p => p;     p|p => p;
01432     //  S = (S1 & S2) | (~V1 & S2) | (S1 & ~V2)
01433     Value *S1 = getShadow(&I, 0);
01434     Value *S2 = getShadow(&I, 1);
01435     Value *V1 = IRB.CreateNot(I.getOperand(0));
01436     Value *V2 = IRB.CreateNot(I.getOperand(1));
01437     if (V1->getType() != S1->getType()) {
01438       V1 = IRB.CreateIntCast(V1, S1->getType(), false);
01439       V2 = IRB.CreateIntCast(V2, S2->getType(), false);
01440     }
01441     Value *S1S2 = IRB.CreateAnd(S1, S2);
01442     Value *V1S2 = IRB.CreateAnd(V1, S2);
01443     Value *S1V2 = IRB.CreateAnd(S1, V2);
01444     setShadow(&I, IRB.CreateOr(S1S2, IRB.CreateOr(V1S2, S1V2)));
01445     setOriginForNaryOp(I);
01446   }
01447 
01448   /// \brief Default propagation of shadow and/or origin.
01449   ///
01450   /// This class implements the general case of shadow propagation, used in all
01451   /// cases where we don't know and/or don't care about what the operation
01452   /// actually does. It converts all input shadow values to a common type
01453   /// (extending or truncating as necessary), and bitwise OR's them.
01454   ///
01455   /// This is much cheaper than inserting checks (i.e. requiring inputs to be
01456   /// fully initialized), and less prone to false positives.
01457   ///
01458   /// This class also implements the general case of origin propagation. For a
01459   /// Nary operation, result origin is set to the origin of an argument that is
01460   /// not entirely initialized. If there is more than one such arguments, the
01461   /// rightmost of them is picked. It does not matter which one is picked if all
01462   /// arguments are initialized.
01463   template <bool CombineShadow>
01464   class Combiner {
01465     Value *Shadow;
01466     Value *Origin;
01467     IRBuilder<> &IRB;
01468     MemorySanitizerVisitor *MSV;
01469 
01470   public:
01471     Combiner(MemorySanitizerVisitor *MSV, IRBuilder<> &IRB) :
01472       Shadow(nullptr), Origin(nullptr), IRB(IRB), MSV(MSV) {}
01473 
01474     /// \brief Add a pair of shadow and origin values to the mix.
01475     Combiner &Add(Value *OpShadow, Value *OpOrigin) {
01476       if (CombineShadow) {
01477         assert(OpShadow);
01478         if (!Shadow)
01479           Shadow = OpShadow;
01480         else {
01481           OpShadow = MSV->CreateShadowCast(IRB, OpShadow, Shadow->getType());
01482           Shadow = IRB.CreateOr(Shadow, OpShadow, "_msprop");
01483         }
01484       }
01485 
01486       if (MSV->MS.TrackOrigins) {
01487         assert(OpOrigin);
01488         if (!Origin) {
01489           Origin = OpOrigin;
01490         } else {
01491           Constant *ConstOrigin = dyn_cast<Constant>(OpOrigin);
01492           // No point in adding something that might result in 0 origin value.
01493           if (!ConstOrigin || !ConstOrigin->isNullValue()) {
01494             Value *FlatShadow = MSV->convertToShadowTyNoVec(OpShadow, IRB);
01495             Value *Cond =
01496                 IRB.CreateICmpNE(FlatShadow, MSV->getCleanShadow(FlatShadow));
01497             Origin = IRB.CreateSelect(Cond, OpOrigin, Origin);
01498           }
01499         }
01500       }
01501       return *this;
01502     }
01503 
01504     /// \brief Add an application value to the mix.
01505     Combiner &Add(Value *V) {
01506       Value *OpShadow = MSV->getShadow(V);
01507       Value *OpOrigin = MSV->MS.TrackOrigins ? MSV->getOrigin(V) : nullptr;
01508       return Add(OpShadow, OpOrigin);
01509     }
01510 
01511     /// \brief Set the current combined values as the given instruction's shadow
01512     /// and origin.
01513     void Done(Instruction *I) {
01514       if (CombineShadow) {
01515         assert(Shadow);
01516         Shadow = MSV->CreateShadowCast(IRB, Shadow, MSV->getShadowTy(I));
01517         MSV->setShadow(I, Shadow);
01518       }
01519       if (MSV->MS.TrackOrigins) {
01520         assert(Origin);
01521         MSV->setOrigin(I, Origin);
01522       }
01523     }
01524   };
01525 
01526   typedef Combiner<true> ShadowAndOriginCombiner;
01527   typedef Combiner<false> OriginCombiner;
01528 
01529   /// \brief Propagate origin for arbitrary operation.
01530   void setOriginForNaryOp(Instruction &I) {
01531     if (!MS.TrackOrigins) return;
01532     IRBuilder<> IRB(&I);
01533     OriginCombiner OC(this, IRB);
01534     for (Instruction::op_iterator OI = I.op_begin(); OI != I.op_end(); ++OI)
01535       OC.Add(OI->get());
01536     OC.Done(&I);
01537   }
01538 
01539   size_t VectorOrPrimitiveTypeSizeInBits(Type *Ty) {
01540     assert(!(Ty->isVectorTy() && Ty->getScalarType()->isPointerTy()) &&
01541            "Vector of pointers is not a valid shadow type");
01542     return Ty->isVectorTy() ?
01543       Ty->getVectorNumElements() * Ty->getScalarSizeInBits() :
01544       Ty->getPrimitiveSizeInBits();
01545   }
01546 
01547   /// \brief Cast between two shadow types, extending or truncating as
01548   /// necessary.
01549   Value *CreateShadowCast(IRBuilder<> &IRB, Value *V, Type *dstTy,
01550                           bool Signed = false) {
01551     Type *srcTy = V->getType();
01552     if (dstTy->isIntegerTy() && srcTy->isIntegerTy())
01553       return IRB.CreateIntCast(V, dstTy, Signed);
01554     if (dstTy->isVectorTy() && srcTy->isVectorTy() &&
01555         dstTy->getVectorNumElements() == srcTy->getVectorNumElements())
01556       return IRB.CreateIntCast(V, dstTy, Signed);
01557     size_t srcSizeInBits = VectorOrPrimitiveTypeSizeInBits(srcTy);
01558     size_t dstSizeInBits = VectorOrPrimitiveTypeSizeInBits(dstTy);
01559     Value *V1 = IRB.CreateBitCast(V, Type::getIntNTy(*MS.C, srcSizeInBits));
01560     Value *V2 =
01561       IRB.CreateIntCast(V1, Type::getIntNTy(*MS.C, dstSizeInBits), Signed);
01562     return IRB.CreateBitCast(V2, dstTy);
01563     // TODO: handle struct types.
01564   }
01565 
01566   /// \brief Cast an application value to the type of its own shadow.
01567   Value *CreateAppToShadowCast(IRBuilder<> &IRB, Value *V) {
01568     Type *ShadowTy = getShadowTy(V);
01569     if (V->getType() == ShadowTy)
01570       return V;
01571     if (V->getType()->isPtrOrPtrVectorTy())
01572       return IRB.CreatePtrToInt(V, ShadowTy);
01573     else
01574       return IRB.CreateBitCast(V, ShadowTy);
01575   }
01576 
01577   /// \brief Propagate shadow for arbitrary operation.
01578   void handleShadowOr(Instruction &I) {
01579     IRBuilder<> IRB(&I);
01580     ShadowAndOriginCombiner SC(this, IRB);
01581     for (Instruction::op_iterator OI = I.op_begin(); OI != I.op_end(); ++OI)
01582       SC.Add(OI->get());
01583     SC.Done(&I);
01584   }
01585 
01586   // \brief Handle multiplication by constant.
01587   //
01588   // Handle a special case of multiplication by constant that may have one or
01589   // more zeros in the lower bits. This makes corresponding number of lower bits
01590   // of the result zero as well. We model it by shifting the other operand
01591   // shadow left by the required number of bits. Effectively, we transform
01592   // (X * (A * 2**B)) to ((X << B) * A) and instrument (X << B) as (Sx << B).
01593   // We use multiplication by 2**N instead of shift to cover the case of
01594   // multiplication by 0, which may occur in some elements of a vector operand.
01595   void handleMulByConstant(BinaryOperator &I, Constant *ConstArg,
01596                            Value *OtherArg) {
01597     Constant *ShadowMul;
01598     Type *Ty = ConstArg->getType();
01599     if (Ty->isVectorTy()) {
01600       unsigned NumElements = Ty->getVectorNumElements();
01601       Type *EltTy = Ty->getSequentialElementType();
01602       SmallVector<Constant *, 16> Elements;
01603       for (unsigned Idx = 0; Idx < NumElements; ++Idx) {
01604         if (ConstantInt *Elt =
01605                 dyn_cast<ConstantInt>(ConstArg->getAggregateElement(Idx))) {
01606           APInt V = Elt->getValue();
01607           APInt V2 = APInt(V.getBitWidth(), 1) << V.countTrailingZeros();
01608           Elements.push_back(ConstantInt::get(EltTy, V2));
01609         } else {
01610           Elements.push_back(ConstantInt::get(EltTy, 1));
01611         }
01612       }
01613       ShadowMul = ConstantVector::get(Elements);
01614     } else {
01615       if (ConstantInt *Elt = dyn_cast<ConstantInt>(ConstArg)) {
01616         APInt V = Elt->getValue();
01617         APInt V2 = APInt(V.getBitWidth(), 1) << V.countTrailingZeros();
01618         ShadowMul = ConstantInt::get(Ty, V2);
01619       } else {
01620         ShadowMul = ConstantInt::get(Ty, 1);
01621       }
01622     }
01623 
01624     IRBuilder<> IRB(&I);
01625     setShadow(&I,
01626               IRB.CreateMul(getShadow(OtherArg), ShadowMul, "msprop_mul_cst"));
01627     setOrigin(&I, getOrigin(OtherArg));
01628   }
01629 
01630   void visitMul(BinaryOperator &I) {
01631     Constant *constOp0 = dyn_cast<Constant>(I.getOperand(0));
01632     Constant *constOp1 = dyn_cast<Constant>(I.getOperand(1));
01633     if (constOp0 && !constOp1)
01634       handleMulByConstant(I, constOp0, I.getOperand(1));
01635     else if (constOp1 && !constOp0)
01636       handleMulByConstant(I, constOp1, I.getOperand(0));
01637     else
01638       handleShadowOr(I);
01639   }
01640 
01641   void visitFAdd(BinaryOperator &I) { handleShadowOr(I); }
01642   void visitFSub(BinaryOperator &I) { handleShadowOr(I); }
01643   void visitFMul(BinaryOperator &I) { handleShadowOr(I); }
01644   void visitAdd(BinaryOperator &I) { handleShadowOr(I); }
01645   void visitSub(BinaryOperator &I) { handleShadowOr(I); }
01646   void visitXor(BinaryOperator &I) { handleShadowOr(I); }
01647 
01648   void handleDiv(Instruction &I) {
01649     IRBuilder<> IRB(&I);
01650     // Strict on the second argument.
01651     insertShadowCheck(I.getOperand(1), &I);
01652     setShadow(&I, getShadow(&I, 0));
01653     setOrigin(&I, getOrigin(&I, 0));
01654   }
01655 
01656   void visitUDiv(BinaryOperator &I) { handleDiv(I); }
01657   void visitSDiv(BinaryOperator &I) { handleDiv(I); }
01658   void visitFDiv(BinaryOperator &I) { handleDiv(I); }
01659   void visitURem(BinaryOperator &I) { handleDiv(I); }
01660   void visitSRem(BinaryOperator &I) { handleDiv(I); }
01661   void visitFRem(BinaryOperator &I) { handleDiv(I); }
01662 
01663   /// \brief Instrument == and != comparisons.
01664   ///
01665   /// Sometimes the comparison result is known even if some of the bits of the
01666   /// arguments are not.
01667   void handleEqualityComparison(ICmpInst &I) {
01668     IRBuilder<> IRB(&I);
01669     Value *A = I.getOperand(0);
01670     Value *B = I.getOperand(1);
01671     Value *Sa = getShadow(A);
01672     Value *Sb = getShadow(B);
01673 
01674     // Get rid of pointers and vectors of pointers.
01675     // For ints (and vectors of ints), types of A and Sa match,
01676     // and this is a no-op.
01677     A = IRB.CreatePointerCast(A, Sa->getType());
01678     B = IRB.CreatePointerCast(B, Sb->getType());
01679 
01680     // A == B  <==>  (C = A^B) == 0
01681     // A != B  <==>  (C = A^B) != 0
01682     // Sc = Sa | Sb
01683     Value *C = IRB.CreateXor(A, B);
01684     Value *Sc = IRB.CreateOr(Sa, Sb);
01685     // Now dealing with i = (C == 0) comparison (or C != 0, does not matter now)
01686     // Result is defined if one of the following is true
01687     // * there is a defined 1 bit in C
01688     // * C is fully defined
01689     // Si = !(C & ~Sc) && Sc
01690     Value *Zero = Constant::getNullValue(Sc->getType());
01691     Value *MinusOne = Constant::getAllOnesValue(Sc->getType());
01692     Value *Si =
01693       IRB.CreateAnd(IRB.CreateICmpNE(Sc, Zero),
01694                     IRB.CreateICmpEQ(
01695                       IRB.CreateAnd(IRB.CreateXor(Sc, MinusOne), C), Zero));
01696     Si->setName("_msprop_icmp");
01697     setShadow(&I, Si);
01698     setOriginForNaryOp(I);
01699   }
01700 
01701   /// \brief Build the lowest possible value of V, taking into account V's
01702   ///        uninitialized bits.
01703   Value *getLowestPossibleValue(IRBuilder<> &IRB, Value *A, Value *Sa,
01704                                 bool isSigned) {
01705     if (isSigned) {
01706       // Split shadow into sign bit and other bits.
01707       Value *SaOtherBits = IRB.CreateLShr(IRB.CreateShl(Sa, 1), 1);
01708       Value *SaSignBit = IRB.CreateXor(Sa, SaOtherBits);
01709       // Maximise the undefined shadow bit, minimize other undefined bits.
01710       return
01711         IRB.CreateOr(IRB.CreateAnd(A, IRB.CreateNot(SaOtherBits)), SaSignBit);
01712     } else {
01713       // Minimize undefined bits.
01714       return IRB.CreateAnd(A, IRB.CreateNot(Sa));
01715     }
01716   }
01717 
01718   /// \brief Build the highest possible value of V, taking into account V's
01719   ///        uninitialized bits.
01720   Value *getHighestPossibleValue(IRBuilder<> &IRB, Value *A, Value *Sa,
01721                                 bool isSigned) {
01722     if (isSigned) {
01723       // Split shadow into sign bit and other bits.
01724       Value *SaOtherBits = IRB.CreateLShr(IRB.CreateShl(Sa, 1), 1);
01725       Value *SaSignBit = IRB.CreateXor(Sa, SaOtherBits);
01726       // Minimise the undefined shadow bit, maximise other undefined bits.
01727       return
01728         IRB.CreateOr(IRB.CreateAnd(A, IRB.CreateNot(SaSignBit)), SaOtherBits);
01729     } else {
01730       // Maximize undefined bits.
01731       return IRB.CreateOr(A, Sa);
01732     }
01733   }
01734 
01735   /// \brief Instrument relational comparisons.
01736   ///
01737   /// This function does exact shadow propagation for all relational
01738   /// comparisons of integers, pointers and vectors of those.
01739   /// FIXME: output seems suboptimal when one of the operands is a constant
01740   void handleRelationalComparisonExact(ICmpInst &I) {
01741     IRBuilder<> IRB(&I);
01742     Value *A = I.getOperand(0);
01743     Value *B = I.getOperand(1);
01744     Value *Sa = getShadow(A);
01745     Value *Sb = getShadow(B);
01746 
01747     // Get rid of pointers and vectors of pointers.
01748     // For ints (and vectors of ints), types of A and Sa match,
01749     // and this is a no-op.
01750     A = IRB.CreatePointerCast(A, Sa->getType());
01751     B = IRB.CreatePointerCast(B, Sb->getType());
01752 
01753     // Let [a0, a1] be the interval of possible values of A, taking into account
01754     // its undefined bits. Let [b0, b1] be the interval of possible values of B.
01755     // Then (A cmp B) is defined iff (a0 cmp b1) == (a1 cmp b0).
01756     bool IsSigned = I.isSigned();
01757     Value *S1 = IRB.CreateICmp(I.getPredicate(),
01758                                getLowestPossibleValue(IRB, A, Sa, IsSigned),
01759                                getHighestPossibleValue(IRB, B, Sb, IsSigned));
01760     Value *S2 = IRB.CreateICmp(I.getPredicate(),
01761                                getHighestPossibleValue(IRB, A, Sa, IsSigned),
01762                                getLowestPossibleValue(IRB, B, Sb, IsSigned));
01763     Value *Si = IRB.CreateXor(S1, S2);
01764     setShadow(&I, Si);
01765     setOriginForNaryOp(I);
01766   }
01767 
01768   /// \brief Instrument signed relational comparisons.
01769   ///
01770   /// Handle sign bit tests: x<0, x>=0, x<=-1, x>-1 by propagating the highest
01771   /// bit of the shadow. Everything else is delegated to handleShadowOr().
01772   void handleSignedRelationalComparison(ICmpInst &I) {
01773     Constant *constOp;
01774     Value *op = nullptr;
01775     CmpInst::Predicate pre;
01776     if ((constOp = dyn_cast<Constant>(I.getOperand(1)))) {
01777       op = I.getOperand(0);
01778       pre = I.getPredicate();
01779     } else if ((constOp = dyn_cast<Constant>(I.getOperand(0)))) {
01780       op = I.getOperand(1);
01781       pre = I.getSwappedPredicate();
01782     } else {
01783       handleShadowOr(I);
01784       return;
01785     }
01786 
01787     if ((constOp->isNullValue() &&
01788          (pre == CmpInst::ICMP_SLT || pre == CmpInst::ICMP_SGE)) ||
01789         (constOp->isAllOnesValue() &&
01790          (pre == CmpInst::ICMP_SGT || pre == CmpInst::ICMP_SLE))) {
01791       IRBuilder<> IRB(&I);
01792       Value *Shadow = IRB.CreateICmpSLT(getShadow(op), getCleanShadow(op),
01793                                         "_msprop_icmp_s");
01794       setShadow(&I, Shadow);
01795       setOrigin(&I, getOrigin(op));
01796     } else {
01797       handleShadowOr(I);
01798     }
01799   }
01800 
01801   void visitICmpInst(ICmpInst &I) {
01802     if (!ClHandleICmp) {
01803       handleShadowOr(I);
01804       return;
01805     }
01806     if (I.isEquality()) {
01807       handleEqualityComparison(I);
01808       return;
01809     }
01810 
01811     assert(I.isRelational());
01812     if (ClHandleICmpExact) {
01813       handleRelationalComparisonExact(I);
01814       return;
01815     }
01816     if (I.isSigned()) {
01817       handleSignedRelationalComparison(I);
01818       return;
01819     }
01820 
01821     assert(I.isUnsigned());
01822     if ((isa<Constant>(I.getOperand(0)) || isa<Constant>(I.getOperand(1)))) {
01823       handleRelationalComparisonExact(I);
01824       return;
01825     }
01826 
01827     handleShadowOr(I);
01828   }
01829 
01830   void visitFCmpInst(FCmpInst &I) {
01831     handleShadowOr(I);
01832   }
01833 
01834   void handleShift(BinaryOperator &I) {
01835     IRBuilder<> IRB(&I);
01836     // If any of the S2 bits are poisoned, the whole thing is poisoned.
01837     // Otherwise perform the same shift on S1.
01838     Value *S1 = getShadow(&I, 0);
01839     Value *S2 = getShadow(&I, 1);
01840     Value *S2Conv = IRB.CreateSExt(IRB.CreateICmpNE(S2, getCleanShadow(S2)),
01841                                    S2->getType());
01842     Value *V2 = I.getOperand(1);
01843     Value *Shift = IRB.CreateBinOp(I.getOpcode(), S1, V2);
01844     setShadow(&I, IRB.CreateOr(Shift, S2Conv));
01845     setOriginForNaryOp(I);
01846   }
01847 
01848   void visitShl(BinaryOperator &I) { handleShift(I); }
01849   void visitAShr(BinaryOperator &I) { handleShift(I); }
01850   void visitLShr(BinaryOperator &I) { handleShift(I); }
01851 
01852   /// \brief Instrument llvm.memmove
01853   ///
01854   /// At this point we don't know if llvm.memmove will be inlined or not.
01855   /// If we don't instrument it and it gets inlined,
01856   /// our interceptor will not kick in and we will lose the memmove.
01857   /// If we instrument the call here, but it does not get inlined,
01858   /// we will memove the shadow twice: which is bad in case
01859   /// of overlapping regions. So, we simply lower the intrinsic to a call.
01860   ///
01861   /// Similar situation exists for memcpy and memset.
01862   void visitMemMoveInst(MemMoveInst &I) {
01863     IRBuilder<> IRB(&I);
01864     IRB.CreateCall(
01865         MS.MemmoveFn,
01866         {IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()),
01867          IRB.CreatePointerCast(I.getArgOperand(1), IRB.getInt8PtrTy()),
01868          IRB.CreateIntCast(I.getArgOperand(2), MS.IntptrTy, false)});
01869     I.eraseFromParent();
01870   }
01871 
01872   // Similar to memmove: avoid copying shadow twice.
01873   // This is somewhat unfortunate as it may slowdown small constant memcpys.
01874   // FIXME: consider doing manual inline for small constant sizes and proper
01875   // alignment.
01876   void visitMemCpyInst(MemCpyInst &I) {
01877     IRBuilder<> IRB(&I);
01878     IRB.CreateCall(
01879         MS.MemcpyFn,
01880         {IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()),
01881          IRB.CreatePointerCast(I.getArgOperand(1), IRB.getInt8PtrTy()),
01882          IRB.CreateIntCast(I.getArgOperand(2), MS.IntptrTy, false)});
01883     I.eraseFromParent();
01884   }
01885 
01886   // Same as memcpy.
01887   void visitMemSetInst(MemSetInst &I) {
01888     IRBuilder<> IRB(&I);
01889     IRB.CreateCall(
01890         MS.MemsetFn,
01891         {IRB.CreatePointerCast(I.getArgOperand(0), IRB.getInt8PtrTy()),
01892          IRB.CreateIntCast(I.getArgOperand(1), IRB.getInt32Ty(), false),
01893          IRB.CreateIntCast(I.getArgOperand(2), MS.IntptrTy, false)});
01894     I.eraseFromParent();
01895   }
01896 
01897   void visitVAStartInst(VAStartInst &I) {
01898     VAHelper->visitVAStartInst(I);
01899   }
01900 
01901   void visitVACopyInst(VACopyInst &I) {
01902     VAHelper->visitVACopyInst(I);
01903   }
01904 
01905   /// \brief Handle vector store-like intrinsics.
01906   ///
01907   /// Instrument intrinsics that look like a simple SIMD store: writes memory,
01908   /// has 1 pointer argument and 1 vector argument, returns void.
01909   bool handleVectorStoreIntrinsic(IntrinsicInst &I) {
01910     IRBuilder<> IRB(&I);
01911     Value* Addr = I.getArgOperand(0);
01912     Value *Shadow = getShadow(&I, 1);
01913     Value *ShadowPtr = getShadowPtr(Addr, Shadow->getType(), IRB);
01914 
01915     // We don't know the pointer alignment (could be unaligned SSE store!).
01916     // Have to assume to worst case.
01917     IRB.CreateAlignedStore(Shadow, ShadowPtr, 1);
01918 
01919     if (ClCheckAccessAddress)
01920       insertShadowCheck(Addr, &I);
01921 
01922     // FIXME: use ClStoreCleanOrigin
01923     // FIXME: factor out common code from materializeStores
01924     if (MS.TrackOrigins)
01925       IRB.CreateStore(getOrigin(&I, 1), getOriginPtr(Addr, IRB, 1));
01926     return true;
01927   }
01928 
01929   /// \brief Handle vector load-like intrinsics.
01930   ///
01931   /// Instrument intrinsics that look like a simple SIMD load: reads memory,
01932   /// has 1 pointer argument, returns a vector.
01933   bool handleVectorLoadIntrinsic(IntrinsicInst &I) {
01934     IRBuilder<> IRB(&I);
01935     Value *Addr = I.getArgOperand(0);
01936 
01937     Type *ShadowTy = getShadowTy(&I);
01938     if (PropagateShadow) {
01939       Value *ShadowPtr = getShadowPtr(Addr, ShadowTy, IRB);
01940       // We don't know the pointer alignment (could be unaligned SSE load!).
01941       // Have to assume to worst case.
01942       setShadow(&I, IRB.CreateAlignedLoad(ShadowPtr, 1, "_msld"));
01943     } else {
01944       setShadow(&I, getCleanShadow(&I));
01945     }
01946 
01947     if (ClCheckAccessAddress)
01948       insertShadowCheck(Addr, &I);
01949 
01950     if (MS.TrackOrigins) {
01951       if (PropagateShadow)
01952         setOrigin(&I, IRB.CreateLoad(getOriginPtr(Addr, IRB, 1)));
01953       else
01954         setOrigin(&I, getCleanOrigin());
01955     }
01956     return true;
01957   }
01958 
01959   /// \brief Handle (SIMD arithmetic)-like intrinsics.
01960   ///
01961   /// Instrument intrinsics with any number of arguments of the same type,
01962   /// equal to the return type. The type should be simple (no aggregates or
01963   /// pointers; vectors are fine).
01964   /// Caller guarantees that this intrinsic does not access memory.
01965   bool maybeHandleSimpleNomemIntrinsic(IntrinsicInst &I) {
01966     Type *RetTy = I.getType();
01967     if (!(RetTy->isIntOrIntVectorTy() ||
01968           RetTy->isFPOrFPVectorTy() ||
01969           RetTy->isX86_MMXTy()))
01970       return false;
01971 
01972     unsigned NumArgOperands = I.getNumArgOperands();
01973 
01974     for (unsigned i = 0; i < NumArgOperands; ++i) {
01975       Type *Ty = I.getArgOperand(i)->getType();
01976       if (Ty != RetTy)
01977         return false;
01978     }
01979 
01980     IRBuilder<> IRB(&I);
01981     ShadowAndOriginCombiner SC(this, IRB);
01982     for (unsigned i = 0; i < NumArgOperands; ++i)
01983       SC.Add(I.getArgOperand(i));
01984     SC.Done(&I);
01985 
01986     return true;
01987   }
01988 
01989   /// \brief Heuristically instrument unknown intrinsics.
01990   ///
01991   /// The main purpose of this code is to do something reasonable with all
01992   /// random intrinsics we might encounter, most importantly - SIMD intrinsics.
01993   /// We recognize several classes of intrinsics by their argument types and
01994   /// ModRefBehaviour and apply special intrumentation when we are reasonably
01995   /// sure that we know what the intrinsic does.
01996   ///
01997   /// We special-case intrinsics where this approach fails. See llvm.bswap
01998   /// handling as an example of that.
01999   bool handleUnknownIntrinsic(IntrinsicInst &I) {
02000     unsigned NumArgOperands = I.getNumArgOperands();
02001     if (NumArgOperands == 0)
02002       return false;
02003 
02004     if (NumArgOperands == 2 &&
02005         I.getArgOperand(0)->getType()->isPointerTy() &&
02006         I.getArgOperand(1)->getType()->isVectorTy() &&
02007         I.getType()->isVoidTy() &&
02008         !I.onlyReadsMemory()) {
02009       // This looks like a vector store.
02010       return handleVectorStoreIntrinsic(I);
02011     }
02012 
02013     if (NumArgOperands == 1 &&
02014         I.getArgOperand(0)->getType()->isPointerTy() &&
02015         I.getType()->isVectorTy() &&
02016         I.onlyReadsMemory()) {
02017       // This looks like a vector load.
02018       return handleVectorLoadIntrinsic(I);
02019     }
02020 
02021     if (I.doesNotAccessMemory())
02022       if (maybeHandleSimpleNomemIntrinsic(I))
02023         return true;
02024 
02025     // FIXME: detect and handle SSE maskstore/maskload
02026     return false;
02027   }
02028 
02029   void handleBswap(IntrinsicInst &I) {
02030     IRBuilder<> IRB(&I);
02031     Value *Op = I.getArgOperand(0);
02032     Type *OpType = Op->getType();
02033     Function *BswapFunc = Intrinsic::getDeclaration(
02034       F.getParent(), Intrinsic::bswap, makeArrayRef(&OpType, 1));
02035     setShadow(&I, IRB.CreateCall(BswapFunc, getShadow(Op)));
02036     setOrigin(&I, getOrigin(Op));
02037   }
02038 
02039   // \brief Instrument vector convert instrinsic.
02040   //
02041   // This function instruments intrinsics like cvtsi2ss:
02042   // %Out = int_xxx_cvtyyy(%ConvertOp)
02043   // or
02044   // %Out = int_xxx_cvtyyy(%CopyOp, %ConvertOp)
02045   // Intrinsic converts \p NumUsedElements elements of \p ConvertOp to the same
02046   // number \p Out elements, and (if has 2 arguments) copies the rest of the
02047   // elements from \p CopyOp.
02048   // In most cases conversion involves floating-point value which may trigger a
02049   // hardware exception when not fully initialized. For this reason we require
02050   // \p ConvertOp[0:NumUsedElements] to be fully initialized and trap otherwise.
02051   // We copy the shadow of \p CopyOp[NumUsedElements:] to \p
02052   // Out[NumUsedElements:]. This means that intrinsics without \p CopyOp always
02053   // return a fully initialized value.
02054   void handleVectorConvertIntrinsic(IntrinsicInst &I, int NumUsedElements) {
02055     IRBuilder<> IRB(&I);
02056     Value *CopyOp, *ConvertOp;
02057 
02058     switch (I.getNumArgOperands()) {
02059     case 3:
02060       assert(isa<ConstantInt>(I.getArgOperand(2)) && "Invalid rounding mode");
02061     case 2:
02062       CopyOp = I.getArgOperand(0);
02063       ConvertOp = I.getArgOperand(1);
02064       break;
02065     case 1:
02066       ConvertOp = I.getArgOperand(0);
02067       CopyOp = nullptr;
02068       break;
02069     default:
02070       llvm_unreachable("Cvt intrinsic with unsupported number of arguments.");
02071     }
02072 
02073     // The first *NumUsedElements* elements of ConvertOp are converted to the
02074     // same number of output elements. The rest of the output is copied from
02075     // CopyOp, or (if not available) filled with zeroes.
02076     // Combine shadow for elements of ConvertOp that are used in this operation,
02077     // and insert a check.
02078     // FIXME: consider propagating shadow of ConvertOp, at least in the case of
02079     // int->any conversion.
02080     Value *ConvertShadow = getShadow(ConvertOp);
02081     Value *AggShadow = nullptr;
02082     if (ConvertOp->getType()->isVectorTy()) {
02083       AggShadow = IRB.CreateExtractElement(
02084           ConvertShadow, ConstantInt::get(IRB.getInt32Ty(), 0));
02085       for (int i = 1; i < NumUsedElements; ++i) {
02086         Value *MoreShadow = IRB.CreateExtractElement(
02087             ConvertShadow, ConstantInt::get(IRB.getInt32Ty(), i));
02088         AggShadow = IRB.CreateOr(AggShadow, MoreShadow);
02089       }
02090     } else {
02091       AggShadow = ConvertShadow;
02092     }
02093     assert(AggShadow->getType()->isIntegerTy());
02094     insertShadowCheck(AggShadow, getOrigin(ConvertOp), &I);
02095 
02096     // Build result shadow by zero-filling parts of CopyOp shadow that come from
02097     // ConvertOp.
02098     if (CopyOp) {
02099       assert(CopyOp->getType() == I.getType());
02100       assert(CopyOp->getType()->isVectorTy());
02101       Value *ResultShadow = getShadow(CopyOp);
02102       Type *EltTy = ResultShadow->getType()->getVectorElementType();
02103       for (int i = 0; i < NumUsedElements; ++i) {
02104         ResultShadow = IRB.CreateInsertElement(
02105             ResultShadow, ConstantInt::getNullValue(EltTy),
02106             ConstantInt::get(IRB.getInt32Ty(), i));
02107       }
02108       setShadow(&I, ResultShadow);
02109       setOrigin(&I, getOrigin(CopyOp));
02110     } else {
02111       setShadow(&I, getCleanShadow(&I));
02112       setOrigin(&I, getCleanOrigin());
02113     }
02114   }
02115 
02116   // Given a scalar or vector, extract lower 64 bits (or less), and return all
02117   // zeroes if it is zero, and all ones otherwise.
02118   Value *Lower64ShadowExtend(IRBuilder<> &IRB, Value *S, Type *T) {
02119     if (S->getType()->isVectorTy())
02120       S = CreateShadowCast(IRB, S, IRB.getInt64Ty(), /* Signed */ true);
02121     assert(S->getType()->getPrimitiveSizeInBits() <= 64);
02122     Value *S2 = IRB.CreateICmpNE(S, getCleanShadow(S));
02123     return CreateShadowCast(IRB, S2, T, /* Signed */ true);
02124   }
02125 
02126   Value *VariableShadowExtend(IRBuilder<> &IRB, Value *S) {
02127     Type *T = S->getType();
02128     assert(T->isVectorTy());
02129     Value *S2 = IRB.CreateICmpNE(S, getCleanShadow(S));
02130     return IRB.CreateSExt(S2, T);
02131   }
02132 
02133   // \brief Instrument vector shift instrinsic.
02134   //
02135   // This function instruments intrinsics like int_x86_avx2_psll_w.
02136   // Intrinsic shifts %In by %ShiftSize bits.
02137   // %ShiftSize may be a vector. In that case the lower 64 bits determine shift
02138   // size, and the rest is ignored. Behavior is defined even if shift size is
02139   // greater than register (or field) width.
02140   void handleVectorShiftIntrinsic(IntrinsicInst &I, bool Variable) {
02141     assert(I.getNumArgOperands() == 2);
02142     IRBuilder<> IRB(&I);
02143     // If any of the S2 bits are poisoned, the whole thing is poisoned.
02144     // Otherwise perform the same shift on S1.
02145     Value *S1 = getShadow(&I, 0);
02146     Value *S2 = getShadow(&I, 1);
02147     Value *S2Conv = Variable ? VariableShadowExtend(IRB, S2)
02148                              : Lower64ShadowExtend(IRB, S2, getShadowTy(&I));
02149     Value *V1 = I.getOperand(0);
02150     Value *V2 = I.getOperand(1);
02151     Value *Shift = IRB.CreateCall(I.getCalledValue(),
02152                                   {IRB.CreateBitCast(S1, V1->getType()), V2});
02153     Shift = IRB.CreateBitCast(Shift, getShadowTy(&I));
02154     setShadow(&I, IRB.CreateOr(Shift, S2Conv));
02155     setOriginForNaryOp(I);
02156   }
02157 
02158   // \brief Get an X86_MMX-sized vector type.
02159   Type *getMMXVectorTy(unsigned EltSizeInBits) {
02160     const unsigned X86_MMXSizeInBits = 64;
02161     return VectorType::get(IntegerType::get(*MS.C, EltSizeInBits),
02162                            X86_MMXSizeInBits / EltSizeInBits);
02163   }
02164 
02165   // \brief Returns a signed counterpart for an (un)signed-saturate-and-pack
02166   // intrinsic.
02167   Intrinsic::ID getSignedPackIntrinsic(Intrinsic::ID id) {
02168     switch (id) {
02169       case llvm::Intrinsic::x86_sse2_packsswb_128:
02170       case llvm::Intrinsic::x86_sse2_packuswb_128:
02171         return llvm::Intrinsic::x86_sse2_packsswb_128;
02172 
02173       case llvm::Intrinsic::x86_sse2_packssdw_128:
02174       case llvm::Intrinsic::x86_sse41_packusdw:
02175         return llvm::Intrinsic::x86_sse2_packssdw_128;
02176 
02177       case llvm::Intrinsic::x86_avx2_packsswb:
02178       case llvm::Intrinsic::x86_avx2_packuswb:
02179         return llvm::Intrinsic::x86_avx2_packsswb;
02180 
02181       case llvm::Intrinsic::x86_avx2_packssdw:
02182       case llvm::Intrinsic::x86_avx2_packusdw:
02183         return llvm::Intrinsic::x86_avx2_packssdw;
02184 
02185       case llvm::Intrinsic::x86_mmx_packsswb:
02186       case llvm::Intrinsic::x86_mmx_packuswb:
02187         return llvm::Intrinsic::x86_mmx_packsswb;
02188 
02189       case llvm::Intrinsic::x86_mmx_packssdw:
02190         return llvm::Intrinsic::x86_mmx_packssdw;
02191       default:
02192         llvm_unreachable("unexpected intrinsic id");
02193     }
02194   }
02195 
02196   // \brief Instrument vector pack instrinsic.
02197   //
02198   // This function instruments intrinsics like x86_mmx_packsswb, that
02199   // packs elements of 2 input vectors into half as many bits with saturation.
02200   // Shadow is propagated with the signed variant of the same intrinsic applied
02201   // to sext(Sa != zeroinitializer), sext(Sb != zeroinitializer).
02202   // EltSizeInBits is used only for x86mmx arguments.
02203   void handleVectorPackIntrinsic(IntrinsicInst &I, unsigned EltSizeInBits = 0) {
02204     assert(I.getNumArgOperands() == 2);
02205     bool isX86_MMX = I.getOperand(0)->getType()->isX86_MMXTy();
02206     IRBuilder<> IRB(&I);
02207     Value *S1 = getShadow(&I, 0);
02208     Value *S2 = getShadow(&I, 1);
02209     assert(isX86_MMX || S1->getType()->isVectorTy());
02210 
02211     // SExt and ICmpNE below must apply to individual elements of input vectors.
02212     // In case of x86mmx arguments, cast them to appropriate vector types and
02213     // back.
02214     Type *T = isX86_MMX ? getMMXVectorTy(EltSizeInBits) : S1->getType();
02215     if (isX86_MMX) {
02216       S1 = IRB.CreateBitCast(S1, T);
02217       S2 = IRB.CreateBitCast(S2, T);
02218     }
02219     Value *S1_ext = IRB.CreateSExt(
02220         IRB.CreateICmpNE(S1, llvm::Constant::getNullValue(T)), T);
02221     Value *S2_ext = IRB.CreateSExt(
02222         IRB.CreateICmpNE(S2, llvm::Constant::getNullValue(T)), T);
02223     if (isX86_MMX) {
02224       Type *X86_MMXTy = Type::getX86_MMXTy(*MS.C);
02225       S1_ext = IRB.CreateBitCast(S1_ext, X86_MMXTy);
02226       S2_ext = IRB.CreateBitCast(S2_ext, X86_MMXTy);
02227     }
02228 
02229     Function *ShadowFn = Intrinsic::getDeclaration(
02230         F.getParent(), getSignedPackIntrinsic(I.getIntrinsicID()));
02231 
02232     Value *S =
02233         IRB.CreateCall(ShadowFn, {S1_ext, S2_ext}, "_msprop_vector_pack");
02234     if (isX86_MMX) S = IRB.CreateBitCast(S, getShadowTy(&I));
02235     setShadow(&I, S);
02236     setOriginForNaryOp(I);
02237   }
02238 
02239   // \brief Instrument sum-of-absolute-differencies intrinsic.
02240   void handleVectorSadIntrinsic(IntrinsicInst &I) {
02241     const unsigned SignificantBitsPerResultElement = 16;
02242     bool isX86_MMX = I.getOperand(0)->getType()->isX86_MMXTy();
02243     Type *ResTy = isX86_MMX ? IntegerType::get(*MS.C, 64) : I.getType();
02244     unsigned ZeroBitsPerResultElement =
02245         ResTy->getScalarSizeInBits() - SignificantBitsPerResultElement;
02246 
02247     IRBuilder<> IRB(&I);
02248     Value *S = IRB.CreateOr(getShadow(&I, 0), getShadow(&I, 1));
02249     S = IRB.CreateBitCast(S, ResTy);
02250     S = IRB.CreateSExt(IRB.CreateICmpNE(S, Constant::getNullValue(ResTy)),
02251                        ResTy);
02252     S = IRB.CreateLShr(S, ZeroBitsPerResultElement);
02253     S = IRB.CreateBitCast(S, getShadowTy(&I));
02254     setShadow(&I, S);
02255     setOriginForNaryOp(I);
02256   }
02257 
02258   // \brief Instrument multiply-add intrinsic.
02259   void handleVectorPmaddIntrinsic(IntrinsicInst &I,
02260                                   unsigned EltSizeInBits = 0) {
02261     bool isX86_MMX = I.getOperand(0)->getType()->isX86_MMXTy();
02262     Type *ResTy = isX86_MMX ? getMMXVectorTy(EltSizeInBits * 2) : I.getType();
02263     IRBuilder<> IRB(&I);
02264     Value *S = IRB.CreateOr(getShadow(&I, 0), getShadow(&I, 1));
02265     S = IRB.CreateBitCast(S, ResTy);
02266     S = IRB.CreateSExt(IRB.CreateICmpNE(S, Constant::getNullValue(ResTy)),
02267                        ResTy);
02268     S = IRB.CreateBitCast(S, getShadowTy(&I));
02269     setShadow(&I, S);
02270     setOriginForNaryOp(I);
02271   }
02272 
02273   void visitIntrinsicInst(IntrinsicInst &I) {
02274     switch (I.getIntrinsicID()) {
02275     case llvm::Intrinsic::bswap:
02276       handleBswap(I);
02277       break;
02278     case llvm::Intrinsic::x86_avx512_cvtsd2usi64:
02279     case llvm::Intrinsic::x86_avx512_cvtsd2usi:
02280     case llvm::Intrinsic::x86_avx512_cvtss2usi64:
02281     case llvm::Intrinsic::x86_avx512_cvtss2usi:
02282     case llvm::Intrinsic::x86_avx512_cvttss2usi64:
02283     case llvm::Intrinsic::x86_avx512_cvttss2usi:
02284     case llvm::Intrinsic::x86_avx512_cvttsd2usi64:
02285     case llvm::Intrinsic::x86_avx512_cvttsd2usi:
02286     case llvm::Intrinsic::x86_avx512_cvtusi2sd:
02287     case llvm::Intrinsic::x86_avx512_cvtusi2ss:
02288     case llvm::Intrinsic::x86_avx512_cvtusi642sd:
02289     case llvm::Intrinsic::x86_avx512_cvtusi642ss:
02290     case llvm::Intrinsic::x86_sse2_cvtsd2si64:
02291     case llvm::Intrinsic::x86_sse2_cvtsd2si:
02292     case llvm::Intrinsic::x86_sse2_cvtsd2ss:
02293     case llvm::Intrinsic::x86_sse2_cvtsi2sd:
02294     case llvm::Intrinsic::x86_sse2_cvtsi642sd:
02295     case llvm::Intrinsic::x86_sse2_cvtss2sd:
02296     case llvm::Intrinsic::x86_sse2_cvttsd2si64:
02297     case llvm::Intrinsic::x86_sse2_cvttsd2si:
02298     case llvm::Intrinsic::x86_sse_cvtsi2ss:
02299     case llvm::Intrinsic::x86_sse_cvtsi642ss:
02300     case llvm::Intrinsic::x86_sse_cvtss2si64:
02301     case llvm::Intrinsic::x86_sse_cvtss2si:
02302     case llvm::Intrinsic::x86_sse_cvttss2si64:
02303     case llvm::Intrinsic::x86_sse_cvttss2si:
02304       handleVectorConvertIntrinsic(I, 1);
02305       break;
02306     case llvm::Intrinsic::x86_sse2_cvtdq2pd:
02307     case llvm::Intrinsic::x86_sse2_cvtps2pd:
02308     case llvm::Intrinsic::x86_sse_cvtps2pi:
02309     case llvm::Intrinsic::x86_sse_cvttps2pi:
02310       handleVectorConvertIntrinsic(I, 2);
02311       break;
02312     case llvm::Intrinsic::x86_avx2_psll_w:
02313     case llvm::Intrinsic::x86_avx2_psll_d:
02314     case llvm::Intrinsic::x86_avx2_psll_q:
02315     case llvm::Intrinsic::x86_avx2_pslli_w:
02316     case llvm::Intrinsic::x86_avx2_pslli_d:
02317     case llvm::Intrinsic::x86_avx2_pslli_q:
02318     case llvm::Intrinsic::x86_avx2_psrl_w:
02319     case llvm::Intrinsic::x86_avx2_psrl_d:
02320     case llvm::Intrinsic::x86_avx2_psrl_q:
02321     case llvm::Intrinsic::x86_avx2_psra_w:
02322     case llvm::Intrinsic::x86_avx2_psra_d:
02323     case llvm::Intrinsic::x86_avx2_psrli_w:
02324     case llvm::Intrinsic::x86_avx2_psrli_d:
02325     case llvm::Intrinsic::x86_avx2_psrli_q:
02326     case llvm::Intrinsic::x86_avx2_psrai_w:
02327     case llvm::Intrinsic::x86_avx2_psrai_d:
02328     case llvm::Intrinsic::x86_sse2_psll_w:
02329     case llvm::Intrinsic::x86_sse2_psll_d:
02330     case llvm::Intrinsic::x86_sse2_psll_q:
02331     case llvm::Intrinsic::x86_sse2_pslli_w:
02332     case llvm::Intrinsic::x86_sse2_pslli_d:
02333     case llvm::Intrinsic::x86_sse2_pslli_q:
02334     case llvm::Intrinsic::x86_sse2_psrl_w:
02335     case llvm::Intrinsic::x86_sse2_psrl_d:
02336     case llvm::Intrinsic::x86_sse2_psrl_q:
02337     case llvm::Intrinsic::x86_sse2_psra_w:
02338     case llvm::Intrinsic::x86_sse2_psra_d:
02339     case llvm::Intrinsic::x86_sse2_psrli_w:
02340     case llvm::Intrinsic::x86_sse2_psrli_d:
02341     case llvm::Intrinsic::x86_sse2_psrli_q:
02342     case llvm::Intrinsic::x86_sse2_psrai_w:
02343     case llvm::Intrinsic::x86_sse2_psrai_d:
02344     case llvm::Intrinsic::x86_mmx_psll_w:
02345     case llvm::Intrinsic::x86_mmx_psll_d:
02346     case llvm::Intrinsic::x86_mmx_psll_q:
02347     case llvm::Intrinsic::x86_mmx_pslli_w:
02348     case llvm::Intrinsic::x86_mmx_pslli_d:
02349     case llvm::Intrinsic::x86_mmx_pslli_q:
02350     case llvm::Intrinsic::x86_mmx_psrl_w:
02351     case llvm::Intrinsic::x86_mmx_psrl_d:
02352     case llvm::Intrinsic::x86_mmx_psrl_q:
02353     case llvm::Intrinsic::x86_mmx_psra_w:
02354     case llvm::Intrinsic::x86_mmx_psra_d:
02355     case llvm::Intrinsic::x86_mmx_psrli_w:
02356     case llvm::Intrinsic::x86_mmx_psrli_d:
02357     case llvm::Intrinsic::x86_mmx_psrli_q:
02358     case llvm::Intrinsic::x86_mmx_psrai_w:
02359     case llvm::Intrinsic::x86_mmx_psrai_d:
02360       handleVectorShiftIntrinsic(I, /* Variable */ false);
02361       break;
02362     case llvm::Intrinsic::x86_avx2_psllv_d:
02363     case llvm::Intrinsic::x86_avx2_psllv_d_256:
02364     case llvm::Intrinsic::x86_avx2_psllv_q:
02365     case llvm::Intrinsic::x86_avx2_psllv_q_256:
02366     case llvm::Intrinsic::x86_avx2_psrlv_d:
02367     case llvm::Intrinsic::x86_avx2_psrlv_d_256:
02368     case llvm::Intrinsic::x86_avx2_psrlv_q:
02369     case llvm::Intrinsic::x86_avx2_psrlv_q_256:
02370     case llvm::Intrinsic::x86_avx2_psrav_d:
02371     case llvm::Intrinsic::x86_avx2_psrav_d_256:
02372       handleVectorShiftIntrinsic(I, /* Variable */ true);
02373       break;
02374 
02375     case llvm::Intrinsic::x86_sse2_packsswb_128:
02376     case llvm::Intrinsic::x86_sse2_packssdw_128:
02377     case llvm::Intrinsic::x86_sse2_packuswb_128:
02378     case llvm::Intrinsic::x86_sse41_packusdw:
02379     case llvm::Intrinsic::x86_avx2_packsswb:
02380     case llvm::Intrinsic::x86_avx2_packssdw:
02381     case llvm::Intrinsic::x86_avx2_packuswb:
02382     case llvm::Intrinsic::x86_avx2_packusdw:
02383       handleVectorPackIntrinsic(I);
02384       break;
02385 
02386     case llvm::Intrinsic::x86_mmx_packsswb:
02387     case llvm::Intrinsic::x86_mmx_packuswb:
02388       handleVectorPackIntrinsic(I, 16);
02389       break;
02390 
02391     case llvm::Intrinsic::x86_mmx_packssdw:
02392       handleVectorPackIntrinsic(I, 32);
02393       break;
02394 
02395     case llvm::Intrinsic::x86_mmx_psad_bw:
02396     case llvm::Intrinsic::x86_sse2_psad_bw:
02397     case llvm::Intrinsic::x86_avx2_psad_bw:
02398       handleVectorSadIntrinsic(I);
02399       break;
02400 
02401     case llvm::Intrinsic::x86_sse2_pmadd_wd:
02402     case llvm::Intrinsic::x86_avx2_pmadd_wd:
02403     case llvm::Intrinsic::x86_ssse3_pmadd_ub_sw_128:
02404     case llvm::Intrinsic::x86_avx2_pmadd_ub_sw:
02405       handleVectorPmaddIntrinsic(I);
02406       break;
02407 
02408     case llvm::Intrinsic::x86_ssse3_pmadd_ub_sw:
02409       handleVectorPmaddIntrinsic(I, 8);
02410       break;
02411 
02412     case llvm::Intrinsic::x86_mmx_pmadd_wd:
02413       handleVectorPmaddIntrinsic(I, 16);
02414       break;
02415 
02416     default:
02417       if (!handleUnknownIntrinsic(I))
02418         visitInstruction(I);
02419       break;
02420     }
02421   }
02422 
02423   void visitCallSite(CallSite CS) {
02424     Instruction &I = *CS.getInstruction();
02425     assert((CS.isCall() || CS.isInvoke()) && "Unknown type of CallSite");
02426     if (CS.isCall()) {
02427       CallInst *Call = cast<CallInst>(&I);
02428 
02429       // For inline asm, do the usual thing: check argument shadow and mark all
02430       // outputs as clean. Note that any side effects of the inline asm that are
02431       // not immediately visible in its constraints are not handled.
02432       if (Call->isInlineAsm()) {
02433         visitInstruction(I);
02434         return;
02435       }
02436 
02437       assert(!isa<IntrinsicInst>(&I) && "intrinsics are handled elsewhere");
02438 
02439       // We are going to insert code that relies on the fact that the callee
02440       // will become a non-readonly function after it is instrumented by us. To
02441       // prevent this code from being optimized out, mark that function
02442       // non-readonly in advance.
02443       if (Function *Func = Call->getCalledFunction()) {
02444         // Clear out readonly/readnone attributes.
02445         AttrBuilder B;
02446         B.addAttribute(Attribute::ReadOnly)
02447           .addAttribute(Attribute::ReadNone);
02448         Func->removeAttributes(AttributeSet::FunctionIndex,
02449                                AttributeSet::get(Func->getContext(),
02450                                                  AttributeSet::FunctionIndex,
02451                                                  B));
02452       }
02453     }
02454     IRBuilder<> IRB(&I);
02455 
02456     unsigned ArgOffset = 0;
02457     DEBUG(dbgs() << "  CallSite: " << I << "\n");
02458     for (CallSite::arg_iterator ArgIt = CS.arg_begin(), End = CS.arg_end();
02459          ArgIt != End; ++ArgIt) {
02460       Value *A = *ArgIt;
02461       unsigned i = ArgIt - CS.arg_begin();
02462       if (!A->getType()->isSized()) {
02463         DEBUG(dbgs() << "Arg " << i << " is not sized: " << I << "\n");
02464         continue;
02465       }
02466       unsigned Size = 0;
02467       Value *Store = nullptr;
02468       // Compute the Shadow for arg even if it is ByVal, because
02469       // in that case getShadow() will copy the actual arg shadow to
02470       // __msan_param_tls.
02471       Value *ArgShadow = getShadow(A);
02472       Value *ArgShadowBase = getShadowPtrForArgument(A, IRB, ArgOffset);
02473       DEBUG(dbgs() << "  Arg#" << i << ": " << *A <<
02474             " Shadow: " << *ArgShadow << "\n");
02475       bool ArgIsInitialized = false;
02476       const DataLayout &DL = F.getParent()->getDataLayout();
02477       if (CS.paramHasAttr(i + 1, Attribute::ByVal)) {
02478         assert(A->getType()->isPointerTy() &&
02479                "ByVal argument is not a pointer!");
02480         Size = DL.getTypeAllocSize(A->getType()->getPointerElementType());
02481         if (ArgOffset + Size > kParamTLSSize) break;
02482         unsigned ParamAlignment = CS.getParamAlignment(i + 1);
02483         unsigned Alignment = std::min(ParamAlignment, kShadowTLSAlignment);
02484         Store = IRB.CreateMemCpy(ArgShadowBase,
02485                                  getShadowPtr(A, Type::getInt8Ty(*MS.C), IRB),
02486                                  Size, Alignment);
02487       } else {
02488         Size = DL.getTypeAllocSize(A->getType());
02489         if (ArgOffset + Size > kParamTLSSize) break;
02490         Store = IRB.CreateAlignedStore(ArgShadow, ArgShadowBase,
02491                                        kShadowTLSAlignment);
02492         Constant *Cst = dyn_cast<Constant>(ArgShadow);
02493         if (Cst && Cst->isNullValue()) ArgIsInitialized = true;
02494       }
02495       if (MS.TrackOrigins && !ArgIsInitialized)
02496         IRB.CreateStore(getOrigin(A),
02497                         getOriginPtrForArgument(A, IRB, ArgOffset));
02498       (void)Store;
02499       assert(Size != 0 && Store != nullptr);
02500       DEBUG(dbgs() << "  Param:" << *Store << "\n");
02501       ArgOffset += alignTo(Size, 8);
02502     }
02503     DEBUG(dbgs() << "  done with call args\n");
02504 
02505     FunctionType *FT =
02506       cast<FunctionType>(CS.getCalledValue()->getType()->getContainedType(0));
02507     if (FT->isVarArg()) {
02508       VAHelper->visitCallSite(CS, IRB);
02509     }
02510 
02511     // Now, get the shadow for the RetVal.
02512     if (!I.getType()->isSized()) return;
02513     // Don't emit the epilogue for musttail call returns.
02514     if (CS.isCall() && cast<CallInst>(&I)->isMustTailCall()) return;
02515     IRBuilder<> IRBBefore(&I);
02516     // Until we have full dynamic coverage, make sure the retval shadow is 0.
02517     Value *Base = getShadowPtrForRetval(&I, IRBBefore);
02518     IRBBefore.CreateAlignedStore(getCleanShadow(&I), Base, kShadowTLSAlignment);
02519     BasicBlock::iterator NextInsn;
02520     if (CS.isCall()) {
02521       NextInsn = ++I.getIterator();
02522       assert(NextInsn != I.getParent()->end());
02523     } else {
02524       BasicBlock *NormalDest = cast<InvokeInst>(&I)->getNormalDest();
02525       if (!NormalDest->getSinglePredecessor()) {
02526         // FIXME: this case is tricky, so we are just conservative here.
02527         // Perhaps we need to split the edge between this BB and NormalDest,
02528         // but a naive attempt to use SplitEdge leads to a crash.
02529         setShadow(&I, getCleanShadow(&I));
02530         setOrigin(&I, getCleanOrigin());
02531         return;
02532       }
02533       NextInsn = NormalDest->getFirstInsertionPt();
02534       assert(NextInsn != NormalDest->end() &&
02535              "Could not find insertion point for retval shadow load");
02536     }
02537     IRBuilder<> IRBAfter(&*NextInsn);
02538     Value *RetvalShadow =
02539       IRBAfter.CreateAlignedLoad(getShadowPtrForRetval(&I, IRBAfter),
02540                                  kShadowTLSAlignment, "_msret");
02541     setShadow(&I, RetvalShadow);
02542     if (MS.TrackOrigins)
02543       setOrigin(&I, IRBAfter.CreateLoad(getOriginPtrForRetval(IRBAfter)));
02544   }
02545 
02546   bool isAMustTailRetVal(Value *RetVal) {
02547     if (auto *I = dyn_cast<BitCastInst>(RetVal)) {
02548       RetVal = I->getOperand(0);
02549     }
02550     if (auto *I = dyn_cast<CallInst>(RetVal)) {
02551       return I->isMustTailCall();
02552     }
02553     return false;
02554   }
02555 
02556   void visitReturnInst(ReturnInst &I) {
02557     IRBuilder<> IRB(&I);
02558     Value *RetVal = I.getReturnValue();
02559     if (!RetVal) return;
02560     // Don't emit the epilogue for musttail call returns.
02561     if (isAMustTailRetVal(RetVal)) return;
02562     Value *ShadowPtr = getShadowPtrForRetval(RetVal, IRB);
02563     if (CheckReturnValue) {
02564       insertShadowCheck(RetVal, &I);
02565       Value *Shadow = getCleanShadow(RetVal);
02566       IRB.CreateAlignedStore(Shadow, ShadowPtr, kShadowTLSAlignment);
02567     } else {
02568       Value *Shadow = getShadow(RetVal);
02569       IRB.CreateAlignedStore(Shadow, ShadowPtr, kShadowTLSAlignment);
02570       // FIXME: make it conditional if ClStoreCleanOrigin==0
02571       if (MS.TrackOrigins)
02572         IRB.CreateStore(getOrigin(RetVal), getOriginPtrForRetval(IRB));
02573     }
02574   }
02575 
02576   void visitPHINode(PHINode &I) {
02577     IRBuilder<> IRB(&I);
02578     if (!PropagateShadow) {
02579       setShadow(&I, getCleanShadow(&I));
02580       setOrigin(&I, getCleanOrigin());
02581       return;
02582     }
02583 
02584     ShadowPHINodes.push_back(&I);
02585     setShadow(&I, IRB.CreatePHI(getShadowTy(&I), I.getNumIncomingValues(),
02586                                 "_msphi_s"));
02587     if (MS.TrackOrigins)
02588       setOrigin(&I, IRB.CreatePHI(MS.OriginTy, I.getNumIncomingValues(),
02589                                   "_msphi_o"));
02590   }
02591 
02592   void visitAllocaInst(AllocaInst &I) {
02593     setShadow(&I, getCleanShadow(&I));
02594     setOrigin(&I, getCleanOrigin());
02595     IRBuilder<> IRB(I.getNextNode());
02596     const DataLayout &DL = F.getParent()->getDataLayout();
02597     uint64_t Size = DL.getTypeAllocSize(I.getAllocatedType());
02598     if (PoisonStack && ClPoisonStackWithCall) {
02599       IRB.CreateCall(MS.MsanPoisonStackFn,
02600                      {IRB.CreatePointerCast(&I, IRB.getInt8PtrTy()),
02601                       ConstantInt::get(MS.IntptrTy, Size)});
02602     } else {
02603       Value *ShadowBase = getShadowPtr(&I, Type::getInt8PtrTy(*MS.C), IRB);
02604       Value *PoisonValue = IRB.getInt8(PoisonStack ? ClPoisonStackPattern : 0);
02605       IRB.CreateMemSet(ShadowBase, PoisonValue, Size, I.getAlignment());
02606     }
02607 
02608     if (PoisonStack && MS.TrackOrigins) {
02609       SmallString<2048> StackDescriptionStorage;
02610       raw_svector_ostream StackDescription(StackDescriptionStorage);
02611       // We create a string with a description of the stack allocation and
02612       // pass it into __msan_set_alloca_origin.
02613       // It will be printed by the run-time if stack-originated UMR is found.
02614       // The first 4 bytes of the string are set to '----' and will be replaced
02615       // by __msan_va_arg_overflow_size_tls at the first call.
02616       StackDescription << "----" << I.getName() << "@" << F.getName();
02617       Value *Descr =
02618           createPrivateNonConstGlobalForString(*F.getParent(),
02619                                                StackDescription.str());
02620 
02621       IRB.CreateCall(MS.MsanSetAllocaOrigin4Fn,
02622                      {IRB.CreatePointerCast(&I, IRB.getInt8PtrTy()),
02623                       ConstantInt::get(MS.IntptrTy, Size),
02624                       IRB.CreatePointerCast(Descr, IRB.getInt8PtrTy()),
02625                       IRB.CreatePointerCast(&F, MS.IntptrTy)});
02626     }
02627   }
02628 
02629   void visitSelectInst(SelectInst& I) {
02630     IRBuilder<> IRB(&I);
02631     // a = select b, c, d
02632     Value *B = I.getCondition();
02633     Value *C = I.getTrueValue();
02634     Value *D = I.getFalseValue();
02635     Value *Sb = getShadow(B);
02636     Value *Sc = getShadow(C);
02637     Value *Sd = getShadow(D);
02638 
02639     // Result shadow if condition shadow is 0.
02640     Value *Sa0 = IRB.CreateSelect(B, Sc, Sd);
02641     Value *Sa1;
02642     if (I.getType()->isAggregateType()) {
02643       // To avoid "sign extending" i1 to an arbitrary aggregate type, we just do
02644       // an extra "select". This results in much more compact IR.
02645       // Sa = select Sb, poisoned, (select b, Sc, Sd)
02646       Sa1 = getPoisonedShadow(getShadowTy(I.getType()));
02647     } else {
02648       // Sa = select Sb, [ (c^d) | Sc | Sd ], [ b ? Sc : Sd ]
02649       // If Sb (condition is poisoned), look for bits in c and d that are equal
02650       // and both unpoisoned.
02651       // If !Sb (condition is unpoisoned), simply pick one of Sc and Sd.
02652 
02653       // Cast arguments to shadow-compatible type.
02654       C = CreateAppToShadowCast(IRB, C);
02655       D = CreateAppToShadowCast(IRB, D);
02656 
02657       // Result shadow if condition shadow is 1.
02658       Sa1 = IRB.CreateOr(IRB.CreateXor(C, D), IRB.CreateOr(Sc, Sd));
02659     }
02660     Value *Sa = IRB.CreateSelect(Sb, Sa1, Sa0, "_msprop_select");
02661     setShadow(&I, Sa);
02662     if (MS.TrackOrigins) {
02663       // Origins are always i32, so any vector conditions must be flattened.
02664       // FIXME: consider tracking vector origins for app vectors?
02665       if (B->getType()->isVectorTy()) {
02666         Type *FlatTy = getShadowTyNoVec(B->getType());
02667         B = IRB.CreateICmpNE(IRB.CreateBitCast(B, FlatTy),
02668                                 ConstantInt::getNullValue(FlatTy));
02669         Sb = IRB.CreateICmpNE(IRB.CreateBitCast(Sb, FlatTy),
02670                                       ConstantInt::getNullValue(FlatTy));
02671       }
02672       // a = select b, c, d
02673       // Oa = Sb ? Ob : (b ? Oc : Od)
02674       setOrigin(
02675           &I, IRB.CreateSelect(Sb, getOrigin(I.getCondition()),
02676                                IRB.CreateSelect(B, getOrigin(I.getTrueValue()),
02677                                                 getOrigin(I.getFalseValue()))));
02678     }
02679   }
02680 
02681   void visitLandingPadInst(LandingPadInst &I) {
02682     // Do nothing.
02683     // See http://code.google.com/p/memory-sanitizer/issues/detail?id=1
02684     setShadow(&I, getCleanShadow(&I));
02685     setOrigin(&I, getCleanOrigin());
02686   }
02687 
02688   void visitCatchSwitchInst(CatchSwitchInst &I) {
02689     setShadow(&I, getCleanShadow(&I));
02690     setOrigin(&I, getCleanOrigin());
02691   }
02692 
02693   void visitFuncletPadInst(FuncletPadInst &I) {
02694     setShadow(&I, getCleanShadow(&I));
02695     setOrigin(&I, getCleanOrigin());
02696   }
02697 
02698   void visitGetElementPtrInst(GetElementPtrInst &I) {
02699     handleShadowOr(I);
02700   }
02701 
02702   void visitExtractValueInst(ExtractValueInst &I) {
02703     IRBuilder<> IRB(&I);
02704     Value *Agg = I.getAggregateOperand();
02705     DEBUG(dbgs() << "ExtractValue:  " << I << "\n");
02706     Value *AggShadow = getShadow(Agg);
02707     DEBUG(dbgs() << "   AggShadow:  " << *AggShadow << "\n");
02708     Value *ResShadow = IRB.CreateExtractValue(AggShadow, I.getIndices());
02709     DEBUG(dbgs() << "   ResShadow:  " << *ResShadow << "\n");
02710     setShadow(&I, ResShadow);
02711     setOriginForNaryOp(I);
02712   }
02713 
02714   void visitInsertValueInst(InsertValueInst &I) {
02715     IRBuilder<> IRB(&I);
02716     DEBUG(dbgs() << "InsertValue:  " << I << "\n");
02717     Value *AggShadow = getShadow(I.getAggregateOperand());
02718     Value *InsShadow = getShadow(I.getInsertedValueOperand());
02719     DEBUG(dbgs() << "   AggShadow:  " << *AggShadow << "\n");
02720     DEBUG(dbgs() << "   InsShadow:  " << *InsShadow << "\n");
02721     Value *Res = IRB.CreateInsertValue(AggShadow, InsShadow, I.getIndices());
02722     DEBUG(dbgs() << "   Res:        " << *Res << "\n");
02723     setShadow(&I, Res);
02724     setOriginForNaryOp(I);
02725   }
02726 
02727   void dumpInst(Instruction &I) {
02728     if (CallInst *CI = dyn_cast<CallInst>(&I)) {
02729       errs() << "ZZZ call " << CI->getCalledFunction()->getName() << "\n";
02730     } else {
02731       errs() << "ZZZ " << I.getOpcodeName() << "\n";
02732     }
02733     errs() << "QQQ " << I << "\n";
02734   }
02735 
02736   void visitResumeInst(ResumeInst &I) {
02737     DEBUG(dbgs() << "Resume: " << I << "\n");
02738     // Nothing to do here.
02739   }
02740 
02741   void visitCleanupReturnInst(CleanupReturnInst &CRI) {
02742     DEBUG(dbgs() << "CleanupReturn: " << CRI << "\n");
02743     // Nothing to do here.
02744   }
02745 
02746   void visitCatchReturnInst(CatchReturnInst &CRI) {
02747     DEBUG(dbgs() << "CatchReturn: " << CRI << "\n");
02748     // Nothing to do here.
02749   }
02750 
02751   void visitInstruction(Instruction &I) {
02752     // Everything else: stop propagating and check for poisoned shadow.
02753     if (ClDumpStrictInstructions)
02754       dumpInst(I);
02755     DEBUG(dbgs() << "DEFAULT: " << I << "\n");
02756     for (size_t i = 0, n = I.getNumOperands(); i < n; i++)
02757       insertShadowCheck(I.getOperand(i), &I);
02758     setShadow(&I, getCleanShadow(&I));
02759     setOrigin(&I, getCleanOrigin());
02760   }
02761 };
02762 
02763 /// \brief AMD64-specific implementation of VarArgHelper.
02764 struct VarArgAMD64Helper : public VarArgHelper {
02765   // An unfortunate workaround for asymmetric lowering of va_arg stuff.
02766   // See a comment in visitCallSite for more details.
02767   static const unsigned AMD64GpEndOffset = 48;  // AMD64 ABI Draft 0.99.6 p3.5.7
02768   static const unsigned AMD64FpEndOffset = 176;
02769 
02770   Function &F;
02771   MemorySanitizer &MS;
02772   MemorySanitizerVisitor &MSV;
02773   Value *VAArgTLSCopy;
02774   Value *VAArgOverflowSize;
02775 
02776   SmallVector<CallInst*, 16> VAStartInstrumentationList;
02777 
02778   VarArgAMD64Helper(Function &F, MemorySanitizer &MS,
02779                     MemorySanitizerVisitor &MSV)
02780     : F(F), MS(MS), MSV(MSV), VAArgTLSCopy(nullptr),
02781       VAArgOverflowSize(nullptr) {}
02782 
02783   enum ArgKind { AK_GeneralPurpose, AK_FloatingPoint, AK_Memory };
02784 
02785   ArgKind classifyArgument(Value* arg) {
02786     // A very rough approximation of X86_64 argument classification rules.
02787     Type *T = arg->getType();
02788     if (T->isFPOrFPVectorTy() || T->isX86_MMXTy())
02789       return AK_FloatingPoint;
02790     if (T->isIntegerTy() && T->getPrimitiveSizeInBits() <= 64)
02791       return AK_GeneralPurpose;
02792     if (T->isPointerTy())
02793       return AK_GeneralPurpose;
02794     return AK_Memory;
02795   }
02796 
02797   // For VarArg functions, store the argument shadow in an ABI-specific format
02798   // that corresponds to va_list layout.
02799   // We do this because Clang lowers va_arg in the frontend, and this pass
02800   // only sees the low level code that deals with va_list internals.
02801   // A much easier alternative (provided that Clang emits va_arg instructions)
02802   // would have been to associate each live instance of va_list with a copy of
02803   // MSanParamTLS, and extract shadow on va_arg() call in the argument list
02804   // order.
02805   void visitCallSite(CallSite &CS, IRBuilder<> &IRB) override {
02806     unsigned GpOffset = 0;
02807     unsigned FpOffset = AMD64GpEndOffset;
02808     unsigned OverflowOffset = AMD64FpEndOffset;
02809     const DataLayout &DL = F.getParent()->getDataLayout();
02810     for (CallSite::arg_iterator ArgIt = CS.arg_begin(), End = CS.arg_end();
02811          ArgIt != End; ++ArgIt) {
02812       Value *A = *ArgIt;
02813       unsigned ArgNo = CS.getArgumentNo(ArgIt);
02814       bool IsByVal = CS.paramHasAttr(ArgNo + 1, Attribute::ByVal);
02815       if (IsByVal) {
02816         // ByVal arguments always go to the overflow area.
02817         assert(A->getType()->isPointerTy());
02818         Type *RealTy = A->getType()->getPointerElementType();
02819         uint64_t ArgSize = DL.getTypeAllocSize(RealTy);
02820         Value *Base = getShadowPtrForVAArgument(RealTy, IRB, OverflowOffset);
02821         OverflowOffset += alignTo(ArgSize, 8);
02822         IRB.CreateMemCpy(Base, MSV.getShadowPtr(A, IRB.getInt8Ty(), IRB),
02823                          ArgSize, kShadowTLSAlignment);
02824       } else {
02825         ArgKind AK = classifyArgument(A);
02826         if (AK == AK_GeneralPurpose && GpOffset >= AMD64GpEndOffset)
02827           AK = AK_Memory;
02828         if (AK == AK_FloatingPoint && FpOffset >= AMD64FpEndOffset)
02829           AK = AK_Memory;
02830         Value *Base;
02831         switch (AK) {
02832           case AK_GeneralPurpose:
02833             Base = getShadowPtrForVAArgument(A->getType(), IRB, GpOffset);
02834             GpOffset += 8;
02835             break;
02836           case AK_FloatingPoint:
02837             Base = getShadowPtrForVAArgument(A->getType(), IRB, FpOffset);
02838             FpOffset += 16;
02839             break;
02840           case AK_Memory:
02841             uint64_t ArgSize = DL.getTypeAllocSize(A->getType());
02842             Base = getShadowPtrForVAArgument(A->getType(), IRB, OverflowOffset);
02843             OverflowOffset += alignTo(ArgSize, 8);
02844         }
02845         IRB.CreateAlignedStore(MSV.getShadow(A), Base, kShadowTLSAlignment);
02846       }
02847     }
02848     Constant *OverflowSize =
02849       ConstantInt::get(IRB.getInt64Ty(), OverflowOffset - AMD64FpEndOffset);
02850     IRB.CreateStore(OverflowSize, MS.VAArgOverflowSizeTLS);
02851   }
02852 
02853   /// \brief Compute the shadow address for a given va_arg.
02854   Value *getShadowPtrForVAArgument(Type *Ty, IRBuilder<> &IRB,
02855                                    int ArgOffset) {
02856     Value *Base = IRB.CreatePointerCast(MS.VAArgTLS, MS.IntptrTy);
02857     Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset));
02858     return IRB.CreateIntToPtr(Base, PointerType::get(MSV.getShadowTy(Ty), 0),
02859                               "_msarg");
02860   }
02861 
02862   void visitVAStartInst(VAStartInst &I) override {
02863     if (F.getCallingConv() == CallingConv::X86_64_Win64)
02864       return;
02865     IRBuilder<> IRB(&I);
02866     VAStartInstrumentationList.push_back(&I);
02867     Value *VAListTag = I.getArgOperand(0);
02868     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
02869 
02870     // Unpoison the whole __va_list_tag.
02871     // FIXME: magic ABI constants.
02872     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
02873                      /* size */24, /* alignment */8, false);
02874   }
02875 
02876   void visitVACopyInst(VACopyInst &I) override {
02877     if (F.getCallingConv() == CallingConv::X86_64_Win64)
02878       return;
02879     IRBuilder<> IRB(&I);
02880     Value *VAListTag = I.getArgOperand(0);
02881     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
02882 
02883     // Unpoison the whole __va_list_tag.
02884     // FIXME: magic ABI constants.
02885     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
02886                      /* size */24, /* alignment */8, false);
02887   }
02888 
02889   void finalizeInstrumentation() override {
02890     assert(!VAArgOverflowSize && !VAArgTLSCopy &&
02891            "finalizeInstrumentation called twice");
02892     if (!VAStartInstrumentationList.empty()) {
02893       // If there is a va_start in this function, make a backup copy of
02894       // va_arg_tls somewhere in the function entry block.
02895       IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
02896       VAArgOverflowSize = IRB.CreateLoad(MS.VAArgOverflowSizeTLS);
02897       Value *CopySize =
02898         IRB.CreateAdd(ConstantInt::get(MS.IntptrTy, AMD64FpEndOffset),
02899                       VAArgOverflowSize);
02900       VAArgTLSCopy = IRB.CreateAlloca(Type::getInt8Ty(*MS.C), CopySize);
02901       IRB.CreateMemCpy(VAArgTLSCopy, MS.VAArgTLS, CopySize, 8);
02902     }
02903 
02904     // Instrument va_start.
02905     // Copy va_list shadow from the backup copy of the TLS contents.
02906     for (size_t i = 0, n = VAStartInstrumentationList.size(); i < n; i++) {
02907       CallInst *OrigInst = VAStartInstrumentationList[i];
02908       IRBuilder<> IRB(OrigInst->getNextNode());
02909       Value *VAListTag = OrigInst->getArgOperand(0);
02910 
02911       Value *RegSaveAreaPtrPtr =
02912         IRB.CreateIntToPtr(
02913           IRB.CreateAdd(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy),
02914                         ConstantInt::get(MS.IntptrTy, 16)),
02915           Type::getInt64PtrTy(*MS.C));
02916       Value *RegSaveAreaPtr = IRB.CreateLoad(RegSaveAreaPtrPtr);
02917       Value *RegSaveAreaShadowPtr =
02918         MSV.getShadowPtr(RegSaveAreaPtr, IRB.getInt8Ty(), IRB);
02919       IRB.CreateMemCpy(RegSaveAreaShadowPtr, VAArgTLSCopy,
02920                        AMD64FpEndOffset, 16);
02921 
02922       Value *OverflowArgAreaPtrPtr =
02923         IRB.CreateIntToPtr(
02924           IRB.CreateAdd(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy),
02925                         ConstantInt::get(MS.IntptrTy, 8)),
02926           Type::getInt64PtrTy(*MS.C));
02927       Value *OverflowArgAreaPtr = IRB.CreateLoad(OverflowArgAreaPtrPtr);
02928       Value *OverflowArgAreaShadowPtr =
02929         MSV.getShadowPtr(OverflowArgAreaPtr, IRB.getInt8Ty(), IRB);
02930       Value *SrcPtr = IRB.CreateConstGEP1_32(IRB.getInt8Ty(), VAArgTLSCopy,
02931                                              AMD64FpEndOffset);
02932       IRB.CreateMemCpy(OverflowArgAreaShadowPtr, SrcPtr, VAArgOverflowSize, 16);
02933     }
02934   }
02935 };
02936 
02937 /// \brief MIPS64-specific implementation of VarArgHelper.
02938 struct VarArgMIPS64Helper : public VarArgHelper {
02939   Function &F;
02940   MemorySanitizer &MS;
02941   MemorySanitizerVisitor &MSV;
02942   Value *VAArgTLSCopy;
02943   Value *VAArgSize;
02944 
02945   SmallVector<CallInst*, 16> VAStartInstrumentationList;
02946 
02947   VarArgMIPS64Helper(Function &F, MemorySanitizer &MS,
02948                     MemorySanitizerVisitor &MSV)
02949     : F(F), MS(MS), MSV(MSV), VAArgTLSCopy(nullptr),
02950       VAArgSize(nullptr) {}
02951 
02952   void visitCallSite(CallSite &CS, IRBuilder<> &IRB) override {
02953     unsigned VAArgOffset = 0;
02954     const DataLayout &DL = F.getParent()->getDataLayout();
02955     for (CallSite::arg_iterator ArgIt = CS.arg_begin() + 1, End = CS.arg_end();
02956          ArgIt != End; ++ArgIt) {
02957       Value *A = *ArgIt;
02958       Value *Base;
02959       uint64_t ArgSize = DL.getTypeAllocSize(A->getType());
02960 #if defined(__MIPSEB__) || defined(MIPSEB)
02961       // Adjusting the shadow for argument with size < 8 to match the placement
02962       // of bits in big endian system
02963       if (ArgSize < 8)
02964         VAArgOffset += (8 - ArgSize);
02965 #endif
02966       Base = getShadowPtrForVAArgument(A->getType(), IRB, VAArgOffset);
02967       VAArgOffset += ArgSize;
02968       VAArgOffset = alignTo(VAArgOffset, 8);
02969       IRB.CreateAlignedStore(MSV.getShadow(A), Base, kShadowTLSAlignment);
02970     }
02971 
02972     Constant *TotalVAArgSize = ConstantInt::get(IRB.getInt64Ty(), VAArgOffset);
02973     // Here using VAArgOverflowSizeTLS as VAArgSizeTLS to avoid creation of
02974     // a new class member i.e. it is the total size of all VarArgs.
02975     IRB.CreateStore(TotalVAArgSize, MS.VAArgOverflowSizeTLS);
02976   }
02977 
02978   /// \brief Compute the shadow address for a given va_arg.
02979   Value *getShadowPtrForVAArgument(Type *Ty, IRBuilder<> &IRB,
02980                                    int ArgOffset) {
02981     Value *Base = IRB.CreatePointerCast(MS.VAArgTLS, MS.IntptrTy);
02982     Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset));
02983     return IRB.CreateIntToPtr(Base, PointerType::get(MSV.getShadowTy(Ty), 0),
02984                               "_msarg");
02985   }
02986 
02987   void visitVAStartInst(VAStartInst &I) override {
02988     IRBuilder<> IRB(&I);
02989     VAStartInstrumentationList.push_back(&I);
02990     Value *VAListTag = I.getArgOperand(0);
02991     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
02992     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
02993                      /* size */8, /* alignment */8, false);
02994   }
02995 
02996   void visitVACopyInst(VACopyInst &I) override {
02997     IRBuilder<> IRB(&I);
02998     Value *VAListTag = I.getArgOperand(0);
02999     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
03000     // Unpoison the whole __va_list_tag.
03001     // FIXME: magic ABI constants.
03002     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
03003                      /* size */8, /* alignment */8, false);
03004   }
03005 
03006   void finalizeInstrumentation() override {
03007     assert(!VAArgSize && !VAArgTLSCopy &&
03008            "finalizeInstrumentation called twice");
03009     IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
03010     VAArgSize = IRB.CreateLoad(MS.VAArgOverflowSizeTLS);
03011     Value *CopySize = IRB.CreateAdd(ConstantInt::get(MS.IntptrTy, 0),
03012                                     VAArgSize);
03013 
03014     if (!VAStartInstrumentationList.empty()) {
03015       // If there is a va_start in this function, make a backup copy of
03016       // va_arg_tls somewhere in the function entry block.
03017       VAArgTLSCopy = IRB.CreateAlloca(Type::getInt8Ty(*MS.C), CopySize);
03018       IRB.CreateMemCpy(VAArgTLSCopy, MS.VAArgTLS, CopySize, 8);
03019     }
03020 
03021     // Instrument va_start.
03022     // Copy va_list shadow from the backup copy of the TLS contents.
03023     for (size_t i = 0, n = VAStartInstrumentationList.size(); i < n; i++) {
03024       CallInst *OrigInst = VAStartInstrumentationList[i];
03025       IRBuilder<> IRB(OrigInst->getNextNode());
03026       Value *VAListTag = OrigInst->getArgOperand(0);
03027       Value *RegSaveAreaPtrPtr =
03028         IRB.CreateIntToPtr(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy),
03029                         Type::getInt64PtrTy(*MS.C));
03030       Value *RegSaveAreaPtr = IRB.CreateLoad(RegSaveAreaPtrPtr);
03031       Value *RegSaveAreaShadowPtr =
03032       MSV.getShadowPtr(RegSaveAreaPtr, IRB.getInt8Ty(), IRB);
03033       IRB.CreateMemCpy(RegSaveAreaShadowPtr, VAArgTLSCopy, CopySize, 8);
03034     }
03035   }
03036 };
03037 
03038 
03039 /// \brief AArch64-specific implementation of VarArgHelper.
03040 struct VarArgAArch64Helper : public VarArgHelper {
03041   static const unsigned kAArch64GrArgSize = 56;
03042   static const unsigned kAArch64VrArgSize = 128;
03043 
03044   static const unsigned AArch64GrBegOffset = 0;
03045   static const unsigned AArch64GrEndOffset = kAArch64GrArgSize;
03046   // Make VR space aligned to 16 bytes.
03047   static const unsigned AArch64VrBegOffset = AArch64GrEndOffset + 8;
03048   static const unsigned AArch64VrEndOffset = AArch64VrBegOffset
03049                                              + kAArch64VrArgSize;
03050   static const unsigned AArch64VAEndOffset = AArch64VrEndOffset;
03051 
03052   Function &F;
03053   MemorySanitizer &MS;
03054   MemorySanitizerVisitor &MSV;
03055   Value *VAArgTLSCopy;
03056   Value *VAArgOverflowSize;
03057 
03058   SmallVector<CallInst*, 16> VAStartInstrumentationList;
03059 
03060   VarArgAArch64Helper(Function &F, MemorySanitizer &MS,
03061                     MemorySanitizerVisitor &MSV)
03062     : F(F), MS(MS), MSV(MSV), VAArgTLSCopy(nullptr),
03063       VAArgOverflowSize(nullptr) {}
03064 
03065   enum ArgKind { AK_GeneralPurpose, AK_FloatingPoint, AK_Memory };
03066 
03067   ArgKind classifyArgument(Value* arg) {
03068     Type *T = arg->getType();
03069     if (T->isFPOrFPVectorTy())
03070       return AK_FloatingPoint;
03071     if ((T->isIntegerTy() && T->getPrimitiveSizeInBits() <= 64)
03072         || (T->isPointerTy()))
03073       return AK_GeneralPurpose;
03074     return AK_Memory;
03075   }
03076 
03077   // The instrumentation stores the argument shadow in a non ABI-specific
03078   // format because it does not know which argument is named (since Clang,
03079   // like x86_64 case, lowers the va_args in the frontend and this pass only
03080   // sees the low level code that deals with va_list internals).
03081   // The first seven GR registers are saved in the first 56 bytes of the
03082   // va_arg tls arra, followers by the first 8 FP/SIMD registers, and then
03083   // the remaining arguments.
03084   // Using constant offset within the va_arg TLS array allows fast copy
03085   // in the finalize instrumentation.
03086   void visitCallSite(CallSite &CS, IRBuilder<> &IRB) override {
03087     unsigned GrOffset = AArch64GrBegOffset;
03088     unsigned VrOffset = AArch64VrBegOffset;
03089     unsigned OverflowOffset = AArch64VAEndOffset;
03090 
03091     const DataLayout &DL = F.getParent()->getDataLayout();
03092     for (CallSite::arg_iterator ArgIt = CS.arg_begin() + 1, End = CS.arg_end();
03093          ArgIt != End; ++ArgIt) {
03094       Value *A = *ArgIt;
03095       ArgKind AK = classifyArgument(A);
03096       if (AK == AK_GeneralPurpose && GrOffset >= AArch64GrEndOffset)
03097         AK = AK_Memory;
03098       if (AK == AK_FloatingPoint && VrOffset >= AArch64VrEndOffset)
03099         AK = AK_Memory;
03100       Value *Base;
03101       switch (AK) {
03102         case AK_GeneralPurpose:
03103           Base = getShadowPtrForVAArgument(A->getType(), IRB, GrOffset);
03104           GrOffset += 8;
03105           break;
03106         case AK_FloatingPoint:
03107           Base = getShadowPtrForVAArgument(A->getType(), IRB, VrOffset);
03108           VrOffset += 16;
03109           break;
03110         case AK_Memory:
03111           uint64_t ArgSize = DL.getTypeAllocSize(A->getType());
03112           Base = getShadowPtrForVAArgument(A->getType(), IRB, OverflowOffset);
03113           OverflowOffset += alignTo(ArgSize, 8);
03114           break;
03115       }
03116       IRB.CreateAlignedStore(MSV.getShadow(A), Base, kShadowTLSAlignment);
03117     }
03118     Constant *OverflowSize =
03119       ConstantInt::get(IRB.getInt64Ty(), OverflowOffset - AArch64VAEndOffset);
03120     IRB.CreateStore(OverflowSize, MS.VAArgOverflowSizeTLS);
03121   }
03122 
03123   /// Compute the shadow address for a given va_arg.
03124   Value *getShadowPtrForVAArgument(Type *Ty, IRBuilder<> &IRB,
03125                                    int ArgOffset) {
03126     Value *Base = IRB.CreatePointerCast(MS.VAArgTLS, MS.IntptrTy);
03127     Base = IRB.CreateAdd(Base, ConstantInt::get(MS.IntptrTy, ArgOffset));
03128     return IRB.CreateIntToPtr(Base, PointerType::get(MSV.getShadowTy(Ty), 0),
03129                               "_msarg");
03130   }
03131 
03132   void visitVAStartInst(VAStartInst &I) override {
03133     IRBuilder<> IRB(&I);
03134     VAStartInstrumentationList.push_back(&I);
03135     Value *VAListTag = I.getArgOperand(0);
03136     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
03137     // Unpoison the whole __va_list_tag.
03138     // FIXME: magic ABI constants (size of va_list).
03139     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
03140                      /* size */32, /* alignment */8, false);
03141   }
03142 
03143   void visitVACopyInst(VACopyInst &I) override {
03144     IRBuilder<> IRB(&I);
03145     Value *VAListTag = I.getArgOperand(0);
03146     Value *ShadowPtr = MSV.getShadowPtr(VAListTag, IRB.getInt8Ty(), IRB);
03147     // Unpoison the whole __va_list_tag.
03148     // FIXME: magic ABI constants (size of va_list).
03149     IRB.CreateMemSet(ShadowPtr, Constant::getNullValue(IRB.getInt8Ty()),
03150                      /* size */32, /* alignment */8, false);
03151   }
03152 
03153   // Retrieve a va_list field of 'void*' size.
03154   Value* getVAField64(IRBuilder<> &IRB, Value *VAListTag, int offset) {
03155     Value *SaveAreaPtrPtr =
03156       IRB.CreateIntToPtr(
03157         IRB.CreateAdd(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy),
03158                       ConstantInt::get(MS.IntptrTy, offset)),
03159         Type::getInt64PtrTy(*MS.C));
03160     return IRB.CreateLoad(SaveAreaPtrPtr);
03161   }
03162 
03163   // Retrieve a va_list field of 'int' size.
03164   Value* getVAField32(IRBuilder<> &IRB, Value *VAListTag, int offset) {
03165     Value *SaveAreaPtr =
03166       IRB.CreateIntToPtr(
03167         IRB.CreateAdd(IRB.CreatePtrToInt(VAListTag, MS.IntptrTy),
03168                       ConstantInt::get(MS.IntptrTy, offset)),
03169         Type::getInt32PtrTy(*MS.C));
03170     Value *SaveArea32 = IRB.CreateLoad(SaveAreaPtr);
03171     return IRB.CreateSExt(SaveArea32, MS.IntptrTy);
03172   }
03173 
03174   void finalizeInstrumentation() override {
03175     assert(!VAArgOverflowSize && !VAArgTLSCopy &&
03176            "finalizeInstrumentation called twice");
03177     if (!VAStartInstrumentationList.empty()) {
03178       // If there is a va_start in this function, make a backup copy of
03179       // va_arg_tls somewhere in the function entry block.
03180       IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
03181       VAArgOverflowSize = IRB.CreateLoad(MS.VAArgOverflowSizeTLS);
03182       Value *CopySize =
03183         IRB.CreateAdd(ConstantInt::get(MS.IntptrTy, AArch64VAEndOffset),
03184                       VAArgOverflowSize);
03185       VAArgTLSCopy = IRB.CreateAlloca(Type::getInt8Ty(*MS.C), CopySize);
03186       IRB.CreateMemCpy(VAArgTLSCopy, MS.VAArgTLS, CopySize, 8);
03187     }
03188 
03189     Value *GrArgSize = ConstantInt::get(MS.IntptrTy, kAArch64GrArgSize);
03190     Value *VrArgSize = ConstantInt::get(MS.IntptrTy, kAArch64VrArgSize);
03191 
03192     // Instrument va_start, copy va_list shadow from the backup copy of
03193     // the TLS contents.
03194     for (size_t i = 0, n = VAStartInstrumentationList.size(); i < n; i++) {
03195       CallInst *OrigInst = VAStartInstrumentationList[i];
03196       IRBuilder<> IRB(OrigInst->getNextNode());
03197 
03198       Value *VAListTag = OrigInst->getArgOperand(0);
03199 
03200       // The variadic ABI for AArch64 creates two areas to save the incoming
03201       // argument registers (one for 64-bit general register xn-x7 and another
03202       // for 128-bit FP/SIMD vn-v7).
03203       // We need then to propagate the shadow arguments on both regions
03204       // 'va::__gr_top + va::__gr_offs' and 'va::__vr_top + va::__vr_offs'.
03205       // The remaning arguments are saved on shadow for 'va::stack'.
03206       // One caveat is it requires only to propagate the non-named arguments,
03207       // however on the call site instrumentation 'all' the arguments are
03208       // saved. So to copy the shadow values from the va_arg TLS array
03209       // we need to adjust the offset for both GR and VR fields based on
03210       // the __{gr,vr}_offs value (since they are stores based on incoming
03211       // named arguments).
03212 
03213       // Read the stack pointer from the va_list.
03214       Value *StackSaveAreaPtr = getVAField64(IRB, VAListTag, 0);
03215 
03216       // Read both the __gr_top and __gr_off and add them up.
03217       Value *GrTopSaveAreaPtr = getVAField64(IRB, VAListTag, 8);
03218       Value *GrOffSaveArea = getVAField32(IRB, VAListTag, 24);
03219 
03220       Value *GrRegSaveAreaPtr = IRB.CreateAdd(GrTopSaveAreaPtr, GrOffSaveArea);
03221 
03222       // Read both the __vr_top and __vr_off and add them up.
03223       Value *VrTopSaveAreaPtr = getVAField64(IRB, VAListTag, 16);
03224       Value *VrOffSaveArea = getVAField32(IRB, VAListTag, 28);
03225 
03226       Value *VrRegSaveAreaPtr = IRB.CreateAdd(VrTopSaveAreaPtr, VrOffSaveArea);
03227 
03228       // It does not know how many named arguments is being used and, on the
03229       // callsite all the arguments were saved.  Since __gr_off is defined as
03230       // '0 - ((8 - named_gr) * 8)', the idea is to just propagate the variadic
03231       // argument by ignoring the bytes of shadow from named arguments.
03232       Value *GrRegSaveAreaShadowPtrOff =
03233         IRB.CreateAdd(GrArgSize, GrOffSaveArea);
03234 
03235       Value *GrRegSaveAreaShadowPtr =
03236         MSV.getShadowPtr(GrRegSaveAreaPtr, IRB.getInt8Ty(), IRB);
03237 
03238       Value *GrSrcPtr = IRB.CreateInBoundsGEP(IRB.getInt8Ty(), VAArgTLSCopy,
03239                                               GrRegSaveAreaShadowPtrOff);
03240       Value *GrCopySize = IRB.CreateSub(GrArgSize, GrRegSaveAreaShadowPtrOff);
03241 
03242       IRB.CreateMemCpy(GrRegSaveAreaShadowPtr, GrSrcPtr, GrCopySize, 8);
03243 
03244       // Again, but for FP/SIMD values.
03245       Value *VrRegSaveAreaShadowPtrOff =
03246           IRB.CreateAdd(VrArgSize, VrOffSaveArea);
03247 
03248       Value *VrRegSaveAreaShadowPtr =
03249         MSV.getShadowPtr(VrRegSaveAreaPtr, IRB.getInt8Ty(), IRB);
03250 
03251       Value *VrSrcPtr = IRB.CreateInBoundsGEP(
03252         IRB.getInt8Ty(),
03253         IRB.CreateInBoundsGEP(IRB.getInt8Ty(), VAArgTLSCopy,
03254                               IRB.getInt32(AArch64VrBegOffset)),
03255         VrRegSaveAreaShadowPtrOff);
03256       Value *VrCopySize = IRB.CreateSub(VrArgSize, VrRegSaveAreaShadowPtrOff);
03257 
03258       IRB.CreateMemCpy(VrRegSaveAreaShadowPtr, VrSrcPtr, VrCopySize, 8);
03259 
03260       // And finally for remaining arguments.
03261       Value *StackSaveAreaShadowPtr =
03262         MSV.getShadowPtr(StackSaveAreaPtr, IRB.getInt8Ty(), IRB);
03263 
03264       Value *StackSrcPtr =
03265         IRB.CreateInBoundsGEP(IRB.getInt8Ty(), VAArgTLSCopy,
03266                               IRB.getInt32(AArch64VAEndOffset));
03267 
03268       IRB.CreateMemCpy(StackSaveAreaShadowPtr, StackSrcPtr,
03269                        VAArgOverflowSize, 16);
03270     }
03271   }
03272 };
03273 
03274 /// \brief A no-op implementation of VarArgHelper.
03275 struct VarArgNoOpHelper : public VarArgHelper {
03276   VarArgNoOpHelper(Function &F, MemorySanitizer &MS,
03277                    MemorySanitizerVisitor &MSV) {}
03278 
03279   void visitCallSite(CallSite &CS, IRBuilder<> &IRB) override {}
03280 
03281   void visitVAStartInst(VAStartInst &I) override {}
03282 
03283   void visitVACopyInst(VACopyInst &I) override {}
03284 
03285   void finalizeInstrumentation() override {}
03286 };
03287 
03288 VarArgHelper *CreateVarArgHelper(Function &Func, MemorySanitizer &Msan,
03289                                  MemorySanitizerVisitor &Visitor) {
03290   // VarArg handling is only implemented on AMD64. False positives are possible
03291   // on other platforms.
03292   llvm::Triple TargetTriple(Func.getParent()->getTargetTriple());
03293   if (TargetTriple.getArch() == llvm::Triple::x86_64)
03294     return new VarArgAMD64Helper(Func, Msan, Visitor);
03295   else if (TargetTriple.getArch() == llvm::Triple::mips64 ||
03296            TargetTriple.getArch() == llvm::Triple::mips64el)
03297     return new VarArgMIPS64Helper(Func, Msan, Visitor);
03298   else if (TargetTriple.getArch() == llvm::Triple::aarch64)
03299     return new VarArgAArch64Helper(Func, Msan, Visitor);
03300   else
03301     return new VarArgNoOpHelper(Func, Msan, Visitor);
03302 }
03303 
03304 } // anonymous namespace
03305 
03306 bool MemorySanitizer::runOnFunction(Function &F) {
03307   if (&F == MsanCtorFunction)
03308     return false;
03309   MemorySanitizerVisitor Visitor(F, *this);
03310 
03311   // Clear out readonly/readnone attributes.
03312   AttrBuilder B;
03313   B.addAttribute(Attribute::ReadOnly)
03314     .addAttribute(Attribute::ReadNone);
03315   F.removeAttributes(AttributeSet::FunctionIndex,
03316                      AttributeSet::get(F.getContext(),
03317                                        AttributeSet::FunctionIndex, B));
03318 
03319   return Visitor.runOnFunction();
03320 }