1//===-- ThreadSanitizer.cpp - race detector -------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file is a part of ThreadSanitizer, a race detector.
11//
12// The tool is under development, for the details about previous versions see
13// http://code.google.com/p/data-race-test
14//
15// The instrumentation phase is quite simple:
16//   - Insert calls to run-time library before every memory access.
17//      - Optimizations may apply to avoid instrumenting some of the accesses.
18//   - Insert calls at function entry/exit.
19// The rest is handled by the run-time library.
20//===----------------------------------------------------------------------===//
21
22#include "llvm/Transforms/Instrumentation.h"
23#include "llvm/ADT/SmallSet.h"
24#include "llvm/ADT/SmallString.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/ADT/StringExtras.h"
28#include "llvm/IR/DataLayout.h"
29#include "llvm/IR/Function.h"
30#include "llvm/IR/IRBuilder.h"
31#include "llvm/IR/IntrinsicInst.h"
32#include "llvm/IR/Intrinsics.h"
33#include "llvm/IR/LLVMContext.h"
34#include "llvm/IR/Metadata.h"
35#include "llvm/IR/Module.h"
36#include "llvm/IR/Type.h"
37#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/MathExtras.h"
40#include "llvm/Support/raw_ostream.h"
41#include "llvm/Transforms/Utils/BasicBlockUtils.h"
42#include "llvm/Transforms/Utils/ModuleUtils.h"
43
44using namespace llvm;
45
46#define DEBUG_TYPE "tsan"
47
48static cl::opt<bool>  ClInstrumentMemoryAccesses(
49    "tsan-instrument-memory-accesses", cl::init(true),
50    cl::desc("Instrument memory accesses"), cl::Hidden);
51static cl::opt<bool>  ClInstrumentFuncEntryExit(
52    "tsan-instrument-func-entry-exit", cl::init(true),
53    cl::desc("Instrument function entry and exit"), cl::Hidden);
54static cl::opt<bool>  ClInstrumentAtomics(
55    "tsan-instrument-atomics", cl::init(true),
56    cl::desc("Instrument atomics"), cl::Hidden);
57static cl::opt<bool>  ClInstrumentMemIntrinsics(
58    "tsan-instrument-memintrinsics", cl::init(true),
59    cl::desc("Instrument memintrinsics (memset/memcpy/memmove)"), cl::Hidden);
60
61STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
62STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
63STATISTIC(NumOmittedReadsBeforeWrite,
64          "Number of reads ignored due to following writes");
65STATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size");
66STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes");
67STATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads");
68STATISTIC(NumOmittedReadsFromConstantGlobals,
69          "Number of reads from constant globals");
70STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads");
71
72namespace {
73
74/// ThreadSanitizer: instrument the code in module to find races.
75struct ThreadSanitizer : public FunctionPass {
76  ThreadSanitizer() : FunctionPass(ID), DL(nullptr) {}
77  const char *getPassName() const override;
78  bool runOnFunction(Function &F) override;
79  bool doInitialization(Module &M) override;
80  static char ID;  // Pass identification, replacement for typeid.
81
82 private:
83  void initializeCallbacks(Module &M);
84  bool instrumentLoadOrStore(Instruction *I);
85  bool instrumentAtomic(Instruction *I);
86  bool instrumentMemIntrinsic(Instruction *I);
87  void chooseInstructionsToInstrument(SmallVectorImpl<Instruction*> &Local,
88                                      SmallVectorImpl<Instruction*> &All);
89  bool addrPointsToConstantData(Value *Addr);
90  int getMemoryAccessFuncIndex(Value *Addr);
91
92  const DataLayout *DL;
93  Type *IntptrTy;
94  IntegerType *OrdTy;
95  // Callbacks to run-time library are computed in doInitialization.
96  Function *TsanFuncEntry;
97  Function *TsanFuncExit;
98  // Accesses sizes are powers of two: 1, 2, 4, 8, 16.
99  static const size_t kNumberOfAccessSizes = 5;
100  Function *TsanRead[kNumberOfAccessSizes];
101  Function *TsanWrite[kNumberOfAccessSizes];
102  Function *TsanAtomicLoad[kNumberOfAccessSizes];
103  Function *TsanAtomicStore[kNumberOfAccessSizes];
104  Function *TsanAtomicRMW[AtomicRMWInst::LAST_BINOP + 1][kNumberOfAccessSizes];
105  Function *TsanAtomicCAS[kNumberOfAccessSizes];
106  Function *TsanAtomicThreadFence;
107  Function *TsanAtomicSignalFence;
108  Function *TsanVptrUpdate;
109  Function *TsanVptrLoad;
110  Function *MemmoveFn, *MemcpyFn, *MemsetFn;
111};
112}  // namespace
113
114char ThreadSanitizer::ID = 0;
115INITIALIZE_PASS(ThreadSanitizer, "tsan",
116    "ThreadSanitizer: detects data races.",
117    false, false)
118
119const char *ThreadSanitizer::getPassName() const {
120  return "ThreadSanitizer";
121}
122
123FunctionPass *llvm::createThreadSanitizerPass() {
124  return new ThreadSanitizer();
125}
126
127static Function *checkInterfaceFunction(Constant *FuncOrBitcast) {
128  if (Function *F = dyn_cast<Function>(FuncOrBitcast))
129     return F;
130  FuncOrBitcast->dump();
131  report_fatal_error("ThreadSanitizer interface function redefined");
132}
133
134void ThreadSanitizer::initializeCallbacks(Module &M) {
135  IRBuilder<> IRB(M.getContext());
136  // Initialize the callbacks.
137  TsanFuncEntry = checkInterfaceFunction(M.getOrInsertFunction(
138      "__tsan_func_entry", IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL));
139  TsanFuncExit = checkInterfaceFunction(M.getOrInsertFunction(
140      "__tsan_func_exit", IRB.getVoidTy(), NULL));
141  OrdTy = IRB.getInt32Ty();
142  for (size_t i = 0; i < kNumberOfAccessSizes; ++i) {
143    const size_t ByteSize = 1 << i;
144    const size_t BitSize = ByteSize * 8;
145    SmallString<32> ReadName("__tsan_read" + itostr(ByteSize));
146    TsanRead[i] = checkInterfaceFunction(M.getOrInsertFunction(
147        ReadName, IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL));
148
149    SmallString<32> WriteName("__tsan_write" + itostr(ByteSize));
150    TsanWrite[i] = checkInterfaceFunction(M.getOrInsertFunction(
151        WriteName, IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL));
152
153    Type *Ty = Type::getIntNTy(M.getContext(), BitSize);
154    Type *PtrTy = Ty->getPointerTo();
155    SmallString<32> AtomicLoadName("__tsan_atomic" + itostr(BitSize) +
156                                   "_load");
157    TsanAtomicLoad[i] = checkInterfaceFunction(M.getOrInsertFunction(
158        AtomicLoadName, Ty, PtrTy, OrdTy, NULL));
159
160    SmallString<32> AtomicStoreName("__tsan_atomic" + itostr(BitSize) +
161                                    "_store");
162    TsanAtomicStore[i] = checkInterfaceFunction(M.getOrInsertFunction(
163        AtomicStoreName, IRB.getVoidTy(), PtrTy, Ty, OrdTy,
164        NULL));
165
166    for (int op = AtomicRMWInst::FIRST_BINOP;
167        op <= AtomicRMWInst::LAST_BINOP; ++op) {
168      TsanAtomicRMW[op][i] = nullptr;
169      const char *NamePart = nullptr;
170      if (op == AtomicRMWInst::Xchg)
171        NamePart = "_exchange";
172      else if (op == AtomicRMWInst::Add)
173        NamePart = "_fetch_add";
174      else if (op == AtomicRMWInst::Sub)
175        NamePart = "_fetch_sub";
176      else if (op == AtomicRMWInst::And)
177        NamePart = "_fetch_and";
178      else if (op == AtomicRMWInst::Or)
179        NamePart = "_fetch_or";
180      else if (op == AtomicRMWInst::Xor)
181        NamePart = "_fetch_xor";
182      else if (op == AtomicRMWInst::Nand)
183        NamePart = "_fetch_nand";
184      else
185        continue;
186      SmallString<32> RMWName("__tsan_atomic" + itostr(BitSize) + NamePart);
187      TsanAtomicRMW[op][i] = checkInterfaceFunction(M.getOrInsertFunction(
188          RMWName, Ty, PtrTy, Ty, OrdTy, NULL));
189    }
190
191    SmallString<32> AtomicCASName("__tsan_atomic" + itostr(BitSize) +
192                                  "_compare_exchange_val");
193    TsanAtomicCAS[i] = checkInterfaceFunction(M.getOrInsertFunction(
194        AtomicCASName, Ty, PtrTy, Ty, Ty, OrdTy, OrdTy, NULL));
195  }
196  TsanVptrUpdate = checkInterfaceFunction(M.getOrInsertFunction(
197      "__tsan_vptr_update", IRB.getVoidTy(), IRB.getInt8PtrTy(),
198      IRB.getInt8PtrTy(), NULL));
199  TsanVptrLoad = checkInterfaceFunction(M.getOrInsertFunction(
200      "__tsan_vptr_read", IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL));
201  TsanAtomicThreadFence = checkInterfaceFunction(M.getOrInsertFunction(
202      "__tsan_atomic_thread_fence", IRB.getVoidTy(), OrdTy, NULL));
203  TsanAtomicSignalFence = checkInterfaceFunction(M.getOrInsertFunction(
204      "__tsan_atomic_signal_fence", IRB.getVoidTy(), OrdTy, NULL));
205
206  MemmoveFn = checkInterfaceFunction(M.getOrInsertFunction(
207    "memmove", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
208    IRB.getInt8PtrTy(), IntptrTy, NULL));
209  MemcpyFn = checkInterfaceFunction(M.getOrInsertFunction(
210    "memcpy", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
211    IntptrTy, NULL));
212  MemsetFn = checkInterfaceFunction(M.getOrInsertFunction(
213    "memset", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt32Ty(),
214    IntptrTy, NULL));
215}
216
217bool ThreadSanitizer::doInitialization(Module &M) {
218  DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
219  if (!DLP)
220    report_fatal_error("data layout missing");
221  DL = &DLP->getDataLayout();
222
223  // Always insert a call to __tsan_init into the module's CTORs.
224  IRBuilder<> IRB(M.getContext());
225  IntptrTy = IRB.getIntPtrTy(DL);
226  Value *TsanInit = M.getOrInsertFunction("__tsan_init",
227                                          IRB.getVoidTy(), NULL);
228  appendToGlobalCtors(M, cast<Function>(TsanInit), 0);
229
230  return true;
231}
232
233static bool isVtableAccess(Instruction *I) {
234  if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa))
235    return Tag->isTBAAVtableAccess();
236  return false;
237}
238
239bool ThreadSanitizer::addrPointsToConstantData(Value *Addr) {
240  // If this is a GEP, just analyze its pointer operand.
241  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr))
242    Addr = GEP->getPointerOperand();
243
244  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
245    if (GV->isConstant()) {
246      // Reads from constant globals can not race with any writes.
247      NumOmittedReadsFromConstantGlobals++;
248      return true;
249    }
250  } else if (LoadInst *L = dyn_cast<LoadInst>(Addr)) {
251    if (isVtableAccess(L)) {
252      // Reads from a vtable pointer can not race with any writes.
253      NumOmittedReadsFromVtable++;
254      return true;
255    }
256  }
257  return false;
258}
259
260// Instrumenting some of the accesses may be proven redundant.
261// Currently handled:
262//  - read-before-write (within same BB, no calls between)
263//
264// We do not handle some of the patterns that should not survive
265// after the classic compiler optimizations.
266// E.g. two reads from the same temp should be eliminated by CSE,
267// two writes should be eliminated by DSE, etc.
268//
269// 'Local' is a vector of insns within the same BB (no calls between).
270// 'All' is a vector of insns that will be instrumented.
271void ThreadSanitizer::chooseInstructionsToInstrument(
272    SmallVectorImpl<Instruction*> &Local,
273    SmallVectorImpl<Instruction*> &All) {
274  SmallSet<Value*, 8> WriteTargets;
275  // Iterate from the end.
276  for (SmallVectorImpl<Instruction*>::reverse_iterator It = Local.rbegin(),
277       E = Local.rend(); It != E; ++It) {
278    Instruction *I = *It;
279    if (StoreInst *Store = dyn_cast<StoreInst>(I)) {
280      WriteTargets.insert(Store->getPointerOperand());
281    } else {
282      LoadInst *Load = cast<LoadInst>(I);
283      Value *Addr = Load->getPointerOperand();
284      if (WriteTargets.count(Addr)) {
285        // We will write to this temp, so no reason to analyze the read.
286        NumOmittedReadsBeforeWrite++;
287        continue;
288      }
289      if (addrPointsToConstantData(Addr)) {
290        // Addr points to some constant data -- it can not race with any writes.
291        continue;
292      }
293    }
294    All.push_back(I);
295  }
296  Local.clear();
297}
298
299static bool isAtomic(Instruction *I) {
300  if (LoadInst *LI = dyn_cast<LoadInst>(I))
301    return LI->isAtomic() && LI->getSynchScope() == CrossThread;
302  if (StoreInst *SI = dyn_cast<StoreInst>(I))
303    return SI->isAtomic() && SI->getSynchScope() == CrossThread;
304  if (isa<AtomicRMWInst>(I))
305    return true;
306  if (isa<AtomicCmpXchgInst>(I))
307    return true;
308  if (isa<FenceInst>(I))
309    return true;
310  return false;
311}
312
313bool ThreadSanitizer::runOnFunction(Function &F) {
314  if (!DL) return false;
315  initializeCallbacks(*F.getParent());
316  SmallVector<Instruction*, 8> RetVec;
317  SmallVector<Instruction*, 8> AllLoadsAndStores;
318  SmallVector<Instruction*, 8> LocalLoadsAndStores;
319  SmallVector<Instruction*, 8> AtomicAccesses;
320  SmallVector<Instruction*, 8> MemIntrinCalls;
321  bool Res = false;
322  bool HasCalls = false;
323  bool SanitizeFunction = F.hasFnAttribute(Attribute::SanitizeThread);
324
325  // Traverse all instructions, collect loads/stores/returns, check for calls.
326  for (auto &BB : F) {
327    for (auto &Inst : BB) {
328      if (isAtomic(&Inst))
329        AtomicAccesses.push_back(&Inst);
330      else if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
331        LocalLoadsAndStores.push_back(&Inst);
332      else if (isa<ReturnInst>(Inst))
333        RetVec.push_back(&Inst);
334      else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
335        if (isa<MemIntrinsic>(Inst))
336          MemIntrinCalls.push_back(&Inst);
337        HasCalls = true;
338        chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores);
339      }
340    }
341    chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores);
342  }
343
344  // We have collected all loads and stores.
345  // FIXME: many of these accesses do not need to be checked for races
346  // (e.g. variables that do not escape, etc).
347
348  // Instrument memory accesses only if we want to report bugs in the function.
349  if (ClInstrumentMemoryAccesses && SanitizeFunction)
350    for (auto Inst : AllLoadsAndStores) {
351      Res |= instrumentLoadOrStore(Inst);
352    }
353
354  // Instrument atomic memory accesses in any case (they can be used to
355  // implement synchronization).
356  if (ClInstrumentAtomics)
357    for (auto Inst : AtomicAccesses) {
358      Res |= instrumentAtomic(Inst);
359    }
360
361  if (ClInstrumentMemIntrinsics && SanitizeFunction)
362    for (auto Inst : MemIntrinCalls) {
363      Res |= instrumentMemIntrinsic(Inst);
364    }
365
366  // Instrument function entry/exit points if there were instrumented accesses.
367  if ((Res || HasCalls) && ClInstrumentFuncEntryExit) {
368    IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
369    Value *ReturnAddress = IRB.CreateCall(
370        Intrinsic::getDeclaration(F.getParent(), Intrinsic::returnaddress),
371        IRB.getInt32(0));
372    IRB.CreateCall(TsanFuncEntry, ReturnAddress);
373    for (auto RetInst : RetVec) {
374      IRBuilder<> IRBRet(RetInst);
375      IRBRet.CreateCall(TsanFuncExit);
376    }
377    Res = true;
378  }
379  return Res;
380}
381
382bool ThreadSanitizer::instrumentLoadOrStore(Instruction *I) {
383  IRBuilder<> IRB(I);
384  bool IsWrite = isa<StoreInst>(*I);
385  Value *Addr = IsWrite
386      ? cast<StoreInst>(I)->getPointerOperand()
387      : cast<LoadInst>(I)->getPointerOperand();
388  int Idx = getMemoryAccessFuncIndex(Addr);
389  if (Idx < 0)
390    return false;
391  if (IsWrite && isVtableAccess(I)) {
392    DEBUG(dbgs() << "  VPTR : " << *I << "\n");
393    Value *StoredValue = cast<StoreInst>(I)->getValueOperand();
394    // StoredValue may be a vector type if we are storing several vptrs at once.
395    // In this case, just take the first element of the vector since this is
396    // enough to find vptr races.
397    if (isa<VectorType>(StoredValue->getType()))
398      StoredValue = IRB.CreateExtractElement(
399          StoredValue, ConstantInt::get(IRB.getInt32Ty(), 0));
400    if (StoredValue->getType()->isIntegerTy())
401      StoredValue = IRB.CreateIntToPtr(StoredValue, IRB.getInt8PtrTy());
402    // Call TsanVptrUpdate.
403    IRB.CreateCall2(TsanVptrUpdate,
404                    IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
405                    IRB.CreatePointerCast(StoredValue, IRB.getInt8PtrTy()));
406    NumInstrumentedVtableWrites++;
407    return true;
408  }
409  if (!IsWrite && isVtableAccess(I)) {
410    IRB.CreateCall(TsanVptrLoad,
411                   IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()));
412    NumInstrumentedVtableReads++;
413    return true;
414  }
415  Value *OnAccessFunc = IsWrite ? TsanWrite[Idx] : TsanRead[Idx];
416  IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()));
417  if (IsWrite) NumInstrumentedWrites++;
418  else         NumInstrumentedReads++;
419  return true;
420}
421
422static ConstantInt *createOrdering(IRBuilder<> *IRB, AtomicOrdering ord) {
423  uint32_t v = 0;
424  switch (ord) {
425    case NotAtomic:              assert(false);
426    case Unordered:              // Fall-through.
427    case Monotonic:              v = 0; break;
428    // case Consume:                v = 1; break;  // Not specified yet.
429    case Acquire:                v = 2; break;
430    case Release:                v = 3; break;
431    case AcquireRelease:         v = 4; break;
432    case SequentiallyConsistent: v = 5; break;
433  }
434  return IRB->getInt32(v);
435}
436
437// If a memset intrinsic gets inlined by the code gen, we will miss races on it.
438// So, we either need to ensure the intrinsic is not inlined, or instrument it.
439// We do not instrument memset/memmove/memcpy intrinsics (too complicated),
440// instead we simply replace them with regular function calls, which are then
441// intercepted by the run-time.
442// Since tsan is running after everyone else, the calls should not be
443// replaced back with intrinsics. If that becomes wrong at some point,
444// we will need to call e.g. __tsan_memset to avoid the intrinsics.
445bool ThreadSanitizer::instrumentMemIntrinsic(Instruction *I) {
446  IRBuilder<> IRB(I);
447  if (MemSetInst *M = dyn_cast<MemSetInst>(I)) {
448    IRB.CreateCall3(MemsetFn,
449      IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()),
450      IRB.CreateIntCast(M->getArgOperand(1), IRB.getInt32Ty(), false),
451      IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false));
452    I->eraseFromParent();
453  } else if (MemTransferInst *M = dyn_cast<MemTransferInst>(I)) {
454    IRB.CreateCall3(isa<MemCpyInst>(M) ? MemcpyFn : MemmoveFn,
455      IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()),
456      IRB.CreatePointerCast(M->getArgOperand(1), IRB.getInt8PtrTy()),
457      IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false));
458    I->eraseFromParent();
459  }
460  return false;
461}
462
463// Both llvm and ThreadSanitizer atomic operations are based on C++11/C1x
464// standards.  For background see C++11 standard.  A slightly older, publicly
465// available draft of the standard (not entirely up-to-date, but close enough
466// for casual browsing) is available here:
467// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf
468// The following page contains more background information:
469// http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/
470
471bool ThreadSanitizer::instrumentAtomic(Instruction *I) {
472  IRBuilder<> IRB(I);
473  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
474    Value *Addr = LI->getPointerOperand();
475    int Idx = getMemoryAccessFuncIndex(Addr);
476    if (Idx < 0)
477      return false;
478    const size_t ByteSize = 1 << Idx;
479    const size_t BitSize = ByteSize * 8;
480    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
481    Type *PtrTy = Ty->getPointerTo();
482    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
483                     createOrdering(&IRB, LI->getOrdering())};
484    CallInst *C = CallInst::Create(TsanAtomicLoad[Idx],
485                                   ArrayRef<Value*>(Args));
486    ReplaceInstWithInst(I, C);
487
488  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
489    Value *Addr = SI->getPointerOperand();
490    int Idx = getMemoryAccessFuncIndex(Addr);
491    if (Idx < 0)
492      return false;
493    const size_t ByteSize = 1 << Idx;
494    const size_t BitSize = ByteSize * 8;
495    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
496    Type *PtrTy = Ty->getPointerTo();
497    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
498                     IRB.CreateIntCast(SI->getValueOperand(), Ty, false),
499                     createOrdering(&IRB, SI->getOrdering())};
500    CallInst *C = CallInst::Create(TsanAtomicStore[Idx],
501                                   ArrayRef<Value*>(Args));
502    ReplaceInstWithInst(I, C);
503  } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) {
504    Value *Addr = RMWI->getPointerOperand();
505    int Idx = getMemoryAccessFuncIndex(Addr);
506    if (Idx < 0)
507      return false;
508    Function *F = TsanAtomicRMW[RMWI->getOperation()][Idx];
509    if (!F)
510      return false;
511    const size_t ByteSize = 1 << Idx;
512    const size_t BitSize = ByteSize * 8;
513    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
514    Type *PtrTy = Ty->getPointerTo();
515    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
516                     IRB.CreateIntCast(RMWI->getValOperand(), Ty, false),
517                     createOrdering(&IRB, RMWI->getOrdering())};
518    CallInst *C = CallInst::Create(F, ArrayRef<Value*>(Args));
519    ReplaceInstWithInst(I, C);
520  } else if (AtomicCmpXchgInst *CASI = dyn_cast<AtomicCmpXchgInst>(I)) {
521    Value *Addr = CASI->getPointerOperand();
522    int Idx = getMemoryAccessFuncIndex(Addr);
523    if (Idx < 0)
524      return false;
525    const size_t ByteSize = 1 << Idx;
526    const size_t BitSize = ByteSize * 8;
527    Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
528    Type *PtrTy = Ty->getPointerTo();
529    Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
530                     IRB.CreateIntCast(CASI->getCompareOperand(), Ty, false),
531                     IRB.CreateIntCast(CASI->getNewValOperand(), Ty, false),
532                     createOrdering(&IRB, CASI->getSuccessOrdering()),
533                     createOrdering(&IRB, CASI->getFailureOrdering())};
534    CallInst *C = IRB.CreateCall(TsanAtomicCAS[Idx], Args);
535    Value *Success = IRB.CreateICmpEQ(C, CASI->getCompareOperand());
536
537    Value *Res = IRB.CreateInsertValue(UndefValue::get(CASI->getType()), C, 0);
538    Res = IRB.CreateInsertValue(Res, Success, 1);
539
540    I->replaceAllUsesWith(Res);
541    I->eraseFromParent();
542  } else if (FenceInst *FI = dyn_cast<FenceInst>(I)) {
543    Value *Args[] = {createOrdering(&IRB, FI->getOrdering())};
544    Function *F = FI->getSynchScope() == SingleThread ?
545        TsanAtomicSignalFence : TsanAtomicThreadFence;
546    CallInst *C = CallInst::Create(F, ArrayRef<Value*>(Args));
547    ReplaceInstWithInst(I, C);
548  }
549  return true;
550}
551
552int ThreadSanitizer::getMemoryAccessFuncIndex(Value *Addr) {
553  Type *OrigPtrTy = Addr->getType();
554  Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
555  assert(OrigTy->isSized());
556  uint32_t TypeSize = DL->getTypeStoreSizeInBits(OrigTy);
557  if (TypeSize != 8  && TypeSize != 16 &&
558      TypeSize != 32 && TypeSize != 64 && TypeSize != 128) {
559    NumAccessesWithBadSize++;
560    // Ignore all unusual sizes.
561    return -1;
562  }
563  size_t Idx = countTrailingZeros(TypeSize / 8);
564  assert(Idx < kNumberOfAccessSizes);
565  return Idx;
566}
567