From 60ebb1947faed42e493179e569c5db0c01d38a2a Mon Sep 17 00:00:00 2001 From: Kostya Serebryany Date: Mon, 13 Feb 2012 22:50:51 +0000 Subject: ThreadSanitizer, a race detector. First LLVM commit. Clang patch (flags) will follow shortly. The run-time library will also follow, but not immediately. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150423 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/InitializePasses.h | 1 + include/llvm/Transforms/Instrumentation.h | 3 + lib/Transforms/Instrumentation/CMakeLists.txt | 1 + lib/Transforms/Instrumentation/Instrumentation.cpp | 1 + lib/Transforms/Instrumentation/ThreadSanitizer.cpp | 169 +++++++++++++++++++++ test/Instrumentation/ThreadSanitizer/dg.exp | 3 + test/Instrumentation/ThreadSanitizer/tsan_basic.ll | 22 +++ 7 files changed, 200 insertions(+) create mode 100644 lib/Transforms/Instrumentation/ThreadSanitizer.cpp create mode 100644 test/Instrumentation/ThreadSanitizer/dg.exp create mode 100644 test/Instrumentation/ThreadSanitizer/tsan_basic.ll diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index cf3c41ee4a..33d20435de 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -105,6 +105,7 @@ void initializeExpandPostRAPass(PassRegistry&); void initializePathProfilerPass(PassRegistry&); void initializeGCOVProfilerPass(PassRegistry&); void initializeAddressSanitizerPass(PassRegistry&); +void initializeThreadSanitizerPass(PassRegistry&); void initializeEarlyCSEPass(PassRegistry&); void initializeExpandISelPseudosPass(PassRegistry&); void initializeFindUsedTypesPass(PassRegistry&); diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h index baa6364f50..bbf3a69d24 100644 --- a/include/llvm/Transforms/Instrumentation.h +++ b/include/llvm/Transforms/Instrumentation.h @@ -17,6 +17,7 @@ namespace llvm { class ModulePass; +class FunctionPass; // Insert edge profiling instrumentation ModulePass *createEdgeProfilerPass(); @@ -34,6 +35,8 @@ ModulePass *createGCOVProfilerPass(bool EmitNotes = true, bool EmitData = true, // Insert AddressSanitizer (address sanity checking) instrumentation ModulePass *createAddressSanitizerPass(); +// Insert ThreadSanitizer (race detection) instrumentation +FunctionPass *createThreadSanitizerPass(); } // End llvm namespace diff --git a/lib/Transforms/Instrumentation/CMakeLists.txt b/lib/Transforms/Instrumentation/CMakeLists.txt index a4a1fef51f..f8dbca389e 100644 --- a/lib/Transforms/Instrumentation/CMakeLists.txt +++ b/lib/Transforms/Instrumentation/CMakeLists.txt @@ -6,4 +6,5 @@ add_llvm_library(LLVMInstrumentation OptimalEdgeProfiling.cpp PathProfiling.cpp ProfilingUtils.cpp + ThreadSanitizer.cpp ) diff --git a/lib/Transforms/Instrumentation/Instrumentation.cpp b/lib/Transforms/Instrumentation/Instrumentation.cpp index 6d6e0ae34b..c7266e2f8d 100644 --- a/lib/Transforms/Instrumentation/Instrumentation.cpp +++ b/lib/Transforms/Instrumentation/Instrumentation.cpp @@ -25,6 +25,7 @@ void llvm::initializeInstrumentation(PassRegistry &Registry) { initializePathProfilerPass(Registry); initializeGCOVProfilerPass(Registry); initializeAddressSanitizerPass(Registry); + initializeThreadSanitizerPass(Registry); } /// LLVMInitializeInstrumentation - C binding for diff --git a/lib/Transforms/Instrumentation/ThreadSanitizer.cpp b/lib/Transforms/Instrumentation/ThreadSanitizer.cpp new file mode 100644 index 0000000000..ab88d1c0b0 --- /dev/null +++ b/lib/Transforms/Instrumentation/ThreadSanitizer.cpp @@ -0,0 +1,169 @@ +//===-- ThreadSanitizer.cpp - race detector -------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file is a part of ThreadSanitizer, a race detector. +// +// The tool is under development, for the details about previous versions see +// http://code.google.com/p/data-race-test +// +// The instrumentation phase is quite simple: +// - Insert calls to run-time library before every memory access. +// - Optimizations may apply to avoid instrumenting some of the accesses. +// - Insert calls at function entry/exit. +// The rest is handled by the run-time library. +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "tsan" + +#include "llvm/ADT/SmallString.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/Intrinsics.h" +#include "llvm/Function.h" +#include "llvm/Module.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/IRBuilder.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Transforms/Instrumentation.h" +#include "llvm/Transforms/Utils/ModuleUtils.h" +#include "llvm/Type.h" + +using namespace llvm; + +namespace { +/// ThreadSanitizer: instrument the code in module to find races. +struct ThreadSanitizer : public FunctionPass { + ThreadSanitizer(); + bool runOnFunction(Function &F); + bool doInitialization(Module &M); + bool instrumentLoadOrStore(Instruction *I); + static char ID; // Pass identification, replacement for typeid. + + private: + TargetData *TD; + // Callbacks to run-time library are computed in doInitialization. + Value *TsanFuncEntry; + Value *TsanFuncExit; + // Accesses sizes are powers of two: 1, 2, 4, 8, 16. + static const int kNumberOfAccessSizes = 5; + Value *TsanRead[kNumberOfAccessSizes]; + Value *TsanWrite[kNumberOfAccessSizes]; +}; +} // namespace + +char ThreadSanitizer::ID = 0; +INITIALIZE_PASS(ThreadSanitizer, "tsan", + "ThreadSanitizer: detects data races.", + false, false) + +ThreadSanitizer::ThreadSanitizer() + : FunctionPass(ID), + TD(NULL) { +} + +FunctionPass *llvm::createThreadSanitizerPass() { + return new ThreadSanitizer(); +} + +bool ThreadSanitizer::doInitialization(Module &M) { + TD = getAnalysisIfAvailable(); + if (!TD) + return false; + // Always insert a call to __tsan_init into the module's CTORs. + IRBuilder<> IRB(M.getContext()); + Value *TsanInit = M.getOrInsertFunction("__tsan_init", + IRB.getVoidTy(), NULL); + appendToGlobalCtors(M, cast(TsanInit), 0); + + // Initialize the callbacks. + TsanFuncEntry = M.getOrInsertFunction("__tsan_func_entry", IRB.getVoidTy(), + IRB.getInt8PtrTy(), NULL); + TsanFuncExit = M.getOrInsertFunction("__tsan_func_exit", IRB.getVoidTy(), + NULL); + for (int i = 0; i < kNumberOfAccessSizes; ++i) { + SmallString<32> ReadName("__tsan_read"); + ReadName += itostr(1 << i); + TsanRead[i] = M.getOrInsertFunction(ReadName, IRB.getVoidTy(), + IRB.getInt8PtrTy(), NULL); + SmallString<32> WriteName("__tsan_write"); + WriteName += itostr(1 << i); + TsanWrite[i] = M.getOrInsertFunction(WriteName, IRB.getVoidTy(), + IRB.getInt8PtrTy(), NULL); + } + return true; +} + +bool ThreadSanitizer::runOnFunction(Function &F) { + if (!TD) return false; + SmallVector RetVec; + SmallVector LoadsAndStores; + bool Res = false; + bool HasCalls = false; + + // Traverse all instructions, collect loads/stores/returns, check for calls. + for (Function::iterator FI = F.begin(), FE = F.end(); + FI != FE; ++FI) { + BasicBlock &BB = *FI; + for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); + BI != BE; ++BI) { + if (isa(BI) || isa(BI)) + LoadsAndStores.push_back(BI); + else if (isa(BI)) + RetVec.push_back(BI); + else if (isa(BI) || isa(BI)) + HasCalls = true; + } + } + + // We have collected all loads and stores. + // FIXME: many of these accesses do not need to be checked for races + // (e.g. variables that do not escape, etc). + + // Instrument memory accesses. + for (size_t i = 0, n = LoadsAndStores.size(); i < n; ++i) { + Res |= instrumentLoadOrStore(LoadsAndStores[i]); + } + + // Instrument function entry/exit points if there were instrumented accesses. + if (Res || HasCalls) { + IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI()); + Value *ReturnAddress = IRB.CreateCall( + Intrinsic::getDeclaration(F.getParent(), Intrinsic::returnaddress), + IRB.getInt32(0)); + IRB.CreateCall(TsanFuncEntry, ReturnAddress); + for (size_t i = 0, n = RetVec.size(); i < n; ++i) { + IRBuilder<> IRBRet(RetVec[i]); + IRBRet.CreateCall(TsanFuncExit); + } + } + return Res; +} + +bool ThreadSanitizer::instrumentLoadOrStore(Instruction *I) { + IRBuilder<> IRB(I); + bool IsWrite = isa(*I); + Value *Addr = IsWrite + ? cast(I)->getPointerOperand() + : cast(I)->getPointerOperand(); + Type *OrigPtrTy = Addr->getType(); + Type *OrigTy = cast(OrigPtrTy)->getElementType(); + assert(OrigTy->isSized()); + uint32_t TypeSize = TD->getTypeStoreSizeInBits(OrigTy); + if (TypeSize != 8 && TypeSize != 16 && + TypeSize != 32 && TypeSize != 64 && TypeSize != 128) { + // Ignore all unusual sizes. + return false; + } + uint32_t Idx = CountTrailingZeros_32(TypeSize / 8); + assert(Idx < kNumberOfAccessSizes); + Value *OnAccessFunc = IsWrite ? TsanWrite[Idx] : TsanRead[Idx]; + IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy())); + return true; +} diff --git a/test/Instrumentation/ThreadSanitizer/dg.exp b/test/Instrumentation/ThreadSanitizer/dg.exp new file mode 100644 index 0000000000..f2005891a5 --- /dev/null +++ b/test/Instrumentation/ThreadSanitizer/dg.exp @@ -0,0 +1,3 @@ +load_lib llvm.exp + +RunLLVMTests [lsort [glob -nocomplain $srcdir/$subdir/*.{ll,c,cpp}]] diff --git a/test/Instrumentation/ThreadSanitizer/tsan_basic.ll b/test/Instrumentation/ThreadSanitizer/tsan_basic.ll new file mode 100644 index 0000000000..33c703b4c9 --- /dev/null +++ b/test/Instrumentation/ThreadSanitizer/tsan_basic.ll @@ -0,0 +1,22 @@ +; RUN: opt < %s -tsan -S | FileCheck %s + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" +target triple = "x86_64-unknown-linux-gnu" + +define i32 @read_4_bytes(i32* %a) { +entry: + %tmp1 = load i32* %a, align 4 + ret i32 %tmp1 +} + +; CHECK: @llvm.global_ctors = {{.*}}@__tsan_init + +; CHECK: define i32 @read_4_bytes(i32* %a) { +; CHECK: call void @__tsan_func_entry(i8* %0) +; CHECK-NEXT: %1 = bitcast i32* %a to i8* +; CHECK-NEXT: call void @__tsan_read4(i8* %1) +; CHECK-NEXT: %tmp1 = load i32* %a, align 4 +; CHECK-NEXT: call void @__tsan_func_exit() +; CHECK: ret i32 + + -- cgit v1.2.3