1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
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<TargetData>();
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<Function>(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<Instruction*, 8> RetVec;
SmallVector<Instruction*, 8> 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<LoadInst>(BI) || isa<StoreInst>(BI))
LoadsAndStores.push_back(BI);
else if (isa<ReturnInst>(BI))
RetVec.push_back(BI);
else if (isa<CallInst>(BI) || isa<InvokeInst>(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<StoreInst>(*I);
Value *Addr = IsWrite
? cast<StoreInst>(I)->getPointerOperand()
: cast<LoadInst>(I)->getPointerOperand();
Type *OrigPtrTy = Addr->getType();
Type *OrigTy = cast<PointerType>(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;
}
|
