ThreadSanitizer.cpp revision 60ebb1947faed42e493179e569c5db0c01d38a2a
160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany//===-- ThreadSanitizer.cpp - race detector -------------------------------===// 260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// 360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// The LLVM Compiler Infrastructure 460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// 560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// This file is distributed under the University of Illinois Open Source 660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// License. See LICENSE.TXT for details. 760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// 860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany//===----------------------------------------------------------------------===// 960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// 1060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// This file is a part of ThreadSanitizer, a race detector. 1160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// 1260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// The tool is under development, for the details about previous versions see 1360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// http://code.google.com/p/data-race-test 1460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// 1560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// The instrumentation phase is quite simple: 1660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// - Insert calls to run-time library before every memory access. 1760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// - Optimizations may apply to avoid instrumenting some of the accesses. 1860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// - Insert calls at function entry/exit. 1960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany// The rest is handled by the run-time library. 2060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany//===----------------------------------------------------------------------===// 2160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 2260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#define DEBUG_TYPE "tsan" 2360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 2460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/ADT/SmallString.h" 2560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/ADT/SmallVector.h" 2660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/ADT/StringExtras.h" 2760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Intrinsics.h" 2860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Function.h" 2960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Module.h" 3060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Support/Debug.h" 3160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Support/IRBuilder.h" 3260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Support/MathExtras.h" 3360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Target/TargetData.h" 3460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Transforms/Instrumentation.h" 3560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Transforms/Utils/ModuleUtils.h" 3660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany#include "llvm/Type.h" 3760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 3860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryanyusing namespace llvm; 3960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 4060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryanynamespace { 4160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany/// ThreadSanitizer: instrument the code in module to find races. 4260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryanystruct ThreadSanitizer : public FunctionPass { 4360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany ThreadSanitizer(); 4460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany bool runOnFunction(Function &F); 4560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany bool doInitialization(Module &M); 4660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany bool instrumentLoadOrStore(Instruction *I); 4760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany static char ID; // Pass identification, replacement for typeid. 4860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 4960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany private: 5060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany TargetData *TD; 5160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // Callbacks to run-time library are computed in doInitialization. 5260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Value *TsanFuncEntry; 5360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Value *TsanFuncExit; 5460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // Accesses sizes are powers of two: 1, 2, 4, 8, 16. 5560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany static const int kNumberOfAccessSizes = 5; 5660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Value *TsanRead[kNumberOfAccessSizes]; 5760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Value *TsanWrite[kNumberOfAccessSizes]; 5860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany}; 5960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany} // namespace 6060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 6160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryanychar ThreadSanitizer::ID = 0; 6260ebb1947faed42e493179e569c5db0c01d38a2aKostya SerebryanyINITIALIZE_PASS(ThreadSanitizer, "tsan", 6360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany "ThreadSanitizer: detects data races.", 6460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany false, false) 6560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 6660ebb1947faed42e493179e569c5db0c01d38a2aKostya SerebryanyThreadSanitizer::ThreadSanitizer() 6760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany : FunctionPass(ID), 6860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany TD(NULL) { 6960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany} 7060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 7160ebb1947faed42e493179e569c5db0c01d38a2aKostya SerebryanyFunctionPass *llvm::createThreadSanitizerPass() { 7260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany return new ThreadSanitizer(); 7360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany} 7460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 7560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryanybool ThreadSanitizer::doInitialization(Module &M) { 7660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany TD = getAnalysisIfAvailable<TargetData>(); 7760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany if (!TD) 7860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany return false; 7960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // Always insert a call to __tsan_init into the module's CTORs. 8060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRBuilder<> IRB(M.getContext()); 8160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Value *TsanInit = M.getOrInsertFunction("__tsan_init", 8260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRB.getVoidTy(), NULL); 8360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany appendToGlobalCtors(M, cast<Function>(TsanInit), 0); 8460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 8560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // Initialize the callbacks. 8660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany TsanFuncEntry = M.getOrInsertFunction("__tsan_func_entry", IRB.getVoidTy(), 8760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRB.getInt8PtrTy(), NULL); 8860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany TsanFuncExit = M.getOrInsertFunction("__tsan_func_exit", IRB.getVoidTy(), 8960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany NULL); 9060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany for (int i = 0; i < kNumberOfAccessSizes; ++i) { 9160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany SmallString<32> ReadName("__tsan_read"); 9260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany ReadName += itostr(1 << i); 9360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany TsanRead[i] = M.getOrInsertFunction(ReadName, IRB.getVoidTy(), 9460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRB.getInt8PtrTy(), NULL); 9560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany SmallString<32> WriteName("__tsan_write"); 9660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany WriteName += itostr(1 << i); 9760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany TsanWrite[i] = M.getOrInsertFunction(WriteName, IRB.getVoidTy(), 9860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRB.getInt8PtrTy(), NULL); 9960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany } 10060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany return true; 10160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany} 10260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 10360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryanybool ThreadSanitizer::runOnFunction(Function &F) { 10460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany if (!TD) return false; 10560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany SmallVector<Instruction*, 8> RetVec; 10660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany SmallVector<Instruction*, 8> LoadsAndStores; 10760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany bool Res = false; 10860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany bool HasCalls = false; 10960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 11060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // Traverse all instructions, collect loads/stores/returns, check for calls. 11160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany for (Function::iterator FI = F.begin(), FE = F.end(); 11260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany FI != FE; ++FI) { 11360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany BasicBlock &BB = *FI; 11460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); 11560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany BI != BE; ++BI) { 11660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany if (isa<LoadInst>(BI) || isa<StoreInst>(BI)) 11760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany LoadsAndStores.push_back(BI); 11860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany else if (isa<ReturnInst>(BI)) 11960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany RetVec.push_back(BI); 12060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany else if (isa<CallInst>(BI) || isa<InvokeInst>(BI)) 12160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany HasCalls = true; 12260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany } 12360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany } 12460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 12560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // We have collected all loads and stores. 12660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // FIXME: many of these accesses do not need to be checked for races 12760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // (e.g. variables that do not escape, etc). 12860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 12960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // Instrument memory accesses. 13060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany for (size_t i = 0, n = LoadsAndStores.size(); i < n; ++i) { 13160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Res |= instrumentLoadOrStore(LoadsAndStores[i]); 13260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany } 13360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 13460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // Instrument function entry/exit points if there were instrumented accesses. 13560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany if (Res || HasCalls) { 13660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI()); 13760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Value *ReturnAddress = IRB.CreateCall( 13860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Intrinsic::getDeclaration(F.getParent(), Intrinsic::returnaddress), 13960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRB.getInt32(0)); 14060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRB.CreateCall(TsanFuncEntry, ReturnAddress); 14160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany for (size_t i = 0, n = RetVec.size(); i < n; ++i) { 14260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRBuilder<> IRBRet(RetVec[i]); 14360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRBRet.CreateCall(TsanFuncExit); 14460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany } 14560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany } 14660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany return Res; 14760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany} 14860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany 14960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryanybool ThreadSanitizer::instrumentLoadOrStore(Instruction *I) { 15060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRBuilder<> IRB(I); 15160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany bool IsWrite = isa<StoreInst>(*I); 15260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Value *Addr = IsWrite 15360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany ? cast<StoreInst>(I)->getPointerOperand() 15460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany : cast<LoadInst>(I)->getPointerOperand(); 15560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Type *OrigPtrTy = Addr->getType(); 15660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType(); 15760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany assert(OrigTy->isSized()); 15860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany uint32_t TypeSize = TD->getTypeStoreSizeInBits(OrigTy); 15960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany if (TypeSize != 8 && TypeSize != 16 && 16060ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany TypeSize != 32 && TypeSize != 64 && TypeSize != 128) { 16160ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany // Ignore all unusual sizes. 16260ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany return false; 16360ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany } 16460ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany uint32_t Idx = CountTrailingZeros_32(TypeSize / 8); 16560ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany assert(Idx < kNumberOfAccessSizes); 16660ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany Value *OnAccessFunc = IsWrite ? TsanWrite[Idx] : TsanRead[Idx]; 16760ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy())); 16860ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany return true; 16960ebb1947faed42e493179e569c5db0c01d38a2aKostya Serebryany} 170