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