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