ThreadSanitizer.cpp revision 261991
1175383Sjhb//===-- ThreadSanitizer.cpp - race detector -------------------------------===// 2175383Sjhb// 3175383Sjhb// The LLVM Compiler Infrastructure 4175383Sjhb// 5175383Sjhb// This file is distributed under the University of Illinois Open Source 6175383Sjhb// License. See LICENSE.TXT for details. 7175383Sjhb// 8175383Sjhb//===----------------------------------------------------------------------===// 9175383Sjhb// 10175383Sjhb// This file is a part of ThreadSanitizer, a race detector. 11175383Sjhb// 12175383Sjhb// The tool is under development, for the details about previous versions see 13175383Sjhb// http://code.google.com/p/data-race-test 14175383Sjhb// 15175383Sjhb// The instrumentation phase is quite simple: 16175383Sjhb// - Insert calls to run-time library before every memory access. 17175383Sjhb// - Optimizations may apply to avoid instrumenting some of the accesses. 18175383Sjhb// - Insert calls at function entry/exit. 19175383Sjhb// The rest is handled by the run-time library. 20175383Sjhb//===----------------------------------------------------------------------===// 21175383Sjhb 22175383Sjhb#define DEBUG_TYPE "tsan" 23175383Sjhb 24175383Sjhb#include "llvm/Transforms/Instrumentation.h" 25175383Sjhb#include "llvm/ADT/SmallSet.h" 26175383Sjhb#include "llvm/ADT/SmallString.h" 27175383Sjhb#include "llvm/ADT/SmallVector.h" 28175383Sjhb#include "llvm/ADT/Statistic.h" 29175383Sjhb#include "llvm/ADT/StringExtras.h" 30175383Sjhb#include "llvm/IR/DataLayout.h" 31175383Sjhb#include "llvm/IR/Function.h" 32175383Sjhb#include "llvm/IR/IRBuilder.h" 33175383Sjhb#include "llvm/IR/IntrinsicInst.h" 34175383Sjhb#include "llvm/IR/Intrinsics.h" 35175383Sjhb#include "llvm/IR/LLVMContext.h" 36175383Sjhb#include "llvm/IR/Metadata.h" 37175383Sjhb#include "llvm/IR/Module.h" 38175383Sjhb#include "llvm/IR/Type.h" 39289437Sngie#include "llvm/Support/CommandLine.h" 40175383Sjhb#include "llvm/Support/Debug.h" 41175383Sjhb#include "llvm/Support/MathExtras.h" 42175383Sjhb#include "llvm/Support/raw_ostream.h" 43175383Sjhb#include "llvm/Transforms/Utils/BasicBlockUtils.h" 44175383Sjhb#include "llvm/Transforms/Utils/ModuleUtils.h" 45289437Sngie#include "llvm/Transforms/Utils/SpecialCaseList.h" 46175383Sjhb 47289437Sngieusing namespace llvm; 48289437Sngie 49175383Sjhbstatic cl::opt<std::string> ClBlacklistFile("tsan-blacklist", 50289437Sngie cl::desc("Blacklist file"), cl::Hidden); 51289437Sngiestatic cl::opt<bool> ClInstrumentMemoryAccesses( 52289437Sngie "tsan-instrument-memory-accesses", cl::init(true), 53289437Sngie cl::desc("Instrument memory accesses"), cl::Hidden); 54298304Sngiestatic cl::opt<bool> ClInstrumentFuncEntryExit( 55298304Sngie "tsan-instrument-func-entry-exit", cl::init(true), 56289437Sngie cl::desc("Instrument function entry and exit"), cl::Hidden); 57289437Sngiestatic cl::opt<bool> ClInstrumentAtomics( 58289437Sngie "tsan-instrument-atomics", cl::init(true), 59289437Sngie cl::desc("Instrument atomics"), cl::Hidden); 60289437Sngiestatic cl::opt<bool> ClInstrumentMemIntrinsics( 61289437Sngie "tsan-instrument-memintrinsics", cl::init(true), 62289437Sngie cl::desc("Instrument memintrinsics (memset/memcpy/memmove)"), cl::Hidden); 63175383Sjhb 64175383SjhbSTATISTIC(NumInstrumentedReads, "Number of instrumented reads"); 65175383SjhbSTATISTIC(NumInstrumentedWrites, "Number of instrumented writes"); 66175383SjhbSTATISTIC(NumOmittedReadsBeforeWrite, 67175383Sjhb "Number of reads ignored due to following writes"); 68175383SjhbSTATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size"); 69175383SjhbSTATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes"); 70175383SjhbSTATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads"); 71175383SjhbSTATISTIC(NumOmittedReadsFromConstantGlobals, 72289437Sngie "Number of reads from constant globals"); 73289437SngieSTATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads"); 74289437Sngie 75289437Sngienamespace { 76175383Sjhb 77175383Sjhb/// ThreadSanitizer: instrument the code in module to find races. 78175383Sjhbstruct ThreadSanitizer : public FunctionPass { 79175383Sjhb ThreadSanitizer(StringRef BlacklistFile = StringRef()) 80175383Sjhb : FunctionPass(ID), 81175383Sjhb TD(0), 82175383Sjhb BlacklistFile(BlacklistFile.empty() ? ClBlacklistFile 83175383Sjhb : BlacklistFile) { } 84175383Sjhb const char *getPassName() const; 85289437Sngie bool runOnFunction(Function &F); 86289437Sngie bool doInitialization(Module &M); 87289437Sngie static char ID; // Pass identification, replacement for typeid. 88289437Sngie 89175383Sjhb private: 90175383Sjhb void initializeCallbacks(Module &M); 91175383Sjhb bool instrumentLoadOrStore(Instruction *I); 92175383Sjhb bool instrumentAtomic(Instruction *I); 93175383Sjhb bool instrumentMemIntrinsic(Instruction *I); 94175383Sjhb void chooseInstructionsToInstrument(SmallVectorImpl<Instruction*> &Local, 95175383Sjhb SmallVectorImpl<Instruction*> &All); 96175383Sjhb bool addrPointsToConstantData(Value *Addr); 97175383Sjhb int getMemoryAccessFuncIndex(Value *Addr); 98175383Sjhb 99298304Sngie DataLayout *TD; 100175383Sjhb Type *IntptrTy; 101289437Sngie SmallString<64> BlacklistFile; 102289437Sngie OwningPtr<SpecialCaseList> BL; 103298304Sngie IntegerType *OrdTy; 104298304Sngie // Callbacks to run-time library are computed in doInitialization. 105289437Sngie Function *TsanFuncEntry; 106175383Sjhb Function *TsanFuncExit; 107289437Sngie // Accesses sizes are powers of two: 1, 2, 4, 8, 16. 108289437Sngie static const size_t kNumberOfAccessSizes = 5; 109289437Sngie Function *TsanRead[kNumberOfAccessSizes]; 110175383Sjhb Function *TsanWrite[kNumberOfAccessSizes]; 111289437Sngie Function *TsanAtomicLoad[kNumberOfAccessSizes]; 112289441Sngie Function *TsanAtomicStore[kNumberOfAccessSizes]; 113298304Sngie Function *TsanAtomicRMW[AtomicRMWInst::LAST_BINOP + 1][kNumberOfAccessSizes]; 114289441Sngie Function *TsanAtomicCAS[kNumberOfAccessSizes]; 115175383Sjhb Function *TsanAtomicThreadFence; 116298304Sngie Function *TsanAtomicSignalFence; 117289437Sngie Function *TsanVptrUpdate; 118289441Sngie Function *TsanVptrLoad; 119175383Sjhb Function *MemmoveFn, *MemcpyFn, *MemsetFn; 120175383Sjhb}; 121298304Sngie} // namespace 122298304Sngie 123175383Sjhbchar ThreadSanitizer::ID = 0; 124175383SjhbINITIALIZE_PASS(ThreadSanitizer, "tsan", 125175383Sjhb "ThreadSanitizer: detects data races.", 126175383Sjhb false, false) 127289437Sngie 128289437Sngieconst char *ThreadSanitizer::getPassName() const { 129175383Sjhb return "ThreadSanitizer"; 130175383Sjhb} 131298304Sngie 132175383SjhbFunctionPass *llvm::createThreadSanitizerPass(StringRef BlacklistFile) { 133298304Sngie return new ThreadSanitizer(BlacklistFile); 134298304Sngie} 135175383Sjhb 136175383Sjhbstatic Function *checkInterfaceFunction(Constant *FuncOrBitcast) { 137298304Sngie if (Function *F = dyn_cast<Function>(FuncOrBitcast)) 138289441Sngie return F; 139289441Sngie FuncOrBitcast->dump(); 140175383Sjhb report_fatal_error("ThreadSanitizer interface function redefined"); 141289441Sngie} 142289441Sngie 143175383Sjhbvoid ThreadSanitizer::initializeCallbacks(Module &M) { 144175383Sjhb IRBuilder<> IRB(M.getContext()); 145298304Sngie // Initialize the callbacks. 146298304Sngie TsanFuncEntry = checkInterfaceFunction(M.getOrInsertFunction( 147175383Sjhb "__tsan_func_entry", IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL)); 148289441Sngie TsanFuncExit = checkInterfaceFunction(M.getOrInsertFunction( 149289441Sngie "__tsan_func_exit", IRB.getVoidTy(), NULL)); 150175383Sjhb OrdTy = IRB.getInt32Ty(); 151175383Sjhb for (size_t i = 0; i < kNumberOfAccessSizes; ++i) { 152289437Sngie const size_t ByteSize = 1 << i; 153289437Sngie const size_t BitSize = ByteSize * 8; 154175383Sjhb SmallString<32> ReadName("__tsan_read" + itostr(ByteSize)); 155175383Sjhb TsanRead[i] = checkInterfaceFunction(M.getOrInsertFunction( 156298304Sngie ReadName, IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL)); 157175383Sjhb 158298304Sngie SmallString<32> WriteName("__tsan_write" + itostr(ByteSize)); 159298304Sngie TsanWrite[i] = checkInterfaceFunction(M.getOrInsertFunction( 160175383Sjhb WriteName, IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL)); 161175383Sjhb 162175383Sjhb Type *Ty = Type::getIntNTy(M.getContext(), BitSize); 163289437Sngie Type *PtrTy = Ty->getPointerTo(); 164289441Sngie SmallString<32> AtomicLoadName("__tsan_atomic" + itostr(BitSize) + 165289441Sngie "_load"); 166289441Sngie TsanAtomicLoad[i] = checkInterfaceFunction(M.getOrInsertFunction( 167298304Sngie AtomicLoadName, Ty, PtrTy, OrdTy, NULL)); 168289441Sngie 169289441Sngie SmallString<32> AtomicStoreName("__tsan_atomic" + itostr(BitSize) + 170175383Sjhb "_store"); 171289441Sngie TsanAtomicStore[i] = checkInterfaceFunction(M.getOrInsertFunction( 172289441Sngie AtomicStoreName, IRB.getVoidTy(), PtrTy, Ty, OrdTy, 173175383Sjhb NULL)); 174298304Sngie 175298304Sngie for (int op = AtomicRMWInst::FIRST_BINOP; 176175383Sjhb op <= AtomicRMWInst::LAST_BINOP; ++op) { 177289441Sngie TsanAtomicRMW[op][i] = NULL; 178289441Sngie const char *NamePart = NULL; 179175383Sjhb if (op == AtomicRMWInst::Xchg) 180175383Sjhb NamePart = "_exchange"; 181289437Sngie else if (op == AtomicRMWInst::Add) 182289437Sngie NamePart = "_fetch_add"; 183175383Sjhb else if (op == AtomicRMWInst::Sub) 184175383Sjhb NamePart = "_fetch_sub"; 185298304Sngie else if (op == AtomicRMWInst::And) 186175383Sjhb NamePart = "_fetch_and"; 187298304Sngie else if (op == AtomicRMWInst::Or) 188298304Sngie NamePart = "_fetch_or"; 189289437Sngie else if (op == AtomicRMWInst::Xor) 190289437Sngie NamePart = "_fetch_xor"; 191289437Sngie else if (op == AtomicRMWInst::Nand) 192289441Sngie NamePart = "_fetch_nand"; 193175383Sjhb else 194175383Sjhb continue; 195298304Sngie SmallString<32> RMWName("__tsan_atomic" + itostr(BitSize) + NamePart); 196289441Sngie TsanAtomicRMW[op][i] = checkInterfaceFunction(M.getOrInsertFunction( 197289441Sngie RMWName, Ty, PtrTy, Ty, OrdTy, NULL)); 198175383Sjhb } 199289441Sngie 200289441Sngie SmallString<32> AtomicCASName("__tsan_atomic" + itostr(BitSize) + 201289441Sngie "_compare_exchange_val"); 202289441Sngie TsanAtomicCAS[i] = checkInterfaceFunction(M.getOrInsertFunction( 203175383Sjhb AtomicCASName, Ty, PtrTy, Ty, Ty, OrdTy, OrdTy, NULL)); 204289441Sngie } 205289441Sngie TsanVptrUpdate = checkInterfaceFunction(M.getOrInsertFunction( 206175383Sjhb "__tsan_vptr_update", IRB.getVoidTy(), IRB.getInt8PtrTy(), 207175383Sjhb IRB.getInt8PtrTy(), NULL)); 208289437Sngie TsanVptrLoad = checkInterfaceFunction(M.getOrInsertFunction( 209289437Sngie "__tsan_vptr_read", IRB.getVoidTy(), IRB.getInt8PtrTy(), NULL)); 210175383Sjhb TsanAtomicThreadFence = checkInterfaceFunction(M.getOrInsertFunction( 211175383Sjhb "__tsan_atomic_thread_fence", IRB.getVoidTy(), OrdTy, NULL)); 212175383Sjhb TsanAtomicSignalFence = checkInterfaceFunction(M.getOrInsertFunction( 213289437Sngie "__tsan_atomic_signal_fence", IRB.getVoidTy(), OrdTy, NULL)); 214289437Sngie 215289437Sngie MemmoveFn = checkInterfaceFunction(M.getOrInsertFunction( 216289441Sngie "memmove", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), 217175383Sjhb IRB.getInt8PtrTy(), IntptrTy, NULL)); 218175383Sjhb MemcpyFn = checkInterfaceFunction(M.getOrInsertFunction( 219289441Sngie "memcpy", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), 220289441Sngie IntptrTy, NULL)); 221175383Sjhb MemsetFn = checkInterfaceFunction(M.getOrInsertFunction( 222289437Sngie "memset", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(), IRB.getInt32Ty(), 223175383Sjhb IntptrTy, NULL)); 224175383Sjhb} 225289437Sngie 226289437Sngiebool ThreadSanitizer::doInitialization(Module &M) { 227175383Sjhb TD = getAnalysisIfAvailable<DataLayout>(); 228175383Sjhb if (!TD) 229175383Sjhb return false; 230175383Sjhb BL.reset(SpecialCaseList::createOrDie(BlacklistFile)); 231175383Sjhb 232289437Sngie // Always insert a call to __tsan_init into the module's CTORs. 233289437Sngie IRBuilder<> IRB(M.getContext()); 234175383Sjhb IntptrTy = IRB.getIntPtrTy(TD); 235175383Sjhb Value *TsanInit = M.getOrInsertFunction("__tsan_init", 236289437Sngie IRB.getVoidTy(), NULL); 237289437Sngie appendToGlobalCtors(M, cast<Function>(TsanInit), 0); 238289437Sngie 239175383Sjhb return true; 240175383Sjhb} 241289437Sngie 242289437Sngiestatic bool isVtableAccess(Instruction *I) { 243175383Sjhb if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa)) 244175383Sjhb return Tag->isTBAAVtableAccess(); 245289437Sngie return false; 246289437Sngie} 247289437Sngie 248175383Sjhbbool ThreadSanitizer::addrPointsToConstantData(Value *Addr) { 249175383Sjhb // If this is a GEP, just analyze its pointer operand. 250289437Sngie if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr)) 251289437Sngie Addr = GEP->getPointerOperand(); 252175383Sjhb 253175383Sjhb if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) { 254175383Sjhb if (GV->isConstant()) { 255175383Sjhb // Reads from constant globals can not race with any writes. 256289441Sngie NumOmittedReadsFromConstantGlobals++; 257175383Sjhb return true; 258175383Sjhb } 259175383Sjhb } else if (LoadInst *L = dyn_cast<LoadInst>(Addr)) { 260289437Sngie if (isVtableAccess(L)) { 261289437Sngie // Reads from a vtable pointer can not race with any writes. 262175383Sjhb NumOmittedReadsFromVtable++; 263175383Sjhb return true; 264175383Sjhb } 265175383Sjhb } 266175383Sjhb return false; 267289437Sngie} 268289437Sngie 269175383Sjhb// Instrumenting some of the accesses may be proven redundant. 270175383Sjhb// Currently handled: 271175383Sjhb// - read-before-write (within same BB, no calls between) 272175383Sjhb// 273175383Sjhb// We do not handle some of the patterns that should not survive 274289437Sngie// after the classic compiler optimizations. 275289437Sngie// E.g. two reads from the same temp should be eliminated by CSE, 276175383Sjhb// two writes should be eliminated by DSE, etc. 277175383Sjhb// 278175383Sjhb// 'Local' is a vector of insns within the same BB (no calls between). 279175383Sjhb// 'All' is a vector of insns that will be instrumented. 280175383Sjhbvoid ThreadSanitizer::chooseInstructionsToInstrument( 281175383Sjhb SmallVectorImpl<Instruction*> &Local, 282175383Sjhb SmallVectorImpl<Instruction*> &All) { 283175383Sjhb SmallSet<Value*, 8> WriteTargets; 284175383Sjhb // Iterate from the end. 285175383Sjhb for (SmallVectorImpl<Instruction*>::reverse_iterator It = Local.rbegin(), 286289437Sngie E = Local.rend(); It != E; ++It) { 287289437Sngie Instruction *I = *It; 288175383Sjhb if (StoreInst *Store = dyn_cast<StoreInst>(I)) { 289175383Sjhb WriteTargets.insert(Store->getPointerOperand()); 290175383Sjhb } else { 291175383Sjhb LoadInst *Load = cast<LoadInst>(I); 292175383Sjhb Value *Addr = Load->getPointerOperand(); 293289437Sngie if (WriteTargets.count(Addr)) { 294289437Sngie // We will write to this temp, so no reason to analyze the read. 295175383Sjhb NumOmittedReadsBeforeWrite++; 296175383Sjhb continue; 297175383Sjhb } 298289437Sngie if (addrPointsToConstantData(Addr)) { 299289437Sngie // Addr points to some constant data -- it can not race with any writes. 300289437Sngie continue; 301289441Sngie } 302175383Sjhb } 303175383Sjhb All.push_back(I); 304289437Sngie } 305175383Sjhb Local.clear(); 306175383Sjhb} 307289441Sngie 308289441Sngiestatic bool isAtomic(Instruction *I) { 309175383Sjhb if (LoadInst *LI = dyn_cast<LoadInst>(I)) 310175383Sjhb return LI->isAtomic() && LI->getSynchScope() == CrossThread; 311289437Sngie if (StoreInst *SI = dyn_cast<StoreInst>(I)) 312289437Sngie return SI->isAtomic() && SI->getSynchScope() == CrossThread; 313175383Sjhb if (isa<AtomicRMWInst>(I)) 314175383Sjhb return true; 315175383Sjhb if (isa<AtomicCmpXchgInst>(I)) 316175383Sjhb return true; 317289437Sngie if (isa<FenceInst>(I)) 318289437Sngie return true; 319175383Sjhb return false; 320289437Sngie} 321289441Sngie 322289441Sngiebool ThreadSanitizer::runOnFunction(Function &F) { 323289441Sngie if (!TD) return false; 324289441Sngie if (BL->isIn(F)) return false; 325289441Sngie initializeCallbacks(*F.getParent()); 326289441Sngie SmallVector<Instruction*, 8> RetVec; 327175383Sjhb SmallVector<Instruction*, 8> AllLoadsAndStores; 328175383Sjhb SmallVector<Instruction*, 8> LocalLoadsAndStores; 329175383Sjhb SmallVector<Instruction*, 8> AtomicAccesses; 330289437Sngie SmallVector<Instruction*, 8> MemIntrinCalls; 331289441Sngie bool Res = false; 332289441Sngie bool HasCalls = false; 333289441Sngie 334289441Sngie // Traverse all instructions, collect loads/stores/returns, check for calls. 335289441Sngie for (Function::iterator FI = F.begin(), FE = F.end(); 336175383Sjhb FI != FE; ++FI) { 337289441Sngie BasicBlock &BB = *FI; 338289441Sngie for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); 339175383Sjhb BI != BE; ++BI) { 340175383Sjhb if (isAtomic(BI)) 341289437Sngie AtomicAccesses.push_back(BI); 342289437Sngie else if (isa<LoadInst>(BI) || isa<StoreInst>(BI)) 343175383Sjhb LocalLoadsAndStores.push_back(BI); 344175383Sjhb else if (isa<ReturnInst>(BI)) 345175383Sjhb RetVec.push_back(BI); 346175383Sjhb else if (isa<CallInst>(BI) || isa<InvokeInst>(BI)) { 347175383Sjhb if (isa<MemIntrinsic>(BI)) 348289437Sngie MemIntrinCalls.push_back(BI); 349289437Sngie HasCalls = true; 350175383Sjhb chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores); 351175383Sjhb } 352175383Sjhb } 353175383Sjhb chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores); 354175383Sjhb } 355175383Sjhb 356175383Sjhb // We have collected all loads and stores. 357175383Sjhb // FIXME: many of these accesses do not need to be checked for races 358175383Sjhb // (e.g. variables that do not escape, etc). 359175383Sjhb 360289437Sngie // Instrument memory accesses. 361289437Sngie if (ClInstrumentMemoryAccesses && F.hasFnAttribute(Attribute::SanitizeThread)) 362175383Sjhb for (size_t i = 0, n = AllLoadsAndStores.size(); i < n; ++i) { 363175383Sjhb Res |= instrumentLoadOrStore(AllLoadsAndStores[i]); 364175383Sjhb } 365298304Sngie 366298304Sngie // Instrument atomic memory accesses. 367175383Sjhb if (ClInstrumentAtomics) 368298304Sngie for (size_t i = 0, n = AtomicAccesses.size(); i < n; ++i) { 369298304Sngie Res |= instrumentAtomic(AtomicAccesses[i]); 370175383Sjhb } 371289441Sngie 372289441Sngie if (ClInstrumentMemIntrinsics) 373289441Sngie for (size_t i = 0, n = MemIntrinCalls.size(); i < n; ++i) { 374175383Sjhb Res |= instrumentMemIntrinsic(MemIntrinCalls[i]); 375298304Sngie } 376289441Sngie 377289441Sngie // Instrument function entry/exit points if there were instrumented accesses. 378289441Sngie if ((Res || HasCalls) && ClInstrumentFuncEntryExit) { 379289441Sngie IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI()); 380289441Sngie Value *ReturnAddress = IRB.CreateCall( 381298304Sngie Intrinsic::getDeclaration(F.getParent(), Intrinsic::returnaddress), 382289441Sngie IRB.getInt32(0)); 383298304Sngie IRB.CreateCall(TsanFuncEntry, ReturnAddress); 384289441Sngie for (size_t i = 0, n = RetVec.size(); i < n; ++i) { 385175383Sjhb IRBuilder<> IRBRet(RetVec[i]); 386298304Sngie IRBRet.CreateCall(TsanFuncExit); 387289441Sngie } 388289437Sngie Res = true; 389175383Sjhb } 390175383Sjhb return Res; 391175383Sjhb} 392298304Sngie 393298304Sngiebool ThreadSanitizer::instrumentLoadOrStore(Instruction *I) { 394175383Sjhb IRBuilder<> IRB(I); 395175383Sjhb bool IsWrite = isa<StoreInst>(*I); 396298304Sngie Value *Addr = IsWrite 397289441Sngie ? cast<StoreInst>(I)->getPointerOperand() 398175383Sjhb : cast<LoadInst>(I)->getPointerOperand(); 399289441Sngie int Idx = getMemoryAccessFuncIndex(Addr); 400289441Sngie if (Idx < 0) 401289441Sngie return false; 402298304Sngie if (IsWrite && isVtableAccess(I)) { 403289441Sngie DEBUG(dbgs() << " VPTR : " << *I << "\n"); 404298304Sngie Value *StoredValue = cast<StoreInst>(I)->getValueOperand(); 405289441Sngie // StoredValue does not necessary have a pointer type. 406175383Sjhb if (isa<IntegerType>(StoredValue->getType())) 407298304Sngie StoredValue = IRB.CreateIntToPtr(StoredValue, IRB.getInt8PtrTy()); 408289441Sngie // Call TsanVptrUpdate. 409289441Sngie IRB.CreateCall2(TsanVptrUpdate, 410175383Sjhb IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()), 411289441Sngie IRB.CreatePointerCast(StoredValue, IRB.getInt8PtrTy())); 412289441Sngie NumInstrumentedVtableWrites++; 413175383Sjhb return true; 414175383Sjhb } 415298304Sngie if (!IsWrite && isVtableAccess(I)) { 416175383Sjhb IRB.CreateCall(TsanVptrLoad, 417175383Sjhb IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy())); 418298304Sngie NumInstrumentedVtableReads++; 419289441Sngie return true; 420175383Sjhb } 421289441Sngie Value *OnAccessFunc = IsWrite ? TsanWrite[Idx] : TsanRead[Idx]; 422289441Sngie IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy())); 423289441Sngie if (IsWrite) NumInstrumentedWrites++; 424298304Sngie else NumInstrumentedReads++; 425289441Sngie return true; 426298304Sngie} 427289441Sngie 428175383Sjhbstatic ConstantInt *createOrdering(IRBuilder<> *IRB, AtomicOrdering ord) { 429175383Sjhb uint32_t v = 0; 430175383Sjhb switch (ord) { 431175383Sjhb case NotAtomic: assert(false); 432175383Sjhb case Unordered: // Fall-through. 433289441Sngie case Monotonic: v = 0; break; 434289441Sngie // case Consume: v = 1; break; // Not specified yet. 435175383Sjhb case Acquire: v = 2; break; 436175383Sjhb case Release: v = 3; break; 437175383Sjhb case AcquireRelease: v = 4; break; 438175383Sjhb case SequentiallyConsistent: v = 5; break; 439175383Sjhb } 440175383Sjhb return IRB->getInt32(v); 441298304Sngie} 442175383Sjhb 443298304Sngiestatic ConstantInt *createFailOrdering(IRBuilder<> *IRB, AtomicOrdering ord) { 444175383Sjhb uint32_t v = 0; 445175383Sjhb switch (ord) { 446175383Sjhb case NotAtomic: assert(false); 447175383Sjhb case Unordered: // Fall-through. 448175383Sjhb case Monotonic: v = 0; break; 449175383Sjhb // case Consume: v = 1; break; // Not specified yet. 450298304Sngie case Acquire: v = 2; break; 451175383Sjhb case Release: v = 0; break; 452175383Sjhb case AcquireRelease: v = 2; break; 453175383Sjhb case SequentiallyConsistent: v = 5; break; 454289441Sngie } 455289441Sngie return IRB->getInt32(v); 456289441Sngie} 457289441Sngie 458289441Sngie// If a memset intrinsic gets inlined by the code gen, we will miss races on it. 459289437Sngie// So, we either need to ensure the intrinsic is not inlined, or instrument it. 460175383Sjhb// We do not instrument memset/memmove/memcpy intrinsics (too complicated), 461175383Sjhb// instead we simply replace them with regular function calls, which are then 462298304Sngie// intercepted by the run-time. 463289441Sngie// Since tsan is running after everyone else, the calls should not be 464175383Sjhb// replaced back with intrinsics. If that becomes wrong at some point, 465289441Sngie// we will need to call e.g. __tsan_memset to avoid the intrinsics. 466289441Sngiebool ThreadSanitizer::instrumentMemIntrinsic(Instruction *I) { 467289441Sngie IRBuilder<> IRB(I); 468298304Sngie if (MemSetInst *M = dyn_cast<MemSetInst>(I)) { 469289441Sngie IRB.CreateCall3(MemsetFn, 470298304Sngie IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()), 471289441Sngie IRB.CreateIntCast(M->getArgOperand(1), IRB.getInt32Ty(), false), 472175383Sjhb IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false)); 473175383Sjhb I->eraseFromParent(); 474175383Sjhb } else if (MemTransferInst *M = dyn_cast<MemTransferInst>(I)) { 475175383Sjhb IRB.CreateCall3(isa<MemCpyInst>(M) ? MemcpyFn : MemmoveFn, 476175383Sjhb IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()), 477175383Sjhb IRB.CreatePointerCast(M->getArgOperand(1), IRB.getInt8PtrTy()), 478175383Sjhb IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false)); 479175383Sjhb I->eraseFromParent(); 480175383Sjhb } 481298304Sngie return false; 482289441Sngie} 483298304Sngie 484175383Sjhb// Both llvm and ThreadSanitizer atomic operations are based on C++11/C1x 485175383Sjhb// standards. For background see C++11 standard. A slightly older, publically 486175383Sjhb// available draft of the standard (not entirely up-to-date, but close enough 487175383Sjhb// for casual browsing) is available here: 488289437Sngie// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf 489289437Sngie// The following page contains more background information: 490289437Sngie// http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/ 491175383Sjhb 492289437Sngiebool ThreadSanitizer::instrumentAtomic(Instruction *I) { 493289437Sngie IRBuilder<> IRB(I); 494175383Sjhb if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 495289437Sngie Value *Addr = LI->getPointerOperand(); 496289437Sngie int Idx = getMemoryAccessFuncIndex(Addr); 497289437Sngie if (Idx < 0) 498289437Sngie return false; 499289437Sngie const size_t ByteSize = 1 << Idx; 500289437Sngie const size_t BitSize = ByteSize * 8; 501289437Sngie Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize); 502289437Sngie Type *PtrTy = Ty->getPointerTo(); 503289437Sngie Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy), 504289437Sngie createOrdering(&IRB, LI->getOrdering())}; 505289437Sngie CallInst *C = CallInst::Create(TsanAtomicLoad[Idx], 506289437Sngie ArrayRef<Value*>(Args)); 507289437Sngie ReplaceInstWithInst(I, C); 508289437Sngie 509289437Sngie } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 510289437Sngie Value *Addr = SI->getPointerOperand(); 511289437Sngie int Idx = getMemoryAccessFuncIndex(Addr); 512289437Sngie if (Idx < 0) 513289437Sngie return false; 514289437Sngie const size_t ByteSize = 1 << Idx; 515289437Sngie const size_t BitSize = ByteSize * 8; 516289437Sngie Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize); 517289437Sngie Type *PtrTy = Ty->getPointerTo(); 518289437Sngie Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy), 519289437Sngie IRB.CreateIntCast(SI->getValueOperand(), Ty, false), 520289437Sngie createOrdering(&IRB, SI->getOrdering())}; 521289437Sngie CallInst *C = CallInst::Create(TsanAtomicStore[Idx], 522289437Sngie ArrayRef<Value*>(Args)); 523289437Sngie ReplaceInstWithInst(I, C); 524289437Sngie } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) { 525289437Sngie Value *Addr = RMWI->getPointerOperand(); 526289437Sngie int Idx = getMemoryAccessFuncIndex(Addr); 527289437Sngie if (Idx < 0) 528289437Sngie return false; 529289437Sngie Function *F = TsanAtomicRMW[RMWI->getOperation()][Idx]; 530298304Sngie if (F == NULL) 531289437Sngie return false; 532289437Sngie const size_t ByteSize = 1 << Idx; 533289437Sngie const size_t BitSize = ByteSize * 8; 534289437Sngie Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize); 535289437Sngie Type *PtrTy = Ty->getPointerTo(); 536289437Sngie Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy), 537289437Sngie IRB.CreateIntCast(RMWI->getValOperand(), Ty, false), 538289437Sngie createOrdering(&IRB, RMWI->getOrdering())}; 539289437Sngie CallInst *C = CallInst::Create(F, ArrayRef<Value*>(Args)); 540289437Sngie ReplaceInstWithInst(I, C); 541289437Sngie } else if (AtomicCmpXchgInst *CASI = dyn_cast<AtomicCmpXchgInst>(I)) { 542289437Sngie Value *Addr = CASI->getPointerOperand(); 543289437Sngie int Idx = getMemoryAccessFuncIndex(Addr); 544289437Sngie if (Idx < 0) 545289437Sngie return false; 546289437Sngie const size_t ByteSize = 1 << Idx; 547289437Sngie const size_t BitSize = ByteSize * 8; 548298304Sngie Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize); 549289437Sngie Type *PtrTy = Ty->getPointerTo(); 550289437Sngie Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy), 551289437Sngie IRB.CreateIntCast(CASI->getCompareOperand(), Ty, false), 552289437Sngie IRB.CreateIntCast(CASI->getNewValOperand(), Ty, false), 553289437Sngie createOrdering(&IRB, CASI->getOrdering()), 554289437Sngie createFailOrdering(&IRB, CASI->getOrdering())}; 555289437Sngie CallInst *C = CallInst::Create(TsanAtomicCAS[Idx], ArrayRef<Value*>(Args)); 556289437Sngie ReplaceInstWithInst(I, C); 557289437Sngie } else if (FenceInst *FI = dyn_cast<FenceInst>(I)) { 558289437Sngie Value *Args[] = {createOrdering(&IRB, FI->getOrdering())}; 559289437Sngie Function *F = FI->getSynchScope() == SingleThread ? 560289437Sngie TsanAtomicSignalFence : TsanAtomicThreadFence; 561289437Sngie CallInst *C = CallInst::Create(F, ArrayRef<Value*>(Args)); 562289437Sngie ReplaceInstWithInst(I, C); 563289437Sngie } 564289437Sngie return true; 565289437Sngie} 566289437Sngie 567289437Sngieint ThreadSanitizer::getMemoryAccessFuncIndex(Value *Addr) { 568289437Sngie Type *OrigPtrTy = Addr->getType(); 569289437Sngie Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType(); 570289437Sngie assert(OrigTy->isSized()); 571289437Sngie uint32_t TypeSize = TD->getTypeStoreSizeInBits(OrigTy); 572289437Sngie if (TypeSize != 8 && TypeSize != 16 && 573289437Sngie TypeSize != 32 && TypeSize != 64 && TypeSize != 128) { 574289437Sngie NumAccessesWithBadSize++; 575289437Sngie // Ignore all unusual sizes. 576289437Sngie return -1; 577289437Sngie } 578289437Sngie size_t Idx = countTrailingZeros(TypeSize / 8); 579289437Sngie assert(Idx < kNumberOfAccessSizes); 580289437Sngie return Idx; 581289437Sngie} 582289437Sngie