llvm/lib/Transforms/Instrumentation/ThreadSanitizer.cpp

   1 //===-- ThreadSanitizer.cpp - race detector -------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file is a part of ThreadSanitizer, a race detector.
  10 //
  11 // The tool is under development, for the details about previous versions see
  12 // http://code.google.com/p/data-race-test
  13 //
  14 // The instrumentation phase is quite simple:
  15 //   - Insert calls to run-time library before every memory access.
  16 //      - Optimizations may apply to avoid instrumenting some of the accesses.
  17 //   - Insert calls at function entry/exit.
  18 // The rest is handled by the run-time library.
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "llvm/Transforms/Instrumentation/ThreadSanitizer.h"
  22 #include "llvm/ADT/DenseMap.h"
  23 #include "llvm/ADT/SmallString.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include "llvm/ADT/StringExtras.h"
  27 #include "llvm/Analysis/CaptureTracking.h"
  28 #include "llvm/Analysis/TargetLibraryInfo.h"
  29 #include "llvm/Analysis/ValueTracking.h"
  30 #include "llvm/IR/DataLayout.h"
  31 #include "llvm/IR/Function.h"
  32 #include "llvm/IR/IRBuilder.h"
  33 #include "llvm/IR/Instructions.h"
  34 #include "llvm/IR/IntrinsicInst.h"
  35 #include "llvm/IR/Intrinsics.h"
  36 #include "llvm/IR/LLVMContext.h"
  37 #include "llvm/IR/Metadata.h"
  38 #include "llvm/IR/Module.h"
  39 #include "llvm/IR/Type.h"
  40 #include "llvm/ProfileData/InstrProf.h"
  41 #include "llvm/Support/CommandLine.h"
  42 #include "llvm/Support/Debug.h"
  43 #include "llvm/Support/MathExtras.h"
  44 #include "llvm/Support/raw_ostream.h"
  45 #include "llvm/Transforms/Instrumentation.h"
  46 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  47 #include "llvm/Transforms/Utils/EscapeEnumerator.h"
  48 #include "llvm/Transforms/Utils/Local.h"
  49 #include "llvm/Transforms/Utils/ModuleUtils.h"
  50
  51 using namespace llvm;
  52
  53 #define DEBUG_TYPE "tsan"
  54
  55 static cl::opt<bool> ClInstrumentMemoryAccesses(
  56     "tsan-instrument-memory-accesses", cl::init(true),
  57     cl::desc("Instrument memory accesses"), cl::Hidden);
  58 static cl::opt<bool>
  59     ClInstrumentFuncEntryExit("tsan-instrument-func-entry-exit", cl::init(true),
  60                               cl::desc("Instrument function entry and exit"),
  61                               cl::Hidden);
  62 static cl::opt<bool> ClHandleCxxExceptions(
  63     "tsan-handle-cxx-exceptions", cl::init(true),
  64     cl::desc("Handle C++ exceptions (insert cleanup blocks for unwinding)"),
  65     cl::Hidden);
  66 static cl::opt<bool> ClInstrumentAtomics("tsan-instrument-atomics",
  67                                          cl::init(true),
  68                                          cl::desc("Instrument atomics"),
  69                                          cl::Hidden);
  70 static cl::opt<bool> ClInstrumentMemIntrinsics(
  71     "tsan-instrument-memintrinsics", cl::init(true),
  72     cl::desc("Instrument memintrinsics (memset/memcpy/memmove)"), cl::Hidden);
  73 static cl::opt<bool> ClDistinguishVolatile(
  74     "tsan-distinguish-volatile", cl::init(false),
  75     cl::desc("Emit special instrumentation for accesses to volatiles"),
  76     cl::Hidden);
  77 static cl::opt<bool> ClInstrumentReadBeforeWrite(
  78     "tsan-instrument-read-before-write", cl::init(false),
  79     cl::desc("Do not eliminate read instrumentation for read-before-writes"),
  80     cl::Hidden);
  81 static cl::opt<bool> ClCompoundReadBeforeWrite(
  82     "tsan-compound-read-before-write", cl::init(false),
  83     cl::desc("Emit special compound instrumentation for reads-before-writes"),
  84     cl::Hidden);
  85
  86 STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
  87 STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
  88 STATISTIC(NumOmittedReadsBeforeWrite,
  89           "Number of reads ignored due to following writes");
  90 STATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size");
  91 STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes");
  92 STATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads");
  93 STATISTIC(NumOmittedReadsFromConstantGlobals,
  94           "Number of reads from constant globals");
  95 STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads");
  96 STATISTIC(NumOmittedNonCaptured, "Number of accesses ignored due to capturing");
  97
  98 const char kTsanModuleCtorName[] = "tsan.module_ctor";
  99 const char kTsanInitName[] = "__tsan_init";
 100
 101 namespace {
 102
 103 /// ThreadSanitizer: instrument the code in module to find races.
 104 ///
 105 /// Instantiating ThreadSanitizer inserts the tsan runtime library API function
 106 /// declarations into the module if they don't exist already. Instantiating
 107 /// ensures the __tsan_init function is in the list of global constructors for
 108 /// the module.
 109 struct ThreadSanitizer {
 110   ThreadSanitizer() {
 111     // Check options and warn user.
 112     if (ClInstrumentReadBeforeWrite && ClCompoundReadBeforeWrite) {
 113       errs()
 114           << "warning: Option -tsan-compound-read-before-write has no effect "
 115              "when -tsan-instrument-read-before-write is set.\n";
 116     }
 117   }
 118
 119   bool sanitizeFunction(Function &F, const TargetLibraryInfo &TLI);
 120
 121 private:
 122   // Internal Instruction wrapper that contains more information about the
 123   // Instruction from prior analysis.
 124   struct InstructionInfo {
 125     // Instrumentation emitted for this instruction is for a compounded set of
 126     // read and write operations in the same basic block.
 127     static constexpr unsigned kCompoundRW = (1U << 0);
 128
 129     explicit InstructionInfo(Instruction *Inst) : Inst(Inst) {}
 130
 131     Instruction *Inst;
 132     unsigned Flags = 0;
 133   };
 134
 135   void initialize(Module &M, const TargetLibraryInfo &TLI);
 136   bool instrumentLoadOrStore(const InstructionInfo &II, const DataLayout &DL);
 137   bool instrumentAtomic(Instruction *I, const DataLayout &DL);
 138   bool instrumentMemIntrinsic(Instruction *I);
 139   void chooseInstructionsToInstrument(SmallVectorImpl<Instruction *> &Local,
 140                                       SmallVectorImpl<InstructionInfo> &All,
 141                                       const DataLayout &DL);
 142   bool addrPointsToConstantData(Value *Addr);
 143   int getMemoryAccessFuncIndex(Type *OrigTy, Value *Addr, const DataLayout &DL);
 144   void InsertRuntimeIgnores(Function &F);
 145
 146   Type *IntptrTy;
 147   FunctionCallee TsanFuncEntry;
 148   FunctionCallee TsanFuncExit;
 149   FunctionCallee TsanIgnoreBegin;
 150   FunctionCallee TsanIgnoreEnd;
 151   // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
 152   static const size_t kNumberOfAccessSizes = 5;
 153   FunctionCallee TsanRead[kNumberOfAccessSizes];
 154   FunctionCallee TsanWrite[kNumberOfAccessSizes];
 155   FunctionCallee TsanUnalignedRead[kNumberOfAccessSizes];
 156   FunctionCallee TsanUnalignedWrite[kNumberOfAccessSizes];
 157   FunctionCallee TsanVolatileRead[kNumberOfAccessSizes];
 158   FunctionCallee TsanVolatileWrite[kNumberOfAccessSizes];
 159   FunctionCallee TsanUnalignedVolatileRead[kNumberOfAccessSizes];
 160   FunctionCallee TsanUnalignedVolatileWrite[kNumberOfAccessSizes];
 161   FunctionCallee TsanCompoundRW[kNumberOfAccessSizes];
 162   FunctionCallee TsanUnalignedCompoundRW[kNumberOfAccessSizes];
 163   FunctionCallee TsanAtomicLoad[kNumberOfAccessSizes];
 164   FunctionCallee TsanAtomicStore[kNumberOfAccessSizes];
 165   FunctionCallee TsanAtomicRMW[AtomicRMWInst::LAST_BINOP + 1]
 166                               [kNumberOfAccessSizes];
 167   FunctionCallee TsanAtomicCAS[kNumberOfAccessSizes];
 168   FunctionCallee TsanAtomicThreadFence;
 169   FunctionCallee TsanAtomicSignalFence;
 170   FunctionCallee TsanVptrUpdate;
 171   FunctionCallee TsanVptrLoad;
 172   FunctionCallee MemmoveFn, MemcpyFn, MemsetFn;
 173 };
 174
 175 void insertModuleCtor(Module &M) {
 176   getOrCreateSanitizerCtorAndInitFunctions(
 177       M, kTsanModuleCtorName, kTsanInitName, /*InitArgTypes=*/{},
 178       /*InitArgs=*/{},
 179       // This callback is invoked when the functions are created the first
 180       // time. Hook them into the global ctors list in that case:
 181       [&](Function *Ctor, FunctionCallee) { appendToGlobalCtors(M, Ctor, 0); });
 182 }
 183 }  // namespace
 184
 185 PreservedAnalyses ThreadSanitizerPass::run(Function &F,
 186                                            FunctionAnalysisManager &FAM) {
 187   ThreadSanitizer TSan;
 188   if (TSan.sanitizeFunction(F, FAM.getResult<TargetLibraryAnalysis>(F)))
 189     return PreservedAnalyses::none();
 190   return PreservedAnalyses::all();
 191 }
 192
 193 PreservedAnalyses ModuleThreadSanitizerPass::run(Module &M,
 194                                                  ModuleAnalysisManager &MAM) {
 195   insertModuleCtor(M);
 196   return PreservedAnalyses::none();
 197 }
 198 void ThreadSanitizer::initialize(Module &M, const TargetLibraryInfo &TLI) {
 199   const DataLayout &DL = M.getDataLayout();
 200   LLVMContext &Ctx = M.getContext();
 201   IntptrTy = DL.getIntPtrType(Ctx);
 202
 203   IRBuilder<> IRB(Ctx);
 204   AttributeList Attr;
 205   Attr = Attr.addFnAttribute(Ctx, Attribute::NoUnwind);
 206   // Initialize the callbacks.
 207   TsanFuncEntry = M.getOrInsertFunction("__tsan_func_entry", Attr,
 208                                         IRB.getVoidTy(), IRB.getPtrTy());
 209   TsanFuncExit =
 210       M.getOrInsertFunction("__tsan_func_exit", Attr, IRB.getVoidTy());
 211   TsanIgnoreBegin = M.getOrInsertFunction("__tsan_ignore_thread_begin", Attr,
 212                                           IRB.getVoidTy());
 213   TsanIgnoreEnd =
 214       M.getOrInsertFunction("__tsan_ignore_thread_end", Attr, IRB.getVoidTy());
 215   IntegerType *OrdTy = IRB.getInt32Ty();
 216   for (size_t i = 0; i < kNumberOfAccessSizes; ++i) {
 217     const unsigned ByteSize = 1U << i;
 218     const unsigned BitSize = ByteSize * 8;
 219     std::string ByteSizeStr = utostr(ByteSize);
 220     std::string BitSizeStr = utostr(BitSize);
 221     SmallString<32> ReadName("__tsan_read" + ByteSizeStr);
 222     TsanRead[i] = M.getOrInsertFunction(ReadName, Attr, IRB.getVoidTy(),
 223                                         IRB.getPtrTy());
 224
 225     SmallString<32> WriteName("__tsan_write" + ByteSizeStr);
 226     TsanWrite[i] = M.getOrInsertFunction(WriteName, Attr, IRB.getVoidTy(),
 227                                          IRB.getPtrTy());
 228
 229     SmallString<64> UnalignedReadName("__tsan_unaligned_read" + ByteSizeStr);
 230     TsanUnalignedRead[i] = M.getOrInsertFunction(
 231         UnalignedReadName, Attr, IRB.getVoidTy(), IRB.getPtrTy());
 232
 233     SmallString<64> UnalignedWriteName("__tsan_unaligned_write" + ByteSizeStr);
 234     TsanUnalignedWrite[i] = M.getOrInsertFunction(
 235         UnalignedWriteName, Attr, IRB.getVoidTy(), IRB.getPtrTy());
 236
 237     SmallString<64> VolatileReadName("__tsan_volatile_read" + ByteSizeStr);
 238     TsanVolatileRead[i] = M.getOrInsertFunction(
 239         VolatileReadName, Attr, IRB.getVoidTy(), IRB.getPtrTy());
 240
 241     SmallString<64> VolatileWriteName("__tsan_volatile_write" + ByteSizeStr);
 242     TsanVolatileWrite[i] = M.getOrInsertFunction(
 243         VolatileWriteName, Attr, IRB.getVoidTy(), IRB.getPtrTy());
 244
 245     SmallString<64> UnalignedVolatileReadName("__tsan_unaligned_volatile_read" +
 246                                               ByteSizeStr);
 247     TsanUnalignedVolatileRead[i] = M.getOrInsertFunction(
 248         UnalignedVolatileReadName, Attr, IRB.getVoidTy(), IRB.getPtrTy());
 249
 250     SmallString<64> UnalignedVolatileWriteName(
 251         "__tsan_unaligned_volatile_write" + ByteSizeStr);
 252     TsanUnalignedVolatileWrite[i] = M.getOrInsertFunction(
 253         UnalignedVolatileWriteName, Attr, IRB.getVoidTy(), IRB.getPtrTy());
 254
 255     SmallString<64> CompoundRWName("__tsan_read_write" + ByteSizeStr);
 256     TsanCompoundRW[i] = M.getOrInsertFunction(
 257         CompoundRWName, Attr, IRB.getVoidTy(), IRB.getPtrTy());
 258
 259     SmallString<64> UnalignedCompoundRWName("__tsan_unaligned_read_write" +
 260                                             ByteSizeStr);
 261     TsanUnalignedCompoundRW[i] = M.getOrInsertFunction(
 262         UnalignedCompoundRWName, Attr, IRB.getVoidTy(), IRB.getPtrTy());
 263
 264     Type *Ty = Type::getIntNTy(Ctx, BitSize);
 265     Type *PtrTy = PointerType::get(Ctx, 0);
 266     SmallString<32> AtomicLoadName("__tsan_atomic" + BitSizeStr + "_load");
 267     TsanAtomicLoad[i] =
 268         M.getOrInsertFunction(AtomicLoadName,
 269                               TLI.getAttrList(&Ctx, {1}, /*Signed=*/true,
 270                                               /*Ret=*/BitSize <= 32, Attr),
 271                               Ty, PtrTy, OrdTy);
 272
 273     // Args of type Ty need extension only when BitSize is 32 or less.
 274     using Idxs = std::vector<unsigned>;
 275     Idxs Idxs2Or12   ((BitSize <= 32) ? Idxs({1, 2})       : Idxs({2}));
 276     Idxs Idxs34Or1234((BitSize <= 32) ? Idxs({1, 2, 3, 4}) : Idxs({3, 4}));
 277     SmallString<32> AtomicStoreName("__tsan_atomic" + BitSizeStr + "_store");
 278     TsanAtomicStore[i] = M.getOrInsertFunction(
 279         AtomicStoreName,
 280         TLI.getAttrList(&Ctx, Idxs2Or12, /*Signed=*/true, /*Ret=*/false, Attr),
 281         IRB.getVoidTy(), PtrTy, Ty, OrdTy);
 282
 283     for (unsigned Op = AtomicRMWInst::FIRST_BINOP;
 284          Op <= AtomicRMWInst::LAST_BINOP; ++Op) {
 285       TsanAtomicRMW[Op][i] = nullptr;
 286       const char *NamePart = nullptr;
 287       if (Op == AtomicRMWInst::Xchg)
 288         NamePart = "_exchange";
 289       else if (Op == AtomicRMWInst::Add)
 290         NamePart = "_fetch_add";
 291       else if (Op == AtomicRMWInst::Sub)
 292         NamePart = "_fetch_sub";
 293       else if (Op == AtomicRMWInst::And)
 294         NamePart = "_fetch_and";
 295       else if (Op == AtomicRMWInst::Or)
 296         NamePart = "_fetch_or";
 297       else if (Op == AtomicRMWInst::Xor)
 298         NamePart = "_fetch_xor";
 299       else if (Op == AtomicRMWInst::Nand)
 300         NamePart = "_fetch_nand";
 301       else
 302         continue;
 303       SmallString<32> RMWName("__tsan_atomic" + itostr(BitSize) + NamePart);
 304       TsanAtomicRMW[Op][i] = M.getOrInsertFunction(
 305           RMWName,
 306           TLI.getAttrList(&Ctx, Idxs2Or12, /*Signed=*/true,
 307                           /*Ret=*/BitSize <= 32, Attr),
 308           Ty, PtrTy, Ty, OrdTy);
 309     }
 310
 311     SmallString<32> AtomicCASName("__tsan_atomic" + BitSizeStr +
 312                                   "_compare_exchange_val");
 313     TsanAtomicCAS[i] = M.getOrInsertFunction(
 314         AtomicCASName,
 315         TLI.getAttrList(&Ctx, Idxs34Or1234, /*Signed=*/true,
 316                         /*Ret=*/BitSize <= 32, Attr),
 317         Ty, PtrTy, Ty, Ty, OrdTy, OrdTy);
 318   }
 319   TsanVptrUpdate =
 320       M.getOrInsertFunction("__tsan_vptr_update", Attr, IRB.getVoidTy(),
 321                             IRB.getPtrTy(), IRB.getPtrTy());
 322   TsanVptrLoad = M.getOrInsertFunction("__tsan_vptr_read", Attr,
 323                                        IRB.getVoidTy(), IRB.getPtrTy());
 324   TsanAtomicThreadFence = M.getOrInsertFunction(
 325       "__tsan_atomic_thread_fence",
 326       TLI.getAttrList(&Ctx, {0}, /*Signed=*/true, /*Ret=*/false, Attr),
 327       IRB.getVoidTy(), OrdTy);
 328
 329   TsanAtomicSignalFence = M.getOrInsertFunction(
 330       "__tsan_atomic_signal_fence",
 331       TLI.getAttrList(&Ctx, {0}, /*Signed=*/true, /*Ret=*/false, Attr),
 332       IRB.getVoidTy(), OrdTy);
 333
 334   MemmoveFn =
 335       M.getOrInsertFunction("__tsan_memmove", Attr, IRB.getPtrTy(),
 336                             IRB.getPtrTy(), IRB.getPtrTy(), IntptrTy);
 337   MemcpyFn =
 338       M.getOrInsertFunction("__tsan_memcpy", Attr, IRB.getPtrTy(),
 339                             IRB.getPtrTy(), IRB.getPtrTy(), IntptrTy);
 340   MemsetFn = M.getOrInsertFunction(
 341       "__tsan_memset",
 342       TLI.getAttrList(&Ctx, {1}, /*Signed=*/true, /*Ret=*/false, Attr),
 343       IRB.getPtrTy(), IRB.getPtrTy(), IRB.getInt32Ty(), IntptrTy);
 344 }
 345
 346 static bool isVtableAccess(Instruction *I) {
 347   if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa))
 348     return Tag->isTBAAVtableAccess();
 349   return false;
 350 }
 351
 352 // Do not instrument known races/"benign races" that come from compiler
 353 // instrumentatin. The user has no way of suppressing them.
 354 static bool shouldInstrumentReadWriteFromAddress(const Module *M, Value *Addr) {
 355   // Peel off GEPs and BitCasts.
 356   Addr = Addr->stripInBoundsOffsets();
 357
 358   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
 359     if (GV->hasSection()) {
 360       StringRef SectionName = GV->getSection();
 361       // Check if the global is in the PGO counters section.
 362       auto OF = Triple(M->getTargetTriple()).getObjectFormat();
 363       if (SectionName.ends_with(
 364               getInstrProfSectionName(IPSK_cnts, OF, /*AddSegmentInfo=*/false)))
 365         return false;
 366     }
 367   }
 368
 369   // Do not instrument accesses from different address spaces; we cannot deal
 370   // with them.
 371   if (Addr) {
 372     Type *PtrTy = cast<PointerType>(Addr->getType()->getScalarType());
 373     if (PtrTy->getPointerAddressSpace() != 0)
 374       return false;
 375   }
 376
 377   return true;
 378 }
 379
 380 bool ThreadSanitizer::addrPointsToConstantData(Value *Addr) {
 381   // If this is a GEP, just analyze its pointer operand.
 382   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr))
 383     Addr = GEP->getPointerOperand();
 384
 385   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
 386     if (GV->isConstant()) {
 387       // Reads from constant globals can not race with any writes.
 388       NumOmittedReadsFromConstantGlobals++;
 389       return true;
 390     }
 391   } else if (LoadInst *L = dyn_cast<LoadInst>(Addr)) {
 392     if (isVtableAccess(L)) {
 393       // Reads from a vtable pointer can not race with any writes.
 394       NumOmittedReadsFromVtable++;
 395       return true;
 396     }
 397   }
 398   return false;
 399 }
 400
 401 // Instrumenting some of the accesses may be proven redundant.
 402 // Currently handled:
 403 //  - read-before-write (within same BB, no calls between)
 404 //  - not captured variables
 405 //
 406 // We do not handle some of the patterns that should not survive
 407 // after the classic compiler optimizations.
 408 // E.g. two reads from the same temp should be eliminated by CSE,
 409 // two writes should be eliminated by DSE, etc.
 410 //
 411 // 'Local' is a vector of insns within the same BB (no calls between).
 412 // 'All' is a vector of insns that will be instrumented.
 413 void ThreadSanitizer::chooseInstructionsToInstrument(
 414     SmallVectorImpl<Instruction *> &Local,
 415     SmallVectorImpl<InstructionInfo> &All, const DataLayout &DL) {
 416   DenseMap<Value *, size_t> WriteTargets; // Map of addresses to index in All
 417   // Iterate from the end.
 418   for (Instruction *I : reverse(Local)) {
 419     const bool IsWrite = isa<StoreInst>(*I);
 420     Value *Addr = IsWrite ? cast<StoreInst>(I)->getPointerOperand()
 421                           : cast<LoadInst>(I)->getPointerOperand();
 422
 423     if (!shouldInstrumentReadWriteFromAddress(I->getModule(), Addr))
 424       continue;
 425
 426     if (!IsWrite) {
 427       const auto WriteEntry = WriteTargets.find(Addr);
 428       if (!ClInstrumentReadBeforeWrite && WriteEntry != WriteTargets.end()) {
 429         auto &WI = All[WriteEntry->second];
 430         // If we distinguish volatile accesses and if either the read or write
 431         // is volatile, do not omit any instrumentation.
 432         const bool AnyVolatile =
 433             ClDistinguishVolatile && (cast<LoadInst>(I)->isVolatile() ||
 434                                       cast<StoreInst>(WI.Inst)->isVolatile());
 435         if (!AnyVolatile) {
 436           // We will write to this temp, so no reason to analyze the read.
 437           // Mark the write instruction as compound.
 438           WI.Flags |= InstructionInfo::kCompoundRW;
 439           NumOmittedReadsBeforeWrite++;
 440           continue;
 441         }
 442       }
 443
 444       if (addrPointsToConstantData(Addr)) {
 445         // Addr points to some constant data -- it can not race with any writes.
 446         continue;
 447       }
 448     }
 449
 450     if (isa<AllocaInst>(getUnderlyingObject(Addr)) &&
 451         !PointerMayBeCaptured(Addr, true, true)) {
 452       // The variable is addressable but not captured, so it cannot be
 453       // referenced from a different thread and participate in a data race
 454       // (see llvm/Analysis/CaptureTracking.h for details).
 455       NumOmittedNonCaptured++;
 456       continue;
 457     }
 458
 459     // Instrument this instruction.
 460     All.emplace_back(I);
 461     if (IsWrite) {
 462       // For read-before-write and compound instrumentation we only need one
 463       // write target, and we can override any previous entry if it exists.
 464       WriteTargets[Addr] = All.size() - 1;
 465     }
 466   }
 467   Local.clear();
 468 }
 469
 470 static bool isTsanAtomic(const Instruction *I) {
 471   // TODO: Ask TTI whether synchronization scope is between threads.
 472   auto SSID = getAtomicSyncScopeID(I);
 473   if (!SSID)
 474     return false;
 475   if (isa<LoadInst>(I) || isa<StoreInst>(I))
 476     return *SSID != SyncScope::SingleThread;
 477   return true;
 478 }
 479
 480 void ThreadSanitizer::InsertRuntimeIgnores(Function &F) {
 481   InstrumentationIRBuilder IRB(F.getEntryBlock().getFirstNonPHI());
 482   IRB.CreateCall(TsanIgnoreBegin);
 483   EscapeEnumerator EE(F, "tsan_ignore_cleanup", ClHandleCxxExceptions);
 484   while (IRBuilder<> *AtExit = EE.Next()) {
 485     InstrumentationIRBuilder::ensureDebugInfo(*AtExit, F);
 486     AtExit->CreateCall(TsanIgnoreEnd);
 487   }
 488 }
 489
 490 bool ThreadSanitizer::sanitizeFunction(Function &F,
 491                                        const TargetLibraryInfo &TLI) {
 492   // This is required to prevent instrumenting call to __tsan_init from within
 493   // the module constructor.
 494   if (F.getName() == kTsanModuleCtorName)
 495     return false;
 496   // Naked functions can not have prologue/epilogue
 497   // (__tsan_func_entry/__tsan_func_exit) generated, so don't instrument them at
 498   // all.
 499   if (F.hasFnAttribute(Attribute::Naked))
 500     return false;
 501
 502   // __attribute__(disable_sanitizer_instrumentation) prevents all kinds of
 503   // instrumentation.
 504   if (F.hasFnAttribute(Attribute::DisableSanitizerInstrumentation))
 505     return false;
 506
 507   initialize(*F.getParent(), TLI);
 508   SmallVector<InstructionInfo, 8> AllLoadsAndStores;
 509   SmallVector<Instruction*, 8> LocalLoadsAndStores;
 510   SmallVector<Instruction*, 8> AtomicAccesses;
 511   SmallVector<Instruction*, 8> MemIntrinCalls;
 512   bool Res = false;
 513   bool HasCalls = false;
 514   bool SanitizeFunction = F.hasFnAttribute(Attribute::SanitizeThread);
 515   const DataLayout &DL = F.getParent()->getDataLayout();
 516
 517   // Traverse all instructions, collect loads/stores/returns, check for calls.
 518   for (auto &BB : F) {
 519     for (auto &Inst : BB) {
 520       // Skip instructions inserted by another instrumentation.
 521       if (Inst.hasMetadata(LLVMContext::MD_nosanitize))
 522         continue;
 523       if (isTsanAtomic(&Inst))
 524         AtomicAccesses.push_back(&Inst);
 525       else if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
 526         LocalLoadsAndStores.push_back(&Inst);
 527       else if ((isa<CallInst>(Inst) && !isa<DbgInfoIntrinsic>(Inst)) ||
 528                isa<InvokeInst>(Inst)) {
 529         if (CallInst *CI = dyn_cast<CallInst>(&Inst))
 530           maybeMarkSanitizerLibraryCallNoBuiltin(CI, &TLI);
 531         if (isa<MemIntrinsic>(Inst))
 532           MemIntrinCalls.push_back(&Inst);
 533         HasCalls = true;
 534         chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores,
 535                                        DL);
 536       }
 537     }
 538     chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores, DL);
 539   }
 540
 541   // We have collected all loads and stores.
 542   // FIXME: many of these accesses do not need to be checked for races
 543   // (e.g. variables that do not escape, etc).
 544
 545   // Instrument memory accesses only if we want to report bugs in the function.
 546   if (ClInstrumentMemoryAccesses && SanitizeFunction)
 547     for (const auto &II : AllLoadsAndStores) {
 548       Res |= instrumentLoadOrStore(II, DL);
 549     }
 550
 551   // Instrument atomic memory accesses in any case (they can be used to
 552   // implement synchronization).
 553   if (ClInstrumentAtomics)
 554     for (auto *Inst : AtomicAccesses) {
 555       Res |= instrumentAtomic(Inst, DL);
 556     }
 557
 558   if (ClInstrumentMemIntrinsics && SanitizeFunction)
 559     for (auto *Inst : MemIntrinCalls) {
 560       Res |= instrumentMemIntrinsic(Inst);
 561     }
 562
 563   if (F.hasFnAttribute("sanitize_thread_no_checking_at_run_time")) {
 564     assert(!F.hasFnAttribute(Attribute::SanitizeThread));
 565     if (HasCalls)
 566       InsertRuntimeIgnores(F);
 567   }
 568
 569   // Instrument function entry/exit points if there were instrumented accesses.
 570   if ((Res || HasCalls) && ClInstrumentFuncEntryExit) {
 571     InstrumentationIRBuilder IRB(F.getEntryBlock().getFirstNonPHI());
 572     Value *ReturnAddress = IRB.CreateCall(
 573         Intrinsic::getDeclaration(F.getParent(), Intrinsic::returnaddress),
 574         IRB.getInt32(0));
 575     IRB.CreateCall(TsanFuncEntry, ReturnAddress);
 576
 577     EscapeEnumerator EE(F, "tsan_cleanup", ClHandleCxxExceptions);
 578     while (IRBuilder<> *AtExit = EE.Next()) {
 579       InstrumentationIRBuilder::ensureDebugInfo(*AtExit, F);
 580       AtExit->CreateCall(TsanFuncExit, {});
 581     }
 582     Res = true;
 583   }
 584   return Res;
 585 }
 586
 587 bool ThreadSanitizer::instrumentLoadOrStore(const InstructionInfo &II,
 588                                             const DataLayout &DL) {
 589   InstrumentationIRBuilder IRB(II.Inst);
 590   const bool IsWrite = isa<StoreInst>(*II.Inst);
 591   Value *Addr = IsWrite ? cast<StoreInst>(II.Inst)->getPointerOperand()
 592                         : cast<LoadInst>(II.Inst)->getPointerOperand();
 593   Type *OrigTy = getLoadStoreType(II.Inst);
 594
 595   // swifterror memory addresses are mem2reg promoted by instruction selection.
 596   // As such they cannot have regular uses like an instrumentation function and
 597   // it makes no sense to track them as memory.
 598   if (Addr->isSwiftError())
 599     return false;
 600
 601   int Idx = getMemoryAccessFuncIndex(OrigTy, Addr, DL);
 602   if (Idx < 0)
 603     return false;
 604   if (IsWrite && isVtableAccess(II.Inst)) {
 605     LLVM_DEBUG(dbgs() << "  VPTR : " << *II.Inst << "\n");
 606     Value *StoredValue = cast<StoreInst>(II.Inst)->getValueOperand();
 607     // StoredValue may be a vector type if we are storing several vptrs at once.
 608     // In this case, just take the first element of the vector since this is
 609     // enough to find vptr races.
 610     if (isa<VectorType>(StoredValue->getType()))
 611       StoredValue = IRB.CreateExtractElement(
 612           StoredValue, ConstantInt::get(IRB.getInt32Ty(), 0));
 613     if (StoredValue->getType()->isIntegerTy())
 614       StoredValue = IRB.CreateIntToPtr(StoredValue, IRB.getPtrTy());
 615     // Call TsanVptrUpdate.
 616     IRB.CreateCall(TsanVptrUpdate, {Addr, StoredValue});
 617     NumInstrumentedVtableWrites++;
 618     return true;
 619   }
 620   if (!IsWrite && isVtableAccess(II.Inst)) {
 621     IRB.CreateCall(TsanVptrLoad, Addr);
 622     NumInstrumentedVtableReads++;
 623     return true;
 624   }
 625
 626   const Align Alignment = IsWrite ? cast<StoreInst>(II.Inst)->getAlign()
 627                                   : cast<LoadInst>(II.Inst)->getAlign();
 628   const bool IsCompoundRW =
 629       ClCompoundReadBeforeWrite && (II.Flags & InstructionInfo::kCompoundRW);
 630   const bool IsVolatile = ClDistinguishVolatile &&
 631                           (IsWrite ? cast<StoreInst>(II.Inst)->isVolatile()
 632                                    : cast<LoadInst>(II.Inst)->isVolatile());
 633   assert((!IsVolatile || !IsCompoundRW) && "Compound volatile invalid!");
 634
 635   const uint32_t TypeSize = DL.getTypeStoreSizeInBits(OrigTy);
 636   FunctionCallee OnAccessFunc = nullptr;
 637   if (Alignment >= Align(8) || (Alignment.value() % (TypeSize / 8)) == 0) {
 638     if (IsCompoundRW)
 639       OnAccessFunc = TsanCompoundRW[Idx];
 640     else if (IsVolatile)
 641       OnAccessFunc = IsWrite ? TsanVolatileWrite[Idx] : TsanVolatileRead[Idx];
 642     else
 643       OnAccessFunc = IsWrite ? TsanWrite[Idx] : TsanRead[Idx];
 644   } else {
 645     if (IsCompoundRW)
 646       OnAccessFunc = TsanUnalignedCompoundRW[Idx];
 647     else if (IsVolatile)
 648       OnAccessFunc = IsWrite ? TsanUnalignedVolatileWrite[Idx]
 649                              : TsanUnalignedVolatileRead[Idx];
 650     else
 651       OnAccessFunc = IsWrite ? TsanUnalignedWrite[Idx] : TsanUnalignedRead[Idx];
 652   }
 653   IRB.CreateCall(OnAccessFunc, Addr);
 654   if (IsCompoundRW || IsWrite)
 655     NumInstrumentedWrites++;
 656   if (IsCompoundRW || !IsWrite)
 657     NumInstrumentedReads++;
 658   return true;
 659 }
 660
 661 static ConstantInt *createOrdering(IRBuilder<> *IRB, AtomicOrdering ord) {
 662   uint32_t v = 0;
 663   switch (ord) {
 664     case AtomicOrdering::NotAtomic:
 665       llvm_unreachable("unexpected atomic ordering!");
 666     case AtomicOrdering::Unordered:              [[fallthrough]];
 667     case AtomicOrdering::Monotonic:              v = 0; break;
 668     // Not specified yet:
 669     // case AtomicOrdering::Consume:                v = 1; break;
 670     case AtomicOrdering::Acquire:                v = 2; break;
 671     case AtomicOrdering::Release:                v = 3; break;
 672     case AtomicOrdering::AcquireRelease:         v = 4; break;
 673     case AtomicOrdering::SequentiallyConsistent: v = 5; break;
 674   }
 675   return IRB->getInt32(v);
 676 }
 677
 678 // If a memset intrinsic gets inlined by the code gen, we will miss races on it.
 679 // So, we either need to ensure the intrinsic is not inlined, or instrument it.
 680 // We do not instrument memset/memmove/memcpy intrinsics (too complicated),
 681 // instead we simply replace them with regular function calls, which are then
 682 // intercepted by the run-time.
 683 // Since tsan is running after everyone else, the calls should not be
 684 // replaced back with intrinsics. If that becomes wrong at some point,
 685 // we will need to call e.g. __tsan_memset to avoid the intrinsics.
 686 bool ThreadSanitizer::instrumentMemIntrinsic(Instruction *I) {
 687   InstrumentationIRBuilder IRB(I);
 688   if (MemSetInst *M = dyn_cast<MemSetInst>(I)) {
 689     Value *Cast1 = IRB.CreateIntCast(M->getArgOperand(1), IRB.getInt32Ty(), false);
 690     Value *Cast2 = IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false);
 691     IRB.CreateCall(
 692         MemsetFn,
 693         {M->getArgOperand(0),
 694          Cast1,
 695          Cast2});
 696     I->eraseFromParent();
 697   } else if (MemTransferInst *M = dyn_cast<MemTransferInst>(I)) {
 698     IRB.CreateCall(
 699         isa<MemCpyInst>(M) ? MemcpyFn : MemmoveFn,
 700         {M->getArgOperand(0),
 701          M->getArgOperand(1),
 702          IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false)});
 703     I->eraseFromParent();
 704   }
 705   return false;
 706 }
 707
 708 // Both llvm and ThreadSanitizer atomic operations are based on C++11/C1x
 709 // standards.  For background see C++11 standard.  A slightly older, publicly
 710 // available draft of the standard (not entirely up-to-date, but close enough
 711 // for casual browsing) is available here:
 712 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf
 713 // The following page contains more background information:
 714 // http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/
 715
 716 bool ThreadSanitizer::instrumentAtomic(Instruction *I, const DataLayout &DL) {
 717   InstrumentationIRBuilder IRB(I);
 718   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 719     Value *Addr = LI->getPointerOperand();
 720     Type *OrigTy = LI->getType();
 721     int Idx = getMemoryAccessFuncIndex(OrigTy, Addr, DL);
 722     if (Idx < 0)
 723       return false;
 724     Value *Args[] = {Addr,
 725                      createOrdering(&IRB, LI->getOrdering())};
 726     Value *C = IRB.CreateCall(TsanAtomicLoad[Idx], Args);
 727     Value *Cast = IRB.CreateBitOrPointerCast(C, OrigTy);
 728     I->replaceAllUsesWith(Cast);
 729   } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 730     Value *Addr = SI->getPointerOperand();
 731     int Idx =
 732         getMemoryAccessFuncIndex(SI->getValueOperand()->getType(), Addr, DL);
 733     if (Idx < 0)
 734       return false;
 735     const unsigned ByteSize = 1U << Idx;
 736     const unsigned BitSize = ByteSize * 8;
 737     Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
 738     Value *Args[] = {Addr,
 739                      IRB.CreateBitOrPointerCast(SI->getValueOperand(), Ty),
 740                      createOrdering(&IRB, SI->getOrdering())};
 741     CallInst *C = CallInst::Create(TsanAtomicStore[Idx], Args);
 742     ReplaceInstWithInst(I, C);
 743   } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) {
 744     Value *Addr = RMWI->getPointerOperand();
 745     int Idx =
 746         getMemoryAccessFuncIndex(RMWI->getValOperand()->getType(), Addr, DL);
 747     if (Idx < 0)
 748       return false;
 749     FunctionCallee F = TsanAtomicRMW[RMWI->getOperation()][Idx];
 750     if (!F)
 751       return false;
 752     const unsigned ByteSize = 1U << Idx;
 753     const unsigned BitSize = ByteSize * 8;
 754     Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
 755     Value *Val = RMWI->getValOperand();
 756     Value *Args[] = {Addr, IRB.CreateBitOrPointerCast(Val, Ty),
 757                      createOrdering(&IRB, RMWI->getOrdering())};
 758     Value *C = IRB.CreateCall(F, Args);
 759     I->replaceAllUsesWith(IRB.CreateBitOrPointerCast(C, Val->getType()));
 760     I->eraseFromParent();
 761   } else if (AtomicCmpXchgInst *CASI = dyn_cast<AtomicCmpXchgInst>(I)) {
 762     Value *Addr = CASI->getPointerOperand();
 763     Type *OrigOldValTy = CASI->getNewValOperand()->getType();
 764     int Idx = getMemoryAccessFuncIndex(OrigOldValTy, Addr, DL);
 765     if (Idx < 0)
 766       return false;
 767     const unsigned ByteSize = 1U << Idx;
 768     const unsigned BitSize = ByteSize * 8;
 769     Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
 770     Value *CmpOperand =
 771       IRB.CreateBitOrPointerCast(CASI->getCompareOperand(), Ty);
 772     Value *NewOperand =
 773       IRB.CreateBitOrPointerCast(CASI->getNewValOperand(), Ty);
 774     Value *Args[] = {Addr,
 775                      CmpOperand,
 776                      NewOperand,
 777                      createOrdering(&IRB, CASI->getSuccessOrdering()),
 778                      createOrdering(&IRB, CASI->getFailureOrdering())};
 779     CallInst *C = IRB.CreateCall(TsanAtomicCAS[Idx], Args);
 780     Value *Success = IRB.CreateICmpEQ(C, CmpOperand);
 781     Value *OldVal = C;
 782     if (Ty != OrigOldValTy) {
 783       // The value is a pointer, so we need to cast the return value.
 784       OldVal = IRB.CreateIntToPtr(C, OrigOldValTy);
 785     }
 786
 787     Value *Res =
 788       IRB.CreateInsertValue(PoisonValue::get(CASI->getType()), OldVal, 0);
 789     Res = IRB.CreateInsertValue(Res, Success, 1);
 790
 791     I->replaceAllUsesWith(Res);
 792     I->eraseFromParent();
 793   } else if (FenceInst *FI = dyn_cast<FenceInst>(I)) {
 794     Value *Args[] = {createOrdering(&IRB, FI->getOrdering())};
 795     FunctionCallee F = FI->getSyncScopeID() == SyncScope::SingleThread
 796                            ? TsanAtomicSignalFence
 797                            : TsanAtomicThreadFence;
 798     CallInst *C = CallInst::Create(F, Args);
 799     ReplaceInstWithInst(I, C);
 800   }
 801   return true;
 802 }
 803
 804 int ThreadSanitizer::getMemoryAccessFuncIndex(Type *OrigTy, Value *Addr,
 805                                               const DataLayout &DL) {
 806   assert(OrigTy->isSized());
 807   uint32_t TypeSize = DL.getTypeStoreSizeInBits(OrigTy);
 808   if (TypeSize != 8  && TypeSize != 16 &&
 809       TypeSize != 32 && TypeSize != 64 && TypeSize != 128) {
 810     NumAccessesWithBadSize++;
 811     // Ignore all unusual sizes.
 812     return -1;
 813   }
 814   size_t Idx = llvm::countr_zero(TypeSize / 8);
 815   assert(Idx < kNumberOfAccessSizes);
 816   return Idx;
 817 }